Импурия Джини в дереве решений (причины для использования)

В дереве решений показатель Джини[1] является метрикой для оценки того, насколько узел содержит различные классы. Он измеряет вероятность ошибочного определения класса, выбирая его случайным образом, используя распределение из этого узла:

$$
I_g(p) = 1 – \sum_{i=1}^J p_i^2
$$

Если у нас 80% класса C1 и 20% класса C2, то случайная маркировка даст 1 – 0.8 x 0.8 – 0.2 x 0.2 = 0.32 значение нечистоты Джини.

Тем не менее, случайное присвоение класса с использованием распределения кажется плохой стратегией по сравнению с простым присвоением самого представленного класса в этом узле (в приведенном примере вы просто будете всегда маркировать C1 и получите только 20% ошибок вместо 32%).

В этом случае я бы был склонен использовать это как метрику, поскольку это также вероятность ошибочной маркировки:

$$
I_m(p) = 1 – \max_i [ p_i]
$$

Существует ли более глубокая причина использовать значение Джини и/или хорошая причина не использовать этот подход вместо этого? (Другими словами, значение Джини, похоже, переоценивает ошибки маркировки, которые произойдут, не так ли?)

[1] https://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity

ИЗМЕНЕНИЕ: Мотивация

Предположим, у вас есть два класса $C_1$ и $C_2$ с вероятностями $p_1$ и $p_2$ ($1 \ge p_1 \ge 0.5 \ge p_2 \ge 0$, $p_1 + p_2 = 1$).

Вы хотите сравнить стратегию “всегда маркировать $C_1$” со стратегией “маркировать $C_1$ с вероятностью $p_1$, а $C_2$ с вероятностью $p_2$“, тогда вероятности успеха соответственно $p_1$ и $p_1^2 + p_2^2$.

Мы можем переписать вторую так:

$$
p_1^2 + p_2^2 = p_1^2 + 2p_1p_2 – 2p_1p_2 + p_2^2 = (p_1 + p_2)^2 – 2p_1p_2 = 1 – 2p_1p_2
$$

Таким образом, если мы вычтем это из $p_1$:

$$
p_1 – 1 + 2p_1p_2 = 2p_1p_2 – p_2 = p_2 ( 2p_1 – 1)
$$

Поскольку $p_1 \ge 0.5$, то $p_2 ( 2p_1 – 1) \ge 0$, и, следовательно:

$$
p_1 \ge p_1^2 + p_2^2
$$

Таким образом, выбор класса с наивысшим приоритетом всегда является лучшим выбором.

ИЗМЕНЕНИЕ: Выбор атрибута

Предположим, теперь у нас есть $n_1$ объектов в $C_1$ и $n_2$ объектов в $C_2$. Нам нужно выбрать, какой атрибут $a \in A$ лучше всего подходит для разделения узла. Если мы используем верхний индекс $n^v$ для обозначения количества объектов, имеющих значение $v$ для данного атрибута (и $n^v_1$ объектов $C_1$, имеющих значение $v$), я предлагаю использовать оценку:

$$
\sum_v \frac{n^v}{n_1 + n_2} \frac{max(n^v_1, n^v_2)}{n^v_1 + n^v_2}
$$

В качестве критерия вместо Джини.

Обратите внимание, что поскольку $n^v = n^v_1 + n^v_2$ и $n_1 + n_2$ не зависит от выбранного атрибута, это можно переписать как:

$$
\sum_v max(n^v_1, n^v_2)
$$

И просто интерпретировать как количество объектов в наборе данных, которые будут правильно классифицированы.

Ошибка неправильно классифицирования не поможет в разделении дерева.

Причина–Мы рассматриваем взвешенный спад ошибки от родительского узла к дочернему узлу, и ошибка неправильно классифицирования всегда будет равна 0 (кроме чистых разделений).

Рассмотрим пример

Данные = 1, 1, 0, 1, 0, 1, 0, 1, 0, 1

Ошибка классификации родителя= 4/10 = 0.4

Нечистота Джини родителя = 1-(0.4×0.4+0.6×0.6) = 0.48

Случай – I

Разделение – 1, 1, 0, 1 Против 1, 0, 1, 0, 1, 0

Ошибка классификации= 0.4×0.25 + 0.6×0.5 = 0.4, разделение невозможно

Нечистота Джини = 0.45

Случай – II

Разделение – 1, 1, 1, 0, 0 Против 0, 1, 0, 1, 0

Ошибка классификации = 0.5×0.4 + 0.5×0.4 = 0.4, разделение невозможно

Нечистота Джини = 0.48

Случай – III

Разделение – 1, 1, 0, 0, 1, 1 Против 1, 0, 1, 0

Ошибка классификации = 0.6x(2/6) + 0.4×0.5 = 0.4, разделение невозможно

Нечистота Джини = 0.477

Чистые разделения

Разделение – 1, 1, 1, 1, 1, 1 Против 0, 0, 0, 0

Ошибка классификации = 0, разделение возможно, но дальнейших разделений нет

Нечистота Джини = 0

Ссылка–

Блог Себастьяна Рашки

Поскольку у меня было лишь интуитивное представление об этом, я решил реализовать это в коде. Для этого я следовал методу, описанному по адресу https://victorzhou.com/blog/gini-impurity/. В общем, вычисление GI дает вам метрику, для которой вам не нужно знать основное распределение, и я думаю, что это причина, по которой ваш пример работает.

В целом, мой вывод: “Да, есть ситуации, в которых подсчет большинства более полезен, но обычно GI обеспечивает лучшее разделение”.

Вот что я сделал, следуя упомянутой выше ссылке:

1. Я сгенерировал 4 x 2000 точек данных с случайными координатами x/y.
2. В зависимости от того, больше или меньше ли результат np.sqrt((data.p_x*data.p_y)) порогового значения, я назначил цвета синий или красный.
3. Затем для каждого набора из 2000 точек я нарисовал 100 вертикальных линий, представляющих потенциальные разделения, которые мог бы оценить узел дерева решений.
4. Затем для каждого из этих разделений я следовал процедуре, описанной по адресу https://victorzhou.com/blog/gini-impurity/#example-1-the-whole-dataset. Таким образом, я в основном оценивал нечистоту Джини для обеих сторон разделения, затем вычислял взвешенную сумму этих значений для каждого разделения и вычислял “Прибавку Джини”, вычитая это из наивной вероятности быть правым.
5. На нижнем центральном графике я изобразил прибавку для каждого из этих разделений по сравнению с соотношением правильно классифицированных точек, которое это разделение могло бы классифицировать. Также для каждого набора я добавил горизонтальную линию, указывающую количество правильно классифицированных точек, если бы я просто выбрал голосование большинства.

Я упростил реальный мир, используя только вертикальные разделения, показанные светло-серым. Также я подхожу к двумерной проблеме в основном в одномерном формате. Горизонтальные линии соответствуют точности принципа голосования большинства, который вы предложили.

Я загрузил код здесь:
https://github.com/dazim/stackoverflow_answers/blob/main/gini-impurity-in-decision-tree-reasons-to-use-it.ipynb

Изменение 2021-02-19:

Основываясь на обсуждении в комментариях, я заменил GI подходом, который предложил Gregwar.

На основе двух подходов я оценил производительность узла, принимающего решение на основе лучшего разреза. Изображено score_gregwar - score_GI

К сожалению, мне нужно заняться другими делами. Но, возможно, кто-то другой захочет продолжить с этим. Судя по тому, что я вижу в этой симуляции, различия не кажутся столь значительными. Однако использование более “реальных” данных и не только вертикальных разрезов может изменить это. Извините!

Я полагаю, этот вопрос освещается в “Элементах статистического обучения” (https://hastie.su.domains/ElemStatLearn/printings/ESLII_print12_toc.pdf.download.html) на странице 360 (возможно, немного отличается в зависимости от вашего издания):

“Мы классифицируем наблюдения в узле $m$ в класс $k(m) = \arg\max_k
> \hat{p}_{mk}$, класс большинства в узле $m$. Различные меры
$Q_m(T)$ нечистоты узла включают следующие:

• Ошибка неправильно классифицирования:
  $1 – \hat{p}_{mk(m)} = \frac{1}{N_m} \sum_{i \in R_m} \mathbb{I}(y_i
  > \neq k(m)).$

• Индекс Джини: $ \sum_{k \neq k’} \hat{p}_{mk} \hat{p}_{mk’} = \sum_{k=1}^K \hat{p}_{mk} (1 – \hat{p}_{mk}). $

• Кросс-энтропия или девиант: $ -\sum_{k=1}^K \hat{p}_{mk} \log \hat{p}_{mk}. $

Для двух классов, если $p$ — это доля во втором классе, эти
три меры равны $1 – \max(p, 1 – p)$, $2p(1-p)$ и $-p\log p –
> (1-p)\log(1-p)$ соответственно. Они показаны на рисунке 9.3. Все три
являются аналогичными, но кросс-энтропия и индекс Джини являются дифференцируемыми,
и, следовательно, лучше поддаются численной оптимизации.

Сравнивая уравнения (9.13) и (9.15), мы видим, что нам нужно взвешивать
меры нечистоты узла по количеству $N_{mL}$ и $N_{mR}$ наблюдений в двух дочерних узлах, созданных разделением узла $m$.

Кроме того, кросс-энтропия и индекс Джини более чувствительны к
изменениям вероятностей узла, чем скорость неправильно классифицирования. Например, в задаче с двумя классами с 400 наблюдениями в каждом классе
(обозначенные как $(400, 400)$), предположим, что одно разделение создает узлы $(300,
> 100)$ и $(100, 300)$, в то время как другое разделение создает узлы $(200, 400)$
и $(200, 0)$. Оба разделения дают скорость ошибочного классифицирования 0.25,
но второе разделение создает чистый узел и, вероятно, предпочтительнее.
Как индекс Джини, так и кросс-энтропия меньше для второго разделения.
По этой причине либо индекс Джини, либо кросс-энтропия должны использоваться
при построении дерева. Для руководства по обрезке с учетом стоимости и сложности можно использовать любую из
тех трех мер, но обычно это скорость неправильно классифицирования.

Индекс Джини можно интерпретировать двумя интересными способами. Вместо того, чтобы
классифицировать наблюдения в класс большинства в узле, мы могли бы
классифицировать их в класс $k$ с вероятностью $\hat{p}_{mk}$. Тогда
уровень ошибки этой модели в узле составляет $\sum_{k \neq k’}
> \hat{p}_{mk} \hat{p}_{mk’}$—индекс Джини. Аналогично, если мы кодируем каждое
наблюдение как 1 для класса $k$ и 0 в противном случае, дисперсия по
узлу этого ответа 0-1 равна $\hat{p}_{mk}(1 – \hat{p}_{mk})$. Суммируя
по классам $k$, мы снова получаем индекс Джини.”