Классификатор на базе деревьев решений

Деревья решений рассматривались ранее  на примере построения модели поведения пользователя исходя из записей в протоколах сервера. Отличительной особенностью деревьев решений является исключительная простота интерпретации. На рис. 12.1 показан пример дерева:

Рис. 12.1. Пример дерева решений

Из рисунка понятно, что делает дерево решений, сталкиваясь с задачей классификации нового образца. Начиная с корня, для образца проверяется условие, хранящееся в узле. Если образец удовлетворяет условию, мы переходим по ветви «Да», иначе – по ветви «Нет». Процесс повторяется, пока не будет достигнут листовый узел, который и соответствует спрогнозированной категории.

Обучение

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

Таблица 12.3. Данные о фруктах

Диаметр

Цвет

Фрукт

4

Красный

Яблоко

4

Зеленый

Яблоко

1

Красный

Вишня

1

Зеленый

Виноград

5

Красный

Яблоко

Разбить набор данных можно по любой из двух переменных: диаметр или цвет – и в обоих случаях будет создан корень дерева. На первом шаге мы должны попробовать обе переменные и решить, какая дает лучшее разбиение. При разбиении по цвету получаются результаты, показанные в табл. 12.4.

Таблица 12.4. Разбиение данных о фруктах по цвету

Красный

Зеленый

Яблоко

Яблоко

Вишня

Виноград

Яблоко

 

Данные все еще перемешаны. Если же провести разбиение набора по диаметру (меньше 4 дюймов и больше или равен 4 дюймам), то результат (табл. 12.5) окажется гораздо более понятным; данные в левом столбце будем далее называть поднабором 1, а в правом – поднабором 2.

Таблица 12.5. Разбиение данных о фруктах по диаметру

Диаметр < 4 дюймов

Диаметр > 4 дюймов

Вишня

Яблоко

Виноград

Яблоко

Это намного лучше, потому что в поднабор 1 попали все яблоки (apple) из исходного набора. В данном примере оптимальная переменная видна сразу, но в больших наборах данных столь очевидное разбиение бывает далеко не всегда. Ранее  было введено понятие энтропии (меры беспорядочности множества) для измерения качества разбиения:

•          p(i) = частота вхождения = количество вхождений / количество строк

•          Энтропия = сумма p(i) x log(p(i)) по всем результатам

Если у множества низкая энтропия, то оно близко к однородному, а значение 0 означает, что все элементы множества одинаковы. Энтропия поднабора 2 (диаметр > 4) в табл. 12.5 равна 0. Энтропии обоих наборов используются для вычисления информационного выигрыша:

•          вес 1 = размер поднабора 1 / размер исходного набора

•          вес 2 = размер поднабора 2 / размер исходного набора

•          выигрыш = энтропия(начальная) – вес 1 x энтропия(поднабор 1) – – вес 2 x энтропия(поднабор 2)

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

Рис. 12.2. Корневой узел дерева решений для набора данных о фруктах

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

Использование классификатора на основе дерева решений

Ранее  данные для обучения деревьев решений были представлены в виде списка списков. В каждом внутреннем списке хранится набор значений, причем последним идет категория. Набор данных о фруктах будет выглядеть следующим образом: >>> fruit=[[4,’red’,’apple’], … [4,’green’,’apple’],

[1,’red’,’cherry’], [1,’green’,’grape’], [5,’red’,’apple’]]

Теперь можно обучить дерево решений и использовать его для классификации новых образцов: >>> import treepredict >>> tree=treepredict.buildtree(fruit) >>> treepredict.classify([2,’red’],tree) {‘cherry’: 1}

>>> treepredict.classify([5,’red’],tree)

{‘apple’: 3}

>>> treepredict.classify([1,’green’],tree)

{‘grape’: 1}

>>> treepredict.classify([120,’red’],tree)

{‘apple’: 3}

Очевидно, что предмет шириной 10 футов красного цвета яблоком (apple) не является, но дерево решений знает только о том, что ему предъявили. Чтобы понять, как дерево принимает решение, можно его распечатать или представить в графическом виде: >>> treepredict.printtree(tree) 0:4?

T-> {‘apple’: 3} F-> 1:green? T-> {‘grape’: 1} F-> {‘cherry’: 1}

Сильные и слабые стороны

Бросающееся в глаза достоинство деревьев решений – простота интерпретации обученной модели и то, как хорошо алгоритм помещает наиболее важные факторы ближе к корню дерева. Это означает, что дерево решений полезно не только для классификации, но и для интерпретации результатов. Как и в случае байесовского классификатора, можно «заглянуть под капот» и понять, почему получился именно такой, а не иной результат. Это может облегчить принятие решений вне процесса классификации. Например, какие пользователи станут платными клиентами; наличие дерева решений, показывающего, какие переменные наиболее существенны для разбиения данных, помогает при планировании рекламной кампании или принятии решения о том, какие данные собирать.

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

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

Основное преимущество деревьев решений по сравнению с байесовским классификатором – способность легко справляться с взаимозависимыми переменными. Антиспамный фильтр, построенный на базе дерева решений, легко определит, что слова online и pharmacy (аптека) по отдельности нормальные, но при употреблении вместе являются индикатором спама.

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100