Изменения

* Для <tex>v \in V_{внутр}</tex> определены функциипредикат ветвления: <tex> f_v \beta_v : X \rightarrow D_v </tex> и , <tex> |D_v : X | < \rightarrow V infty</tex>, и функция перехода в следующую вершину по значению предиката <tex>|S_v : D_v| < \inftyrightarrow V </tex>,

'''Бинарное решающее дереворешений''' {{---}} частный случай дерева решений, для которого <tex> D_v = \{0,1\} </tex>.* Пример <tex>f_v \beta_v = [f_j(x) > a_j]</tex>, где <tex>f_j(x)</tex> - значение <tex>j</tex>-ого признака объекта <tex>x \in X</tex>

== Алгоритм Рекурсивный алгоритм построения решающего бинарного дерева решений ID3 ==Идея алгоритма <tex>ID3</tex> (англ. ''Induction of Decision Tree'') заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Проще всего записать этот алгоритм в виде рекурсивной процедуры <tex>TreeGrowingID3</tex>, которая строит дерево по заданной подвыборке <tex>U</tex> и возвращает его корневую вершину.TODO: возможные StopCriterion, Major

'''V''' TreeGrowingID3(<tex>U</tex>): '''if''' StopCriterion(все объекты множества <tex>U</tex>)принадлежат одному классу <tex>y \in Y</tex> '''then''' '''return''' создать новый лист <tex>v</tex>, взяв <tex>y_v</tex> := Major(<tex>Uy</tex>) '''return''' v выбрать признак, наиболее выгодный для ветвления дереванайти предикат с максимальной информативностью: <tex>f_v \beta= \mathrm{arg}\max_{f\in F} </tex> Gain(<tex>f</tex>, <tex>U</tex>) '''if''' Gain(разбить выборку на две части <tex>f_vU = U_0 \cup U_1</tex>, по предикату <tex>U\beta</tex>: <tex>U_0 := \{x \in U: f_v(x) = 0\}</tex> < G_0tex>U_1 := \{x \in U: f_v(x) = 1\}</tex> '''thenif'''<tex>U_0 = \emptyset</tex> или <tex>U_1 = \emptyset</tex> '''returnthen''' создать новый лист <tex>v</tex> взяв <tex>y_v</tex> := Major(класс, в котором находится большинство объектов из <tex>U</tex>) '''else''' создать новую внутреннюю вершину <tex>v</tex> с функцией <tex>f_v\beta_v = \beta</tex> '''for''' ( <tex>k \in D_vS_0</tex>): = ID3(<tex>U_k := \{x \in U: f_v(x) = k\}U_0</tex>) <tex>S_v(k)S_1</tex> := TreeGrowingID3(<tex>U_kU_1</tex>)

 == Разновидности решающих деревьев Деревья регрессии == === Тип задачи ===* [[Классификация]]* [[Регрессия]]