Методы классификации и прогнозирования. Деревья решений
Аннотация: Описывается метод деревьев решений. Рассматриваются элементы дерева решения, процесс его построения. Приведены примеры деревьев, решающих задачу классификации. Даны алгоритмы конструирования деревьев решений CART и C4.5.
Метод деревьев решений ( decision trees ) является одним из наиболее популярных методов решения задач классификации и прогнозирования. Иногда этот метод Data Mining также называют деревьями решающих правил , деревьями классификации и регрессии.
Как видно из последнего названия, при помощи данного метода решаются задачи классификации и прогнозирования.
Если зависимая, т.е. целевая переменная принимает дискретные значения, при помощи метода дерева решений решается задача классификации.
Если же зависимая переменная принимает непрерывные значения, то дерево решений устанавливает зависимость этой переменной от независимых переменных, т.е. решает задачу численного прогнозирования.
Впервые деревья решений были предложены Ховилендом и Хантом (Hoveland, Hunt) в конце 50-х годов прошлого века. Самая ранняя и известная работа Ханта и др., в которой излагается суть деревьев решений — «Эксперименты в индукции» («Experiments in Induction «) — была опубликована в 1966 году.
В наиболее простом виде дерево решений — это способ представления правил в иерархической, последовательной структуре. Основа такой структуры — ответы «Да» или «Нет» на ряд вопросов.
На рис. 9.1 приведен пример дерева решений, задача которого — ответить на вопрос: «Играть ли в гольф?» Чтобы решить задачу, т.е. принять решение, играть ли в гольф, следует отнести текущую ситуацию к одному из известных классов (в данном случае — «играть» или «не играть»). Для этого требуется ответить на ряд вопросов, которые находятся в узлах этого дерева, начиная с его корня.
Первый узел нашего дерева «Солнечно?» является узлом проверки , т.е. условием. При положительном ответе на вопрос осуществляется переход к левой части дерева, называемой левой ветвью , при отрицательном — к правой части дерева. Таким образом, внутренний узел дерева является узлом проверки определенного условия. Далее идет следующий вопрос и т.д., пока не будет достигнут конечный узел дерева, являющийся узлом решения . Для нашего дерева существует два типа конечного узла : «играть» и «не играть» в гольф.
В результате прохождения от корня дерева (иногда называемого корневой вершиной) до его вершины решается задача классификации, т.е. выбирается один из классов — «играть» и «не играть» в гольф.
Целью построения дерева решения в нашем случае является определение значения категориальной зависимой переменной.
Итак, для нашей задачи основными элементами дерева решений являются:
Внутренний узел дерева или узел проверки : «Температура воздуха высокая?», «Идет ли дождь?»
Лист , конечный узел дерева, узел решения или вершина : «Играть», «Не играть»
Ветвь дерева (случаи ответа): «Да», «Нет».
В рассмотренном примере решается задача бинарной классификации , т.е. создается дихотомическая классификационная модель. Пример демонстрирует работу так называемых бинарных деревьев.
В узлах бинарных деревьев ветвление может вестись только в двух направлениях, т.е. существует возможность только двух ответов на поставленный вопрос («да» и «нет»).
Бинарные деревья являются самым простым, частным случаем деревьев решений. В остальных случаях, ответов и, соответственно, ветвей дерева, выходящих из его внутреннего узла , может быть больше двух.
Рассмотрим более сложный пример. База данных , на основе которой должно осуществляться прогнозирование, содержит следующие ретроспективные данные о клиентах банка, являющиеся ее атрибутами: возраст, наличие недвижимости, образование, среднемесячный доход, вернул ли клиент вовремя кредит . Задача состоит в том, чтобы на основании перечисленных выше данных (кроме последнего атрибута) определить, стоит ли выдавать кредит новому клиенту.
Как мы уже рассматривали в лекции, посвященной задаче классификации, такая задача решается в два этапа: построение классификационной модели и ее использование.
На этапе построения модели, собственно, и строится дерево классификации или создается набор неких правил . На этапе использования модели построенное дерево , или путь от его корня к одной из вершин, являющийся набором правил для конкретного клиента, используется для ответа на поставленный вопрос «Выдавать ли кредит ?»
Правилом является логическая конструкция, представленная в виде «если : то :».
На рис. 9.2. приведен пример дерева классификации, с помощью которого решается задача «Выдавать ли кредит клиенту?». Она является типичной задачей классификации, и при помощи деревьев решений получают достаточно хорошие варианты ее решения.
Как мы видим, внутренние узлы дерева (возраст, наличие недвижимости, доход и образование) являются атрибутами описанной выше базы данных . Эти атрибуты называют прогнозирующими, или атрибутами расщепления (splitting attribute ). Конечные узлы дерева, или листы, именуются метками класса, являющимися значениями зависимой категориальной переменной «выдавать» или «не выдавать» кредит .
Каждая ветвь дерева, идущая от внутреннего узла , отмечена предикатом расщепления . Последний может относиться лишь к одному атрибуту расщепления данного узла. Характерная особенность предикатов расщепления : каждая запись использует уникальный путь от корня дерева только к одному узлу-решению. Объединенная информация об атрибутах расщепления и предикатах расщепления в узле называется критерием расщепления (splitting criterion ) [33].
На рис. 9.2. изображено одно из возможных деревьев решений для рассматриваемой базы данных . Например, критерий расщепления «Какое образование?», мог бы иметь два предиката расщепления и выглядеть иначе: образование «высшее» и «не высшее». Тогда дерево решений имело бы другой вид.
Таким образом, для данной задачи (как и для любой другой) может быть построено множество деревьев решений различного качества, с различной прогнозирующей точностью.
Качество построенного дерева решения весьма зависит от правильного выбора критерия расщепления . Над разработкой и усовершенствованием критериев работают многие исследователи.
Метод деревьев решений часто называют «наивным» подходом [34]. Но благодаря целому ряду преимуществ, данный метод является одним из наиболее популярных для решения задач классификации.
Источник
Дерево решений (Decision Trees)
Дерево решений — классификатор, построенный на основе решающих правил вида «если, то», упорядоченных в древовидную иерархическую структуру.
В основе работы дерева решений лежит процесс рекурсивного разбиения исходного множества объектов на подмножества, ассоциированные с предварительно заданными классами. Разбиение производится с помощью решающих правил, в которых осуществляется проверка значений атрибутов по заданному условию.
Строятся на основе обучения с учителем. В качестве обучающего набора данных используется множество наблюдений, для которых предварительно задана метка класса.
Структурно дерево решений состоит из объектов двух типов — узлов (node) и листьев (leaf). В узлах расположены решающие правила и подмножества наблюдений, которые им удовлетворяют. В листьях содержатся классифицированные деревом наблюдения: каждый лист ассоциируется с одним из классов, и объекту, который распределяется в лист, присваивается соответствующая метка класса.
Визуально узлы и листья в дереве хорошо различимы: в узлах указываются правила, разбивающие содержащиеся в нем наблюдения, и производится дальнейшее ветвление. В листьях правил нет, они помечаются меткой класса, объекты которого попали в данный лист. Ветвление в листьях не производится, и они заканчивают собой ветвь дерева (поэтому их иногда называют терминальными узлами).
Если класс, присвоенный деревом, совпадает с целевым классом, то объект является распознанным, в противном случае — нераспознанным. Самый верхний узел дерева называется корневым (root node). В нем содержится весь обучающий или рабочий набор данных.
Дерево решений является линейным классификатором, т.е. производит разбиение объектов в многомерном пространстве плоскостями (в двумерном случае — линиями).
Дерево, представленное на рисунке, решает задачу классификации объектов по двум атрибутам на три класса.
На рисунке кружки представляют объекты класса 1, квадраты — класса 2, а треугольники — класса 3. Пространство признаков разделено линиями на три подмножества, ассоциированных с классами. Эти же подмножества будут соответствовать и трем возможным исходам классификации. В классе «треугольников» имеются нераспознанные примеры («квадраты»), т.е. примеры, попавшие в подмножества, ассоциированные с другим классом.
Теоретически, алгоритм может генерировать новые разбиения до тех пор, пока все примеры не будут распознаны правильно, т.е. пока подмножества, ассоциированные с листьями, не станут однородными по классовому составу. Однако это приводит к усложнению дерева: большое число ветвлений, узлов и листьев усложняет его структуру и ухудшает его интерпретируемость. Поэтому на практике размер дерева ограничивают даже за счет некоторой потери точности. Данный процесс называется упрощением деревьев решений и может быть реализован с помощью методов ранней остановки и отсечения ветвей.
Деревья решений являются жадными алгоритмами. Могут быть дихотомичными (бинарными), имеющими только два потомка в узле, и полихотомичными — имеющими более 2-х потомков в узле. Дихотомичные деревья являются более простыми в построении и интерпретации.
В настоящее время деревья решений стали одним из наиболее популярных методов классификации в интеллектуальном анализе данных и бизнес-аналитике. Поэтому они входят в состав практически любого аналитического ПО.
Разработано большое количество различных алгоритмов построения деревьев решений. Наиболее известным является семейство алгоритмов, основанное на критерии прироста информации (information gain) — ID3, C4.5, С5.0, — предложенное Россом Куинленом в начале 1980-х.
Также широкую известность приобрел алгоритм CART (Classification and Regression Tree — дерево классификации и регрессии), который, как следует из названия, позволяет решать не только задачи классификации, но и регрессии. Алгоритм предложен Лео Брейманом в 1982 г.
Широкая популярность деревьев решений обусловлена следующими их преимуществами:
- правила в них формируются практически на естественном языке, что делает объясняющую способность деревьев решений очень высокой;
- могут работать как с числовыми, так и с категориальными данными;
- требуют относительно небольшой предобработки данных, в частности, не требуют нормализации, создания фиктивных переменных, могут работать с пропусками;
- могут работать с большими объемами данных.
Вместе с тем, деревьям решений присущ ряд ограничений:
- неустойчивость — даже небольшие изменения в данных могут привести к значительным изменениям результатов классификации;
- поскольку алгоритмы построения деревьев решений являются жадными, они не гарантируют построения оптимального дерева;
- склонность к переобучению.
В настоящее время деревья решений продолжают развиваться: создаются новые алгоритмы (SHAID, MARS, Random Forest) и их модификации, изучаются проблемы построения ансамблей моделей на основе деревьев решений.
Деревья решений становятся важным инструментом управления бизнес-процессами и поддержки принятия решений. Общие принципы работы и области применения описаны в статье «Деревья решений: общие принципы».
Источник