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

Введение


В данной статье сделан обзор деревьев принятия решений (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

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 31

  • UFO just landed and posted this here
      +4
      + конечно за то, что вообще написали. Но как-то слишком общо получилось. Нет ничего про ID3, про энтропию и про усечение(тот самый pruning) только в двух словах упоминается. Возможно будет продолжение?
        +2
        Собираюсь написать ещё по статье про каждый алгоритм, более подробно. Это только вводная статья — посмореть, интересна ли вообще тема.
        0
        Статья очень вовремя. Учитывая что в раскрытой недавно майкрософтом технологии трекинга людей с помощью Kinect используются именно деревья решений.
          0
          Казалось бы, причем тут data mining?

          Хинт: перенесите сюда.
            +1
            Классификация и регрессия — это прежде всего задачи анализа данных. А ИИ это просто более общая область, которая использует наработки в анализе данных. Вы же не будете предлагать, к примеру, пост чисто по математике перенести в ИИ — даже если там используется эта математика.
            0
            застряёт?
              0
              Спасибо. Исправил на «Часто сходится на локальном решении».
              +3
              Мне, как практику, сложно понять актуальность изложенных подходов без привязки к конкретным примерам.
              Предлагаю написать продолжение статьи с конкретными примерами, с рассказами насколько хорошо/плохо всё это работало на его задачах. Очень полезная будет статья. Спасибо заранее.
                +1
                У вас есть некое множество векторов в N-мерном пространстве. Вам необходимо классифицировать эти вектора в K групп, в простейшем случае K = 2. Дальше все по тексту ;-)

                Это математика, привыкайте ;) статья очень простая для понимания, достаточно приложить немного усилий.
                  0
                  Ну, как-бы, математика мне не чужда, не об этом речь.
                  Речь вот о чём: вся эта математика, она зачем? Куда её можно применить, конкретно?

                  В качестве примера: можно очень долго обсуждать теорию bsp-деревьев. Но гораздо лучше, если обсуждение будет идти в применении к рисованию трёхмерной сцены на современном оборудовании.

                  Я лично за то, чтобы теория и практика шли вместе, рука об руку. Одно без другого — уже не то (повторюсь, это моё личное мнение).

                  Причём под практикой я понимаю не абстрактные задачи уровня «азбуки» (хотя и они важны на самом подготовительном этапе), а совершенно конкретные задачи реального мира, с которыми в работе встречается автор.
                    0
                    Согласен, что практика нужна. И я попытаюсь написать ещё статей, с примерами по каждому из алгоритмов. Просто не хочется писать полотно на 10 страниц, которое потом никто не прочтёт. Или разжевывать совсем простые вещи.
                    Собственно — это была обзорная статья. Цель её была попасть на хабр посмотреть насколько интересна тема.
                  +1
                  Ну для деревьев принятия решений есть примеры в картинках :)
                  А вообще, хочу написать конкретно по каждмоу алгоритму — с описанием данных, результирующией модели и тд и тп.
                  Или Вы хотите увидеть именно модели для одних данных, что бы сравнить разные методы?
                    0
                    Пожалуйста, посмотрите комментарий чуть выше. Там я как раз предложил, как бы можно было улучшить статью (с моей точки зрения, разумеется).
                      0
                      И, кстати, спасибо за саму статью. Все мои вопросы не с точки зрения «лишь бы покритиковать», а, скорее, исходят из желания лучше понять, куда применить те интересные подходы, которые Вы излагаете.
                    +1
                    Такое ощущение, что лучшие статьи из песочницы.
                      0
                      Довелось использовать Random forest в одном проекте. Алгоритм был выбран после теста в среде Weka. Так вот исходя из теории и практики, если у вас огромные деревья — you are doing it wrong! Ансамбль (ensemble) почти всегда означает слабые (weak) классификаторы в качестве участников. Одна из сильных сторон таких классификаторов — устойчивость к шуму (data noise). Но если делать деревья большими, то во первых они получаются сильно привязаны к тестовым данным (over-fitting), а во вторых шум становиться частью классификации, что, естественно снижает всю эффективность.
                        0
                        Да, Random Forest не всегда удачное решение — собственно плюсы и минусы я описал выше. Из практики скажу, что я например, пользуюсь в основном Gradient Boosting (TreeNet от Salford-Systems) — он даёт намного более устойчивую модель и неплохо справляется с переобучением (особенно, если вовремя остановиться с количеством деревьев).

                        Однако ансамбли — тоже хорошая техника, но я использовал ее не на слабых классификаторах — а для некоторого количества TreeNet моделей, каждая из которых давала мне хороший результат. Их ансамбль дал результат ещё лучше (проверка велась на валидационных данных, не учавствовавших в обучении).
                          0
                          Собственно я сказал, что Random Forest удачное решение (в моём случае), а вы неудачно описали плюсы и минусы выше.
                            0
                            Извините, неправильно Вас понял.
                            Просто в Random Forest, который я использую (и который описан Брейманом), используются нормальные деревья, а не «слабые» классификаторы. Именно поэтому я перечислил те "+" и "-".
                            Просто «слабые» классификаторы — это основная идея алгоритмов семейства «boosting». Поэтому, если в Weka используется «слабые» классификаторы для Random Forest, то наверно это собственная модификация.
                            Я посмотрю на этот проект и попробую сделанный там алгортим. Спасибо за ссылку и Ваш комментарий.
                        0
                        Пример использования. Приготовил эту статью для ленты, но написать не могу — кармы нет.
                        Идея лежит в моем «долгом ящике» уже давно, а вновь напомнила о себе после поста "Битва брендов: с 0 до 100 000 уников в сутки за неделю". Данный пост, напомнил мне о том, что люди очень любят выражать свое imho, сравнивать его c мнением окружающих, а также о том, что подобного рода проекты должны быть просты до безобразия и наиболее эффективно продвигаются через социальные сети.
                        Что касается «Битвы брендов», то, пожалуй, я соглашусь с комментаторами этого поста в двух вещах. В чистом виде, интерес к нему быстро угаснет. Ну и пока что, там ноль монетизации. Идея, которую я предлагаю на ваш суд, по-моему, лишена данных недостатков.
                        Полить грязью еще одну идею<habracut />

                        Насколько я могу судить, количество людей который знают о том, что такое Data mining среди пользователей Habra, заметно превышает среднее по популяции. Тем не менее, приведу необходимый комментарий и прошу не кидать помидорами за неточности в формулировках. Главное чтобы любой читатель ухватил суть.
                        Существует нехитрый математический аппарат, который позволяет проделать следующий трюк: опрашивая людей по существу какого-нибудь вопроса и фиксируя помимо ответа на вопрос некоторые параметры самих людей, можно с лучшей, чем пальцем в небо хорошей вероятностью предсказать ответ на данный вопрос другого человека, зная только его параметры. Такие методы называются «обучение с учителем», и к ним относятся деревья решений, логистическая регрессия, нейронные сети и т.д. и т.п.
                        А теперь представьте, что можно делать, гоняя некие веселые опросы, но при этом, зная немного информации о тех, кто в них принимал участие. Можно попробовать угадывать результат для других людей, причем определять не только «да», «нет», но и показывать степень уверенности в предсказании.
                        Получается, что на сайте есть регистрация с подробной анкетой (анонимной и закрытой), раздел с текущими голосовалками, раздел с результатами голосований и раздел с предсказаниями.
                        Почему это привлечет пользователя? Потому же, почему их привлекла «Битва брендов». Собственно, весь текущий функционал «Битвы брендов» включен. А помимо этого появляются занятные вкусности, которые увеличат интерес к проекту. Можно рекомендовать посетителю фильмы, книги, музыкальные новинки, туры и т.д. которые, статистически понравятся именно ему.
                        Монетизацию можно построить на платных опросах. В сети их немало и спрос на услугу есть, прежде всего, со стороны маркетинговых отделов. Но не многим пользователям в сети интересно за копейки терять время, заполняя огромные опросники. Совершенно другое дело для пользователя заполнить анкету один раз, а посреди голосовалок кто круче Джена Джемесон или Тера Патрик выбрать, какой из вариантов нового лого Евросети ему больше нравится. Доходами от таких исследований можно делиться с пользователями в том или ином виде.
                        Ваше мнение?
                          0
                          Тут надо крепко подумать, какие данные брать в расчет в каждой области (фильмы/книги/политика/...). Например, если житель города N проголосовал за собаку (в опросе собака vs кошка), то не факт же, что другой житель того же города проголосует так же. Или если два человека в течении нескольких вопросов выбирали один вариант, то как раз вряд ли в будущем они выберут опять один. (Т.е. если оба предпочитают собак, кока-колу и дирол, то это не значит, что они выберут один вариант в опросе ролики vs велосипед).
                            0
                            Конечно, в идее здравое зерно есть. Однако, меня например бы напрягла длинная анкета (а нужно достаточно много параметров набрать) при регистрации — что бы всего лишь проголосовать за колу или пепси. (Хотя меня и «Битва брендов» не заставила пойти проголосовать).
                            Другой вопрос, что если это будет сервис именно рекомендаций — я оставляю о себе информацию. А мне рекомендует интересные для меня вещи — в этом что-то есть.
                              +1
                              Детрактор длинной регистрации можно просто обойти — сделать постоянную конкретизацию своего профиля частью увлекательного процесса. При каждом посещении можно делиться данными по кусочкам. Начни с основного и заполняй дальше при следующих визитах. Выращиванию деревьев неполные данные не помешают — с мисингами они прекрасно дружат.
                            0
                            Спасибо за комментарий, но у вас бы не сложилось таких вопросов если бы вы на практике вырастили немного деревьев на основе того же CART. Дерево будет выращиваться под каждый опрос. А это означает, что если фактор ГО РОД in ('';'';'') попал как элемент разбиения одного узла на неколько подузлов, то в этих полученных послеразбиения подузлах наблюдается существенный дисбаланс относительно заданного вопроса, а не 50% на 50%. А значит повышается шанс угадать. Короче, сильно думать там не надо, за все подумает статистика.
                              0
                              Я по образовани не математик, но мне кажется использование понятия гиперплоскость для классификационных деревьев некорректно.
                                0
                                Смотрите — набор критериев — это Н-мерое пространство, где каждое наблюдения — это какая-то точка. Тогда условия классификационных деревьев, это не что иное как гиперплоскости, делящие это пространство на два полупространства.
                                Т.е. условия вида X > 10 просто значит, что мы провели гиперплоскость X = 10, соответственно два наследника этого узла будут содержать первое и второе полученные полупространства.
                                  0
                                  в каждом узле дерева мы делим данные на определенное количество «веток», а не на 2 подпространства, т.к. 2 листа в ветке это крайне примитивный способ их построения. Поэтому в каждый момент ветвления мы работаем с набором данных, который ветвится до какого-то предела. Поэтому мне не понравилось употребление этого термина, т.к. гиперплоскость часто подразумевает разделение на две части.
                                    0
                                    Эм… Я с Вами не согласен — я не видел ни одного алгоритма (да что там, я сейчас поискал и не нашел ни одного упоминания) строящего не бинарное дерево принятия решений. Однако, если у Вас есть литература по таким алгоритмам, прошу просветить меня.
                                    Плюс, даже если предположить, что у нас Н-ринчное дерево, его узлы можно в конце концов разбить на бинарные.
                                      0
                                      Да несколько перепутал, каюсь. В софте, который я использовал применялся алоритм Recursive partitioning, он несколько отличается от Decision trees.
                                      Вот пример диссертации на тему — PDF.
                                        0
                                        Хм, если я правильно понял, то рекурсивное разделение (Recursive partitioning) это именно тот метод, которым строятся любые деревья принятия решений. Однако в той диссертации какое-то расширение этого метода — я просмотрю, тогда смогу нормально что-то ответить.
                                        Спасибо за ссылки.

                              Only users with full accounts can post comments. Log in, please.