Деревья решений. Часть I: Введение

Алгоритмы обучения с учителем, основанные на использовании деревьев решений (англ. "decision trees"; в русскоязычных источниках используются также термины "деревья принятия решений", "деревья классификации и регрессии" (от "regression and classification trees, CART"), "решающие деревья" и др.) чрезвычайно популярны. Эта популярность обусловлена несколькими причинами:

• Деревья решений позволяют получать очень легко интерпретируемые модели, представляющие собой набор правил вида "если..., то...". Интерпретация облегчается в том числе за счет возможности представить эти правила в виде наглядной древовидной структуры.
• В силу своего устройства деревья решений позволяют работать с переменными любого типа без необходимости какой-либо предварительной подготовки этих переменных для ввода в модель (например, логарифмирование, преобразование категориальных переменных в индикаторные, и т.п.).
• Исследователю нет необходимости в явном виде задавать форму взаимосвязи между откликом и предикторами, как это, например, происходит в случае с обычными регрессионными моделями. Это оказывается особенно полезным при работе с большими объемами данных, о свойствах которых мало что известно.
• Деревья решений, по сути, автоматически выполняют отбор информативных предикторов и учитывают возможные взаимодействия между ними. Это, в частности, делает деревья решений полезным инструментом разведочного анализа данных.
• Деревья решений можно эффективно применять к данным с пропущенными значениями, что очень полезно при решении практических задач, где наличие пропущенных значений - это, скорее, правило, чем исключение.
• Деревья решений одинаково хорошо применимы как к количественным, так и к качественным зависимым переменным.

Конечно, как и любой другой инструмент, деревья решений не лишены недостатков. Наиболее важными из них являются следующие:

• Нестабильность (дисперсия) модели. Речь здесь идет о том, что даже незначительные изменения в обучающих данных могут существенно изменять структуру получаемой модели. Это, в свою очередь, может приводить к совершенно иной интерпретации модели.
• Относительно невысокая точность предсказаний. Это обусловлено тем, что деревья решений разбивают пространство предикторов на прямоугольные области (см. ниже). Если взаимосвязь между откликом и предикторами невозможно адекватно представить с помощью таких областей, то соответствующая модель будет допускать значительные ошибки при предсказании отклика для новых наблюдений.

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

Для начала рассмотрим, что собой представляют регрессионные деревья (англ. "regression trees"). В качестве примера воспользуемся набором данных Auto из пакета ISLR, который является приложением к книге "An Introduction to Statistical Analysis with Applications with R" (в переводе на русский яз. см. здесь). На приведенном ниже рисунке показано регрессионное дерево, позволяющее предсказывать эффективность расхода топлива автомобилем (mpg, миль/галлон) на основе количества цилиндров в двигателе (cylinders) и веса автомобиля (weight).

О дереве решений можно думать как о наборе из нескольких правил разбиения (англ. "splitting rule"). Под "правилом разбиения" понимают утверждение в отношении той или иной переменной, которое может быть истинным или ложным и которое, соответственно, позволяет разбить данные на сегменты (например, для части наблюдений будет справедливо утверждение cylinders >= 5.5, а для другой - утверждение cylinders < 5.5). Графически представленное дерево решений, как правило, состоит из нескольких узлов (англ. "nodes") и отходящих от них ветвей (англ. "branches"). Обычно дерево изображают "вверх ногами", в связи с чем его первый, корневой узел ("root node"), располагается вверху диаграммы. Остальные узлы называют внутренними ("internal nodes").

На приведенном выше рисунке правило разбиения, приходящееся на корневой узел, относит все автомобили с количеством цилиндров >=5 к левой ветви дерева (хотя это правило представлено как cylinders >= 5.5, понятно, что количество цилиндров - это дискретная величина, и поэтому речь, по сути, идет о cylinders >= 5). Соответствующие наблюдения разбиваются далее на две группы согласно правилу weight >= 3658. В итоге модель предсказывает, что у автомобилей с количеством цилиндров >= 5 и весом >= 3658 фунтов, средняя эффективность расхода топлива составит 14.62 миль/галлон, а у автомобилей с количеством цилиндров >= 5 и весом < 3658 фунтов - 19.78 миль/галлон. Это легко проверить, например, следующим образом:

library(ISLR)
data(Auto)
library(dplyr)
 
Auto %>% 
    filter(cylinders >= 5.5, weight >= 3658) %>%
    summarise(MEAN = mean(mpg))
 
MEAN
1 14.61505
 
Auto %>% 
    filter(cylinders >= 5.5, weight < 3658) %>% 
    summarise(MEAN = mean(mpg))
 
     MEAN
1 19.7828

Спускаясь вниз по правой ветви, отходящей от корневого узла дерева, можно увидеть, как оно аналогичным образом предсказывает средние значения эффективности расхода топлива, равные 26.13 и 32.61 миль/галлон.

Таким образом, это дерево разбивает все автомобили в пространстве предикторов (cylinders и weight) на 4 области, или сегмента. Математически эти области можно представить как

• \(R_1 = \{\text{cylinders} \geq 5.5, \text{weight} \geq 3658\}  \)
• \(R_2 = \{\text{cylinders} \geq 5.5, \text{weight} < 3658\}  \)
• \(R_3 = \{\text{cylinders} < 5.5, \text{weight} \geq 2217\}  \)
• \(R_4 = \{\text{cylinders} < 5.5, \text{weight} < 2217\}  \)

На следующем рисунке эти области для наглядности показаны в координатах cyliners и weight:

Области \(R_1, R_2, R_3, R_4 \) называют также конечными узлами ("terminal nodes"), или листьями дерева ("leaves"). Как мы выяснили, в пределах каждой области предсказываемые значения количественной переменной (здесь mpg) постоянны и равны среднему значению обучающих наблюдений.

В рассмотренном примере дерево решений было построено с целью предсказания значений количественной зависимой переменной, однако, как было отмечено ранее, деревья решений одинаково хорошо справляются и с задачами классификации. В отличие от регрессионных деревьев, деревья классификации ("classification trees") относят то или иное наблюдение к наиболее часто встречающемуся классу в области, в которую оно попадает.

В следующих сообщениях мы рассмотрим алгоритмы построения деревьев классификации и регрессии, т.е. подробнее выясним, как именно происходит разбиение обучающих наблюдений на отдельные области в пространстве предикторов.