Изменения

* <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>.

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

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

* === Алгоритм C4[https://en.5** В отличие от ID3 работает и с непрерывными значениями признаков: устанавливает для них пороговые значения и по ним разбивает объекты на две части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] =======Бутстрэп====Метод бутстрэпа (англ. ''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>. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределенияполученных подмножеств;* Использует редукцию для избежания переобучения;* Обрабатывает пропущенные или аномальные значения признаков.

====Бэггинг==Случайный лес ==Рассмотрим, следующий вид ансамбля — бэггинг (англ. ''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)один из примеров объединения классификаторов в [[Виды_ансамблей|ансамбль]]. </texbr>.  Алгоритм построения случайного леса, состоящего из <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(X_test, y_test) Результат классификации показан на рисунке.  [[0Файл:RFC.png |800px|thumb|center|Классификация RandomForestClassifier. Кружочками изображены объекты обучающей выборки, 0крестиками тестовой выборки. Справа цветом выделены границы принятия решений, 0, 0в правом нижнем углу {{---}} значение 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.  [[Категория: Машинное обучение]][[Категория: Классификация и регрессия]]