Уменьшение Джини и примеси Джини у детей

15

Я работаю над критерием важности функции Джини для случайного леса. Следовательно, мне нужно рассчитать уменьшение Джини примеси в узле. Вот как я это делаю, что приводит к конфликту с определением, предполагающим, что я где-то ошибаюсь ... :)

Для бинарного дерева и с учетом вероятностей левого и правого потомков я могу вычислить примесь Джини узла N :

я(N)знак равно1-пL2-пр2

И снижение Джини:

Δя(N)знак равноя(N)-пLя(NL)-пря(Nр)

Итак, для этого примера с 110 наблюдениями на узле:

- node (110)
   - left (100)
      - left_left (60)
      - left_right (40)
   - right (10)
      - right_left (5)
      - right_right (5)

Я бы рассчитал уменьшение Джини для узла следующим образом:

i(leеT)знак равно1-(60/100)²-(40/100)²знак равно0,48я(ряграммчасT)знак равно1-(5/10)²-(5/10)²знак равно0,50я(Nоdе)знак равно1-(100/110)²-(10/110)²знак равно0,16

Но, следуя определению Бреймана (или этому ответу на CV: как измерить / оценить «переменную важность» при использовании CART , но у меня нет доступа к указанной книге), критерий загрязненности потомка должен быть меньше, чем родительский. узел:

Важность Джини
Каждый раз, когда деление узла выполняется по переменной m, критерий нечистоты Джини для двух дочерних узлов меньше, чем родительский узел. Сложение уменьшений джини для каждой отдельной переменной по всем деревьям в лесу дает важность быстрой переменной, которая часто очень согласуется с мерой важности перестановки.

Потому что в противном случае это приводит к отрицательному снижению Джини ...

Δi(node)=i(node)(100/110)i(left)(10/110)i(right)=0,32

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

Реми Мелиссон
источник

Ответы:

16

Вы просто не использовали переменную целевого класса вообще. Примесь Джини, как и все другие примесные функции, измеряет примеси выходов после разделения. Что вы сделали, это измерили что-то, используя только размер выборки.

Я пытаюсь вывести формулу для вашего случая.

Предположим, для простоты у вас есть двоичный классификатор. Обозначим через тестовый атрибут, через - атрибут класса, который имеет значения .ACc+,c

Начальный индекс Джини перед разделением дается где - это доля точек данных, которые имеют значение для класса переменная.

I(A)=1P(A+)2P(A)2
P(A+)c+

Теперь примесь для левого узла будет где - это доля точек данных из левого подмножества которые имеют значение в переменной класса и т. Д.

I(Al)=1P(Al+)2P(Al)2
I(Ar)=1P(Ar+)2P(Ar)2
P(Al+)Ac+

Теперь окончательная формула для GiniGain будет

граммяNяграммaяN(A)знак равноя(A)-пLееTя(AL)-пряграммчасTя(Aр)
где - это доля экземпляров для левого подмножества, или (сколько экземпляров находятся в левом подмножестве , деленное на общее количество экземпляров из .пLееT#|AL|#|AL|+#|Aр|A

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

Вывод

Использование только количества точек данных недостаточно, примеси означают, насколько хорошо одна функция (функция тестирования) способна воспроизвести распределение другой функции (функция класса). Распределение тестового объекта дает число, которое вы использовали (как налево, как направо), но распределение компонента класса не используется в ваших формулах.

Позже отредактируйте - докажите, почему это уменьшается

Теперь я заметил, что пропустил ту часть, которая доказывает, почему индекс Джини всегда на дочернем узле меньше, чем на родительском узле. У меня нет полного или проверенного доказательства, но я думаю, что это веское доказательство. Для других интересных вещей, связанных с темой, вы можете проверить Техническое примечание: Некоторые свойства критериев расщепления - Лео Брейман . Теперь это будет следовать моим доказательствам.

Предположим , что мы в двоичном случае, и все значения в узле может быть полностью описывается парой со значением экземпляров первого класса, и экземпляров второго класса. Мы можем утверждать, что в родительском узле у нас есть экземпляры.(a,б)aб(a,б)

Чтобы найти лучшее разбиение, мы сортируем экземпляры в соответствии с тестовой функцией и пробуем все двоичные возможные разбиения. Сортировка по заданному признаку на самом деле представляет собой перестановку экземпляров, в которой классы начинаются с экземпляра первого класса или второго класса. Не теряя общности, мы предположим, что он начинается с экземпляра первого класса (если это не так, у нас есть зеркальное доказательство с тем же вычислением).

Первая попытка раскола происходит в левом и правом экземплярах. Как индекс Джини для этих возможных кандидатов для левого и правого дочерних узлов сравнивается с родительским узлом? Очевидно, слева мы имеем . Так что с левой стороны у нас есть меньшее значение индекса Джини. Как насчет правого узла?(1,0)(a-1,б)час(LееT)знак равно1-(1/1)2-(0/1)2знак равно0

час(пaреNT)знак равно1-(aa+б)2-(бa+б)2
час(ряграммчасT)знак равно1-(a-1(a-1)+б)2-(б(a-1)+б)2

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

Теперь последний этап доказательства заключается в том, чтобы при рассмотрении всех возможных точек разделения, определяемых имеющимися у нас данными, мы оставляем ту, которая имеет наименьший агрегированный индекс Джини, что означает, что выбранный нами оптимум меньше или равен тривиальный, который я доказал, что меньше. Что делает вывод, что в конце индекс Джини будет уменьшаться.

В качестве окончательного вывода мы должны отметить, что даже если различные разбиения могут дать значения больше, чем родительский узел, тот, который мы выберем, будет наименьшим среди них и также меньше значения родительского индекса Джини.

Надеюсь, это поможет.

rapaio
источник
Большое спасибо, вы разблокировали мой мозг ... На самом деле, поскольку я имею дело с деревьями регрессии, использование переменной целевого класса оказалось менее очевидным, чем для чисто классификационной задачи. Но теперь это имеет смысл.
Реми Мелиссон
Я обновил ответ, чтобы содержать недостающие части.
Rapaio