Изменения

Покажем идею построения дерева решения на частном случае бинарного дерева. Алгоритм <tex>ID3</tex> (англ. ''Induction of Decision Tree'') заключается в последовательном дроблении выборки на две части до тех пор, пока в каждой части не окажутся объекты только одного класса. Разделение производится по предикату <tex>\beta</tex>, который выбирается из множества элементарных предикатов. На практике в качестве элементарных предикатов чаще всего берут простые пороговые условия вида <tex>\beta(x) = [f_j(x) >= d_j]</tex>. ===Информативность ветвления===Для того, чтобы оценивать качество разбиения объектов по предикату <tex>\beta</tex>, введем понятие ''меры неопределенности распределения'' значений классов среди объектов после разбиения их на множества. {{Определение|id=def1 |neat =|definition='''Частотная оценка вероятности класса <tex>y</tex> в вершине <tex>v \in V_{внутр}</tex> ''': <br><tex>p_y = P(y | x \in U) = \frac{1}{|U|} \sum\nolimits_{x_i \in U}[y_i = y]</tex>}} {{Определение|id=def1 |neat =|definition='''Мера неопределенности (англ. ''impurity'') распределения <tex>p_y</tex>''': <br>* минимальна, когда <tex>p_y \in \{0,1\}</tex>* максимальна, когда <tex>p_y = \frac{1}{|Y|}</tex> для всех <tex>y \in Y</tex>* не зависит от перенумерации классов<tex>Ф(U) = \sum\nolimits_{y \in Y} p_y L(p_y) = \frac{1}{|U|} \sum\nolimits_{x_i \in U}L(P(y_i | x_i \in U)) \rightarrow min</tex>, <br> где <tex>L(p)</tex> убывает и <tex>L(1) = 0</tex>, например: <tex>-log_2(p)</tex>, <tex>1 - p</tex>, <tex>1 - p^2</tex>}}Примеры:* Энтропия: <tex>Ф(U) = -\sum\nolimits_{i}p_i log_2p_i</tex>* Критерий Джини: <tex>Ф(U) = \sum\nolimits_{i != j}p_i p_j = \sum\nolimits_{i}p_i*(1-p_i)</tex>{{Определение|id=def1 |neat =|definition='''Неопределенность распределения <tex>P(y_i | x_i \in U_{\beta(x_i)})</tex> после ветвления вершины <tex>v</tex> по предикату <tex>\beta</tex> и разбиения <tex>U = \bigcup_{k \in D_v} U_k</tex>''': <br><tex>Ф(U_0, ... ,U_{D_v}) = \frac{1}{|U|} \sum\nolimits_{k \in D_v} \sum\nolimits_{x_i \in U_k}L(P(y_i | x_i \in U_k)) = \sum\nolimits_{k \in D_v} \frac{|U_k|}{|U|}Ф(U_k)</tex>}} {{Определение|id=def1 |neat =|definition='''Информационный выигрыш от ветвления вершины <tex>v</tex>''' <br><tex>Gain(\beta, U) = Ф(U) - Ф(U_1, ... ,U_{|D_v|}) = Ф(U) - \sum\nolimits_{k \in D_v} \frac{|U_k|}{|U|}Ф(U_k) \rightarrow max_{\beta \in B} </tex>}}