Особенности построения полных и непротиворечивых баз знаний в интегрированных экспертных системах

Размещено на http://www.allbest.ru/

Московский инженерно-физический институт

Особенности построения полных и непротиворечивых баз знаний в интегрированных экспертных системах

Рыбина Г.В., д.т.н., профессор,

Дейнеко А.О.

Нистратов О. В.

e-mail: galina@ailab.mephi.ru

В данной работе рассматриваются особенности процесса построения полных и непротиворечивых баз знаний (БЗ) в интегрированных экспертных системах (ИЭС).

Как показал опыт применения задачно-ориентированной методологии (ЗОМ) построения ИЭС и поддерживающего ее инструментального комплекса АТ-технология [1] для разработки целого ряда прототипов ИЭС (в частности, для задач медицинской и технической диагностики), использование только двух источников знаний, а именно экспертов и проблемно-ориентированных естественно-языковых текстов (ЕЯ-текстов), часто приводит к неполноте извлекаемых знаний.

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

Применение технологии извлечения знаний из БД как дополнительного источника знаний является новым приложением концепций Data Mining и Knowledge Discovery in Databases [2], ориентированных на интеллектуальный анализ больших объемов информации и выявление в них скрытых закономерностей в современных интеллектуальных системах, в частности, в ИЭС, разрабатываемых на основе ЗОМ.

Целью данной работы является анализ опыта применения технологии Data Mining в рамках ЗОМ и комплекса АТ-ТЕХНОЛОГИЯ при решении одной из наиболее востребованных неформализованных задач -- задачи диагностики.

полный непротиворечивый база продукционный

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

Важное место в ЗОМ занимает комбинированный метод приобретения знаний (КМПЗ) [1] и технология его использования на различных стадиях жизненного цикла, связанного с автоматизированным построением БЗ прототипа ИЭС. В рамках КМПЗ концепция Data Mining реализована тремя способами [1]: генерация начального поля знаний (ПЗ) из БД с последующей модификацией его экспертом; верификация ПЗ, полученного в процессе интервьюирования эксперта, а так же его частичная модификация, связанная с нахождением коэффициентов уверенности для уже выявленных знаний; слияние ПЗ, полученных в результате применения двух методологий.

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

Учитывая, что в КМПЗ предусмотрено использование трех источников знаний, один из которых -- проблемно-ориентированные ЕЯ-тексты, обобщенная структура ПЗ представляется в виде:

П_ЗН = <S_ПЗ, М_ПО, И, S_ЯПЗ>,

где S_ПЗ структура входных данных на языке представления ПЗ; S_ЯПЗ структура выходных данных (представление на конкретном ЯПЗ); М_ПО операционная модель ПрО; И правила конвертации структур представления S_ПЗ в структуры S_ЯПЗ.

В соответствии с [1] множество процедур, применяемых рамках КМПЗ на этапе извлечения знаний из БД, представлено как

F_D = <F_D1, F_D2, F_D3, F_D4, F_D5, F_D6, F_D7, F_D8 >,

где: F_D1 - процедура генерации SQL-запроса к СУБД; F_D2 - процедура извлечения данных из БД; F_D3 - процедура фильтрации некоторого подмножества данных; F_D4 - процедура преобразования данных; F_D5 - процедура извлечения знаний из БД; F_D6 - процедура оценки точности полученной модели; F_D7 - процедура определения алгоритма и его параметров; F_D8 - процедура конвертации полученных правил в необходимый формат.

Одной из особенностей применения Data Mining в рамках КМПЗ является необходимость организации доступа к конкретной БД, содержащей информацию по анализируемой предметной области, а также ее предобработки, поэтому КМПЗ включает в себя множество процедур для работы с БД, таких как процедура генерации SQL-запроса к СУБД (F_D1), процедура извлечения данных из БД в соответствии с запросом, сформированным процедурой F_D1 (F_D2), процедура фильтрации некоторого подмножества данных, которое в дальнейшем будет использоваться для построения набора правил (F_D3), процедура преобразования данных, осуществляющая конвертацию в тот формат, который может напрямую использоваться алгоритмами извлечения знаний (F_D4). Ниже приводится описание данных процедур, предназначенных для подготовки выборки данных для последующего анализа.

С помощью процедуры генерации SQL-запроса формируется выборка для дальнейшего применения алгоритмов Data Mining. Инженер по знаниям выбирает атрибуты из БД, которые необходимо включить в выборку, на основании которой система генерирует SQL-запрос.

В силу специфики использованных алгоритмов Data Mining, таких как ID3 [3], C4.5 [4] и CART [5], с помощью инженера по знаниям осуществляется процедура выделения зависимых и независимых атрибутов (столбцов) в анализируемой выборке. Далее происходит обработки неизвестных значений атрибутов. В модели КМПЗ данные две процедуры составляют процедуру фильтрации некоторого подмножества данных.

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

После того, как выборка для анализа готова, применяется непосредственно процедура извлечения знаний из БД (определение зависимостей в виде продукционных правил) (F_D5) для построения результирующего фрагмента, использующая тот или иной алгоритм. Процедуры построения деревьев решений и множеств продукционных правил с помощью конкретных алгоритмов и процедура преобразования деревьев решений в множества правил необходимы для работы с алгоритмами основанными на деревьях решений (ID3, C4.5, CART).

Заключительными являются процедуры: F_D6 - процедура оценки точности полученной модели с использованием тестовых данных; F_D7 - процедура определения алгоритма и его параметров, обеспечивающих наилучший результат в процессе извлечения знаний, и процедура конвертации полученных правил в необходимый формат (F_D8).

В рамках ЗОМ для синхронизации процесса извлечения знаний из трех источников существует специальная типовая проектная процедура (ТПП), названная «Извлечение знаний из БД» [1]. Рассмотрим её подробнее.

ОСОБЕННОСТИ ТИПОВОЙ ПРОЕКТНОЙ ПРОЦЕДУРЫ «ИЗВЛЕЧЕНИЕ ЗНАНИЙ ИЗ БД»

Процесс разработки любого прототипа ИЭС в соответствии с ЗОМ заключается в выполнении определенного набора ТПП, управление которым осуществляет интеллектуальный планировщик (ИП) комплекса АТ-ТЕХНОЛОГИЯ. ТПП «Извлечение знаний из БД» использует технологическую базу знаний ИП и программные средства интеграции источников знаний, на основе которых осуществляется слияние фрагментов ПЗ, получаемых из разных источников.

Сценарий выполнения ТПП «Извлечение знаний из БД» включает следующие этапы:

1) Получение фрагментов ПЗ за счет использования КМПЗ (интервьюирование экспертов и извлечение знаний из БД на основе алгоритмов ID3 [4], C4.5 [5] и CART [6]) и последующая верификация полученных фрагментов.

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

3) Верификация единого ПЗ.

Отметим, что объединение наборов правил является одной из наиболее трудоемких задач. Этой процедуре предшествует автоматизированное сравнение наборов правил, полученных из разных источников. Для сравнения наборов правил используются расширенные таблицы решений (РТР), эффективно применяющиеся в ЗОМ для обнаружения статических аномалий [8].

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

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

Каждая ячейка РТР разбита на 2 части: одна - для IF-частей правил, а другая - для THEN-частей правил. Обе части имеют одну и ту же структуру, только в первой хранятся данные об условиях правил, а во второй - о заключениях правил.

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

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

ОСОБЕННОСТИ АВТОМАТИЗИРОВАННОГО СРАВНЕНИЯ НАБОРОВ ПРАВИЛ

Для объединения двух наборов правил в единый набор используется анализ РТР, который сводится к подсчету совпадающих атрибутов, участвующих в правилах R_i и R_k, а также общего количества атрибутов, участвующих в данных правилах. Далее отдельно для левой и правой частей правил подсчитывается мера сходства Хемминга [7] (м^NL_ik и м^NR_ik):

м^N_ik = n_ik/N,

где n_ik - число совпадающих признаков у образцов R_i и R_k,

м^NL_ik - отношение количества совпавших атрибутов правых частей правил R_i и R_k к количеству всех атрибутов, участвующих в правых частях правил.

Затем формируется таблица мер схожести правил. Таблица мер схожести имеет число строк и столбцов, равное суммарному числу правил, находящихся в сравниваемых наборах правил.

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

· производится выбор первой незаполненной строки таблицы мер схожести;

· в РТР выбирается столбец, номер (имя) которого равен номеру текущей строки таблицы мер схожести;

· проводится пошаговое сравнение с каждым столбцом РТР, вычисляются меры схожести посылок и заключений пар правил;

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

· по окончании анализа РТР и заполнения таблицы мер схожести полученный результат сохраняется для дальнейшего анализа.

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

Рис. 1 Общий вид таблицы схожести правил

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

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

ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ

Экспериментальное исследование описанного подхода проводилось на нескольких реальных и экспериментальных БД. В их число входят: специально созданная для исследований БД, содержащая медицинские данные по диагностике заболеваний дыхательных путей; БД, содержащая информацию о различных аварийных сообщениях, возникающих в сети передачи данных компании Golden Telecom, а так же БД сервиса IpGeoBase - сервиса поиска географического местонахождения IP-адреса, выделенного RIPE локальным интернет-реестрам для Российской Федерации. В настоящее время экспериментальные исследования проводятся в рамках планового тестирования и их основной целью является выявление недостатков разрабатываемых программных средств, но уже на данном этапе можно говорить о хорошей эффективности предложенного подхода (например, на контрольной выборке, содержащей 500 строк, было получено 236 правил).

Описанный в работе подход позволяет эффективно использовать методы Data Mining, в результате чего строятся достаточно полные и непротиворечивые БЗ ИЭС, а так же существенно снижается нагрузка на инженера по знаниям, возникающая на этапе сравнения и слияния наборов правил, полученных из различных источников.

Литература

1. Рыбина Г.В. Теория и технология построения интегрированных экспертных систем. - М: «Научтехлитиздат», 2008.

2. Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Технологии анализа данных. Data Mining, Visual Mining, Text Mining, OLAP. - СПб: БХВ-Петербург, 2007.

3. Clark P., Niblett T. The CN2 induction algorithm //Machine Learning Journal. 1988. №4.

4. Quinlan J.R. Induction of Decision Trees //Machine Learning Journal. 1986. №1.

5. Sreerama K.Murthy, Simon Kasif, Steven Salzberg. A System for Induction of Oblique Decision Trees//Journal of Artificial Intelligence Research. 1994. №8.

6. Breiman L., Friedman J.H., Olshen R.A., Stone C.T. Classification and Regression Trees.- Wadsworth, Belmont, California, 1984.

7. Загоруйко Н.Г. Прикладные методы анализа данных и знаний.-Новосибирск: Издательство института математики,1999. - 210 с.

8. Рыбина Г.В., Смирнов В.В. Планирование процедур верификации баз знаний в интегрированных экспертных системах // Инженерная физика. 2006. № 3.С.53-65.

Размещено на Allbest.ru