Содержание к диссертации
Введение
ГЛАВА 1. Обзор методов извлечения и обобщения знаний 11
1.1. Машинное обучение и извлечение знаний 11
1.2. Основные понятия и определения 12
1.3. Представление знаний 16
1.4. Проблемы извлечения и обобщения знаний 19
1.4.1. Ограниченная информация 20
1.4.2. Искаженная и неполная исходная информация 24
1.5. Подходы к решению задачи обобщения понятий 26
1.5.1. Стратегии управления в обучении на примерах 27
1.5.2. Алгоритм исключения кандидата и фокусирование 28
1.5.3. Индукция решающих деревьев 35
1.5.4. Подход с использованием приближенных множеств 39
1.6. Выводы 41
ГЛАВА 2. Подход с использованием теории приближенных множеств 44
2.1. Основные понятия и определения теории приближенных множеств 44
2.2. Методы теории приближенных множеств 52
2.2.1. Проблема поиска среза 53
2.2.2. Выполнение дискретизации 57
2.2.3. Построение решающих правил 63
2.3. Выводы 66
ГЛАВА 3. Разработка алгоритма обобщения на основе подхода приближенных множеств 68
3.1. Разработка модификации алгоритма дискретизации непрерывных областей значений атрибутов 69
3.2. Разработка модификации алгоритма выбора существенных атрибутов, совмещенного с этапом дискретизации 80
3.3. Разработка модифицированной стратегии применения решающих правил для классификации ранее неизвестных объектов 84
3.4. Эксперименты на тестовых наборах данных
3.4.1. Эксперименты на данных «задач монахов» 87
3.4.2. Медицинские данные 89
3.4.3. Данные проекта StatLog 90
3.4.4. Другие наборы данных 92
3.5. Выводы 94
ГЛАВА 4. Программная реализация 96
4.1. Структура программного комплекс а 96
4.2. Основные функции, выполняемые программой 97
4.3. Описание программы 98
4.4. Примеры работы 104
4.5. Выводы 112
Заключение 114
Список литературы 119
- Алгоритм исключения кандидата и фокусирование
- Основные понятия и определения теории приближенных множеств
- Разработка модификации алгоритма выбора существенных атрибутов, совмещенного с этапом дискретизации
- Разработка модифицированной стратегии применения решающих правил для классификации ранее неизвестных объектов
Введение к работе
Актуальность темы исследований. Диссертационная работа посвящена исследованию и разработке алгоритмов обобщения на основе теории приближенных множеств. В современных системах принятия решений крайне важной является проблема построения обобщенных моделей на основе обработки больших массивов экспериментальных данных. Источники таких больших потоков данных имеются во многих областях, таких как медицина, биология, маркетинг, банковская деятельность, прогнозирование спроса, космические исследования и многое другое. Общим для этих данных является то, что они содержат большое количество скрытых закономерностей, которые важны для принятия стратегических решений. Однако выявление этих закономерностей лежит за пределами человеческих возможностей главным образом из-за большого и все возрастающего объема данных. Поэтому для вывода таких закономерностей используются методы обобщения и разрабатываются компьютерные системы, реализующие эти методы. Задача обобщения информации является, таким образом, одной из важных задач искусственного интеллекта.
Целью алгоритмов обобщения является получение классификационных правил, позволяющих эффективно распознавать объекты определенного класса. В настоящее время известен ряд алгоритмов, решающих задачу обобщения объектов, заданных наборами признаков. Широко известны такие алгоритмы, как фокусирование (см., например, работы Т. Митчелла, Б. Смита), индукция решающих деревьев (работы Р. Куинлана, Р. Кохави, Дж. Шлиммера, Л. Бримана, В.Н. Вагина), нейронные сети (работы Д. Румельхарта), построение продукционных правил, использование теории приближенных множеств (работы 3. Пав-лака, Я. Комовски, С. Нгуена) и другие подходы. Однако при обработке реальных массивов данных, которые характеризуются большим размером, неполнотой, противоречивостью и зашумленностью хранящейся информации, данные алгоритмы либо не пригодны вовсе, либо не всегда показывали удовлетворительные результаты, что привело к дальнейшим исследованиям в области применения методов обобщения для обработки реальных массивов данных. Одним из способов решения проблемы работы с неполной и противоречивой информацией является подход, основанный на теории приближенных множеств.
В работах Я. Базана, С. Нгуена, Я. Степанюка было показано, что использование теории приближенных множеств в алгоритмах обобщения позволяет существенно повысить точность классификации объектов. Важнейшими этапами в работе алгоритма обобщения, основанного на теории приближенных множеств, являются следующие: дискретизации непрерывных областей значений атрибутов, выделение значимых атрибутов (поиск срезов) и формирование решающих правил. Следует отметить, что задачи дискретизации и поиска минимального среза NP-сложны, что требует разработки эффективных эвристических алгоритмов для их решения. Таким образом, исследование и разработка алгоритмов обобщения, основанных н^сод>щ4дл^^дщ^йых мно-
жеств и в то же время способных обрабатывать большие обучающие выборки за приемлемое время, является весьма актуальной задачей.
Объектом исследования работы являются методы обобщения понятий. Предметом исследования - методы обобщения, основанные на теории приближенных множеств.
Цель работы заключается в разработке алгоритма обобщения, способного обрабатывать реальные массивы данных и основанного на теории приближенных множеств.
Поставленная задача потребовала решения следующих проблем:
-
Разработка эффективного эвристического алгоритма дискретизации непрерывных областей значений признаков.
-
Разработка эффективного алгоритма выбора существенных атрибутов, совмещенного с этапом дискретизации.
-
Разработка модифицированной стратегии применения решающих правил для классификации ранее неизвестных объектов.
-
Разработка и программная реализация системы обобщения понятий на основе предлагаемого алгоритма обобщения.
Методы исследования. Для достижения поставленной в работе цели использовались следующие методы исследования: методы дискретной математики, математической логики, искусственного интеллекта, теории приближенных множеств, математической статистики и методы анализа математической сложности алгоритмов.
Достоверность научных результатов подтверждена теоретическими выкладками, данными компьютерного моделирования, результатами экспериментов, а также сравнением полученных результатов с результатами, приведенными в научной литературе.
Научная новизна исследования состоит в следующем:
-
Сформулированы и доказаны две теоремы, предназначенные для итерационного вычисления количества пар объектов, различимых делением непрерывного атрибута, и имеющие силу для произвольной решающей таблицы. Они положены в основу предлагаемого алгоритма дискретизации.
-
Разработан эффективный эвристический алгоритм дискретизации непрерывных областей значений атрибутов.
-
Разработан алгоритм выбора существенных атрибутов, совмещенный с этапом дискретизации, что позволяет избежать разбиения на интервалы непрерывных областей значений несущественных признаков.
-
Разработана модифицированная стратегия применения решающих правил при классификации неизвестных объектов, позволяющая в большинстве случаев достичь более высокой точности классификации.
Практическая значимость работы заключается в создании программной системы обобщения понятий, реализующей разработанные алгоритмы дискре-
тизации и выбора существенных признаков, а также модифицированную стратегию применения решающих правил.
Практическая значимость работы подтверждается использованием полученных результатов в динамической экспертной системе оперативной диагностики состояния экологически опасных объектов и производств «ДИЭКС» в ОАО «ЦНИИКА», о чем имеется акт о внедрении, а также применением на известном тестовом наборе данных Калифорнийского университета информатики и вычислительной техники UCI Machine Learning Repository, включающем реальные данные из различных сфер: медицины, экономики, биологии идр.
Реализация результатов. Результаты работы использованы в НИР, выполненных в рамках грантов РФФИ, проекты №99-01-00049 и №02-07-90042 по тематике «Исследование и разработка инструментальных средств создания экспертных систем семиотического типа» и в рамках Федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 годы по теме «Системы мониторинга и поддержки принятия решений на основе аппарата нетрадиционных логик».
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 7-й национальной конференции по искусственному интеллекту с международным участием КИИ-2000 (г. Переславль-Залесский, 2000 г.), Международной школе по искусственному интеллекту (Белоруссия, г.Минск, 1999 г.), пяти научно-технических конференциях МЭИ (ТУ) (2000 — 2004 гг.), четырех научных сессиях МИФИ (2001 - 2004 гг.), на 9-й национальной конференции по искусственному интеллекту с международным участием КИИ-2004 (г. Тверь, 2004 г.), на международных форумах информатизации МФИ-2000, МФИ-2003 и МФИ-2004 (Международные конференции «Информационные средства и технологии» (г.Москва, 2000, 2003, 2004 гг.), на двух молодежных научно-технических конференциях студентов, аспирантов и молодых ученых «Наукоемкие технологии и интеллектуальные системы» (г. Москва, 2003,2004 гг.).
Публикации. Основные результаты, полученные по теме диссертационной работы, опубликованы в 20 печатных работах.
Структура и объем работы. Диссертация состоит из введения, четырех
глав, заключения, списка использованной литературы (54 наименования) и приложений. Диссертация содержит 251 страницу машинописного текста.
Алгоритм исключения кандидата и фокусирование
Митчелл разработал изящную структуру, пространство версий, для описания систем, которые для обучения понятию используют подход, управляемый данными [34]. Эта структура может быть описана следующим образом. Предположим, что мы пытаемся изучить некоторое неизвестное целевое понятие, определенное на пространстве примеров. Нам дана последовательность положительных и отрицательных примеров, которые называются выборками целевого понятия. Задача состоит в том, чтобы вывести понятие, которое является совместимым с выборками. Множество всех гипотез Н, которые являются совместимыми с выборками, называется пространством версий выборок. Пространство версий пусто в случае, если ни одна гипотеза не совместима с выборками.
С целью решить эту задачу обучения Митчелл предложил алгоритм, названный алгоритмом исключения кандидата. Алгоритм использует два подмножества пространства версий: множество S наиболее узких гипотез в пространстве версий и множество G наиболее общих гипотез. Эти множества корректируются в зависимости от каждого нового примера. Положительные примеры заставляют программу обобщать множество S, а отрицательные -сужать множество G. Процесс обучения прекращается, когда G = S.
Положительной особенностью этого метода является то, что обучающей программой может быть выполнено инкрементное обучение. Множества S и G могут быть легко модифицированы для того, чтобы объяснить новые обучающие примеры без какого-либо повторного вычисления.
Однако, как и все управляемые данными алгоритмы, алгоритму исключения кандидата присущи трудности при работе с зашумленными обучающими примерами. Так как этот алгоритм стремится найти понятие, которое является совместимым со всеми обучающими примерами, то любой «плохой» пример (то есть ложный положительный или ложный отрицательный) может иметь нежелательные последствия. Так, когда обучающей системе дают ложный положительный пример, множество понятий становится чрезмерно обобщенным. Аналогично, ложный отрицательный пример заставляет множество понятий стать чрезмерно ограниченным. В конечном счете, зашумленные обучающие примеры могут привести к ситуации, что не останется ни одного понятия, совместимого со всеми обучающими примерами. Второй и наиболее серьезный недостаток этого алгоритма - его неспособность обнаруживать дизъюнктивные понятия.
Существуют две вычислительные проблемы, связанные с этим методом. Первая состоит в том, что для модификации множеств S и G мы должны иметь эффективную процедуру проверки, действительно ли одна гипотеза более общая, чем другая. К сожалению, эта задача проверки NP-полна, если мы допускаем произвольно большое число примеров и признаков в гипотезе [13]. Вторая вычислительная проблема состоит в том, что размер множеств S и G может быть неограниченно большим. Показано, что если число признаков велико, то размеры множеств S и G, могут возрастать в экспоненциальной зависимости от числа примеров [13].
Для улучшения вычислительной эффективности данного метода Хаусслер (Haussler) предложил односторонний алгоритм вместо двустороннего подхода, использующегося в алгоритме исключения кандидата. Используя положительные примеры, односторонний алгоритм вычисляет только множество S и затем выясняет, содержатся ли какие-либо отрицательные примеры в множестве S. Если нет отрицательных примеров, которые удовлетворяли бы правилу множества S, то правило имеет силу [14]. Иначе не существует правила, совместимого с обучающей выборкой.
Общая стратегия максимизации качества поиска состоит в том, чтобы выбирать пример, который делит пополам число возможных формул (кандидатов), то есть тот пример, что удовлетворяет половине кандидатов и не удовлетворяет другой половине. Преимущество этой стратегии заключается в том, что, получая классификацию такого примера, мы можем исключить половину остающихся кандидатов. Однако, главная проблема стратегии деления пополам — вычислительная сложность. В наихудшем случае, мы должны сравнить каждый пример с каждым понятием. Если имеется п примеров и к формул-кандидатов, то необходимо пк шагов, чтобы выбрать лучший пример. Это означает существенный расход времени, когда « или к очень большие.
Субраманиан (Subramanian) и Фейгенбаум (Feigenbaum) [49] предложили разбить пример на несколько независимых подпримеров и разложить полное пространство версий на множество отдельных более мелких пространств версий. Процедура проверки для выбора лучшего обучающего примера может быть сначала выполнена в каждом раздробленном пространстве версий, а затем полученный в результате «подпример» может быть объединен в единственный пример, который будет проверен.
Самым известным развитием этого подхода является метод фокусирования [18, 47]. Он предполагает, что над значениями каждого из атрибутов QJGA построена иерархия. Элементы нижнего уровня являются значениями атрибутов и встречаются в обучающем множестве. Другие элементы соответствуют более общим понятиям, т.е. подмножествам Ду с Va .
Важным требованием к подобной иерархии является то, что каждые два элемента должны иметь наименьшую верхнюю грань, т.е. это должно быть не просто частично упорядоченное множество, а верхняя полурешетка. На практике этому требованию легко удовлетворить, добавив Va на вершину иерархии.
Основные понятия и определения теории приближенных множеств
В этой главе была формализована задача извлечения знаний и рассмотрены основные способы представления знаний в системах извлечения знаний. Далее были описаны проблемы, возникающие при извлечении и обобщении знаний, на основе которых строится специфика современных требований к алгоритмам обобщения: Информация, содержащаяся в реальных массивах данных, как правило, ограничена. Данные являются разнородными (количественными, качественными, структурными). Реальные базы данных очень велики, а потому алгоритмы экспоненциальной сложности могут оказаться неприемлемыми. Получаемые результаты должны быть конкретны и понятны человеку. Отдельные значения в исходных данных могут быть искажены или вовсе отсутствовать. Бьши предложены способы преодоления этих проблем. Далее был выполнен сравнительный анализ ряда подходов к решению задачи обобщения. При этом основным критерием являлось их соответствие изложенным выше требованиям. В результате анализа рассмотренных подходов были сделаны следующие выводы: Фокусировка и алгоритм исключения кандидата являются типичными методами классического машинного обучения. Модификация алгоритма исключения кандидата и метод фокусировки имеют низкую вычислительную сложность. Однако их неспособность обрабатывать атрибуты с непрерывными областями значений, а также данные, содержащие отсутствующие значения атрибутов и шум, не позволяет использовать их для обобщения понятий в реальных массивах данных. Подход, основанный на индукции решающих деревьев, позволяет обрабатывать атрибуты как с дискретной, так и с непрерывной областью значений, а также допускает наличие как ошибок в обучающем множестве, так и отсутствующих значений признаков классифицируемых объектов. Кроме того, в рамках этого подхода разработан ряд модификаций, позволяющих обрабатывать неполную информацию (в обучающей выборке возможны неизвестные значения атрибутов). Алгоритмы данного класса, как правило, обладают низкой вычислительной сложностью. Однако с помощью этого подхода не всегда удается получить удовлетворительное качество классификации, если скрытые в обучающей выборке закономерности не представимы в виде дерева (например, правило «если (ai=l) или (а2=\), то класс Сі» нельзя представить в виде дерева). Подход, основанный на теории приближенных множеств, способен удачно справляться с противоречивой и неполной информацией, свойственной реальным массивам данных. Получаемые в результате работы решающие правила удобны для восприятия человеком и позволяют описывать более широкий класс скрытых закономерностей. Однако большинство алгоритмов, базирующихся на этом подходе, имеют недостаток, связанный с высокой вычислительной сложностью. В следующих главах будут изложены пути устранения этого недостатка и предложен эффективный алгоритм обобщения, основанный на данном подходе. В этой главе будет рассмотрен подход к обобщению, который основан на теории приближенных множеств, введены основные понятия теории, исследованы этапы работы алгоритма, базирующего на данном подходе. Далее будет рассмотрен ряд алгоритмов теории приближенных множеств и выявлены их сильные и слабые стороны. Теория приближенных множеств (rough sets theory) была предложена в начале 80-х годов прошлого века польским математиком 3. Павлаком (Z, Pawlak). В дальнейшем эта теория развивалась многими исследователями и применялась для решения разнообразных задач. Рассмотрим, как теория приближенных множеств может быть использована для решения задачи обобщения понятий по признакам. В работах Павлака было введено понятие информационной системы [40, 41]. Под информационной системой понимается пара S = (U,A), где U= {х\, хг, ..., х„} - непустое конечное множество объектов, называемое обучающим множеством или универсумом, а А = {а\, а2 ..., а } - непустое конечное множество атрибутов. Решающая таблица (или решающая система) — это информационная система вида = (U,A j{d}), где d&A - выделенный атрибут, называемый решением или решающим атрибутом, А - условные атрибуты. Пусть на обучающем множестве U введено IND(A) UxU - отношение неразличимости или эквивалентности на U. Упорядоченную пару AS = (U JND(A))) будем называть пространством аппроксимации или пространством приближений. Скажем, что если (х, у) є IND(A), го х и у неразличимы в AS по значениям атрибутов из А. Классы эквивалентности по отношению к IND называются элементарными множествами, или атомами в AS. Обозначим все множество классов эквивалентности как {Xf ,Х ,..., X }. Любое конечное объединение элементарных множеств в AS назовем составным множеством в AS. Семейство составных множеств в AS будем обозначать DeJ{AS).
Разработка модификации алгоритма выбора существенных атрибутов, совмещенного с этапом дискретизации
Были обсуждены три алгоритма, основанные соответственно на существенности атрибута, понятии динамического среза и усовершенствованной стратегии Джонсона. Каждый из данных алгоритмов является эвристическим. Первые два алгоритма находят субминимальный срез, а третий находит не срез, а приближение к нему. Алгоритм, основанный на усовершенствованной стратегии Джонсона, обладает наименьшей вычислительной сложностью. В то же время, алгоритм, основанный на существенности атрибута, позволяет учесть предпочтения пользователя, если он хорошо знаком с предметной областью, а алгоритм поиска динамического среза находит такой срез, что созданные на его основе решающие правила в наибольшей степени подходят для классификации неизвестных объектов. Поэтому выбор алгоритма поиска среза зависит от конкретной предметной области, размера массива данных и производительности имеющейся вычислительной техники.
Был рассмотрен ряд алгоритмов дискретизации. Вычислительная сложность базового и наиболее широко используемого алгоритма дискретизации обладает кубической зависимостью от числа объектов решающей таблицы, что делает его неприменимым для обработки больших баз данных. Поэтому в следующей главе будет предложен эвристический алгоритм дискретизации, который направлен на снижение затрат времени и памяти.
Кроме того, были рассмотрены методы построения решающих правил и отмечена предпочтительность формирования наиболее общих правил. Разработка алгоритма обобщения на основе подхода приближенных множеств
В этой главе, опираясь на выявленные достоинства и недостатки рассмотренных ранее алгоритмов, предлагается их модификация - алгоритм, предназначенный для обработки реальных массивов данных. При этом учитываются такие особенности информации, хранящейся в реальных массивах данных, как большой объем, а также неполнота и противоречивость данных. Представлены результаты тестирования разработанного алгоритма на наборах данных из известного хранилища UCI Machine Learning Repository [28], проведено их сравнение с результатами других эффективных алгоритмов обобщения.
В результате анализа рассмотренных алгоритмов будет предложена их модификация. В ее основу будет положен подход приближенных множеств из-за богатых возможностей обработки неполной и противоречивой информации, а также удобства восприятия человеком получаемых логических правил. Важнейшими этапами в работе алгоритма, основанного на данном подходе, являются следующие: дискретизация непрерывных областей значений атрибутов, выделение значимых атрибутов (поиск срезов) и формирование решающих правил. Поскольку задачи дискретизации и поиска минимального среза NP-сложны, то для их решения необходимы эффективные эвристические алгоритмы.
Разработанная модификация направлена на снижение затрат времени и памяти при сохранении высокого качества классификации, а также на обработку неполноты и противоречивости данных. При этом были решены следующие проблемы: 1. Разработка эффективного эвристического алгоритма дискретизации непрерывных областей значений признаков. 2. Разработка эффективного алгоритма выбора существенных атрибутов, совмещенного с этапом дискретизации. 3. Разработка модифицированной стратегии применения решающих правил для классификации ранее неизвестных объектов. В этом разделе будет предложен новый алгоритм дискретизации, который базируется на идеях, изложенных в [36]. Как отмечалось ранее, для нахождения субоптимального множества делений необходимы эффективные эвристические алгоритмы. Вычислительная сложность алгоритма Джонсона, изложенного в разделе 2.2.2, равна 0(\P\-kn ), что делает его неприменимым для обработки больших баз данных. Предлагаемый эвристический алгоритм направлен на снижение затрат времени и памяти. Он основан на стратегии Джонсона и расширении идеи итерационного вычисления количества пар объектов, различимых делением. Первоначально эта идея была предложена в [36], однако она применима лишь при наложении ряда ограничений на решающую таблицу. Эта идея основана на наблюдении, что между двумя последовательными делениями существует тесная связь. Так, например, можно заметить, что в каждой строке таблицы ! все единицы идут подряд в пределах одного атрибута. А значит, некоторые пары объектов различимы обоими соседними делениями, а изменения в количестве различимых пар объектов могут быть лишь за счет объектов, значения атрибута которых лежат между двумя этими делениями. С.Нгуеном и Х.Нгуеном [36] рассматривается ситуация, когда в этот интервал может попасть ровно один объект. В представленной работе эта идея обобщается на случай произвольного числа таких объектов. Таким образом, идея итерационного вычисления количества пар объектов, различимых делением, расширяется на случай произвольной решающей таблицы.
Разработка модифицированной стратегии применения решающих правил для классификации ранее неизвестных объектов
В проведенных экспериментах все наборы данных были разделены на обучающее множество примеров и тестовое множество. Любые настройки параметров алгоритма выполнялись только в отношении обучающего множества. Сформированные решающие правила были применены для классификации новых объектов из тестовых наборов данных. В качестве критерия успешной или неудачной классификации использовался наиболее распространенный критерий, называемый коэффициентом ошибки классификатора (см. например, [54], [32]), который определяется как отношение числа неверно классифицированных объектов к общему числу всех возможных объектов. Поскольку в реальности число имеющихся в распоряжении объектов всегда ограничено, то коэффициент ошибки необходимо оценивать, исходя из его эмпирических оценок, рассчитанных по относительно небольшим выборкам. Имеется несколько методов оценки коэффициента ошибки классификатора (см. [10, 22]). В проведенных экспериментах применялись методы «обучения и проверки», 10-кратной перекрестной проверки и бутстрепа, описанные ранее в подпункте 1.4.1.1.
В этом разделе будут изложены результаты экспериментов на данных задач монахов [50]. Сначала дадим краткую историческую справку, касающуюся возникновения этой самой известной тестовой задачи. В июле 1991 года в Корсендонкском монастыре была проведена 2-я европейская летняя школа по машинному обучению. После того как монахи этого монастыря в течение двух недель познакомились с множеством разнообразных алгоритмов обучения, перед ними встал вопрос: Какой же алгоритм лучше использовать? И какой -нет? Как следствие этой дилеммы, они создали три простых задачи для сравнения алгоритмов - так называемые три задачи монахов.
Первая задача монахов состоит в том, чтобы в результате обучения получить классифицирующее правило, которое позволяет описать понятие, представленное в дизъюнктивной нормальной форме. Целевое понятие может быть представлено как простое выражение: [х2 = 1] v [х4 = х5] Л/1, которое можно интерпретировать следующим образом: «если для неизвестного объекта атрибут х2 принимает значение 1 или атрибуты х4 и х5 принимают одинаковое значение (неважно, какое именно), то вне зависимости от значений других атрибутов следует классифицировать этот объект как принадлежащий понятию М\». В данном случае для оценки ошибки классификации был применен метод «обучения и проверки». Обучающее множество состояло из 124 примеров (62 положительных и 62 отрицательных), что составляет 30% от полного пространства примеров (432 объекта). Множество тестовых примеров включало все возможные примеры (216 положительных и столько же отрицательных). Каждый объект характеризуется шестью условными атрибутами (области значений которых дискретны и включают малое число значений) и одним решающим атрибутом (с двумя классами решения).
Вторая задача монахов связана с обучением понятию, которое можно описать с помощью следующего высказывания: «Если ровно два атрибута из шести для некоторого объекта принимают первое значение, то классифицировать этот объект как принадлежащий классу Ml». Обучающее множество состояло из 169 примеров (105 положительных и 64 отрицательных), что составляет 40% от полного пространства примеров. Множество тестовых примеров включало все возможные примеры (190 положительных и 242 отрицательных). Каждый объект характеризуется шестью условными атрибутами (области значений которых дискретны и включают малое число значений) и одним решающим атрибутом (с двумя классами решения).
Третья задача монахов заключается в том, чтобы описать понятие, которое задается с помощью следующего выражения: [х2 -ф- 4] & [х5 = 1 v 2] v [xl = 1] & [х2 = 3] Mi. Обучающее множество состояло из 122 примеров (62 положительных и 60 отрицательных), что составляет 30% от полного пространства примеров. Множество тестовых примеров включало все возможные примеры (204 положительных и 228 отрицательных). Каждый объект характеризуется шестью условными атрибутами (области значений которых дискретны и включают малое число значений) и одним решающим атрибутом (с двумя классами решения). Следует отметить, что обучающее множество этой задачи содержит шум.
Результаты показывают, что разработанный алгоритм позволяет для первой задачи достичь коэффициента ошибки 0.000 (или точности классификации 100%). При этом процедурой обучения было построено 21 решающее правило. В случае второй задачи монахов было построено 78 решающих правил, а коэффициент ошибки классификатора составил 0.169 (точность классификации = 83.10%). В ходе решения третьей задачи монахов было сформировано 25 решающих правил, а коэффициент ошибки при классификации тестовых примеров составил примерно 0.046 (точность классификации = 95.37%).
В табл. 11 приведены результаты экспериментов, полученных при применении разработанного алгоритма и других известных алгоритмов обобщения для решения рассматриваемых в данном разделе тестовых задач. В этой таблице задачи монахов обозначены как МопкЛ, Мопк-2 и Мопк-Ъ.
Следует отметить, что точность классификации, полученная с помощью предложенного алгоритма при решении задач монахов, значительно выше точности классификации, достигнутой методами индукции решающих деревьев ID3, ID4, ID5R, С4.5, что объясняется невозможностью представления описания целевого понятия в виде дерева. Кроме того, можно отметить, что процедура дискретизации (а при решении данных задач эта процедура сводится к группировке значений атрибутов) очень полезна, особенно для решения второй задачи монахов. Что касается сравнения с другими алгоритмами подхода приближенных множеств, то для двух задач из трех точность предложенного
