Введение в DataMining
Часть 3. Построение деревьев решений
В предыдущей части данной статьи мы рассказали об алгоритме
кластеризации и рассмотрели его применение на примере построения антиспамового
фильтра с помощью реализации этого алгоритма, содержащейся в составе аналитических
служб Microsoft SQL Server 2000. В завершающей части статьи речь пойдет о применении
другого алгоритма Data Mining, носящего название Decision Trees (построение
деревьев решений).
Что такое деревья решений
од
термином «деревья решений» подразумевается семейство алгоритмов, основанных
на создании иерархической структуры, которая базируется на ответе «Да» или «Нет»
на набор вопросов. Такие алгоритмы весьма популярны: в настоящее время они реализованы
практически во всех коммерческих средствах 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
