Редактирование: Дерево решений и случайный лес

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

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

{{Определение
|id=def1. 
|neat = 
|definition=
'''Дерево решений''' (англ. ''decision tree, DT'') {{---}} алгоритм классификации <tex>a(x) = (V_{внутр}, v_0, V_{лист}, S_v, \beta_v)</tex>, задающийся деревом (связным ациклическим графом), где:
* <tex> V = V_{внутр} \cup V_{лист} </tex> {{---}} множество вершин , <tex>v_0 \in V</tex> {{---}} корень дерева
* <tex> S_v : D_v \rightarrow V_v </tex> {{---}} функция перехода по значению предиката в множество детей вершины <tex>v</tex>
* <tex> \beta_v : X \rightarrow D_v </tex> {{---}} предикат ветвления, <tex>v \in V_{внутр}</tex> и <tex>|D_v| < \infty</tex>
* Для листьев <tex>v \in V_{лист}</tex> определена метка класса <tex>y_v \in Y</tex>
}}
{{Определение
|id=def1 
|neat =
|definition=
'''Бинарное дерево решений''' {{---}}  частный случай дерева решений, для которого <tex> D_v = \{0,1\} </tex>.
}}
[[Файл:BinDT.jpg |300px|thumb|right|Классификация объекта <tex> x \in X </tex> бинарным решающим деревом]]

 '''function''' classify(x):
   <tex>v = v_0</tex>
   '''if''' <tex>\beta_v(x) = 1 </tex> 
      <tex>v := R_v</tex>
   '''else'''
      <tex>v := L_v</tex>
   '''return''' <tex>y_v</tex>

===Информативность ветвления===
Для того, чтобы оценивать качество разбиения объектов по предикату <tex>\beta</tex>, введем понятие ''информационного выигрыша'' разбиения. <br>
Сначала оценим распределение значений классов объектов внутри каждого множества из разбиения, введя понятие ''меры неопределенности распределения''.
{{Определение
|id=def1 
|neat =
|definition=
'''Частотная оценка вероятности класса <tex>y</tex> в вершине <tex>v \in V_{внутр}</tex> ''': <br>
<tex>p_y = P(y | x \in U) = \frac{1}{|U|} \sum\nolimits_{x_i \in U}[y_i = y]</tex>
}}

{{Определение
|id=def1 
|neat =
|definition=
'''Мера неопределенности (англ. ''impurity'') распределения <tex>p_y</tex>''': <br>
* минимальна, когда <tex>p_y \in \{0,1\}</tex>
* максимальна, когда <tex>p_y = \frac{1}{|Y|}</tex> для всех <tex>y \in Y</tex>
* не зависит от перенумерации классов
<tex>Ф(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</tex>, <br> где <tex>L(p)</tex> убывает и <tex>L(1) = 0</tex>, например: <tex>-log_2(p)</tex>, <tex>1 - p</tex>, <tex>1 - p^2</tex>
}}

Примерами мер неопределенности распределения являются: 
* Энтропия: <tex>Ф(U) = -\sum\limits_{i}^N p_i log_2p_i</tex>, определяется для каждого множества из разбиения, <tex>N</tex> {{---}} количество возможных классов, и <tex>p_i</tex> {{---}} вероятность объекта принадлежать <tex> i</tex>-ому классу.
* Критерий Джини: <tex>Ф(U) = \sum\nolimits_{i != j}p_i p_j = \sum\nolimits_{i}p_i*(1-p_i)</tex>, максимизацию этого критерия можно интерпретировать как максимизацию числа пар объектов одного класса, оказавшихся после разбиения в одном множестве. <br>

Теперь определим суммарную ''неопределенность распределения'' в разбиении.
{{Определение
|id=def1 
|neat =
|definition=
'''Неопределенность распределения <tex>P(y_i | x_i \in U_{\beta(x_i)})</tex> после ветвления вершины <tex>v</tex> по предикату <tex>\beta</tex> и разбиения <tex>U = \bigcup_{k \in D_v} U_k</tex>''': <br>
<tex>Ф(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)</tex>
}}

''Информационный выигрыш'' от разбиения определяется как изменение неопределенности в системе.
{{Определение
|id=def1 
|neat =
|definition=
'''Информационный выигрыш от разбиения по предикату <tex>\beta</tex>''' <br>
<tex>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} </tex>
}}

=== Рекурсивный алгоритм построения бинарного дерева решений ID3 ===
Покажем идею построения дерева решения на частном случае бинарного дерева. Алгоритм <tex>ID3</tex> (англ. ''Induction of Decision Tree'') заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Разделение производится по предикату <tex>\beta</tex>, который выбирается из множества элементарных предикатов. На практике в качестве элементарных предикатов чаще всего берут простые пороговые условия вида <tex>\beta(x) = [f_j(x) >= d_j]</tex>. 
<br>Проще всего записать этот алгоритм в виде рекурсивной процедуры <tex>ID3</tex>, которая строит дерево по заданной подвыборке <tex>U</tex> и возвращает его корневую вершину. 

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

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

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

===Постредукция===
Постредукция (англ. ''post-pruning'') просматривает все внутренние вершины дерева и заменяет отдельные вершины либо одной из дочерних вершин (при этом вторая дочерняя удаляется), либо терминальной вершиной. Процесс замен продолжается до тех
пор, пока в дереве остаются вершины, удовлетворяющие критерию замены. <br><br>
''Критерием замены'' является сокращение числа ошибок на контрольной выборке, отобранной заранее, и не участвовавшей в обучении дерева. Стандартная рекомендация — оставлять в контроле около 30% объектов. <br><br>
Для реализации постредукции контрольная выборка <tex>X^k</tex> пропускается через
построенное дерево. При этом в каждой внутренней вершине <tex>v</tex> запоминается подмножество <tex>S_v \subseteq X_k</tex> попавших в неё контрольных объектов. Если <tex>S_v = \emptyset </tex>, то вершина <tex>v</tex> считается ненадёжной и заменяется терминальной по ''мажоритарному правилу'': <br>
в качестве <tex>y_v</tex> берётся тот класс, объектов которого больше всего в обучающей подвыборке <tex>U</tex>, пришедшей в вершину <tex>v</tex>. <br>
Затем для каждой внутренней вершины <tex>v</tex> вычисляется число ошибок, полученных при классификации выборки <tex>S_v</tex> следующими способами: <br>
* <tex>r(v)</tex> — классификация поддеревом, растущим из вершины <tex>v</tex>;
* <tex>r_L(v)</tex> — классификация поддеревом левой дочерней вершины <tex>L_v</tex>;
* <tex>r_R(v)</tex> — классификация поддеревом правой дочерней вершины <tex>R_v</tex>;
* <tex>r_c(v)</tex> — отнесение всех объектов выборки <tex>S_v</tex> к классу <tex>y \in Y</tex>. <br>
Эти величины сравниваются, и, в зависимости от того, какая из них оказалась
минимальной, принимается, соответственно, одно из четырёх решений: <br>
* сохранить поддерево вершины <tex>v</tex>;
* заменить поддерево вершины <tex>v</tex> поддеревом левой дочерней вершины <tex>L_v</tex>;
* заменить поддерево вершины <tex>v</tex> поддеревом правой дочерней вершины <tex>R_v</tex>;
* заменить поддерево <tex>v</tex> терминальной вершиной класса <tex>y_v = \mathrm{arg}\min_{y\in Y}r_c(v) </tex>.

== Алгоритмы построения деревьев решения ==
Недостатки рассмотренного алгоритма ID3: 
* Применим только для дискретных значений признаков
* Переобучение
* На каждом шаге решение принимается по одному атрибуту

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

=== Алгоритм C4.5 ===
* Также работает и с непрерывными значениями признаков: на каждом шаге построения дерева выбирает правило разбиения по одному из признаков. Разбивает объекты на несколько частей по этому правилу, рекурсивно запускается из полученных подмножеств.
* Использует редукцию для избежания переобучения.
* Обрабатывает пропущенные или аномальные значения признаков.

== Случайный лес ==
Случайный лес {{---}} один из примеров объединения классификаторов в [[Виды_ансамблей|ансамбль]]. 
Алгоритм случайного леса, состоящего из <tex>N</tex> деревьев на основе обучающей выборки <tex>X</tex>
 '''for''' (n: 1,...,N):
    <font color=green>// сгенерировать выборку <tex>X_n</tex> c помощью [[Виды_ансамблей#Бутстрэп|бутстрэпа]]</font>
    <tex>X_n</tex> = bootstrap(<tex>X</tex>)
    <font color=green>// построить решающее дерево <tex>t_n</tex> по выборке <tex>X_n</tex></font>
    <tex>t_n</tex> = ID3(<tex>X_n</tex>) <br>

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

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

== Примеры использования (в scikit-learn) ==
*Для решения задач классификации и регрессии используют [https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree.DecisionTreeClassifier DecisionTreeClassifier], [https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html#sklearn.tree.DecisionTreeRegressor DecisionTreeRegressor]

*В '''sklearn.ensemble''' также представлены методы классификации, основанные на ансамблях, в том числе: [https://scikit-learn.org/stable/modules/ensemble.html#bagging бэггинг] и [https://scikit-learn.org/stable/modules/ensemble.html#forest случайный лес], которые были описаны выше. 
<br>Так, в этом примере создается бэггинг ансамбль из классификаторов '''KNeighborsClassifier''', каждый из которых обучен на случайных подмножествах из 50% объектов из обучающей выборки, и 50% случайно выбранных признаков.

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

Пример использования классификатора на случайном лесе:
Полную версию кода можно найти [https://scikit-learn.org/stable/auto_examples/classification/plot_classifier_comparison.html#sphx-glr-download-auto-examples-classification-plot-classifier-comparison-py| здесь]
 '''from''' sklearn '''import''' RandomForestClassifier
 '''from''' sklearn.datasets '''import''' make_classification
 <font color=green>// сгенерируем случайную обучающую выборку с классификацией по n_classes классам</font>
 X, y = make_classification(n_features=2, n_redundant=0, n_informative=2,
                           random_state=1, n_clusters_per_class=1, n_classes=2)
 <font color=green>// разбиваем выборку на обучающую и тестовую </font>
 X = StandardScaler().fit_transform(X)
 X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=.4, random_state=42)
 <font color=green>// создадим классификатор на случайном лесе, состоящим из n_estimators деревьев</font>
 RandomForestClassifier(max_depth=5, n_estimators=10, max_features=1)
 clf.fit(X_train, y_train)
 score = clf.score(X_test, y_test)

Результат классификации показан на рисунке. 

[[Файл:RFC.png |800px|thumb|center|Классификация RandomForestClassifier. Кружочками изображены объекты обучающей выборки, крестиками тестовой выборки. Справа цветом выделены границы принятия решений, в правом нижнем углу {{---}} значение accuracy.]]

== Пример на языке Scala ==
SBT зависимость:
  libraryDependencies '''+=''' "com.github.haifengl" '''%%''' "smile-scala" '''%''' "1.5.2"
Пример классификации датасета и вычисления F1 меры<ref>[https://en.wikipedia.org/wiki/F1_score F1 мера]</ref> используя smile.classification.cart<ref>[https://haifengl.github.io/smile/classification.html#cart Smile, Decision Trees]</ref>:
  '''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)

== См. также ==
* [[Виды ансамблей]]

== Источники информации ==
# [http://www.machinelearning.ru/wiki/images/3/3e/Voron-ML-Logic.pdf Логические алгоритмы классификации] {{---}} Лекция К. В. Воронцова
# [https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-5-ensembles-of-algorithms-and-random-forest-8e05246cbba7 Случайный лес] {{---}} статья на Medium, Yury Kashnitskiy
# [https://scikit-learn.org/stable/modules/tree.html Деревья решений] {{---}} scikit-learn.org
#[https://scikit-learn.org/stable/modules/ensemble.html Ансамбли классификаторов] — scikit-learn.org.


[[Категория: Машинное обучение]]
[[Категория: Классификация и регрессия]]