Дерево по Джини
Вместо энтропии решающие деревья часто меряют неопределённость неоднородностью Джини — так по умолчанию делает, например, scikit-learn. Для группы из m примеров, среди которых c единиц, будем считать её «в штуках»:
$$G(m, c) = m - \frac{c^2 + (m - c)^2}{m}.$$Это m, умноженное на вероятность того, что два случайных примера группы (с возвращением) окажутся разных классов: 0 у чистой группы, m/2 у половинчатой. Постройте дерево по этим правилам и ответьте на вопросы.
- В узле с примерами S рассматриваются вопросы «xf ≤ v?», где f — номер признака, v — значение этого признака у какого-нибудь примера из S, и хотя бы у одного примера из S признак больше v.
- Лучший вопрос — с наименьшей суммой G(группа «да») + G(группа «нет»). При равенстве выбирается меньший f, при равных f — меньшее v. Сравнивать нужно точно.
- Узел делится лучшим вопросом, если его глубина меньше D (у корня глубина 0), в нём есть и нули, и единицы, а сумма G после деления строго меньше G(S). Иначе это лист, и его ответ — 1, если единиц в нём больше половины, иначе 0.
Один из тестов — землетрясения 2015–2021 годов из каталога USGS (признаки: магнитуда в сотых, глубина в десятых долях километра, расстояние до ближайшего города в километрах; ответ — почувствовал ли кто-нибудь), а вопросы — толчки 2022–2025 годов.
Вход
В первой строке n, F, D (1 ≤ n ≤ 2000, 1 ≤ F ≤ 3, 0 ≤ D ≤ 12). В каждой из следующих n строк — F целых признаков (от 0 до 10⁶) и ответ 0 или 1. Затем q (1 ≤ q ≤ 2000) и q строк по F целых признаков.
Выход
Для каждого вопроса — ответ дерева, 0 или 1, в отдельной строке.
Примеры
Пример 1
8 1 2 1 0 2 0 2 0 2 1 3 1 3 1 4 1 4 0 5 0 2 3 4 5
0 0 1 0 0
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Это решающее дерево из статьи, только с другой мерой. Начните с одного узла: как за один проход по отсортированным примерам перебрать все вопросы «xf ≤ v?» одного признака?
2Подсказка 2
«Сравнивать нужно точно». В G есть деление. Раз размер узла m не зависит от вопроса, что достаточно сравнивать, и как сравнить две дроби, не деля?
3Идея
Сумма G двух групп равна m − (s₁/m₁ + s₂/m₂), где s = c² + (m − c)². Значит, лучший вопрос — с наибольшей дробью (s₁m₂ + s₂m₁)/(m₁m₂), и две такие дроби сравниваются перекрёстным умножением в целых числах. Порог v — значение признака у последнего примера группы «да» в отсортированном порядке, и вопросы между одинаковыми значениями не рассматриваются: они не делят такие примеры.
4Разбор
Рекурсивно строим узлы. В узле для каждого признака сортируем его примеры устойчиво и идём слева направо, считая единицы слева. В каждой точке, где значение меняется, получаем вопрос: числитель s₁m₂ + s₂m₁ и знаменатель m₁m₂. Новый вопрос заменяет лучший, только если он строго лучше — так при равенстве остаются меньший признак и меньший порог. Делим узел, если глубина меньше D, узел не чистый и (s₁/m₁ + s₂/m₂) > s/m, то есть неоднородность действительно падает. Потом спускаем каждый вопрос по дереву.
Порядок величин: s до 4·10⁶, числитель до 1,6·10¹⁰, знаменатель до 10⁶, их произведения при сравнении — до 1,6·10¹⁶: в 64-битные целые помещаются, в float64 точно уже нет.
4+Решение
5Сложность
На каждом уровне дерева каждый пример сортируется по каждому признаку: O(D·F·n log n) на построение и O(D) на вопрос.
6Типичные ошибки
- Вопрос между равными значениями. Если оценивать деление после каждого примера, а порогом брать значение левого, оценка принадлежит одному разбиению, а вопрос «≤ v» делает другое — все равные значения уходят налево. Признаки землетрясений повторяются постоянно (магнитуды кратны сотым), и третий тест это ловит.
- Сравнение в числах с плавающей точкой. Равные дроби, посчитанные разными путями, могут разойтись в последнем бите, и правило ничьей сработает не там.
- Деление без выигрыша. Если вопрос не уменьшает неоднородность, узел должен остаться листом.
- Лист «пополам». При равном числе нулей и единиц ответ — 0: единиц должно быть больше половины.