Welcome to svlab

Member Login

Lost your password?

Not a member yet? Sign Up!

Предыдущий пост Следующий пост
05 Aug 2019

Сетевая модель экспертной системы

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

Введение

Одной из моделей хранения базы знаний является сетевая модель. Такие знания хранятся в графе с вершинами представленными фактами и связями осуществляющих условия переходов между фактами. Две вершины связываются однонаправленной связью и соответствующий паттерн знаний может читаться как «ЕСЛИ факт 1, ТО факт 2, при УСЛОВИИ факт 3». В связях тем самым также хранятся факты. В данной реализации связи имеют положительные или отрицательные по величине веса. Два факта в узлах графа, могут быть отрицанием друг друга и связаны отрицательной связью. Одной из моделей использования такого сетевого графа является установка исходов и целей логического вывода. И задачей экспертной системы является соединение или обоснование цели из исхода с помощью поиска наиболее оптимального пути связей узлов графа.

Алгоритм

Для реализации хранения фактов и поиска оптимальных путей в сетевом графе могут быть использованы различные программные структуры данных. В авторской реализации используются массивы фактов вершин и фактов связей. В качестве массивов выбраны хеш объекты, с ключами в виде id фактов и значениями в виде объектов, хранящих текст факта и другие нужные поля. Для хеш объектов связей в дополнительных полях значений хранятся id1 и id2 двух соединяемых фактов, а также w -- величину связи. А также хранится текст факта связи. При задании исхода и целей, осуществляется поиск двух наиболее подходящих узлов в графе под исход и цель с помощью функции searchTextArr2 осуществляющей сортировку узлов сетевого графа по наибольшему семантическому подобию текста фактов узлов тексту исхода и цели. В задаче логического вывода и обоснования далее два найденных узла сетевого графа связываются оптимальным путем связей с помощью функции findPath. В этой функции находятся все неповторяющиеся нецикличные пути, исходящие из узла исхода с помощью функции построения дерева путей findAllPath3, и определения путей с помощью функции findAllPathToId3. В функции findAllPath3 осуществляется рекурсивное создания дерева путей исходящих из исхода и заканчивающихся в цели. Рекурсия осуществляется пока не будет найден узел цели. В качестве программной структуры данных дерева путей выбирается исходный хеш объект имеющий следующую древовидную структуру:

item = {

     ids: [id1],

     tids: [],

     path: []

}

В этой структуре поле ids хранится массив всех id узлов подграфа родительского пути, а поле tids -- id связей подграфа родительского пути. Поле path -- это массив дочерних структур item соответствующих связям из последнего узла в родительской структуре и осуществляющих ветви графа дочерних путей (рис. 1).

Рис. 1. Древовидная структура путей.

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

Численный эксперимент

Данный алгоритм был программно реализован в виде сервера, хранящего базу знаний пользователя и Web клиента. Было создано Android приложение предоставляющее интерфейс обучения экспертной системы и логический вывод. Приложение доступно в Google Play по адресу: https://play.google.com/store/apps/details?id=svlab3.expertsystem.

Заключение

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

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

1. Хлебалина Е.А. Энциклопедия для детей. Том 22. Информатика. М.: Аванта, 2003. 624с.

2. Кершан Б., Новембер А., Стоун Ж. Основы компьюторной грамотности. Пер. с англ. М.: Мир, 1989.

SHARE:

#

Post dicussion

Контакты

Для связи svbeat@yandex.ru

  • 1
  • 1