Изменения

'''Дерево решений''' (англ. ''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\beta</tex> (англ, введем понятие ''информационного выигрыша'' разбиения. <br>Сначала оценим распределение значений классов объектов внутри каждого множества из разбиения, введя понятие ''меры неопределенности распределения''.{{Определение|id=def1 |neat =|definition='Induction of Decision Tree'') заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного Частотная оценка вероятности класса. Проще всего записать этот алгоритм <tex>y</tex> в виде рекурсивной процедуры вершине <tex>ID3v \in V_{внутр}</tex>, которая строит дерево по заданной подвыборке ''': <br><tex>p_y = P(y | x \in U) = \frac{1}{|U|} \sum\nolimits_{x_i \in U}[y_i = y]</tex> и возвращает его корневую вершину.}}

1:'''function{{Определение|id=def1 |neat =|definition=''' ID3Мера неопределенности (<tex>U</tex>): 2: англ. ''impurity'if''' все объекты множества <tex>U) распределения </tex> принадлежат одному классу <tex>y \in Yp_y</tex> '''then''' 3: создать новый лист <tex>v</texbr> 4: * минимальна, когда <tex>y_v = yp_y \in \{0,1\}</tex>; 5: '''return''' v 6: найти предикат с максимальной информативностью: * максимальна, когда <tex>\betap_y = \mathrmfrac{arg1}\max_{f\in F|Y|} </tex> I(для всех <tex>fy \in Y</tex>, ;* не зависит от перенумерации классов<tex>Ф(U</tex>) 7: разбить выборку на две части <tex>U = U_0 \cup U_1</tex> по предикату <tex>\beta</tex>: <tex>U_0 := sum\nolimits_{x y \in U: f_vY} p_y L(xp_y) = 0\frac{1}{|U|}</tex> <tex>U_1 := \sum\nolimits_{x x_i \in U: f_v}L(P(xy_i | x_i \in U)) = 1\}</tex> 8: '''if''' <tex>U_0 = \emptyset</tex> или <tex>U_1 = \emptyset</tex> '''then''' 9: создать новый лист <tex>v</tex> 10: <tex>y_vrightarrow min</tex> = класс, в котором находится большинство объектов из <texbr>Uгде </tex> 11: '''else''' 12: создать новую внутреннюю вершину <tex>vL(p)</tex> 13: убывает и <tex>\beta_v L(1) = \beta0</tex> 14, например: <tex>S_0</tex> = ID3-log_2(<tex>U_0p)</tex>) 15: , <tex>S_11 - p</tex> = ID3(, <tex>U_11 - p^2</tex>) 16: '''return''' <tex>v</tex>}}

Примерами мер неопределенности распределения являются: * Энтропия: <tex>Ф(U) =-\sum\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>

Теперь определим суммарную ''неопределенность распределения'' в разбиении.{{Определение|id=def1 |neat =|definition=Критерий '''Неопределенность распределения <tex>P(y_i | x_i \in U_{\beta(x_i)})</tex> после ветвлениявершины <tex>v</tex> по предикату <tex>\beta</tex> и разбиения <tex>U =\bigcup_{k \in D_v} U_k</tex>''': <br><tex>Ф(U_0, ... ,U_{D_v}) =\frac{1}{|U|} \sum\nolimits_{k \in D_v} \sum\nolimits_{x_i \in U_k}L(P(y_i | x_i \in U_k)) =\sum\nolimits_{k \in D_v} \frac{|U_k|}{|U|}Ф(U_k)</tex>}}

''Информационный выигрыш'' от разбиения определяется как изменение неопределенности в системе.{{Определение|id=def1 |neat =|definition='''Информационный выигрыш от разбиения по предикату <tex>\beta</tex>''' <br><tex>Gain(\beta, U) =Критейрий Джини===Ф(U) - Ф(U_1, ... ,U_{|D_v|}) =Ф(U) - \sum\nolimits_{k \in D_v} \frac{|U_k|}{|U|}Ф(U_k) \rightarrow max_{\beta \in B} </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)

<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)

== Пример использования (через scikit-learn) См. также ==* [[Виды ансамблей]]

== История Источники информации ==# [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.