29 March 2011

Классификация и регрессия с помощью деревьев принятия решений

Data Mining
Sandbox

Введение


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

Деревья принятия решений


Дерево принятия решений — это дерево, в листьях которого стоят значения целевой функции, а в остальных узлах — условия перехода (к примеру “ПОЛ есть МУЖСКОЙ”), определяющие по какому из ребер идти. Если для данного наблюдения условие истина то осуществляется переход по левому ребру, если же ложь — по правому.

Классификация



На изображении приведенном выше показано дерево классификации ирисов. Классификация идет на три класса (на изображении помечены — красным, синим и зеленым), и проходит по параметрам: длина\толщина чашелистика (SepalLen, SepalWid) и длина\толщина лепестка (PetalLen, PetalWid). Как видим, в каждом узле стоит его принадлежность к классу (в зависимости от того, каких элементов больше попало в этот узел), количество попавших туда наблюдений N, а так же количество каждого класса. Так же не в листовых вершинах есть условие перехода — в одну из дочерних. Соответственно, по этим условиям и разбивается выборка. В результате, это дерево почти идеально (6 из 150 неправильно) классифицировало исходные данные (именно исходные — те на которых оно обучалось).

Регрессия

Если при классификации в листах стоят результирующие классы, при регрессии же стоит какое-то значение целевой функции.


На выше приведенном изображении регрессионное дерево, для определения цены на землю в городе Бостон в 1978 году, в зависимости от параметров RM — количество комнат, LSTAT — процент неимущих и нескольких других параметров (более детально можно посмотреть в [4]). Соответственно, здесь в каждом узле мы видим среднее значение (Avg) и стандартное отклонение (STD) значений целевой функции наблюдений попавших в эту вершину. Общее количество наблюдений попавших в узел N. Результатом регрессии будет то значение среднего (Avg), в какой узел попадёт наблюдение.
Таким образом изначально классификационное дерево, может работать и для регрессии. Однако при таком подходе, обычно требуются большие размеры дерева, чем при классификации, что бы достигнуть хороших результатов регрессии.

Основные методы


Ниже перечислены несколько основных методов, которые используют деревья принятия решений. Их краткое описание, плюсы и минусы.

CART

CART (англ. Classification and regression trees — Классификационные и регрессионные деревья) был первым из методов, придуманный в 1983 четверкой известных ученых в области анализа данных: Leo Breiman, Jerome Friedman, Richard Olshen and Stone [1].
Суть этого алгоритма состоит в обычном построении дерева принятия решений, не больше и не меньше.
На первой итерации мы строим все возможные (в дискретном смысле) гиперплоскости, которые разбивали бы наше пространство на два. Для каждого такого разбиения пространства считается количество наблюдений в каждом из подпространств разных классов. В результате выбирается такое разбиение, которое максимально выделило в одном из подпространств наблюдения одного из классов. Соответственно, это разбиение будет нашим корнем дерева принятия решений, а листами на данной итерации будет два разбиения.
На следующих итерациях мы берем один худший (в смысле отношения количества наблюдений разных классов) лист и проводим ту же операцию по разбиению его. В результате этот лист становится узлом с каким-то разбиением, и двумя листами.
Продолжаем так делать, пока не достигнем ограничения по количеству узлов, либо от одной итерации к другой перестанет улучшаться общая ошибка (количество неправильно классифицированных наблюдений всем деревом). Однако, полученное дерево будет “переобучено” (будет подогнано под обучающую выборку) и, соответственно, не будет давать нормальные результаты на других данных. Для того, что бы избежать “переобучения”, используют тестовые выборки (либо кросс-валидацию) и, соответственно, проводится обратный анализ (так называемый pruning), когда дерево уменьшают в зависимости от результата на тестовой выборке.
Относительно простой алгоритм, в результате которого получается одно дерево принятия решений. За счет этого, он удобен для первичного анализа данных, к примеру, что бы проверить на наличие связей между переменными и другим.
+ Быстрое построение модели
+ Легко интерпретируется (из-за простоты модели, можно легко отобразить дерево и проследить за всеми узлами дерева)
- Часто сходится на локальном решении (к примеру, на первом шаге была выбрана гиперплоскость, которая максимально делит пространство на этом шаге, но при этом это не приведёт к оптимальному решению)

RandomForest

Random forest (Случайный лес) — метод, придуманный после CART одним из четверки — Leo Breiman в соавторстве с Adele Cutler [2], в основе которого лежит использование комитета (ансамбля) деревьев принятия решений.
Суть алгоритма, что на каждой итерации делается случайная выборка переменных, после чего, на этой новой выборке запускают построение дерева принятия решений. При этом производится “bagging” — выборка случайных двух третей наблюдений для обучения, а оставшаяся треть используется для оценки результата. Такую операцию проделывают сотни или тысячи раз. Результирующая модель будет будет результатом “голосования” набора полученных при моделировании деревьев.
+ Высокое качество результата, особенно для данных с большим количеством переменных и малым количеством наблюдений.
+ Возможность распараллелить
+ Не требуется тестовая выборка
- Каждое из деревьев огромное, в результате модель получается огромная
- Долгое построение модели, для достижения хороших результатов.
- Сложная интерпретация модели (Сотни или тысячи больших деревьев сложны для интерпретации)

Stochastic Gradient Boosting

Stochastic Gradient Boosting (Стохастическое градиентное добавление) — метод анализа данных, представленный Jerome Friedman [3] в 1999 году, и представляющий собой решение задачи регрессии (к которой можно свести классификацию) методом построения комитета (ансамбля) “слабых” предсказывающих деревьев принятия решений.
На первой итерации строится ограниченное по количеству узлов дерево принятия решений. После чего считается разность между тем, что предсказало полученное дерево умноженное на learnrate (коэффициент “слабости” каждого дерева) и искомой переменной на этом шаге.
Yi+1=Yi-Yi*learnrate
И уже по этой разнице строится следующая итерация. Так продолжается, пока результат не перестанет улучшаться. Т.е. на каждом шаге мы пытаемся исправить ошибки предыдущего дерева. Однако здесь лучше использовать проверочные данные (не участвовавшие в моделировании), так как на обучающих данных возможно переобучение.
+ Высокое качество результата, особенно для данных с большим количеством наблюдений и малым количеством переменных.
+ Сравнительно (с предыдущим методом) малый размер модели, так как каждое дерево ограничено заданными размерами.
+ Сравнительно (с предыдущим методом) быстрое время построение оптимальное модели
- Требуется тестовая выборка (либо кросс-валидация)
- Невозможность хорошо распараллелить
- Относительно слабая устойчивость к ошибочным данным и переобучению
- Сложная интерпретация модели (Так же как и в Random forest)

Заключение


Как мы увидели у каждого метода есть свои плюсы и минусы, и соответственно, в зависимости от задачи и исходных данных, при решении можно использовать один из трех методов и получить нужный результат. Однако, CART больше используется в университетах для обучения и исследований, когда необходима какая-то чёткая описательная база для решения (как в приведенном выше примере анализа цены земли в Бостоне). А для решения промышленных задач обычно используют один из его потомков — Random Forest или TreeNet.
Перечисленные методы можно найти в многих современных пакетах для анализа данных:

Список литературы


  1. “Classification and Regression Trees”. Breiman L., Friedman J. H., Olshen R. A, Stone C. J.
  2. “Random Forests”. Breiman L.
  3. “Stochastic Gradient Boosting”. Friedman J. H.
  4. http://www.cs.toronto.edu/~delve/data/boston/bostonDetail.html
Tags:анализ данныхdata miningалгоритмыcartrandom foresttreenetdecision treesдеревья решенийдеревья принятия решений
Hubs: Data Mining
+56
54.8k 166
Comments 31
Popular right now
Курс по аналитике данных
November 30, 202053,500 ₽SkillFactory
Data Engineer
November 30, 202080,000 ₽OTUS
BIG DATA с нуля
December 22, 202019,700 ₽Нетология