Изменения

Перейти к: навигация, поиск

Дерево решений и случайный лес

4705 байт добавлено, 20:02, 20 января 2019
Нет описания правки
Идея алгоритма <tex>ID3</tex> (англ. ''Induction of Decision Tree'') заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Проще всего записать этот алгоритм в виде рекурсивной процедуры <tex>ID3</tex>, которая строит дерево по заданной подвыборке <tex>U</tex> и возвращает его корневую вершину.
1:'''Vfunction''' 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_{f\in F} </tex> GainI(<tex>f</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</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</tex>
===Мера неопределенности распределенияИнформативность===
===Критерий ветвления===
====Энтропийный критерий====
 ==Рецукция решающих деревьев = Критерии =Суть редукции состоит в удалении поддеревьев, имеющих недостаточную статистическую надёжность. При этом дерево перестаёт безошибочно классифицировать обучающую выборку, зато качество классификации новых объектов, как правило, улучшается. Рассмотрим наиболее простые варианты редукции. ===Предредукция===Предредукция (англ. ''pre-pruning'') или критерий раннего останова досрочно прекращает дальнейшее ветвление в вершине дерева, если информативность <tex>I(\beta, U)</tex> для всех возможных предикатов <tex>\beta</tex> не дотягивает до заданного порогового значения <tex>I_0</tex>. <br>Для этого на шаге 8 алгоритма <tex>ID3</tex> условие <tex>U_0 =\emptyset</tex> или <tex>U_1 =\emptyset</tex> заменяется условием <tex>I(\beta, U) <=I_0 </tex>. Порог <tex>I_0 </tex> является управляющим параметром метода. <br>Предредукция считается не самым эффективным способом избежать переобучения, так как жадное ветвление по-прежнему остаётся глобально неоптимальным. Более эффективной считается cтратегия постредукции. ===Постредукция (post-pruning)===Постредукция (англ. ''post-pruning'') просматривает все внутренние вершины дерева и заменяет отдельные вершины либо одной из дочерних вершин (при этом вторая дочерняя удаляется), либо терминальной вершиной. Процесс замен продолжается до техпор, пока в дереве остаются вершины, удовлетворяющие критерию замены. <br>''Критерием замены'' является сокращение числа ошибок на контрольной выборке, отобранной заранее, и не участвовавшей в обучении дерева. Стандартная рекомендация — оставлять в контроле около 30% объектов. <br>Для реализации постредукции контрольная выборка <tex>X^k</tex> пропускается черезРекурсию останавливают построенное дерево. При этом в каждой внутренней вершине <tex>v</tex> запоминается подмножество <tex>S_v \subseteq X_k</tex> попавших в следующих случаяхнеё контрольных объектов. Если <tex>S_v = \emptyset </tex>, то вершина <tex>v</tex> считается ненадёжной и заменяется терминальной по ''мажоритарному правилу'': <br>в качестве <tex>c_v</tex> берётся тот класс, объектов которого больше всего в обучающей подвыборке <tex>U</tex>, пришедшей в вершину <tex>v</tex>.Затем для каждой внутренней вершины <tex>v</tex> вычисляется число ошибок, полученных при классификации выборки <tex>S_v</tex> следующими способами: <br>* Все объекты множества <tex>Ur(v)</tex> — классификация поддеревом, растущим из вершины <tex>v</tex>;* <tex>r_L(v)</tex> — классификация поддеревом левой дочерней вершины <tex>S_v(0)</tex>;* <tex>r_R(v)</tex> — классификация поддеревом правой дочерней вершины S_v(1);* <tex>r_c(v)</tex> — отнесение всех объектов выборки <tex>S_v</tex> принадлежат одному к классу <tex>y \in Y</tex>. <br>Эти величины сравниваются, и, в зависимости от того, какая из них оказаласьминимальной, принимается, тогда создается лист соответственно, одно из четырёх решений: <br>* сохранить поддерево вершины <tex>v</tex>;* заменить поддерево вершины <tex>v</tex> поддеревом левой дочерней вершины Lv;* заменить поддерево вершины <tex>v</tex> поддеревом правой дочерней вершины Rv;* заменить поддерево <tex>v</tex> с меткой терминальной вершиной класса <tex>y_v = \mathrm{arg}\min_{y\in Y}r_c(v) </tex> . 
== Деревья регрессии ==
* [[Критерий Джини]]
 
=== Рецукция решающих деревьев ===
* [[Предредукция]]
* [[Постредукция]]
=== Оценивание вероятностей ===
Анонимный участник

Навигация