Изменения

'''Дерево решений''' (англ. ''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 S_v : D_v \in V_rightarrow V_v </tex> {{внутр---}}функция перехода по значению предиката в множество детей вершины <tex>v</tex> определены предикат ветвления: ;* <tex> \beta_v : X \rightarrow D_v </tex>{{---}} предикат ветвления, <tex>|D_v| < v \inftyin V_{внутр}</tex> и функция перехода в следующую вершину по значению предиката <tex> S_v : |D_v | < \rightarrow 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>a(x) = \frac{1}{N} \sum\limits_{i = 1}^{N} t_iID3(x)<tex>X_n</tex>. Для задачи кассификации мы выбираем решение по большинству результатов, выданных классификаторами, а в задаче регрессии — по их среднему значению. ) <br> Таким образом, случайный лес — это бэггинг над решающими деревьями, при обучении которых для каждого разбиения признаки выбираются из некоторого случайного подмножества признаков.

Итоговый классификатор {{---}} <tex>a(x) =\frac{1}{N} \sum\limits_{i = Примеры использования 1}^{N} t_i(через scikit-learnx) ==*[https:<//scikittex>. Для задачи классификации мы выбираем решение по большинству результатов, выданных классификаторами, а в задаче регрессии {{---learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html#sklearn.tree}} по их среднему значению.DecisionTreeClassifier DecisionTreeClassifier] - используется для классификации <br>

'''from''' sklearn '''import''' tree <font color=green>// X Таким образом, случайный лес {{--- массив}} бэггинг над решающими деревьями, содержащий описание объектов при обучении которых для каждого разбиения признаки выбираются из обучающей выборки</font> X = [[0, 0], [1, 1]] <font color=green>// Y - значения классов объектов из обучающей выборки </font> Y = [0, 1] clf = tree.DecisionTreeClassifier() <font color=green> // обучение классификатора </font> clf = clf.fit(X, Y) <font color=green> // предсказание значений классов </font> clfнекоторого случайного подмножества признаков.predict([[2, 2]]) <font color=green> // вывод: array([1]) </font>

==Примеры кода=====Примеры на языке Python===*Для решения задачи задач классификации и регрессии используют [https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressorDecisionTreeClassifier.html#sklearn.tree.DecisionTreeRegressor DecisionTreeRegressor] '''from''' sklearn '''import''' tree X = [[0, 0DecisionTreeClassifier DecisionTreeClassifier], [2, 2]] y = [0https://scikit-learn.5, 2org/stable/modules/generated/sklearn.5] clf = tree.DecisionTreeRegressor() clf = clf.fit(X, y) clfhtml#sklearn.predict([[1, 1]]) <font color=green> // вывод: array([0tree.5DecisionTreeRegressor DecisionTreeRegressor]) </font>;

*В '''sklearn.ensemble''' также представлены методы классификации, основанные на ансамблях, в том числе: [https://scikit-learn.org/stable/modules/ensemble.html#bagging бэггинг] и [https://scikit-learn.org/stable/modules/ensemble.html#forest случайный лес], которые были описаны выше. <br>Так, в этом примере создается бэггинг ансамбль из классификаторов '''KNeighborsClassifier''', каждый из которых обучен на рандомных случайных подмножествах из 50% объектов из обучающей выборки, и 50% рандомно случайно выбранных признаков.

Пример использования классификатора на случайном лесе:Полную версию кода можно найти [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> зависимость: <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.statmachinelearning.cmu.eduru/~cshaliziwiki/350images/lectures3/223e/lectureVoron-22ML-Logic.pdf Classification Логические алгоритмы классификации] {{---}} Лекция К. В. Воронцова# [https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-5-ensembles-of-algorithms-and Regression Trees-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 Ансамбли классификаторов] — лекции Cosma Shalizi, ноябрь 2009scikit-learn.org.  [[Категория: Машинное обучение]][[Категория: Классификация и регрессия]]