635
правок
Изменения
Нет описания правки
== Основные определения Алгоритм построения решающего дерева ID3 ==Идея алгоритма <tex>ID3</tex> (англ. ''Induction of Decision Tree'') заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Проще всего записать этот алгоритм в виде рекурсивной процедуры <tex>TreeGrowing</tex>, которая строит дерево по заданной подвыборке <tex>U</tex> и возвращает его корневую вершину.TODO: возможные StopCriterion, Major '''V''' TreeGrowing(<tex>U</tex>): '''if''' StopCriterion(<tex>U</tex>)'''then''' '''return''' новый лист <tex>v</tex>, взяв <tex>y_v</tex> := Major(<tex>U</tex>) выбрать признак, наиболее выгодный для ветвления дерева: <tex>f_v = \mathrm{arg}\max_{f\in F} </tex> Gain(<tex>f</tex>, <tex>U</tex>) '''if''' Gain(<tex>f_v</tex>, <tex>U</tex>) <tex> < G_0</tex> '''then''' '''return''' новый лист <tex>v</tex> взяв <tex>y_v</tex> := Major(<tex>U</tex>) создать новую внутреннюю вершину <tex>v</tex> с функцией <tex>f_v</tex> '''for''' (<tex>k \in D_v</tex>): <tex>U_k := \{x \in U: f_v(x) = k\}</tex> <tex>S_v(k)</tex> := TreeGrowing(<tex>U_k</tex>) '''return''' <tex>v</tex> ===Мера неопределенности распределения=== ===Критерий ветвления=== ====Критейрий Джини========Энтропийный критерий====
== Разновидности решающих деревьев ==
