автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование и разработка алгоритмов обобщения на основе теории приближенных множеств

На правах рукописи

Куликов Алексей Владимирович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ ОБОБЩЕНИЯ НА ОСНОВЕ ТЕОРИИ ПРИБЛИЖЕННЫХ МНОЖЕСТВ

Специальность 05.13.11 -Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва-2004

Работа выполнена на кафедре Прикладной матемагики Московского энергетического института (Технического университета)

Научный руководитель: доктор технических наук, профессор

Вадим Николаевич Вагин

Официальные оппоненты: доктор физико-математических наук,

профессор

Осипов Геннадий Семенович

кандидат физико-математических наук, профессор

Геральд Станиславович Плесневич

Ведущая организация: РосНИИ информационных технологий

и систем автоматизированного проектирования (РосНИИ ИТ и АП)

Защита состоится «24» декабря 2004 г. в 16 час. 00 мин. на заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (Техническом университете) по адресу: 111250, Москва, Красноказарменная ул., 17 (ауд. Г-306).

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (Технического университета).

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу: 111250, г. Москва, Красноказарменная улица, д. 14, Ученый Совет МЭИ (ТУ).

Автореферат разослан «23» ноября 2004 г.

Ученый секретарь

диссертационного совета Д 212.157.01 кандидат технических наук, профессор

1С-,к

И.И. Ладыгин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследований. Диссертационная работа посвящена исследованию и разработке алгоритмов обобщения на основе теории приближенных множеств. В современных системах принятия решений крайне важной является проблема построения обобщенных моделей на основе обработки больших массивов экспериментальных данных. Источники таких больших потоков данных имеются во многих областях, таких как медицина, биология, маркетинг, банковская деятельность, прогнозирование спроса, космические исследования и многое другое. Общим для этих данных является то, что они содержат большое количество скрытых закономерностей, которые важны для принятия стратегических решений. Однако выявление этих закономерностей лежит за пределами человеческих возможностей главным образом из-за большого и все возрастающего объема данных. Поэтому для вывода таких закономерностей используются методы обобщения и разрабатываются компьютерные системы, реализующие эти методы. Задача обобщения информации является, таким образом, одной из важных задач искусственного интеллекта.

Целью алгоритмов обобщения является получение классификационных правил, позволяющих эффективно распознавать объекты определенного класса. В настоящее время известен ряд алгоритмов, решающих задачу обобщения объектов, заданных наборами признаков. Широко известны такие алгоритмы, как фокусирование (см., например, работы Т. Митчелла, Б. Смита), индукция решающих деревьев (работы Р. Куинлана, Р. Кохави, Дж. Шлиммера, Л. Бримана, В.Н. Вагина), нейронные сети (работы Д. Румельхарта), построение продукционных правил, использование теории приближенных множеств (работы 3. Пав-лака, Я. Комовски, С. Нгуена) и другие подходы. Однако при обработке реальных массивов данных, которые характеризуются большим размером, неполнотой, противоречивостью и зашумленностью хранящейся информации, данные алгоритмы либо не пригодны вовсе, либо не всегда показывали удовлетворительные результаты, что привело к дальнейшим исследованиям в области применения методов обобщения для обработки реальных массивов данных. Одним из способов решения проблемы работы с неполной и противоречивой информацией является подход, основанный на теории приближенных множеств.

В работах Я. Базана, С. Нгуена, Я. Степанюка было показано, что использование теории приближенных множеств в алгоритмах обобщения позволяет существенно повысить точность классификации объектов. Важнейшими этапами в работе алгоритма обобщения, основанного на теории приближенных множеств, являются следующие: дискретизации непрерывных областей значений атрибутов, выделение значимых атрибутов (поиск срезов) и формирование решающих правил. Следует отметить, что задачи дискретизации и поиска минимального среза NP-сложны, что требует разработки эффективных эвристических алгоритмов для их решения. Таким образом, исследование и разработка алгоритмов обобщения,

{ БИБЛИОТЕКА

09 яг/ ми" » /,

1ьлми1»я

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

Объектом исследования работы являются методы обобщения понятий. Предметом исследования - методы обобщения, основанные на теории приближенных множеств.

Цель работы заключается в разработке алгоритма обобщения, способного обрабатывать реальные массивы данных и основанного на теории приближенных множеств.

Поставленная задача потребовала решения следующих проблем:

1. Разработка эффективного эвристического алгоритма дискретизации непрерывных областей значений признаков.

2. Разработка эффективного алгоритма выбора существенных атрибутов, совмещенного с этапом дискретизации.

3. Разработка модифицированной стратегии применения решающих правил для классификации ранее неизвестных объектов.

4. Разработка и программная реализация системы обобщения понятий на основе предлагаемого алгоритма обобщения.

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

Достоверность научных результатов подтверждена теоретическими выкладками, данными компьютерного моделирования, результатами экспериментов, а также сравнением полученных результатов с результатами, приведенными в научной литературе.

Научная новизна исследования состоит в следующем:

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

2. Разработан эффективный эвристический алгоритм дискретизации непрерывных областей значений атрибутов.

3. Разработан алгоритм выбора существенных атрибутов, совмещенный с этапом дискретизации, что позволяет избежать разбиения на интервалы непрерывных областей значений несущественных признаков.

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 страницу машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, её научная новизна и практическая значимость, сформулирована цель работы и приведено краткое содержание диссертации по главам.

В первой главе формализуется задача обобщения понятий и рассматриваются основные способы представления знаний в системах извлечения и обоб-

щения понятий. Анализируются проблемы, возникающие при извлечении и обобщении знаний, и предлагаются способы их преодоления. Дается обзор основных подходов к обобщению и сравниваются возможности их применения к реальным массивам данных.

Под обобщением понимается переход от рассмотрения единичного объекта х или некоторой совокупности объектов Хк рассмотрению множества объектов Жтакого, что х е ЖпляХа W. В качестве объекта может рассматриваться реальный физический объект, реализация некоторого процесса или явления. Подразумевается, что все объекты множества W обладают некоторыми общими свойствами.

Для описания объекта используются признаки Дь .....О-ь называемые далее атрибутами. Каждый объект х е X характеризуется набором конкретных значений этих признаков (атрибутов): x={v¡, ...5v*}> где v, - значение /-го признака. Такое описание объекта называют признаковым описанием; признаками могут служить цвет, размер, возраст, форма, вес, цена, прибыль и т.п.

В основе процесса обобщения лежит сравнение описаний исходных объектов, заданных совокупностью значений признаков, и выделение наиболее характерных фрагментов этих описаний. Этот процесс получил также название индуктивного формирования понятий.

Множество объектов W, которому соответствует понятие, называется объемом понятия. В зависимости от того, входит или не входит объект в объем некоторого понятия, он называется положительным или отрицательным объектом для этого понятия.

Задача индуктивного формирования понятий, называемая также задачей обобщения понятий по признакам, состоит в том, чтобы, на основе анализа обучающей выборки U, построить понятие, позволяющее с помощью некоторого правила распознавания правильно разделить все положительные и отрицательные объекты множества обучающей выборки U.

Свяжем с множеством U следующие понятия. Пусть U = {хь хг.....х„} —

непустое конечное множество объектов. - непустое конечное множество атрибутов. Для каждого атрибута известно множество Va , которое называется множеством значений атрибута а. Обозначим с помощью а(х) конкретное значение атрибута а для объекта x€U. При решении задачи обобщения бывает необходимо получить описание понятия, заданного значением одного из атрибутов. Обозначим такой атрибут d и назовем его далее решением или решающим атрибутом. Атрибуты, входящие в А, называются условными атрибутами. Количество возможных значений решающего атрибута d называется рангом решения и обозначается как r(d). Множество значений решения будем обозначать Vj ={v1d,Vj.....vr<,d)}- Решающий атрибут d

определяет разбиение U на классы

\<i<r(d). Иногда вместо CuC2,...,CrW будем писать .

В общем случае понятие, сформированное на основе обучающего множества U, является приближением к понятию множества X, причем степень близости

этих понятий зависит от представительности обучающей выборки, т.е. от того, насколько полно в ней отражены особенности множествах

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

При извлечении и обобщении знаний, хранящихся в реальных массивах данных, возникают следующие проблемы:

• Данные являются разнородными (количественными, качественными, структурными).

• Реальные базы данных, как правило, велики, а потому алгоритмы экспоненциальной сложности могут оказаться неприемлемыми.

• Информация, содержащаяся в реальных массивах данных, может быть неполна, избыточна, искажена, противоречива, а также некоторые значения ряда атрибутов могут вовсе отсутствовать. Поэтому для построения классификационных правил следует использовать только существенные атрибуты.

• Получаемые результаты должны быть конкретны и понятны человеку. Были предложены способы преодоления этих проблем. Описаны методики проверки классификационной модели, такие как перекрестная проверка, проверка исключением одного примера и метод бутстрепа.

Проведен сравнительный анализ ряда подходов к решению задачи обобщения. При этом основным критерием являлось их соответствие изложенным выше требованиям. В результате анализа рассмотренных подходов был сделан вывод, что наиболее предпочтительным является подход, основанный на теории приближённых множеств. Он способен удачно справляться с противоречивой и неполной информацией, свойственной реальным массивам данных. Получаемые в результате работы решающие правила удобны для восприятия человеком и позволяют описывать широкий класс скрытых закономерностей. Однако большинство алгоритмов, базирующихся на теории приближенных множеств, имеют недостаток, связанный с высокой вычислительной сложностью. В следующих главах будут изложены пути устранения этого недостатка и предложен эффективный алгоритм обобщения, основанный на данном подходе.

Во второй главе рассматривается подход к решению задачи обобщения, который основан на теории приближенных множеств. Рассмотрены основные понятия теории приближенных множеств. Показано, как методы приближенных множеств могут быть использованы для классификации объектов. Для этих целей вводятся следующие понятия.

Под информационной системой понимается пара § = (£/,/1), где и = {х^,хг,...,хп} - непустое конечное множество объектов, называемое обучающим множеством или универсумом, а А = {а], аг.....а— непустое конечное множество атрибутов.

Решающая таблица (илирешающая система) - это информационная система вида § = (£/, Ли {if}), где diA - выделенный атрибут, называемый решением илирешающим атрибутом, А — множество условных атрибутов.

Пусть BçzA. Отношение неразличимости по В определяется следующим образом: IND{B) = {(х,у) е UxU: УаеВ (а(х) = а(у))}. Обозначим все множество классов эквивалентности отношенияINDÇB) как {Xf, X*,..., X* }.

Тогда мы можем приближенно определять произвольные подмножества (классы) объектов XçzU путем построения нижнего и верхнего приближений X, обозначаемых ВХ и ВХ соответственно:

Таким образом, под нижним приближением множества Xпонимается объединение классов эквивалентности отношения неразличимости, которые входят в X А под верхним приближением множества X понимается объединение классов эквивалентности, часть объектов которых принадлежит X.

Пара <ВХ, ВХ> составляет приближенное множество.

Множество BNb(X) = ВХ\ВХ называется граничной (или недостоверной) областью множества X. Множество U \ВХсостоит из отрицательных объектов.

Приближенные множества могут быть использованы для классификации объектов следующим образом.

Описание ВС -> С,

Описание U\ ВС -» -¡С, Описание ВС\ ВС -» возможно С,

где описание множества включает набор характерных атрибутов, С - некоторый класс решения.

Множество включает объекты, гарантированно

относящиеся к одному из классов решения, и называется положительной областью решающей системы §.

Обобщенным решением объекта х является множество решений объектов, входящих в тот же класс эквивалентности отношения IND(B), что и объект х:

ôB(x) = {v<=Vd :Зх' е U ((*',*) е IND(B) л d(x') = v)}.

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

В общем виде работа алгоритма, основанного на теории приближенных множеств, состоит из следующих шагов: поиск классов эквивалентности отношения неразличимости, поиск верхнего и нижнего приближений, поиск среза решающей системы и построение набора решающих правил. Кроме то-

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

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

Довольно часто информационная система имеет более одного среза. Поэтому естественным является вопрос выбора наилучшего среза. Как правило, выбирают наиболее короткий срез. Однако проблема поиска такого среза является NP-сложной. Существует ряд подходов к ее решению.

Одна из первых идей состояла в том, чтобы рассматривать в качестве важных признаков те признаки, которые содержатся в пересечении всех срезов информационной системы. Другой подход связан с динамическими срезами, т.е. множествами условных атрибутов, «достаточно часто» встречающихся среди срезов подвыборок первоначальной решающей таблицы. Атрибуты, принадлежащие «большинству» динамических срезов считаются существенными. Значения порогов для понятий «достаточно часто» и «большинство» должны выбираться на конкретных данных. Третий подход основан на введении понятия значимости атрибутов, что позволяет посредством вещественных значений из замкнутого интервала [0,1] отразить, насколько важным является тот или иной атрибут в решающей таблице.

Этап дискретизации необходим для большинства современных алгоритмов обобщения. Под дискретизацией мы будем понимать преобразование непрерывной области значений атрибута в дискретную. Например, температура тела человека, которая обычно измеряется с помощью вещественных чисел, может быть разделена на несколько интервалов, соответствующих, например, пониженной, нормальной, повышенной и высокой температуре. Выбор подходящих интервалов и разбиение непрерывных областей значений атрибутов - сложная проблема, сложность которой возрастает в экспоненциальной зависимости от числа атрибутов, к которым должна быть применена дискретизация.

Приведем постановку задачи дискретизации. Пусть - непро-

тиворечивая решающая система. Будем предполагать, что область значений любого атрибута является вещественным интервалом, т.е. Любую пару вида ра=(а,с), где аеА и се Я, будем называть делением на области Уа. Для каждого атрибута а множество Ра = {Р\,Р1,—,Р1(1}, где р" - деления атрибута а, будем называть множеством делений атрибута а. Полное множество делений Р определяется как Ра.

Любое множество делений Р на основе исходной решающей системы определяет новую решающую систему где Ар={ар: аеА} и аР(х)=1 о а(х)е[с,я,с°+|) для любого объекта хеС/и /е{0......

Решающую таблицу Б'' называют дискретизацией таблицы § на основе мно-

жества делений Р. Наша цель состоит в тем, чтобы в процессе дискретизации построить такое множество делений Р.

Очевидно, что можно построить неограниченное количество множеств делений. Для поиска множества делений с минимальным числом элементов введем следующие понятия.

Два множества делений Р и Р' будем считать эквивалентными, если . Будем говорить, что множество делений Рявляется непротиворечивым для если обобщенные решения систем § и равны, т.е. 38(х) =

Ухе и. Непротиворечивое для В множество делений Ргг будем называть несократимым для Б, если никакое его собственное подмножество не является непротиворечивым для 5. И, наконец, непротиворечивое множество делений Р°р' будем называть оптимальным для §,если оно обладает минимальной мощностью среди непротиворечивых для § множеств делений.

Задача нахождения оптимального множества делений Р для данной решающей системы Б является iVP-сложной. Этот факт ясно говорит о важности создания эффективных эвристических алгоритмов поиска субоптимального множества делений.

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

следующим образом.

Пусть § = (СУ,Ли{с/}) - исходная решающая таблица. Произвольный атрибут определяет последовательность =

{а(х): хеЩ и па<п. Объектами новой решающей таблицы 8* являются все пары объектов из § с различными решениями, а множество условных атрибутов определяется делениями областей значений атрибутов исходной решающей

таблицы, т.е. А* = [Л^,"-р"= (а, с",\ гДе с" =(у° +уД,)/2, 1 <г <па-1|. Эти атасА

рибуты будут бинарными. Множество А* называют начальным множеством делений. Мы будем говорить, что деление р" — (сг,с;а) различает объекты х и у из разных классов решений, если Значение

нового атрибута, соответствующего делению для пары равно 1, если с помощью этого деления различаются объекты х и у, и 0 в противном случае. Кроме того, к объектам новой решающей таблицы добавляется еще один объект X, для которого все условия и решение d* будут иметь значение 0. Для всех остальных объектов новой решающей таблицы значение нового решения равно 1. Срезы новой решающей таблицы §* определяют все несократимые множества делений исходной решающей таблицы

На основе этой общей схемы и строятся эвристические алгоритмы, находящие субоптимальное множество делений. Был дан сравнительный анализ ряда алгоритмов дискретизации. На практике довольно часто используется алгоритм дискретизации, основанный на прямой реализации стратегии Джонсона. Вы-

числительная сложность этого алгоритма равна 0(\Р\-кпг), что делает его неприменимым для обработки больших баз данных. Также исследованы алгоритмы дискретизации, которые базируются, соответственно, на понятии динамического среза и на идее итерационного вычисления количества пар объектов, различимых делением. Показано, что главной проблемой этапа дискретизации непрерывных атрибутов является его высокая вычислительная сложность. Поэтому в третьей главе предложен эвристический алгоритм дискретизации, который направлен на снижение затрат времени и памяти.

В третьей главе, опираясь на выявленные достоинства и недостатки рассмотренных ранее алгоритмов, предлагается их модификация - алгоритм, предназначенный для обработки реальных массивов данных. При этом учитываются такие особенности информации, хранящейся в реальных массивах данных, как большой объем, а также неполнота и противоречивость данных. Представлены результаты тестирования разработанного алгоритма на наборах данных из известного хранилища UCI Machine Learning Repository, проведено их сравнение с результатами других известных алгоритмов обобщения.

Разработанная модификация направлена на снижение затрат времени и памяти при сохранении высокого качества классификации, а также на обработку неполных и противоречивых данных. При этом были решены следующие задачи:

1. Задача разработки эффективного эвристического алгоритма дискретизации непрерывных областей значений признаков.

2. Задача разработки эффективного алгоритма выбора существенных атрибутов, совмещенного с этапом дискретизации.

3. Задача разработки модифицированной стратегии применения решающих правил для классификации ранее неизвестных объектов.

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

Были сформулированы и доказаны две теоремы, которые лежат в основе предлагаемого алгоритма дискретизации. Для их изложения введем ряд обозначений.

Пусть pi = (а,с")еА* - некоторое деление атрибута а, где яеА и 1 <t<na, и X C.U - некоторое подмножество обучающего множества. Тогда обозначим:

• Wx(p°) — число пар объектов из X, различимых с помощью деления р°;

• Iх {р") и гх(р°) - количество объектов из X, имеющих значение атрибута а, меньшее (большее) с";

• и гх(р°) — количество объектов из X, имеющих значение атрибута а, меньшее (большее) с,", и принадлежащих q-му классу решения, где

• №х(р%р°+,)— число объектов из X, значения атрибута а которых лежат в интервале (с",^",);

• - число объектов из X, значения атрибута а которых лежат в интервале (с,и принадлежащих д-му классу решения, где

• №Р(р) - количество пар объектов, не различимых делениями из Р, но различимых делениями из Р и {р}.

Первая теорема позволяет вывести значение 1Рх(рЦ,) из УУх(р°), где р° и рам - два последовательных деления области значений атрибута а.

Теорема 1. Пусть множеству X с: и принадл еж^^о/Й^ е к т о в , значения атрибута а которых лежат в интервале Тогда:

Вторая теорема применима для случая, когда в процессе дискретизации у нас имеется множество делений Р^А*, определяющее классы эквивалентности Х\,Хг, ...,Хт отношения неразличимости ШЕ>{АР) таблицы и два последовательных деления атрибута а. Тогда мы можем вычислить значение зная Т¥г(р°), следующим образом: Теорема 2. Пусть имеется К классов эквивалентности Хщ,Ха1,...,Хак, каждому из которых принадлежит объектов, значения атрибута а которых лежат в интервале Тогда:

Далее разработанный алгоритм представлен по шагам. Назовем его обобщенным итерационным алгоритмом дискретизации (Generalized Iterative algorithm for Discretization, GID).

Алгоритм 1. Алгоритм GID.

Вход: Непротиворечивая решающая таблица S.

Выход: Субоптимальное множество делений Р.

Используемые структуры данных: Р — субоптимальное множество делений, L = [IND[AP)\ - множество классов эквивалентности отношения неразличимости таблицы SP;A* - множество возможных делений.

1. Р:=0; L :={[/}; А* := начальное множество делений;

2. Для каждого атрибута аеА выполнить:

начало

Для всех Х,е£ выполнить:

Для каждого деления выполнить:

Для всех классов Ха , объекты которых имеют значение атрибута а из интервала вычислить Найти WP(Pj) в соответствии с теоремой 2. Пересчитать значения г*"' ,1х'' и гХ°' ,1х'' по теореме 1. конец;

3. Взять в качестве ртт деление с максимальным значением Wf(p) среди всех делений р из А*.

4. Присвоить Р:=Ри{раш}; А*:=А*\{ртк);

5. Для всех XeL выполнить:

Если Ртах разделяет множество Xh&Xi иХг, то удалить ХЙЗ L Идо-бавить в L два множества

6. Если все множества в L состоят из объектов, принадлежащих единственному классу решения, то шаг 7, иначе перейти к шагу 2.

7. Конец.

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

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

Помимо этого, в качестве существенных признаков мы будем рассматривать признаки, входящие в приблизительные срезы достаточно высокого качества.

Понятие приблизительного среза представляет собой обобщение понятия среза, рассмотренного ранее. Любое подмножество В множества А может быть рассмотрено как приблизительный срез множества А, а величину

будем называть ошибкой аппроксимации среза. Здесь величина dep(B, d) представляет собой меру зависимости между

Ошибка аппроксимации среза показывает, насколько точно множество атрибутов В аппроксимирует множество условных атрибутов А (относительно d).

Применение идеи приблизительных срезов полезно при обработке противоречивых и зашумленных данных. В то же время, это может позволить увеличить точность классификации тестовых данных. Уровень ошибки аппроксимации среза можно задать так, чтобы достичь этого эффекта.

Таким образом, разработанный алгоритм поиска существенных атрибутов основан на двух идеях: 1) совмещение дискретизации количественных признаков с поиском существенных атрибутов, 2) поиск не среза, а его приближения.

Представим шаги разработанного алгоритма. Назовем его обобщенным итерационным алгоритмом поиска существенных атрибутов, основанным на подходе приближенных множеств (Generalized Iterative algorithm based on the Rough Set approach, GJRS).

Алгоритм 2. Алгоритм GIRS.

Вход: Решающая таблица §; Максимальная величина ошибки аппроксимации среза Б«».

Выход: Субоптимальное множество делений Р и приблизительный срез R. Используемые структуры данных: L — [IND(AP)] - множество классов эквивалентности отношения неразличимости таблицы - множество возможных свойств (т.е. делений и дискретных атрибутов).

{начальное множество делений} {множество дискретных атрибутов};

2. Для каждого непрерывного атрибута а е А выполнить:

Для каждого деления = (а,с°) еА* выполнить:

Для всех классов Ха , объекты которых имеют значение атрибута а из интервала (Cj_itCj), вычислить NX°' и N. Найти fVp(Pj) в соответствии с теоремой 2. Пересчитать значения по теореме 1.

3. Для каждого дискретного атрибута аеА рассчитать WR(a) - количество пар объектов, различимых атрибутом а.

4. Взять в качестве ртт свойство, т.е. деление р=(а,с) или атрибут а, с максимальным значением Wt{p) или WR(a) среди всех свойств из А*.

5. Присвоить R:=R^j{pmx)\A*:-A*\{pmw}\ если ртт - деление непрерывного атрибута, то P'.= P^j{p„wi}',

6. Для всех X е L выполнить:

Если ртт - деление и разделяет множество Хна.Х] иЛ^, то удалить X из L и добавить в L два множества Если - дискретный атрибут, то L := [INDX> (PmilJ] и... и [Ж/" (Рпих)].

7. Если отношение количества объектов, не различимых с помощью R, к общему числу объектов в Uменьше етах, то шаг 8, иначе шаг 2.

8. Конец.

Как показывают проведенные эксперименты, разработанный алгоритм, позволяет значительно сократить время поиска существенных атрибутов.

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

В предложенной процедуре решение о том, к какому классу отнести объект, принимается на основе трех параметров: достоверность, поддержка решающего правила и длина его условной части. Достоверность решающего правила - это отношение количества объектов, правильно классифицированных с помощью данного правила, к числу объектов, подпадающих под левую часть правила. Длина условной части — количество пар вида «атрибут=значение» в условной части правила. Поддержка решающего правила определяется как количество объектов, подтверждающих это правило. Тогда модифицированная стратегия применения решающих правил будет выглядеть следующим образом:

Модифицированная стратегия применения решающих правил_

1. Когда на вход классификатора поступает новый пример, то множество правил просматривается с целью найти применимые достоверные правила, т.е. правила, достоверность которых равна 1 и посылки которых соответствуют примеру.

2. Если никакое правило не найдено, то переход к п.4.

3. Если найдено более одного правила, то принять классификацию, выдаваемую каждым найденным правилом R, с весом равным Поддержка(К)-Длина(К). В результате выбрать класс с наибольшим суммарным весом по всем найденным правилам.

4. Найти решающие правила, достоверность которых превышает пороговое значение MinConf. Принять классификацию, выдаваемую каждым найденным правилом R, с весом равным МЕ(К)-Поддержка(К)Достоверность(К)-Длта(К), где MF(R) - коэффициент совпадения правила R с классифицируемым объектом. Определяется он как отношение количества совпадающих пар «атри-бут=значение» в классифицируемом объекте и решающем правиле R. В результате выбрать класс с наибольшим суммарным весом по всем найденным правилам._

Как показывают эксперименты на тестовых данных, в большинстве случаев предложенная процедура позволяет увеличить точность классификации.

Представлены результаты экспериментов, выполненных на следующих четырех группах данных из известной коллекции тестовых наборов данных Калифорнийского университета информатики и вычислительной техники UCI Machine Learning Repository:

1. Данные «задач монахов» (Monk's problems).

2. Медицинские данные, относящиеся к сердечным заболеваниям и гепатиту.

3. Репозиторий данных проекта StatLog: диабет и австралийский кредит.

4. Другие наборы данных (из области биологии и судебно-следственной практики).

В табл. 1 приведены результаты сравнения точности классификации разработанного алгоритма с другими известными алгоритмами обобщения.

Таблица 1

Сравнение точности классификации разработанного алгоритма с другими известными алгоритмами обобщения

1T Jit г Набор данных, Точность классификации ¡,1** *•

ID3 •МО- Holte-II GIftS

Monk-1 81.25 75.70 100 100 100

Monk-2 65.00 69.91 99.70 81.9 83.10

Monk-3 90.28 97.20 93.51 97.2 95.40

Heart 77.78 77.04 77.04 77.2 78.72

Hepatitis н/д 80.80 н/д 82.7 84.51

Diabetes 66.23 70.84 71.09 н/д 81.00

Australian 78.26 85.36 83.69 82.5 88.71

Glass 62.79 65.89 66.41 37.5 70.10

Iris 94.67 96.67 95.33 94.0 96.24

Mushroom 100 100 100 100 100

Soybean 100 95.56 100 100 100

Среднее4^ 81.63 im.w Ш,бУ • i85:3 ; 88,89

На всех взятых для сравнения наборах данных разработанный алгоритм показал точность классификации не уступающую другим алгоритмам обобщения, а в ряде случаев и превосходящую ее. Средняя точность классификации составила примерно 88.9%. Следует отметить, что точность классификации, полученная с помощью нашего алгоритма, при решении большинства задач оказалась значительно выше точности классификации, достигнутой методами индукции решающих деревьев ID3, ID4, ID5R, С4.5, что объясняется невозможностью представления описания некоторых целевых понятий в виде дерева. Кроме того, можно отметить, что совмещение поиска существенных атрибутов и процедуры дискретизации очень полезно. Наиболее отчетливо это видно из результатов, полученных при решении задачи по австралийскому кредиту (набор данных «Australian»), что можно объяснить наличием в этих данных атрибутов как с непрерывными, так и с дискретными областями значений, а именно

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

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

Система состоит из главной программы и модулей, реализующих различные методы обобщения знаний (в настоящее время реализованы алгоритмы вШЗ, ГО3 и С4.5). Структура программной системы приведена на рис. 1.

Другие алгоритмы обобщения

Рис. 1. Структура программного комплекса

Программа выполняет следующие основные функции:

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

• По построенным решающим правилам производит распознавание (классификацию) объектов.

Основные возможности программы:

• работа с атрибутами, имеющими как дискретные, так и непрерывные области значений;

• обобщение объектов при неполной исходной информации об объектах путем построения двух систем решающих правил;

• классификация новых объектов. При неполноте информации о классифицируемом объекте программа позволяет получить результат классификации объекта в виде множества пар вида (Кр т,), где К, - класс, т] -оценка достоверности принадлежности объекта классу К/,

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

• использование в качестве обучающего множества таблиц баз данных. При этом возможна обработка таблиц с числом объектов до 30 000 и количеством атрибутов до 64.

В заключении приведены основные результаты, полученные в диссертационной работе.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

4. Разработан алгоритм, в котором этап выбора существенных атрибутов совмещен с этапом дискретизации, что позволяет избежать разбиения на интервалы непрерывных областей значений несущественных признаков.

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

6. Разработана и программно реализована система обобщения понятий, которая использует полученные теоретические результаты и создана на основе предложенных алгоритмов. Проведены эксперименты по сравнению эффективности созданной модификации с известными алгоритмами обобщения на тестовых наборах данных.

7. Разработанные алгоритмы и программные средства применены в динамической экспертной системе оперативной диагностики состояния экологи-

чески опасных объектов и производств «ДИЭКС» для повышения точности технической диагностики и эффективности прогнозирования ресурса оборудования, о чем имеется акт о внедрении.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Куликов А.В. Исследование алгоритмов обобщения, строящих деревья решений // Третья международная школа-семинар по искусственному интеллекту для студентов и аспирантов (Браславская школа- 1999): Сборник научных трудов. -Мн.: БГУИР, 1999. - С. 173-177.

2. Куликов А.В., Фомина М.В. Разработка алгоритма обобщения знаний // Тр. седьмой нац. конф. по искусственному интеллекту с междунар. участием (КИИ 2000). В 2 т. -Т.1. -М.: ФизМатЛит, 2000. -С.135-142.

3. Куликов А.В. Исследование и разработка алгоритмов извлечения и обобщения знаний в системах поддержки принятия решений // Радиоэлектроника, электротехника и энергетика: Тез. докл. шестой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. - Т. 1. - М.: МЭИ, 2000. -С.229-230.

4. Фомина М.В., Куликов А.В. Исследование алгоритмов извлечения и обобщения знаний // Международный форум информатизации - 2000: Доклады международной конференции «Информационные средства и технологии». В 3-х т. - Т.2. - М.: Станкин, 2000. - С.76-79.

5. Куликов А.В. Индуктивный вывод в системах поддержки принятия решений // Научная сессия МИФИ - 2001: Сборник научных трудов. В 14 т. - Т.З. -М.: МИФИ, 2001. -С.198-199.

6. Куликов А.В. Современные методы классификации // Радиоэлектроника, электротехника и энергетика: Тез. докл. седьмой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т.- Т.1.- М.: МЭИ, 2001.- С.260-261.

7. Куликов А.В. Исследование и разработка методов обобщения объектов по признакам // Научная сессия МИФИ - 2002: Сборник научных трудов. В 14 т. - Т.З. - М.: МИФИ, 2002. - С.161-162.

8. Куликов А.В. Исследование методов обобщения, основанных на теории приближенных множеств // Радиоэлектроника, электротехника и энергетика: Тез. докл. восьмой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. -T.I. -M.: МЭИ, 2002. - С. 277.

9. Куликов А.В. Алгоритмы обобщения, основанные на теории приближенных множеств // Научная сессия МИФИ - 2003: Сборник научных трудов. В 14 т. - Т.З. -М.: МИФИ, 2003. - С. 93-94.

10.Куликов А.В. Методы приближенных множеств в интеллектуальных системах // Радиоэлектроника, электротехника и энергетика: Тез. докл. девятой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. — Т.1. -М.: Изд. МЭИ, 2003. - С.295-296.

П.Куликов А.В. Использование методов приближенных множеств в области интеллектуального анализа данных // Молодежная науч.-техн. конф. «Наукоемкие технологии и интеллектуальные системы - 2003»: Сб. науч. трудов. В 2-хч.-4.1.-М.: МГТУ им. Н.Э.Баумана, 2003. - С.157-160.

20 №22 7 0 4

12.Куликов А.В. Этап дискретизации в решении задачи обобщения объектов с использованием теории приближенных множеств // Международный форум информатизации - 2003: Тр. междунар. конф. «Информационные средства и технологии». В 3-х т. - Т.1 - М: Янус-К, 2003. - С. 139-142.

13.Куликов А.В., Фомина М.В. Использование алгоритмов обобщения, основанных на теории приближенных множеств, в интеллектуальных системах // Тр. междунар. науч.-техн. конференций «Интеллектуальные системы (IEEE AIS'03)» и «Интеллектуальные САПР (CAD-2003)». Научное издание в 3-х т. - Т.1. - М.: ФизМатЛит, 2003. - С.357-362.

14.Куликов А.В. Разработка алгоритма обобщения, основанного на теории приближенных множеств и предназначенного для обработки реальных массивов данных. // Научная сессия МИФИ - 2004: Сборник научных трудов. В 14т.~Т.З.-М.:МИФИ,2004.-С. 180-181.

15.Куликов А.В. Разработка алгоритма обобщения на основе теории приближенных множеств // Радиоэлектроника, электротехника и энергетика: Тез. докл. десятой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. - Т.1. - М.: Изд. МЭИ, 2004. -С.319-320.

16.Куликов А.В. Разработка алгоритма обобщения информации, основанного на теории приближенных множеств // Молодежная науч.-техн. конф. «Наукоемкие технологии и интеллектуальные системы - 2004»: Сб. научных трудов. В 2-х ч. - Часть 1. - М.: МГТУ им. Н.Э.Баумана, 2004. -С. 157-160.

17.Куликов А.В., Фомина М.В. Разработка алгоритма обобщения понятий с использованием подхода, основанного на теории приближенных множеств / Труды шестой междунар. конф. по технологии программирования на основе знаний // Под. ред. В.Стефанюка и К.Каджири. - IOS Press, 2004. - С.261-268. - (на англ. яз.).

18.Куликов А.В., Фомина М.В. Разработка модификации алгоритма обобщения на основе теории приближенных множеств // Тр. девятой нац. конф. по искусственному интеллекту с междунар. участием (КИИ 2004). В 3-х т. - Т. 1. - М.: ФизМатЛит, 2004. - С.289-298.

19.Куликов А.В., Фомина М.В. Алгоритм индуктивного формирования понятий на основе подхода приближенных множеств // Международный форум информатизации - 2004: Тр. междунар. конф. «Информационные средства и технологии». В 3-х т. - Т.1. - М.: Янус-К, 2004. - С. 175-178.

20.Вагин В.Н., Куликов А.В., Фомина М.В. Методы теории приближенных множеств в решении задачи обобщения понятий // Известия РАН. Теория и системы управления. - 2004. - №6. - С.62-76.

Подписано в печать А Зак. Ч Тир. Ц'[' П. л.

Полиграфический центр МЭИ (ТУ) Красноказарменная ул., д.13

ВВЕДЕНИЕ.

ГЛАВА 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.1. Эксперименты на данных «задач монахов».

3.4.2. Медицинские данные.

3.4.3. Данные проекта StatLog.

3.4.4. Другие наборы данных.

3.5. Выводы.

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ.

4.1. Структура программного комплекса.

4.2. Основные функции, выполняемые программой.

4.3. Описание программы.

4.4. Примеры работы.

4.5. Выводы.

Диссертационная работа посвящена исследованию и разработке алгоритмов обобщения на основе теории приближенных множеств. Задача обобщения информации является одной из важных задач искусственного интеллекта. Благодаря применению методов обобщения информации в системах принятия решений возможно построение обобщенных моделей данных и обработка больших массивов экспериментальных данных, полученных в ходе различного рода процессов и явлений. Источники таких больших потоков данных имеются во многих областях. Общим для этих данных является то, что они содержат большое количество скрытых закономерностей, которые важны для принятия стратегических решений. Однако выявление этих закономерностей лежит за пределами человеческих возможностей главным образом из-за большого и все возрастающего объема данных. Поэтому для вывода таких закономерностей разрабатываются методы обобщения и компьютерные системы, реализующие эти методы. В качестве областей применения алгоритмов обобщения можно назвать медицину, биологию, маркетинг, банковскую деятельность, прогнозирование спроса, космические исследования и многое другое.

В настоящее время известен ряд алгоритмов, решающих задачу распознавания объекта по его признаковому описанию. Эти алгоритмы используют различные подходы к построению классификационных правил, такие как фокусировка [18, 47], индукция решающих деревьев (ID3 [43, 21], С4.5 [42], ID4 [45], ID5R [51, 52], CART [7, 21], ДРЕВ [3]), построение продукционных правил (семейство алгоритмов AQ [29, 30]), нейронные сети [44, 12], использование теории приближенных множеств [40, 36, 23, 41] и другие подходы [2, 20, 19]. Однако при обработке реальных массивов данных, которые характеризуются большим размером, неполнотой, противоречивостью и зашумленностью хранящейся информации, данные алгоритмы либо не пригодны вовсе, либо не всегда показывали удовлетворительные результаты, что привело к дальнейшим исследованиям в области применения методов обобщения для обработки реальных массивов данных. Одним из способов решения проблемы работы с неполной и противоречивой информацией является подход, основанный на теории приближенных множеств.

В работах [5, 38, 48] было показано, что использование теории приближенных множеств в алгоритмах обобщения позволяет существенно повысить точность классификации объектов. Важнейшими этапами в работе алгоритма обобщения, основанного на теории приближенных множеств, являются следующие: дискретизации непрерывных областей значений атрибутов, выделение значимых атрибутов (поиск срезов) и формирование решающих правил. Следует отметить, что задачи дискретизации и поиска минимального среза КР-сложны, что требует разработки эффективных эвристических алгоритмов для их решения. Таким образом, исследование и разработка алгоритмов обобщения, основанных на теории приближенных множеств и в то же время способных обрабатывать большие обучающие выборки за приемлемое время, является весьма актуальной задачей.

Объектом исследования работы являются методы обобщения понятий. Предметом исследования - методы обобщения, основанные на теории приближенных множеств.

Цель работы заключается в разработке алгоритма обобщения, способного обрабатывать реальные массивы данных и основанного на теории приближенных множеств.

Поставленная задача потребовала решения следующих проблем:

1. Разработка эффективного эвристического алгоритма дискретизации непрерывных областей значений признаков.

2. Разработка эффективного алгоритма выбора существенных атрибутов, совмещенного с этапом дискретизации.

3. Разработка модифицированной стратегии применения решающих правил для классификации ранее неизвестных объектов.

4. Разработка и программная реализация системы обобщения понятий на основе предлагаемого алгоритма обобщения.

В работе будет предложен оригинальный алгоритм дискретизации количественных атрибутов. Как отмечалось ранее, для выполнения дискретизации необходимы эффективные эвристические алгоритмы. Вычислительная сложность наиболее часто используемого алгоритма Джонсона имеет кубическую зависимость от количества объектов обучающей выборки, что делает его неприменимым для обработки больших баз данных. Предлагаемый эвристический алгоритм дискретизации направлен на снижение затрат времени и памяти. Он основан на стратегии Джонсона и развивает идею итерационного вычисления количества пар объектов, различимых делением, первоначально предложенную в [36], на случай произвольной решающей таблицы. Вычислительная сложность разработанного на основе этой идеи алгоритма дискретизации имеет линейную зависимость от количества объектов решающей таблицы.

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

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

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

Достоверность научных результатов подтверждена теоретическими выкладками, данными компьютерного моделирования, результатами экспериментов, а также сравнением полученных результатов с результатами, приведенными в научной литературе.

Научная новизна исследования состоит в следующем:

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

2. Разработан эффективный эвристический алгоритм дискретизации непрерывных областей значений атрибутов.

3. Разработан алгоритм выбора существенных атрибутов, совмещенный с этапом дискретизации, что позволяет избежать разбиения на интервалы непрерывных областей значений несущественных признаков.

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

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

Практическая значимость работы подтверждается использованием полученных результатов в динамической экспертной системе оперативной диагностики состояния экологически опасных объектов и производств «ДИЭКС» в ОАО «ЦНИИКА», о чем имеется акт о внедрении, а также применением на известном тестовом наборе данных Калифорнийского университета информатики и вычислительной техники UCI Machine Learning Repository, включающем реальные данные из различных сфер: медицины, экономики, биологии и др.

Реализация результатов. Результаты работы использованы в НИР, выполненных в рамках грантов РФФИ, проекты №99-01-00049 и №02-07-90042 по тематике «Исследование и разработка инструментальных средств создания экспертных систем семиотического типа» и в рамках Федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 годы по теме «Системы мониторинга и поддержки принятия решений на основе аппарата нетрадиционных логик».

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 7-й национальной конференции по искусственному интеллекту с международным участием КИИ-2000 (г.Переславль-Залесский, 2000 г.), Международной школе по искусственному интеллекту (Белоруссия, г. Минск, 1999 г.), пяти научно-технических конференциях МЭИ (ТУ) (2000, 2001, 2002, 2003, 2004 гг.), четырех научных сессиях МИФИ (2001, 2002, 2003 и 2004 гг.), на 9-й национальной конференции по искусственному интеллекту с международным участием КИИ-2004 (г.Тверь, 2004 г.), на международных форумах информатизации МФИ-2000, МФИ-2003 и МФИ-2004 (Международные конференции «Информационные средства и технологии» (г. Москва, 2000, 2003, 2004 гг.), на двух молодежных научнотехнической конференциях студентов, аспирантов и молодых ученых «Наукоемкие технологии и интеллектуальные системы» (г. Москва, 2003, 2004 гг.).

Публикации. Основные результаты, полученные по теме диссертационной работы, опубликованы в 20 печатных работах.

Рассмотрим структуру диссертационной работы подробнее.

В первой главе формализуется задача обобщения понятий и рассматриваются основные способы представления знаний в системах извлечения и обобщения понятий. Далее рассматриваются проблемы, возникающие при извлечении и обобщении знаний, и предлагаются способы их преодоления. Также в этой главе дается обзор основных подходов к обобщению и сравниваются возможности их применения к реальным массивам данных.

Во второй главе рассматривается подход к выполнению обобщения, который основан на теории приближенных множеств, вводятся основные понятия теории, исследуются этапы работы алгоритма, базирующего на данном подходе. Далее рассматривается ряд алгоритмов теории приближенных множеств, выявляются их сильные и слабые стороны.

В третьей главе, опираясь на выявленные достоинства и недостатки рассмотренных ранее алгоритмов, предлагается их модификация - алгоритм, предназначенный для обработки реальных массивов данных. При этом учитываются такие особенности информации, хранящейся в реальных массивах данных, как большой объем, а также неполнота и противоречивость данных. Представлены результаты тестирования разработанного алгоритма на наборах данных из известного хранилища UCI Machine Learning Repository [28], проведено их сравнение с результатами других эффективных алгоритмов обобщения.

В четвертой главе рассматривается реализация системы на основе предложенной модификации. Описывается структура, основные функции реализованного программного комплекса, а также его главные возможности.

Также представлено описание пользовательского интерфейса и приведены примеры работы программы.

4.5. Выводы

В этой главе была рассмотрена реализация программной системы на основе алгоритма обобщения, использующего разработанные алгоритмы дискретизации и поиска существенных признаков. Система формирует обобщенное правило в виде наборов решающих правил, а также производит распознавание объектов на базе предложенной стратегии применения решающих правил. При этом обобщение и классификация могут проводиться на неполной информации об объектах, что может выражаться в отсутствии ряда значений атрибутов для части объектов. Были представлены структура, основные функции реализованного программного комплекса и его главные возможности. Также были приведены примеры работы программы, в том числе на выборках из коллекции тестовых наборов данных UCI Machine Learning Repository [28].

Заключение

Целью диссертационной работы являлась разработка алгоритма обобщения, способного обрабатывать реальные массивы данных и основанного на теории приближенных множеств. При этом были получены следующие основные результаты:

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

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

3. Разработан эффективный эвристический алгоритм дискретизации непрерывных областей значений атрибутов, который расширяет идею, предложенную в [36] на случай произвольной решающей системы и имеет значительно более низкую вычислительную сложность, чем наиболее широко используемый алгоритм дискретизации.

4. Разработан алгоритм выбора существенных атрибутов, совмещенный с этапом дискретизации, что позволяет избежать разбиения на интервалы непрерывных областей значений несущественных признаков.

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

6. Разработана и программно реализована система обобщения понятий, которая использует полученные теоретические результаты и создана на основе предложенных алгоритмов. Проведены эксперименты по сравнению эффективности созданной модификации с известными алгоритмами обобщения на тестовых наборах данных.

Разработанные алгоритмы и программные средства применены в динамической экспертной системе оперативной диагностики состояния экологически опасных объектов и производств «ДИЭКС» в ОАО «ЦНИИКА» для повышения точности технической диагностики и эффективности прогнозирования ресурса оборудования.

Работа выполнена по тематике НИР кафедры ПМ по разработке интеллектуальных систем поддержки принятия решений семиотического типа (проект РФФИ № 02-07-90042).

По теме диссертации опубликовано 20 работ и сделано несколько выступлений на научно-технических конференциях:

1. Куликов A.B. Исследование алгоритмов обобщения, строящих деревья решений // Третья международная школа-семинар по искусственному интеллекту для студентов и аспирантов (Браславская школа - 1999): Сборник научных трудов. - Мн.: БГУИР, 1999. - С. 173-177.

2. Куликов A.B., Фомина М.В. Разработка алгоритма обобщения знаний // Труды седьмой национальной конференции по искусственному интеллекту с международным участием (КИИ 2000). В 2 т. - Т. 1. - М.: ФизМатЛит, 2000. - С. 135-142.

3. Куликов A.B. Исследование и разработка алгоритмов извлечения и обобщения знаний в системах поддержки принятия решений // Радиоэлектроника, электротехника и энергетика: Тез. докл. шестой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. - Т.1. - М.: МЭИ, 2000. - С. 229-230.

4. Фомина М.В., Куликов A.B. Исследование алгоритмов извлечения и обобщения знаний // Международный форум информатизации - 2000:

Доклады международной конференции «Информационные средства и технологии». В 3-х т. - Т.2. - М.: Станкин, 2000. - С.76-79.

5. Куликов A.B. Индуктивный вывод в системах поддержки принятия решений // Научная сессия МИФИ - 2001: Сборник научных трудов. В 14 т. - Т.З. Банки данных. Интеллектуальные системы. Программное обеспечение. - М.: МИФИ, 2001. - С. 198-199.

6. Куликов A.B. Современные методы классификации // Радиоэлектроника, электротехника и энергетика: Тез. докл. седьмой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. - Т.1. - М.: МЭИ, 2001. - С. 260261.

7. Куликов A.B. Исследование и разработка методов обобщения объектов по признакам // Научная сессия МИФИ - 2002: Сборник научных трудов. В 14 т. - Т.З. Интеллектуальные системы и технологии. - М.: МИФИ, 2002. - С.161-162.

8. Куликов A.B. Исследование методов обобщения, основанных на теории приближенных множеств // Радиоэлектроника, электротехника и энергетика: Тез. докл. восьмой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. - Т. 1. - М.: МЭИ, 2002. - С. 277.

9. Куликов A.B. Алгоритмы обобщения, основанные на теории приближенных множеств // Научная сессия МИФИ - 2003: Сборник научных трудов. В 14 т. - Т.З. Интеллектуальные системы и технологии. - М.: МИФИ, 2003. - С. 93-94.

Ю.Куликов A.B. Методы приближенных множеств в интеллектуальных системах // Радиоэлектроника, электротехника и энергетика: Тез. докл. девятой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. -Т.1. - М.: Изд. МЭИ, 2003. - С.295-296.

П.Куликов A.B. Использование методов приближенных множеств в области интеллектуального анализа данных // Молодежная научно-техническая конференция «Наукоемкие технологии и интеллектуальные системы

2003»: Сборник научных трудов. В 2-х ч. - Часть 1. - М.: МГТУ им. Н.Э.Баумана, 2003. - С.157-160.

12.Куликов A.B. Этап дискретизации в решении задачи обобщения объектов с использованием теории приближенных множеств // Международный форум информатизации - 2003: Труды международной конференции «Информационные средства и технологии». В 3-х т. - T.1 - М.: Янус-К, 2003. - С. 139-142.

1 З.Куликов A.B., Фомина М.В. Использование алгоритмов обобщения, основанных на теории приближенных множеств, в интеллектуальных системах // Труды международных научно-технических конференций «Интеллектуальные системы (IEEE AIS'03)» и «Интеллектуальные САПР (CAD-2003)». Научное издание в 3-х томах. - T.I. - М.: ФизМатЛит, 2003.- С.357-362.

14.Куликов A.B. Разработка алгоритма обобщения, основанного на теории приближенных множеств и предназначенного для обработки реальных массивов данных. // Научная сессия МИФИ - 2004: Сборник научных трудов. В 14 т. - T.3. Интеллектуальные системы и технологии. - М.: МИФИ, 2004. - С. 180-181.

15.Куликов A.B. Разработка алгоритма обобщения на основе теории приближенных множеств // Радиоэлектроника, электротехника и энергетика: Тез. докл. десятой междунар. науч.-техн. конф. студентов и аспирантов. В 3-х т. - Т. 1. - М.: Изд. МЭИ, 2004. - С.319-320.

16.Куликов A.B. Разработка алгоритма обобщения информации, основанного на теории приближенных множеств // Молодежная научно-техническая конференция «Наукоемкие технологии и интеллектуальные системы - 2004»: Сборник научных трудов. В 2-х ч. - Часть 1. - М.: МГТУ им. Н.Э.Баумана, 2004. - С.157-160.

17.Kulikov A., Fomina М. The Development of Concept Generalization Algorithm Using Rough Set Approach / Knowledge-Based Software

Engineering: Proceedings of the Sixth Joint Conference on Knowledge-Based Software Engineering (JCKBSE 2004) // V.Stefanuk and K. Kajiri (eds). - IOS Press, 2004. - pp.261-268.

18.Куликов A.B., Фомина M.B. Разработка модификации алгоритма обобщения на основе теории приближенных множеств // Труды девятой национальной конференции по искусственному интеллекту с международным участием (КИИ 2004). В 3-х т. - Т.1. - М.: ФизМатЛит, 2004. - С.289-298.

19.Куликов A.B., Фомина М.В. Алгоритм индуктивного формирования понятий на основе подхода приближенных множеств // Международный форум информатизации - 2004: Труды международной конференции «Информационные средства и технологии». В 3-х т. - Т.1. - М.: Янус-К, 2004. - С.175-178.

20.Вагин В.Н., Куликов A.B., Фомина М.В. Методы теории приближенных множеств в решении задачи обобщения понятий // Известия РАН. Теория и системы управления. - 2004. - №6. - С.62-76.

В заключение хотелось бы выразить свою благодарность за оказанное содействие в процессе работы над диссертацией, за обеспечение необходимыми теоретическими материалами и за общую организацию работы своему научному руководителю — доктору технических наук, профессору кафедры ПМ института АВТ МЭИ Вагину Вадиму Николаевичу и кандидату технических наук, доценту Фоминой Марине Владимировне.

1. Бонгард М.М. Проблема узнавания. М.: Наука, 1967. - 320 с.

2. Вагин В.Н., Гулидова В.Г., Фомина М.В. Распознавание состояний сложного объекта при неполной входной информации. Техническая кибернетика, 1992. - №5. - С. 120-132.

3. Вагин В.Н. Дедукция и обобщение в системах принятия решений. М.: Наука, 1988.-384 с.

4. Гладун В.П. Эвристический поиск в сложных средах. Киев: Наукова думка, 1977.-206 с.

5. Berzal F., Cubero J.C., Sanchez D., Serrano J.M. ART: A Hybrid Classification Model // Machine Learning, 2004. Vol. 54. - № 1. - P. 67-92.

6. Breiman L., Friedman J.H., Olshen R.A., Stone C.J. Classification and Regression Trees. Monterey: Wadsworth and Books, 1984. - 368 p.

7. Dietterich T.G., Michalski R.S. Inductive Learning of Structural Descriptions: Evaluation Criteria and Comparative Review of Selected Methods // Artificial Intelligence, 1981. Vol. 16. - P. 251-294.

8. Dietterich T.G., Michalski R.S. A Comparative Review of Selected Methods for Learning from Examples // Machine Learning: An Artificial Intelligence

9. Approach. / Michalski R.S., Carbonell J., Mitchell T.M., (Eds.). Chapter 3. -Palo Alto: Tioga Press, 1983. - P. 41-82.

10. Efron B., Tibshirani R. J. An Introduction to the Bootstrap. New York: Chapman and Hall, 1993. - 456 p.

11. Halgamuge S. K., Glesner M. Neural networks in designing fuzzy systems for real world applications // Fuzzy Sets and Systems, 1994. №65. - P. 1-12.

12. Haussler D. Learning Conjunctive Concepts in Structural Domains // Machine Learning, 1989. Vol. 4. - P. 7-40.

13. Hayes-Roth F., McDermott J. Knowledge Acquisition from Structural Descriptions // Proceedings of 5th International Joint Conference on Artificial Intelligence. Cambridge, MA, 1977. - P. 356-362.

14. Holsheimer M., Siebes A. Data mining: the search for knowledge in databases / Technical Report CS-R9406, CWI, 1994. 78 p.

15. Hu X. Knowledge Discovery in Databases: Attribute-Oriented Rough Set Approach. PhD thesis Canada, Regina, University of Regina, 1995.

16. Hutchinson A. Algorithmic Learning. Oxford: Clarendon Press, 1994. -460 p.

17. Janikow C.Z., Fajfer M. Fuzzy Partitioning with FID3.1 // Proceedings of the 18th International Conference of the North American Fuzzy Information Society. June 10-12, 1999, New York. N.Y.: IEEE Press, 1999. - P.467-471.

18. Janikow C.Z. Fuzzy Decision Trees: Issues and Method // IEEE Transactions on Systems, Man and Cybernetics, 1998. Vol. 28. - Issue 1. - P.1-14.

19. Kohavi R., Quinlan J.R. Decision-tree discovery // Handbook of Data Mining and Knowledge Discovery / Will Klosgen, Jan M. Zytkow (Eds.). Chapter 16.1.3. - Oxford University Press, 2002. - P. 267-276.

20. Kohavi R., Frasca B. Useful Feature Subsets and Rough Set Reducts. // Proceedings of the third international workshop on rough sets and soft computing (RSSC'94). San Jose, California, 1994. - P. 310-317.

21. Komorowski J., Pawlak Z., Polkowski L., Skowron A. Rough Sets: A Tutorial // Rough Fuzzy Hybridization A New Trend in Decision Making. / Pal S.K., Skowron A. (Eds.). - Singapore: Springer-Verlag, 1999. - P. 3-98.

22. Langley P., Bradshaw G., Simon H.A. Rediscovering chemistry with the BACON system // Machine Learning: An Artificial Intelligence Approach / R.S. Michalski, J.G. Carbonell, T.M. Mitchell (Eds.). Palo Alto, CA: Tioga Press. -1983. - P.307-330.

23. Langley P., Simon H.A., Bradshaw G.L., Zytkow J.M. Scientific Discovery: Computational Explorations of the Creative Process. Cambridge, MA: MIT Press, 1987.-344 p.

24. Lenat D.B. On automated scientific theory formation: a case study using the

25. AM program. / J.E. Hayes and D. Michie (editors). // Machine Intelligence, 1981. Vol. 9. - N.Y.: Horwood. - P.251 -283.

26. Lindsay R.K., Buchanan B.G., Feigenbaum E.A., Lederberg J. DENDRAL: A Case Study of the First Expert System for Scientific Hypothesis Formation. -Artificial Intelligence, 1993. №61. - P. 209-261.

27. Merz C.J., Murphy P.M. UCI Repository of Machine Learning Datasets. -Information and Computer Science University of California, Irvine, CA, 1998. Режим доступа: http://www.ics.uci.edu/~mlearn/MLRepository.html.

28. Michalski R., Wnek J. Constructive Induction: An Automated Improvement of Knowledge Representation Spaces for Machine Learning // The Second International Workshop on Intelligent Information Systems. Augustow, Poland, June 7-11,1993.-P. 188-236.

29. Michie D., Spiegelhalter DJ., Taylor C.C. Machine Learning, Neural and Statistical Classification. N.Y.: Ellis Horwood, 1994.

30. Mitchell T.M. Version Spaces: A Candidate Elimination Approach to Rule Learning // Proceedings of 5th International Joint Conference on Artificial Intelligence. Cambridge, MA, 1977. - P.305-310.

31. Mitchell T.M. An Analysis of Generalization as a Search Problem // Proceedings of the 6th IJCAI Conference. Tokyo, Japan, 1979. P.577-582.

32. Nguyen H.S., Skowron A. Quantization of real value attributes // Proceedings of the Second Annual Joint Conference on Information Sciences (JCIS'95) // Wang P.P. (ed.). Wrightsville Beach, North Carolina, USA, 1995. - P.34-37.

33. Nguyen H.S., Nguyen S.H. Discretization methods in data mining // Rough Sets in Knowledge Discovery 1: Methodology and Applications / Polkowski L. and Skowron A. (Eds.). Heidelberg: Physica-Verlag, 1998. - P.451-482.

34. Nguyen S., Nguyen H. Pattern extraction from data. Fundamenta Informaticae, 1998. - Vol. 34. - № 1-2. - P. 129-144.

35. Nilsson N.J. Introduction to Machine Learning // Department of Computer Science, Stanford University, 1999. Режим доступа: http://robotics.stanford.edu/ people/ nilsson/ mlbook.html.

36. Pawlak Z. Rough Sets // International Journal of Information and Computer Science, 1982.-№ 11(5).-P. 341-356.

37. Pawlak Z. Rough sets and intelligent data analysis // Information Sciences, Elsevier Science, 2002. Vol. 147. - № 1-4. - P. 1-12.

38. Quinlan J.R. C4.5: Programs for Machine Learning. San Mateo, CA: Morgan Kaufmann Publishers, 1993.

39. Quinlan J.R. Induction of Decision Trees // Machine Learning, 1986. № 1 -P.l-81.

40. Schlimmer J.C., Fisher D. A Case Study of Incremental Concept Induction // Proceedings of the 5th National Conference on Artificial Intelligence. Philadelphia, PA. In 2 volumes. Vol. 1. - San Mateo: Morgan Kauffman Publishers, 1986. -P.496-501.

41. Skowron A., Rauszer C. The Discernibility Matrices and Functions in Information Systems // Intelligent Decision Support Handbook of Applications and Advances of the Rough Sets Theory / R. Slowinski (Ed.). - Kluwer, 1992. -P.331-362.

42. Stepaniuk J. Optimizations of Rough Set Model // Fundamenta Informaticae, 1998. Vol. 36. - № 2-3. - P. 265-283.

43. Subramanian D., Feigenbaum J. Factorization in Experiment Generation 11 Proceedings of the 5th National Conference on Artificial Intelligence. Philadelphia, PA. In 2 volumes. Vol. 1. - San Mateo: Morgan Kauffman Publishers, 1986. -P.518-522.

44. Utgoff P.E. ID5: An Incremental ID3 // Proceedings of the Fifth International Conf. on Machine Learning. San Mateo: Morgan Kauffman Publishers, 1988. -P. 107-120.

45. Utgoff P.E. Incremental Induction of Decision Trees // Machine Learning, 1989.-№4.-P. 161-186.

46. Watanabe L., Elio R. Guiding Constructive Induction for Incremental Learning from Examples // Proceedings of the 10th IJCAI Conference. Milan, Italy, 1987. -P. 293-296.

47. Weiss S., Kulikowski C. Computer Systems that Learn. San Mateo: Morgan Kaufmann Publishers, 1991.-223 p.