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

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

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

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

Множество вершин , [math]v_0 \in V[/math] — корень дерева
Для [math]v \in V_{внутр}[/math] определены предикат ветвления: , [math]|D_v| \lt \infty[/math] и функция перехода в следующую вершину по значению предиката [math] S_v : D_v \rightarrow V [/math],
Для [math]v \in V_{лист}[/math] определена метка класса [math]y_v \in Y[/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]ID3[/math], которая строит дерево по заданной подвыборке [math]U[/math] и возвращает его корневую вершину.

V ID3([math]U[/math]):
  if все объекты множества [math]U[/math] принадлежат одному классу [math]y \in Y[/math] then
     создать новый лист [math]v[/math] 
     [math]y_v = y[/math]
     return v
  найти предикат с максимальной информативностью:
     [math]\beta= \mathrm{arg}\max_{f\in F} [/math] Gain([math]f[/math], [math]U[/math])
  разбить выборку на две части [math]U = U_0 \cup U_1[/math] по предикату [math]\beta[/math]:
     [math]U_0 := \{x \in U: f_v(x) = 0\}[/math]
     [math]U_1 := \{x \in U: f_v(x) = 1\}[/math]
  if [math]U_0 = \emptyset[/math] или [math]U_1 = \emptyset[/math] 
     then
     создать новый лист [math]v[/math]
     [math]y_v[/math] = класс, в котором находится большинство объектов из [math]U[/math]
     else
     создать новую внутреннюю вершину [math]v[/math]
     [math]\beta_v = \beta[/math]
     [math]S_0[/math] = ID3([math]U_0[/math])
     [math]S_1[/math] = ID3([math]U_1[/math])
  return [math]v[/math]

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

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

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

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

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

Рекурсию останавливают в следующих случаях:

Все объекты множества [math]U[/math] принадлежат одному классу [math]y \in Y[/math], тогда создается лист [math]v[/math] с меткой класса [math]y_v = y[/math]

Деревья регрессии

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

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

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

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

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

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

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

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

История

Ссылки

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

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