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

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

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

· Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.

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

· Медицина. Диагностика различных заболеваний.

· Молекулярная биология. Анализ строения аминокислот.

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

 

Процесс построения деревьев решений на примере системы ID3.

ID3 – один из самых первых алгоритмов построения дерева решений из набора данных. Вся информация об объекте должна быть описана конечным числом признаков (атрибутов), признаки могут быть как дискретными так и непрерывными, атрибут указывающий на класс может быть только дискретным. Процесс обучения происходит путем предъявления объекта с указанием класса к которому он принадлежит, так называемое "обучение с учителем". Разработан Р.Куинленом (R.Quinlan) в конце 1970-х годов.

В основе системы ID3 лежит алгоритм CLS. Этот алгоритм циклически разбивает обучающие примеры (записи БД) на классы в соответствии с переменной (полем), имеющей наибольшую классифицирующую силу. Каждое подмножество примеров, выделяемое такой переменной, вновь разбивается на классы с использованием следующей переменной с наибольшей классифицирующей способностью и т. д. Разбиение заканчивается, когда в подмножестве оказываются объекты лишь одного класса. В ходе процесса образуется дерево решений. Пути движения по этому дереву с верхнего уровня на самые нижние определяют логические правила в виде цепочек конъюнкций.

Подавляющее большинство современных аналитических приложений в классе Data Mining используют алгоритмы построения деревьев решений. Одними из наиболее известных систем являются See5/С5.0 (RuleQuest, Австралия), Darwin Tree (Thinking Machine Corporation, США), Clementine (Integral Solutions, Великобритания), SIPINA (University of Lyon, Франция), IDIS (Information Discovery, США), KnowledgeSeeker (ANGOSS, Канада), AnswerTree (SPSS). Разработчики таких систем, отличающихся незначительными и несущественными вариациями на тему статистических критериев ветвления и подрезания (pruning) деревьев, не скупятся на рекламирование их “превосходных” аналитических свойств, делая акцент на наглядности и понятности получаемых решений.

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

Так, тест 1 оказывается “непроходимым” для алгоритмов построения деревьев решений. Признаки Х1 и Х2, рассматриваемые по отдельности, не обладают способностью отделить крестики от ноликов. Поэтому уже на первом шаге определения “наилучшего” признака эти алгоритмы единодушно отказываются от нахождения какого-либо логического правила.

Результат решения теста 2 с помощью системы AnswerTree v. 2.1 (SPSS) приведен на рис. 4. Распознаваемые классы обозначены буквами L и К, 100 анализируемых признаков обозначены а1,…, а100, каждый признак может принимать два значения – А и В. Тест упрощен – из матрицы данных исключено 200 случайным образом сгенерированных объектов.

Как следует из рисунка, система AnswerTree нашла 7 правил. Они располагаются на концах веток построенного дерева и обведены красным цветом. При этом только два правила можно считать более или менее удовлетворительными по точности и полноте охвата объектов собственного класса. Так, правило № 2

IF (а62=В) и (а72=А) THEN класс L

со 100 % точностью покрывает 39 из 100 объектов (строк) класса L. В свою очередь, правило № 7

IF (а62=А) и (а89=А) и (а84=В) и (а91=В) THEN класс К

относит 57 объектов к классу К с одной ошибкой. Таким образом, в целом тест 2 остался нерешенным. Система не сумела найти 4 известных экзаменатору правила, которые покрывают все объекты распознаваемых классов со 100 % точностью. Аналогично с данным тестом не справляются другие системы, реализующие те или иные алгоритмы построения деревьев решений.

Рисунок 5. Дерево решений, построенное системой AnswerTree по данным теста 2

 

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