Критерий Джини

Материал из MachineLearning.

Статья подготовлена с использованием модели OpenAI GPT‑5.6 Sol с уровнем рассуждений High и проверена участником Д.О. Кистанов 23:22, 18 июля 2026 (MSK)

Промпт приводится полностью в Обсуждение:Критерий Джини

Содержание

1 История
2 Основная идея
3 Математические основы
4 Использование при построении дерева
5 Сравнение с другими критериями
6 Диагностика и оценка качества
7 Практическое применение
- 7.1 Классификационные деревья
- 7.2 Ансамбли деревьев и важность признаков
8 Трудности и ограничения
9 Современные направления исследований
10 См. также
11 Примечания
12 Литература
13 Ссылки

Критерий Джини (англ. Gini criterion) — критерий выбора разбиения в дереве решений, основанный на уменьшении нечистоты Джини (англ. Gini impurity). Для узла, в котором условные вероятности $K$ классов равны $p_1,\ldots,p_K$ , нечистота определяется как

$G(p_1,\ldots,p_K)=1-\sum_{k=1}^{K}p_k^2=\sum_{k=1}^{K}p_k(1-p_k).$

Она равна нулю в однородном узле и возрастает по мере смешения классов. При построении дерева выбирают разбиение, которое сильнее всего уменьшает взвешенную нечистоту дочерних узлов. Критерий получил широкое распространение благодаря алгоритму CART (Classification and Regression Trees), где он является одним из основных правил выращивания классификационных деревьев.^[1]

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

История

Формула $1-\sum_k p_k^2$ восходит к книге итальянского статистика Коррадо Джини Variabilità e mutabilità 1912 года. Джини рассматривал её как индекс изменчивости качественного признака: величина выражала вероятность того, что две независимо выбранные единицы принадлежат разным категориям.^[1] История этой части труда долго оставалась менее известной, чем история коэффициента концентрации Джини; перевод и анализ разделов об изменчивости качественных рядов были опубликованы Лидией Чериани и Паоло Верме в 2024 году.^[1]

В экологии близкая величина стала известна после работы Эдварда Симпсона 1949 года. Индекс Симпсона $\sum_k p_k^2$ оценивает вероятность совпадения категорий, а его дополнение — вероятность различия; поэтому нечистоту Джини также называют индексом разнообразия Джини — Симпсона.^[1]

В 1984 году Лео Брейман, Джером Фридман, Ричард Олшен и Чарльз Стоун систематически использовали индекс Джини как функцию нечистоты в методологии CART.^[1] CART строит бинарные разбиения и выбирает их по уменьшению нечистоты, после чего применяет обрезку дерева по стоимости сложности. Параллельно развивалось семейство ID3, использующее информационный выигрыш на основе энтропии Шеннона; подробное описание ID3 Джона Росса Куинлана вышло в 1986 году.^[1]

После появления случайных лесов уменьшение нечистоты Джини стало использоваться не только для построения отдельных деревьев, но и для оценки важности признаков путём суммирования улучшений по узлам.^[1] Последующие исследования показали, что и выбор разбиений, и основанная на нём важность могут быть смещены в пользу признаков с большим числом возможных точек разреза или категорий.^[1]

Основная идея

В каждом узле классификационного дерева находится подвыборка объектов. Если почти все объекты относятся к одному классу, узел называют чистым; если классы представлены сопоставимыми долями, узел неоднороден. Критерий Джини предпочитает такое правило разбиения, после которого дочерние узлы в среднем становятся однороднее.

Нечистота имеет две простые вероятностные интерпретации.

Если независимо выбрать два класса из распределения $(p_1,\ldots,p_K)$ , то $G$ есть вероятность получить разные классы.
Если истинный класс имеет это распределение и предсказываемый класс независимо разыгрывается из того же распределения, то $G$ есть вероятность ошибочной метки.

Вторая интерпретация не означает, что обученное дерево обязано случайно выбирать метку: обычно в листе предсказывают класс с максимальной оценённой вероятностью, а сам вектор долей классов используют как оценку вероятностей.

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

Математические основы

Нечистота узла

Пусть в узле $t$ находятся объекты $I_t$ с метками $y_i\in\{1,\ldots,K\}$ и неотрицательными весами $w_i$ . Обозначим

$W_t=\sum_{i\in I_t}w_i,\qquad p_{tk}=\frac{1}{W_t}\sum_{i\in I_t}w_i[ y_i=k ].$

Здесь скобка $[A]$ равна единице, если утверждение $A$ истинно, и нулю иначе. Эмпирическая нечистота узла равна

$G(t)=1-\sum_{k=1}^{K}p_{tk}^2.$

Для невзвешенной выборки $p_{tk}=n_{tk}/n_t$ . При двух классах, если $p$ — доля первого класса,

$G(p)=1-p^2-(1-p)^2=2p(1-p).$

В бинарном случае нечистота вдвое больше дисперсии индикатора класса. В многоклассовом случае она равна следу ковариационной матрицы вектора индикаторов класса:

$G(p)={\rm tr}({\rm diag}(p)-pp^{\prime}).$

Свойства

Для любого распределения по $K$ классам выполняются следующие свойства.

$0\leq G(p)\leq 1-1/K$ .
Минимум $G=0$ достигается тогда и только тогда, когда вся вероятность сосредоточена в одном классе.
Максимум $1-1/K$ достигается при равных вероятностях $p_k=1/K$ .
Функция симметрична относительно перестановки названий классов и строго вогнута на симплексе вероятностей.
Объединение различных распределений классов не может иметь меньшую нечистоту, чем средняя нечистота составляющих распределений.

Последнее свойство следует из вогнутости и обеспечивает неотрицательность популяционного выигрыша от разбиения. Иногда индекс нормируют множителем $K/(K-1)$ , чтобы максимум был равен единице. При фиксированном числе классов такая нормировка умножает все выигрыши на одну константу и не меняет выбор разбиения.

Нечистота разбиения и выигрыш

Пусть кандидатное правило делит узел $t$ на непересекающиеся дочерние узлы $t_1,\ldots,t_m$ . Их взвешенная нечистота равна

$G_{\rm split}(t)=\sum_{j=1}^{m}\frac{W_{t_j}}{W_t}G(t_j).$

Выигрыш Джини (англ. Gini gain), или уменьшение нечистоты, определяется как

$\Delta_G(t)=G(t)-G_{\rm split}(t).$

Лучшим считается разбиение с максимальным $\Delta_G$ , что равносильно минимизации взвешенной нечистоты потомков. Вес дочернего узла необходим: без него разбиение, отделяющее несколько чистых объектов и оставляющее почти неизменным большой узел, могло бы получить неоправданное преимущество.

Обозначим вектор долей классов в узле $t_j$ через $p_j$ , в родительском узле — через $p$ , а $q_j=W_{t_j}/W_t$ . Тогда выигрыш допускает представление

$\Delta_G(t)=\sum_{j=1}^{m}q_j\|p_j-p\|^2.$

Для бинарного разбиения это выражение упрощается:

$\Delta_G(t)=q_Lq_R\|p_L-p_R\|^2.$

Таким образом, критерий одновременно поощряет различие распределений классов в потомках и достаточно сбалансированный размер потомков. Очень неравное разбиение получает малый множитель $q_Lq_R$ , если различие распределений не компенсирует дисбаланс размеров.

Связь с квадратичной функцией потерь

Пусть класс кодируется вектором $e_Y$ , у которого одна координата равна единице, а остальные нулю. Если в узле прогнозируется вектор вероятностей $p$ , условное математическое ожидание многоклассовой квадратичной оценки Брайера равно

${\rm E}\|e_Y-p\|^2=1-\sum_{k=1}^{K}p_k^2=G(p).$

Следовательно, минимизация суммарной нечистоты листьев эквивалентна минимизации эмпирической квадратичной ошибки кусочно-постоянных вероятностных прогнозов, с точностью до соглашения о нормировке оценки Брайера. Квадратичная оценка относится к строго правильным правилам оценки вероятностных прогнозов: в среднем она минимизируется истинным распределением классов.^[1] Однако жадный выбор структуры дерева и использование тех же данных для выбора разбиения не гарантируют калиброванности вероятностей на новых объектах.

Оценивание по конечной выборке

Обычная подстановочная оценка

$\widehat G=1-\sum_{k=1}^{K}\left(\frac{n_k}{n}\right)^2$

смещена вниз как оценка популяционной нечистоты. При независимой выборке из мультиномиального распределения

${\rm E}\widehat G=\frac{n-1}{n}\left(1-\sum_{k=1}^{K}p_k^2\right).$

При $n>1$ несмещённая оценка имеет вид

$\widetilde G=\frac{n}{n-1}\widehat G=1-\sum_{k=1}^{K}\frac{n_k(n_k-1)}{n(n-1)}.$

Стандартные реализации CART обычно используют подстановочную оценку: она непосредственно согласована с эмпирической квадратичной потерей. В малых узлах её смещение и дисперсия, а также максимизация по множеству кандидатов влияют на выбор признака; поэтому ограничения минимального размера узла имеют статистический, а не только вычислительный смысл.^[1]

Использование при построении дерева

Поиск разбиения

В узле выполняется жадная процедура.

Для каждого допустимого признака формируется множество кандидатных правил.
Для каждого кандидата подсчитываются классы в дочерних узлах и вычисляется $G_{\rm split}$ или $\Delta_G$ .
Выбирается кандидат с наибольшим выигрышем с учётом ограничений на размер потомков, глубину и минимальное улучшение.
Процедура рекурсивно повторяется для новых узлов до выполнения правила остановки.

Для числового признака с $M$ различными упорядоченными значениями достаточно рассмотреть пороги между соседними значениями; после сортировки статистики классов можно обновлять накопительными суммами. Порог между объектами с одинаковой меткой иногда можно пропустить, но точный набор допустимых кандидатов зависит от реализации и ограничений на веса.

Для номинального признака с $M$ категориями полное бинарное перечисление содержит $2^{M-1}-1$ различных разбиений. В двухклассовой задаче для вогнутых критериев, включая Джини, категории можно упорядочить по доле одного класса и проверить только $M-1$ последовательных разрезов. Для трёх и более классов задача сложнее, и применяются исчерпывающий поиск, приближённые схемы или предварительное кодирование категорий.^[1]

Пример

Пусть в родительском узле находятся 20 объектов двух классов: 10 положительных и 10 отрицательных. Его нечистота равна

$G(t)=1-(10/20)^2-(10/20)^2=0{,}5.$

Кандидатное правило создаёт два узла одинакового размера. В левом находятся 8 положительных и 2 отрицательных объекта, в правом — 2 положительных и 8 отрицательных. Нечистота каждого потомка равна

$1-(8/10)^2-(2/10)^2=0{,}32.$

Взвешенная нечистота разбиения равна $0{,}32$ , а выигрыш Джини —

$\Delta_G=0{,}5-0{,}32=0{,}18.$

Это число следует сравнивать с выигрышами других признаков и порогов в том же узле. Само по себе значение $0{,}18$ не имеет универсальной шкалы качества: максимум зависит от исходного распределения классов и числа классов.

Остановка и обрезка

Повторное максимизирование эмпирического выигрыша способно довести обучающее дерево до почти чистых листьев, в том числе за счёт случайных закономерностей. Обычно рост ограничивают максимальной глубиной, минимальным числом или весом объектов в узле, минимальным выигрышем либо максимальным числом листьев. В CART также строят последовательность вложенных поддеревьев посредством обрезки по стоимости сложности и выбирают размер дерева по независимой проверочной выборке или кросс-валидации.^[1] Критерий разбиения и правило выбора окончательного дерева решают разные задачи и не должны смешиваться.

Сравнение с другими критериями

Энтропия и информационный выигрыш

Энтропийная нечистота определяется как

$H(p)=-\sum_{k=1}^{K}p_k\log p_k,\qquad 0\log 0=0.$

Её уменьшение называется информационным выигрышем. Энтропия и нечистота Джини симметричны, строго вогнуты, равны нулю на чистых распределениях и максимальны на равномерном распределении. Поэтому они часто выбирают близкие разбиения, но не являются монотонными преобразованиями друг друга при нескольких дочерних узлах и не обязаны давать одинаковое дерево. Энтропия сильнее реагирует на появление класса с очень малой вероятностью, тогда как критерий Джини вычисляется без логарифмов. Теоретические и эмпирические сравнения не дают универсального превосходства одного из критериев: результат зависит от распределения данных, множества кандидатов и последующей обрезки.^[1]

Нечистота Джини является частным случаем энтропии Цаллиса порядка $q=2$ :

$H_q(p)=\frac{1-\sum_{k=1}^{K}p_k^q}{q-1},\qquad H_2(p)=G(p).$

В пределе $q\longrightarrow 1$ при подходящем выборе основания логарифма получается энтропия Шеннона. Это связывает два критерия в общем семействе вогнутых функций нечистоты.

Ошибка классификации

Если в узле всегда выбирать наиболее вероятный класс, условная ошибка равна

$E(p)=1-\max_k p_k.$

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

Регрессия и другие типы отклика

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

Диагностика и оценка качества

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

Качество классификации оценивают по подходящим внешним метрикам: ошибке, сбалансированной точности, полноте классов, логарифмической или квадратичной потере. При дисбалансе классов одной общей точности недостаточно.
Вероятности в листьях проверяют на калиброванность и качество по правильным вероятностным потерям. Чистый маленький лист может давать чрезмерно уверенную оценку.
Сложность контролируют по глубине, числу листьев, минимальному размеру листа и ошибке на проверочных данных. Параметры выбирают внутри процедуры кросс-валидации; окончательную оценку получают на внешнем тесте или во внешнем цикле вложенной кросс-валидации.
Устойчивость проверяют повторным ресэмплингом: небольшие изменения выборки могут менять ранние разбиения и всю последующую структуру дерева.
Если уменьшения нечистоты суммируются как важность признака, результат сопоставляют с перестановочной важностью, проверками на искусственных шумовых признаках и предметными знаниями. Важность не является причинным эффектом.

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

Практическое применение

Классификационные деревья

Критерий применяется в задачах табличной классификации, где требуется автоматически находить пороги и взаимодействия признаков: в диагностике, кредитном скоринге, контроле качества, распознавании объектов, биоинформатике и анализе поведения. Его достоинства — простая интерпретация, работа с нелинейными границами и отсутствие необходимости масштабировать числовые признаки. Эти свойства принадлежат в основном деревьям как классу моделей, а не исключительно критерию Джини.

Весовая форма позволяет учитывать неодинаковую значимость наблюдений, выборочный дизайн и веса классов. Однако назначение большого веса редкому классу меняет целевое распределение, относительно которого оптимизируется разбиение. Если цена ошибок задаётся полной несимметричной матрицей, одних весов может быть недостаточно: стоимость следует учитывать также в прогнозирующем правиле, обрезке и внешней метрике.

Ансамбли деревьев и важность признаков

В случайном лесе каждый узел обычно выбирает лучшее разбиение среди случайного подмножества признаков. Для признака $X_j$ среднее уменьшение нечистоты (англ. mean decrease impurity, MDI) получают суммированием взвешенных выигрышей всех узлов, где использован этот признак, и усреднением по деревьям:

${\rm MDI}(X_j)=\frac{1}{B}\sum_{b=1}^{B}\sum_{t\in T_b:v(t)=j}\frac{W_t}{W_{\rm root}}\Delta_G(t).$

Эта величина описывает использование признака конкретным алгоритмом в присутствии остальных признаков. При коррелированных предикторах важность может распределяться между заменяющими друг друга переменными; при разных мощностях шкал возникает смещение выбора. Теоретическая интерпретация MDI получена для идеализированных ансамблей полностью рандомизированных деревьев и бесконечных выборок, но эти результаты не переносятся без оговорок на конечные стандартные случайные леса.^[1]

Трудности и ограничения

Жадность и переобучение

Критерий оценивает ближайший шаг, а не полное дерево. Локально лучший порог может закрыть путь к более компактной или точной последующей структуре. Задача построения оптимального бинарного дерева является вычислительно трудной; классический результат устанавливает NP-полноту одной из естественных постановок оптимизации дерева.^[1] Это мотивирует жадный поиск, но не делает его глобально оптимальным. Глубокие деревья особенно склонны подгонять шум, поскольку на каждом шаге выбирается максимум из множества случайно флуктуирующих выигрышей.

Смещение выбора признака

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

Это смещение существенно, когда дерево интерпретируют как процедуру отбора переменных или когда на выигрышах строят MDI. Возможные средства контроля — предварительно заданное и сопоставимое число кандидатов, честное разделение данных для выбора переменной и порога, перестановочные тесты, условные деревья вывода и оценка на независимых данных. В условном рекурсивном разбиении проверка связи отклика с каждым признаком отделена от поиска лучшего порога, что уменьшает систематическое предпочтение признаков с большим числом разрезов.^[1]

Дисбаланс, порядок и цена ошибок

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

Малые узлы, пропуски и новые категории

Оценки долей в малых узлах имеют большой разброс, а нулевая доля класса не доказывает нулевую условную вероятность. Сглаживание вероятностей в листьях может улучшать вероятностный прогноз, но обычно не входит в определение критерия разбиения. Сам критерий также не задаёт обработку пропусков: возможны импутация, отдельная категория, вероятностное направление или суррогатные разбиения. Эти варианты приводят к разным деревьям. Категории, не встречавшиеся при обучении, требуют заранее определённого правила маршрутизации.

Ограниченность номинального представления

Нечистота использует только частоты классов. Она не учитывает геометрию признакового пространства внутри узла, расстояния между объектами и близость классов. Два узла с одинаковым вектором долей получают одинаковую нечистоту, даже если один легко разделить следующим порогом, а другой нет. В этом проявляется одноступенчатый характер критерия.

Современные направления исследований

Исследования критерия Джини развиваются вместе с общей теорией и алгоритмами деревьев.

Несмещённый статистический выбор. Разрабатываются процедуры, отделяющие проверку наличия связи от оптимизации точки разреза, и поправки на максимальный выигрыш. Для бинарной классификации выведено точное нулевое распределение максимально выбранного выигрыша Джини в ряде постановок, что позволяет использовать скорректированное $p$ -значение как критерий выбора.^[1]
Регуляризация сложности и стоимости тестов. К выигрышу добавляют компоненты, учитывающие баланс разбиения, стоимость признака и ожидаемую длину пути. Для регуляризованного критерия, включающего уменьшение Джини, получены логарифмические аппроксимационные гарантии по ожидаемой стоимости классификации при заданных предположениях.^[1]
Теория жадной индукции. Для булевых функций при специальных распределительных предположениях установлены верхние и нижние границы размера деревьев, создаваемых нисходящими эвристиками. Эти результаты формализуют одновременно полезность и ограничения локальных критериев.^[1] Критерии более высокого порядка, учитывающие совместные корреляции небольших групп признаков, дают универсальные гарантии в ограниченной булевой постановке, но требуют значительно больших вычислений, чем обычный Джини.^[1]
Потоковые данные. Для стационарных потоков предложены статистически обоснованные критерии на основе ошибки классификации и нечистоты Джини, различающие гарантию выбора наилучшего ожидаемого разбиения и гарантию совпадения с выбором по бесконечному потоку.^[1]
Адаптация к структуре отклика. Для порядковой классификации, иерархических меток, цензурированных данных и сильного дисбаланса изучаются модификации, которые заменяют номинальную симметрию критерия расстояниями, весами или специализированными потерями.

Эти направления не отменяют классический критерий: он остаётся дешёвой и хорошо изученной базовой функцией. Современные методы уточняют, в каких задачах локальное уменьшение нечистоты соответствует конечной цели, а где требуется поправка на множественный поиск, структуру классов или сложность дерева.

См. также

Примечания

Литература

Breiman, L.; Friedman, J. H.; Olshen, R. A.; Stone, C. J. Classification and Regression Trees. — Belmont, California: Wadsworth International Group, 1984. — ISBN 0-534-98053-8
Hastie, T.; Tibshirani, R.; Friedman, J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2-е изд.. — New York: Springer, 2009. — ISBN 978-0-387-84857-0
Ceriani, L.; Verme, P. Gini on Mutability // METRON. — 2024. — Т. 82. — № 3. — С. 269—292.
Raileanu, L. E.; Stoffel, K. Theoretical Comparison between the Gini Index and Information Gain Criteria // Annals of Mathematics and Artificial Intelligence. — 2004. — Т. 41. — № 1. — С. 77—93.
Strobl, C.; Boulesteix, A.-L.; Augustin, T. Unbiased Split Selection for Classification Trees Based on the Gini Index // Computational Statistics & Data Analysis. — 2007. — Т. 52. — № 1. — С. 483—501.
Hothorn, T.; Hornik, K.; Zeileis, A. Unbiased Recursive Partitioning: A Conditional Inference Framework // Journal of Computational and Graphical Statistics. — 2006. — Т. 15. — № 3. — С. 651—674.
Gneiting, T.; Raftery, A. E. Strictly Proper Scoring Rules, Prediction, and Estimation // Journal of the American Statistical Association. — 2007. — Т. 102. — № 477. — С. 359—378.
Louppe, G.; Wehenkel, L.; Sutera, A.; Geurts, P. Understanding Variable Importances in Forests of Randomized Trees // Advances in Neural Information Processing Systems 26. — 2013. — Т. 26. — С. 431—439.
Zhang, G.; Gionis, A. Regularized Impurity Reduction: Accurate Decision Trees with Complexity Guarantees // Data Mining and Knowledge Discovery. — 2023. — Т. 37. — № 1. — С. 434—475.

Ссылки

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9A%D1%80%D0%B8%D1%82%D0%B5%D1%80%D0%B8%D0%B9_%D0%94%D0%B6%D0%B8%D0%BD%D0%B8»

Категории: Машинное обучение | Решающие деревья | Классификация | Критерии качества