Дерево решений и случайный лес

Материал из Викиконспекты
Перейти к: навигация, поиск

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

Определение:
Дерево решений (англ. 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]


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

Идея алгоритма [math]ID3[/math] (англ. Induction of Decision Tree) заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Проще всего записать этот алгоритм в виде рекурсивной процедуры [math]TreeGrowing[/math], которая строит дерево по заданной подвыборке [math]U[/math] и возвращает его корневую вершину. TODO: возможные StopCriterion, Major

V TreeGrowing([math]U[/math]):
  if StopCriterion([math]U[/math])then
     return новый лист [math]v[/math], взяв [math]y_v[/math] := Major([math]U[/math])
  выбрать признак, наиболее выгодный для ветвления дерева: 
     [math]f_v = \mathrm{arg}\max_{f\in F} [/math] Gain([math]f[/math], [math]U[/math])
  if Gain([math]f_v[/math], [math]U[/math]) [math] \lt  G_0[/math] then
     return новый лист [math]v[/math] взяв [math]y_v[/math] := Major([math]U[/math])
  создать новую внутреннюю вершину [math]v[/math] с функцией [math]f_v[/math]
  for ([math]k \in D_v[/math]):
     [math]U_k := \{x \in U: f_v(x) = k\}[/math]
     [math]S_v(k)[/math] := TreeGrowing([math]U_k[/math])
  return [math]v[/math]

Мера неопределенности распределения

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

Критейрий Джини

Энтропийный критерий

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

Тип задачи

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

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

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

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

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

  • (alternating decision tree)

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

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

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

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

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

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

История

Ссылки

Литература