Точный сплиттер для двоичной классификации с числовыми признаками, Точный сплиттер для двоичной классификации с числовыми признаками

В этом модуле вы изучите простейший и наиболее распространенный алгоритм разделения, который создает условия вида $\mathrm{feature}_i \geq t$ в следующих настройках:

• Задача двоичной классификации
• Без пропущенных значений в примерах
• Без заранее вычисленного индекса в примерах

Предположим, имеется набор из $n$ примеров с числовым признаком и двоичной меткой «оранжевый» и «синий». Формально опишем набор данных $D$ как:

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

где:

• $x_i$ — значение числового признака в $\mathbb{R}$ (множестве действительных чисел).
• $y_i$ — значение метки двоичной классификации в {оранжевом, синем} цвете.

Наша цель — найти такое пороговое значение $t$ (порог), при котором разделение примеров $D$ на группы $T(rue)$ и $F(alse)$ по условию $x_i \geq t$ улучшает разделение меток; например, больше «оранжевых» примеров в $T$ и больше «синих» примеров в $F$.

Энтропия Шеннона является мерой беспорядка. Для двоичной метки:

• Энтропия Шеннона максимальна, когда метки в примерах сбалансированы (50% синего и 50% оранжевого).
• Энтропия Шеннона минимальна (значение 0), когда метки в примерах чистые (100% синие или 100% оранжевые).

Рисунок 8. Три разных уровня энтропии.

Формально мы хотим найти условие, уменьшающее взвешенную сумму энтропии распределений меток в $T$ и $F$. Соответствующая оценка — это прирост информации , который представляет собой разницу между энтропией $D$ и энтропией {$T$,$F$}. Эта разница называется приростом информации .

На следующем рисунке показано плохое разделение, при котором энтропия остается высокой, а прирост информации – низким:

Рисунок 9. Плохое разделение не снижает энтропию метки.

Напротив, на следующем рисунке показано лучшее разделение, при котором энтропия становится низкой (а прирост информации высок):

Рисунок 10. Хорошее разделение снижает энтропию метки.

Формально:

$$\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}$$

где:

• $IG(D,T,F)$ — это информационный выигрыш от разделения $D$ на $T$ и $F$.
• $H(X)$ — энтропия множества примеров $X$.
• $|X|$ — количество элементов в множестве $X$.
• $t$ — пороговое значение.
• $pos$ — это положительное значение метки, например «синий» в приведенном выше примере. Выбор другой метки в качестве «положительной метки» не меняет значения энтропии или прироста информации.
• $R(X)$ — соотношение положительных значений меток в примерах $X$.
• $D$ — это набор данных (как определено ранее в этом модуле).

В следующем примере мы рассматриваем набор данных двоичной классификации с одним числовым признаком $x$. На следующем рисунке показаны различные пороговые значения $t$ (ось X):

1. Гистограмма признака $x$.
2. Соотношение «синих» примеров в $D$, $T$ и $F$ устанавливается в соответствии с пороговым значением.
3. Энтропия в $D$, $T$ и $F$.
4. Прирост информации; то есть дельта энтропии между $D$ и {$T$,$F$}, взвешенная по количеству примеров.

Рисунок 11. Четыре пороговых графика.

Эти графики показывают следующее:

• График «частоты» показывает, что наблюдения относительно хорошо разбросаны с концентрациями от 18 до 60. Широкий разброс значений означает, что существует много потенциальных разделений, что хорошо для обучения модели.

• Доля «синих» меток в наборе данных составляет ~25%. График «коэффициента синей метки» показывает, что для пороговых значений от 20 до 50:

  • Набор $T$ содержит избыток примеров «синих» меток (до 35% для порога 35).
  • Набор $F$ содержит дополнительный дефицит примеров «синих» меток (всего 8% для порога 35).

  Как «соотношение синих меток», так и графики «энтропии» показывают, что метки могут быть относительно хорошо разделены в этом пороговом диапазоне.

• Это наблюдение подтверждается графиком «прироста информации». Мы видим, что максимальный прирост информации достигается при t~=28 при значении прироста информации ~0,074. Следовательно, условие, возвращаемое разделителем, будет $x \geq 28$.

• Прирост информации всегда положителен или равен нулю. Он сходится к нулю, когда пороговое значение приближается к своему максимальному/минимальному значению. В этих случаях либо $F$, либо $T$ становится пустым, а другой содержит весь набор данных и показывает энтропию, равную энтропии в $D$. Прирост информации также может быть нулевым, когда $H(T)$ = $H(F)$ = $H(D)$. На пороге 60 соотношение «синих» меток как для $T$, так и для $F$ такое же, как и для $D$, и прирост информации равен нулю.

Возможные значения $t$ в множестве действительных чисел ($\mathbb{R}$) бесконечны. Однако при конечном числе примеров существует лишь конечное число делений $D$ на $T$ и $F$. Следовательно, только конечное число значений $t$ имеет смысл проверять.

Классический подход заключается в сортировке значений x _i в порядке возрастания x _s(i) так, чтобы:

$$x_{s(i)} \leq x_{s(i+1)}$$

Затем проверьте $t$ для каждого значения на полпути между последовательными отсортированными значениями $x_i$. Например, предположим, что у вас есть 1000 значений с плавающей запятой для определенного объекта. Предположим, что после сортировки первые два значения равны 8,5 и 8,7. В этом случае первое пороговое значение для проверки будет 8,6.

Формально мы рассматриваем следующие возможные значения t:

$$X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\}$$

Временная сложность этого алгоритма составляет $\mathcal{O} ( n \log n)$ с $n$ количеством примеров в узле (из-за сортировки значений признаков). При применении к дереву решений алгоритм разделения применяется к каждому узлу и каждому объекту. Обратите внимание, что каждый узел получает ~1/2 своих родительских примеров. Следовательно, согласно основной теореме , временная сложность обучения дерева решений с помощью этого сплиттера равна:

$$\mathcal{O} ( m n \log^2 n )$$

где:

• $m$ — количество функций.
• $n$ — количество обучающих примеров.

В этом алгоритме ценность признаков не имеет значения; важен только порядок. По этой причине этот алгоритм работает независимо от масштаба или распределения значений признаков. Вот почему нам не нужно нормализовать или масштабировать числовые характеристики при обучении дерева решений.