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

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

Национальный исследовательский ядерный университет «МИФИ», Москва

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

А.О. Дейнеко

Г.В. Рыбина

Как показано в [Рыбина, 2008], одним из основных этапов построения как классических экспертных систем (ЭС), так и интегрированных экспертных систем (ИЭС), отличающихся масштабируемой архитектурой, позволяющей расширять функциональность с помощью дополнительных подсистем, по-прежнему является этап построения модели проблемной области (ПрО).

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

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

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

Следует отметить, что в настоящее время, среди небольшого числа работ в области группового извлечения знаний из экспертов, наиболее известными являются работы [Кобринский, 2004], которые пока носят лишь теоретико-методологический характер, проект [Mendoncaetal., 2000], описывающий возможности графического представления распределенных знаний, а так же работы французской группы ACACIA по созданию инструментального средства KATEMES (Knowledge Acquisition Toot for Explainable, Multi-Expert Systems) [Diengetal., 1992], предназначенного для частичной автоматизации работы инженера по знаниям на этапе группового извлечения знаний. Помимо перечисленных работ, практически, отсутствуют исследования в области создания инструментальных средств распределенного приобретения знаний из различных источников (эксперт, проблемно-ориентированные тексты, базы данных).

В контексте данной работы основное внимание уделяется решению проблемы распределенного приобретения знаний в рамках задачно-ориентированной методологии (ЗОМ) построения ИЭС, предложенной Г.В. Рыбиной в середине 90-х годов [Рыбина, 2008], и созданной на её основе автоматизированной технологии, включающей инструментарий нового поколения - программный комплекс АТ-ТЕХНОЛОГИЯ [Рыбина, 2008].

Комбинированный метод приобретения знаний и особенности его применения для распределенного приобретения знаний.

Неотъемлемой частью ЗОМ является ЗОМ приобретения знаний, представляющая собой совокупность комбинированного метода приобретения знаний (КМПЗ) и технологии его использования на различных стадиях жизненного цикла построения ИЭС и веб-ИЭС [Рыбина, 2008]. В базовом КМПЗ рассматривается так называемый локальный вариант приобретения знаний.

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

В целом обобщенную модель КМПЗ [Рыбина, 2008] с учетом особенностей распределенного приобретения знаний можно представить в виде:

М_км = <N^~, S^~, F^~, K, Z>,

где N^~ = {N^~_{лок n}}, n=1,…,m_n - множество неструктурированных описаний ПрО;

N^~_{лок n}= <IN, TN, SN, CN>,

где IN - порядковый номер описания, TN - тип описания, SN - источник, откуда получено описание, CN - собственно само описание; S^~={S^~_m}, m=1,…, m_m - множество структурированных описаний ПрО; F^~ - множество процедур отображения N^~ в S^~, K - процедуры конвертации сформированного поля знаний (ПЗ) в форматы языков представления знаний (ЯПЗ) различных инструментальных средств для построения ЭС; Z - фрагменты БЗ в форматах ЯПЗ других инструментальных средств построения ЭС.

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

Соответственно, с учетом особенностей распределенного приобретения знаний обобщенную модель ПЗ можно представить в виде:

S^~_m= <IS_m, TS_m, SS_m, O_m, R_m>,

где IS_m - порядковый номер структурированного описания ПрО; TS_m - тип структурированного описания ПрО; SS_m - источник, откуда получено описание; O_m = {O_mj}, j=1,…, n - множество объектов; R_m = {R_mk}, k=1,…, p - множество правил.

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

Особенности применения Knowledge Discovery in Databases для распределенного приобретения знаний

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

Следует отметить, что в ЗОМ эти термины трактуются следующим образом: под KDD подразумевается весь процесс извлечения знаний, начиная от соединения с БД, заканчивая представлением полученных результатов, а Data Mining являешься лишь некоторым этапом общего процесса KDD. Анализ экспериментальных данных, полученных при создании БЗ значительного числа ИЭС, показал, что использование БД в качестве дополнительного источника знаний способно пополнить объем разрабатываемых БЗ на 10-20%, в зависимости от специфики ПрО. Рассмотрим подробнее предложенный подход.

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

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

На основе процедуры генерации SQL-запроса формируется выборка для дальнейшего применения алгоритмов Data Mining. Инженер по знаниям выбирает атрибуты из БД, включаемые в выборку, на основании которой система генерирует SQL-запрос. C учетом специфики используемых в КМПЗ алгоритмов Data Mining, таких как ID3 [Clark, 1989], C4.5 [Quinlan, 1986] и CART [Sreerama, 1994], с помощью инженера по знаниям осуществляется процедура выделения зависимых и независимых атрибутов (столбцов) в анализируемой выборке. Далее происходит обработка неизвестных значений атрибутов.

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

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

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

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

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

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

верификация единого ПЗ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Экспериментальное программное исследование распределенного варианта КМПЗ (включающего совокупность алгоритмов и процедур совместной обработки знаний, полученных в процессе интервьюирования экспертов, анализа протоколов интервьюирования и извлечения знаний из БД) на нескольких реальных и тестовых БД показало достаточно высокую эффективность предложенного подхода, как с точки зрения решения проблемы неполноты БЗ, так и поддержания БЗ в актуальном состоянии, автоматического пополнения БЗ при появлении новых БД или изменении старых БД.

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

Благодарности. Работа выполнена при поддержке РФФИ (проект №09-01-00638)

Список литературы

распределенный знание эксперт информация

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

2. [Кобринский, 2004] Кобринский Б.А. Извлечение экспертных знаний: групповой вариант // Новости искусственного интеллекта. 2004. № 3.

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

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

5. [Рыбина и др., 2009] Рыбина Г.В., Дейнеко А.О., Нистратов О.В. Особенности построения полных и непротиворечивых баз знаний в интегрированных экспертных системах // Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте. Сборник научних трудов V-й международной научно-практической конференции. Т 2. - М.: Физматлит. 2009.

6. [Clark et al., 1989] Clark P., Niblett T. The CN2 induction algorithm // Machine Learning Journal. 1989. № 3.

7. [Dieng et al., 1992] Dieng R., Giboin A., Tourtier P., Corby O., Knowledge Acquisition for Explainable, Multi-Expert, Knowledge-Based Design Systems // EKAW. 1992.

8. [Mendonca et al., 2000] Mendonca D., Kelton K., Rush R., Wallace W. Acquiring and Assessing Knowledge From Multiple Experts Using Graphical Representations // Knowledge-Based Systems. Academic Press. 2000. Vol. 1 C.T. Leondes (ed.).

9. [Quinlan et al., 1986] Quinlan J.R. Induction of Decision Trees // Machine Learning Journal. 1986. № 1.

10. [Sreerama et al., 1994] Sreerama K., Kasif S., Salzberg S. A System for Induction of Oblique Decision Trees // Journal of Artificial Intelligence Research. 1994. № 2.

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