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

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

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

Дерево решений (англ. 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] \beta_v : X \rightarrow D_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] D_v = \{0,1\} [/math]. Пример [math]\beta_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]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]

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

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

• Энтропийный критерий
• Критерий Джини

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

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

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

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

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

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

Ссылки

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