Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
“Кубанский государственный университет” (ФГБОУ ВПО “КубГУ”)
Кафедра математического моделирования
Выпускная квалификационная работа бакалавра
Реализация таблиц принятия решений в объектных базах данных
Работу выполнил
М.О. Полковников
Научный руководитель
канд. физ.-мат. наук, доцент
Н.В. Бессарабов
Нормоконтролер
доцент, канд. физ.-мат. наук
М.С. Капустин
Краснодар 2014
Реферат
Выпускная квалификационная работа 41 с., 14 рис., 4 таблицы, 7 источников, 1 приложение.
Искусственный интеллект, объектные таблицы принятия решений, объектно-реляционная модель данных в СУБД Oracle.
Объектом исследования является встроенное в базу данных интеллектуальное расширение СУБД, использующее таблицы принятия решений (ТПР).
Цели работы: создать систему таблиц принятия решений в рамках объектной модели данных СУБД Oracle. Провести сравнительный анализ данного подхода с реляционным.
Более детально:
– Разработать новый подход к формированию таблиц принятия решений в объектной базе Oracle использующий возможности данной модели и дающий преимущества по сравнению с реляционными ТПР в ряде случаев;
– создать приложение, на примере которого можно будет показать эффективность нового подхода;
– провести сравнительный анализ подхода с объектными ТПР и реляционными, на основании разработанного приложения (пример объектного подхода) и приложения iThink, разработанного в рамках курсовой работы “Построение экспертной системы на базе таблиц принятия решений” (пример реляционного подхода).
Приложение, с интегрированными в него объектными таблицами принятия решений было разработано при помощи технологий: Java 7, Oracle PL/SQL. Таблицы принятия решений реализованы в СУБД Oracle XE 11g.
Содержание
Введение
1. Системы искусственного интеллекта на базе ТПР
1.1 Продукции общего вида. Реализация в реляционной СУБД
1.2 Прямой и обратный логический вывод
1.3 Варианты реализации интеллектуальных систем на основе ТПР
1.4 Табличный подход к реализации экспертной системы на основе ТПР с использованием универсальной модели данных
1.5 Объектный подход к реализации системы ТПР
2. Интеграция объектных таблиц принятия решения в проект по распознаванию символов
2.1 Описание концепции приложения и роли ТПР в нем
2.2 Первичная обработка bmp файла средствами Java Development Kit
2.3 Глубокий анализ первичной информации средствами Oracle
2.4 Процесс распознавания символа при помощи объектных ТПР
Заключение
Список использованных источников
Приложение
Введение
Искусственный интеллект – одно из направлений информатики, целью которого является разработка аппаратно-программных средств, позволяющих непрограммисту ставить и решать свои, традиционно считающиеся интеллектуальными задачи, общаясь с ЭВМ на ограниченном подмножестве естественного языка [1].
В контексте данной дипломной работы будут затронуты такие системы искусственного интеллекта, как экспертные системы.
Экспертная система – программа, которая использует знания специалистов (экспертов) о некоторой конкретной узко специализированной предметной области и в пределах этой области способна принимать решения на уровне эксперта-профессионала [2]. Можно выделить отдельный класс экспертных систем, базирующихся на системах таблиц принятия решений. Данный класс экспертных систем, а так же подходы к их созданию и будут рассмотрены в данной работе.
1. Системы искусственного интеллекта на базе ТПР
1.1 Продукции общего вида. Реализация в реляционной СУБД
По Поспелову Д.А. [3] продукционная модель знаний основывается на правилах, имеющих в общем случае вид:
И; О; У; А >К; П (1)
где:
И – идентификатор продукции;
О – область применения;
У – условие применения;
А – антецедент;
К – консеквент;
П – последействие.
Более точно, ядро продукции А>К для предлагаемого проекта следовало бы записать в виде:
АХ >КУ. (2)
где x,y принадлежит{БД, РС, БЗ} и через БД обозначен внешний мир, которым в нашем случае является база данных, РС это рассуждающая система, БЗ – база знаний. Имеется в виду, что информация может поступать из внешнего мира (АБД), из базы знаний (АБЗ) и из самой рассуждающей системы мира (АРС), а следствие представляет изменения в базе данных(КБД), в базе знаний (КБЗ) или в рассуждающей системе (КРС). Поясним на простом примере, как ядро продукции можно реализовать с помощью SQL-запроса. Любую таблицу можно воспринимать как набор фактов описываемых предикатом, полученным взаимно однозначным отображением схемы таблицы. Пусть задана единственная таблица БО (“Быть отцом”) и используется единственная продукция, определяющая отношение “Быть дедом”, то есть “отец отца есть дед”:
БО(Сын, X)&БО(X, Отец) >БД(Сын, Отец). (3)
Остаётся в предикате БД (“Быть дедом”) переименовать Сын=Внук, Отец=Дед.
В языке SQL этой продукции соответствует запрос, порождающий врйменное отношение “Быть дедом”:
SELECT БО1.Сын “Внук”, БО2.Отец “Дед”
FROM БО БО1, БО БО2
WHERE БО1.Отец = БО2.Сын
В общем случае можно выделить три класса атрибутов. Два из них предназначены для:
– организации соединений;
– использования в консеквенте.
Третий класс составляют безразличные атрибуты, обозначаемые в продукциях знаком подчёркивания и не относящиеся к первым двум классам.
Остается рассмотреть таблицы принятия решений, представляемые как наборы продукций связанных по смыслу. В общем случае таблица принятия решений, предназначенная для восприятия человеком, разделяется на четыре области (таблица 1).
Таблица 1 – Строение таблицы принятия решений
|
Условия |
Комбинации выполнения условий |
|
|
Действия |
Выполняемые действия |
Для пояснения приведём пример таблицы решений заимствованный из Википедии [4] (таблица 2).
Таблица 2 – Пример таблицы принятия решений
|
Свет в соседней комнате горит |
Да |
Нет |
Нет |
|
|
Свет у соседей горит |
– |
Да |
Нет |
|
|
Поменять лампочку |
Х |
|||
|
Проверить пробки |
Х |
|||
|
Позвонить электрику |
Х |
Х |
||
|
Позвонить диспетчеру |
Х |
Две верхних строки относятся к условиям, остальные четыре – к действиям.
Для хранения таблицы решений в реляционной базе данных, транспонируем представляющую матрицу (таблица 3).
Таблица 3 – Транспонированная таблица принятия решений
|
Свет в соседней комнате горит |
Свет у соседей горит |
Поменять лампочку |
Проверить пробки |
Позвонить электрику |
Позвонить диспетчеру |
|
|
Да |
– |
Х |
||||
|
Нет |
Да |
Х |
Х |
|||
|
Нет |
Нет |
Х |
Х |
Получилась реляционная таблица с шестью столбцами и тремя строками.
Каждой строке этой таблицы соответствует продукция. Например, для первой строки:
Свет_в_соседней_комнате_горит(Да) & Свет_у_соседей_горит(Безразлично) > Поменять_лампочку(Да)(4)
Использование продукций в которых консеквент относится к одной или нескольким столбцам, не повторяющимся в разных продукциях, крайне неудобно. Поэтому данную структуру можно изменить к виду таблицы (таблица 4).
Высокая эффективность работы с таблицами решений позволяет строить сложные системы искусственного интеллекта. Их преимущества по сравнению с обычными экспертными системами – простота эксплуатации, встраивание в базу данных и вытекающая из этого обстоятельства возможность использования индексов базы для ускорения доступа к большому объёму фактов, представленных таблицами базы данных. Существенно облегчена факторизация базы знаний.
Таблица 4 – таблица принятия решений, адаптированная для хранения в реляционной СУБД
|
Свет в соседней комнате горит |
Свет у соседей горит |
Действие |
Последействие |
Поскольку действий при одних и тех же условиях может быть больше одного, в реализованном варианте для каждого такого действия предусмотрена своя строка (т. е. продукция). Возможен вариант со списком в столбце “Действие”.
В столбце “Последействия” записываются возможные переходы к другим строкам таблицы (это позволяет работать с исключениями из правил) или к другим таблицам.
Существует три типа таблиц решений:
– с ограниченными входами (входы принимают значения “Да”, “Нет” и “Безразлично”);
– с расширенными входами (входы принимают интервалы и наборы интервалов значений);
– комплексные, содержащие и данные и метаданные.
1.2 Прямой и обратный логический вывод
Механизм логического вывода – алгоритм поиска в базе знаний интеллектуальной системы последовательности правил, необходимых для получения заключений. Существует два таких алгоритма – прямой и обратный.
Формирование рассуждений в стиле обратного логического вывода может осуществляться следующим образом. Работа по поиску причин отключения электричества начинается с выдвижения гипотезы. Например, пусть в рассмотренном выше примере это “проверить пробки”. После этого цепочка рассуждений в сети логического вывода формируется в обратном направлении. Для подтверждения этой гипотезы необходимо, чтобы утверждение “свет у соседей горит” было истинным, а утверждение “свет в соседней комнате горит” ложным [5].
В обратном механизме логического вывода работа начинается от поставленной цели. Если цель A согласуется с консеквентном (заключением) продукции, то антецедент (посылка) принимается за подцель и делается попытка подтверждения истинности этого факта. Процесс повторяется до тех пор, пока не будут просмотрены все правила, имеющие в качестве заключения требуемый факт.
Прямой логический вывод начинается не с гипотез, а с некоторых подтвержденных фактов. Производится последовательная проверка условий, горит ли свет на кухне или у соседей, и на основании полученных ответов строится логическое заключение.
Хотя алгоритм обратного вывода имеет больше возможностей, чем прямого, на практике, для решения довольно большого класса задач естественным является прямой логический вывод.
Прямой логический вывод начинается не с гипотез, а с некоторых подтвержденных фактов [6].
К неоспоримым достоинствам прямого вывода так же можно отнести тот факт, что рассуждения, построенные по его принципу более естественны для понимания человеком.
1.3 Варианты реализации интеллектуальных систем на основе ТПР
Концепция таблиц принятия решений была сформулирована задолго до написания этой работы. Однако подход, в котором на ТПР бы базировалась система искусственного интеллекта, не получил должной огласки в научной литературе и по сей день. Данную проблему я изучал в рамках курсовых работ (“Построение экспертной системы на базе таблиц принятия решений” и “Таблицы принятия решений в СУБД Cache”) совместно с Семенютиной Л.В. (в первой работе) и самостоятельно.
В ходе этих исследований был сформирован подход, который позднее был развит и уточнен в [7].
Далее по тексту мы будем называть его “Реляционный” или “Табличный”. Бесспорно имея множество преимуществ в рамках одних задач, данный подход имел так же и ряд недостатков, которые затрудняли его использование при решении других. Так, например, этот подход позволял без труда создавать экспертные системы, для которых основной массив фактов поступает из интерфейса пользователя. О примере такой системы будет рассказано в пункте 1.4.
Но существует масса задач, в которых этот подход не так хорош. Недостатки реляционной системы таблиц принятия решений легко можно увидеть на примере случая, когда не требуется создавать новую информационную систему, а напротив, нужно добавить элементы искусственного интеллекта к уже работающей БД.
Тогда, для интеграции реляционной системы ТПР придется вносить изменения в структуру боевой БД, для обеспечения должного быстродействия и масштабируемости, после добавления интеллектуальной подсистемы.
1.4 Табличный подход к реализации экспертной системы на основе ТПР с использованием универсальной модели данных
Можно выделить ряд важнейших особенностей реляционного подхода, такие как:
– Использование варианта универсальной модели данных (УМД). УМД – подход, благодаря которому в ограниченном числе таблиц можно хранить неограниченное число виртуальных таблиц. Данный подход применим для информационных систем, в которых имеет место неограниченный рост количества таблиц БД. Более подробно об универсальной модели данных можно прочитать в [6].
– Продукция представляется как строка реляционной таблицы.
– Базой фактов является сугубо специфичной таблицей, представимой как часть интеллектуальной системы
– Система ТПР использует механизм прямого вывода
– Антецедент продукции представляется в виде конъюнкции условий истинности.
– Условия истинности атомарны. Каждое условие является проверкой на равенство (неравенство) того или иного факта, полученного либо из базы знаний, либо как промежуточный результат работы системы.
Данные подход имеет как свои достоинства, так и недостатки, подробнее о которых я расскажу на примере разработанной в рамках курсовой работы “Построение экспертной системы на базе таблиц принятия решений” расширением СУБД Cache под названием iThink.
На базе данного расширения была создана экспертная система по диагностике некоторого числа заболеваний дыхательной системы человека. В процессе создания данного расширения мне удалось в полной мере оценить разные аспекты такого подхода к созданию интеллектуальных систем, как с точки зрения программиста, так и с точки зрения эксперта.
Одним из важнейших аспектов стало использование упрощенной универсальной модели данных для хранения таблиц принятия решений. Модель реализована была реализована двумя таблицами:
Рисунок 1 – Пример заполнения таблицы solutionsTables
Рисунок 2 – Пример заполнения таблицы solutionsTables
Рисунок 3 – Пример заполнения таблицы solutionsTables
Где на рисунках 1-3
pDomain,pSubDomain,name,id – поля для идентификации таблицы;
p1-p10 – условия таблиц решений;
countCond – количество условий у данной таблицы;
Рисунок 4- Пример заполнения таблицы solutions
Рисунок 5 – Пример заполнения таблицы solutions
Рисунок 6 – Пример заполнения таблицы solutions
Где на рисунках 4-6:
– pDomain, pSubDomain, name, id – поля для идентификации таблицы;
– p1-p24 – набор значений условий соответствующей таблицы;
– conclusion – решение по заданным значениям;
– aftereffect – последействие (имя следующей таблицы решений).
Конечно, данная структура позволяет уместить в себе множество таблиц принятия решений, но она же приведет к серьезной конкуренции за ресурсы, когда число параллельно работающих пользователей станет больше определенного порога. Причем потери масштабируемости будут очень существенны. Также, данный подход не подразумевает добавление уникальных для каждой таблицы функций, например для загрузки фактов из схемы БД или других не универсальных механизмов.
1.5 Объектный подход к реализации системы ТПР
Как уже было сказано в пункте 1.3, иногда возникает необходимость добавить интеллектуальную составляющую в уже реализованный IT проект. В такой ситуации необходимо максимально органично вписать систему ТПР в готовый программный код, сделав как можно меньше изменений в последнем. Следуя этой идее разработана концепция, когда одна таблица принятия решений представляется как одна объектная таблица.
Такой подход к организации системы ТПР имеет как ряд очевидных достоинств, так и ряд недостатков по сравнению с реляционным. К достоинствам можно отнести:
– Инкапсуляция внутренних структур ТПР. Сокрытие тех или иных сугубо технических аспектов реализации системы ТПР позволит упростить задачу освоения данной технологии разработчиками.
– Включенные в состав ТПР процедуры подключения источников фактов для каждой конкретной ТПР позволяет разработчику очень гибко использовать реальную БД как базу фактов.
– Интегрированные в ТПР функции последействия также облегчат разработку приложений и повысят поддерживаемость кода, т.к. специфичные последействия необходимые лишь в одной ТПР не будут видны за пределами области видимости ТПР.
К недостаткам можно отнести следующие факты:
– Отказ от универсальной модели данных приводит к быстрому росту числа объектных таблиц в системе вместе с ростом количества таблиц принятия решений.
– Структура объектной ТПР неочевидна и может показаться запутанной на первый взгляд.
– Современные СУБД лучше оптимизированы для работы с реляционной моделью данных. Однако, реляционная ТПР будет быстрее объектной лишь в случае отказа от УМД. Так как в основе объектно-реляционной модели данных в Oracle лежит реляционная модель, ее производительность не сильно отличается от своей основы, а использование УМД приведет к снижению фактора кластеризации многих индексов и снизит эффективность их использования.
Рассмотрим концепцию создания объектной таблицы принятия решений.
Продукция в объектной таблице решений представляется одной строкой. В составе продукции могут быть как сравнения с примитивными типами, так и заключения, полученные на основе вложенных в нее объектных таблиц.
Объектная таблица принятия решений в своем составе может иметь как условия с участием примитивных типов, так и условия, в которых главным действующим лицом будет вложенная объектная таблица принятия решений. Подобную конструкцию можно увидеть на рисунке 7.
Рисунок – 7 Пример структуры ТПР объектного типа
На данном примере видно, что 3 столбца реализуют условия с участием примитивных типов, а в столбце BRCHS указан тип REF BRANCHES_OBJ_TYPE. Данный тип – ссылка на вложенную ТПР. В ее состав так же могут входить как условия с примитивами, так и с другими объектными ТПР. Нужно заметить, что столбец должен иметь тип именно объектной ссылки, а не быть объектного типа. А сами значения, на которые указывают oid, необходимо хранить в таблице, созданной командой типа:
CREATE TABLE TABLE_NAME OF OBJECT_TYPE;
Это необходимо сделать, чтоб избежать дублирования объектов при использовании схожих конструкций в рамках разных таблиц принятия решений.
Важно заметить, что помимо столбцов, у объектной ТПР должно быть реализовано несколько обязательных методов.
– Метод compare. Он должен быть включен во все без исключения объектные ТПР. Его задача – по переданному ключу найти необходимые для логического вывода факты в базе данных, и по ним проверить свою истинность.
– Метод STATIC find(КЛЮЧ_К_ОБЪЕКТУ). Он должен входить в состав коренной (не являющейся столбцом другой ТПР) ТПР и запускать процесс вывода в рамках данной таблицы и всех в нее вложенных. В качестве параметров метод должен принимать записи, являющиеся уникальным ключом строки базы, столбцы которой, в свою очередь, являются атрибутами продукции.
– STATIC aftereffect_ЛОГИЧЕСКОЕ_ИМЯ. Его назначение – хранить набор команд, которые следует выполнить после завершения прямого вывода. Так же следует заметить, что ТПР может иметь несколько таких методов, если входящие в ее состав продукции требуют разных последействий.
2. Интеграция объектных таблиц принятия решения в проект по распознаванию символов
2.1 Описание концепции приложения и роли ТПР в нем
В качестве проекта, в который была интегрирована система объектных таблиц принятия решений, выбрано приложение, цель которого – распознание символа с произвольным шрифтом, изображенного в растровом (BMP) файле. Данный процесс протекает в 2 этапа:
– Получение изображения из файла и сбор первичной информации об изображенном объекте средствами Java Development Kit 7.
– Глубокий анализ полученных данных и их унификация с символом при помощи таблиц принятия решений. Данные процессы протекают на сервере Oracle Data Base 11 XE и используют возможности данной СУБД.
Идея данного проекта отлично подходит под использование именно объектных таблиц принятия решений, так как:
– Приложение состоит не только из модуля принятия решений, а включает в себя еще и сложный процесс предобработки входных данных. Благодаря такому подходу к организации таблиц принятия решений можно построить более органичную архитектуру приложения в целом.
– Входные данные (в данной главе будет подробно описана их структура), на основании которых придется принимать решение о их соответствии какому-либо символу, очень разнородны. И поэтому задача получения атрибутов для ТПР сводится не только к извлечению оных из БД, но и их предобработке.
Так как тема данной дипломной работы – интеллектуальное расширение на основе объектных таблиц принятия решений, а вовсе не все приложение, этапы обработки данных будут описаны без углубления в программную реализацию.
Наиболее важные с точки зрения реализации алгоритмов части исходного кода можно найти в “Приложении А” к данной дипломной работе.
2.2 Первичная обработка bmp файла средствами Java Development Kit
В качестве средства изначальной обработки данных был выбран язык программирования Java, который отлично подходит для работы с неструктурированной информацией.
На первом этапе распознания нам необходимо решить задачу получения из растрового изображения набор точек, составляющих “каркас” нашего символа. Для примера на вход нашей java программы поступил файл с изображением цифры 6 (Рисунок 8).
Рисунок 8 – Входное изображение
После всей обработки Java модулем мы должны получить координаты и последовательность точек, выделенных красным на рисунке 9.
Рисунок 9 – Отмечены искомые точки
Алгоритм первичной обработки:
– Загрузка изображения в двумерный массив
– Получение каркаса изображения заключается в итеративном удалении пикселей, касающихся фона, с проверкой на сохранение связности каркаса. Каждый пиксель сначала помечается на удаление, а зануляется только после просмотра всего массива. Это позволяет сохранить перекрестия.
– Далее на нашем центральном контуре ищем точку, которая в окрестности радиуса 1 имела бы одного соседа. Если такая точка не была найдена (такое будет происходить, например, с числом 8)- ищем точку с максимальным числом соседей. Данная точка- начало пути обхода.
– Последовательно обходим наш контур от начала пути обхода, либо до конца контура, либо до первой точки с числом соседей больше двух. Если в центральном контуре есть перекрестки, то удобно выделить отдельные кривые без перекрестков. Назовем их “Ветви каркаса”. При попадании в перекресток, нужно завершить обход текущей ветви, и произвести обход из перекрестка в сторону каждого соседа помечая новые обходы как новые ветви. Алгоритм данного этапа вы можете найти в “приложении А”, в методе run(Token startPoint, int plusIDPoint) класса SerialChar.
– По ходу обхода контура формируем скрипт, добавляющий в таблицу в БД Oracle значения координат точек, направление шага (если в данную точку мы попали из соседа слева, то направление будет 0 градусов, если вверх – 90, вниз – 90, влево – 180),
В результате работы данного алгоритма в БД будут добавлены данные в таблицу capt_tbl.
2.3 Глубокий анализ первичной информации средствами Oracle
Теперь, имея начальные данные, мы можем собрать такие сведения о входном символе как:
– Общую информацию об объекте анализа
Общая информация об объектах хранится в таблице capt_obj_tbl, структура которой изображена на Рисунке 10.
Рисунок 10 – Структура таблицы capt_obj_tbl
Где:
ID_OBJECT – уникальный идентификатор объекта анализа (символа). Первичный ключ таблицы.
BRANCH_COUNT – число веток в объекте (понятие “ветка” введено в пункте 2.2)
POINT_COUNT – общее число точек в объекте. По данному показателю вычисляются относительные длины веток и прочие относительные длины, зачастую необходимые для принятия решения о определении какого либо объекта.
CREATE_DATE – дата внесения объекта в информационную систему
RESULT – результат распознавания символа. Заполняется в последнюю очередь. На данном этапе обработки остается равным NULL.
– Информацию о ветках объекта (термин “ветка” был описан выше, в пункте 2.2).
Расширенная информация о ветках символа хранится в таблице capt_brch_tbl структура которой изображена на (Рисунок 11).
Рисунок 11 – Структура таблицы capt_brch_tbl
Где:
ID_OBJECT – уникальный идентификатор объекта. Внешний ключ на capt_obj_tbl.
ID_BRANCH – уникальный идентификатор ветки объекта. В совокупности с ID_OBJECT образует первичный ключ данной таблицы.
POINT_COUNT – количество точек, из которых состоит данная ветка. Этот параметр участвует при расчетах относительной длинны ветки (относительно протяженности всего контура объекта), а так же его значение совпадает с id_point последней точки ветки.
SECTOR_COUNT – задает количество промежутков ветки, подпадающих под одно из определений: прямая, дуга, угол. Поиск секторов осуществляется на последних этапах анализа объекта при помощи объектной таблицы принятия решений. На данном этапе поле SECTOR_COUNT содержит значение null.
START_POINT_ID, END_POINT_ID – содержат ID особых точек (Внешний ключ к таблице CAPT_SPECIAL_POINTS. Данная таблица содержит подробную информацию о точках на концах контура объекта и перекрестках. Ее структура будет разобрана позднее), с которых начинался/закончился обход ветки.
RELATIVE_LENGTH – длинна ветки относительно общей длины границы объекта. Задана на интервале от 0 до 1. Достаточно важный параметр ветки сам по себе. Используется в таблице принятия решений на финальном этапе вынесения вердикта.
DESC_ORDER_FLAG – принимает значение 1, если ветка была пройдена снизу вверх или справа налево. Служит для определения правильного порядка обхода веток, на этапе их анализа при помощи ТПР.
– Информация о точках объекта анализа. В ней хранится результат первичного анализа изображения.
Рисунок 12 – Структура таблицы capt_tbl
Где:
ID_OBJECT – уникальный идентификатор объекта
ID_BRANCH – уникальный идентификатор ветки. Вместе с ID_OBJECT составляет внешний ключ к таблице capt_brch_tbl.
ID_POINT – порядковый номер точки при обходе ветки с текущим ID_BRANCH в рамках объекта с текущим ID_OBJECT.
X, Y – координаты точки на растровом изображении. Они могут понадобиться, когда форма анализируемого объекта не даст всех необходимых, для принятия решения, фактов. Например форма цифр 6 и 9 идентична, а все их различие заключается во взаимном расположении особых точек.
ANGLE – угол, под которым мы попадаем в текущую точку из предыдущей. Т.е. если мы переходим из пикселя вертикально вниз, то угол будет равен – 90 градусов. Вверх – 90. Влево – 180, вправо – 0.
CURVATURE – степень кривизны контура в данной точке. Вычисляется как разница между суммой углов предыдущей точки и текущей минус сумма углов двух следом идущих.
– Информация об особых точках объектах анализа.
Особыми точками будем называть точки лишь с одним соседом (на краю ветки), либо перекрестки (точки с тремя и более соседями). Информация о таких точках чрезвычайно важна для анализа исследуемого объекта. Часто можно решить задачу распознавания символа только лишь по типу и взаимному расположению особых вершин.
Рисунок 13 – Структура таблицы CAPT_SPECIAL_POINTS
Где:
ID_OBJECT – уникальный идентификатор объекта. Внешний ключ на capt_obj_tbl.
ID_SPOINT – уникальный идентификатор особой точки в рамках одного объекта анализа. В совокупности с ID_OBJECT образует первичный ключ.
POINT_TYPE – определяет тип особой точки (на границе, перекресток двух, трех или четырех ветвей)
X, Y – координаты особой точки на исходном растровом изображении.
Информация для данной таблицы вычисляется на основании таблиц.
2.4 Процесс распознавания символа при помощи объектных ТПР
В рамках задачи распознавания символа была организована структура таблиц принятия решений, изображенная на рисунке 14:
экспертный решение таблица символ
Рисунок 14 – Структура системы ТПР
Рассмотрим подробнее задачу каждой таблицы принятия решений:
– Object_obj_type ответственен за проверку числа особых точек и ветвей, а также за вызов вложенных в нее таблиц, производящих дальнейший анализ символа.
– Spec_point_obj_type проводит расширенный анализ числа и типа особых точек. Также, при необходимости, способен анализировать положение особых точек относительно друг друга.
– Branches_obj_type строка данной таблицы представляет собой продукцию, определяющую правильную последовательность веток
– Branch_obj_type анализирует длину ветвей, а так же порядок секторов (дуг, углов, прямых)
– Sect_obj_type производит измерение угла поворота ветвей (угол между направлениями вначале и в конце сектора), относительную длину сектора, а так же принадлежность его к тому или иному типу.
При анализе продукции, в антецеденте которой участвует вложенная таблица принятия решения, из функции compare анализируемой продукции будет рекурсивно вызвана вложенная таблица.
Заключение
В рамках данной работы был разработан подход создания таблиц принятия решений на основе объектных таблиц Oracle.
Создано приложение, позволяющее распознавать растровые изображения символов. В нее была интегрирована система объектных таблиц принятия решений.
Было произведено сравнение объектного и реляционного подхода создания интеллектуальных систем на базе таблиц принятия решений.
Список использованных источников
1 Базы знаний интеллектуальных систем. / Гаврилова Т.А., Хорошевский В.Ф – Питер, 2001, – С. 17-18
2 Бессарабов Н.В. Универсальная модель данных. / Н.В. Бессарабов, Е.С. Муса-Оглы – RSDN, 2011, №3 – С. 51-55.
3 Бессмертный И.А. Применение реляционных операций для логического вывода в продукционных системах. / И.А. Бессмертный – Изв. вузов. Приборостроение, 2010, – С. 34-38.
4 Википедия – свободная энциклопедия [Электронный ресурс]. URL: http://ru.wikipedia.org/ (дата обращения 03.06.2014)
5 Братко И. Алгоритмы искусственного интеллекта на языке PROLOG. / И. Братко – М.: Вильямс, 2004, – С. 331-334.
6 Бессарабов Н.В. Таблицы принятия решений, встроенные в базы данных. / Н.В. Бессарабов, Л.В. Семенютина – INTELS, 2014.
7 Национальный Открытый Университет “Интуит” [Электронный ресурс]. URL: http://www.intuit.ru (дата обращения 15.05.2014)
Приложение
Коды создания объектов БД, процедур сбора статистики и таблиц принятия решений:
CREATE TABLE “HR”.”CAPT_TBL” (
id_object number,
ID_branch NUMBER,
ID_point NUMBER,
X NUMBER,
Y NUMBER,
angle number,
curvature number default 0 not null,
primary key(id_object, id_branch, id_point)
)
create table capt_special_points(
id_object number,
id_spoint number,
point_type number,
x number,
y number,
primary key(id_object, id_spoint)
)
CREATE SEQUENCE capt_object_id_seq
START WITH 1
INCREMENT BY 1
NOCACHE
NOCYCLE;
CREATE OR REPLACE TRIGGER Print_salary_changes
BEFORE INSERT ON hr.capt_tbl
FOR EACH ROW
DECLARE
sal_diff number;
BEGIN
:new.id_object := capt_object_id_seq.nextval;
END;
drop table capt_obj_tbl;
create table capt_obj_tbl(
id_object number,
branch_count number,
point_count number,
create_date date,
result number,
primary key(id_object)
);
create table capt_brch_tbl(
id_object number,
id_branch number,
point_count number,
sector_count number,
start_point_id number,
end_point_id number,
relative_length number,
desc_order_falg char(1),
primary key(id_object, id_branch)
);
drop table branch_orientation;
create global temporary table branch_orientation (
id_object number,
id_branch number,
orientation char(1),
primary key(id_object, id_branch, orientation)
) on commit delete rows;
create global temporary table point_curvature (
id_branch number,
id_point number,
curvature number,
primary key(id_branch, id_point)
) on commit delete rows;
drop table capt_sector
create table capt_sector(
id_object number,
id_branch number,
id_sector number,
id_type_sector number,
angle number,
len number,
primary key(id_object, id_branch, id_sector)
)
create or replace procedure capt_calc_statistic(id_obj number) is
begin
insert into capt_obj_tbl(id_object, branch_count, point_count, create_date)
select max(id_obj), count(distinct ct.id_branch), count(1), sysdate
from capt_tbl ct
where ct.id_object = id_obj;
insert into capt_brch_tbl(id_object, id_branch, point_count, relative_length)
select max(ct.id_object), ct.id_branch, count(1), count(1) / max(co.point_count)
from capt_tbl ct
, capt_obj_tbl co
where ct.id_object = co.id_object
and co.id_object = id_obj
and ct.id_object = id_obj
group by ct.id_branch;
insert into capt_special_points(id_object, id_spoint, x, y, point_type)
with pre_spec_point as (
select id_obj, ct.x, ct.y
, case when count(distinct cb.id_branch) > 1 — = 2, = 3 …
then 1
else 0
end type
from capt_brch_tbl cb
join capt_tbl ct on cb.id_object = ct.id_object
and cb.id_branch = ct.id_branch
where ct.id_point = 1 or ct.id_point = cb.point_count
group by ct.x, ct.y
)
select id_obj, rownum, ps.x, ps.y, ps.type
from pre_spec_point ps;
update capt_brch_tbl cb
set cb.start_point_id = (select cs.id_spoint
from capt_tbl ct
join capt_special_points cs on ct.id_object = cs.id_object
and ct.x = cs.x
and ct.y = cs.y
where ct.id_point = 1
and ct.id_branch = cb.id_branch
and ct.id_object = id_obj),
cb.end_point_id = (select cs.id_spoint
from capt_tbl ct
join capt_special_points cs on ct.id_object = cs.id_object
and ct.x = cs.x
and ct.y = cs.y
where ct.id_point <> 1
and ct.id_branch = cb.id_branch
and ct.id_object = id_obj)
where cb.id_object = id_obj;
insert into branch_orientation(id_object, id_branch, orientation)
select cb.id_object, cb.id_branch
, case when ((ctf.x < ctl.x * 1.1) or (ctf.x < ctl.x and ctf.y < ctl.y))
then ‘A’
else ‘D’
end ord_flag
from capt_brch_tbl cb
join capt_tbl ctf on cb.id_object = ctf.id_object
and cb.id_branch = ctf.id_branch
and ctf.id_point = 1
join capt_tbl ctl on cb.id_object = ctl.id_object
and cb.id_branch = ctl.id_branch
and ctl.id_point = cb.point_count;
update capt_brch_tbl cb
set cb.desc_order_falg = (select bo.orientation
from branch_orientation bo
where cb.id_object = bo.id_object
and cb.id_branch = bo.id_branch)
where cb.id_object = id_obj;
for rec in (
select ct.id_branch
from capt_tbl ct
where ct.id_object = id_obj
group by ct.id_branch
) loop
insert into point_curvature(id_branch, id_point, curvature)
select l.id_branch
, l.id_point
, angle_diff(
angle_summ(lead(l.angle, 1) over (order by l.id_point), lead(l.angle, 2) over (order by l.id_point))
, angle_summ(lag(l.angle, 1) over (order by l.id_point), l.angle)
) * 2
from capt_tbl l
where l.id_object = id_obj
and l.id_branch = rec.id_branch;
end loop;
update capt_tbl ct
set ct.curvature = nvl((select pc.curvature
from point_curvature pc
where pc.id_branch = ct.id_branch
and pc.id_point = ct.id_point
and pc.id_point > 3
and exists(select null from point_curvature pcc where pcc.id_branch = pc.id_branch and pcc.id_point = pc.id_point + 2) ), 0)
where ct.id_object = id_obj;
end;
create or replace type sect_obj_type as object(
type number,
min_angle number,
max_angle number,
min_len number,
max_len number,
MEMBER FUNCTION compare(id_obj number, id_brch number, id_sect number) RETURN NUMBER
);
CREATE OR REPLACE TYPE BODY sect_obj_type IS
MEMBER FUNCTION compare(id_obj number, id_brch number, id_sect number) RETURN NUMBER IS
res number := 0;
BEGIN
select 1
into res
from capt_sector cs
where cs.id_object = id_obj
and cs.id_branch = id_brch
and cs.id_sector = id_sect
and cs.id_type_sector = type
and cs.angle between min_angle and max_angle
and cs.len between min_len and max_len
;
return res;
END;
END;
create or replace type branch_obj_type as object(
len number,
sector_count number,
sector1 ref sect_obj_type,
sector2 ref sect_obj_type,
sector3 ref sect_obj_type,
sector4 ref sect_obj_type,
sector5 ref sect_obj_type,
MEMBER FUNCTION compare(id_obj number, id_brch number) RETURN NUMBER
)
CREATE OR REPLACE TYPE BODY branch_obj_type IS
MEMBER FUNCTION compare(id_obj number, id_brch number) RETURN NUMBER IS
res number := 0;
sect_cnt number;
lengt number;
BEGIN
select cbt.sector_count, cbt.relative_length
into sect_cnt, lengt
from capt_brch_tbl cbt
where cbt.id_object = id_obj
and cbt.id_branch = id_brch;
if (len <> lengt or sect_cnt <> sector_count) then
return res;
end if;
dbms_output.put_line(res);
select deref(sector1).compare(id_obj, id_brch, 1)
into res
from dual;
if (sect_cnt >= 2 and res = 1) then
select deref(sector2).compare(id_obj, id_brch, 2)
into res
from dual;
end if;
if (sect_cnt >= 3 and res = 1) then
select deref(sector3).compare(id_obj, id_brch, 3)
into res
from dual;
end if;
if (sect_cnt >= 4 and res = 1) then
select deref(sector4).compare(id_obj, id_brch, 4)
into res
from dual;
end if;
if (sect_cnt >= 5 and res = 1) then
select deref(sector5).compare(id_obj, id_brch, 5)
into res
from dual;
end if;
return res;
END;
END;
drop type branches_obj_type
create or replace type branches_obj_type as object(
branch_count number,
brcp ref branch_obj_type,
brch2 ref branch_obj_type,
brch3 ref branch_obj_type,
brch4 ref branch_obj_type,
MEMBER FUNCTION compare(id_obj number) RETURN NUMBER
);
CREATE OR REPLACE TYPE BODY branches_obj_type IS
MEMBER FUNCTION compare(id_obj number) RETURN NUMBER IS
res number := 0;
brch_cnt number;
BEGIN
select co.branch_count
into brch_cnt
from capt_obj_tbl co
where co.id_object = id_obj;
if (branch_count <> brch_cnt) then
return res;
end if;
select deref(brcp).compare(id_obj, 1)
into res
from dual;
if (brch_cnt >= 2 and res = 1) then
select deref(brch2).compare(id_obj, 2)
into res
from dual;
end if;
if (brch_cnt >= 3 and res = 1) then
select deref(brch3).compare(id_obj, 3)
into res
from dual;
end if;
if (brch_cnt >= 4 and res = 1) then
select deref(brch4).compare(id_obj, 4)
into res
from dual;
end if;
return res;
END;
END;
drop type object_obj_type
create or replace type object_obj_type as object(
branch_cnt number,
spec_point_count number,
brchs ref branches_obj_type,
result number,
STATIC FUNCTION find(id_obj number) RETURN NUMBER,
MEMBER FUNCTION compare(id_obj number)RETURN NUMBER,
STATIC PROCEDURE write_result(id_obj number, res number)
);
CREATE OR REPLACE TYPE BODY object_obj_type IS
MEMBER FUNCTION compare(id_obj number) RETURN NUMBER IS
res number;
spc number;
BEGIN
select 1
into res
from capt_obj_tbl co
where co.id_object = id_obj
and co.branch_count = branch_cnt
and co.point_count = spec_point_count;
if (res = 1) then
select deref(brchs).compare(id_obj)
into res
from dual;
end if;
return res;
END;
STATIC FUNCTION find(id_obj number) RETURN NUMBER IS
brch_cnt number;
spc number;
res number;
BEGIN
select co.branch_count
into brch_cnt
from capt_obj_tbl co
where co.id_object = id_obj;
select count(1)
into spc
from capt_special_points csp
where csp.id_object = id_obj;
for rec in (select ref(cot) rf
from object_obj_tbl cot
where cot.branch_cnt = brch_cnt
and cot.spec_point_count = spc
and cot.brchs.compare(id_obj) = 1) loop
select deref(rec.rf).result
into res
from dual;
Dbms_Output.put_line(res);
write_result(id_obj, res);
end loop;
return 1;
END;
STATIC procedure write_result(id_obj number, res number) IS
BEGIN
update capt_obj_tbl co
set co.result = res
where co.id_object = id_obj;
commit;
END;
END;
create table sect_obj_tbl of sect_obj_type;
create table branch_obj_tbl of branch_obj_type;
create table branches_obj_tbl of branches_obj_type;
create table object_obj_tbl of object_obj_type;
