Комбинаторные оценки вероятности переобучения и их применение в логических алгоритмах классификации

• Автор: Ивахненко, Андрей Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 100 с. : ил.

Оглавление
Введение
1 Обобщающая способность
1.1 Задача классификации
1.2 Проблема переобучения
1.3 Логические алгоритмы классификации
1.4 Постановка задачи
2 Комбинаторные оценки вероятности переобучения
2.1 Метод порождающих и запрещающих множеств
2.2 Оценки расслоения-связности
2.3 Структура классов эквивалентности
2.4 Обобщение на случай номинальных и порядковых признаков
2.5 Численные методы оценивания вероятности переобучения
2.6 Информативность с поправкой на переобучение
2.7 Численные эксперименты на модельных данных
2.7.1 Анализ завышенное оценки расслоения-связности
2.7.2 Экспериментальное подтверждение методики
3 Построение логических алгоритмов классификации
3.1 Методы оценивания информативности правил

3.1.1 Эвристический пороговый е, 5-критерий
3.1.2 Гипергеометрический критерий (точный тест Фишера)
3.1.3 Энтропийный критерий и индекс Джини
3.1.4 Парето-оитимальный фронт по паре критериев (р. п)
3.2 Методы поиска информативных конъюнкций
3.2.1 Бинаризация исходной информации
3.2.2 Стабилизация набора правил
3.2.3 Случайный поиск
3.2.4 Случайный поиск с адаптацией
3.2.5 Усеченный поиск в ширину
3.3 Методы построения композиций информативных правил
3.3.1 Решающий список
3.3.2 Взвешенное голосование
3.3.3 Логистическая регрессия
3.4 Методы оценивания апостериорных вероятностей
4 Вычислительные эксперименты на реальных данных
4.1 Модифицированный критерий информативности
4.2 Анализ переобученное правил
4.3 Уменьшение переобученное
4.4 Оценивание апостериорной вероятности
Заключение

Введение
Диссертационная работа относится к математической теории распознавания и классификации и посвящена проблеме повышения обобщающей способности логических алгоритмов классификации, основанных на поиске информативных конъюнктивных закономерностей в массивах прецедентных данных с вещественными, порядковыми и номинальными признаками.
Актуальность темы. Логические алгоритмы классификации широко используются для автоматизации принятия решений в трудноформализуемых областях, таких как медицинская диагностика, геологическое прогнозирование, кредитный скоринг, направленный маркетинг и т.д. Их преимуществом является возможность содержательной интерпретации как внутреннего строения алгоритма, так и принимаемых им решений на естественном языке в терминах предметной области. Однако качество классификации (обобщающая способность) логических алгоритмов, как правило, немного уступает более сложным конструкциям, таким как бустинг или бэггинг над решающими деревьями, которые являются «чёрными ящиками» и не обладают свойством интерпретируемости. Поэтому актуальной задачей является повышение обобщающей способности логических алгоритмов классификации без существенного усложнения их внутреннего строения.
Стандартные подходы теории статистического обучения дают слишком осторожные, пессимистичные оценки обобщающей способности. Эффекты переобучения, возникающие при поиске логических закономерностей, являются относительно слабыми. Они существенно зависят от конкретной выборки данных и потому плохо описываются стандартными оценками. Недавно разработанная комбинаторная теория переобучения даёт существенно более точные оценки вероятности переобучения. Актуальность данной диссертационной работы связана ещё и с тем, что она является первым примером практического применения комбинаторной

к правилу г:
• Бг — объекты недоминирующегося множества, соответствующего правилу г;
• ,5у = {х|г -< ж} — объекты, которые доминируют правило г;
• Б1Г = {ж|а; -< г, х $ 5Г} — объекты, которые доминируются правилом г;
• 5" = -ЛГ(5Г и 5* и 5') — объекты, несравнимые с правилом г.
По определению правила г и (7 называются связанными, если р(г, д) = 1 и г ^ д. Существует единственный объект хгд Є X такой, что 0 = 1{г,хгд) < І^,хт<1) = 1.
Для работы данного алгоритма нам потребуется предвычисленная информация об отношениях доминирования между объектами выборки.
Построим минимальную транзитивную редукцию графа отношений объектов в выборке <3 = (X, Е). Вершинами графа Є будут объекты множества X, ребро (и, у) Є Е между вершинами гг, щ Є X существует тогда и только тогда, когда и < V и не существует объекта а: Є X такого, что и < х < V. Для построения графа С сначала воспользуемся топологической сортировкой, описанной в [23]. После этого, перебирая объекты ио-порядку удалим лишние связи. Функция д{х) выдает по заданному объекту х все объекты
Допустим что мы хотим найти все правила связанные с правилом г, тогда нам надо придерживаться алгоритма 2.5.1.
Шаг 0. Подготовительный. Первое что нужно сделать это определить для данного правила г множества 5Г, , 5*, 5Сложность этой операции 0{пЬ). В
результате мы можем дальше рассматривать в качестве правила, стандартного представителя класса эквивалентности, к которому принадлежит правило г. Стандартный представитель однозначно определяется по множеству Бг за время 0{п2).