Какие критерии информативности используются при построении дерева решений

Что проверяют

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

Как отвечать

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

• энтропия Шеннона: H = -Σ p·log2(p) по всем классам. Для двух классов от 0 (узел чистый) до 1 (половина на половину);
• прирост информации (information gain): энтропия родителя минус взвешенная по размеру энтропия потомков. На нём построены ID3 и C4.5;
• индекс Джини: G = 1-Σ p², вероятность ошибиться, если выбрать метку случайно по распределению узла. Это критерий CART и значение по умолчанию criterion="gini" в DecisionTreeClassifier из scikit-learn;
• gain ratio: прирост информации, делённый на энтропию самого разбиения. Так C4.5 штрафует признаки с большим числом значений;
• для регрессии: снижение дисперсии, то есть squared_error, а также absolute_error, friedman_mse и poisson.

В scikit-learn для классификации есть gini, entropy и log_loss, последние два считают одно и то же. Джини и энтропия на практике почти всегда выбирают одни и те же разбиения, Джини чуть дешевле, потому что обходится без логарифма.

Хорошо добавить про бустинг: в XGBoost и LightGBM разбиение выбирают по приросту функции потерь, посчитанному через градиенты и гессианы, а не по энтропии.

Где спотыкаются

Говорят, что индекс Джини меняется от 0 до 1. Для K классов максимум равен 1-1/K, для двух классов это 0.5.

Путают критерий разбиения с метрикой качества модели. Энтропия в узле и accuracy на тесте это разные вещи, а оптимизация критерия жадная и локальная.

Не упоминают смещение прироста информации в пользу признаков с множеством уникальных значений. Идентификатор клиента даст идеально чистые листья и нулевую обобщающую способность.