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

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

Определение:

Дерево решений (англ. decision tree, DT) — алгоритм классификации , задающийся деревом (связным ациклическим графом):

Множество вершин , [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]f_v = [f_j(x) \gt a_j][/math], где [math]f_j(x)[/math] - значение [math]j[/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)

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

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

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

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

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

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

Решающий лес
Бустинг над решающими деревьями

История

Ссылки

Classification and Regression Trees — лекции Cosma Shalizi, ноябрь 2009.

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