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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 128 промежуточных версий 9 участников)
Строка 1: Строка 1:
 +
Дерево решений {{---}} логический алгоритм классификации, решающий задачи классификации и регрессии. Представляет собой объединение логических условий в структуру дерева.
 +
 
==Дерево решений==
 
==Дерево решений==
  
Строка 5: Строка 7:
 
|neat =  
 
|neat =  
 
|definition=
 
|definition=
'''Дерево решений''' (англ. ''decision tree, DT'') {{---}} алгоритм классификации <tex>a(x)</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>v \in V_{внутр}</tex> определены функции: <tex> f_v : X \rightarrow D_v </tex> и <tex> D_v : X \rightarrow V </tex>, <tex>D_v < \infty</tex>
+
* <tex> S_v : D_v \rightarrow V_v </tex> {{---}} функция перехода по значению предиката в множество детей вершины <tex>v</tex>;
* Для <tex>v \in V_{лист}</tex> определена метка класса <tex>y_v \in Y</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  
 
|id=def1  
 
|neat =
 
|neat =
 
|definition=
 
|definition=
'''Бинарное решающее дерево''' {{---}}  это алгоритм классификации, задающийся бинарным деревом, в котором каждой внутренней вершине <tex> v \in V </tex> приписан предикат <tex> \beta_v : X \rightarrow {0, 1} </tex>, каждой терминальной вершине <tex> v \in V </tex> приписано имя класса <tex> c_v \in Y </tex>. При классификации объекта <tex> x \in X </tex> он проходит по дереву путь от корня до некоторого листа, в соответствии с Алгоритмом 1.5.
+
'''Бинарное дерево решений''' {{---}}  частный случай дерева решений, для которого <tex> D_v = \{0,1\} </tex>.
 
}}
 
}}
 
[[Файл:BinDT.jpg |300px|thumb|right|Классификация объекта <tex> x \in X </tex> бинарным решающим деревом]]
 
[[Файл:BinDT.jpg |300px|thumb|right|Классификация объекта <tex> x \in X </tex> бинарным решающим деревом]]
  
  '''void''' fix('''int''' i):
+
  '''function''' classify(x):
   '''if''' d[i] == b
+
   <tex>v = v_0</tex>
    d[i] = 0
+
   '''if''' <tex>\beta_v(x) = 1 </tex>
    d[i + 1]++
+
      <tex>v := R_v</tex>
   '''if''' d[i + 1] == b - 1:
 
    L'[i] = L'[i + 1]
 
 
   '''else'''
 
   '''else'''
     L'[i] = i + 1
+
      <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:
 +
* Применим только для дискретных значений признаков;
 +
* Переобучение;
 +
* На каждом шаге решение принимается по одному атрибуту.
 +
 
 +
=== Алгоритм [https://en.wikipedia.org/wiki/Predictive_analytics#Classification_and_regression_trees_.28CART.29 CART] (англ. ''Classification And Regression Trees'')===
 +
* В отличие от ID3 работает и с непрерывными значениями признаков: на каждом шаге построения дерева последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него. Разбивает объекты на две части;
 +
* Использует редукцию для избежания переобучения;
 +
* Обрабатывает пропущенные или аномальные значения признаков.
 +
 
 +
=== Алгоритм [https://en.wikipedia.org/wiki/C4.5_algorithm C4.5] ===
 +
* Также работает и с непрерывными значениями признаков: на каждом шаге построения дерева выбирает правило разбиения по одному из признаков. Разбивает объекты на несколько частей по этому правилу, рекурсивно запускается из полученных подмножеств;
 +
* Использует редукцию для избежания переобучения;
 +
* Обрабатывает пропущенные или аномальные значения признаков.
 +
 
 +
== Случайный лес ==
 +
Случайный лес {{---}} один из примеров объединения классификаторов в [[Виды_ансамблей|ансамбль]]. <br>
 +
Алгоритм построения случайного леса, состоящего из <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>
 +
 
 +
Таким образом, случайный лес {{---}} бэггинг над решающими деревьями, при обучении которых для каждого разбиения признаки выбираются из некоторого случайного подмножества признаков.
 +
 
 +
==Примеры кода==
 +
===Примеры на языке 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 случайный лес], которые были описаны выше.
 +
<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)
  
=== Что находится в листьях ===
+
===Пример на языке Java===
 +
Пример классификации с применением <code>weka.classifiers.trees.RandomForest</code><ref>[http://weka.sourceforge.net/doc.dev/weka/classifiers/trees/RandomForest.html Weka, Random Forest]</ref>
  
=== Передача информации между вершинами ===
+
<code>Maven</code> зависимость:
* (alternating decision tree)
+
  <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());
  
=== Полужадный синтез ===
+
=== Пример на языке R ===
 +
{{Main|Примеры кода на R}}
 +
==== Деревья решений ====
 +
Для создания деревьев решений используется функция <code>ctree()</code> из пакета <code>party</code>.
  
== Алгоритмы построения решающих деревьев ==
+
<font color="gray"># importing package </font>
 +
install.packages(<font color="green">"party"</font>)
 +
 +
<font color="gray"># reading data</font>
 +
rdata <- read.csv(<font color="green">"input.csv"</font>, <font color="#660099">sep</font> = <font color="green">','</font>, <font color="#660099">header</font> = FALSE)
 +
 +
<font color="gray"># evaluating model</font>
 +
output.tree <- ctree(target ~ x + y + z, <font color="#660099">data</font> = rdata)
 +
 +
<font color="gray"># plotting results</font>
 +
plot(output.tree)
  
* [[Алгоритм ID3]]
+
==== Случайный лес ====
* [[Алгоритм C4.5]]
+
Для создания случайного леса необходимо импортировать пакет <code>randomForest</code>
* [[Алгоритм C5.0]]
 
* [[Алгоритм CART]]
 
* [[Алгоритм LISTBB]]
 
  
== Обобщающая способность решающих деревьев ==
+
<font color="gray"># importing packages </font>
 +
install.packages(<font color="green">"party"</font>)
 +
install.packages(<font color="green">"randomForest"</font>)
 +
 +
<font color="gray"># reading data</font>
 +
rdata <- read.csv(<font color="green">"input.csv"</font>, <font color="#660099">sep</font> = <font color="green">','</font>, <font color="#660099">header</font> = FALSE)
 +
 +
<font color="gray"># creating the forest</font>
 +
output.forest <- randomForest(target ~ x + y + z, <font color="#660099">data</font> = rdata)
 +
 +
<font color="gray"># getting results</font>
 +
print(output.forest)
  
== Композиции решающих деревьев ==
+
== См. также ==
* [[Решающий лес]]
+
* [[Виды ансамблей]]
* [[Бустинг]] над решающими деревьями
 
  
== История ==
+
== Источники информации ==
 +
# [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.
  
== Ссылки ==
 
*[http://www.stat.cmu.edu/~cshalizi/350/lectures/22/lecture-22.pdf Classification and Regression Trees] — лекции Cosma Shalizi, ноябрь 2009.
 
  
== Литература ==
+
[[Категория: Машинное обучение]]
 +
[[Категория: Классификация и регрессия]]

Текущая версия на 19:22, 4 сентября 2022

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

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

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

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

Основная статья: Примеры кода на R

Деревья решений

Для создания деревьев решений используется функция ctree() из пакета party.

# importing package 
install.packages("party")

# reading data
rdata <- read.csv("input.csv", sep = ',', header = FALSE)

# evaluating model
output.tree <- ctree(target ~ x + y + z, data = rdata)

# plotting results
plot(output.tree)

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

Для создания случайного леса необходимо импортировать пакет randomForest

# importing packages 
install.packages("party")
install.packages("randomForest")

# reading data
rdata <- read.csv("input.csv", sep = ',', header = FALSE)

# creating the forest
output.forest <- randomForest(target ~ x + y + z, data = rdata)

# getting results
print(output.forest)

См. также

Источники информации

  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=85012»