Исследование и разработка алгоритмов обобщения на основе теории приближенных множеств

• Автор: Куликов, Алексей Владимирович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 251 с.

Содержание
ВВЕДЕНИЕ

ГЛАВА 1. ОБЗОР МЕТОДОВ ИЗВЛЕЧЕНИЯ И ОБОБЩЕНИЯ ЗНАНИЙ.

1.1. Машинное обучение и извлечение знаний

1.2. Основные понятия и определения.

1.3. Представление знаний

1.4. Проблемы извлечения и обобщения знаний.

1.4.1. Ограниченная информация.

1.4.2. Искаженная и неполная исходная информация.

1.5. ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ ОБОБЩЕНИЯ ПОНЯТИЙ

1.5.1. Стратегии управления в обучении на примерах.

1.5.2. Алгоритм исключения кандидата и фокусирование.
1.5.3. Индукция решающих деревьев
1.5.4. Подход с использованием приближенных множеств.
1.6. Выводы
ГЛАВА 2. ПОДХОД С ИСПОЛЬЗОВАНИЕМ ТЕОРИИ ПРИБЛИЖЕННЫХ МНОЖЕСТВ
2.1. Основные понятия и определения теории приближенных множеств .
2.2. Методы теории приближенных множеств.
2.2.1. Проблема поиска среза.
2.2.2. Выполнение дискретизации
2.2.3. Построение решающих правил
2.3. Выводы
ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМА ОБОБЩЕНИЯ НА ОСНОВЕ ПОДХОДА ПРИБЛИЖЕННЫХ МНОЖЕСТВ.
3.1. Разработка модификации алгоритма дискретизации непрерывных областей значений атрибутов.
3.2. Разработка модификации алгоритма выбора существенных атрибутов, совмещенного с этапом дискретизации
3.3. Разработка модифицированной стратегии применения решающих правил для классификации ранее неизвестных объектов.
3.4. Эксперименты на тестовых наборах данных
3.4. . Эксперименты на данных задач монахов.
3.4.2. Медицинские данные
3.4.3. Данные проекта БгаИо.
3.4.4. Другие наборы данных
3.5. Выводы.
ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ.
4.1. Структура программного комплекса.
4.2. Основные функции, выполняемые программой.
4.3. Описание программы.
4.4. Примеры работы
4.5. Выводы
ЗАКЛЮЧЕНИЕ.
СПИСОК ЛИТЕРАТУРЫ


Например, на обучающей выборке с п логическими признаками можно построить " возможных решающих функций (таких как решающие деревья или продукционные правила). Такая проблема особенно остра, если размер обучающего множества заметно меньше размера пространства возможных решающих функций. Было предложено несколько методик устранения этой проблемы, рассмотрим некоторые из них. Мы можем искать правила, которые не обязательно классифицируют все объекты корректно, просто они показывают вероятность того, что объект, удовлетворяющий описанию, принадлежит классу. Такие вероятностные правила предоставляют очень важную информацию об отношениях в базе данных. Например, отношение между курением и раком не является корректным, т. Если ни один из предсказывающих атрибутов не имеет отношения к классификации, получается, что атрибуты и класс объектов никак не связаны. В этом случае нельзя найти даже вероятностных правил. Например, при решении задач медицинской диагностики бесполезно искать связь между фамилией пациента и фактом заболевания какой-либо болезнью. Корректность найденных описаний может быть проверена разделением обучающего множества на несколько частей. Далее будет рассмотрен ряд таких методов. Они проверяют, насколько удачно построенное решающее дерево может классифицировать новые объекты. Наиболее простой способ оценить, насколько хорошо возможная решающая функция (такая как система решающих правил или дерево решений) работает на тестовом множеегве - это проверить еб на тестовом множестве. Обучение на тестовых данных увеличивает множество обучения и, как следствие, приводит к улучшению обобщения. Другой методикой является разбиение обучающего множества, г. Этот метод называется методом «обучения и проверки». Но такое разбиение сокращает размер обучающего множества, а следовательно, возрастает возможность переизбытка подходящих решающих функций. Далее будут описаны некоторые методики проверки (см. ПОГрСШНОСТИ е, на и. Коэффициент погрешности - это отношение числа ошибок классификации, сделанных в к количеству примеров в ? Тогда для классификационной модели, обученной на всех примерах V, величина коэффициента погрешности, которую можно ожидать на новых примерах, будет равняться среднему арифметическому всех ? Проверка исключением одного примера является частным случаем перекрестной проверки, при которой к равняется числу примеров выборки и, и каждое подмножество V. При проверке на каждом мы просто замечаем, была ли сделана ошибка. Далее считаем общее количество ошибок и делим на к для того, чтобы получить коэффициент погрешности. Этот вариант проверки, конечно, более сложен в вычислительном отношении, но полезен, когда необходима более точная оценка коэффициента погрешности классификационной модели. Метод бутстрепа был предложен Эфроном и подробно изложен в []. Предположим, что обучающее множество состоит из п примеров. Метод бутстрепа состоит в создании к выборок путем взятия по п примеров (возможно, с повторами) в каждую из выборок, где к - внешний параметр. При этом в каждую выборку примеры выбираются из исходного обучающего множества независимо друг от друга. Таким образом, в каждой выборке, практически наверняка, будут повторы. Для каждого примера обучающего множества вероятность не быть выбранным после того, как уже были взяты п примеров, равна (1 -Мп)п &е~] «0. II, и проверено на неизвестных примерах (т. Пусть ? На каждый лист решающего дерева может приходиться лишь небольшое число примеров. Для этих узлов проверка основана на очень малой выборке и, їдким образом, вероятно, мы будем иметь переизбыток подходящих решений. Эту проблему можно решить путем завершения процедуры построения дерева до того, как все примеры будут отнесены к разным классам. То есть листовая вершина может содержать примеры более чем одного класса, но в этом случае принимается решение в пользу наиболее многочисленного класса. Эта процедура приведет к небольшому числу ошибок, но часто принятие малого числа ошибок на обучающем множестве, приводит к меньшему количеству ошибок на тестовом множестве. Такая особенность проиллюстрирована на рис.