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

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

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

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

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

Бинарное решающее дерево — это алгоритм классификации, задающийся бинарным деревом, в котором каждой внутренней вершине приписан предикат , каждой терминальной вершине приписано имя класса . При классификации объекта он проходит по дереву путь от корня до некоторого листа, в соответствии с Алгоритмом 1.5.

Классификация объекта бинарным решающим деревом

void fix(int i):
  if d[i] == b
    d[i] = 0
    d[i + 1]++
  if d[i + 1] == b - 1:
    L'[i] = L'[i + 1]
  else
    L'[i] = i + 1

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

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

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

Тип задачи

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

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

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

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

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

(alternating decision tree)

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

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

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

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

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

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

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

История

Ссылки

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

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