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

На правах рукописи

КУЗЕННЫЙ Виктор Викторович

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ИНТЕЛЛЕКТУАЛЬНОЙ СИСТЕМЫ РАЗРАБОТКИ СЦЕНАРИЕВ ДЛЯ ГЕОИНФОРМАЦИОННОГО МОДЕЛИРОВАНИЯ СЛОЖНЫХ ПРОЦЕССОВ

Специальность 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2013

Я АПР 20Ь

005057571

005057571

Работа выполнена в Федеральном государственном бюджетном учреждении науки Санкт-Петербургском институте информатики и автоматизации Российской академии наук (СПИИРАН).

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

профессор Попович Василий Васильевич

Официальные оппоненты: доктор технических наук, профессор,

заведующий лабораторией автоматизации научных исследований

СПИИРАН Александров Виктор Васильевич

кандидат технических наук, доцент,

начальник научно-исследовательского

сектора ОАО Концерн «Океанприбор» Федоров Сергей Алексеевич Ведущая организация:

Государственное образовательное учреждение высшего профессионального образования Санкт-Петербургский государственный электротехнический университет ЛЭТИ им. В.И. Ульянова (Ленина)

Защита состоится «2» апреля 2013 г. в 14.30 часов на заседании диссертационного совета Д.002.199.01 при Федеральном государственном бюджетном учреждении науки Санкт-Петербургском институте информатики и автоматизации Российской академии наук по адресу: 199178, Санкт-Петербург, В.О., 14 линия, 39.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Санкт-Петербургского института информатики и автоматизации Российской академии наук.

Автореферат разослан «1» марта 2013 г. Ученый секретарь

диссертационного совета Д.002.199.01

к.т.н.

Нестерук Филипп Геннадьевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы диссертации. Географические информационные системы (ГИС) в настоящее время находят широкое применение в различных сферах деятельности человека. Анализ современных полнофункциональных ГИС (ArcGIS, ERDAS, GeoMedia, Онтомап и др.), а также технологий их проектирования и реализации, показывает, что немаловажную роль на различных стадиях их жизненного цикла играют сценарные языки программирования. Многие задачи, возникающие при разработке и эксплуатации ГИС, решаются с помощью сценариев - программ, написанных на сценарных языках. Среди этих задачи: автоматизация процесса настройки и связывания готовых модулей для получения конечного решения ГИС под определенный класс задач и пользователей (XML, Groovy и др.); автоматизация процессов обработки геопространственных данных (Python и др.); геоинформационное моделирование сложных процессов и ситуаций, происходящих во времени, для выработки и обоснования управленческих решений (DroolsTabScene); настройка графического интерфейса ГИС под конкретные требования пользователя (VBScript, JavaScript, XML и др.) и другие.

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

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

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

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

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

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

2. Предложить структуру интеллектуальной системы разработки сценариев.

3. Предложить алгоритм поиска шаблонов разработки сценариев на основе методов интеллектуального анализа графов.

4. Разработать алгоритм извлечения знаний из сценариев на основе структурного обучения марковских логических сетей (МЛС).

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

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

Основные положения, выносимые на защиту:

1. Алгоритм поиска шаблонов разработки сценариев на основе адаптации алгоритма gSpaIl извлечения частых подграфов во множестве графов.

2. Алгоритм автоматического извлечения знаний из сценариев на основе структурного обучения марковской логической сети.

3. Программная архитектура интеллектуальной системы разработки сценариев.

Научная новизна:

1. Новизна первого результата заключается в применении и модификации известного алгоритма gSpan для решения задачи поиска шаблонов разработки сценариев в предлагаемой интеллектуальной системе. Модификация предусматривает добавление проверки устойчивости подграфов при поиске шаблонов.

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

моделировании извлекаемых знаний.

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

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

Обоснованность и достоверность научных положений, основных выводов и результатов диссертации обеспечивается за счет анализа современного состояния исследований в области проектирования и разработки сценариев для ГИС, согласованности теоретических выводов с результатами экспериментальной проверки на наборах сценариев, разработанных в СПИИРАН, а также апробацией основных теоретических положений диссертации в печатных трудах и докладах на международных научных конференциях.

Практическая ценность работы. В результате выполнения работы программно реализована интеллектуальная подсистема разработки сценариев для ИГИС (интеллектуальной ГИС). Разработанная система внедрена и используется в ряде НИОКР:

1. «Разработка оперативно-тактического тренажерного комплекса» (шифр — «Автоматизм»), Работа доведена до уровня серийного образца;

2. «Разработка автоматизированной геоинформационной системы для решения задач мониторинга дна моря в пунктах базирования сил ВМФ» (шифр - «Галтель - Алеврит»).

Апробация работы. Результаты работы докладывались на международном семинаре IF&GIS «Интеграция информации и геоинформационные системы» (Санкт-Петербург, 2009 год), Санкт-Петербургской международной конференции по интегрированным навигационным системам (Санкт-Петербург, 2010 год), конференции «Информационные технологии в управлении» (Санкт-Петербург, 2012 год), а также использовались в СЧ НИР «Обоснование состава, технических требований, вариантов построения и размещения интегрированных систем защиты объектов ОАО «Газпром», эксплуатируемых в шельфовых и морских зонах» («Интеграция - НТБВТ»),

Публикации. По материалам диссертации опубликовано 7 печатных работ, включая 2 публикации в научных журналах, рекомендованных ВАК («Труды СПИИРАН» и «IEEE Aerospace and Electronic Systems Magazine»).

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

объем работы составляет 129 страниц, в том числе 36 иллюстраций и 9 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Выполненный анализ можно разделить на следующие части:

1. Алгоритмы поиска шаблонов разработки сценариев. Под шаблоном разработки сценариев в данной работе понимается повторимая конструкция на сценарном языке, представляющая собой решение некоторой часто возникающей при разработке сценариев проблемы. Шаблон отражает некоторую синтаксическую структуру на сценарном языке и типы ее элементов без их конкретизации. В соответствии с данным определением один из подходов к поиску шаблонов разработки сценариев основывается на методах извлечения частых структур из данных (frequent substructure mining), которые в свою очередь можно разделить на три группы: методы поиска в наборах, методы поиска в последовательностях и методы поиска в графах. Так как структура программных сценариев формально описывается с помощью графов, то для решения задачи поиска шаблонов разработки сценариев целесообразно применять алгоритмы третьей группы, а именно извлечения частых подграфов из множества графов (frequent subgraph mining). Для выбора соответствующего алгоритма были сформулированы следующие требования к нему, а также к шаблонам, которые требуется искать:

- входные данные - ориентированные размеченные графы;

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

- алгоритм должен учитывать частоту использования шаблона;

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

- возможность задания ограничения на размер подграфов.

Сравнение существующих алгоритмов (MoFa, Gaston, gSpan, SUBDUE, AGM и др.) показало, что наиболее полно заданным требованиям удовлетворяет gSpan и его расширения, однако они не позволяют находить устойчивые шаблоны и в результате требуют доработки или модификации.

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

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

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

Извлечение знаний из сценариев можно рассматривать как структурное обучение MJIC, которое представляет собой процесс построения наилучшей MJIC, описывающей имеющиеся в репозитории сценарии. Большинство из существующих алгоритмов структурного обучения MJIC основано на поиске в пространстве клауз (дизъюнктов). Алгоритм LSM (Learning using Structural Motifs) является наиболее современным и основан на том соображении, что реляционные данные содержат часто повторяющиеся плотно связанные группы объектов. Такие группы называются структурными мотивами или шаблонами (structural motifs). Структурные мотивы формируют подмножества во множестве всех клауз, и если при обучении ограничивать поиск этими подмножествами, можно достаточно быстро найти "хорошие" правила, и тем самым повысить точность логико-вероятностного вывода в МЛС. В алгоритме LSM для поиска мотивов при структурном обучении МЛС применяется метод случайных блужданий по одному большому графу, который формируется по входным данным, что не совсем целесообразно в случае со сценариями для ГИС, репозиторий которых формально представляется в виде множества небольших несвязанных графов.

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

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

Ниже (рис. 1) представлена структура интеллектуальной системы разработки сценариев, в состав которой входит подсистема анализа с блоками

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

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

Рис. 1. Структурная схема интеллектуальной системы разработки сценариев

Задача поиска шаблонов разработки сценариев сформулирована как задача извлечения частых подграфов из множества графов (frequent subgraph mining) с учетом дополнительных требований. Пусть В = {bh b2, ..., b„} - множество базовых операторов (инструкций, команд) сценарного языка. Базовые операторы являются элементарными языковыми конструкциями, из которых разрабатываются сценарии. С использованием В был разработан некоторый набор сценариев DS = {Sh S2, ..., S^,}, которые хранятся в репозитории сценариев. Каждому сценарию .S', из DB ставится в соответствие ориентированный размеченный граф G„ множество вершин которого помечено элементами ЬкеВ. Между двумя вершинами в графе G, существует дуга, если оператор, соответствующий первой вершине следует в сценарии за оператором, соответствующим второй вершине. Другими словами, структура графа G, соответствует структуре сценария Граф G, называется граф-схемой сценария по аналогии с понятием граф-схемы алгоритма. Множество граф-схем сценариев, построенных для каждого S, е DS, обозначается через DG = {G;, G2, ..., Gpi}, где \DG\=\DS\. Пусть g - некоторый граф. При введенных обозначениях задача поиска шаблонов разработки сценариев с учетом требований, перечисленных в первой главе, формулируется следующим образом:

В заданном множестве DG граф-схем сценариев и при заданных константах <5щт и Кт¡п требуется найти набор шаблонов (подграфов) F = {g}, удовлетворяющих следующим требованиям:

sDG(g) = \SDG(g)\/\DG\>5min (1)

где - функция поддержки подграфа g множеством графов БС, равная

доли графов в ОС, которые содержат g; дрс^) - множество поддержки подграфа g, содержит все графы из в которые g входит хотя бы один раз; дтЫ - минимальный порог поддержки; 1оо(ё) ~ показатель устойчивости подграфа g, основанный на критерии Стьюдента:

tDfj(s)=

fig)' IL^/Ц,)

ш

N

где f(g) - нормированная частота вхождения подграфа g в DG; E(g) -множество ребер подграфа g; N - общее количество вершин в DG; tmirl — критическое значение показателя устойчивости.

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

1. Загрузить множество сценариев DS = {Sj, S2, ..., SBBi} из репозитория.

2. Сформировать множество графов DG = (С/, G2, ..., Gpi), то есть для каждого сценария 5, из DS построить граф-схему G, и добавить ее в DG.

3. Найти F множество граф-схем шаблонов разработки сценариев.

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

модифицированный с учетом добавленных условий алгоритм gSpan извлечения частых подграфов из множества графов. Данный алгоритм основан на поиске в глубину по дереву DFS-кодов (Depth First Search). DFS-код представляет собой последовательность дуг графа, которая получается в результате его обхода в глубину. При этом каждая дуга в данной последовательности представляется шестеркой (г, j, l„ 1„ Ц, d;j), где i - номер открытия первой вершины дуги при обходе графа в глубину, j - номер открытия второй вершины, /, - метка первой

5.

h

d -

метка и направление дуги

вершины, /у - метка второй вершины, соответственно. Очевидно, что у одного графа может быть много Г)Р8-кодов. Пример графа с соответствующим ему БРв-деревом и ОН8-кодом показан на рис. 2 (а, б, в):

(<0,U,a,y,->),

(2,3,х,с,z,-»),

(l,4,y,d,z,—>)) (в)

Рис. 2. Пример графа (а) с построенным для него DFS-деревом (б) и DFS-кодом (в)

Известно, что если определить лексикографический порядок на множестве всех ОРБ-кодов графа, то минимальный элемент данного множества будет совпадать с минимальным элементом аналогичных множеств графов, изоморфных данному. Дерево ЭР8-кодов строится так, что его обход в глубину позволяет пройти все минимальные [ЖЧ-коды, избавляя, таким образом, от необходимости проверки изоморфизма. При обходе ОРБ-дерева в глубину на каждом шаге достаточно проверить, является ли БРЗ-код минимальным. Если это не так, то соответствующий подграф далее не рассматривается и отсекается все идущее от данного узла поддерево. Если ОРБ-код - минимальный, то проверяется выполнение условия (1) постановки задачи. В случае невыполнения данного условия, подграф также отбрасывается и отсекается все идущее от данного узла поддерево. В обратном случае, проверяется условие (2), и если подграф удовлетворяет и этому условию, то он добавляется во множество иначе - нет. Таким образом, за счет отсечения сокращается пространство поиска и тем самым время работы алгоритма. Пример ЭРЗ-дерева приведен ниже на рис. 3:

Рис. 3. Пример ирй-лерева и иллюстрация работы алгоритма

Возможность отсечения поддерева при невыполнении условия (1) постановки задачи гарантируется свойством антимонотонности функции поддержки <5д0(£), которое означает, что если g' - подграф g, то доа(£') >

Известно, что задача поиска частых подграфов во множестве графов является ЫР-л одной. Если оценивать сложность через число проверок изоморфизма графов/подграфов, то она может быть ограничена величиной (Э(кРБ + г/0, где к - максимальное число изоморфизмов между частыми подграфами и графами из входного набора, ^ - число частых подграфов, 5 -размер входного набора графов, г - максимальное число дублирующихся Синодов для частого подграфа.

В третьей главе разработан алгоритм извлечения знаний из сценариев на основе модификации алгоритма ЬБМ структурного обучения МЛС.

Формально, МЛС представляет собой множество пар Ь = {(Т7,, м^)}, где — это формула логики предикатов первого порядка, а - вес данной формулы, являющийся действительным числом. МЛС Ь вместе с конечным множеством констант С={с/, с2, ..., С\С\} однозначно определяет марковскую сеть Мис,

содержащую:

- одну вершину для каждого возможного означивания (интерпретации) каждого предиката из Ь. Данной вершине присваивается значение 1, если ее означивание истинно, и 0 в обратном случае;

- один фактор (клику) для каждого означивания (интерпретации) каждой формулы из Ь с соответствующим весом и',-.

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

Р(Х=*)Цехр(|>Л(х)), (3)

где - это число формул в М£ С, «¿(х) - количество истинных означиваний (верных интерпретаций) формулы в мире х,Х~ нормировочная константа, которая вычисляется по формуле:

2 = 2]ехр(^или,(л0)

.геЛ' м

Пусть х = {х/,..., X),..., х„} - это реляционные данные, где х/ -истинностное значение (0 или 1) 1-го атома. Тогда задача структурного обучения МНС состоит в том, чтобы по данным х построить МЛС /^{(/^уи^)}, которая будет их описывать. Данную задачу принято разбивать на две подзадачи:

1. Выбор структуры МЛС, то есть построение множества формул Р, логики предикатов первого порядка.

2. Настройка (оценивание) весов м/1 МЛС, которые являются параметрами совместного распределения (3).

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

Рис. 4. Общая схема алгоритма 1,$М

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

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

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

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

Процедура генерации путей заключается в том, что для каждого подграфа, полученного на предыдущем шаге, формируется множество всевозможных путей, узлы которых представляют собой атомы. При построении МЛС полученные пути сначала преобразуются в конъюнкции атомов. Затем константы в атомах меняются на переменные, и после чего конъюнкции положительных литералов преобразовываются в дизъюнкции. Далее дизъюнкции перебираются в порядке возрастания их длины, начиная с самых коротких. Для каждой дизъюнкции с вычисляется значение оценки Score(c), и если оно положительно, то сравнивается со значениями оценок ее подклауз, которые уже были вычислены ранее. Если значение оценки клаузы с превышает значение оценок всех ее подклауз, то она добавляется в MJIC, иначе - отбрасывается. При этом оценка клаузы вычисляется по следующей формуле:

Scored) = WPLL, (x,wc)-WPLL^{x,wu)-n-d, где Lc - МЛС, включающая с и дизъюнкции с одним литералом для каждого предиката, wc - множество весов МЛС Lc, Lu — МЛС из дизъюнкций с одним литералом для каждого предиката (унарная МЛС), wu - множество весов МЛС Lu, d - длина дизъюнкции, ж - штрафной коэффициент, функция WPLL{x, w) -взвешенная логарифмическая функция псевдоправдоподобия (Weighted Pseudo-Log-Likelihood).

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

В соответствии со структурой, описанной во второй главе, была разработана трехуровневая распределенная программная архитектура (рис. 5), удовлетворяющая требованиям к программному обеспечению. Графический редактор, который входит в клиентский слой, может быть реализован на базе таких систем, как NetBeans, Eclipse и Protégé с добавлением динамически встраиваемого модуля (plug-in), реализующего функции автозавершения и вставки шаблона. Блоки логико-вероятностного вывода, обучения весов МЛС и анализа сценариев предлагается реализовывать в качестве компонентов промежуточного слоя (middleware) в составе сервера приложений JBoss. Для удаленного хранения сценариев и управления репозиторием может быть использована система контроля версий SVN (Subversion). Взаимодействие между ПО клиентского и промежуточного уровней предлагается осуществлять по протоколу REST (Representational State Transfer). База знаний будет

отображаться в реляционную СУБД PostgreSQL, доступ к которой выполняется по протоколу JDBC (Java Database Connectivity). Для интеллектуального анализа графов использовалась программная библиотека ParSeMiS с открытым исходным кодом, а для логико-вероятностного вывода в МЛС -масштабируемый решатель Tuffy. В рамках данной архитектуры основным языком реализации является Java, что обеспечивает разрабатываемой системе кроссплатформенность.

■ Ol

1 Plug-in формирования и | выдачи рекомендации

I

REST

|| Компонент II Компонент |

И структурного логико- I

II обучения вероятностного 1

1 МЛС m вывода в МПС В

Компонент обучения весов МЛС

HTTP

JDBC

IJDBC

JDBC

СИ HH^i fd (CT

SVN репозиторий JS сценариев/ PostgreSQL БД онтологии PostgreSQL БД шаблонов PostgreSOL БД МЛС (Tuffy)

Рис. 5. Программная архитектура интеллектуальной системы разработки сценариев

Предложенные во второй и в третьей главе алгоритмы были реализованы на языке Java и вошли в компоненты поиска шаблонов и структурного обучения МЛС соответственно. Объем программного кода компонента поиска шаблонов без учета библиотеки ParSeMiS, составил - 2106 строк, при этом общее количество классов - 8, количество пакетов классов - 2. Объем программного кода компонента структурного обучения МЛС составил - 4552 строк, при этом общее количество классов - 29, количество пакетов классов — 4.

При оценке производительности и времени работы алгоритмов все вычисления производились на компьютере с четырех-ядерным процессором Intel Core i7, имеющем тактовую частоту 3.40 ГГц, и 16 Гб оперативной памяти. При этом в качестве данных были использованы сценарии, разработанные на сценарном языке DroolsTabScene для ИГИС Онтомап. Репозиторий представляет собой базу из 2052 сценариев моделирования действий на море, разработанных в СПИИРАН (2007-2011). Язык DroolsTabScene включает в свой состав 32 оператора (действия). По репозиторию сценариев был сформирован набор из 3135 графов. Экспериментальный анализ частоты встречаемости подграфов в полученном наборе показал выполнимость закона Ципфа для разработанных на языке DroolsTabScene сценариев (рис. 6).

■

X

In (ранг) МОЙ

Рис. 6. Кривая ранг/частота для подграфов, полученных из сценариев

На рис. 7 показаны примеры граф-схем шаблонов, которые были получены в результате поиска модифицированным алгоритмом (5сепР5рап):

I / ' ■

next_âctlons ; next_actiorune><t_actions

Jl. *

подеце«армй Подсценарий

7Ш

next actionsnext actions / <

é

Подсценарий Подсценарий

(а) (б)

Рис. 7. Примеры полученных шаблонов из трех (а) и четырех (б) операторов

Количество шаблонов, полученных в результате поиска модифицированным алгоритмом, по сравнению с исходным сократилось на 27%, а время поиска - на 6%. На рис. 8 приведена сравнительная гистограмма количества шаблонов от их размера:

«IgSpon SiScenGSpan

3 2

Размер шаблонов

Рис. 8. Гистограммы количества шаблонов от их размера

Для сравнения предложенного адаптированного алгоритма ALSM для извлечения знаний из сценариев с известным LSM алгоритмом была выбрана реализация последнего, входящая в состав системы Alchemy (http://alchemy.cs.washington.edu/) с открытым исходным кодом. Из репозитория сценариев с использованием 58 предикатов были сформированы два набора атомов: один для обучения MJ1C (748 атомов), другой (тестовый) для оценки результата обучения (254 атома). Ниже (табл. 1) приведены примеры формул с весами MJIC, полученной в результате работы адаптированного алгоритма LSM:

Веса Формулы

0.16367 !putObProperties(al) v \next actions(a2,al)

6.54404 pntObProperties(al) v \next actions(a2,al)

-2.81921 \putOnMap{al) v \next actions(al ,a2) v putOnPlace{a2)

-2.96045 \delay(al) v !next actions(al,a2) v \timeMessage(a2)

1.02106 calculus(al) v \next actions(al,a2) v \mark(a2)

6.26834 delay(al) v \next actionsial,a2) v \timeMessage(a2)

-3.86666 \calculus(al) v \next actions(al,a2) v \mark(a2)

4.2229 putOnMap(al) v \next actions(al,a2) v \pntOnPlace(a2)

-10.6869 \putOnMap(al) v \next actions(al,a2) v \putOnPlace(a2)

Табл. 1. Примеры формул с весами, полученных в результате обучения MJ1C

Оценка производительности адаптированного алгоритма LSM и его сравнение с исходным выполнялись с применением логико-вероятностного вывода по тестовым данным в MJIC, полученных тем и другим алгоритмами. Вывод осуществлялся с применением метода Монте-Карло по схеме марковской цепи, реализованного в Alchemy. Каждый запуск логико-вероятностного вывода генерировал 10000 выборок. Для оценки производительности сравниваемых алгоритмов обучения применялось два показателя. Первый из них - среднее значение логарифма условного правдоподобия по всем тестовым атомам (CLL -conditional log-likelihood), позволяющего непосредственно показать качество полученных вероятностных оценок. В качестве второго показателя вычислялось значение площади под кривой точности-полноты (AUC — area under the precision-recall curve). Кривые точности/полноты (рис. 9) были построены путем варьирования порога (threshold) отсечения по значению CLL, превышение

Рис. 9. Кривые точности/полноты

Значения, приведенные в табл. 2, показывают, что адаптированный алгоритм позволяет достичь улучшения показателя CLL на 14,6%, а AUC - на

ALSM LSM

CLL AUC Время (мин.) CLL AUC Время (мин.)

-0,015±0.04 0.502±0.01 10.36 -0.1±0.01 0.326±0.03 10.58

Табл. 2. Значения показателей CLL и AUC Для вычисления временных затрат на разработку сценариев с использованием предложенной интеллектуальной системы применялась модель KLM-GOMS (Keystroke-level model - Goals, Operators, Methods and Selection Rules) оценки качества интерфейсов. Результаты вычислений показали, что учет опыта на основе поиска и использования шаблонов разработки сценариев позволяет снизить временные затраты от 5,4% до 25,2% в зависимости от степени подготовки разработчика.

ЗАКЛЮЧЕНИЕ

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

1. Известный алгоритм gSpan извлечения частых подграфов из множества графов адаптирован к поиску шаблонов разработки сценариев за счет добавления проверки устойчивости подграфов при поиске, что позволило повысить точность поиска на 27% и сократить время на 6%.

2. Предложен подход к автоматическому извлечению знаний из сценариев на основе структурного обучения марковских логических сетей. Разработан модифицированный LSM алгоритм структурного обучения MJIC, в котором перебор формул осуществляется в пределах часто повторяющихся групп связанных объектов, предварительно получаемых с помощью алгоритмов извлечения частых подграфов из множества графов, а именно адаптированного gSpan алгоритма. Применение предложенного модифицированного LSM алгоритма для извлечения знаний из сценариев позволило добиться повышения точности и полноты выдачи рекомендаций при поддержке разработки сценариев на 10,8%.

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

4. Реализован прототип интеллектуальной системы разработки сценариев. Анализ результатов работы с данным прототипом показал, что использование предложенной системы позволяет сократить трудозатраты

на разработку сценариев от 5,4% до 25,2% в зависимости от уровня подготовленности разработчика.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в рецензируемых изданиях из списка ВАК

1. Кузенный В.В. Повышение эффективности разработки сценариев в интеллектуальной среде моделирования / Васильев П.В., Кузенный В.В. // Труды СПИИРАН. Вып. 19, 2011, С. 288-297.

2. Kuzyonny, V. Intellectual Geographic Information System for Navigation Safety / Popovich, V., Vanurin, S., Kokh, S., Kuzyonny, V. // IEEE Aerospace and Electronic Systems Magazine, August, 2011, pp. 29-31.

Публикации в других изданиях

3. Кузенный В.В. Оптимизация визуальной среды пространственного моделирования / Осипов В.Ю., Кузенный В.В. // Труды СПИИРАН. Вып. 12,2010, С. 235-246.

4. Кузенный В.В. Интеллектуальные геоинформационные системы в интересах навигационной безопасности / Попович В.В., Ванурин С.М., Кох С.А., Кузенный В.В. // Материалы XVII Санкт-Петербургской международной конференции по интегрированным навигационным системам, ЦНИИ «Электроприбор», 31 мая - 2 июня 2010, Санкт-Петербург, С. 226-228.

5. Kuzyonny V. Data Harmonization in CIS / Pankin A., Kuzyonny V. // Information Fusion and Geographic Information Systems, Lecture Notes in Geoinformation and Cartography, Edited by Vasily Popovich, Manfred Schrenk, Christophe Claramunt, Kyrill Korolenko, Springer, 2009, pp. 227240.

6. Кузенный В.В. Интеллектуальный анализ сценариев моделирования пространственных процессов // Материалы конференции «Информационные технологии в управлении» (ИТУ-2012), ЦНИИ «Электроприбор», 9-11 октября 2012, Санкт-Петербург, С. 431.

7. Kuzyonny V. Remote Sensing Data Analysis Based on Hierarchical Image Approximation with Previously Computed Segments / Galiano P., Kharinov M., Kuzyonny V. // Information Fusion and Geographic Information Systems, Lecture Notes in Geoinformation and Cartography, Edited by Vasily Popovich, Manfred Schrenk, Christophe Claramunt, Kyrill Korolenko, Thomas Devogele, Springer, 2011, pp. 119-128.

Подписано в печать 28.02.2013г. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 2999.

Отпечатано в ООО «Издательство "J1EMA"» 199004, Россия, Санкт-Петербург, В.О., Средний пр., д. 24 тел.: 323-30-50, тел./факс: 323-67-74 e-mail: izd_lema@mail.ru http://www.lemaprint.ru