Изменения

Перейти к: навигация, поиск

Дерево решений и случайный лес

499 байт добавлено, 01:06, 23 января 2019
Информативность ветвления
===Информативность ветвления===
Для того, чтобы оценивать качество разбиения объектов по предикату <tex>\beta</tex>, введем понятие ''меры неопределенности распределенияинформационного выигрыша'' разбиения. <br>Сначала оценим распределение значений классов среди объектов после внутри каждого множества из разбиения их на множества, введя понятие ''меры неопределенности распределения''.
{{Определение
|id=def1
<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\limits_{i}^N p_i log_2p_i</tex>, определяется для каждого множества из разбиения, <tex>N</tex> {{---}} количество возможных классов, и <tex>p_i</tex> {{--- }} вероятность объекта принадлежать <tex> i</tex>-ому классу.* Критерий Джини: <tex>Ф(U) = \sum\nolimits_{i != j}p_i p_j = \sum\nolimits_{i}p_i*(1-p_i)</tex>, максимизацию этого критерия можно интерпретировать как максимизацию числа пар объектов одного класса, оказавшихся после разбиения в одном множестве. <br> Теперь определим суммарную ''неопределенность распределения'' в разбиении.
{{Определение
|id=def1
}}
''Информационный выигрыш'' от разбиения определяется как изменение неопределенности в системе.
{{Определение
|id=def1
|neat =
|definition=
'''Информационный выигрыш от ветвления вершины разбиения по предикату <tex>v\beta</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>
}}
635
правок

Навигация