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

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

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

Дерево решений (англ. 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)

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

• Предредукция
• Постредукция

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

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

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

• Алгоритм ID3
• Алгоритм C4.5
• Алгоритм C5.0
• Алгоритм CART
• Алгоритм LISTBB

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

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

Ссылки

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