ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 8, с. 1428-1454
УДК 519.6:519.710.24
ПРЕДСТАВЛЕНИЕ И ОБНАРУЖЕНИЕ ЗНАНИЙ В ЭКСПЕРТНЫХ СИСТЕМАХ ДЛЯ ЗАДАЧ РАСПОЗНАВАНИЯ ОБРАЗОВ1}
© 2007 г. О. М. Васильев, Д. П. Ветров, Д. А. Кропотов
(119992 Москва, Ленинские Горы, МГУ, ВМиК) e-mail: ovasiliev@inbox.ru; vetrovd@yandex.ru; dkropotov@yandex.ru Поступила в редакцию 01.09.2006 г.
Переработанный вариант 21.02.2007 г.
Предложен новый подход к проектированию нечетких экспертных систем. Подробно рассмотрены вопросы представления знаний и формирования высказываний средствами нечеткой логики, а также описана модель нечетких рассуждений. Основное внимание уделено вопросам автоматического получения знаний (нечетких правил вывода) по множеству прецедентов. В частности, введены различные критерии качества правил и предложен алгоритм их генерации (метод эффективных сужений). Описаны возможности расширения вида допустимых правил путем введения операции нечеткой дизъюнкции. Также исследованы возможности последующей оптимизации найденных правил. Представлены результаты экспериментов, демонстрирующие ценность предлагаемых подходов. Библ. 47. Фиг. 10. Табл. 2.
Ключевые слова: распознавание образов, поиск закономерностей в данных, нечеткая логика, экспертные системы.
ВВЕДЕНИЕ
Теория распознавания образов оперирует с задачами, связанными с предсказанием набора зависимых переменных по множеству независимых переменных, доступных для измерений и оценок, в ситуациях, когда известна некоторая эмпирическая информация об исследуемой взаимосвязи (см. [1, 2]). Для решения подобных задач разработано большое количество методов (см. [3]). Большинство из них (например, нейтронные сети, см. [4]) используют концепцию "черного ящика", т.е. просто выдают результат предсказания для данного набора признаков. Таким образом, связь между переменными внутри процесса остается неясной. Хотя для ряда задач одного прогноза оказывается достаточно, но зачастую возникают ситуации, когда необходимы дополнительные знания об исследуемом процессе (см. [5]). Последнее становится особенно актуальным в тех случаях, когда значения независимых переменных могут быть модифицированы исследователем. Тогда приходят к так называемой задаче data mining. После извлечения необходимых знаний можно вернуться к прогнозу зависимых переменных, принимая во внимание полученную информацию. В широком поле прикладных задач подобную дополнительную информацию получают при помощи экспертов данной прикладной области. В связи с этим необходимо, чтобы знания, извлекаемые автоматически при помощи компьютера в процессе data mining, были сформулированы в тех же терминах, что и информация, получаемая от экспертов. Таким образом, эксперт будет в состоянии оценить, добавить или отвергнуть часть полученной дополнительной информации. Системы подобного рода, в которых важную роль играют экспертные дополнительные знания об исследуемой области, получили название экспертных систем.
Исследования в области экспертных систем берут свое начало с середины 50-х годов прошлого столетия и уже пережили несколько этапов развития. За это время был реализован ряд успешных проектов по созданию экспертных систем, работающих на практике (см. [6, 7]). Однако большинство из них следует отнести к области нечеткого логического управления. Дело в том, что в задачах управления база знаний системы (совокупность управляющих правил) зачастую состоит из небольшого количества правил, непосредственно подсказываемых предметной областью. Поэтому основной проблемой при разработке таких систем становится реализация нечетких рассуждений или выводов. В этой области существует большое количество наработок,
1) Работа выполнена при финансовой поддержке РФФИ (коды проектов 05-07-90333, 06-01-00492, 06-01-08045, 07-0100211), ИНТАС (YS 04-83-2942, 04-77-7036) и программы ОМН РАН < 02.
которые приводят к успешным результатам (см. [8-10]). При построении экспертных систем, ориентированных на решение задач распознавания и прогнозирования, проблема построения базы данных (представления знаний в системе), организация базы знаний (получение знаний от экспертов предметной области) и получение модели вычисления прогноза играют ключевую роль. Необходимость решения комплекса сложных проблем приводит к ограниченному распространению экспертных систем распознавания и прогноза на сегодняшний день.
В области экспертных систем выделяют три основные проблемы:
1) представление знаний;
2) использование знаний;
3)приобретение знаний.
Наиболее естественной формой представления знаний является совокупность утверждений типа "ЕСЛИ..., ТО..." (см. [9]). При этом условия в посылке правила (антецеденте), а также в заключении правила (выводе) должны формулироваться достаточно просто, чтобы эксперт мог относительно легко проинтерпретировать то или иное правило. Для задач распознавания образов в качестве условий, входящих в правила, традиционно выбираются набор отрезков (значение признака лежит в определенном диапазоне a < x < b, см. [11, 12]) или совокупность нечетких подмножеств значений признаков (см. [13]). Нечеткие подмножества предоставляют возможность задавать правила на естественном языке, т.е. в форме, наиболее приближенной к представлению знаний эксперта. В настоящей статье исследуются различные способы представления знаний в виде совокупности нечетких подмножеств, рассматриваются вопросы генерации и оптимизации представления.
Использование знаний для прогнозирования, как правило, представляет собой различные схемы голосования по набору закономерностей (правил, см. [3, 11]). В случае представления знаний с помощью нечетких подмножеств здесь подключается развитый аппарат нечеткой логики. При этом в конечном итоге механизм нечеткого вывода также может быть проинтерпретирован с точки зрения схемы голосования (см. [6]). В статье рассматриваются различные способы голосования и настройки весов правил.
Наиболее трудоемкой является задача приобретения знаний. Для решения этой проблемы требуются как талант исследователя находить общий язык с экспертами, так и специальные автоматические алгоритмы извлечения знаний из эмпирической информации. Алгоритмы автоматической генерации знаний, как правило, связаны с решением многопараметрических оптимизационных задач, в которых целевая функция обладает большим количеством локальных оптиму-мов (см. [11]). Более того, в случае экспертных систем возникает ряд дополнительных требований к множеству искомых закономерностей. Среди них можно отметить следующие:
а) относительно небольшое количество информативных закономерностей, для того чтобы эксперт мог просмотреть, оценить и/или изменить набор правил;
б) небольшое количество условий в посылках правил;
в) правила должны быть сформулированы относительно исходных признаков, выражения типа VBec или 8ш(Рост) являются недопустимыми.
Для поиска набора информативных закономерностей в экспертных системах обычно используют алгоритмы на базе нечетких нейтронных сетей (neuro-fuzzy approach, см. [14, 15]), генетических алгоритмов (см. [16], [17], 13]), а также гибридные подходы с использованием кластерного анализа (см. [18]). К сожалению, эти подходы обладают рядом недостатков:
- нечеткие нейронные сети (ННС) генерируют огромное количество правил относительно низкой информативности, что соответствует ситуации переобучения, а также не позволяет интерпретировать и редактировать набор правил;
- высокий порядок генерируемых правил для ННС;
- большая зависимость ННС от начального приближения;
- значительное время обучения ННС и генетических алгоритмов;
- необходимость определения числа кластеров в алгоритмах, использующих кластеризацию;
- большое количество параметров, настраиваемых пользователем, в генетических алгоритмах.
Можно отметить также такие алгоритмы генерации знаний, как решающие списки (см. [19]) и
подходы с использованием процедуры адаптивной коррекции или бустинга (boosting, см. [20-23]). В этих алгоритмах применяется последовательная схема использования правил, что на практике значительно затрудняет или делает невозможной интерпретацию решений для эксперта.
Большое количество исследований посвящено алгоритмам с использованием решающих деревьев (см. [5, 24-26]). Эти алгоритмы обладают высокими точностными показателями и часто используются на практике. Однако интерпретация древовидной структуры в виде набора правил часто приводит к большому количеству "длинных" правил, посылки которых очень похожи друг на друга (см. [24]). Это также затрудняет интерпретацию решения.
В данной статье предлагается алгоритм генерации знаний, лишенный большинства упомянутых недостатков. Он строит небольшой набор компактных информативных правил, которые могут быть успешно использованы при решении задач.
Работа состоит из пяти разделов. В разд. 1 рассматриваются способы представления знаний в виде совокупности нечетких подмножеств. В разд. 2 рассматриваются вопросы использования знаний, описывается модель получения прогноза в случае нечетких закономерностей. Разд. 3 посвящен проблеме генерации знаний. В нем предлагаются автоматические алгоритмы поиска закономерностей, а также исследуются свойства алгоритмов. Разд. 4 посвящен вопросам оптимизации модели, поиска начального представления, настройки весов правил, поиска границ множеств в посылках правил и пр. В разд. 5 приводятся результаты экспериментов по применению разрабатываемых технологий для решения реальных прикладных задач, подводятся итоги и делаются выводы.
В дальнейшем будут использоваться следующие обозначения. Предположим, что имеется d действительных признаков (независимых переменных) и одна зависимая переменная, принимающая значения на конечном множестве {1, 2, ..., Д А} для задачи распознавания образов (классификации) с l классами или на множестве действительных чисел для задачи восстановления регрессии (прогнозирования). Прецедентная (эмпирическая) информация (обучающая выборка)
представляет собой совокупность пар (хг, у1 } = 1, где xi е К , у1 е {1, 2, ..., Ц, или у1 е К.
Особенностью эксперт
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.