ML Данные и машинное обучение Алгоритм
Решающее дерево
Также: Decision tree · дерево решений · CART · ID3
Почувствует ли кто-нибудь землетрясение? Решающее дерево отвечает цепочкой вопросов вроде «до города ближе 107 км?» и «магнитуда больше 5,3?», а каждый вопрос выбирает жадно — тот, после которого неопределённость падает сильнее всего. Энтропия, выбор разбиения и переобучение на 19 тысячах настоящих толчков.
С 2015 по 2025 год на Земле случилось 19 073 землетрясения магнитудой 5 и больше. Больше чем о каждом третьем кто-нибудь сообщил в службу сейсмологов USGS «Did You Feel It?» — «Вы это почувствовали?». Можно ли заранее, по магнитуде и по тому, далеко ли ближайший город, сказать, почувствуют ли толчок? Решающее дерево строит ответ из простых вопросов: каждый делит толчки на две группы, а следующий вопрос задаётся уже внутри группы. Ниже дерево учится на 2015–2021 годах и проверяется на 2022–2025 годах, которых не видело.
Первый вопрос дерева — не о магнитуде, а о расстоянии: «ближайший город не дальше 106,5 км?». Почувствовать толчок может только тот, кто рядом. Дерево глубины 3 — восемь прямоугольников — угадывает 79,0 % толчков новых лет; если всегда отвечать «не почувствуют», выйдет 62,9 %. Теперь двигайте глубину к двадцати. На учебных годах доля верных ответов растёт до 86,7 %, а на новых падает до 74,6 %: дерево режет плоскость на тысячи кусочков и запоминает случайности.
Идея
Задайте один вопрос «признак ≤ порог?» — тот, который лучше всего разделяет ответы. В каждой из двух получившихся групп задайте следующий лучший вопрос и так далее, пока группы не станут однородными или вопросы не кончатся. Ответ для нового примера — то, что было большинством в группе, куда его привели вопросы.
Деревья любят за то, что их можно прочитать. Вот верхушка дерева из сцены — три уровня, восемь листьев; в скобках — сколько учебных толчков почувствовали из скольких.
km to a town <= 106.5? (4291/11933 felt, gain 0.172 bits) yes km to a town <= 44.5? (2772/4034 felt, gain 0.048 bits) yes yes magnitude <= 5.320? (1440/1753 felt, gain 0.043 bits) yes yes yes -> felt (870/1147 felt) yes yes no -> felt (570/606 felt) yes no magnitude <= 5.110? (1332/2281 felt, gain 0.056 bits) yes no yes -> not felt (441/1021 felt) yes no no -> felt (891/1260 felt) no magnitude <= 5.950? (1519/7899 felt, gain 0.061 bits) no yes km to a town <= 533.5? (1123/7285 felt, gain 0.043 bits) no yes yes -> not felt (924/4016 felt) no yes no -> not felt (199/3269 felt) no no km to a town <= 224.5? (396/614 felt, gain 0.102 bits) no no yes -> felt (206/239 felt) no no no -> felt (190/375 felt)
Если ближайший город не дальше 44,5 км, толчок заметят в трёх случаях из четырёх даже при магнитуде до 5,32, а при большей — в 570 случаях из 606. Если город дальше 106,5 км, а магнитуда не больше 5,95 — скорее всего, нет; а дальше 533,5 км такой толчок почувствовали лишь в 199 случаях из 3269. Сильный толчок, магнитудой больше 5,95, замечают и издалека, если до города не больше 224,5 км.
Как выбрать вопрос
Что значит «лучше всего разделяет»? Неопределённость группы удобно мерить энтропией — средним числом бит, нужным, чтобы сообщить ответ. Если в группе доля почувствованных толчков p, то
$$H(p) = -p\log_2 p - (1-p)\log_2(1-p).$$У однородной группы H = 0: ответ известен заранее. У группы, где почувствовали ровно половину, H = 1 бит: каждый ответ — честная монета. У всех учебных толчков p ≈ 0,36, и H = 0,942 бита. После вопроса у нас две группы со своими энтропиями; их среднее, взвешенное по размерам групп, и есть оставшаяся неопределённость. Разница «до» и «после» — прирост информации. Лучший вопрос — с наибольшим приростом.
Кандидатов немного. Вопрос «x ≤ t?» делит толчки одинаково при всех t между двумя соседними значениями признака, поэтому достаточно перебрать середины между соседними различными значениями. Если отсортировать толчки по признаку и идти слева направо, перекладывая по одному из правой группы в левую, счётчики обеих групп обновляются за O(1), и все пороги одного признака проверяются за один проход. Расстояние до города даёт прирост 0,172 бита при пороге 106,5 км, лучший порог магнитуды — всего 0,042 бита (это первая задача статьи). Расстояние побеждает.
Энтропия или Джини. Вместо энтропии часто берут неоднородность Джини: 1 − p² − (1 − p)², вероятность того, что два случайных примера группы окажутся разных классов. Её не нужно логарифмировать, а деревья с ней обычно получаются почти такими же; в scikit-learn она стоит по умолчанию. Вторая задача статьи — дерево по Джини с точной арифметикой.
Жадность и её цена
Дерево выбирает каждый вопрос, не заглядывая вперёд. Построить лучшее дерево целиком — например, с наименьшим средним числом вопросов до ответа, — NP-полная задача: это доказали Лоран Хиафиль и Рональд Ривест в 1976 году. Поэтому все практические алгоритмы жадные, и иногда жадность ошибается. Классический пример — «исключающее или»: ответ 1, когда ровно один из двух признаков равен 1. Каждый признак по отдельности не говорит об ответе ничего, прирост у обоих вопросов нулевой, и жадное дерево может не задать ни одного, хотя два вопроса подряд решили бы задачу целиком.
Переобучение
Дерево можно растить, пока в каждом листе не останется один пример, — тогда на учебных данных оно не ошибётся вовсе. Но учить нужно не учебные данные, а закономерность. Листинг строит дерево глубины 20 один раз — жадный рост не зависит от того, где остановиться, так что дерево глубины d — его верхушка, — и проверяет каждую верхушку:
depth leaves train test
1 2 76.7% 76.5%
2 4 78.2% 78.4%
3 8 79.4% 79.0%
4 16 80.0% 79.6%
6 57 80.4% 79.1%
8 182 81.2% 78.0%
12 787 83.5% 76.1%
16 1459 85.6% 75.0%
20 1836 86.7% 74.6%
До глубины 4 обе доли растут вместе: дерево находит настоящие правила. Дальше учебная продолжает расти, а проверочная падает. В глубоких листьях по несколько толчков, и вопросы там отвечают уже не на «почувствуют ли», а на «какие именно толчки случились в 2015–2021 годах». Шестнадцать листьев объясняют новые годы лучше, чем 1836.
Средства против этого — ограничить глубину, запретить листья меньше заданного размера, не делить узел, если прирост мал, или вырастить большое дерево и потом подрезать ветки, которые не окупаются на отложенных данных, — так делают в CART. Какой именно предел выбрать, решает проверка на данных, которых дерево не видело. Здесь это честно: учимся на прошлом, проверяем на будущем, как и пришлось бы на практике.
Чему на самом деле учится дерево. «Почувствовали» здесь значит «кто-то прислал сообщение». Сообщения присылают люди, которые знают о службе, у которых есть интернет и которые живут рядом. Расстояние до города от десяти тысяч жителей — грубая замена «рядом живут люди», а глубина очага и местные грунты в модели не участвуют вовсе. Дерево честно описывает эти данные, но не физику толчков: о том, как сильно трясёт в данном месте, оно ничего не знает.
Код
Листинг читает каталог с сервера, где исполняется код. Признаки хранятся целыми числами, магнитуда — в сотых. Приросты сравниваются округлёнными до 10⁻⁹: так одинаковые приросты не разводит последний бит логарифма, и Python и Go строят одно и то же дерево. При равенстве побеждают более ранний признак и меньший порог.
Сколько это стоит
В каждом узле примеры сортируются по каждому из F признаков, и это главная работа. На одном уровне дерева узлы вместе содержат не больше n примеров, поэтому уровень стоит O(F·n log n), а всё дерево глубины h — O(h·F·n log n). Если отсортировать примеры по каждому признаку один раз и при делении узла сохранять порядок внутри групп, логарифм уходит: так устроены быстрые библиотеки. Ответ на вопрос — проход от корня к листу, O(h), и это одна из причин, почему деревья любят там, где отвечать надо быстро.
Линии почти прямые с наклоном около единицы: время растёт как n log n, логарифм на таких размерах почти незаметен. Глубина 12 стоит дороже глубины 4 в полтора — три раза, хотя уровней втрое больше: многие ветви останавливаются раньше, когда группа становится однородной.
Где работает
Одно дерево редко бывает самой точной моделью: небольшое изменение данных может поменять первый вопрос, а с ним всё дерево. Зато из деревьев удобно строить. Случайный лес (Лео Брейман, 2001) учит сотни деревьев на случайных подвыборках примеров и признаков и голосует. Градиентный бустинг строит деревья по очереди, каждое — исправлять ошибки предыдущих; библиотеки XGBoost, LightGBM и CatBoost делают именно это, и на табличных данных — заявки, транзакции, измерения датчиков — они часто оказываются точнее нейросетей. А одиночное неглубокое дерево остаётся там, где решение нужно объяснить: его можно распечатать и проверить глазами, как сделали выше.
История
Первое дерево для анализа данных предложили Джеймс Морган и Джон Сонквист в 1963 году. Их метод AID последовательно делил данные социологических опросов на группы, не предполагая, что влияния признаков просто складываются; встретили его в основном критикой. В 1984 году Лео Брейман, Джером Фридман, Ричард Олшен и Чарльз Стоун выпустили книгу «Classification and Regression Trees»; сокращение названия, CART, стало именем метода, а подрезка дерева по проверочным данным — стандартом. Независимо от них Росс Куинлан построил алгоритм ID3 (статья 1986 года) с приростом информации по энтропии Шеннона и потом его наследника C4.5. Большинство нынешних деревьев — потомки этих двух схем.
Задачи
Первая задача — главный шаг алгоритма: лучший порог одного признака за O(n log n), с проверкой на настоящих толчках. Вторая — дерево целиком, но с мерой Джини и точной арифметикой: правила ничьих и одинаковые значения признаков там решают всё.
Лучший первый вопрос Дерево по ДжиниДанные: Землетрясения: каталог USGS, общественное достояние Населённые пункты: GeoNames, CC BY 4.0