Построение и исследование полных решающих деревьев для задач классификации по прецедентам

• Автор: Генрихов, Игорь Евгеньевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 169 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
Глава 1. Обзор и основные понятия, используемые при построении классического решающего дерева

1.1 Основные понятия, используемые при построении классического решающего дерева

1.2 Синтез корректного бинарного решающего дерева с помощью алгоритма построения допустимого разбиения

1.3 Описание алгоритма С4.5 в случае целочисленной информации

1.4 Описание алгоритма С4.5 в случае вещественнозначной информации и наличия пропусков
1.5 0 методах решения задачи распознавания, основанных на поиске информативных фрагментов в признаковых описаниях объектов. Связь с решающими деревьями

1.6 Основные выводы

Глава 2. Описание распознающих алгоритмов, основанных на построении полных решающих деревьев
2.1 Основные понятия и схемы построения полных решающих деревьев
2.2 Описание алгоритма Полный С4.
2.3 Описание алгоритмов АСТ.Уоюе, AGI.La.max, AGI.La.sum и АИ-ЕНаз
2.4 Критерий выбора оптимального порога перекодировки
2.5 Основные выводы
Глава 3. Практические исследования распознающих процедур, основанных на построении полных решающих деревьев
3.1 Тестирование алгоритма Полный С4.
3.2 Тестирование алгоритмов АСТУоюе, AGI.La.max и AGI.La.sum..
3.3 Тестирование алгоритма АОТЕЯаэ
3.4 Изучение переобученности распознающих процедур, основанных на построении полных решающих деревьев
3.5 Исследование полного решающего дерева как выпуклой корректирующей процедуры

3.6 Основные выводы
Глава 4. Теоретические исследования распознающих процедур, основанных на построении полных решающих деревьев
4.1 Числовые характеристики полного решающего дерева
4.2 Оценки емкости семейства полных решающих деревьев..
4.3 Оценки времени синтеза полного решающего дерева
4.4 Применение теории отступов для анализа обобщающей способности полного решающего дерева
4.5 Исследование эмпирической радемахеровской сложности полного
решающего дерева
4.6 Основные выводы
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
ПРИЛОЖЕНИЯ

ВВЕДЕНИЕ
Для решения прикладных задач классификации, распознавания и прогнозирования, возникающих в различных плохо формализованных областях, успешно применяются методы распознавания образов [2, 30, 40, 57, 86, 102]. Одной из центральных задач распознавания образов является задача распознавания по прецедентам, стандартная постановка которой заключается в следующем [39].
Исследуется некоторое множество объектов М. Объекты множества М описываются системой признаков {хх,...,хп}. Известно, что множество М представимо в виде объединения непересекающихся подмножеств, называемых классами КХ,...,К1, /> 2. Имеется конечное множество объектов (прецедентов
или обучающих объектов) {5,1,...,5т} из М, о которых известно каким классам они принадлежат. Требуется по предъявленному описанию некоторого объекта из М определить класс, которому принадлежит этот объект.
Одним из известных инструментов решения рассматриваемой задачи являются деревья решений. Первые работы, связанные с построением деревьев решений, выполнены К. И. Ховлендом и Э. Б. Хантом [89-93] в конце 50-х начале 60-х годов XX века. Важные результаты для развития этого направления были получены в работе Э. Б. Ханта, Дж. Мэрина и Ф. Дж. Стоуна "Experiments in Induction" [94], вышедшей в 1966 году. Вопросы, связанные с построением решающих деревьев (РД), рассматривались в следующих работах: Г. X. Бабич [1], А. Ш. Блох [3], И. JT. Букатова [4], Р. С. Гольдман [16], В. А. Дискант [17], Г. Л. Жуков [38], А. Д. Закревский и Н. Р. Торопов [41], А. В. Карелина и Ю. Н. Печерский [43], А. М. Кукинов [47], Г. С. Лбов [48, 49], И. Б. Сироджа [55], В. И. Донской [20-24], Ю. Ю. Дюличева [23, 24, 27, 28], М. Ю. Мошков [51, 113, 114], А. Гловацки [84], Л. Н. Канал [95], А. В. Кулкарни [101], М. В. Курзински [103], Дж. Му и К. С. Фу [82], X. Дж. Пайн и В. С. Мейзель [119], Д. А. Прис [123], Дж. Р. Куинлан [98, 124-127], Л. Брейман [67-70], X. Хауска и П. Ш.
<Л е.0, разбивает множество Т на два подмножества |7^°7^1Н. Подмножество
7?) | состоит из обучающих объектов множества Т, для которых аг1 < с
{аг1 >с1), г = ,...,т.
Величина, вычисляемая по формуле
г,(0)

называется количеством информации, необходимым для определения класса, которому принадлежит объект из множества Т при разбиении Т по порогу d признака xt.
Величина Info (Г) определяется также как и для случая целочисленной
информации (разд. 1.3).
Информационный выигрыш (information gain), получаемый при разбиении множества Т по порогу d признака xt , вычисляется по формуле
Gain (хг =Info (Т) - Info (х, )d.
Величина, вычисляемая по формуле
7’(°)

Splitlnfo (хг ) = —j—— log

7’(1)

Щ т |г| |г| ’
определяет потенциальную информацию, получаемую при разбиении множества Т по порогу d признака х1.
Оптимальным порогом d(xt) признака х1 считается порог deGl, для которого величина (нормированный информационный выигрыш)
Оа^,ю(,
принимает наибольшее значение.
Поиск оптимального порога осуществляется для каждого признака из Х{Т). После этого из всех признаков в Х(Т) выбирается только один наиболее