Изменения

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

* <tex> V = V_{внутр} \cup V_{лист} </tex> {{---}} множество вершин , <tex>v_0 \in V</tex> {{---}} корень дерева;* <tex> S_v : D_v \rightarrow V_v </tex> {{---}} функция перехода по значению предиката в множество детей вершины <tex>v</tex>;* <tex> \beta_v : X \rightarrow D_v </tex> {{---}} предикат ветвления, <tex>v \in V_{внутр}</tex> и <tex>|D_v| < \infty</tex>;* Для листьев <tex>v \in V_{лист}</tex> определена метка класса <tex>y_v \in Y</tex>.

'''if''' <tex>\beta_v(x) = 1 </tex> '''then'''

* минимальна, когда <tex>p_y \in \{0,1\}</tex>;* максимальна, когда <tex>p_y = \frac{1}{|Y|}</tex> для всех <tex>y \in Y</tex>;

ПримерыПримерами мер неопределенности распределения являются:* Энтропия: <tex>Ф(U) = -\sum\nolimits_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> Теперь определим суммарную ''неопределенность распределения'' в разбиении.

'''Информационный выигрыш от ветвления вершины разбиения по предикату <tex>v\beta</tex>''' <br>

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

Эти величины сравниваются, и, в зависимости от того, какая из них оказалась

*[httpsНедостатки рассмотренного алгоритма ID3://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] (англ. ''bootstrap aggregationClassification And Regression Trees'') — один из первых ===* В отличие от ID3 работает и самых простых видов ансамблей, который позволяет оценивать многие статистики сложных распределений и заключается в следующем. Пусть имеется выборка <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. ''bagging'')wikipedia. Пусть имеется обучающая выборка <tex>X<org/tex>. С помощью бутстрэпа сгенерируем из неё выборки <tex>X_1 ... X_M<wiki/tex>C4. Теперь на каждой выборке обучим свой классификатор <tex>a_i(x)</tex>5_algorithm C4. Итоговый классификатор будет усреднять ответы всех этих алгоритмов <tex>a(x) 5] == \frac{1}{M} \sum\limits_{i = 1}^{M} a_i(x)</tex>* Также работает и с непрерывными значениями признаков: на каждом шаге построения дерева выбирает правило разбиения по одному из признаков. Разбивает объекты на несколько частей по этому правилу, рекурсивно запускается из полученных подмножеств;* Использует редукцию для избежания переобучения;* Обрабатывает пропущенные или аномальные значения признаков.

=== Случайный лес ===Случайный лес {{---}} один из примеров объединения классификаторов в [[Виды_ансамблей|ансамбль]]. <br>Алгоритм построения случайного леса, состоящего из <tex>N</tex> деревьев на основе обучающей выборки <tex>X</tex>такой:

<font color=green>// сгенерировать выборку <tex>X_n</tex> c помощью [[Виды_ансамблей#Бутстрэп|бутстрэпа]]</font> <tex>X_n</tex> = bootstrap(<tex>X</tex>) <font color=green>// построить решающее дерево <tex>t_n</tex> по выборке <tex>X_n</tex></font> <tex>t_n</tex> = ID3(<tex>X_n</tex>) <br>

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

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

== Примеры использования (в scikit-learn) кода=====Примеры на языке 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];

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

<font color=green>// сгенерируем рандомный обучающий набор случайную обучающую выборку с классификацией по n_classes классам</font> X, y = make_classification(n_samplesn_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 =1000train_test_split(X, n_featuresy, test_size=.4, n_classes random_state= 542)

clf = RandomForestClassifier(max_depth=5, n_estimators=10010, max_depthmax_features=21) <font color=green>// обучим классификатор на сгенерированном обучающем множестве</font> clf.fit(XX_train, yy_train) score = clf.predictscore([[0, 0, 0X_test, 0]]y_test)

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

== Ссылки =Пример на языке 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> зависимость: <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) ==== Случайный лес ====Для создания случайного леса необходимо импортировать пакет <code>randomForest</code>  <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.  [[Категория: Машинное обучение]][[Категория: Классификация и регрессия]]