Изменения

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

== Рекурсивный алгоритм построения бинарного дерева решений ID3 =Информативность ветвления=Идея алгоритма <tex>ID3</tex> (англ. ''Induction of Decision Tree'') заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Разделение производится по предикату <tex>\beta</tex>, который выбирается из множества элементарных предикатов. На практике в качестве элементарных предикатов чаще всего берут простые пороговые условия вида <tex>\beta(x) = [f_j(x) >= d_j]</tex>.<br><br>Проще всего записать этот алгоритм в виде рекурсивной процедуры <tex>ID3</tex>Для того, которая строит дерево чтобы оценивать качество разбиения объектов по заданной подвыборке <tex>U</tex> и возвращает его корневую вершину.   1:'''function''' ID3(<tex>U</tex>): 2: '''if''' все объекты множества <tex>U</tex> принадлежат одному классу <tex>y \in Y</tex> '''then''' 3: создать новый лист <tex>v</tex> 4: <tex>y_v = y</tex> 5: '''return''' v 6: найти предикат с максимальной информативностью : <tex>\beta= \mathrm{arg}\max_{\beta\in B} </tex> Gain(предикату <tex>\beta</tex>, <tex>U</tex>) 7: разбить выборку на две части <tex>U = U_0 \cup U_1</tex> по предикату <tex>\beta</tex>: <tex>U_0 := \{x \in U: f_v(x) = 0\}</tex> <tex>U_1 := \{x \in U: f_v(x) = 1\}</tex> 8: введем понятие '''if'информационного выигрыша'' разбиения. <tex>U_0 = \emptyset</tex> или <tex>U_1 = \emptyset</tex> '''then''' 9: создать новый лист <tex>v</texbr> 10: <tex>y_v</tex> = класс, в котором находится большинство Сначала оценим распределение значений классов объектов внутри каждого множества из <tex>U</tex> 11: разбиения, введя понятие ''меры неопределенности распределения'else''' 12: создать новую внутреннюю вершину <tex>v</tex> 13: <tex>\beta_v = \beta</tex> 14: <tex>S_0</tex> = ID3(<tex>U_0</tex>) 15: <tex>S_1</tex> = ID3(<tex>U_1</tex>) 16: '''return''' <tex>v</tex> ===Критерии информативности===.

* минимальна, когда <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/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>Алгоритм построения случайного леса, состоящего из <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]; *В '''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>

* [[Алгоритм ID3]] <font color="gray"># importing packages </font>* [[Алгоритм C4 install.5]]packages(<font color="green">"party"</font>)* [[Алгоритм C5 install.0]]packages(<font color="green">"randomForest"</font>)* [[Алгоритм CART]] * [[Алгоритм LISTBB]] <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.