Методы и средства построения интеллектуальных систем в троичной логике тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Королева Юлия Александровна

• Королева Юлия Александровна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Королева Юлия Александровна

ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ ТЕКУЩИХ ИССЛЕДОВАНИЙ И ПОСТАНОВКА

ЗАДАЧ ИССЛЕДОВАНИЯ

1.1 АНАЛИЗ СОСТОЯНИЯ ПРОБЛЕМЫ В ОБЛАСТИ БАЗ ЗНАНИЙ

1.1.1. Проблема поиска в частично определенных базах знаний

1.1.2. Особенности поиска в допущениях открытого и замкнутого мира 16 1.2. ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ

1.2.1. Анализ особенностей троичной логики и ее применения в базах знаний

1.2.2. Постановка задач исследования

Выводы

ГЛАВА 2. РАЗРАБОТКА МЕТОДОВ ПОСТРОЕНИЯ ЧАСТИЧНО ОПРЕДЕЛЕННЫХ БАЗ ЗНАНИЙ

2.1. ОРГАНИЗАЦИЯ БАЗ ЗНАНИЙ В ТРОИЧНОЙ ЛОГИКЕ

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

2.1.2. Способы построения правил в базисе троичной логики

2.2. МЕТОДЫ ГЕНЕРАЦИИ ТЕРНАРНЫХ БАЗ ЗНАНИЙ

2.2.1. Разработка алгоритма преобразования бинарных фактов в тернарные

2.2.2. Разработка алгоритма автоматического создания отрицающих фактов на основе словаря взаимоисключающих состояний

Выводы

ГЛАВА 3. ОРГАНИЗАЦИЯ ЛОГИЧЕСКОГО ПОИСКА В ЧАСТИЧНО

ОПРЕДЕЛЕННЫХ БАЗАХ ЗНАНИЙ

3.1. РАЗРАБОТКА МЕТОДОВ ПОИСКА В БАЗИСЕ ТРОИЧНОЙ ЛОГИКИ

3.1.1. Анализ особенностей поиска решений в частично определенных базах знаний

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

3.2. РАЗРАБОТКА МЕТОДА ПОИСКА В ТРОИЧНОЙ ЛОГИКЕ И В РАСШИРЯЮЩЕМСЯ ДОМЕНЕ

3.2.1. Метод устранения неопределенностей в расширяющемся домене

3.2.2. Визуализации результатов поиска в частично определенных базах знаний

Выводы

ГЛАВА 4. МЕТОДЫ РЕДУЦИРОВАНИЯ ПРОСТРАНСТВА ПОИСКА В

РАСШИРЯЮЩЕМСЯ ДОМЕНЕ

4.1. РЕДУЦИРОВАНИЕ ПРОСТРАНСТВА ПОИСКА В БАЗИСЕ ТРОИЧНОЙ ЛОГИКИ И В РАСШИРЯЮЩЕМСЯ ДОМЕНЕ

4.1.1. Анализ списков неопределенных фактов при поиске в базах знаний на основе троичной логики

4.1.2. Разработка алгоритма редуцирования списков неопределенных фактов

4.2. АНАЛИЗ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ РЕДУЦИРОВАНИЯ ПРОСТРАНСТВА ПОИСКА

4.2.1. Сравнительный анализ разработанных алгоритмов редуцированных списков неопределенных фактов

4.2.2. Анализ эффективности поиска в расширяющемся домене

Выводы

ГЛАВА 5. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ ОРГАНИЗАЦИИ И ПОИСКА В БАЗАХ ЗНАНИЙ НА ОСНОВЕ ТРОИЧНОЙ ЛОГИКИ

5.1. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ ГЕНЕРАЦИИ БАЗ ЗНАНИЙ ИЗ ТРОИЧНОЙ ЛОГИКИ

5.1.1. Реализация алгоритмов преобразования двоичных баз знаний в тернарные

5.1.2. Реализация алгоритма создания отрицающих фактов

5.2. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДОВ ПОИСКА В ТРОИЧНОЙ ЛОГИКЕ

5.2.1. Реализация алгоритмов редуцирования списков неопределенных

фактов

5.2.2 . Организация поиска в расширяющемся домене

Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Приложение

Программная реализация библиотеки для построения визуализации списков

недостающих фактов

Приложение

Программная реализация алгоритмов редуцирования списков

неопределенных фактов на языке PL/SQL

Приложение

Блок-схема Алгоритма 4.1 для редуцирования списка неопределенных

фактов

Приложение

Блок-схема Алгоритма 4.2 для редуцирования списка неопределенных

фактов

Приложение

Реализация программы на языке Prolog для экспериментального

исследования времени вывода в расширяющемся домене

Приложение

Акт о внедрении результатов интеллектуальной собственности

ВВЕДЕНИЕ

Введение диссертации (часть автореферата) на тему «Методы и средства построения интеллектуальных систем в троичной логике»

Актуальность проблемы

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

Информационные технологии всегда были сосредоточены именно на получении и хранении информации и существующих знаний, также, как и политика в области науки инноваций и технологий в первую очередь направлена на накопление, создание и распространение знаний. Ввиду того, что информационные и наукоемкие технологии в последнее время привлекают повышенное внимание и занимают центральное место в планах развития любой корпорации и развитых государств, различные знания генерируются огромными темпами, превращаясь во многие терабайты данных и приобретая распределенную структуру хранения и представления, подтверждая тем самым понятие «общества знаний» [1], [2]. Распределенными знаниями и базами знаний, в контексте данной работы, предлагается называть знания не только распределенные территориально, но и отличающиеся узкой предметной областью, знания, получаемые из различных внешних источников, путем их осмысленного объединения. Использование распределенных знаний, по сути, является основным источником новых идей и методов для развития в странах с низким и средним уровнем технологий [3]. Соответственно, невозможно представить развитие информационных технологий без высокопроизводительных обучающихся информационно-поисковых систем, позволяющих реализовать быстрый поиск новых или существующих знаний и использующих современные возможности вычислительной техники в совокупности с

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

Степень теоретической разработанности темы

Основные идеи искусственного интеллекта были сформулированы в работах Маккарти Дж., Саймона Г., Ньюэла А., основоположника теории нечетких множеств - Заде Л. [4], [5], [6]. Наибольший вклад в развитие многозначной логики был сделан Керолом Л., Лукасевичем Я. [7], Брусенцовым Н.П. [8]. Достижения в области ситуационного управления проходили под руководством Поспелова Д. А. [9], [10], [11]. Значительный вклад в теорию и практику экспертных систем и баз знаний был внесен Гаазе-Раппопортом М.Г. [12], [13], Гавриловой Т.А., Хорошевским В.Ф., Бессмертным И.А. [14], [15] Еремеевым А.П. [16], [17], Вагиным В.Н., Курейчиком В.М.

Объект исследования

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

Предмет исследования

Методы логического поиска в базах знаний.

Цель и задачи исследования

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

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

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

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

4. Экспериментальное исследование разработанных методов и алгоритмов повышения качества и полноты поиска в распределенных базах знаний.

Теоретическая и методическая основа исследования

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

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

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

Положения, выносимые на защиту, обладающие научной новизной

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

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

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

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

Практическая значимость исследования

Полученные результаты внедрены в информационную систему университета ИТМО, а также в учебный процесс на кафедре вычислительной техники Университета ИТМО для студентов, обучающихся по направлениям 09.04.01 — Информатика и вычислительная техника и 09.04.04 — Программная инженерия.

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

Апробация результатов исследования

Основные положения диссертационной работы и результаты исследований докладывались на различных конференциях, в числе которых ХLIV научная и учебно-методическая конференция Университета ИТМО

(2015г.); Межд. конгресс по интеллектуальным системам и информационным технологиям К&ГГ'14 (2014г.); IV Научно-практическая конференция молодых ученых «Вычислительные системы и сети», «Майоровские чтения» (2013г.); Межд. конгресс по интеллектуальным системам и информационным технологиям ^&ГГ'13 (2013г.); V Российская мультиконференция «Информационные технологии в управлении» (ИТУ-2012).

Публикации результатов исследования

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

Личный вклад

Все результаты, представленные в диссертации, получены лично автором. Постановка экспериментов делалась совместно с научным руководителем.

Объем и структура работы

Диссертационная работа изложена на 105 страницах, состоит из введения, пяти глав, содержащих 10 рисунков, 7 таблиц и заключения. Библиографический список включает 95 наименований. В приложении к диссертации представлены блок-схемы разработанных алгоритмов, тексты реализованных программ, акт о внедрении результатов интеллектуальной деятельности.

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

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

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

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

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

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

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

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

На предварительно сформированной тестовой базе знаний проведена серия экспериментов по оценке эффективности и целесообразности

расширения пространства поиска путем предварительного формирования гиперсписка фактов, недостающих для доказательства истинности цели.

Пятая глава посвящена практической реализации. Приводится описание подсистемы «Командировки» информационной системы университета, в которой использованы разработанные методы. Для апробации, тестирования и оценки эффективности созданных алгоритмов построена тестовая база знаний, предложенные в работе алгоритмы были реализованы на языке PL/SQL, на основании того, что в своих информационно-программных решениях информационная система университета использует базу данных Oracle.

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

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

ГЛАВА 1. АНАЛИЗ ТЕКУЩИХ ИССЛЕДОВАНИЙ И ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ

1.1 АНАЛИЗ СОСТОЯНИЯ ПРОБЛЕМЫ В ОБЛАСТИ БАЗ ЗНАНИЙ

1.1.1. Проблема поиска в частично определенных базах знаний

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

В распределенных базах знаний, из-за нарастающего количества данных, возникает проблема не только поиска данных различной природы и накопления знаний на их основе, но и накоплении метаинформации о том, где эти данные располагаются и с помощью каких средств их можно извлечь. Значительный вклад в теорию и практику ЭС и БЗ внесли и продолжают вносить Гаврилова Т.А. [18], Хорошевский В.Ф. [19], Бессмертный И.А. [20], Еремеев А.П. [21], [22] и др. исследователи. Прежде чем переходить к проблеме поиска в частично определенных базах знаний, стоит рассмотреть информационные системы, работающие с текстовыми документами или текстовыми данными для поиска и извлечения информации, так как знания базируются на информации.

Все многообразие информационных систем, работающих с текстовыми документами или текстовыми данными можно разделить на несколько типов:

1. Информационно-поисковые системы.

2. Системы выборки данных.

3. Комбинированные. Совмещают в себе подходы информационно-поисковых систем и систем выборки данных.

Основные отличия информационно-поисковых систем от систем выборки данных заключаются в том, что в системах выборки данных более строгие правила к поисковым запросам, классификациям документов, языку запросов [23]. Например, в системах выборки данных язык запросов является искусственным (язык SQL для реляционных баз данных), более того системы выборки данных неустойчивы к ошибкам в данных и запросах. Более того, в информационно-поисковых системах можно использовать не строгие булевы правила для выборки документов, а непосредственно и троичную логику, [24] и разрабатываемые в работе алгоритмы.

Классическим примером систем выборки данных выступают реляционные СУБД. Однако на текущий момент, можно отнести и ряд NoSQL баз данных к данному виду систем. Для систем выборки данных основные задачи состоят в надежном и эффективном хранении и извлечении данных, а так же высокой скорости выполнения запросов пользователей [25].

Информационно-поисковые системы решают же ряд других задач. Для этих систем важно решить общую задачу поиска, в отличие от систем выборки данных, где поиск выполняется на точное соответствие. Помимо этого, конечной целью поиска является выбор соответствующей поисковому запросу информации, степень соответствия которой определяется смысловой близостью к поисковому запросу пользователя, а это значит, что все запросы должны выполнять на естественном языке или приводиться к этому языку с помощью внутренних системных текстовых препроцессоров [26], [27].

Помимо этого, на основе одной из множества существующих классификаций информационно-поисковые системы можно условно разделить на:

• неформализованные;

• формализованные.

В упрощенном виде для осуществления поиска в информационно-поисковых системах может быть выполнена следующая последовательность действий:

1. Необходимо найти ресурс, на котором гипотетически или фактически может располагаться искомая информация.

2. Далее на ресурсе осуществляется поиск документа, в котором могут располагаться нужные данные.

3. После чего уже внутри документа ищется подходящее заданному запросу утверждение.

Наиболее удобным и распространенным способом поиска необходимого ресурса является метаинформация о том, где и какие данные располагаются. Поиск данных внутри определенного документа, построенного в соответствии с одной из существующих онтологии, аналогичен SQL-запросу [28], [29], [30]. В большинстве случаев сложность возникает при поиске самого документа на ресурсе. Человеко-ориентированные информационно-поисковые системы, такие как Google, Yahoo, Yandex и др., неэффективны, из-за того, что HTML-теги или другие разметки не индексируются. Не так давно стали возникать сервисы, предоставляющие возможность поиска формализованных данных, в качестве наиболее известных примеров можно привести - SWOOGLE и SWSE. SWOOGLE анализирует документы и собирает метаданные и отношения между этими метаданными. Помимо этого, документы индексируются с помощью информационно-поисковой системы, в случае с SWOOGLE используется программное обеспечение Apache Lucene. В частности, используются символы N-gram или URIs, как термы для быстрого нахождения документов, которые соответствуют запросу пользователя, или нахождения похожих наборов документов. Одно из главных свойств, которое вычисляется для каждого документа - это его ранг. Ранг показывает меру важности документа в Semantic Web. Помимо этого также существовали попытки моделирования правил для извлечения знаний с помощью искусственных языков в системах управления базами данных, то есть попытки сформировать базы знаний средствами самой СУБД

В данной работе более подробно будет рассмотрен второй этап поиска -поиск на ресурсе. Как показано на рисунке 1.1 поиск может быть реализован на основе двух подходов:

• путем сужения домена поиска;

• путем расширения домена поиска.

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

Расширение домена поиска (на рисунке 1.1 показано как округлые изогнутые стрелки) часто приводит к неоправданно большому времени поиска из-за того, что неизвестно до какой степени потребуется расширение домена поиска. В других случаях неоправданно большое время поиска может быть получено в результате обработки сложных правил, невзирая на сравнительно небольшие объемы данных, в данной области было проведено исследование, описание которого приведено в разделе 3.2.1 и получены

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

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

1.1.2. Особенности поиска в допущениях открытого и замкнутого мира

Допущение открытого мира (англ. OWA, open-world assumption) в формальной логике - это предположение о том, что истинность искомого утверждения не зависит от того, известно истинно/ложно искомое утверждение или нет конкретному наблюдателю или агенту.

Оно противоположно допущению о замкнутости мира (англ. CWA, closed world assumption), из которого следует, что утверждение, о котором известно, что оно истинно, считается истинным, любое другое утверждение считается ложным [33].

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

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

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

Допущение открытого мира используют языки семантической паутины, например, такие как RDF(S) и OWL. Отсутствие искомого результата в пределах ресурса означает, что искомое утверждение явно не существует или не было создано, безотносительно того, было бы утверждение истинным или нет, или от того, возможно ли, что это утверждение может быть истинным или ложным. Только в допущении замкнутого мира вследствие отсутствия искомого утверждения агент

(рассуждатель, машина) вывода позиционирует как результат поиска, что искомое утверждение ложно.

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

1.2. ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ

1.2.1. Анализ особенностей троичной логики и ее применения в базах знаний

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

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

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

информационной системе об окружающем мире только с помощью источников знаний [36].

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

Таким образом, единственным логичным решением в данном случае является допущение открытого мира. Так как в допущении замкнутого мира существование отрицательного решения и отсутствие решения в результате поиска рассматривались как тождественные решения, это повлекло за собой возникновение специфического термина «négation as failure». В допущении открытого мира существование отрицания рассматривается как противоречие (négation as contradiction). То есть, истинность утверждения не может зависеть от того, известно ли оно определенному человеку или нет.

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

Для реализации допущения открытого мира более логичным будет использование не бинарной логики, а троичной, в силу того, что, кроме двух состояний, которые могут принимать утверждения, истина (true) и ложь (false), добавляется промежуточное состояние возможно или неизвестно (unknown), которое соответствует отсутствию решения, таким образом:

Список литературы диссертационного исследования кандидат наук Королева Юлия Александровна, 2015 год

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Robertson, Paul L., Smith, Keith. Distributed Knowledge Bases in Low and Medium Technology Industries // AIRC Working Paper Series, 2008. -Т. 6. -C.93-117.

2. Чернавский Д. С. Синергетика и информация: Динамическая теория информации // Либроком, 2009. -C. 304.

3. Goldman, Arieh. Characterizing the technology firm: An exploratory study // Research Policy, 2006 г. -Т. 35. -C.121-143.

4. Заде Л. А. Основы нового подхода к анализу сложных систем и процессов принятия решений // Математика сегодня. -Москва: Знание, 1974.

5. Заде Л. А. Понятие лингвистической переменной и его применение к принятию приближенных решений // Математика. Новое в зарубежной науке. -Москва: Мир, 1976.

6. Zadeh L.A. Toward a Theory of Fuzzy Systems// Aspect Network and System Theory. -New York : Rinehart and Winston, 1971.

7. Лукасевич Я. Аристотелевская силлогистика с точки зрения современной формальной логики. -Москва: Иностранная литература, 1959.

8. Брусенцов Н. П. Исчерпывающее решение «неодолимой» проблемы парадоксов. -Москва: Фонд "Новое тысячелетие", 2008.

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

10. Нарьяни А., Яхно Т. Представление знаний в человеко-машинных и робототехнических системах. -Москва: ВЦ АН СССР ВИНИТИ, 1984. -Том А. Фундаментальные исследования в области представления знаний.

11. Поспелов Д. А. Ситуационное управление. Теория и практика. -Москва: Наука, 1986.

12. Аверкин А. Н., Гаазе-Рапопорт Д. А., Поспелов, Д. А. Толковый словарь по искусственному интеллекту. -Москва: Радио и связь, 1992.

13. Поспелов Д.А., Гаазе-Рапопорт М.Г., Семенова Е.Т. Порождение структур волшебных сказок. -Москва: Научный Совет по комплексной проблеме "Кибернетика" при Президиуме АН СССР, 1980.

14. Бессмертный И.А. Методы, модели и программные средства для построения интеллектуальных систем на продукционной модели знаний. дис.д-ра тех.наук: 05.13.11/ Бессмертный Игорь Александрович // - Санкт-Петербург, 2014. -С. 304.

15. Бессмертный И. А. Интеллектуальные системы на продукционной модели знаний: Проблемы практической реализации // Lap Lambert Academic Publishing GmbH & Co. KG, 2012.

16. Еремеев А. П. Королев Ю. И. Средства моделирования на основе темпоральных сетей Петри для интеллектуальных систем поддержки принятия решений // Тезисы докладов Тринадцатой национальной конференции по искусственному интеллекту КИИ-2012. -Белгород, 2012.

17. Еремеев А.П., Куриленко И.Е. Компонента временных рассуждений для интеллектуальных систем поддержки принятия решений реального времени // Искусственный интеллект и принятие решений, 2009. -№ 1. -С. 32-45. -ISSN 2071-8594. URL: http://aidt.ru/images/documents/2009-01/31 45.pdf

18. Частиков А.П., Гаврилова Т.А., Белов Д.Л. Разработка экспертных систем. Среда CLIPS. -Санкт-Петербург: БХВ-Петербург, 2003.

19. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем // Питер. -Санкт-Петербур, 2001.

20. Bessmertnyi I., Nevidimov A., Eliseev S. About creating intelligence systems in ternary logic // Proc. of 4th Int'l Conf. on knowledge engineering and ontology development. -Barcelona: SciTePress, 2012. -С. 161-165. ISBN 978-989-856530-3.

21. Еремеев А.П., Куриленко И.Е. Средства темпорального вывода для интеллектуальных систем реального времени // Интеллектуальные системы. -Москва: Физматлит, 2010.

22. Еремеев А.П., Куриленко И.Е. Темпоральные модели на основе логики ветвящегося времени в интеллектуальных системах // Искусственный интеллект и принятие решений, 2011. -№1. -С.14-26.

23. Schalkoff Robert J., Intelligent Systems: Principles, Paradigms, And Pragmatics. Massachusetts // Jones & Bartlett Learning, 2009.

24. Selinger P. G., Astrahan M.M., Chamberlin D. D., Lorie R. A., Price T. G. Access Path Selection in a Relational Database Management System // California : IBM Research Division, San Jose, 1979.

25. Гергей Т. Когнитивные системы - потребность информационного общества и вызов компьютерным наукам // Труды Девятой Национальной Конференции по Искусственному Интеллекту. -Москва: Физматлит, 2004.

26. Алиев Р.А., Алиев P.P. Теория интеллектуальных систем. -Баку: Чашигоглу, 2001.

27. Kurilenko I.E., Eremeev A.P. Temporal reasoning component for real-time intelligent decision-support systems // Journal Scientific and Technical Information Processing, 2011. -№ 38. Issue 5. -C. 332-343.

28. Кузнецов О.П., Суховеров В.С, Шипилина Л.Б. Онтологии в современных информационных системах: состояние, проблемы, перспективы // Датчики и системы. -№8. Москва: СенСиДат-Контрол, 2011.

29. Bratko Ivan. Prolog Programming for Artificial Intelligence (International Computer Science Series). 4th Edition. -USA: Boston: Addison Wesley, 2011.

30. Date C. J. SQL and Relational Theory: How to Write Accurate SQL. -California: O'Reilly Media, 2011.

31. Kaula, Rajeev. Data Modeling of Knowledge Rules: An Oracle Prototype // Journal of Software. Missouri State University. Springfield. - USA, 2012. -С. 2857-2865.

32. Филиппов В.А. Интеллектуальный анализ данных: методы и средства. -Москва: Едиториал, 2001.

33. Cadoli M., Lenzerini M. The complexity of prepositional closed world reasoning and circumscription // Journal of Computer and System Sciences. -France: Arras, 1994.

34. Ю.А. Королёва. Тезисы - Проблемы поиска в частично определенных базах знаний // Сборник тезисов докладов конгресса молодых ученых. Электронное издание. -Санкт-Петербург: Университет ИТМО, 2015. URL: http: //openbooks .ifmo .ru/ru/file/869/869.pdf.

35. Бессмертный И.А., Катериненко Р.С. Компетентностная модель искусственного интеллекта // Труды конгресса по интеллектуальным системам и информационным технологиям IS&IT'11. -Москва: Физматлит Минобрнауки РФ. РАИИ. Технологический институт ЮФУ, 2011. -Т. 3. -С. 11-16. ISBN 978-5-9221-1329-8.

36. Davis, Randall. Knowledge-Based Systems in Artificial Intelligence // McGraw-Hill advanced computer science series. -New York, 1981.

37. Зверев Г.Н. Объективные многозначные логики в интеллектуальных системах моделирования и обработки информации // Вестник УГАТУ. -Уфа, 2003. -Т. 4, -№ 1.

38. Michael, Negnevitsky. Artificial Intelligence: A Guide to Intelligent Systems . 2nd Edition // Addison-Wesley. -Boston, 2004.

39. Cox E. Relational database queries using fuzzy logic // Artificial Intelligence Expert, 1995. -С. 23-29.

40. Bosc, Patrick и Pivert, Olivier. On a fuzzy bipolar relational algebra // Information Sciences: an International Journal, 2013. -Т. 219, -С. 1-16.

41. Galindo, Jose. Handbook of Research on Fuzzy Information Processing in Databases // Information Science Reference. -Hershey, 2008.

42. Zadeh L.A., Nikravesh M., Aminzadeh F. Computing with Words and the BISC Decision Support System // Proceedings of IV Int. Conference on Soft Computing and Measurements, 2002.

43. Zongmin, Yan, Li, Ma. Soft Computing in XML Data Management // Springer-Verlag Berlin Heidelberg. -Berlin, 2010.

44. Bosc P., Pivert O. SQLf: a relational database language for fuzzy querying // Fuzzy Systems, IEEE Transactions on, 1995. -Т. 3. -С. 1-17.

45. Kacprzyk J., Zadrozny S. FQUERY for Access: fuzzy querying for a Windows-based DBMS. Fuzziness in Database Management Systems (Studies in Fuzziness and Soft Computing) // Physica. Amsterdam, 1995. -С. 415-433.

46. Goncalves Marlene, Tineo Leonid. SQLfi sus Aplicaciones // Revista Avances en Sistemas e Informática, 2008. -Т. 5. -С. 33-40.

47. Yager, Ronald R. Soft querying of standard and uncertain databases // Fuzzy Systems, IEEE Transactions on, 2010. -Т. 18, -С. 336-347.

48. Fernández, Alberto, и др. A study of the behaviour of linguistic fuzzy rule based classification systems in the framework of imbalanced data-sets // Fuzzy Sets and Systems, 2008. -Т. 159. -С. 2378-2398.

49. Calero, Julio, и др. An Experience in Management of Imprecise Soil Databases by Means of Fuzzy Association Rules and Fuzzy Approximate Dependencies // Porto, 2004. ICEIS 2004.

50. Ross Timothy. J. Fuzzy Logic with Engineering Applications. Third Edition // Wiley. -USA: New Jersey, 2010.

51. Kosko B. Neural Networks and Fuzzy Systems: A dynamical systems approach to machine intelligence // Englewood Cliffs: Prentice Hall int.ed., 1992.

52. Zadeh Lotfi A. Fuzzy Logic, Neural Networks, and Soft Computing // Communications of the ACM, March 1994. -С. 77-84. -Т. 3.

53. Нариньяни А.С. НЕ-факторы // Труды Девятой Национальной Конференции по Искусственному Интеллекту. Москва: Физматлит, 2004.

54. Кэролл Л. Символическая логика. Москва: Мир, 1973.

55. Stakhov A. Brousentsov's ternary principle, Bergman's number system and ternary mirror-symmetrical. -Ukraine: British Computer Society, 2002.

56. Rusu, O., Halcu, I., и др. Converting unstructured and semi-structured data into knowledge // IEEE 2013. Roedunet International Conference (RoEduNet). -Sinaia, 2013. 11th. -С. 1-4.

57. Brewka С., Dix J., Konolige К. Nonmonotonic Reasoning: An Overview. -Stanford, 1995.

58. Bowen Kenneth A. Prolog & Expert Systems Programming. -USA: New York Mcgraw-Hill College, 1991.

59. Belisle E., Huang Z., Le Digabel S., Gheribi A.E. Evaluation of machine learning interpolation techniques for prediction of physical properties // Computational Materials Science, 2015. -С.170-177.

60. Кузнецов О.П. Когнитивная семантика и искусственный интеллект и принятие решений //Искусственный интеллект и принятие решений. -Москва: Институт системного анализа РАН, 2012. -№4.

61. Карпенко А.С. Логический подход к искусственному интеллекту: От классической логики к логическому программированию. -Москва, 1990.

62. Zadeh L.A, Yager R.R. Uncertainty in Knowledge Base. Berlin // SpringerVerlag, 1991.

63. Королёва Ю. А., Бессмертный И. А. О построении интеллектуальных систем в троичной логике // Программирование. Pleiades Publishing, Ltd. -Москва, 2014. -№ 1. -С. 31-35.

64. Королёва Ю. А., Бессмертный И. А. Применение троичной логики в интеллектуальных информационно-управляющих системах // Тезисы докладов 5-й Российской мультиконференции «Информационные технологии в управлении» (ИТУ-2012). -Санкт-Петербург, 2012. -С. 567-572.

65. Рассел С., Норвиг П. Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach (AIMA). 2-е. -Москва: "Вильямс", 2007.

66. Королёва Ю. А., Бессмертный И. А. Способ организации фактов в базах знаний, ориентированный на создание и использование прецедентов // Труды межд. конгресса по интеллектуальным системам и информационным технологиям IS&IT14. -Москва: Физматлит Минобрнауки РФ. РАИИ. Технологический институт ЮФУ, 2014. -C245-250.ISBN 978-5-9221-1329-8.

67. Королёва Ю.А., Бессмертный И.А., Суринов Р.Т. Использование прецедентов для редуцирования дерева решений в задаче поиска путей на графе // Научно-технический вестник информационных технологий, механики и оптики. -Санкт-Петербург, 2015. -Т.15. -№ 1. -С. 166-168. -ISSN 2226-1494.

68. Saha A., Setua S.K. Architectural model for next generation content management system // Electrical and Computer Engineering (ICECE), 2014 International Conference. -Dhaka, 2014. -С. 437-440.

69. Никитин Н.О. К вопросу моделирования динамических процессов накопления знаний в интеллектуальных системах // Научный журнал. РГТУ: Вестник РГТУ. -Москва, 2013. №14/13. серия «Информатика. Защита информации. Математика».

70. Виноградов Г.П. Индивидуальное принятие решений: поведение целеустремленного агента. Научная монография. -Тверь, 2011. -С. 164.

71. Ullman Jeffrey. Principles of Database & Knowledge-Base Systems: Classical Database Systems. -United Kingdom : Computer Science Press, 1990.

72. Ibaraki T., Kameda T. Optimal Nesting for Computing N-Relational Joins // ACM Transactions on. Database Systems. September 1984.

73. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Динамическое программирование // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. Москва: Вильямс, 2005.

74. Габасов Р.Ф., Кириллова Ф. М. Основы динамического программирования. -Минск: Изд-во БГУ, 1975.

75. Rijsbergen C. Information Retrieval // Dept. of Computer Science: University of Glasgow, 1979.

76. Brin Sergey, Lawrence Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine // Computer Networks and ISDN Systems, 1998. -Т. 30. -С. 107-117.

77. Peter Marendy. A Review of World Wide Web searching techniques, focusing on HITS and related algorithms that utilise the link topology of the World Wide

Web to provide the basis for a structure based search technology, 2001. [Электронный ресурс] / Peter Marendy. - Режим доступа к документу: http://citeseer.nj.nec.com/559198.html.

78. Haveliwala Taher. Efficient computation of pagerank // Stanford University. -Stanford, 1999.

79. Zamir, Oren и Etzioni, Oren. Web document clustering: a feasibility demonstration. -New Yourk, 1998.

80. Weiss, Dawid. Introduction to Search Results Clustering. Rzeszow // Proceedings of the 6th International Conference on Soft Computing and Distributed Processing, 2002.

81. Grana M., Toro C., Posada J., Howlett R.J., Jain L.C. Advances in Knowledge-Based and Intelligent Information and Engineering Systems // IOS Press. -San Sebastian, 2012.

82. Bin Pei, Suyun Zhao, Hong Chen, Xuan Zhou, Dingjie Chen. Mining fuzzy association rules from a probabilistic quantitative database // Information Sciences: an International Journal, 2013. -С. 242-260.

83. Кормен Томас Х., и др. Introduction To Algorithms. -Москва. Вильямс, 2012.

84. Charras, Christian, Lecroq, Thierry. Exact string matching algorithms // Rouen: Université de Rouen, 1997.

85. Luhn H. P. A statistical approach to mechanised encoding and searching of library information // IBM Journal of Research and Development, 1957. -Т. 1. -С. 309-317.

86. Королёва Ю.А. Метод извлечения знаний в условиях неполной определенности // Сборник трудов 4-й Научно практической конференции молодых ученых «Вычислительные системы и сети». -Санкт-Петербург, 2013. -С. 11-13.

87. Shepherdson J. C. Negation as Failure, Completion and Stratification // Handbook of Logic in Artificial Intelligence and Logic Programming / edited by

Dov M. Gabbay, Christopher John Hogger, John Alan Robinson. Oxford University Press, 1998.

88. Королёва Ю. А., Бессмертный И. А. Поиск в базах знаний в базисе троичной логики и расширяющемся домене // Труды Международного конгресса по интеллектуальным системам и информационным технологиям IS&IT'2013. -Москва: Физматлит. Минобрнауки РФ. РАИИ. Технологический институт ЮФУ, 2013. -С. 128-132. ISBN978-5-9221-1329-8.

89. Бессмертный И.А. Визуализация знаний на основе семантической сети // Программирование. -Москва: Pleiades Publishing, 2010.

90. Gawlick D., Ghoneimy A., Zhen Hua Liu. Situation aware computing for big data // Washington DC: IEEE, 2014. Big Data 2014 IEEE International Conference on. -С. 1-6.

91. Katerinenko R.S., Bessmertnyi I.A. A method for acceleration of logical inference in the production knowledge model // Programming and Computer Software, 2011. -Т. 37. -№ 4, -С. 197-199.

92. Овчинникова И. Г., Сахнова Т. Н. Алгоритмы сортировки при решении задач по программированию // Информатика и образование, 2011. -С. 53-56.

93. Сэлтон Г. Автоматическая обработка, хранение и поиск информации. -Москва: Сов. радио, 1973.

94. Rajendra Akerkar, Priti Sajja. Knowledge-Based Systems. -Sudbury, Massachusetts: Jones and bartlett publishers, 2010.

95. Tweedale Jeffrey W., Jain Lakhmi C. Knowledge-Based Information Systems in Practice (Smart Innovation, Systems and Technologies). -USA: New York: Sringer, 2015.

Приложение 1.

Программная реализация библиотеки для построения визуализации списков

недостающих фактов.

<i__*********************************************************************__i>

Реализация визуализации списков недостающих фактов выполнена на языке javascript, согласно стандарту ES5 и использует открытую библиотеку построения графов vis.js http://visjs.org/. Визуализация выполняется средствами vis.js, предварительно происходит разбор списков недостающих фактов для передачи их в удобном формате библиотеке vis.js. Наибольший интерес представляет метод разбора списка недостающих фактов buildPredicatesNetwork.

Автор: Королёва Ю. А. (с) Университет ИТМО, 2015 <i__*********************************************************************__i>

<html> <head>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/vis/3.11.0/vis.min.js"></script>

<link type="text/css" src="https://cdnjs.cloudflare.com/ajax/libs/vis/3.11.0/vis.min.css" /> </head> <body>

<div id="mynetwork"></div> <script type="text/javascript"> (function() { "use stict";

/****************************************************************************

Метод для преобразования списков недостающих фактов из prolog-списков в значения, которые использует библиотека vis.js, в частности в javascript-массивы данных

Аргумент 1: Принимает исходный список недостающих фактов

Возвращаемое значение: javascript-объект с двумя массивами: узлы и связи. ****************************************************************************/

function buildPredicatesNetwork(prologPredicates) {

//локальные переменные для разбора списка предикатов и хранения узлов и связей

var i = 0,

level = 0, node = {}, nodesTemp = [], edgesTemp = [], arrld = 0;

for (i = 0; i < prologPredicates.length; i++) { if (prologPredicates.charAt(i) == '[') { level++;

if (nodesTemp.length == 0) { arrld = 0; nodesTemp.push({ id: arrld, label: "", level: level

}); } else {

arrId++;

nodesTemp.push({ id: arrId,

label: "", level: level

});

edgesTemp.push({

from: (level - 2), to: arrId

});

}

} else if (prologPredicates.charAt(i) != '[' && prologPredicates.charAt(i) != ']') {

if (!(prologPredicates.charAt(i) === ',' && prologPredicates.charAt(i + 1) === '[')) {

nodesTemp[arrId].label = nodesTemp[arrId].label +

prologPredicates.charAt(i);

}

} else if (prologPredicates.charAt(i) == ']') { level-- ;

}

}

return {

"nodes": nodesTemp, "edges": edgesTemp

};

}

// подготавливаем данные для визуализации var container = document.getElementById('mynetwork'), prologPredicates =

"[bonnie,canMarry,clyde,[bonnie,oppositeSex,clyde,[bonnie,hasSex,female]],[NO T,bonnie,closeRelative,clyde]]",

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

data = buildPredicatesNetwork(prologPredicates), // преобразование списка недостающих фактов в удобный для vis.js вид options = {

width: '100%', height: '100%', hierarchicalLayout: true

},

network = {}; //Визуализация списка недостающих фактов network = new vis.Network(container, data, options); })(); </script>

</body> </body> </html>

Приложение 2.

Программная реализация алгоритмов редуцирования списков

неопределенных фактов на языке PL/SQL.

/****************************************************************************

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

Автор: Королёва Ю. А. (с) Университет ИТМО, 2015 ***************************************************************************/

create table no info lists (id number,

list name varchar2(4000),

CONSTRAINT no_info_lists_pk PRIMARY KEY (id)); /****************************************************************************

Создание таблицы для функций связанных с неизвестными фактами в системе.

Автор: Королёва Ю. А. (с) Университет ИТМО, 2015 ***************************************************************************/

create table no info

(function name varchar2(4000), question for user varchar2(4000), list id number,

CONSTRAINT list_id_fk foreign key (list_id) references no info lists(id));

create index no info IX2 on no info (list id) tablespace FLOW_1160600771459341 _

pctfree 10 initrans 2 maxtrans 255 storage (

initial 64K next 1M minextents 1 maxextents unlimited

);

/****************************************************************************

Реализация Алгоритма 4.1 для редуцирования списков неопределенных фактов, описанный в главе 4 диссертации.

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

Входные параметры: отсутствуют

Выходные параметры: результат редуцирования списков - true или false

Автор: Королёва Ю. А. (с) Университет ИТМО, 2015 ***************************************************************************/

create or replace function reduction min return boolean is v return value boolean := false;

v exists number; v max function varchar2(4000); v max question varchar2(4000); v exists list boolean := true; begin

--проверка наличия списков для редуцирования

select count(*) into v exists from dual where exists(select * from

no info);

--если списков для редуцирования нет, выйти из функции вернув false-значение

if v exists = 0 then

return false; end if;

--до тех пор пока существуют списки для редуцирования, выполнить

while v exists

loop

--выбрать функцию и вопрос к функции на основании минимальной длины списка, то есть начать рассмотрение значений списков наименьшей длины select function name, question for user into v max function, v max question

from no info s where s.list id = (

select list id

from no info group by list id

having count(*) = (select min(cn) from (select count(*) cn,

list id

from no info group by list id))); --получить ответ от эксперта, либо отложено запустить процедуру по расписанию и предоставить возможность ответить эксперту в любой момент, либо в режиме реального времени

v return value := get answer on question(v max function, v max question);--получаем ответ от пользователя.

if v return value = true then --если результат истина, то проверить не является ли в этом списке это утверждение единственным и если является, то выйти из цикла

select min(count(*)) into v exists from no info p where p.list id in (select list id from no info s where s.function name = v max function) group by p.list id;

delete from no info s where s.function name = v max function; if v exists = 1 then

exit; end if;

else

-- в противном случае удалить список, так как одно из утверждений ложно

delete from no info s where s.list id = (select distinct list id from no info p where p.function name = v max function); end if; commit;

select count(*) into v exists from dual where exists(select * from no info);

--если больше нет списков для редуцирования, то выйти из цикла if v exists = 0 then

v exists list := false; end if; end loop;

--возврат результата редуцирования, return v return value;

end;

/****************************************************************************

Реализация Алгоритма 4.2 для редуцирования списков неопределенных фактов, описанного в главе 4 диссертационной работы. Алгоритм находит элементы или

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

Входные параметры: отсутствуют

Выходные параметры: результат редуцирования списков - true или false

Автор: Королёва Ю. А. (с) Университет ИТМО, 2015 ***************************************************************************/

create or replace function reduction_max return boolean is

v return value boolean := false; -- возвращаемое значение

v exists number;

v max function varchar2(4000);

v max question varchar2(4000);

v exists list boolean := true;

begin

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

select count(*) into v exists from dual where exists(select * from

no info);

if v exists = 0 then

return false; end if;

-- до тех пор пока списки есть в системе произвести их редуцирование while v exists loop

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

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

select function name, question for user into v max function, v max question

from no info group by function name, question for user having count(*) = (select max(cn) from (select count(*) cn from no info group by function name, question for user)); --получение информации от пользователя, на основе которой будут формироваться дальнейшие утверждения, данная процедура может запускаться по расписанию или в режиме реального времени с выяснением результата, для редуцирования списка, то есть эксперт даст ответ на вопрос, тем самым делая выбранное утверждение истинным или ложным

v return value := get answer on question(v max function, v max question);

if v return value = true then -- если получено, что искомое утверждение истинно, найти рассматриваемое утверждение в с писке неопределенных утверждений

select min(count(*)) into v exists from no info p where p.list id in (select list id from no info s where s.function name = v max function) group by p.list id;

-- удалить только рассматриваемое утверждение из списка неопределенных утверждений

delete from no info s where s.function name = v max function;

if v exists = 1 then -- если рассматриваемое утверждение истинно и оно является единственным в списке неопределенных утверждений, выйти из цикла, так как искомое утверждение - истинно exit; end if;

else

-- в противном случае удалить список, так как одно из утверждений ложно

delete from no info s where s.list id = (select distinct list id from no info p where p.function name = v max function); end if; commit;

select count(*) into v exists from dual where exists(select * from no info);

-- если больше нет списков, завершить цикл if v exists = 0 then

v exists list := false; end if; end loop; -- вернуть результат редуцирования return v return value; end;

Приложение 3.

Блок-схема Алгоритма 4.1 для редуцирования списка неопределенных

фактов

Конец

Приложение 4.

Блок-схема Алгоритма 4.2 для редуцирования списка неопределенных

фактов

Приложение 5.

Реализация программы на языке Prolog для экспериментального

исследования времени вывода в расширяющемся домене

/****************************************************************************

Программа на языке prolog в нотации swi-prolog для экспериментального исследования времени вывода в расширяющемся домене.

Для запуска программы необходимо в среде swi-prolog загрузить программу с данным файлом и в консоли набрать:

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

go3. —для измерения времени поиска в расширенном домене по различным файлам

Автор: Королёва Ю. А. (с) Университет ИТМО, 2015 ****************************************************************************/

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

:- dynamic f/3, i/1, j/1, k/1.

-- вычисление количества людей женского пола

to3 :- f( ,has sex,female), inc j( ), fail.

to3 :- j(N), write(' females='), write(N), reset j, fail.

--считаем количество людей мужского пола

to3 :- f( ,has sex,male), inc j( ), fail.

to3 :- j(N), write(' males='), write(N), reset j, fail.

--определяем людей у которых есть дети

to3 :- f( ,has child, ), inc k( ), fail.

to3 :- k(N), write(' has child='), write(N), reset k, fail. to3. _ _

использование троичной логики для определение наличия истинности/ложности и отсутствии информации об определенном факте

fact(Subj,Pred,Obj,1,[]) :- f(Subj,Pred,Obj).

если известно, что субъект мужского пола с достоверностью «-1» - это означает, что это женский пол

fact(Subj, has sex, male, -1, []) :-f(Subj, has sex, female).

если известно, что субъект женского пола с достоверностью «-1» - это мужской пол

fact(Subj, has sex, female, -1, []) :-f(Subj, has sex, male).

факт с достоверностью 0 не может иметь фактов с достоверностью «-1»

fact(S,P,O,0,[S,P,O]) :- not(f(S,P,O)),not(fact(S,P,O,-1,_)).

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

говорит о том, что факт того, что этот человек является дядей не определен,

на основе чего и будет сформирован гиперсписок неопределенных фактов **************************************************************************/

fact(X2, uncle,X4,Cty,[L1,L2,L3,L4]) :-

fact(X2,has sex,male,Cty3,L3), Cty3>=0, fact(X1,has_child,X3,Cty2,L2), Cty2> 0, fact(X1,has_child,X2,Cty1,L1), Cty1>=0, fact(X3,has_child,X4,Cty4,L4), Cty4>=0, Cty is min(Cty1,min(Cty2,min(Cty3,Cty4))). g4 :- dynamic f/3.

--определение методов инкрементирования счетчиков inc i(J) :- retract(i(J)), J1 is J+1, assert(i(J1)). inc j(J) :- retract(j(J)), J1 is J+1, assert(j(J1)). inc k(J) :- retract(k(J)), J1 is J+1, assert(k(J1)). inc u(J) :- retract(u(J)), J1 is J+1, assert(u(J1)).

-- методы для сброса счетчиков в нулевые значения reset i :- retractall(i( )),assert(i(0)). reset j :- retractall(j( )),assert(j(0)). reset k :- retractall(k( )),assert(k(0)). reset u :- retractall(u( )),assert(u(0)).

--принудительная сборка мусора и сброс всех счетчиков и существующих фактов reset :- retractall(f( , , , )),g4,

retractall(f( , , )),garbage collect, reset i,reset j,reset k,reset u.

--метод для определения возможного состояния того, что человек является дядей g(LL) :- findall(L,fact( ,uncle, ,0,L),LL),inc u( ).

--метод гарантированно выбирающий и подсчитывающий количество человек, которые являются дядями

g3 :- fact( ,uncle, ,1, ), inc u( ), fail.

g3 :- u(N), write(' uncle='), write(N), nl, reset u,fail. g3.

--вспомогательные методы для формирования гиперсписков достоверных фактов solve([]).

solve([H|T]):- solve1(H), solve(T). solve([[A,B,C,D] | T]) :-

solve1(A), solve1(B), solve1(C),solve1(D), solve(T). solve1([]).

solve1([S,P,O]):- fact(S,P,O,1,_). /**************************************************************************

--реализация цикла for на языке Prolog с использованием рекурсии; реализовано

для удобного подключения и быстрого прохождения по множеству файлов **************************************************************************/

for(I, Start, Finish):-

Start > Finish, !, fail; I is Start;

for(I, Start + 1, Finish).

--добавление и поиск фактов сначала в узком домене, после чего в расширяющемся домене go(C,D) :- reset,

working directory(Path, Path), nl, write(Path), atom concat(Path,C,Str3), atom concat(Str3,'.txt',Str4), A = [Str4], consult(A), to3, g3,

get_time(T11), g(LL),

get_time(T12), T111 is T12-T11, reset,

working directory(Path, Path), nl, write(Path), atom concat(Path,D,Str5), atom concat(Str5,'.txt',Str6), B=[Str6], consult(B), sort(LL,Out),

get_time(T13), solve(Out),!, get_time(T22), T222 is T22-T13,

Tkonec is T222+T111, write(' Tkonec = '),write(Tkonec).

-- добавление и поиск фактов сразу в расширенном домене go0(S) :- reset,

atom_concat('D:/exp/2 0_8 0/D2-2 0-8 0-',S,Str3),

atom concat(Str3,'.txt',Str4),

A = [Str4],

consult(A),

to3,

get_time(T11),

g3, %-----

get_time(T12), Tim_D1_D2 is T12-T11,

write(' Tim_D1_D2= T12-T11 ='),write(Tim_D1_D2). /**************************************************************************

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

именно этот метод вызывается в консоли программы первым **************************************************************************/

go2 :- for(I,1,10),C is I*5000,D is I*20000,go(C,D),fail. /***************************************************************

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

в консоли программы вторым **************************************************************************/

go3 :- for(I,1,5),S is I*25000, go0(S),fail.

Приложение 6.

Акт о внедрении результатов интеллектуальной собственности

федеральное государственное автономное учреждение высшею образования САНКТ-ПЕТЕРБУРГСКИЙ Н АЦИОН AJ1ЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОН1ГЬ1Х ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

О внедрении п информационном' систему университета и учебным процесс результатов диссертационной работы Ко ролен он Юл ни Александровны «Методы н средства построения интеллектуальны к систем в троичной логике» на соискание ученой степени кандидата технических ниук по специальности 05.13,11 «Математическое и программное обеспечение вычислительных машин, комплексов и ком и ь ю г ерны\ сетей»

Комиссия в составе

председателя дл",н., профессора, заведующего кафедрой вычисли дельной

техники Алиева Гауфнка Измайловы ча и членов к/г.н,, начальника денарта\1йР1та ипформаци онны\

технологий Поповой Ирины Анатольевны,

Д-T.el, профессора, профессора кафелры вычислительной

техники Ьогйтырева В л ад и м и ра Ан ато л ьеьн ча,

к.т.н., доцента, доцента кафедры вычислительной техники

11 оля ко на Владимира Ивановича

составила настоящий акт о том, что результаты интеллектуальной деятельности аспиранта кафедры вычислительной техники Королёвой Юлии Александров!гы, лежащие в основе сс диссертационной работы, внедрены в информационную систему университета ИТМО, а также в учебный процесс на кафедре вычислительной техники Университета ИТМО дли студентов, обучающихся но направлению 09.04.04 - Программная инженерия.

Внедрение заключается в следующем:

АКТ

1. Королёва Ю.А. разработала метол обработки данных и троичной логике и алгоритмы, повышающие качество и полноту поиска в распределенных базах знаний,

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

3- Разработанные методы и алгоритмы используются к процессе автоматизации обработки данных н составе информационной системы У ни верситета ИТМ 0.

Члены комиссии

11опова И .Л.