Изменения

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

8: '''if''' <tex>U_0 = \emptyset</tex> или <tex>U_1 = \emptyset</tex>

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