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

Дерево решений — логический алгоритм классификации, решающий задачи классификации и регрессии. Представляет собой объединение логических условий в структуру дерева.

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

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

Дерево решений (англ. decision tree, DT) — алгоритм классификации [math]a(x) = (V_{внутр}, v_0, V_{лист}, S_v, \beta_v)[/math], задающийся деревом (связным ациклическим графом), где: [math] V = V_{внутр} \cup V_{лист} [/math] — множество вершин , [math]v_0 \in V[/math] — корень дерева [math] S_v : D_v \rightarrow V_v [/math] — функция перехода по значению предиката в множество детей вершины [math]v[/math] [math] \beta_v : X \rightarrow D_v [/math] — предикат ветвления, [math]v \in 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] x \in X [/math] бинарным решающим деревом

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

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

Для того, чтобы оценивать качество разбиения объектов по предикату [math]\beta[/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\limits_{i}^N p_i log_2p_i[/math], определяется для каждого множества из разбиения, [math]N[/math] — количество возможных классов, и [math]p_i[/math] — вероятность объекта принадлежать [math] 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]\beta[/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]

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

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

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

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

Предредукция (англ. 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].

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

• Алгоритм C4.5
  • В отличие от ID3 работает и с непрерывными значениями признаков: устанавливает для них пороговые значения и по ним разбивает объекты на две части.
  • Использует редукцию, чтобы избежать переобучения.
  • Обрабатывает пропущенные или аномальные значения признаков.
• Алгоритм CART (англ. Classification And Regression Trees)

На каждом шаге построения дерева алгоритм последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него.

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

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

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

Итоговый классификатор — [math]a(x) = \frac{1}{N} \sum\limits_{i = 1}^{N} t_i(x)[/math]. Для задачи кассификации мы выбираем решение по большинству результатов, выданных классификаторами, а в задаче регрессии — по их среднему значению.

Таким образом, случайный лес — это бэггинг над решающими деревьями, при обучении которых для каждого разбиения признаки выбираются из некоторого случайного подмножества признаков.

Примеры использования (в scikit-learn)

• Для решения задач классификации и регрессии используют DecisionTreeClassifier, DecisionTreeRegressor

• В sklearn.ensemble также представлены методы классификации, основанные на ансамблях, в том числе: бэггинг и случайный лес, которые были описаны выше.

Так, в этом примере создается бэггинг ансамбль из классификаторов KNeighborsClassifier, каждый из которых обучен на рандомных подмножествах из 50% объектов из обучающей выборки, и 50% рандомно выбранных признаков.

from sklearn.ensemble import BaggingClassifier
from sklearn.neighbors import KNeighborsClassifier
bagging = BaggingClassifier(KNeighborsClassifier(), max_samples=0.5, max_features=0.5)

Пример использования классификатора на случайном лесе:

from sklearn import RandomForestClassifier
from sklearn.datasets import make_classification
// сгенерируем рандомный обучающий набор с классификацией по n_classes классам
X, y = make_classification(n_samples=1000, n_features=4, n_classes = 5)
// создадим классификатор на случайном лесе, состоящим из n_estimators деревьев
clf = RandomForestClassifier(n_estimators=100, max_depth=2)
// обучим классификатор на сгенерированном обучающем множестве
clf.fit(X, y)
clf.predict(0, 0, 0, 0)

Пример на языке Scala

SBT зависимость:

 libraryDependencies += "com.github.haifengl" %% "smile-scala" % "1.5.2"

Пример классификации датасета и вычисления F1 меры используя smile.classification.cart:

 import smile.classification._
 import smile.data._
 import smile.plot._
 import smile.read
 import smile.validation.FMeasure

 val iris: AttributeDataset = read.table("iris.csv", delimiter = ",", response = Some((new NumericAttribute("class"), 2)))
 val x: Array[Array[Double]] = iris.x()
 val y: Array[Int] = iris.y().map(_.toInt)
 val dt: DecisionTree = cart(x, y, 1000)
 val predictions: Array[Int] = x.map(dt.predict)
 val f1Score = new FMeasure().measure(predictions, y)
 plot(x, y, dt)

Ссылки

• Лекции по логическим алгоритмам классификации — К. В. Воронцов.
• Случайный лес — Medium, Yury Kashnitskiy.
• Деревья решений — scikit-learn.org.
• Ансамбли — scikit-learn.org.

F1 мера

Smile, Decision Trees