Лабораторная работа №2, Цель работы, Теоретическое введение - Интеллектуальные информационные системы

Деревья решений - общие принципы работы

Цель работы

Изучить принцип построения деревьев решений и построить дерево решений на основе имеющейся выборки примеров.

Теоретическое введение

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

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

пример дерева решений

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

Введем основные понятия из теории деревьев решений:

Название Описание

Объект Пример, шаблон, наблюдение

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

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

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

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

Проверка (test) Условие в узле

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

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

Пусть через {C1, C2, ... CK} обозначены классы(значения метки класса), тогда существуют 3 ситуации:

    1. множество T содержит один или более примеров, относящихся к одному классу CK. Тогда дерево решений для Т - это лист, определяющий класс CK; 2. множество T не содержит ни одного примера, т. е. пустое множество. Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества отличного от T, скажем, из множества, ассоциированного с родителем; 3. множество T содержит примеры, относящиеся к разным классам. В этом случае следует разбить множество T на некоторые подмножества. Для этого выбирается один из признаков, имеющий два и более отличных друг от друга значений O1, O2, ... ON. T разбивается на подмножества T1, T2, ... TN, где каждое подмножество TI содержит все примеры, имеющие значение OI для выбранного признака. Это процедура будет рекурсивно продолжаться до тех пор, пока конечное множество не будет состоять из примеров, относящихся к одному и тому же классу.

При использовании данной методики, построение дерева решений будет происходит сверху вниз.

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

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

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

Правило разбиения. Каким образом следует выбрать признак?

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

Рассмотрим теоретико-информационный критерий разбиения.

Для выбора наиболее подходящего атрибута, предлагается следующий критерий:

Где, Info(T) - энтропия множества T

- количество примеров из некоторого множества S, относящихся к одному и тому же классу CJ. Тогда вероятность того, что случайно выбранный пример из множества S будет принадлежать к классу CJ

Согласно теории информации количество содержащейся в сообщении информации зависит от ее вероятности

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

Множества T1, T2, ... Tn получены при разбиении исходного множества T по проверке X. Выбирается атрибут, дающий максимальное значение по критерию (1).

Впервые эта мера была предложена Р. Куинленом в разработанном им алгоритме ID3. Кроме вышеупомянутого алгоритма C4.5, есть еще целый класс алгоритмов, которые используют этот критерий выбора атрибута.

Правило остановки. Разбивать дальше узел или отметить его как лист?

В дополнение к основному методу построения деревьев решений были предложены следующие правила:

    - Использование статистических методов для оценки целесообразности дальнейшего разбиения, так называемая "ранняя остановка" (prepruning). В конечном счете "ранняя остановка" процесса построения привлекательна в плане экономии времени обучения, но здесь уместно сделать одно важное предостережение: этот подход строит менее точные классификационные модели и поэтому ранняя остановка крайне нежелательна. Признанные авторитеты в этой области Л. Брейман и Р. Куинлен советуют буквально следующее: "Вместо остановки используйте отсечение". - Ограничить глубину дерева. Остановить дальнейшее построение, если разбиение ведет к дереву с глубиной превышающей заданное значение. - Разбиение должно быть нетривиальным, т. е. получившиеся в результате узлы должны содержать не менее заданного количества примеров.

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

Правило отсечения. Каким образом ветви дерева должны отсекаться?

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

Ценность правила, справедливого скажем для 2-3 объектов, крайне низка, и в целях анализа данных такое правило практически непригодно.

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

Для решения вышеописанной проблемы часто применяется так называемое отсечение ветвей (pruning).

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

    - построить дерево; - отсечь или заменить поддеревом те ветви, которые не приведут к возрастанию ошибки.

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

Путь дерева - совокупность вершин от корня дерева до листа. Путь - это фактически одно продукционное правило.

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

Похожие статьи




Лабораторная работа №2, Цель работы, Теоретическое введение - Интеллектуальные информационные системы

Предыдущая | Следующая