Методы классификации и прогнозирования. Деревья решений

Технологии обработки информации. Лекция 11. Методы классификации и прогнозирования. Деревья решений к.т.н., доцент Буряченко В.В. Красноярск, 2019 Содержание 1. 2. 3. 4. 5. 6. 2 Понятие деревьев решений. Примеры деревьев. Достоинства метода деревьев решений. Критерий расщепления. Правила остановки. Алгоритмы построения деревьев решений. Деревья решений  Метод деревьев решений (decision trees) является одним из наиболее популярных методов решения задач классификации и прогнозирования. Иногда этот метод Data Mining также называют деревьями решающих правил, деревьями классификации и регрессии.  Если зависимая, т.е. целевая переменная принимает дискретные значения, при помощи метода дерева решений решается задача классификации. Если же зависимая переменная принимает непрерывные значения, то дерево решений устанавливает зависимость этой переменной от независимых переменных, т.е. решает задачу численного прогнозирования.  3 Пример дерева решений В наиболее простом виде дерево решений - это способ представления правил в иерархической, последовательной структуре. Основа такой структуры - ответы "Да" или "Нет" на ряд вопросов.  4 Элементы деревьев решений  Целью построения дерева решения является определение значения категориальной зависимой переменной.  Внутренний узел дерева является узлом проверки определенного условия. Далее идет следующий вопрос и т.д., пока не будет достигнут конечный узел дерева, являющийся узлом решения. В рассмотренном примере решается задача бинарной классификации.   5 Целесообразность выдачи кредитов клиенту База данных, на основе которой должно осуществляться прогнозирование, содержит следующие ретроспективные данные о клиентах банка, являющиеся ее атрибутами: возраст, наличие недвижимости, образование, среднемесячный доход, вернул ли клиент вовремя кредит. Задача состоит в том, чтобы на основании перечисленных выше данных (кроме последнего атрибута) определить, стоит ли выдавать кредит новому клиенту.   На этапе построения модели строится дерево классификации или создается набор неких правил. На этапе использования модели построенное дерево, или путь от его корня к одной из вершин, являющийся набором правил для конкретного клиента, используется для ответа на поставленный вопрос "Выдавать ли кредит?"   6 Целесообразность выдачи кредитов клиенту Внутренние узлы дерева являются атрибутами базы данных. Их называют прогнозирующими или атрибутами расщепления (splitting attribute).  7 Достоинства метода деревьев решений Интуитивность деревьев решений.   Классификационная модель, представленная в виде дерева решений, является интуитивной и упрощает понимание решаемой задачи. Деревья решений дают возможность извлекать правила из базы данных на естественном языке.   Пример правила: Если Возраст > 35 и Доход > 30, то выдать кредит. Алгоритм конструирования дерева решений пользователя выбора входных атрибутов. Точность моделей,    8 не требует от созданных при помощи деревьев решений, сопоставима с другими методами построения классификационных моделей Достоинства метода деревьев решений Разработан ряд масштабируемых алгоритмов,   которые могут быть использованы для построения деревьев решения на сверхбольших базах данных. Быстрый процесс обучения.   На построение классификационных моделей при помощи алгоритмов конструирования деревьев решений требуется значительно меньше времени, чем, например, на обучение нейронных сетей. Большинство алгоритмов конструирования деревьев решений имеют возможность специальной обработки пропущенных значений. Деревья решений работают и с числовыми, и с категориальными типами данных. Деревья решений, в отличие от статистических методов, строят непараметрические модели.    9 Процесс конструирования дерева решений  Рассматриваемая задача классификации относится к стратегии обучения с учителем, иногда называемого индуктивным обучением.   В этих случаях все объекты тренировочного набора данных заранее отнесены к одному из предопределенных классов. Алгоритмы конструирования деревьев решений состоят из этапов "построение" или "создание" дерева (tree building) и " сокращение " дерева (tree pruning). 10 Критерий расщепления  Процесс создания дерева происходит сверху вниз, т.е. является нисходящим.   В ходе процесса алгоритм должен найти такой критерий расщепления, иногда также называемый критерием разбиения, чтобы разбить множество на подмножества, которые бы ассоциировались с данным узлом проверки. Правило выбора атрибута: он должен разбивать исходное множество данных таким образом, чтобы объекты подмножеств, получаемых в результате этого разбиения, являлись представителями одного класса или же были максимально приближены к такому разбиению. 11 Мера энтропии  Существуют различные критерии расщепления. Наиболее известные мера энтропии и индекс Gini.  Мера информативности подпространств атрибутов, которая основывается на энтропийном подходе и известна под названием "мера информационного выигрыша" (information gain measure) - мера энтропии. 12 Индекс Gini   Другой критерий расщепления, предложенный Брейманом (Breiman) и др., реализован в алгоритме CART и называется индексом Gini.  При помощи этого индекса атрибут выбирается на основании расстояний между распределениями классов. Если дано множество T, включающее примеры из n классов, индекс Gini, т.е. gini(T), определяется по формуле: 𝑛 𝑃2𝑗 𝐺𝑖𝑛𝑖 𝑇 = 1 − 𝑗=1  где T - текущий узел, pj - вероятность класса j в узле T, n - количество классов. 13 Принципы построения деревьев    Чем больше частных случаев описано в дереве решений, тем меньшее количество объектов попадает в каждый частный случай. В процессе построения дерева, чтобы его размеры не стали чрезмерно большими, используют специальные процедуры, которые позволяют создавать оптимальные деревья, так называемые деревья "подходящих размеров". Дерево должно использовать информацию, улучшающую качество модели, и игнорировать ту информацию, которая ее не улучшает. 14 Оптимальный размер дерева  Существует две возможные стратегии.     Первая состоит в наращивании дерева до определенного размера в соответствии с параметрами, заданными пользователем. Определение этих параметров может основываться на опыте и интуиции аналитика, а также на некоторых "диагностических сообщениях" системы, конструирующей дерево решений. Вторая стратегия состоит в использовании набора процедур, определяющих "подходящий размер" дерева, они разработаны Бриманом, Куилендом и др. Процедуры, которые используют для предотвращения создания чрезмерно больших деревьев, включают:   15 сокращение дерева путем отсечения ветвей; использование правил остановки обучения. Правила остановки построения дерева  Один из вариантов правил остановки - "ранняя остановка" (prepruning),   Второй вариант остановки обучения - ограничение глубины дерева.   она определяет целесообразность разбиения узла. В этом случае построение заканчивается, если достигнута заданная глубина. Третий вариант - задание минимального количества примеров, которые будут содержаться в конечных узлах дерева. 16 Сокращение дерева или отсечение ветвей   Решением проблемы слишком ветвистого дерева является его сокращение путем отсечения (pruning) некоторых ветвей. Качество классификационной модели, построенной при помощи дерева решений, характеризуется двумя основными признаками:    Точность распознавания рассчитывается как отношение объектов, правильно классифицированных в процессе обучения, к общему количеству объектов набора данных, которые принимали участие в обучении. Ошибка рассчитывается как отношение объектов, неправильно классифицированных в процессе обучения, к общему количеству объектов набора данных, которые принимали участие в обучении. Отсечение ветвей или замену некоторых ветвей поддеревом следует проводить там, где эта процедура не приводит к возрастанию ошибки. Процесс проходит снизу вверх, т.е. является восходящим. 17 Алгоритмы построения деревьев решений          На сегодняшний день существует большое число алгоритмов, реализующих деревья решений: CART, C4.5, CHAID, CN2, NewId, ITrule, Sprint, и др. 18 Алгоритм CART       Алгоритм CART (Classification and Regression Tree), как видно из названия, решает задачи классификации и регрессии. Алгоритм CART предназначен для построения бинарного дерева решений. функция оценки качества разбиения; механизм отсечения дерева; алгоритм обработки пропущенных значений; построение деревьев регрессии. 19 Алгоритм C4.5  Алгоритм C4.5 строит дерево количеством ветвей у узла.  Каждая запись набора данных должна быть ассоциирована с одним из предопределенных классов. Классы должны быть дискретными. Каждый пример должен однозначно относиться к одному из классов. Количество классов должно быть значительно меньше количества записей в исследуемом наборе данных.   20 решений с неограниченным Алгоритмы построения деревьев решений Алгоритмы построения деревьев решений различаются следующими характеристиками:  вид расщепления - бинарное (binary), множественное (multi-way);  критерии расщепления - энтропия, Gini, другие;  возможность обработки пропущенных значений;  процедура сокращения ветвей или отсечения;  возможности извлечения правил из деревьев.  масштабируемость алгоритма. 21