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

ММИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

(ФГБОУ ВПО «КубГУ»)

Кафедра математического моделирования

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ (ДИПЛОМНАЯ) РАБОТА

«ТАБЛИЦЫ ПРИНЯТИЯ РЕШЕНИЙ В СУБД С ТАБЛИЧНОЙ МОДЕЛЬЮ ДАННЫХ»

Работу выполнил Зубко М.Д

Факультет компьютерных технологий и прикладной математики

Специальность прикладная информатика и математика

Научный руководитель

канд. тех. наук, доцент Бессарабов Н.В

Нормоконтролер

канд. физ.-мат. наук,

доцент Капустин М.С.

Краснодар 2014

РЕФЕРАТ

Объектом исследования является встроенное в базу данных интеллектуальное расширение СУБД, использующее таблицы принятия решений.

Цели работы: создать систему ТПР, встроенную в СУБД Oracle. Провести экспериментальные исследования быстродействия.

Более детально:

- создать базу данных для инструментального средства, предназначенного для работы с таблицами принятия решений, встроенными в СУБД Oracle,

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

- доработать интерфейсы, разработанные в курсовой работе Дербеневой Е. «Адаптивный интерфейс для работы с таблицами принятия решений», выполнить экспериментальную проверку инструментального средства.

Исследования проводились с помощью СУБД Oracle.

Адаптивный WEB-интерфейс пользователя был реализован с использованием технологий HTML5, CSS3, JavaScript, JSON, PHP.

ВВЕДЕНИЕ

Искусственный интеллект - это один из разделов информатики, в котором рассматриваются задачи аппаратного и программного моделирования тех видов человеческой деятельности, которые считаются интеллектуальными [1].

Экспертные системы являются одним из основных направлений искусственного интеллекта. Как правило, экспертные системы создаются для решения практических задач в некоторых узкоспециализированных областях, где большую роль играют знания и опыт специалистов. Фундаментом экспертной системы любого типа является база знаний, которая составляется на основе знаний специалистов [2].

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

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

Таблицы принятия решений (ТПР) - способ компактного представления модели со сложной логикой. ТПР возникли в деловой практике еще в 60-ых годах прошлого века, зарекомендовав себя как удобное средство для быстрого, простого описания сложных процессов, структур и задач.

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

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

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

В представленной работе используются таблицы принятия решений, встроенные в СУБД Oracle, которые не требуют инсталяции Oracle Fusion Middleware и потому могут работать в любой комплектации СУБД, в частности в бесплатной для коммерческого использования версии Oracle XE.

1. Таблицы принятия решений

запрос логика таблица данные

1.1 Продукции общего вида. Продукции по Поспелову

В общем виде под продукцией понимают выражение вида

AB

Импликация, чаще всего, может истолковываться в обычном логическом смысле, как знак логического следования B из А. Но классическая продукционная система Поста с продукциями общего вида слишком ограниченна. Имеется гораздо более широкое определение.

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

И; О; У; А К; П

где И - идентификатор продукции;

О - область применения;

У - условие применения;

А - антецедент;

К - консеквент;

П - последействие.

Более точно, ядро продукции АК для предлагаемого проекта следовало бы записать в виде:

АХ КУ.

где x,y {БД, РС, БЗ} и через БД обозначен внешний мир, которым в нашем случае является база данных, РС это рассуждающая система, БЗ - база знаний.

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

Поясним на примере, как ядро продукции можно реализовать с помощью SQL-запроса. Любую таблицу можно воспринимать как набор фактов описываемых предикатом, полученным взаимно однозначным отображением схемы таблицы в предикат.

В качестве примера возьмём таблицы employees, departmets и locations из многим известной учебной схемы HR в СУБД Oracle. Используем продукцию, определяющую отношение «Работает в городе», то есть «город, в котором находится отдел, в котором работает сотрудник»:

Работает_в_отделе(employee, department)?

Отдел_находится_в_городе(department, city)

Сотрудник_работет_в_городе(employee,city)

В языке SQL этой продукции соответствует запрос:

SELECT e.employee_id, l.city

FROM employees e, departments d, locations l

WHERE e.department_id = d.department_id

AND d.location_id = l.location_id

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

В общем случае таблица принятия решений, предназначенная для восприятия человеком, разделяется на четыре области (таблица 1).

Таблица 1 - Таблица принятия решений

Условия	Комбинации выполнения условий
Действия	Выполняемые действия

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

Пример таблицы решений, для ситуации «Вода в гостинной» приведён в таблице 2.

Таблица 2 - Пример таблицы принятия решений

В ванной сухо	Нет	Да	Да	Да
На кухне сухо	-	Нет	Да	Да
Потолок в гостиной сухой	-	-	Да	Нет
Окно в гостиной закрыто	-	-	_	Да
Проверить сантехнику в ванной	Х
Проверить сантехнику на кухне		Х
Идти к соседям сверху			Х
Закрыть окно				Х

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

1.2 Переходы внутри таблиц. Работа с исключениями

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

Таблицу решения, вызванную другой таблицей решения, называют подтаблицей-действием или подтаблицей-условием. Эти подтаблицы играют важную роль в структурировании решения и позволяют производить более тщательный и детальный анализ.

Как частный случай перехода от одной таблицы к другой можно рассматривать переходы внутри таблицы, что позволяет работать с исключениями из правил. Например, представим, что таблица принятия решений содержит 7 условий, первые 2 из которых являются исключением из правил, и, если истинно хотя бы одно из них, проверка остальных 5 условий не имеет смысла. В том случае, если мы хотим обойти рассмотрение этих исключений, можно осуществить переход не к началу таблицы, а к какой-либо её части. А затем, при необходимости, вернуться к началу для проверки истинности условий-исключений (рисунок 1).

Рисунок 1 - схема работы с исключениями

1.3 Прямой и обратный логический выводы

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

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

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

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

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

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

1.4 Возможность реализации таблиц принятия решений в СУБД

Для хранения таблицы решений в базе данных реляционного типа (см. табл. 3), транспонируем представляющую матрицу.

Таблица 3 - реляционное представление таблицы принятия решений для ситуации «вода на полу»

В ванной сухо	В кухне сухо	Потолок в гостиной сухой	Окно в гостиной закрыто	Проверить сантехнику в ванной	Проверить сантехнику в кухне	Идти к соседям сверху	Закрыть окно
нет	-	-	-	Х
да	нет	-	-		Х
да	да	нет	-			Х
да	да	да	нет				Х

Каждой строке этой таблицы соответствует продукция. Например, для первой строки:

В ванной сухо (Да) В кухне сухо (нет) Утечка в кухне

Преобразование транспонированием известно давно. Оно же было использовано в предыдущих разработках [9].

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

Таблица 4 - реляционное представление таблицы принятия решений

В ванной сухо	В кухне сухо	Потолок в гостиной сухой	Окно в гостиной закрыто	Действие	Последействие

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

В столбце «Последействия» записываются возможные переходы к другим строкам таблицы (это позволяет работать с исключениями из правил) или к другим таблицам.

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

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

1.5 Универсальная модель данных

Как упоминалось выше, возможность использования запросов SQL с соединениями в качестве эквивалентов простых продукций вида A?K известна. В предлагаемой дипломной работе применяется более эффективное решение, в котором одной продукции соответствует единственный простой запрос к одной таблице. Этот подход распространён на таблицы принятия решений (с ограниченным и расширенными вводами), основанными на продукциях общего вида (с выбором области и подобласти, условий применения и заданием последействия). Для хранения этих таблиц и работы с любыми таблицами решения была использована универсальная модель данных (УМД).

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

Рисунок 2 - схема УМД

Этот набор таблиц остаётся неизменным. Для добавления имени таблицы в виртуальную схему необходимо добавить одну строку в таблицу «Таблица», а для добавления столбца - добавить одну строку в таблицу «Столбец». Количество строк в таблице «Данные», определяющих одну строку таблицы, равно числу столбцов у этой таблицы. Заметим, что тип столбца может быть описан в колонке «Описание» таблицы «Столбец», но может быть добавлен в дополнительном столбце [6].

Универсальность расширения обеспечивается, прежде всего, хранением множества систем таблиц принятия решений, или продукций в универсальной модели данных. При добавлении любого количества интеллектуальных подсистем структура хранения не меняется. При добавлении новых таблиц принятии решений, условия и действия записываются в таблицу metadata, а содержимое таблиц - в decision. Таким образом, одной продукции соответствует единственный простой запрос к одной таблице.

Особенности УМД - низкая скорость. Но в наших задачах для экспертных систем малые объёмы данных.

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

1.6 Динамические SQL-запросы и их использование

Хранение таблиц решений в универсальной модели данных позволяет осуществлять работу с таблицами при помощи однотипных запросов, состоящих из трёх базовых фраз языка SQL: SELECT, FROM, WHERE в стандарте SQL-2, что обеспечивает встраиваемость в различные СУБД с табличной моделью данных.

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

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

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

SELECT actions, aftereffect FROM decision

WHERE sysname = 'Medicine' AND Domain = 'Diagnostics'

AND Subdomain ='Breathing System' AND table_id = 1

AND ( ( ('yes'='yes') OR 'yes'='_') AND( ('no'='no') OR 'no'='_')

AND( ('yes'='yes') OR 'yes'='_') );

Здесь подчёркнутые «yes» и «no» - элементы массива, содержащего ответы пользователя на поставленные условия, хранящиеся в отдельной таблице базы и извлечённые заранее.

1.7 Нечёткая логика в таблицах принятия решений

Классическая логика, по определению, не может оперировать с нечетко очерченными понятиями, поскольку все высказывания в формальных логических системах могут иметь только два взаимоисключающих состояния: «истина» со значением истинности «1» и «ложь» со значением истинности «0».

Одной из попыток уйти от двузначной бинарной логики для описания неопределенности было введение Лукашевичем трехзначной логики с третьим состоянием «возможно» со значением истинности «0,5». Введя в рассмотрение нечеткие множества, Заде предложил обобщить классическую бинарную логику на основе рассмотрения бесконечного множества значений истинности. В предложенном Заде варианте нечеткой логики множество значений истинности высказываний обобщается до интервала [0;1] , т.е. включает как частные случаи классическую бинарную логику и трехзначную логику Лукашевича. Такой подход позволяет рассматривать высказывания с различными значениями истинности и выполнять рассуждения с неопределенностью.

Нечеткое высказывание - это законченная мысль, об истинности или ложности которой можно судить только с некоторой степенью уверенности [0;1]: «возможно истинно», «возможно ложно» и т.п. Чем выше уверенность в истинности высказывания, тем ближе значение степени истинности к 1. В предельных случаях 0, если мы абсолютно уверены в ложности высказывания, и 1, если мы абсолютно уверены в истинности высказывания, что соответствует классической бинарной логике. В нечеткой логике нечеткие высказывания обозначаются так же, как и нечеткие множества: A, B, C … . Введем нечеткое отображение T: ?>[0 ; 1] , которое действует на множестве нечетких высказываний ?=A, B, C… . В этом случае значение истинности высказывания A?? определяется как TA?[0;1] и является количественной оценкой нечеткости, неопределенности, содержащейся в высказывании A .

Логическое отрицание нечеткого высказывания A обозначается ¬A - это унарная (т.е. производимая над одним аргументом) логическая операция, результат которой является нечетким высказыванием «не A », «неверно, что A », значение истинности которого:

T ¬ A = 1 ? T A

Логическая конъюнкция нечетких высказываний A и B обозначается A?B- это бинарная (т.е. производимая над двумя аргументами) логическая операция, результат которой является нечетким высказыванием «A и B», значение истинности которого:

T A ? B = min (T A ; T B)

Помимо приведенного выше исторически принятого основного определения логической конъюнкции (нечеткого «И»), введенного Заде, могут использоваться альтернативные формулы, например:

T A ? B = max (T A + T B ? 1 ; 0) - в базисе Лукашевича-Гилеса;

Логическая дизъюнкция нечетких высказываний A и B обозначается A B - это бинарная логическая операция, результат которой является нечетким высказыванием «A или B», значение истинности которого:

T A B = max (TA ; TB).

Могут использоваться альтернативные формулы, например:

T A B = min ( T A + T B ; 1) - в базисе Лукашевича-Гилеса;

Нечеткая импликация нечетких высказываний A и B обозначается A ? B - это бинарная логическая операция, результат которой является нечетким высказыванием «из A следует B », «если A , то B », значение истинности которого:

T A B = max( (min T A ; T B) ; 1 ? T A)

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

T A B = max (1 ? T A ; T B) - Гедель;

T A B = min (T A ; T B) - Мамдани;

T A B = min (1 ; 1 ? T A + T B) - Лукашевич;

T A B = min (T A + T B ; 1) - Лукашевич-Гилес.

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

Так же, как в классической бинарной логике, в нечеткой логике с помощью рассмотренных выше логических связок можно формировать достаточно сложные логические высказывания [9].

В представленной работе нечёткие логики используются для нахождения значимости полученного решения и определения приоритета в случае нескольких решений: пусть, необходимо работать с предикатами, атрибуты которых имеют разные значимости. На каждый основной атрибут вводится по одному дополнительному атрибуту, хранящему его вес. Взвешенная сумма произведений весов на признаки наличия атрибута (0 или 1), даёт значимость продукции, позволяющую выбирать наиболее существенные из выделенных, обычно, нескольких продукций и «отсекать» продукции, значимость которых ниже какого-либо установленного порога.

Например, пусть исходная комбинация условий имеет вид:

условие_1&( условие_2|| ^условие_3),

где значимость первого условия равна 0.2, второго - 0.7, третьего - 0.6. С учётом весов комбинация примет вид:

0.2&(0.7||^0.6)

При условии, что & есть min(A;B), || - max(A;B), а ^ есть (1-A), получим значение продукции равное 0.2.

Для более точного анализа можно применить расширенный ввод, использование которого, позволит пользователю отвечать на поставленные условия не строго «да»/«нет», но выставлять «показатель выраженности» условия, значения которого также могут находиться в интервале [0;1].

Введём для предыдущего примера дополнительные показатели для 3х условий: 0.7, 0.8 и 0.2 соответственно. Тогда получим:

(0.2*0.7) & ( (0.7*0.8) || (0.6*0.2) ),

где значение продукции будет равно 0.14.

2. Реализация ТПР, встроенных в БД табличного типа

Общая схема приложения для СУБД Oracle приведена на рисунке 3.

Рисунок 3 - схема приложения для Oracle

2.1 Схемы базы данных

Для хранения таблиц решения в УМД используются 2 таблицы: decision и metadata. То есть, при добавлении новых таблиц принятия решений не требуется создание новых таблиц для их хранения.

Таблицы data_users и data_clients содержат данные о пользователях и «привязанных» к ним клиентах и служат для поддержки работы интерфейса.

Схема модели данных в Oracle приведена на рисунке 4. Условные обозначения на рисунке: P - превичный ключ, F - внешний ключ.



Рисунок 4 - Схема базы данных в Oracle

Таблица data (рисунок 5) - хранит ответы клиента на условия, пройденных таблиц решения. Также содержит имя системы, область, подобласть, в которых работает клиент, его идентификационный номер. Данные в таблицу заносятся в процессе работы клиента с системой: на соответствующей странице интерфейса клиент отвечает на поставленные вопросы (условия в соответствующей таблице принятия решений), после чего ответ автоматически заносится в таблицу и обрабатывается системой для получения «ответа» (действия) и возможного перехода на следующую таблицу.



Рисунок 5 - таблица data

Здесь: sysname - название системы, domain - название области, subdomain - название подобласти, table_id - номер таблицы принятия решений, tablename - название этой таблицы, client_id - номер клиента, condition_id - номер условия, condition_name - само условие, answer - ответ клиента на заданное условие, sid - суррогатный ключ. В случае ограниченного ввода ответы клиента имеют вид «yes», «no» или «_» (безразлично). На рисунке 6 приведён пример заполнения таблицы data с расширенным вводом, где значения поля answer характеризуют степень выраженности условия.

Рисунок 6 - пример заполнения таблицы data

Таблица data_clients (рисунок 7) - содержит личную информацию о клиентах, данные об областях в которых он работает, а также номер пользователя (является уникальным), к которому он «привязан». Например, в случае постановки медицинского диагноза, клиентом является пациент, а пользователем - доктор. Таким образом, каждый клиент должен быть привязан к какому-либо пользователю.

Клиент в каждый момент времени может находиться только в одной системе, области и подобласти. Учётная запись клиента создаётся пользователем, данные в таблицу так же добавляются пользователем. При этом пользователь имеет право редактировать данные только своих клиентов.

Данные о текущей таблице решения и номере продукции заносятся автоматически в процессе работы с системой.

Рисунок 7 - таблица data_clients

Здесь: current_progress - номер текущей таблицы решения и номер продукции, dob - дата рождения, home_city - город проживания, home_state - штат/область, home_street - улица, marital_status - семейное положение, name - имя, next_visit - дата последнего посещения, sex - пол, user_id - номер пользователя, к которому привязан клиент, visit - первичный визит, basis_id и basis_name - id и название базиса с которым работает клиент. Базис для каждого клиента устанавливается пользователем перед началом работы системы и сохраняется до её окончания.

Таблица data_users (рисунок 8) - содержит личную информацию о всех пользователях, работающих с системой: имя, адрес, id, названия системы, области и подобласти, с которыми работает данный пользователь, а также логин и пароль для входа в систему. Причём логин является уникальным и не может быть одинаковым у разных пользователей. Данные пользователя заносятся в таблицу автоматически при регистрации пользователя в системе. При этом пользователь может находиться только в одной области и подобласти.

Рисунок 8 - таблица data_users

Таблица decision (рисунок 9) - хранит все таблицы принятия решений, т.е. при добавлении новых таблиц решений не требуется создание новых таблиц в базе для их хранения. Наборам ответов на условия, хранящимся в столбце conditions, соответствуют наборы действий и последействий (actions и aftereffects).



Рисунок 9 - таблица decision

Здесь: prod_id - номер соответствующей продукции, sid - суррогатный ключ, генерирующийся автоматически при помощи триггера, conditions - комбинация ответов на условия, actions - содержит комбинацию действий, соединенные между собой логическим «И», aftereffect - последействие (переход на другую таблицу/продукцию). Для столбца conditions допустимы логические операции: and (&) и or (||).

Рисунок 10 - пример заполнения таблицы decision

Данные в таблицу decision заносятся администратором и не могут редактироваться пользователями и клиентами.

Таблица metadata (рисунок 11) - содержит списки всех условий и действий, соответствующих данной таблице принятия решений, названия системы, области и подобласти, к которым принадлежит эта таблица, а также вспомогательные поля для верного построения логического условия, такие как: type, определяющее «вид» ответа клиента: checkbox, в случае ограниченного ввода, и text, в случае расширенного ввода (например, значение температуры); connection - определяет тип соединения данного условия с последующим («AND» или «OR»); brackets - наличие открывающей или закрывающей скобок. Для поддержки нечётких логик используются следующий поля: condition_weight и action_weight - вес условий и действий, значения от 0 до 1; prod_limit - «порог» значения продукции, т.е. продукции, значение которых ниже этого порога, не рассматриваются в дальнейшей работе системы. Данные в таблицу также заносятся администратором и недоступны пользователям и клиентам для редактирования.

Рисунок 11 - таблица metadata

Рисунок 12 - пример заполнения таблицы metadata

Таблица history (рисунок 13) - хранит историю работы каждого клиента. Содержит последовательность переходов между таблицами принятия решения, а также информацию о завершении работы с той или иной таблицей принятия решений. Помимо номера таблицы, к которой осуществляется переход, также хранится номер условия, с которого будет начата работа на следующем шаге (по умолчанию имеет значение 1), номер продукции, по которой был осуществлён переход, полученное при работе значение продукции и название базиса, в соответствии с которым это значение рассчитывалось. Также присутствует поле reason, в которое выводится информация о причинах принятого решения.

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

Рисунок 13 - таблица history

Поля: status - статус работы с таблицей, step - номер шага, на котором осуществлялась работа с таблицей.



Рисунок 14 - пример заполнения таблицы history(часть 1)

Рисунок 15 - пример заполнения таблицы history(часть 2)

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

Информацию об области и подобласти, с которыми работает клиент, можно извлечь из таблицы decision, используя суррогатный ключ из столбца sid.

Таблица bases (рисунок 16) - содержит формулы конъюнкции, дизъюнкции, отрицания и импликации в различных базисах, которые используются для вычисления значимости продукции.



Рисунок 16 - таблица bases

Поля: basis_id, formula_id - id базиса и одной из 4х формул, вместе образуют первичный ключ. Basis_name - название базиса, например «базис Вебера», formula_type - тип описываемой формулы, принимает одно из четырёх значений: «&»(and), «||»(or), «^»(not), «->»(implication). Поле formula содержит непосредственно формулы соответствующих операций. Для унарных операций в качестве обозначения переменной используется «А», для бинарных «А» и «В». Каждую операцию над двумя переменными следует выделять скобками, например, для операции импликации:

max(min(A,B),(1-A))

2.2 Пакет pkg_ get_answer. Использование процедур и функций пакета

Рисунок 17 - схема пакета pkg_get_answer

Пакет pkg_get_answer (рисунок 17) содержит процедуры и функции, реализующие процессы, обеспечивающие создание, редактирование и работу с таблицами принятия решений

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

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

Пример поиска нужной продукции:

((p(1)=a(1)) OR (p(1)='_')) AND ((p(2)= a(2)) OR (p(2)='_')) AND

((p(3)= a(3)') OR ( p(3)='_')) AND ((p(4)= a(4)) OR (p(4)='_')) AND

((p(5)= a(5)) OR (p(5)='_'))

где p(i) - массив элементов продукции, a(i) - массив ответов пользователя.

Входными параметрами являются имя системы (p_sysname), область (p_domain), подобласть (p_subdomain), номер таблицы (p_table_id), id клиента (p_client_id).

Пример вызова процедуры:

begin

get_answer.go('Medicine','Diagnostics','Skin',1,1);

end;

Процедура add_history - добавляет данные о новом шаге работы пользователя в таблицу history: id таблицы, с которой пользователь завершил работу, полученный список действий и последействий, номер шага. В столбце последействия записывается номер таблицы и условия, к которому будет осуществлён переход. Если последействие имеет значение null, то процедура записывает шаг в таблицу history (рисунок 21) без перехода на другие таблицы и выдаёт сообщение о завершении работы с системой. В этом случае, в поле current_progress таблицы data_clients будет записано значение null.Помимо этого процедура сравнивает значение продукции с порогом значимости и, в случае, если значение ниже этого порога, ставит статус «abort», означающий, что с данной веткой дальнейшая работа невозможна. В поле reason выводится обоснование принятого решения: исходные условия, по которым была выбрана эта продукция, значение продукции, значение порога

Перед добавлением данных процедура проверяет: работал ли клиент с таблицей, к которой мы собираемся перейти. Если работа с этой таблицей уже была закончена, то данное последействие игнорируется и не заносится в таблицу. В случае успешного перехода к новой таблице, её номер записывается в поле current_progress таблицы data_clients.

Входными параметрами процедуры add_history являются суррогатный ключ (p_sid), id клиента (p_client), id пользователя (p_user), номер продукции, по которому будет осуществлён переход (p_prod_id), номер условия, с которого начата работа с таблицей (p_position) и значение данной продукции (p_prod_value). Вызывается только в процессе работы другой процедуры prc_go.

Процедура trans - осуществляет преобразование заданной таблицы решения в вид, понятный пользователю. Результат записывается в соответствующую временную таблицу.

Входными параметрами являются имя системы (sysname), область (domain), подобласть (subdomain), номер таблицы (tableno).

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

Пример вызова процедуры:

begin

get_answer.trans('Medicine','Diagnostics','Skin',1);

end;

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

yes&(yes||no),

где значимость первого условия равна 0.2, второго - 0.7, третьего - 0.6, примет вид:

0.2&(0.7||^0.6)

Унарная операция отрицания уже на этом этапе вычисляется при помощи функции fnc_calculation, в соответствии с выбранным базисом. Например, ^A = 1-A. Тогда ^0.6 = 0.4 Далее, используя принцип обратной польской нотации, формула приводится к виду, удобному для вычисления системой:

0.2 ; 0.7 ; 0.4 ; || ; &.

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

вес комбинации условий -> вес комбинации действий.

В ситуации с расширенным вводом помимо значимости условий, учитываются ещё и степень «выраженности». Например, если есть всего два условия, соединённых &, и значимость первого равна 0.3, степень 0.6, второго - 0.7 и 1, тогда значение продукции будет вычислено как:

(0.3*0.6)&(0.7*1).

Входными параметрами служат суррогатный ключ sid, id клиента и номер продукции, значение которой нужно вычислить.

Пример вызова:

value := pkg_get_answer.fnc_get_value(1, 1, 1);

Для вычисления операций &, ||, ^, -> используется функция fnc_calculation, которая выбирает необходимую формулу из таблицы bases, подставляет в неё значения, полученные в качестве входных параметров и вычисляет её, также используя обратную польскую нотацию. Работает как с унарными, так и бинарными операторами. Входные параметры: id базиса, тип логической операции, 2 числовых параметра. Пример вызова:

x := pkg_get_answer.fnc_calculation(0.1, 0.9, '&', 1);

Обе функции возвращают числовые значения.

2.3 Контроль корректности данных

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

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

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

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

В представленной работе, «эталонной» таблицей считается metadata. Подразумевается, что в ней хранятся верная информация о системах, областях, подобластях, таблицах, условиях и действиях. При добавлении данных в таблицы decision, data, data_users, data_clients проверяется наличие таковых данных в metadata и, в случае их отсутствия, выдаётся ошибка. Это позволит сохранить «согласованность» данных не только при сбоях в работе интерфейса, но и в случае заполнения таблиц непосредственно из СУБД.

Также, ведётся контроль за форматом хранения комбинации условий (поле conditions в таблице decision). Комбинация должна содержать только ответы «yes», «no» и символы «& || _». Например

yes&(no||yes)

Ошибки вида «yesno&&yes» помогает исключить использование регулярных выражений.

Аналогичным образом контролируются ответы пользователя: допустимы значения «yes» и «no», в случае ограниченного ввода, и числовые значения в интервале от 0 до 1 в случае расширенного.

Помимо триггеров, контролировать данные помогают ограничения целостности, например ограничение CHECK(formula_type IN ('&', '||', '^', '->')) в комбинации с UNIQUE(basis_id, formula_type) в таблице bases позволяет хранить лишь 4 различных типа формул на каждый базис. Внешние ключи позволяют контролировать привязку клиентов к пользователям.

Примеры используемых триггеров можно посмотреть в приложении.

2.4 Адаптивный интерфейс пользователя

В представленной работе был доработан адаптивный web-интерфейс, основная часть которого была разработана в курсовой работе «Адаптивный интерфейс для работы с таблицами принятия решений», автор - Дербенева Е.Е.

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

Обмен данными с пользовательским интерфейсом осуществляется с помощью технологии Ajax, с использованием формата JSON. На стороне клиента создаётся подключение к СУБД и формируются SQL-запросы.

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

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

Рисунок 18 - главная страница интерфейса



Рисунок 19 - Главная страница интерфейса

Рисунок 10 - главная страница

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

Рисунок 20 - аутентификация

Так выглядит регистрационная форма (рисунок 21). Обязательными являются только три поля: имя, логин и пароль.

Рисунок 21 - регистрация пользователя

Если аутентификация пройдена успешно, то пользователь попадает на вторую страницу (рисунок 22). На ней находится динамически построенный список его клиентов. Для обеспечения динамики необходимые параметры (имя системы, область, подобласть, идентификатор пользователя) передаются странице в адресной строке.



Рисунок 22 - база клиентов

При необходимости пользователь может добавлять и удалять клиентов (рисунок 23). Данные манипуляции проводятся с таблицей Data_Clients.

Рисунок 23 - регистрация клиентов

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



Рисунок 24 - страница с базисами

На странице с данными о клиентах столбцы ANS и HIS содержат ссылки на страницы, отображающие данные обо всех ответах конкретного клиента и историю его работы с системой соответственно (рисунки 25-26).

Рисунок 25 - страница с ответами клиента



Рисунок 26 - страница с историей клиента

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

В столбце CURRENT_PROGRESS находится номер следующей таблицы решений. И при нажатии на ссылку происходит переход на страницу заполнения (рисунки 27-28). В качестве параметров выступают: имя системы, область, подобласть знаний, номер таблицы и идентификатор клиента.

Рисунок 27 - опрос клиента (вариант с ограниченным вводом)



Рисунок 28 - опрос клиента (вариант с ограниченным вводом)

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

Рисунок 29 - отображение таблицы принятия решений

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

По завершении работы открывается страница с результатами: поля step, tablename, actions, value пройденных таблиц принятия решения, загруженные из истории клиента (рисунок 30).

В рамочке отображаются действия с наибольшим значением продукции.

Рисунок 30 - страница с результатами

3. Экспериментальные исследования

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

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

Основными запрашиваемыми характеристиками служат тип операционной системы, предназначение, качество камеры, ценовой диапазон. Отдельным, частным случаем можно рассматривать выбор конкретной модели фирмы Apple.

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

Рисунок 31 - схема тестовой базы

Время работы в Oracle процедуры prc_go, включая вызов процедуры prc_add_history и функций fnc_get_value и fnc_calculation для одной из таблиц учебной базы: 00.233 секунд.

Время работы в Oracle процедуры prc_translate для одной таблицы: 00.118 секунд.

ЗАКЛЮЧЕНИЕ

Создана база данных для инструментального средства, предназначенного для работы с таблицами принятия решений, встроенными в СУБД Oracle.

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

Доработаны интерфейсы, разработанные в курсовой работе Дербеневой Е. «Адаптивный интерфейс для работы с таблицами принятия решений», выполнить экспериментальную проверку инструментального средства. В частности, созданы страницы редактирования истории и таблицы ответов пользователей, реализован расширенный ввод данных.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1 Бессмертный И.А., Применение реляционных операций для логического вывода в продукционных системах. Изв. вузов. Приборостроение, 2010 - с.34-38.

2 Бессарабов Н.В., Муса-Оглы Е.С. Универсальная модель данных. RSDN, 2011, №3 - с. 51-55.

3 Братко И., Алгоритмы искусственного интеллекта на языке PROLOG. Мск.: Вильямс, 2004 - с. 331-334.

4 В. Г. Рубанов, А. Г. Филатов, И. А. Рыбин. Интеллектуальные системы автоматического управления. Нечеткое управление в технических системах [электронное пособие]. URL: http://nrsu.bstu.ru/

5 Бессарабов Н.В., Семенютина Л.В. Таблицы принятия решений встроенные в базы данных. - INTELS, 2014.

6 Поспелов Д. А. Моделирование рассуждений. Опыт анализа мыслительных актов. М.: Радио и связь, 1989, 184 с.

ПРИЛОЖЕНИЕ А

Спецификация пакета pkg_get_answer

create or replace PACKAGE pkg_get_answer AS

PROCEDURE prc_go( p_sysname decision.sysname%TYPE,

p_domain decision.domain%TYPE,

p_subdomain decision.subdomain%TYPE,

p_table_id decision.table_id%TYPE,

p_client_id data.client_id%TYPE);

PROCEDURE prc_add_history( p_sid history.sid%TYPE,

p_user history.user_id%TYPE,

p_client history.client_id%TYPE,

p_prod_id NUMBER,

p_position NUMBER,

p_prod_value history.prod_value%TYPE

);

PROCEDURE prc_translate( p_sysname decision.sysname%TYPE,

p_domain decision.domain%TYPE,

p_subdomain decision.subdomain%TYPE,

p_table_id decision.table_id%TYPE

);

FUNCTION fnc_get_value(p_sid metadata.sid%TYPE,

p_client_id data_clients.client_id%TYPE,

p_prod_id decision.prod_id%TYPE)

RETURN NUMBER;

FUNCTION fnc_calculation( p_x1 VARCHAR2

, p_x2 VARCHAR2

, p_operation VARCHAR2

, p_basis_id data_clients.basis_id%TYPE)

RETURN NUMBER;

END pkg_get_answer;?

ПРИЛОЖЕНИЕ Б

Тело пакета pkg_get_answer

CREATE OR REPLACE PACKAGE BODY pkg_get_answer AS

TYPE arr_type IS TABLE OF VARCHAR2(2000)INDEX BY BINARY_INTEGER;

PROCEDURE prc_go( p_sysname decision.sysname%TYPE,

p_domain decision.domain%TYPE,

p_subdomain decision.subdomain%TYPE,

p_table_id decision.table_id%TYPE,

p_client_id data.client_id%TYPE)

AS

c_sid NUMBER;

c_user_id NUMBER;

c_condition NUMBER; --число условий

c_min_condition NUMBER;

c_action NUMBER; --число действий

c_product NUMBER; --число продукций

q_select VARCHAR(2000);

q_where VARCHAR(2000);

i NUMBER; --чёрная рабочая сила)

j NUMBER;

v_in_str NUMBER;

v_substr_condition VARCHAR2(2000);

v_char_left VARCHAR(5);

v_char_right VARCHAR(5);

v_connection VARCHAR(5);

m_answer arr_type; -- масс в ответов пользователя

m_connection arr_type; -- массив логических операций

m_char arr_type; -- массив со скобками

m_product arr_type; -- массив, в который помещаются все распасенные продукци

v_productuctno NUMBER; -- массив с номерами эквивалентных продукций

v_prod_value history.prod_value%TYPE := 0;

v_condition decision.conditions%TYPE;

--m_condition arr_type; -- массив с продукциями

v_equals_cnt NUMBER;

v_count NUMBER := 0;

-- c_prc_name VARCHAR2(50) := 'PKG_GET_ANSWER_NEW.PRC_GO';

--v_prc_step NUMBER := 0;

v_right_bkt NUMBER;

v_left_bkt NUMBER;

x NUMBER;

v_type metadata.type%TYPE;

TIME_START TIMESTAMP;

TIME_END TIMESTAMP;

BEGIN

TIME_START := SYSTIMESTAMP;

SELECT DISTINCT sid INTO c_sid FROM metadata

WHERE sysname = p_sysname

AND domain = p_domain

AND subdomain = p_subdomain

AND table_id = p_table_id;

SELECT COUNT(condition_id),COUNT(action_id) INTO c_condition, c_action --находим количество условий и действий

FROM metadata

WHERE sid = c_sid;

IF c_condition < 1 THEN raise_application_error(-20050,'Количество условий должно быть не меньше 1.'); END IF;

IF c_action < 1 THEN raise_application_error(-20050,'Количество действий должно быть не меньше 1.'); END IF;

SELECT COUNT(brackets) INTO v_right_bkt

FROM metadata

WHERE sid = c_sid

AND table_id = p_table_id