Дерево решений и случайный лес — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Рекурсивный алгоритм построения бинарного дерева решений ID3)
 
(не показано 46 промежуточных версий 5 участников)
Строка 1: Строка 1:
Дерево решений {{---}} логический алгоритм классификации, решающий задачи классификации и регрессии.  
+
Дерево решений {{---}} логический алгоритм классификации, решающий задачи классификации и регрессии. Представляет собой объединение логических условий в структуру дерева.
  
 
==Дерево решений==
 
==Дерево решений==
Строка 8: Строка 8:
 
|definition=
 
|definition=
 
'''Дерево решений''' (англ. ''decision tree, DT'') {{---}} алгоритм классификации <tex>a(x) = (V_{внутр}, v_0, V_{лист}, S_v, \beta_v)</tex>, задающийся деревом (связным ациклическим графом), где:
 
'''Дерево решений''' (англ. ''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> V = V_{внутр} \cup V_{лист} </tex> {{---}} множество вершин , <tex>v_0 \in V</tex> {{---}} корень дерева;
* <tex> S_v : D_v \rightarrow V_v </tex> {{---}} функция перехода по значению предиката в множество детей вершины <tex>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> \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>
+
* Для листьев <tex>v \in V_{лист}</tex> определена метка класса <tex>y_v \in Y</tex>.
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 23: Строка 23:
 
  '''function''' classify(x):
 
  '''function''' classify(x):
 
   <tex>v = v_0</tex>
 
   <tex>v = v_0</tex>
   '''if''' <tex>\beta_v(x) = 1 </tex> '''then'''
+
   '''if''' <tex>\beta_v(x) = 1 </tex>  
 
       <tex>v := R_v</tex>
 
       <tex>v := R_v</tex>
 
   '''else'''
 
   '''else'''
 
       <tex>v := L_v</tex>
 
       <tex>v := L_v</tex>
 
   '''return''' <tex>y_v</tex>
 
   '''return''' <tex>y_v</tex>
 
=== Рекурсивный алгоритм построения бинарного дерева решений ID3 ===
 
Покажем идею построения дерева решения на частном случае бинарного дерева. Алгоритм <tex>ID3</tex> (англ. ''Induction of Decision Tree'') заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Разделение производится по предикату <tex>\beta</tex>, который выбирается из множества элементарных предикатов. На практике в качестве элементарных предикатов чаще всего берут простые пороговые условия вида <tex>\beta(x) = [f_j(x) >= d_j]</tex>.
 
<br><br>Проще всего записать этот алгоритм в виде рекурсивной процедуры <tex>ID3</tex>, которая строит дерево по заданной подвыборке <tex>U</tex> и возвращает его корневую вершину.
 
 
1:'''function''' ID3(<tex>U</tex>):
 
<font color=green>// все объекты из множества <tex>U</tex> принадлежат одному классу <tex>y \in Y</tex></font>
 
2:  '''if''' <tex>for all</tex> <tex>u \in U</tex>: <tex>y_u = y</tex></tex>
 
        '''then'''
 
3:        создать новый лист <tex>v</tex>
 
4:        <tex>y_v = y</tex>
 
5:        '''return''' v
 
6:  найти предикат с максимальной информативностью :
 
      <tex>\beta= \mathrm{arg}\max_{\beta\in B} </tex> Gain(<tex>\beta</tex>, <tex>U</tex>)
 
7:  разбить выборку на две части <tex>U = U_0 \cup U_1</tex> по предикату <tex>\beta</tex>:
 
      <tex>U_0 := \{x \in U: f_v(x) = 0\}</tex>
 
      <tex>U_1 := \{x \in U: f_v(x) = 1\}</tex>
 
8:  '''if''' <tex>U_0 = \emptyset</tex> или <tex>U_1 = \emptyset</tex>
 
      '''then'''
 
9:    создать новый лист <tex>v</tex>
 
10:    <tex>y_v</tex> = класс, в котором находится большинство объектов из <tex>U</tex>
 
11:  '''else'''
 
12:    создать новую внутреннюю вершину <tex>v</tex>
 
13:    <tex>\beta_v = \beta</tex>
 
14:    <tex>S_0</tex> = ID3(<tex>U_0</tex>)
 
15:    <tex>S_1</tex> = ID3(<tex>U_1</tex>)
 
16:  '''return''' <tex>v</tex>
 
  
 
===Информативность ветвления===
 
===Информативность ветвления===
 +
Для того, чтобы оценивать качество разбиения объектов по предикату <tex>\beta</tex>, введем понятие ''информационного выигрыша'' разбиения. <br>
 +
Сначала оценим распределение значений классов объектов внутри каждого множества из разбиения, введя понятие ''меры неопределенности распределения''.
 
{{Определение
 
{{Определение
 
|id=def1  
 
|id=def1  
Строка 70: Строка 45:
 
|definition=
 
|definition=
 
'''Мера неопределенности (англ. ''impurity'') распределения <tex>p_y</tex>''': <br>
 
'''Мера неопределенности (англ. ''impurity'') распределения <tex>p_y</tex>''': <br>
* минимальна, когда <tex>p_y \in \{0,1\}</tex>
+
* минимальна, когда <tex>p_y \in \{0,1\}</tex>;
* максимальна, когда <tex>p_y = \frac{1}{|Y|}</tex> для всех <tex>y \in Y</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\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\nolimits_{i}p_i log_2p_i</tex>
+
Примерами мер неопределенности распределения являются:  
* Критерий Джини: <tex>Ф(U) = \sum\nolimits_{i != j}p_i p_j = \sum\nolimits_{i}p_i*(1-p_i)</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  
 
|id=def1  
Строка 86: Строка 64:
 
}}
 
}}
  
 +
''Информационный выигрыш'' от разбиения определяется как изменение неопределенности в системе.
 
{{Определение
 
{{Определение
 
|id=def1  
 
|id=def1  
 
|neat =
 
|neat =
 
|definition=
 
|definition=
'''Информационный выигрыш от ветвления вершины <tex>v</tex>''' <br>
+
'''Информационный выигрыш от разбиения по предикату <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>
 
<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'') состоит в удалении поддеревьев, имеющих недостаточную статистическую надёжность. При этом дерево перестаёт безошибочно классифицировать обучающую выборку, зато качество классификации новых объектов, как правило, улучшается. Рассмотрим наиболее простые варианты редукции.
  
 
===Предредукция===
 
===Предредукция===
Строка 114: Строка 119:
 
* <tex>r_R(v)</tex> — классификация поддеревом правой дочерней вершины <tex>R_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>
 
* <tex>r_c(v)</tex> — отнесение всех объектов выборки <tex>S_v</tex> к классу <tex>y \in Y</tex>. <br>
Эти величины сравниваются, и, в зависимости от того, какая из них оказалась
+
Эти величины сравниваются, и в зависимости от того, какая из них оказалась
 
минимальной, принимается, соответственно, одно из четырёх решений: <br>
 
минимальной, принимается, соответственно, одно из четырёх решений: <br>
 
* сохранить поддерево вершины <tex>v</tex>;
 
* сохранить поддерево вершины <tex>v</tex>;
Строка 122: Строка 127:
  
 
== Алгоритмы построения деревьев решения ==
 
== Алгоритмы построения деревьев решения ==
*[https://en.wikipedia.org/wiki/ID3_algorithm Алгоритм ID3]
+
Недостатки рассмотренного алгоритма ID3:  
* [https://en.wikipedia.org/wiki/C4.5_algorithm Алгоритм C4.5]
+
* Применим только для дискретных значений признаков;
* Алгоритм CART
+
* Переобучение;
* Алгоритм LISTBB
+
* На каждом шаге решение принимается по одному атрибуту.
  
== Композиции решающих деревьев ==
+
=== Алгоритм [https://en.wikipedia.org/wiki/Predictive_analytics#Classification_and_regression_trees_.28CART.29 CART] (англ. ''Classification And Regression Trees'')===
Для повышения точности модели применяют объединения моделей (классификаторов) в ансамбль.  
+
* В отличие от ID3 работает и с непрерывными значениями признаков: на каждом шаге построения дерева последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него. Разбивает объекты на две части;
===Виды ансамблей===
+
* Использует редукцию для избежания переобучения;
====Бутстрэп====
+
* Обрабатывает пропущенные или аномальные значения признаков.
Метод бутстрэпа (англ. ''bootstrap aggregation'') — один из первых и самых простых видов ансамблей, который позволяет оценивать многие статистики сложных распределений и  заключается в следующем. Пусть имеется выборка <tex>X</tex> размера <tex>N</tex>. Равномерно возьмем из выборки <tex>N</tex> объектов с возвращением. Это означает, что мы будем <tex>N</tex> раз равновероятно выбирать произвольный объект выборки, причем каждый раз мы выбираем из всех исходных <tex>N</tex> объектов. Отметим, что из-за возвращения среди них окажутся повторы. <br>Обозначим новую выборку через <tex>X_1</tex>. Повторяя процедуру <tex>M</tex> раз, сгенерируем <tex>M</tex> подвыборок <tex>X_1 ... X_M</tex>. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.
 
  
====Бэггинг====
+
=== Алгоритм [https://en.wikipedia.org/wiki/C4.5_algorithm C4.5] ===
Рассмотрим, следующий вид ансамбля — бэггинг (англ. ''bagging''). Пусть имеется обучающая выборка <tex>X</tex>. С помощью бутстрэпа сгенерируем из неё выборки <tex>X_1 ... X_M</tex>. Теперь на каждой выборке обучим свой классификатор <tex>a_i(x)</tex>. Итоговый классификатор будет усреднять ответы всех этих алгоритмов <tex>a(x) = \frac{1}{M} \sum\limits_{i = 1}^{M} a_i(x)</tex>.
+
* Также работает и с непрерывными значениями признаков: на каждом шаге построения дерева выбирает правило разбиения по одному из признаков. Разбивает объекты на несколько частей по этому правилу, рекурсивно запускается из полученных подмножеств;
 +
* Использует редукцию для избежания переобучения;
 +
* Обрабатывает пропущенные или аномальные значения признаков.
  
=== Случайный лес ===
+
== Случайный лес ==
Алгоритм построения случайного леса, состоящего из <tex>N</tex> деревьев на основе обучающей выборки <tex>X</tex>:
+
Случайный лес {{---}} один из примеров объединения классификаторов в [[Виды_ансамблей|ансамбль]]. <br>
 +
Алгоритм построения случайного леса, состоящего из <tex>N</tex> деревьев на основе обучающей выборки <tex>X</tex> такой:
 
  '''for''' (n: 1,...,N):
 
  '''for''' (n: 1,...,N):
     сгенерировать выборку <tex>X_n</tex> c помощью бутстрэпа
+
     <font color=green>// сгенерировать выборку <tex>X_n</tex> c помощью [[Виды_ансамблей#Бутстрэп|бутстрэпа]]</font>
     построить решающее дерево <tex>t_n</tex> по выборке <tex>X_n</tex><br>
+
     <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>
+
Итоговый классификатор {{---}} <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]
+
===Примеры на языке Python===
 +
*Для решения задач классификации и регрессии используют [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 случайный лес], которые были описаны выше.  
 
*В '''sklearn.ensemble''' также представлены методы классификации, основанные на ансамблях, в том числе: [https://scikit-learn.org/stable/modules/ensemble.html#bagging бэггинг] и [https://scikit-learn.org/stable/modules/ensemble.html#forest случайный лес], которые были описаны выше.  
<br>Так, в этом примере создается бэггинг ансамбль из классификаторов '''KNeighborsClassifier''', каждый из которых обучен на рандомных подмножествах из 50% объектов из обучающей выборки, и 50% рандомно выбранных признаков.
+
<br>Так, в этом примере создается бэггинг ансамбль из классификаторов '''KNeighborsClassifier''', каждый из которых обучен на случайных подмножествах из 50% объектов из обучающей выборки, и 50% случайно выбранных признаков.
  
 
  '''from''' sklearn.ensemble '''import''' BaggingClassifier
 
  '''from''' sklearn.ensemble '''import''' BaggingClassifier
Строка 157: Строка 167:
  
 
Пример использования классификатора на случайном лесе:
 
Пример использования классификатора на случайном лесе:
 +
Полную версию кода можно найти [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 '''import''' RandomForestClassifier
 
  '''from''' sklearn.datasets '''import''' make_classification
 
  '''from''' sklearn.datasets '''import''' make_classification
  <font color=green>// сгенерируем рандомный обучающий набор с классификацией по n_classes классам</font>
+
  <font color=green>// сгенерируем случайную обучающую выборку с классификацией по n_classes классам</font>
  X, y = make_classification(n_samples=1000, n_features=4, n_classes = 5)
+
  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>
 
  <font color=green>// создадим классификатор на случайном лесе, состоящим из n_estimators деревьев</font>
  clf = RandomForestClassifier(n_estimators=100, max_depth=2)
+
  RandomForestClassifier(max_depth=5, n_estimators=10, max_features=1)
<font color=green>// обучим классификатор на сгенерированном обучающем множестве</font>
+
  clf.fit(X_train, y_train)
  clf.fit(X, y)
+
  score = clf.score(X_test, y_test)
  clf.predict([[0, 0, 0, 0]])
 
  
== Пример использования на языке Scala ==
+
Результат классификации показан на рисунке.
 +
 
 +
[[Файл:RFC.png |800px|thumb|center|Классификация RandomForestClassifier. Кружочками изображены объекты обучающей выборки, крестиками тестовой выборки. Справа цветом выделены границы принятия решений, в правом нижнем углу {{---}} значение accuracy.]]
 +
 
 +
===Пример на языке Scala===
 
SBT зависимость:
 
SBT зависимость:
 
   libraryDependencies '''+=''' "com.github.haifengl" '''%%''' "smile-scala" '''%''' "1.5.2"
 
   libraryDependencies '''+=''' "com.github.haifengl" '''%%''' "smile-scala" '''%''' "1.5.2"
Строка 185: Строка 203:
 
   plot(x, y, dt)
 
   plot(x, y, dt)
  
== Ссылки ==
+
===Пример на языке Java===
*[http://www.machinelearning.ru/wiki/images/3/3e/Voron-ML-Logic.pdf Лекции по логическим алгоритмам классификации] К. В. Воронцов.
+
Пример классификации с применением <code>weka.classifiers.trees.RandomForest</code><ref>[http://weka.sourceforge.net/doc.dev/weka/classifiers/trees/RandomForest.html Weka, Random Forest]</ref>
*[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.
+
<code>Maven</code> зависимость:
*[https://scikit-learn.org/stable/modules/ensemble.html Ансамбли] — scikit-learn.org.
+
  <dependency>
 +
    <groupId>nz.ac.waikato.cms.weka</groupId>
 +
    <artifactId>weka-stable</artifactId>
 +
    <version>3.8.0</version>
 +
  </dependency>
 +
 
 +
  '''import''' weka.classifiers.evaluation.Evaluation;
 +
  '''import''' weka.classifiers.trees.RandomForest;
 +
 
 +
  <font color="green">// read dataset</font>
 +
  '''var''' trainingDataSet = getDataSet(...);
 +
  '''var''' testingDataSet = getDataSet(...);
 +
  <font color="green">// create random forest classifier</font>
 +
  '''var''' forest = new RandomForest();
 +
  forest.setMaxDepth(15);
 +
  forest.setNumFeatures(2);
 +
  forest.buildClassifier(trainingDataSet);
 +
  <font color="green">// evaluate the model on test dataset and print summary</font>
 +
  '''var''' eval = new Evaluation(trainingDataSet);
 +
  eval.evaluateModel(forest, testingDataSet);
 +
  System.out.println(eval.toSummaryString());
 +
 
 +
== См. также ==
 +
* [[Виды ансамблей]]
 +
 
 +
== Источники информации ==
 +
# [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.
 +
 
 +
 
 +
[[Категория: Машинное обучение]]
 +
[[Категория: Классификация и регрессия]]

Текущая версия на 17:23, 8 апреля 2019

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

Дерево решений[править]

Определение:
Дерево решений (англ. 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].

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

Недостатки рассмотренного алгоритма ID3:

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

Алгоритм CART (англ. Classification And Regression Trees)[править]

  • В отличие от ID3 работает и с непрерывными значениями признаков: на каждом шаге построения дерева последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него. Разбивает объекты на две части;
  • Использует редукцию для избежания переобучения;
  • Обрабатывает пропущенные или аномальные значения признаков.

Алгоритм C4.5[править]

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

Случайный лес[править]

Случайный лес — один из примеров объединения классификаторов в ансамбль.
Алгоритм построения случайного леса, состоящего из [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]. Для задачи классификации мы выбираем решение по большинству результатов, выданных классификаторами, а в задаче регрессии — по их среднему значению.

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

Примеры кода[править]

Примеры на языке Python[править]

  • В 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_features=2, n_redundant=0, n_informative=2,
                          random_state=1, n_clusters_per_class=1, n_classes=2)
// разбиваем выборку на обучающую и тестовую 
X = StandardScaler().fit_transform(X)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=.4, random_state=42)
// создадим классификатор на случайном лесе, состоящим из n_estimators деревьев
RandomForestClassifier(max_depth=5, n_estimators=10, max_features=1)
clf.fit(X_train, y_train)
score = clf.score(X_test, y_test)

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

Классификация RandomForestClassifier. Кружочками изображены объекты обучающей выборки, крестиками тестовой выборки. Справа цветом выделены границы принятия решений, в правом нижнем углу — значение accuracy.

Пример на языке Scala[править]

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

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

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

 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)

Пример на языке Java[править]

Пример классификации с применением weka.classifiers.trees.RandomForest[3]

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

 <dependency>
   <groupId>nz.ac.waikato.cms.weka</groupId>
   <artifactId>weka-stable</artifactId>
   <version>3.8.0</version>
 </dependency>
 import weka.classifiers.evaluation.Evaluation;
 import weka.classifiers.trees.RandomForest;
 // read dataset
 var trainingDataSet = getDataSet(...);
 var testingDataSet = getDataSet(...);
 // create random forest classifier
 var forest = new RandomForest();
 forest.setMaxDepth(15);
 forest.setNumFeatures(2);
 forest.buildClassifier(trainingDataSet);
 // evaluate the model on test dataset and print summary
 var eval = new Evaluation(trainingDataSet);
 eval.evaluateModel(forest, testingDataSet);
 System.out.println(eval.toSummaryString());

См. также[править]

Источники информации[править]

  1. Логические алгоритмы классификации — Лекция К. В. Воронцова
  2. Случайный лес — статья на Medium, Yury Kashnitskiy
  3. Деревья решений — scikit-learn.org
  4. Ансамбли классификаторов — scikit-learn.org.
    1. F1 мера
    2. Smile, Decision Trees
    3. Weka, Random Forest
    Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дерево_решений_и_случайный_лес&oldid=70887»