Методы data mining деревья решений

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

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

Идею построения деревьев решений из множества T, впервые высказанную Хантом, приведем по Р. Куинлену (R. Quinlan).

Пусть через 1, C₂, . C_k> обозначены классы(значения метки класса), тогда существуют 3 ситуации:

1. множество T содержит один или более примеров, относящихся к одному классу C_k. Тогда дерево решений для Т – это лист, определяющий класс C_k;
2. множество T не содержит ни одного примера, т.е. пустое множество. Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества отличного от T, скажем, из множества, ассоциированного с родителем;
3. множество T содержит примеры, относящиеся к разным классам. В этом случае следует разбить множество T на некоторые подмножества. Для этого выбирается один из признаков, имеющий два и более отличных друг от друга значений O₁, O₂, . O_n. T разбивается на подмножества T₁, T₂, . T_n, где каждое подмножество T_i содержит все примеры, имеющие значение O_i для выбранного признака. Это процедура будет рекурсивно продолжаться до тех пор, пока конечное множество не будет состоять из примеров, относящихся к одному и тому же классу.

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

Поскольку все объекты были заранее отнесены к известным нам классам, такой процесс построения дерева решений называется обучением с учителем (supervised learning). Процесс обучения также называют индуктивным обучением или индукцией деревьев (tree induction).

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

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

Большинство из известных алгоритмов являются «жадными алгоритмами». Если один раз был выбран атрибут, и по нему было произведено разбиение на подмножества, то алгоритм не может вернуться назад и выбрать другой атрибут, который дал бы лучшее разбиение. И поэтому на этапе построения нельзя сказать даст ли выбранный атрибут, в конечном итоге, оптимальное разбиение.

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

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

Источник

Введение в DataMining: Построение деревьев решений (часть III)

В предыдущей части данной статьи мы рассказали об алгоритме кластеризации и рассмотрели его применение на примере построения антиспамового фильтра с помощью реализации этого алгоритма, содержащейся в составе аналитических служб Microsoft SQL Server 2000. В завершающей части статьи речь пойдет о применении другого алгоритма Data Mining, носящего название Decision Trees (построение деревьев решений).

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

Что такое деревья решений

Под термином «деревья решений» подразумевается семейство алгоритмов, основанных на создании иерархической структуры, которая базируется на ответе «Да» или «Нет» на набор вопросов. Такие алгоритмы весьма популярны: в настоящее время они реализованы практически во всех коммерческих средствах Data Mining.

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

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

Действие алгоритмов построения деревьев решений базируется на применении методов регрессионного и корреляционного анализа. Один из самых популярных алгоритмов этого семейства — CART (Classification and Regression Trees), основанный на разделении данных в ветви дерева на две дочерние ветви; при этом дальнейшее разделение той или иной ветви зависит от того, много ли исходных данных описывает данная ветвь. Некоторые другие сходные алгоритмы позволяют разделить ветвь на большее количество дочерних ветвей. В данном случае разделение производится на основе наиболее высокого для описываемых ветвью данных коэффициента корреляции между параметром, согласно которому происходит разделение, и параметром, который в дальнейшем должен быть предсказан.

А теперь рассмотрим пример реализации подобного дерева с помощью алгоритма Microsoft Decision Trees. Для этого нам потребуется Microsoft SQL Server 2000 (Enterprise Edition, Standard Edition или Personal Edition) с установленными аналитическими службами, причем можно использовать и ознакомительную версию.

Постановка задачи

Итак, рассмотрим задачу определения того, является ли ядовитым найденный гриб (такой пример был рассмотрен в одной из публикаций [1] и показался нам весьма удачным). Действие нашего «определителя грибов», как и других инструментов предсказания с помощью Data Mining, будет состоять из двух процессов: обучение модели (которое выполняется однократно и требует относительно много времени) и принятие решения о том, относится ли конкретный гриб к категории съедобных (что происходит неоднократно).

В качестве исходных данных для обучения модели мы воспользуемся набором данных о более чем 8 тыс. грибов, доступных в виде файла в формате CSV по адресу http://www.ics.uci.edu/~mlearn/MLRepository.html (мы уже пользовались другим набором данных с этого сайта), который содержит таблицу, где имеется колонка Edibility с двумя возможными значениями (Еdible — съедобный и poisonous — ядовитый). Для упрощения работы с этим набором данных переведем его на русский язык и импортируем в какую-нибудь СУБД, например в Access или в Microsoft SQL Server. Создадим в этой таблице автоматически заполняемое целочисленное ключевое поле — оно потребуется при создании модели Data Mining на основе этих данных (рис. 1).

Теперь можно приступить к созданию самого дерева решений.

Создание дерева решений

Для создания дерева решений следует запустить инструмент администрирования аналитических служб Microsoft SQL Server Analysis Manager. С помощью Analysis Manager можно создать новую многомерную базу данных (или воспользоваться той, что была создана нами при рассмотрении предыдущего примера) и описать там доступ к источнику исходных данных (в нашем случае — к базе данных Access; рис. 2).

Далее следует выбрать соответствующую дочернюю ветвь Mining Models, из ее контекстного меню выбрать пункт New Mining Model, а затем ответить на вопросы мастера построения моделей Data Mining. В частности, следует указать, что для построения модели используются реляционные данные, что применяется алгоритм Microsoft Decision Trees и что данные для анализа расположены в одной таблице (при этом нужно выбрать ее имя). Далее в таблице необходимо выбрать поле, являющееся уникальным идентификатором каждой записи в наборе данных (case key), и наконец, поля, значения которых в дальнейшем будут предсказываться (в нашем случае — «съедобность»), а также поля, значения которых будут использоваться в качестве параметров для построения ветвей дерева. В нашем примере мы выбрали все 22 поля, присутствующие в исходных данных (рис. 3).

Завершить создание модели можно в редакторе Relational Mining Model Editor. Затем следует произвести обучение модели с помощью выбора пункта меню Tools®Process Mining Model.

Результаты

Созданное дерево решений можно увидеть, выбрав пункт View®Content меню редактора Relational Mining Model Editor или пункт Browse из контекстного меню модели в приложении Аnalysis Manager (рис. 4).

• если запах гриба миндальный или анисовый, то гриб съедобный;
• если запах другой, то гриб ядовитый;
• если запаха нет, то вопрос требует дальнейшего изучения.

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

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

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

С помощью алгоритма построения деревьев решений мы смогли выяснить, какие характеристики оказывают влияние на предсказываемый параметр и какова степень этого влияния. Для изучения взаимозависимости параметров можно воспользоваться инструментом Dependency Network Browser, доступным из контекстного меню модели (рис. 5).

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

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

На этом мы завершаем рассмотрение технологии Data Mining, которая с каждым годом становится все более востребованной, а ее реализация появляется в новых версиях многих популярных коммерческих продуктов, таких как системы управления базами данных и средства Business Intelligence. Поэтому через некоторое время мы обязательно вернемся к этой теме.

Литература

1. Seidman.C. Data Mining with Microsoft SQL Server 2000: Technical Reference. — Microsoft Press, 2001.
2. Ville.B., de. Microsoft Data Mining. — Digital Press, 2001

Дополнительная информация

Источник