авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 | 3 |

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

-- [ Страница 1 ] --

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

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

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

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

и компьютерных сетей

А В Т О Р Е Ф Е Р А Т

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

кандидата технических наук

Москва – 2004

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

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

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

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

профессор

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

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

профессор

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

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

и систем автоматизированного

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

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

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

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

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

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

диссертационного совета Д 212.157.01

кандидат технических наук,

профессор

И.И. Ладыгин

Общая характеристика работы

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

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





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

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

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

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

  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 или Х W. В качестве объекта может рассматриваться реальный физический объект, реализация некоторого процесса или явления. Подразумевается, что все объекты множества W обладают некоторыми общими свойствами.

Для описания объекта используются признаки a1, a2, …, ak, называемые далее атрибутами. Каждый объект х Х ха­рактеризуется набором конкретных значений этих признаков (атрибутов): х={v1, v2, …,vk}, где vi - значение i-го признака. Такое описание объекта называют признаковым описанием; призна­ками могут служить цвет, размер, возраст, форма, вес, цена, прибыль и т.п.

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

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

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

Свяжем с множеством U следующие понятия. Пусть U = {x1, x2, …, xn} – непустое конечное множество объектов. A = {a1, a2, …, ak} – непустое конечное множество атрибутов. Для каждого атрибута известно множество Va, которое называется множеством значений атрибута a. Обозначим с помощью a(x) конкретное значение атрибута a для объекта xU. При решении задачи обобщения бывает необходимо получить описание понятия, заданного значением одного из атрибутов. Обозначим такой атрибут d и назовем его далее решением или решающим атрибутом. Атрибуты, входящие в A, называются условными атрибутами. Количество возможных значений решающего атрибута d называется рангом решения и обозначается как r(d). Множество значений решения будем обозначать Vd ={}. Решающий атрибут d определяет разбиение U на классы , где Сi = {xU: d(x)=}, 1ir(d). Иногда вместо будем писать .

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

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

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

  1. Данные являются разнородными (количественными, качественными, структурными).
  2. Реальные базы данных, как правило, велики, а потому алгоритмы экспоненциальной сложности могут оказаться неприемлемыми.
  3. Информация, содержащаяся в реальных массивах данных, может быть неполна, избыточна, искажена, противоречива, а также некоторые значения ряда атрибутов могут вовсе отсутствовать. Поэтому для построения классификационных правил следует использовать только существенные атрибуты.
  4. Получаемые результаты должны быть конкретны и понятны человеку.

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

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

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

Под информационной системой понимается пара , где – непустое конечное множество объектов, называемое обучающим множеством или универсумом, а A = {a1, a2, …, ak} – непустое конечное множество атрибутов.

Решающая таблица (или решающая система) – это информационная система вида , где dA – выделенный атрибут, называемый решением или решающим атрибутом, А – множество условных атрибутов.

Пусть BA. Отношение неразличимости по В определяется следующим образом: IND(B) = {(x, y) UU: aB (a(x) = a(y))}. Обозначим все множество классов эквивалентности отношения IND(B) как {, ,…, }.

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

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

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

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

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

Описание C,

Описание U \ ¬C,

Описание \ возможно C,

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

Множество POSA(d) = AC1…ACr(d) включает объекты, гарантированно относящиеся к одному из классов решения, и называется положительной областью решающей системы .

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

.

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

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

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

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



Pages:   || 2 | 3 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.