01b — Логические методы классификации

Решающие деревья

Алгоритм построения решающего дерева

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

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

можно проводить эксперименты и смотреть, в каких задачах работает лучше один критерий, в каких работает лучше другой
они строят немного по-разному деревья

есть еще один — энтропийный критерий с достаточно сложной формулой, которая вытекает из теории информации
мы не будем ее разбирать подробно
на практике оказывается, что этот критерий очень похож на критерий Джини
и работает примерно так же

Обработка пропусков. Достоинства и недостатки решающих деревьев.

мы можем по-разному задавать множество предикатов, из которого мы выбираем предикаты во внутренних вершинах
вплоть до того, что это могут быть какие-то другие модели классификации – главное, чтобы они давали ответ да или нет

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

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

еще раз, эти недостатки вытекают из того, что алгоритм жадный

Способы устранения недостатков решающих деревьев

известный пример
синтетическая задача классификации
classification of XOR problem
это пример задачи, которая не решается, например, линейным классификатором
выборка не может быть разделена прямой на два класса без ошибок

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

Резюме:

плохо работают на выборках с большим количеством признаков

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

Quiz: Решающие деревья