Модель, метод и комплекс программ для решения задачи классификации с использованием генетических алгоритмов

• Автор: Ржеуцкий, Александр Викторович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Санкт-Петербург
• Количество страниц: 156 с. : ил.

Оглавление
Введение
1. Анализ существующих подходов к решению задачи классификации на основе обучения по прецедентам. Постановка задачи исследования
1.1. Содержательная постановка задачи классификации на основе обучения по прецедентам

1.2. Формальная постановка задачи классификации

1.3. Оценка качества классификатора

1.4. Сравнительный анализ основных моделей классификации

1.5. Генетические алгоритмы в задачах машинного обучения

1.6. Постановка задачи исследования

Выводы по главе

2. Разработка метода и эффективных алгоритмов построения деревьев классификации на основе генетического программирования
2.1. Анализ существующих алгоритмов построения деревьев классификации как основы для предлагаемого генетического алгоритма
2.1.1. Алгоритм ID3
2.1.2. Алгоритм С4
2.1.3. Алгоритм CART
2.1.4. Результаты анализа классического метода и алгоритмов построения деревьев классификации
2.2. Предлагаемый метод построения деревьев классификации на основе применения генетического алгоритма комбинирования эвристик
2.2.1. Виды эвристик, используемые при построении дерева классификации
2.2.2. Выбор представления дерева классификации в виде особи генетического алгоритма
2.2.3. Общее описание алгоритма
2.2.4. Формирование начальной популяции
2.2.5. Оператор кроссовера
2.2.6. Оператор мутации
2.2.7. Выполнение эволюции особей. Переход к новому этапу
2.3. Используемые структуры данных
Выводы по главе
3. Реализация и анализ алгоритмов построения деревьев классификации. Вычислительный эксперимент на тестовых данных
3.1. Особенности реализации алгоритмов
3.1.1. Борьба с переобучением. Выделение тестовой и экзаменационной выборки данных
3.1.2. Использование скользящего контроля для оценки точности классификации
3.1.3. Обработка числовых значений целевых атрибутов. Дискретизация данных
3.2. Анализ вычислительной сложности алгоритма
3.2.1. Асимптотическая оценка вычислительной сложности алгоритма
3.2.2. Экспериментальное исследование времени исполнения алгоритма
3.3. Экспериментальное сравнение реализованных алгоритмов с известными алгоритмами классификации на основе нейронных сетей
3.3.1. Подбор оптимальной архитектуры нейронный сети.
Классификация данных с дискретными значениями целевого атрибута
3.3.2. Сравнение результатов классификации при наличии пропущенных данных
3.3.3. Сравнение результатов классификации с числовыми значениями атрибутов
Выводы по главе
4. Комплекс проблемно-ориентированных программ для проведения вычислительного эксперимента. Прикладные результаты работы
4.1. Разработка структуры комплекса проблемно-ориентированных программ для проведения вычислительного эксперимента
4.1.1. Методика построения и использования классификационной модели
4.1.2. Структура системы анализа данных с использованием подсистемы классификации

4.1.3. Структура комплекса программ для проведения вычислительного эксперимента
4.2. Применение результатов работы для анализа данных в CRM-системе предприятия
4.2.1. Описание предметной области
4.2.2. Постановка задачи классификации, определение входных величин
4.2.3. Сравнение результатов с известными алгоритмами классификации
4.3. Применение результатов работы для анализа исполнительской дисциплины сотрудников в системе электронного документооборота
4.3.1. Описание предметной области
4.3.2. Постановка задачи классификации, определение входных атрибутов
4.3.3. Сравнение результатов с известными алгоритмами классификации
4.4. Применение результатов работы для классификации учебных задач по их сложности в системе электронного обучения
4.4.1. Описание предметной области
4.4.2. Постановка задачи классификации, определение входных атрибутов
4.4.3. Сравнение результатов с известными алгоритмами классификации
Выводы по главе
Заключение
Список использованных источников
Приложения

вероятностью, т.е. к такому классу, для которого обучающая выборка наиболее правдоподобна.
Определение 1.8. Апостериорная вероятность класса к для объекта х -это условная вероятность Р(кх) принадлежности объекта х классу к. Она может быть вычислена по формуле Байеса, если известны р(х,к) и Р(к):
Пцд)Д (110)
Р(х) УР(г.1).Р(1)
Оптимальный алгоритм байесовской классификации при условии бинарной функции штрафа, задаваемый выражением (1.3), можно
переписать через апостериорные вероятности:
а(х) = атахР(£ | х) (Е11)
ка К
Если классы ещё и равновероятны (Р(к) = |К| ), то объект х просто относится к классу к с наибольшим значением плотности распределения р(х,к) в точке х.
Выражение (1.11) называют байесовским решающим правилом или принципом максимума апостериорной вероятности.
Определение 1.9. Минимальное значение ожидаемого среднего риска <2(а), достигаемое байесовским решающим правилом, называется байесовским риском или байесовским уровнем ошибки.
Байесовский уровень ошибки часто используют в качестве эталона (нижней границы погрешности) при тестировании различных алгоритмов классификации на модельных данных.
На практике априорные вероятности и плотности распределения классов у реальных данных, как правило, не известны. Их приходится оценивать по обучающей выборке. В результате байесовский алгоритм перестаёт быть оптимальным, так как восстановить вероятностные характеристики по конечной выборке можно только с некоторой погрешностью. Чем короче выборка, тем выше шансы подогнать распределение под конкретные данные и столкнуться с эффектом