Про Олю-жадину и алгоритм-жадину поговорили, но это еще не все члены нашего хинкального клуба.
У жадного алгоритма принятия решений есть потомки - он вообще хорошо растет и пускает корни. И делает это не только в переносном смысле, но и во вполне прямом - на его основе выросли деревья. Впоследствии деревья эволюционировали, поумнели и стали чего-то там между собой решать, а потом вообще сколотили ансамбль (то ли народной музыки, то ли джазовый - выясним это как-нибудь потом).
Так вот эти решающие деревья (decision trees) делают также, как в задаче с хинкали и шашлыком: шаг за шагом принимают решения, только не едят при этом, а отращивают ветки, и, конечно, не могут вернуться назад и передумать, если отрощенная ветка оказалась не идеальна.
Деревья растут во имя решения задачи оптимизации (к сожалению, идеал не достижим: задача построения оптимального по качеству и минимального по глубине дерева - NP-полная, поэтому жадины строят не оптимальное, а просто хорошее решение). Задача дерева - раскидать приходящие на него объекты по кучкам: необходимо с помощью постановки вопросов направлять объект либо в правую ветку, либо в левую, и так шаг за шагом.
Если визуализировать дерево, идеально решившее задачу бинарной классификации, то это была бы вишня, на концах ветвей которой висели бы гроздья ягод, но при этом четкими группами: где-то только красные, где-то только желтые.
Фермеру было бы удобно собирать ягоды, если бы кучек было всего две: красные в одну корзину, желтые в другую. Такое дерево имеет глубину 1 и называется "пнем". Но вырастить пень с идеальным разбиением по цветам ягод можно только для простейшей задачи, а для реальных кейсов - никак.
Для того, чтобы отрастить ветвь, дерево задает вопрос (решающее правило / условие / предикат), а спрашивает оно об определенном качестве (фиче / признаке / абрибуте). Чтобы правильно сформулировать вопрос, нужно правильно выбрать о чем спрашивать. Решающее условие выбирается так, чтобы улучшать разбиение.
Как оценить, что разбиение улучшилось?
1. Теоретико-информационный критерий, уменьшаем информационную энтропию. Чем меньше «разнородность» данных, тем лучше. Когда все вишни красные - энтропия равна нулю. Лучший атрибут - тот, который даст максимальный gain (прирост информации, величина противоположная энтропии) результирующей ветки относительно исходной
2. Статистический подход, уменьшаем расстояние между распределениями целевых(настоящих) и предсказанных значений = уменьшаем индекс Джини. Чем меньше индекс Джини, находящийся в пределах от 0 до 1, тем лучше. Когда все вишни красные, Джини равен нулю.
Но если фермер ничего с деревом делать не будет, оно может так сильно разрастись, что на каждой финальной ветке окажется по одной ягодке. Про такие деревья говорят "переобучилось", т.е. подогналось под обучающую выборку и на новых данных будет плохо обобщать. Что делать?
1. Можно ограничивать ягоды. Например, прекращать выращивать дерево, когда на концах ветвей остается определенное количество плодов (задание минимального числа объектов в узле) или когда доля правильно раскрашенных ягод будет достигнута (ранняя остановка)
2. Можно ограничивать ветви, например, при достижении заданного количества ветвлений (ограничение глубины дерева)
Но а можно поступить как ленивый фермер: сначала дождаться, когда дерево вырастет до своего предела, а затем взять секатор и пойти срезать (отсечение ветвей). При этом отрезаются ветви, которые не приведут к значимому снижению качества модели.
Вообще говоря, деревья решений - большие молодцы. Они быстрые, простые и легко интерпретируемые, позволяют увидеть новые неочевидные зависимости.
Из минусов, что чувствительны к шуму в обучающей выборке, могут переобучаться и не дают гарантированно оптимального решения. А еще не экстраполируют зависимости, т.е. не могут как линейная модель выйти за границы области значений обучающей выборки - там будет просто константное предсказание.
Ксатати, сейчас сезон вишни! А еще, не все деревья - жадины.
Шпаргалка:
https://faculty.ucmerced.edu/mcarreira-perpinan/papers/ijcnn21a-slides.pdf
