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

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

- Выбор критерия атрибута;

- Правило остановки обучения;

- Отсечение ветвей.

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

Далее в работе мы рассмотрим подробнее теоретико-информационный и статистический критерий.

Теоретико-информационный критерий

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

Gain(X) = Info(T) − Infox(T), где:

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

- Infox(T)=∑i=1n∣Ti∣∣T∣∗Info(Ti)

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

Статистический критерий

Алгоритм CART использует индекс Gini, который оценивает "расстояние" между распределениями классов:

Gini(c)=1−∑jp2j, где:

- c – текущий узел;

- pj – вероятность класса j в узле c.

Правило остановки

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

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

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

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

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

Правило отсечения

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

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

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

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

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

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

Извлечение и создание набора правил

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

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

Самоорганизующиеся карты Кохонена

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

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

Преимущества

Основные преимущества самоорганизующихся карт Кохонена:

- устойчивость к зашумленным данным

- быстрое и неуправляемое обучение

- возможность визуализировать многомерные входные данные

Описание алгоритма

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