Редактирование: Дерево решений и случайный лес

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 30: Строка 30:
  
 
===Информативность ветвления===
 
===Информативность ветвления===
Для того, чтобы оценивать качество разбиения объектов по предикату <tex>\beta</tex>, введем понятие ''информационного выигрыша'' разбиения. <br>
+
Для того, чтобы оценивать качество разбиения объектов по предикату <tex>\beta</tex>, введем понятие ''меры неопределенности распределения'' значений классов среди объектов после разбиения их на множества.
Сначала оценим распределение значений классов объектов внутри каждого множества из разбиения, введя понятие ''меры неопределенности распределения''.
 
 
{{Определение
 
{{Определение
 
|id=def1  
 
|id=def1  
Строка 50: Строка 49:
 
<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_{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\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>
+
* Критерий Джини: <tex>Ф(U) = \sum\nolimits_{i != j}p_i p_j = \sum\nolimits_{i}p_i*(1-p_i)</tex>, максимизацию этого критерия можно интерпретировать как максимизацию числа пар объектов одного класса, оказавшихся после разбиения в одном множестве.
 
 
Теперь определим суммарную ''неопределенность распределения'' в разбиении.
 
 
{{Определение
 
{{Определение
 
|id=def1  
 
|id=def1  
Строка 64: Строка 60:
 
}}
 
}}
  
''Информационный выигрыш'' от разбиения определяется как изменение неопределенности в системе.
 
 
{{Определение
 
{{Определение
 
|id=def1  
 
|id=def1  
 
|neat =
 
|neat =
 
|definition=
 
|definition=
'''Информационный выигрыш от разбиения по предикату <tex>\beta</tex>''' <br>
+
'''Информационный выигрыш от ветвления вершины <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>
 
<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>
 
}}
 
}}

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: