Алгоритмы построения деревьев решений
При построении дерева на каждом внутреннем узле находят условие, разделяющее ассоциированное с этим узлом множество на подмножества. Конкретное содержание условия определяется выбранным атрибутом. Общее правило для выбора атрибута: выбранный атрибут должен разбивать исходное множество на подмножества, состоящие из объектов одного класса или классы, максимально приближены к этому. Другими словами, количество объектов из других классов (примесей) в каждом подмножестве должно быть минимальным.
Известно значительное число алгоритмов, реализующих деревья решений. Наибольшее распространение получили два алгоритма:
§ алгоритм CART (Classification and Regression Tree), реализующий построение бинарного дерева решений для дихотомической классификационной модели. Все узлы дерева при разбиении имеет двух потомков. В алгоритме используется теоретико-информационный критерий оценки качества разбиения. С применением алгоритма, решаются задачи классификации и регрессии;
§ алгоритм C4.5 ( Iterative Dichotomizer), реализующий построение дерева решений, в котором количество потомков у каждого узла не ограничено. В алгоритме используется статистический критерий оценки качества разбиения. Алгоритм не работает с непрерывным множеством значений целевой функции и поэтому применяется только для решения задач классификации.
Алгоритм построения бинарного дерева CART предложен Л. Брейманом и представляет собой дихотомическую классификационную модель. В алгоритме CART используется индекс Gini (предложен итальянским экономистом Corrado Gini). В соответствие с индексом Gini «расстояние» между распределениями классов в узле оценивается в следующем виде:
|
|
|
,
где 
– текущий узел; 
– вероятность (частота) класса 
в узле .
В алгоритме C4.5 для выбора наиболее подходящего атрибута разбиения, предлагается следующий критерий:
, (1)
где, 
– энтропия исходного множества 
, 
– энтропия подмножеств, полученных при разбиении исходного множества 
по условию. Энтропия подмножеств объектов 
, определяется выражением:
Окончательно выбирается атрибут, дающий максимальное значение по критерию(1). Впервые эта мера была предложена Р. Куинленом в разработанном им алгоритме ID3. Кроме вышеупомянутого алгоритма C4.5, есть еще целый класс алгоритмов, используют этот критерий 
. В SQL Server Data Mining используется алгоритм Microsoft Decision Trees.
Для остановки работы алгоритма предложены различные правила. В правилах на основе статистических методов остановка выполняется оценка целесообразности дальнейшего разбиения. Это правило экономит время обучения, но снижает точность классификационных моделей. В правилах на основе ограничения глубины дерева остановка алгоритма осуществляется, если глубина построенного дерева превышает заданное значение. Разбиение объектов на классы должно быть нетривиальным и определённые узлы должны содержать примеры в количестве не меньше заданного количества по условию задачи.
|
|
|
Краткие итоги
§ Задачи классификации и регрессии связаны с определением значений зависимой переменной объекта по значениям независимых переменных, характеризующих объект.
§ Посредством математической функции описывают зависимость переменной от независимой переменной. При этом объекты классификации и регрессии рассматриваются как точки в 
– пространстве.
§ Деревья решений являются способом представления правил в иерархической и последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение. Под правилом понимается логическая конструкция «если …, то …».
§ Построение деревьев решений реализуется на основе методики «разделяй и властвуй», предполагающей рекурсивное разбиение множества объектов из обучающей выборки на классы (подмножества) объектов.
§ Компанией Microsoft предложен популярный алгоритм деревьев решений (Microsoft Decision Trees), который используется при решении задач классификации, регрессионного анализа и анализа взаимосвязей.
|
|
|
Контрольные вопросы
1. Задача классификации решается в случае, если зависимая переменная принимает значения из:
а) конечного множества;
б) бесконечного множества;
в) счётного множества;
г) континуума.
2. В деревьях решений в качестве листа рассматривается:
а) внутренняя вершина дерева или узел проверки;
б) конечный узел дерева или узел решения;
в) отсечённые при построении дерева узлы решений;
г) узел дерева решений, не содержащий объектов.
3. В алгоритме CART (Classification and Regression Tree), для оценки качества разбиения объектов в процессе обучения используется:
а) статистический критерий;
б) отношение правильно классифицированных объектов к общему количеству объектов;
в) статистический, и теоретико-информационный критерий.
г) теоретико-информационный критерий.
4. Правило классификации может быть представлено в виде:
а) наборами параметров, определяющих принадлежность объекта к одному из классов заданного множества;
б) классификационного правила: если (условие), то (заключение);
в) аналитического выражения, определяющего функциональную зависимость между зависимой переменной и независимыми переменными;
|
|
|
г) математической функции, выражающей отношение зависимой переменной от независимых переменных;
5. Условие разделения объектов в узле дерева решений должно отвечать требованию:
а) формирования подмножеств из объектов одного класса или с минимальным количеством объектов из других классов;
б) формирования подмножеств с равным количеством объектов;
в) формирования подмножеств,
г) формирования подмножества
Литература
1. Барсегян А.А. Методы и модели анализа данных: OLAP и Data Mining / Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. – СПб.: БХВ-Петербург, 2004. – 336 с.
2. Microsoft SQL Server 2008: Data mining – интеллектуальный анализ данных. Пер. с англ. / Дж. Макленнен, Чж. Танг, Б. Криват. – БХВ-Петербург. 2009. – 720 с.
3. Ларсон Б. Разработка бизнес-аналитики в SQL Server 2005. – СПб.: Питер, 2008. – 684 с.
4. Паклин Н.Б., Орешков В.И. Бизнес-аналитика: от данных к знаниям. – СПб.: Питер, 2009 год. – 624 с.
5. Новиков Ф.А. Дискретная математика для программистов. – Спб.: Питер, 2001. – 304 с.
Дата добавления: 2018-10-26; просмотров: 492; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!