Алгоритм извлечения продукционных правил

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

Переменные:

• T – класс, к которому относится пример обучения.

• ES – множество примеров обучения.
• AES – выборка примеров для которых заданы аргументы.
• – первый аргументированный пример из множества AES.
• RULE_LIST – множество правил.
• BEST_RULE – данная переменная содержит оптимальное правило, полученное из аргументированного примера.
• RULE_LIST – множество всех продукционных правил полученных алгоритмом.
• STAR – элементами множества являются все положительные аргументы представленные как условия из примера .
• BEST_CPX – данная переменная хранит лучшее условие, на основании которого будет сформировано правило.
• SELECTORS – множество всех возможных селекторов примера .
• ARG_REASONS – все положительные аргументы примера .
• NEWSTAR – множество условий {x ^y||x Î STAR, yÎSELECTORS}.
• ABNEWSTAR – подмножество NEWSTAR, где условия содержат селекторы из ARG_REASONS.
• ABSTAR – N лучших условий из ABNEWSTAR.

Алгоритм извлечения правил:

0. Начало.

1. Инициализация переменных.

2. Запись в AES всех примеров с аргументами из множества ES.

3. Поиск пороговых значений (см. раздел 2.4.4) для всех атрибутов, для которых они не заданы.

4. Оценка аргументов каждого примера из множества AES и сортировка этих примеров по лучшему аргументу.

5. Присвоение первого аргументированного примера из множества AES.

5.1 Запись в STAR положительных аргументов из примера в виде условий.

5.2 Оценка всех условий из STAR и присвоение переменной BEST_CPX условия с самым высоким значением оценочной функции.

5.3 Формирование SELECTORS и ARG_REASONS из примера .

5.4 Формирование NEWSTAR как множество условий в виде конъюнкции условий из STAR и селектора из SELECTORS.

5.5 Удаление всех условий из NEWSTAR, которые содержат отрицательные аргументы из .

5.6 Оценка всех условий из NEWSTAR, если найдено условие лучше чем BEST_CPX, то присвоение BEST_CPX этого условия, иначе – удалить условие из NEWSTAR.

5.7 Сортировка условий из NEWSTAR. Формирование STAR как N лучших условий из NEWSTAR

5.8 Формирование ABNEWSTAR как подмножество условий из NEWSTAR, содержащих селекторы из ARG_REASONS.

5.9 Запись в ABSTAR N условий из ABNEWSTAR.

5.10 Формирование STAR как объединение множества из STAR c множеством из ABSTAR.

5.11 Если в STAR содержит условия – переход к шагу 5.4, иначе – переход к шагу 6.

6. Присвоение переменой BEST_RULE правила, формируемое из условия BEST_CPX.

7. Добавление BEST_RULE в список правил RULE_LIST.

8. Удаление всех примеров из AES, которые покрываются правилом BEST_RULE.

9. Если в AES остались аргументированные примеры – переход к шагу 5, иначе - переход к шагу 10.

10. Удаление всех примеров из ES, покрываемых правилами из RULE_LIST.

11. Конец.

Выводы

В данной главе был дан обзор нескольких алгоритмов обобщения «с учителем». Для дальнейшей реализации и исследования выбран алгоритм ABCN2, так как он позволяет на порядок лучше решать задачу обобщения в условиях зашумленных обучающих выборок, особенно содержащих искаженные значения в решающем атрибуте. Также, аргументы объясняют эксперту, почему (по какому критерию) очередной пример в экзаменационной выборке был отнесен к тому или иному классу, что несомненно важно в повседневной жизни (Задачи медицинской направленности, скорринг, прогноз погоды и т.д.).

В следующем разделе будет подробно рассмотрен этап программной реализации алгоритма ABCN2 и проведено его тестирование с целью анализа_эффективности_основных_архитектурных_решений

Глава 3. Программная реализация алгоритма CN2 и ABCN2

Постановка задачи

Исходные данные для решения задачи обобщения с аргументацией представлены в виде таблиц, в которых каждой строке соответствует признаковое описание объекта, а каждому столбцу – определенный атрибут с известными характеристиками.

Один из признаков является результирующим (предсказываемым) - его допустимые значения определяют возможные классы, к которым могут быть отнесены объекты.

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

 

Требования к системе

Требования к оборудованию и ОС:

1. операционная система Microsoft Windows 2000 и выше

2. процессор не ниже 166 МГц

3. оперативная память не ниже 64 МБ

4. монитор VGA: диагональ 17 дюймов, разрешение 1024х768

5. наличие мыши и клавиатуры

 

Функциональные требования к системе:

1. ввод существующей или создание новой таблицы с описанием объектов с последующей возможностью их редактирования;

2. ввод из файла основных характеристик объектов – по которым проводится классификация, их названия, принимаемые ими значения;

3. возможность интерактивного ввода описания атрибутов;

4. сохранение введенных или измененных данных в существующем или новом файле в формате, пригодном для повторной загрузки и обработки;

5. построение и вывод набора продукционных правил на основе обучающей выборки заданной размерности;

6. тестирование полученных наборов продукционных правил на различных примерах с выводом статистической информации о проценте распознавания объектов.

Среда разработки

Программная реализация проводилась с использованием продукта компании Microsoft Visual C# 2012 Express Edition.

Язык программирования С#[8] очень близок к таким успешным языкам как C++ и Java, он также базируется на объектно-ориентированных концепциях и достаточно широко используется в настоящее время для создания различных приложений со стандартным интерфейсом операционной системы Windows. Используемая инструментальная среда имеет широкий набор компонент для создания удобного пользовательского интерфейса.