Методы построения дерева решений

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

Сокращение дерева или  отсечение ветвей. Решением проблемы слишком ветвистого дерева является его сокращение путем отсечения  некоторых ветвей.

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

Точность распознавания  рассчитывается как отношение объектов, правильно классифицированных в  процессе обучения, к общему количеству объектов набора данных, которые принимали  участие в обучении.

Ошибка рассчитывается как  отношение объектов, неправильно  классифицированных в процессе обучения, к общему количеству объектов набора данных, которые принимали участие  в обучении.

Отсечение ветвей или замену некоторых ветвей поддеревом следует  проводить там, где эта процедура  не приводит к возрастанию ошибки. Процесс проходит снизу вверх, т.е. является восходящим. Это более популярная процедура, чем использование правил остановки. Деревья, получаемые после  отсечения некоторых ветвей, называют усеченными.

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

Ни один алгоритм построения дерева нельзя априори считать наилучшим  или совершенным, подтверждение  целесообразности использования конкретного  алгоритма должно быть проверено  и подтверждено экспериментом.[3,с.495]

         2. Методы построения дерева решений

 

2.1 Методика "Разделяй  и властвуй"

 

Методика основана на рекурсивном  разбиении множества объектов из обучающей выборки на подмножества, содержащие объекты, относящиеся к  одинаковым классам.

 Сперва выбирается независимая переменная, которая помещается в корень дерева.

 Из вершины строятся  ветви, соответствующие всем возможным  значениям выбранной независимой  переменной.

 Множество объектов  из обучающей выборки разбивается  на несколько подмножеств в  соответствии со значением выбранной  независимой переменной.

 Таким образом, в  каждом подмножестве будут находиться  объекты, у которых значение  выбранной независимой переменной  будет одно и то же.

 Относительно обучающей  выборки T и множества классов  C возможны три ситуации:

 множество Т содержит один или более объектов, относящихся к одному классу cr. Тогда дерево решений для T - это лист, определяющий класс cr;

 множество Т не содержит ни одного объекта (пустое множество). Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества, отличного от Т, например из множества, ассоциированного с родителем;

 Множество Т содержит объекты, относящиеся к разным классам. В этом случае следует разбить множество Т на некоторые подмножества. Для этого выбирается одна из независимых переменных xh, имеющая два и более отличных друг от друга значений ; Множество Т разбивается на подмножества T1,T2,...,Tn, где каждое подмножество Ti содержит все объекты, у которых значение выбранной зависимой переменной равно . Далее процесс продолжается рекурсивно для каждого подмножества до тех пор, пока значение зависимой переменной во вновь образованном подмножестве не будет одинаковым (когда объекты принадлежат одному классу). В этом случае процесс для данной ветви дерева прекращается.

При использовании данной методики построение дерева решений  будет происходить сверху вниз. Большинство  алгоритмов, которые её используют, являются "жадными алгоритмами". Это значит, что если один раз  переменная была выбрана и по ней было произведено разбиение, то алгоритм не может вернуться назад и выбрать другую переменную, которая дала бы лучшее разбиение.

 Вопрос в том, какую  зависимую переменную выбрать  для начального разбиения. От  этого целиком зависит качество  получившегося дерева.

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

 Другой проблемой при  построении дерева является проблема  остановки его разбиения. Методы  её решения: 

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

 Ограничение глубины  дерева. Нужно остановить дальнейшее  построение, если разбиение ведёт  к дереву с глубиной, превышающей  заданное значение.

 Разбиение должно быть  нетривиальным, т.е. получившиеся  в результате узлы должны содержать  не менее заданного количества объектов.

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

Построить все возможные  варианты разбиения и выбрать  наилучший проблематично при наличии большого числа независимых переменных или при большом числе возможных классов.[8,с. 672]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.2 Алгоритм C4.5

 

Представляет собой усовершенствованный  вариант алгоритма ID3. Среди улучшений  стоит отметить следующие:

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

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

Один из недостатков алгоритма ID3 является то, что он некорректно  работает с атрибутами, имеющими уникальные значения для всех объектов из обучающей  выборки. Для таких объектов информационная энтропия равна нулю и никаких  новых данных от построенного дерева по данной зависимой переменной получить не удасться. Поскольку получаемые после разбиения подмножества буду содержать по одному объекту.

 Алгоритм C4.5 решает эту  проблему путём введения нормализации.

 Оценивается не количество  объектов того или иного класса  после разбиения, а число подмножеств  и их мощность (число элементов).

 Выражение  оценивает  потенциальную информацию, получаемую  при разбиении множества Т на m подмножеств.

 Критерием выбора переменной  для разбиения будет выражение:  или .

 При условии, что  имеется k классов и n - число объектов в обучающей выборке и одновременно количество значений переменных, тогда числитель максимально будет равен log2k, а знаменатель максимально равен log2n. Если предположить, что количество объектов знаведомо больше количества классов, то знаменатель растёт быстрее, чем числитель и, соответственно, значение выражения будет небольшим.

 В обучающей выборке  могут присутствовать объекты  с пропущенными значениями атрибутов.  В этом случае их либо отбрасывают  (что влечёт за собой риск  потерять часть данных), либо применить  подход, предполагающий, что пропущенные  значения по переменной вероятностно  распределены пропорционально частоте  появления существующих значений.[9,с.80]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.3 Алгоритм покрытия

 

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

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

 Для выбора независимой  переменной и её значения, которое  разделяет множество, выполняются  следующие действия:

 Из построенного на  предыдущем этапе подмножества (для  первого этапа это вся обучающая  выборка), включающего объекты, относящиеся  к выбранному классу для каждой  независимой переменной, выбираются  все значения, встречающиеся в  этом подмножестве.

 Для каждого значения  каждой переменной подсчитывается  количество объектов, удовлетворяющих  этому условию и относящихся  к выбранному классу.

 Выбираются условия,  покрывающие наибольшее количество  объектов выбранного класса.

 Выбранное условие  является условием разбиения  подмножества на два новых. 

После построения дерева для  одного класса таким же образом строятся деревья для других классов.

Преимущества использования  деревьев решений

 быстрый процесс обучения;

 генерация правил в  областях, где эксперту трудно  формализовать свои знания;

 извлечение правил  на естественном языке; 

 интуитивно понятная  классификационная модель;

 высокая точность прогноза, сопоставимая с другими методами (статистика, нейронные сети).[6,с.352]

 

3. Практическая часть. Построение дерева решений на примере

 

Для финансирования проекта  построения нового торгового зала предпринимателю  требуется занять сроком на 1 год 150000 рублей. Банк может одолжить ему  эти деньги под 20% годовых или  вложить в дело со 100% возвратом , но под 10% годовых. Из прошлого опыта банку известно ,что 5% таких клиентов сумму не возвращают. Встает вопрос: давать ли заём?

Решение:

Максимизируем ожидаемый  в конце года чистый доход, который  представляет собой разность суммы, полученной в конце года, и. инвестированной  в его начале. Таким образом, если заем был выдан и возвращен, то чистый доход составит: Чистый доход =((150000+(150000/100%)*20%)-150000)=30000(руб.)

Таблица 1. «Чистый доход  в конце года (руб.)

Возможные исходы	Возможные решения		Вероятность
	Выдавать заём	Не выдавать заём
Заём возвращён	30000	15000	0,95
Заём не возвращён	-150000	15000	0,05
Ожидаемый чистый доход	21000	15000	-

 

Если банк решает выдать заем, то максимальный ожидаемый чистый доход равен 21000

По дереву решений:

 

 

 

 

21000

 Заём уплачен 20% годовых(-150000)

 0,95

  

  0,05

Не давать заём

 

Инвестирование  под 10% годовых

 

 

 

 

Расчёт ведётся аналогично расчёту по таблице доходов. Ожидаемый  чистый доход в кружках А и Б вычисляется следующим образом:

В кружке А:(давать заём)=(180000*0,95+0*0,5)-150000=171000-150000=21000(руб.)

В кружке Б: (не давать заём)=(165000*1,0-15000)=150000