Изменения

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

[[Файл:BinDT1BinDT.jpg |300px|thumb|right|Классификация объекта <tex> x \in X </tex> бинарным решающим деревом]]

'''Yfunction''' classify(x):

'''whileif''' <tex>v \in V_{внутр}beta_v(x) = 1 </tex>: <tex>v := S_vR_v</tex>( '''else''' <tex>f_vv := L_v</tex>(x)) ;

{{Определение|id=def1 |neat = Рекурсивный алгоритм построения бинарного дерева решений ID3 =|definition=Идея алгоритма '''Мера неопределенности (англ. ''impurity'') распределения <tex>ID3p_y</tex> (англ. ''Induction of Decision Tree'') заключается в последовательном дроблении выборки на две части до тех пор: <br>* минимальна, когда <tex>p_y \in \{0,1\}</tex>;* максимальна, пока в каждой части когда <tex>p_y = \frac{1}{|Y|}</tex> для всех <tex>y \in Y</tex>;* не окажутся объекты только одного класса. Проще всего записать этот алгоритм в виде рекурсивной процедуры зависит от перенумерации классов<tex>ID3Ф(U) = \sum\nolimits_{y \in Y} p_y L(p_y) = \frac{1}{|U|} \sum\nolimits_{x_i \in U}L(P(y_i | x_i \in U)) \rightarrow min</tex>, которая строит дерево по заданной подвыборке <br> где <tex>UL(p)</tex> убывает и возвращает его корневую вершину.<tex>L(1) = 0</tex>, например: <tex>-log_2(p)</tex>, <tex>1 - p</tex>, <tex>1 - p^2</tex>}}

1:'''function''' ID3(<tex>U</tex>)Примерами мер неопределенности распределения являются: 2* Энтропия: '''if''' все объекты множества <tex>Ф(U</tex> принадлежат одному классу <tex>y ) = -\sum\in Ylimits_{i}^N p_i log_2p_i</tex> '''then''' 3: создать новый лист , определяется для каждого множества из разбиения, <tex>vN</tex> 4: {{---}} количество возможных классов, и <tex>y_v = yp_i</tex> 5: '''return''' v 6: найти предикат с максимальной информативностью: <tex>\beta= \mathrm{arg{---}\max_{f\in F} </tex> I(вероятность объекта принадлежать <tex>fi</tex>, <tex>U</tex>)-ому классу. 7* Критерий Джини: разбить выборку на две части <tex>Ф(U ) = U_0 \cup U_1</tex> по предикату <tex>\beta</tex>: <tex>U_0 := sum\nolimits_{x \in U: f_v(x) i != 0\j}</tex> <tex>U_1 :p_i p_j = \sum\nolimits_{x \in U: f_vi}p_i*(x1-p_i) = 1\}</tex> 8: '''if''' <tex>U_0 = \emptyset</tex> или <tex>U_1 = \emptyset</tex> '''then''' 9: создать новый лист <tex>v</tex> 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</texbr>

Теперь определим суммарную ''неопределенность распределения'' в разбиении.{{Определение|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>}}

===Рекурсивный алгоритм построения бинарного дерева решений 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> и возвращает его корневую вершину.

== Рецукция Редукция решающих деревьев ==Суть редукции (англ. ''pruning'') состоит в удалении поддеревьев, имеющих недостаточную статистическую надёжность. При этом дерево перестаёт безошибочно классифицировать обучающую выборку, зато качество классификации новых объектов, как правило, улучшается. Рассмотрим наиболее простые варианты редукции.

===Постредукция (post-pruning)===

пор, пока в дереве остаются вершины, удовлетворяющие критерию замены. <br><br>''Критерием замены'' является сокращение числа ошибок на контрольной выборке, отобранной заранее, и не участвовавшей в обучении дерева. Стандартная рекомендация — оставлять в контроле около 30% объектов. <br><br>

в качестве <tex>c_vy_v</tex> берётся тот класс, объектов которого больше всего в обучающей подвыборке <tex>U</tex>, пришедшей в вершину <tex>v</tex>.<br>

* <tex>r_L(v)</tex> — классификация поддеревом левой дочерней вершины <tex>S_v(0)L_v</tex>;* <tex>r_R(v)</tex> — классификация поддеревом правой дочерней вершины S_v(1)<tex>R_v</tex>;

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

* заменить поддерево вершины <tex>v</tex> поддеревом левой дочерней вершины Lv<tex>L_v</tex>;* заменить поддерево вершины <tex>v</tex> поддеревом правой дочерней вершины Rv<tex>R_v</tex>;

== Деревья регрессии =Пример на языке Java===Пример классификации с применением <code>weka.classifiers.trees.RandomForest</code><ref>[http://weka.sourceforge.net/doc.dev/weka/classifiers/trees/RandomForest.html Weka, Random Forest]</ref>

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

== Композиции решающих деревьев См. также ==* [[Решающий лесВиды ансамблей]]* [[Бустинг]] над решающими деревьями

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