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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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>
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 45: Строка 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>
Строка 75: Строка 75:
 
=== Рекурсивный алгоритм построения бинарного дерева решений ID3 ===
 
=== Рекурсивный алгоритм построения бинарного дерева решений ID3 ===
 
Покажем идею построения дерева решения на частном случае бинарного дерева. Алгоритм <tex>ID3</tex> (англ. ''Induction of Decision Tree'') заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Разделение производится по предикату <tex>\beta</tex>, который выбирается из множества элементарных предикатов. На практике в качестве элементарных предикатов чаще всего берут простые пороговые условия вида <tex>\beta(x) = [f_j(x) >= d_j]</tex>.  
 
Покажем идею построения дерева решения на частном случае бинарного дерева. Алгоритм <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> и возвращает его корневую вершину.  
+
 
 +
<br><br>Проще всего записать этот алгоритм в виде рекурсивной процедуры <tex>ID3</tex>, которая строит дерево по заданной подвыборке <tex>U</tex> и возвращает его корневую вершину.  
  
 
  1:'''function''' ID3(<tex>U</tex>):
 
  1:'''function''' ID3(<tex>U</tex>):
Строка 82: Строка 83:
 
  3:      v = createLeafVertex(<tex>y_v</tex>)
 
  3:      v = createLeafVertex(<tex>y_v</tex>)
 
  4:      '''return''' v
 
  4:      '''return''' v
       <font color=green>// найти предикат с максимальным информационным выигрышом </font>
+
       <font color=green>// найти предикат с максимальной информативностью </font>
 
       <tex>\beta= \mathrm{arg}\max_{\beta\in B} </tex> Gain(<tex>\beta</tex>, <tex>U</tex>)
 
       <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>
 
       <font color=green>// разбить выборку на две части <tex>U = U_0 \cup U_1</tex> по предикату <tex>\beta</tex> </font>
Строка 100: Строка 101:
  
 
== Редукция решающих деревьев ==
 
== Редукция решающих деревьев ==
Суть редукции (англ. ''pruning'') состоит в удалении поддеревьев, имеющих недостаточную статистическую надёжность. При этом дерево перестаёт безошибочно классифицировать обучающую выборку, зато качество классификации новых объектов, как правило, улучшается. Рассмотрим наиболее простые варианты редукции.
+
Суть редукции состоит в удалении поддеревьев, имеющих недостаточную статистическую надёжность. При этом дерево перестаёт безошибочно классифицировать обучающую выборку, зато качество классификации новых объектов, как правило, улучшается. Рассмотрим наиболее простые варианты редукции.
  
 
===Предредукция===
 
===Предредукция===
Строка 119: Строка 120:
 
* <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>;
Строка 127: Строка 128:
  
 
== Алгоритмы построения деревьев решения ==
 
== Алгоритмы построения деревьев решения ==
Недостатки рассмотренного алгоритма ID3:
+
*[https://en.wikipedia.org/wiki/ID3_algorithm Алгоритм 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>.
* Использует редукцию для избежания переобучения;
 
* Обрабатывает пропущенные или аномальные значения признаков.
 
  
== Случайный лес ==
+
=== Случайный лес ===
Случайный лес {{---}} один из примеров объединения классификаторов в [[Виды_ансамблей|ансамбль]]. <br>
+
Алгоритм построения случайного леса, состоящего из <tex>N</tex> деревьев на основе обучающей выборки <tex>X</tex>:
Алгоритм построения случайного леса, состоящего из <tex>N</tex> деревьев на основе обучающей выборки <tex>X</tex> такой:
 
 
  '''for''' (n: 1,...,N):
 
  '''for''' (n: 1,...,N):
     <font color=green>// сгенерировать выборку <tex>X_n</tex> c помощью [[Виды_ансамблей#Бутстрэп|бутстрэпа]]</font>
+
     сгенерировать выборку <tex>X_n</tex> c помощью бутстрэпа
     <tex>X_n</tex> = bootstrap(<tex>X</tex>)
+
     построить решающее дерево <tex>t_n</tex> по выборке <tex>X_n</tex><br>
    <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) ==
===Примеры на языке 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]
*Для решения задач классификации и регрессии используют [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
Строка 167: Строка 163:
  
 
Пример использования классификатора на случайном лесе:
 
Пример использования классификатора на случайном лесе:
Полную версию кода можно найти [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_features=2, n_redundant=0, n_informative=2,
+
  X, y = make_classification(n_samples=1000, n_features=4, n_classes = 5)
                          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>
  RandomForestClassifier(max_depth=5, n_estimators=10, max_features=1)
+
  clf = RandomForestClassifier(n_estimators=100, max_depth=2)
  clf.fit(X_train, y_train)
+
<font color=green>// обучим классификатор на сгенерированном обучающем множестве</font>
  score = clf.score(X_test, y_test)
+
  clf.fit(X, y)
 +
  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"
Строка 203: Строка 191:
 
   plot(x, y, dt)
 
   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>
+
*[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.
<code>Maven</code> зависимость:
+
*[https://scikit-learn.org/stable/modules/tree.html Деревья решений] scikit-learn.org.
  <dependency>
+
*[https://scikit-learn.org/stable/modules/ensemble.html Ансамбли] — scikit-learn.org.
    <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.
 
 
 
 
 
[[Категория: Машинное обучение]]
 
[[Категория: Классификация и регрессия]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: