В этом модуле вы изучите простейший и наиболее распространенный алгоритм разделения, который создает условия формы $\mathrm{feature}_i \geq t$ в следующих настройках:
- Задача бинарной классификации
- Без пропущенных значений в примерах
- Без предвычисленного индекса на примерах
Предположим, есть набор из $n$ примеров с числовым признаком и двоичной меткой "оранжевый" и "синий". Формально опишем набор данных $D$ как:
куда:
- $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):
- Гистограмма признака $x$.
- Соотношение «синих» примеров в наборах $D$, $T$ и $F$ соответствует пороговому значению.
- Энтропия в $D$, $T$ и $F$.
- прирост информации; то есть дельта энтропии между $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) таким образом, чтобы:
Затем проверьте $t$ для каждого значения на полпути между последовательными отсортированными значениями $x_i$. Например, предположим, что у вас есть 1000 значений с плавающей запятой определенной функции. После сортировки предположим, что первые два значения равны 8,5 и 8,7. В этом случае первое пороговое значение для проверки будет 8,6.
Формально мы рассматриваем следующие возможные значения для t:
Временная сложность этого алгоритма составляет $\mathcal{O} ( n \log n) $ с $n$ числом примеров в узле (из-за сортировки значений признаков). При применении к дереву решений алгоритм разделения применяется к каждому узлу и каждой функции. Обратите внимание, что каждый узел получает примерно 1/2 своих родительских примеров. Следовательно, согласно основной теореме , временная сложность обучения дерева решений с помощью этого сплиттера составляет:
куда:
- $m$ — количество функций.
- $n$ — количество обучающих примеров.
В этом алгоритме значения признаков не имеют значения; важен только порядок. По этой причине этот алгоритм работает независимо от масштаба или распределения значений признаков. Вот почему нам не нужно нормализовать или масштабировать числовые признаки при обучении дерева решений.