Решающие деревья
Решающее дерево (decision tree) представляет со бой алгоритм прогнозирования, основанный на применении иерархической системы правил. Пример решающего дерева для банковской задачи кредитного скоринга показан ниже:
Дерево делится на внутренние узлы (inner nodes) и терминальные узлы (листья, terminal nodes, leaves).
-
Во внутренних узлах производится проверка условия вида "признакпорог". Если условие выполнено, то осуществляется спуск в левую дочернюю вершину, а если не выполнено, то в правую, пока не дойдём до терминальной вершины.
-
Каждой терминальной вершине сопоставлен константный прогноз:
-
в случае регрессии - это число
-
в случае классификации - это метка класса либо вектор распределения вероятностей классов.
-
Работу решающего дерева можно представить непересекающейся системой правил. Например, для дерева из иллюстрации это будет:
ЕСЛИ (доход 40.000) ИЛИ (есть просрочки) И (задолженность>10.000) ТО отказать.
ЕСЛИ (доход>40.000) ИЛИ (нет просрочек) ИЛИ (есть просрочки) И (задолженность 10.000) ТО дать кредит.
Существует целый класс правиловых алгоритмов машинного обучения (rule induction), которые строят интерпретируемые, но не очень точные прогнозы. В настоящее время из них используются в основном только решающие деревья, недостаточную точность которых компенсируют применением не одного, а целого набора решающих деревьев (ансамбля).
Здесь рассматривается самый популярный алгоритм решающего дерева CART (classification and regression tree). Тем не менее, существуют и другие алгоритмы, такие как ID3 и C4.5. В них число потомков внутренних вершин может быть больше двух, а внутри вершин применяться другие решающие правила.
Далее мы рассмотрим примеры и особенности работы решающих деревьев для задачи регрессии и классификации, алгоритм обучения и обрезки решающих деревьев, а также как оценивать важность признаков по решающему дереву. Мы также изучим основные достоинства и недостатки этого метода.