635
правок
Изменения
→Рекурсивный алгоритм построения бинарного дерева решений ID3
== Рекурсивный алгоритм построения бинарного дерева решений 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>):
4: <tex>y_v = y</tex>
5: '''return''' v
6: найти предикат с максимальной информативностью: <tex>\beta= \mathrm{arg}\max_{f\beta\in FB} </tex> IGain(<tex>f\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>
