Студопедия — Критерий расщепления
Студопедия Главная Случайная страница Обратная связь

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

Критерий расщепления






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

Существуют различные критерии расщепления. Наиболее известные - мера энтропии и индекс Gini. При помощи индекса Gini атрибут выбирается на основании расстояний между распределениями классов.

Если дано множество T, включающее примеры из k классов, индекс Gini, т.е. gini(T), определяется по формуле:

где T - текущий узел, pj – вероятность (доля) класса j в узле T, n – количествообъектов, k – количество классов.

Энтропия или прирост информации. Мера количества информации – это энтропия, а в нашем случае это мера разнообразия классов в узле. В результате разбиения должны образовываться узлы с меньшим разнообразием состояний выходной переменной. Следовательно, энтропия падает, а количество внутренней информации в узле растет. Формально энтропия определенного узла Т дерева решений определяется так:

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

Энтропия всего разбиения – сумма энтропий всех узлов, умноженная на долю записей каждого узла в общем числе записей:

.

Для выбора атрибута расщепления используется критерий, называемый приростом информации или уменьшением энтропии:

.

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

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

В процессе построения дерева, чтобы его размеры не стали чрезмерно большими, используют специальные процедуры, которые позволяют создавать оптимальные деревья, так называемые деревья "подходящих размеров" (Breiman,1984).

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

Тут существует две возможные стратегии. Первая состоит в наращивании дерева до определенного размера в соответствии с параметрами, заданными пользователем.

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

Вторая стратегия состоит в использовании набора процедур, определяющих "подходящий размер" дерева, они разработаны Бриманом, Куилендом и др. в 1984 году. Однако, как отмечают авторы, нельзя сказать, что эти процедуры доступны начинающему пользователю.

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

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







Дата добавления: 2015-09-19; просмотров: 968. Нарушение авторских прав; Мы поможем в написании вашей работы!



Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Логические цифровые микросхемы Более сложные элементы цифровой схемотехники (триггеры, мультиплексоры, декодеры и т.д.) не имеют...

Тема 5. Организационная структура управления гостиницей 1. Виды организационно – управленческих структур. 2. Организационно – управленческая структура современного ТГК...

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

Методы анализа финансово-хозяйственной деятельности предприятия   Содержанием анализа финансово-хозяйственной деятельности предприятия является глубокое и всестороннее изучение экономической информации о функционировании анализируемого субъекта хозяйствования с целью принятия оптимальных управленческих...

ЛЕЧЕБНО-ПРОФИЛАКТИЧЕСКОЙ ПОМОЩИ НАСЕЛЕНИЮ В УСЛОВИЯХ ОМС 001. Основными путями развития поликлинической помощи взрослому населению в новых экономических условиях являются все...

МЕТОДИКА ИЗУЧЕНИЯ МОРФЕМНОГО СОСТАВА СЛОВА В НАЧАЛЬНЫХ КЛАССАХ В практике речевого общения широко известен следующий факт: как взрослые...

СИНТАКСИЧЕСКАЯ РАБОТА В СИСТЕМЕ РАЗВИТИЯ РЕЧИ УЧАЩИХСЯ В языке различаются уровни — уровень слова (лексический), уровень словосочетания и предложения (синтаксический) и уровень Словосочетание в этом смысле может рассматриваться как переходное звено от лексического уровня к синтаксическому...

Studopedia.info - Студопедия - 2014-2024 год . (0.014 сек.) русская версия | украинская версия