[Назад]

7.Деревья решений


7.1.   Общие сведения

"Деревья решений" (классификации) – это метод, позволяющий предсказывать принадлежность наблюдений или объектов к тому или иному классу категориальной зависимой переменной в соответствии со значениями одной или нескольких предикторных переменных. Иерархическое строение "дерева классификации" – одно из наиболее важных его свойств. "Стволом дерева" является проблема или ситуация, требующая решения. "Вершиной дерева" являются цели или ценности, которыми руководствуется человек, принимающий решение.

Первые идеи создания деревьев решений восходят к работам Ховленда (Hoveland) и Ханта (Hunt) конца 50-х годов XX века. Однако, основополагающей работой, давшей импульс развитию этого направления, явилась книга Ханта (Hunt, E.B.), Мэрина (Marin J.) и Стоуна (Stone P.J) "Experiments in Induction", увидевшая свет в 1966 г.

 

7.2.   Терминология

Введем основные понятия из теории "деревьев решений" (табл. 7.1).

 

Т а б л и ц а 7.1

 

Название

Описание

Объект

Пример, шаблон, наблюдение

Атрибут

Признак, независимая переменная, свойство

Метка класса

Зависимая переменная, целевая переменная, признак, определяющий класс объекта

Узел

Внутренний узел дерева, узел проверки

Лист

Конечный узел дерева, узел решения

Проверка

Условие в узле

 

 

7.3.   Что такое "дерево решений" и типы решаемых задач?

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

Под правилом понимается логическая конструкция, представленная в виде "если … то …" (рис 7.1).

Мы используем алгоритм "дерево решений" для ответа на вопрос: "Кто, возможно, купит автомашину Buick?" При каждом расщеплении дерева клиенты делятся на две группы. В данном примере первое расщепление происходит на основе возраста, второе – на основе пола. Отметим, что по мере того, как Data Mining "вкапывается" все глубже и глубже в данные, он создает все больше "отфильтрованных" (refined) сегментов однородных групп клиентов с похожим поведением.

Каждый конечный узел предоставляет "правило" (rule), которое описывает группу клиентов. Чем глубже вы спускаетесь по дереву, добавляя характеристики "правилу", тем выше уровень "уверенности" (confidence) в точности предсказания. Например, правило нижнего левого узла дерева таково: "Родители владеют автомобилем Buick, Мужчина, возраст более 45 лет" ("Parents owned Buick, Male, and Age is over 45").  Уровнь уверенности, что клиент с этим профилем купит Buick – 92%. Обладая такой информацией, компании могут взаимодействовать с клиентами индивидуально.

 

Рис. 7.1

 

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

·       описание данных: "деревья решений" позволяют хранить информацию о данных в компактной форме, вместо них мы можем хранить дерево решений, которое содержит точное описание объектов;

·       классификация: "деревья решений" отлично справляются с задачами классификации, т.е. отнесения объектов к одному из заранее известных классов. Целевая переменная должна иметь дискретные значения;

·       регрессия: если целевая переменная имеет непрерывные значения, "деревья решений" позволяют установить зависимость целевой переменной от независимых (входных) переменных. Например, к этому классу относятся задачи численного прогнозирования (предсказания значений целевой переменной).

7.4.   Как построить "дерево решений" ?

На сегодняшний день существует значительное число алгоритмов, реализующих деревья решений CART, C4.5, NewId, ITrule, CHAID, CN2 и др. Но наибольшее распространение и популярность получили следующие два:

·       CART (Classification and Regression Tree) – это алгоритм построения бинарного "дерева решений" – дихотомической классификационной модели. Каждый узел дерева при разбиении имеет только двух потомков. Как видно из названия алгоритма, он решает задачи классификации и регрессии;

·       C4.5 – это алгоритм построения "дерева решений", количество потомков у узла не ограничено. Не умеет работать с непрерывным целевым полем, поэтому решает только задачи классификации.

В пакете Statistic в модуле "Деревья классификации" реализованы три метода:

·       дискриминантное одномерное ветвление по категориальным и порядковым предикторам;

·       дискриминантное многомерное ветвление по линейным комбинациям порядковых предикторов;

·       одномерное ветвление по методу CART.

Первые два представляют собой адаптацию соответствующих алгоритмов пакета QUEST (Quick, Unbiased, Efficient Statistical Trees). QUEST – это программа деревьев классификации, разработанная Loh и Shih (1997), в которой используются улучшенные варианты метода рекурсивного квадратичного дискриминантного анализа и которая содержит ряд новых средств для повышения надежности и эффективности "деревьев классификации", которые она строит. Алгоритмы пакета QUEST довольно сложны.

В модуле Деревья классификации имеется другой, концептуально более простой, подход. Реализованный здесь алгоритм Одномерного ветвления по методу CART является адаптацией алгоритмов пакета CART. CART (Classification And Regression Trees) – это программа, которая при построении "дерева" осуществляет полный перебор всех возможных вариантов одномерного ветвления.

          Метод  CART применяется для категоризующих (обычно двухуровневых) и порядковых предикторных переменных. Для категоризующей предикторной переменной, принимающей в данном узле k значений, имеется ровно 2(k-1) –1 вариантов разбиения множества ее значений на две части. Для порядкового предиктора, имеющего в данном узле k различных уровней, имеется k–1 точек, разделяющих разные уровни. Мы видим, что количество различных вариантов ветвления, которые необходимо просмотреть, будет очень большим: если в задаче много предикторов, то у них много уровней значений, а значит в дереве много терминальных вершин.

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

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

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

Широкая сфера применения "деревьев классификации" делает их весьма привлекательным инструментом анализа данных, но не следует полагать, что его рекомендуется использовать вместо традиционных методов статистики. Напротив, если выполнены более строгие теоретические предположения, налагаемые традиционными методами, и выборочное распределение обладает некоторыми специальными свойствами, то более результативным будет использование именно традиционных методов. Однако, как метод разведочного анализа или последнее средство, в случае отказа всех традиционных методов, "деревья классификации", по мнению многих исследователей, не знают себе равных.

Дополнительная информация по методам анализа, добычи, визуализации и прогнозирования данных содержится на Портале StatSoft (http://www.statsoft.ru/home/portal/default.asp).

 

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

Основными достоинствами метода "деревья решений являются":

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

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

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

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

·       высокая точность прогноза, сопоставимая с другими методами (статистика, нейронные сети);

·       построение непараметрических моделей.

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

 

7.4.2. Области применения деревьев решений

"Деревья решений" являются прекрасным инструментом в системах поддержки принятия решений, интеллектуального анализа данных (Data Mining). В состав многих пакетов, предназначенных для интеллектуального анализа данных, уже включены методы построения "деревьев решений". В областях, где высока цена ошибки, они послужат отличным подспорьем аналитика или руководителя

"Деревья решений" успешно применяются для решения практических задач в:

·       банковском деле при оценке кредитоспособности клиентов банка при выдаче кредитов;

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

·       медицине при  диагностике различных заболеваний;

·       молекулярной биологии, проводя анализ строения аминокислот.

Это далеко не полный список областей, где можно использовать "деревья решений".

 

7.5.   STATISTICA. Проверка результатов контрольного примера в Classification Tree

Предположим, что у вас имеются данные о координатах – Долготе (Longitude) и Широте (Latitude) – для 37 циклонов (табл. 7.2), достигающих силы урагана, по двум классификациям циклонов – Baro и Trop. Приведенный ниже модельный набор данных использовался для целей иллюстрации в работе Elsner, Lehmiller, Kimberlain (1996), авторы которой исследовали различия между бароклинными и тропическими циклонами в Северной Атлантике. 

 

Т а б л и ц а 7.2

 

N/N

LONGITUD

LATITUDE

   CLASS

№/№

LONGITUD

LATITUDE

  CLASS

1

2

3

4

5

6

7

8

1

59.00

17.00

BARO

21

66.00

14.00

TROP

2

59.50

21.00

BARO

22

66.00

17.00

TROP

3

60.00

12.00

BARO

23

66.50

17.00

TROP

4

60.50

16.00

BARO

24

66.50

18.00

TROP

5

61.00

13.00

BARO

25

66.50

21.00

TROP

6

61.00

15.00

BARO

26

67.00

14.00

TROP

7

61.50

17.00

BARO

27

67.50

18.00

TROP

8

61.50

19.00

BARO

28

68.00

14.00

BARO

9

62.00

14.00

BARO

29

68.50

18.00

BARO

10

63.00

15.00

TROP

30

69.00

13.00

BARO

11

63.50

19.00

TROP

31

69.00

15.00

BARO

12

64.00

12.00

TROP

32

69.50

17.00

BARO

13

64.50

16.00

TROP

33

69.50

19.00

BARO

14

65.00

12.00

TROP

34

70.00

12.00

BARO

15

65.00

15.00

TROP

35

70.50

16.00

BARO

16

65.00

17.00

TROP

36

71.00

17.00

BARO

17

65.50

16.00

TROP

37

71.50

21.00

BARO

18

65.50

19.00

TROP

 

 

 

 

19

65.50

21.00

TROP

 

 

 

 

20

66.00

13.00

TROP

 

 

 

 

·       Откроем модуль Classification Tree.

·       Введем или откроем файл barotrop.sta с исходными данными.

·       Выполним команду Analysis/Resume Analysis, на экране появится окно, изображенное на рис. 7.2

 

 

Рис. 7.2

 

·       В разделе Split selection method выберем метод CART (C&RT-style);

·       Нажмите кнопку Variables и выделите переменные, как показано на рисунке и нажмите OK. Появится окно (рис. 7.3).

 

 

Рис. 7.3

 

·       В разделе Codes for variables нажмите кнопку Dep. Variable, а в появившемся окне – соответственно кнопку All, а затем OK (рис. 7.4).

 

 

Рис. 7.4

 

·       В итоге должны получить следующее окно (рис. 7.5).

 

 

Рис. 7.5

·       Нажав OK, получим окно (рис. 7.6).

 

 

Рис. 7.6

·       В открытом диалоговом окне поочередно будем нажимать кнопки для  вывода результатов и анализа данных: (OK (Tree Graph), Tree structure, Importance) и получать соответствующие картинки.

"Дерево классификации" для переменной Class, использующее опцию Полный перебор деревьев с одномерным ветвлением по методу CART, сумело правильно классифицировать все 37 циклонов. "Граф дерева" для этого "дерева классификации" показан на рис. 7.7.

В заголовке "графа" приведена общая информация, согласно которой полученное "дерево классификации" имеет 2 ветвления и 3 терминальные вершины. Терминальные вершины (или, как их иногда называют, листья) – это узлы "дерева", начиная с которых никакие решения больше не принимаются. На рисунке терминальные вершины показаны красными пунктирными линиями, а остальные – так называемые решающие вершины или вершины ветвления – сплошными черными линиями. Началом "дерева" считается самая верхняя решающая вершина, которую иногда также называют корнем "дерева". На рисунке она расположена в левом верхнем углу и помечена цифрой 1. Первоначально все 37 циклонов приписываются к этой корневой вершине и предварительно классифицируются как Baro - на это указывает надпись Baro в правом верхнем углу вершины. Класс Baro был выбран для начальной классификации потому, что число циклонов Baro немного больше, чем циклонов Trop (см. гистограмму, изображенную внутри корневой вершины). В левом верхнем углу "графа" имеется надпись – легенда, указывающая, какие столбики гистограммы вершины соответствуют циклонам Baro и Trop.

 

 

Рис. 7.7

Корневая вершина разветвляется на две новых вершины. Под корневой вершиной имеется текст, описывающий схему данного ветвления. Из него следует, что циклоны, имеющие значение Долготы, меньшее или равное 67.75, отнесены к вершине номер 2 и предположительно классифицированы как Trop, а циклоны с Долготой, большей 67.75, приписаны к вершине 3 и классифицированы как Baro. Числа 27 и 10 над вершинами 2 и 3 соответственно обозначают число наблюдений, попавших в эти две дочерние вершины из родительской корневой вершины. Затем точно так же разветвляется вершина 2. В результате 9 циклонов со значениями Долготы меньшими или равными 62.5, приписываются к вершине 4 и классифицируются как Baro, а остальные 18 циклонов с Долготой, большей 62.5, – к вершине 5 и классифицируются как Trop.

На "графе дерева" вся эта информация представлена в простом, удобном для восприятия виде. Если теперь мы посмотрим на гистограммы терминальных вершин "дерева", расположенных в нижней строке, то увидим, что "дерево классификации" сумело абсолютно правильно расклассифицировать циклоны. Каждая из терминальных вершин "чистая", т.е. не содержит неправильно классифицированных наблюдений. Вся информация, содержащаяся в "графе дерева", продублирована в таблице результатов Структура дерева, которая приведена на рис. 7.8.

 

 

Рис. 7.8

Обратите внимание на то, что в этой таблице результатов вершины с 3-й по 5-ю помечены как терминальные, так как в них не происходит ветвления. Обратите также внимание на знаки постоянных ветвления, например, -67.75 для вершины 1.

Если делаются одномерные ветвления, то каждой предикторной переменной можно приписать ранг по шкале от 0 до 100 в зависимости от степени ее влияния на отклик зависимой переменной. В нашем примере очевидно, что Долгота (Longitude) имеет большую важность, а Широта (Latitude) – относительно небольшую (рис. 7.9).

 

 

Рис. 7.9

7.6.        Индивидуальные задания

Выполните задания 1 и 2, указанные в  п. 5.4, с использованием метода "деревья решений". Сделайте сравнительный анализ результатов, полученных методами  "деревья решений" и дискриминантного анализа.

[Назад]