Дерево решений и случайный лес — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
'''Дерево решений''' (англ. ''decision tree, DT'') {{---}} алгоритм классификации <tex>a(x)</tex>, задающийся деревом (связным ациклическим графом):
 
'''Дерево решений''' (англ. ''decision tree, DT'') {{---}} алгоритм классификации <tex>a(x)</tex>, задающийся деревом (связным ациклическим графом):
 
* Множество вершин <tex> V = V_{внутр} \cup V_{лист} </tex>, <tex>v_0 \in V</tex> {{---}} корень дерева
 
* Множество вершин <tex> V = V_{внутр} \cup V_{лист} </tex>, <tex>v_0 \in V</tex> {{---}} корень дерева
−
* Для <tex>v \in V_{внутр}</tex> определены функции: <tex> f_v : X \rightarrow D_v </tex> и <tex> D_v : X \rightarrow V </tex>, <tex>D_v < \infty</tex>
+
* Для <tex>v \in V_{внутр}</tex> определены функции: <tex> f_v : X \rightarrow D_v </tex> и <tex> D_v : X \rightarrow V </tex>, <tex>|D_v| < \infty</tex>
 
* Для <tex>v \in V_{лист}</tex> определена метка класса <tex>y_v \in Y</tex>
 
* Для <tex>v \in V_{лист}</tex> определена метка класса <tex>y_v \in Y</tex>
 +
}}
 +
{{Определение
 +
|id=def1
 +
|neat =
 +
|definition=
 +
'''Бинарное решающее дерево''' {{---}}  частный случай дерева решений, для которого <tex> D_v = {0,1} </tex>.
 +
* Пример <tex>f_v = [f_j(x) > a_j]</tex>, где <tex>f_j(x)</tex> - значение <tex>j</tex>-ого признака объекта <tex>x \in X</tex>
 
}}
 
}}
 
[[Файл:BinDT1.jpg |300px|thumb|right|Классификация объекта <tex> x \in X </tex> бинарным решающим деревом]]
 
[[Файл:BinDT1.jpg |300px|thumb|right|Классификация объекта <tex> x \in X </tex> бинарным решающим деревом]]
Строка 17: Строка 24:
 
     <tex>v := S_v</tex>(<tex>f_v</tex>(x)) ;
 
     <tex>v := S_v</tex>(<tex>f_v</tex>(x)) ;
 
   '''return''' <tex>y_v</tex>
 
   '''return''' <tex>y_v</tex>
−
 
−
{{Определение
 
−
|id=def1
 
−
|neat =
 
−
|definition=
 
−
'''Бинарное решающее дерево''' {{---}}  это алгоритм классификации, задающийся бинарным деревом, в котором каждой внутренней вершине <tex> v \in V </tex> приписан предикат <tex> \beta_v : X \rightarrow {0, 1} </tex>, каждой терминальной вершине <tex> v \in V </tex> приписано имя класса <tex> c_v \in Y </tex>. При классификации объекта <tex> x \in X </tex> он проходит по дереву путь от корня до некоторого листа, в соответствии с Алгоритмом 1.5.
 
−
}}
 
  
  

Версия 16:05, 20 января 2019

Дерево решений

Определение:
Дерево решений (англ. decision tree, DT) — алгоритм классификации [math]a(x)[/math], задающийся деревом (связным ациклическим графом):
  • Множество вершин [math] V = V_{внутр} \cup V_{лист} [/math], [math]v_0 \in V[/math] — корень дерева
  • Для [math]v \in V_{внутр}[/math] определены функции: [math] f_v : X \rightarrow D_v [/math] и [math] D_v : X \rightarrow V [/math], [math]|D_v| \lt \infty[/math]
  • Для [math]v \in V_{лист}[/math] определена метка класса [math]y_v \in Y[/math]


Определение:
Бинарное решающее дерево — частный случай дерева решений, для которого [math] D_v = {0,1} [/math].
  • Пример [math]f_v = [f_j(x) \gt a_j][/math], где [math]f_j(x)[/math] - значение [math]j[/math]-ого признака объекта [math]x \in X[/math]
Классификация объекта [math] x \in X [/math] бинарным решающим деревом
Y classify(x):
  [math]v = v_0[/math]
  while [math]v \in V_{внутр}[/math]:
    [math]v := S_v[/math]([math]f_v[/math](x)) ;
  return [math]y_v[/math]


Основные определения

Простейший алгоритм синтеза дерева

Разновидности решающих деревьев

Тип задачи

Критерии ветвления

Критерии останова

Что находится во внутренних вершинах

Что находится в листьях

Передача информации между вершинами

  • (alternating decision tree)

Рецукция решающих деревьев

Оценивание вероятностей

Полужадный синтез

Алгоритмы построения решающих деревьев

Обобщающая способность решающих деревьев

Композиции решающих деревьев

История

Ссылки

Литература

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дерево_решений_и_случайный_лес&oldid=68578»