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

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

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

Дерево решений (англ. 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] бинарным решающим деревом

function classify(x):
  [math]v = v_0[/math]
  if [math]\beta_v(x) = 1 [/math] then
     [math]v := R_v[/math]
  else
     [math]v := L_v[/math]
  return [math]y_v[/math]

Рекурсивный алгоритм построения бинарного дерева решений ID3

Идея алгоритма [math]ID3[/math] (англ. Induction of Decision Tree) заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Разделение производится по предикату [math]\beta[/math], который выбирается из множества элементарных предикатов. На практике в качестве элементарных предикатов чаще всего берут простые пороговые условия вида [math]\beta(x) = [f_j(x) \gt = d_j][/math].

Проще всего записать этот алгоритм в виде рекурсивной процедуры [math]ID3[/math], которая строит дерево по заданной подвыборке [math]U[/math] и возвращает его корневую вершину.

1:function ID3([math]U[/math]):
2:  if все объекты множества [math]U[/math] принадлежат одному классу [math]y \in Y[/math] 
       then
3:        создать новый лист [math]v[/math] 
4:        [math]y_v = y[/math]
5:        return v
6:  найти предикат с максимальной информативностью :
     [math]\beta= \mathrm{arg}\max_{\beta\in B} [/math] Gain([math]\beta[/math], [math]U[/math])
7:  разбить выборку на две части [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]
8:  if [math]U_0 = \emptyset[/math] или [math]U_1 = \emptyset[/math] 
     then
9:     создать новый лист [math]v[/math]
10:    [math]y_v[/math] = класс, в котором находится большинство объектов из [math]U[/math]
11:  else
12:    создать новую внутреннюю вершину [math]v[/math]
13:    [math]\beta_v = \beta[/math]
14:    [math]S_0[/math] = ID3([math]U_0[/math])
15:    [math]S_1[/math] = ID3([math]U_1[/math])
16:  return [math]v[/math]

Информативность ветвления

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

Частотная оценка вероятности класса [math]y[/math] в вершине [math]v \in V_{внутр}[/math] : [math]p_y = P(y | x \in U) = \frac{1}{|U|} \sum\nolimits_{x_i \in U}[y_i = y][/math]

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

Мера неопределенности (англ. impurity) распределения [math]p_y[/math]: минимальна, когда [math]p_y \in \{0,1\}[/math] максимальна, когда [math]p_y = \frac{1}{|Y|}[/math] для всех [math]y \in Y[/math] не зависит от перенумерации классов [math]Ф(U) = \sum\nolimits_{y \in Y} p_y L(p_y) = \frac{1}{|U|} \sum\nolimits_{x_i \in U}L(P(y_i | x_i \in U)) \rightarrow min[/math], где [math]L(p)[/math] убывает и [math]L(1) = 0[/math], например: [math]-log_2(p)[/math], [math]1 - p[/math], [math]1 - p^2[/math]

Примеры:

• Энтропия: [math]Ф(U) = -\sum\nolimits_{i}p_i log_2p_i[/math]
• Критерий Джини: [math]Ф(U) = \sum\nolimits_{i != j}p_i p_j = \sum\nolimits_{i}p_i*(1-p_i)[/math]

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

Неопределенность распределения [math]P(y_i | x_i \in U_{\beta(x_i)})[/math] после ветвления вершины [math]v[/math] по предикату [math]\beta[/math] и разбиения [math]U = \bigcup_{k \in D_v} U_k[/math]: [math]Ф(U_0, ... ,U_{D_v}) = \frac{1}{|U|} \sum\nolimits_{k \in D_v} \sum\nolimits_{x_i \in U_k}L(P(y_i | x_i \in U_k)) = \sum\nolimits_{k \in D_v} \frac{|U_k|}{|U|}Ф(U_k)[/math]

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

Информационный выигрыш от ветвления вершины [math]v[/math] [math]Gain(\beta, U) = Ф(U) - Ф(U_1, ... ,U_{|D_v|}) = Ф(U) - \sum\nolimits_{k \in D_v} \frac{|U_k|}{|U|}Ф(U_k) \rightarrow max_{\beta \in B} [/math]

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

Суть редукции состоит в удалении поддеревьев, имеющих недостаточную статистическую надёжность. При этом дерево перестаёт безошибочно классифицировать обучающую выборку, зато качество классификации новых объектов, как правило, улучшается. Рассмотрим наиболее простые варианты редукции.

Предредукция

Предредукция (англ. pre-pruning) или критерий раннего останова досрочно прекращает дальнейшее ветвление в вершине дерева, если информативность [math]I(\beta, U)[/math] для всех возможных предикатов [math]\beta[/math] не дотягивает до заданного порогового значения [math]I_0[/math].
Для этого на шаге 8 алгоритма [math]ID3[/math] условие [math]U_0 = \emptyset[/math] или [math]U_1 = \emptyset[/math] заменяется условием [math]I(\beta, U) \lt = I_0 [/math]. Порог [math]I_0 [/math] является управляющим параметром метода.
Предредукция считается не самым эффективным способом избежать переобучения, так как жадное ветвление по-прежнему остаётся глобально неоптимальным. Более эффективной считается cтратегия постредукции.

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

Постредукция (англ. post-pruning) просматривает все внутренние вершины дерева и заменяет отдельные вершины либо одной из дочерних вершин (при этом вторая дочерняя удаляется), либо терминальной вершиной. Процесс замен продолжается до тех пор, пока в дереве остаются вершины, удовлетворяющие критерию замены.

Критерием замены является сокращение числа ошибок на контрольной выборке, отобранной заранее, и не участвовавшей в обучении дерева. Стандартная рекомендация — оставлять в контроле около 30% объектов.

Для реализации постредукции контрольная выборка [math]X^k[/math] пропускается через построенное дерево. При этом в каждой внутренней вершине [math]v[/math] запоминается подмножество [math]S_v \subseteq X_k[/math] попавших в неё контрольных объектов. Если [math]S_v = \emptyset [/math], то вершина [math]v[/math] считается ненадёжной и заменяется терминальной по мажоритарному правилу:
в качестве [math]y_v[/math] берётся тот класс, объектов которого больше всего в обучающей подвыборке [math]U[/math], пришедшей в вершину [math]v[/math].
Затем для каждой внутренней вершины [math]v[/math] вычисляется число ошибок, полученных при классификации выборки [math]S_v[/math] следующими способами:

• [math]r(v)[/math] — классификация поддеревом, растущим из вершины [math]v[/math];
• [math]r_L(v)[/math] — классификация поддеревом левой дочерней вершины [math]L_v[/math];
• [math]r_R(v)[/math] — классификация поддеревом правой дочерней вершины [math]R_v[/math];
• [math]r_c(v)[/math] — отнесение всех объектов выборки [math]S_v[/math] к классу [math]y \in Y[/math].
  

Эти величины сравниваются, и, в зависимости от того, какая из них оказалась минимальной, принимается, соответственно, одно из четырёх решений:

• сохранить поддерево вершины [math]v[/math];
• заменить поддерево вершины [math]v[/math] поддеревом левой дочерней вершины [math]L_v[/math];
• заменить поддерево вершины [math]v[/math] поддеревом правой дочерней вершины [math]R_v[/math];
• заменить поддерево [math]v[/math] терминальной вершиной класса [math]y_v = \mathrm{arg}\min_{y\in Y}r_c(v) [/math].

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

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

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

Для повышения точности модели применяют объединения моделей (классификаторов) в ансамбль.

Виды ансамблей

Бутстрэп

Метод бутстрэпа (англ. bootstrap aggregation) — один из первых и самых простых видов ансамблей, который позволяет оценивать многие статистики сложных распределений и заключается в следующем. Пусть имеется выборка [math]X[/math] размера [math]N[/math]. Равномерно возьмем из выборки [math]N[/math] объектов с возвращением. Это означает, что мы будем [math]N[/math] раз равновероятно выбирать произвольный объект выборки, причем каждый раз мы выбираем из всех исходных [math]N[/math] объектов. Отметим, что из-за возвращения среди них окажутся повторы.
Обозначим новую выборку через [math]X_1[/math]. Повторяя процедуру [math]M[/math] раз, сгенерируем [math]M[/math] подвыборок [math]X_1 ... X_M[/math]. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.

Бэггинг

Рассмотрим, следующий вид ансамбля — бэггинг (англ. bagging). Пусть имеется обучающая выборка [math]X[/math]. С помощью бутстрэпа сгенерируем из неё выборки [math]X_1 ... X_M[/math]. Теперь на каждой выборке обучим свой классификатор [math]a_i(x)[/math]. Итоговый классификатор будет усреднять ответы всех этих алгоритмов [math]a(x) = \frac{1}{M} \sum\limits_{i = 1}^{M} a_i(x)[/math].

Случайный лес

Алгоритм построения случайного леса, состоящего из [math]N[/math] деревьев на основе обучающей выборки [math]X[/math]:

for (n: 1,...N):
   сгенерировать выборку [math]X_n[/math] c помощью бутстрэпа
   построить решающее дерево [math]t_n[/math] по выборку [math]X_n[/math]

Ссылки

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