Изменения

'''Дерево решений''' (англ. ''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>

== Рецукция = Рекурсивный алгоритм построения бинарного дерева решений 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'') состоит в удалении поддеревьев, имеющих недостаточную статистическую надёжность. При этом дерево перестаёт безошибочно классифицировать обучающую выборку, зато качество классификации новых объектов, как правило, улучшается. Рассмотрим наиболее простые варианты редукции.

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

Недостатки рассмотренного алгоритма ID3: * Применим только для дискретных значений признаков;* Переобучение;*На каждом шаге решение принимается по одному атрибуту. === Алгоритм [https://en.wikipedia.org/wiki/ID3_algorithm Алгоритм 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>Алгоритм CARTпостроения случайного леса, состоящего из <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]; * Алгоритм LISTBBВ '''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> зависимость: <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)

== Композиции решающих деревьев См. также ==Для повышения точности модели применяют объединения моделей (классификаторов) в ансамбль. ===* [[Виды ансамблей=======Бустинг (англ. ''boosting'')====При бустинге происходит последовательное обучение классификаторов. Таким образом, обучающий набор данных на каждом последующем шаге зависит от точности прогнозирования предыдущего базового классификатора. Первый алгоритм Boost1, например, применял три базовых классификатора. При этом первый классификатор обучался на всем наборе данных, второй на выборке примеров, а третий – на наборе тех данных, где результаты прогнозирования первых двух классификаторов разошлись. Современная модификация первого алгоритма подразумевает использование неограниченного количества классификаторов, каждый из которых обучается на одном наборе примеров, поочередно применяя их на различных шагах.====Бутстрэп====Метод бутстрэпа (англ. ''bagging or 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>. Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.]]

== Пример использования (через Источники информации ==# [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.