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

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

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

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

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

куда:

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

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

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

• Энтропия Шеннона максимальна, когда метки в примерах сбалансированы (50% синего и 50% оранжевого).
• Энтропия Шеннона минимальна (нулевое значение), когда метки в примерах чистые (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$ — количество обучающих примеров.

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