Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

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



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

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

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

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

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

Алгоритмы ДР часто строят «ветвистые деревья» =>их сложно воспринять и снижает ценность классификационно модели

Идеальное дерево-дерево состоит из корня и двух узлов , листьев

Для уменьшения ветвистости используют отсечение (Pruning)

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

· построить дерево;

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

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

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

  • быстрый процесс обучения;
  • генерация правил в областях, где эксперту трудно формализовать свои знания;
  • извлечение правил на естественном языке;
  • интуитивно понятная классификационная модель;
  • высокая точность прогноза, сопоставимая с другими методами (статистика, нейронные сети);
  • построение непараметрических моделей.

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

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

 

 

Как разбивать на подмножества:

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

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

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.