ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
17 June 2024

Software package for structural similarity analysis of systems taking placement of fragments into account

The article was published in issue no. № 4, 2010
Abstract:We introduce the original software tools for building and analysis of the stratified system of structural complexity and similarity models. The models are based on the characterization of placement of fragments in a system topology. The software tools are implemented as a subsystem of the integrated research environment «Graph Model Workshop» and are used in studies of equality and tolerance relations of various graph models of systems.
Аннотация:Рассмотрены оригинальные программные средства, реализующие построение и анализ системы моделей струк-турной сложности и сходства, основанных на характеризации расположения фрагментов в топологии структур. Данные средства реализованы в виде подсистемы АСНИ «Graph Model Workshop» и нашли применение при исследовании отношений эквивалентности и толерантности на графовых моделях систем.
Authors: (aneznanov@hse.ru) - , Ph.D, (viktorkokhov@rambler.ru) - , Ph.D
Keywords: software package, structural analysis, structural complexity, graph model of system, structure
Page views: 13360
Print version
Full issue in PDF (6.26Mb)
Download the cover in PDF (1.28Мб)

Font size:       Font:

Подпись:  
Рис. 1. BCOM(Emb, C£1, v³1, 2 %<Max(D1)<100 %)В настоящее время актуальной задачей является создание программных средств, позволяющих повысить эффективность исследования отношений эквивалентности и толерантности структур, что определяется потребностями анализа структурного сходства систем в различных областях (химическая информатика, распознавание образов, структурная лингвистика, интеллектуальный анализ данных). Наиболее общими подходами к анализу структурного сходства графовых моделей систем (ГМС) являются подструктурный (на основе поиска максимальных общих фрагментов ГМС) и структурно-характеристический (на основе сравнения различных видов моделей структурной сложности ГМС). Авторы активно участвуют в развитии оригинального обобщенного подструктурного подхода к анализу сходства, основанного на построении структурных инвариантов ГМС, позволяющих исследовать структурное сходство с учетом расположения и сходства расположения фрагментов в топологии ГМС. Стратифицированная иерархическая система моделей структурной сложности, предложенная в [1], получила название системы g-моделей (SGM). Одним из результатов реализации SGM стала подсистема «Fragments-Symmetry-Similarity» (FSS), расширяющая функциональное наполнение АСНИ «Graph Model Workshop».

Подход к построению и анализу моделей системы SGM

Рассматриваемые программные средства используют принцип спектральной характеризации ГМС, дополненный учетом различных отношений между отдельными фрагментами, их классами или типами. ГМС t, изоморфно вкладываемая в исследуемую ГМС G, образует множество F(l)t помеченных фрагментов (ПФ) типа t. Каждый ПФ представляется каноническим изоморфным вложением t в G; g-модели самого верхнего уровня характеризуют расположение ПФ заданного набора типов T=(t1, …, tn) в топологии ГМС. Типы фрагментов, используемые при анализе ГМС, называют структурными дескрипторами (СД), а используемое множество СД – базисом СД. Подмодели SGM дополнительно характеризуют расположение классов эквивалентности ПФ (КЭПФ). Пределом разбиения КЭПФ служат орбиты t-группы, то есть группы, индуцированной группой автоморфизмов ГМС и действующей на ПФ типа t. Характеристики t-группы определяют симметрию расположения ПФ типа t в исследуемой ГМС.

Подпись:  
Рис. 2. Исходная ГМСНа основе предложенных моделей можно строить различные характеристические инварианты ГМС, как числовые, так и структурные. Построенные инварианты могут выражать метрические и спектральные свойства ГМС, симметрию расположения ПФ и разнообразие взаимного расположения ПФ разных типов в топологии ГМС. Наращивание базиса СД позволяет исследовать влияние расположения фрагментов различных типов на отношения эквивалентности и толерантности ГМС. При этом большинство подмоделей SGM являются двудольными графами и используют два базиса СД (левый и правый), которые могут различаться. Ребра моделей характеризуют отношения между ПФ (КЭПФ). В качестве отношений на помеченных фрагментах исследуемой ГМС рассматриваются отношения на основе операций пересечения и вложения ПФ. На рисунке 1 приведен пример визуализации bco-моде­ли, отражающей отношения между орбитами ПФ (цепей длины 0–3) и типами ПФ (цепей длины 1–3) для ГМС, изображенной на рисунке 2.

Основные положения анализа сходства ГМС с использованием системы SGM

Построение g-модели нетривиально (большинство задач, решаемых в процессе построения, принадлежат к классу NPC) и требует следующее:

-    определение базисов СД (Bl и Br) и, возможно, структурной сложности их элементов, если задано сохранение весов модели;

-    построение баз всех ПФ (F(l)ti) для всех СД, входящих в Bl и Br;

-    поиск орбит t-групп или КЭПФ для непустых F(l)ti, если задана свертка долей модели;

-    поиск общих частей ПФ (возможно, не всех ПФ для некоторых подмоделей);

-    вычисление коэффициентов сходства ПФ;

-    визуализация и/или сохранение модели.

Приведем возможную последовательность этапов исследования сходства ГМС с использованием g-моделей (рис. 3).

1.   Построение базы g-моделей заданного вида для базы исследуемых ГМС.

2.  

Формирование разнообразных отношений на g-моделях:

-    установление изоморфизма g-моделей;

-    установление изоморфного вложения g-мо­делей;

-    определение максимального общего фрагмента (МОФ) каждой пары g-моделей;

-    построение базы b(g)-моделей и определение МОФ b(g)-моделей – этот вариант более универсален и позволяет понизить вычислительную сложность с экспоненциальной (вариант с) до полиномиальной.

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

Границы применимости прямых методов анализа сходства моделей для ГМС общего вида:

·       для g-моделей – 45–100 вершин в зависимости от вида ГМС;

·       для b-моделей, построенных для g-модели (b(g)-моделей), – 250–400 вершин.

Для отдельных классов графов  граница применимости заметно повышается (до нескольких тысяч вершин для деревьев).

Подпись:  Рис. 3. Уровни исследований отношений эквивалентности и толерантности структур
Универсальность g-моделей и широта их возможной параметризации (включающей стратификацию и иерархию) впервые позволяет исследовать многообразие отношений эквивалентности и толерантности ГМС и обобщить большинство предложенных ранее моделей структурной сложности и сходства.

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

Программный комплекс FSS

Подпись:  
Рис. 4. Алгоритмическое наполнение FSSКомплекс FSS предназначен для автоматизации исследования широкого класса отношений эквивалентности и толерантности ГМС, строящихся на основе различных классов моделей системы SGM. Комплекс реализован в виде набора расширений АСНИ «Graph Model Workshop» и образует замкнутую подсистему, которая, однако, хорошо интегрирована с другими подсистемами АСНИ. Разработка была начата в 2003 году, сейчас доступна вторая версия FSS. Комплекс создан с использованием сред CodeGear RAD Studio (язык Delphi) и Microsoft Visual Studio (C++). Объем авторского исходного кода – более 2 Мб, число компилируемых строк исходного кода – более 620 000, объем машинного кода – 6,2 Мб. АСНИ «Graph Model Workshop» работает под управлением ОС Microsoft Windows 98-Vista.

Основные особенности комплекса:

-    концепция автоматизированного проведения вычислительных экспериментов (все этапы выполняются с использованием FSS в пакетном режиме для баз ГМС, а результаты могут накапливаться в БД);

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

-    ориентация на априори заданные базисы СД (декомпозиция ГМС используется именно для построения базисов);

-    единообразная обработка строковых и числовых весов вершин и ребер ГМС в любом количестве (что повышает качество исследования отношений эквивалентности и толерантности);

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

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

В процессе реализации FSS выявлено и уточнено пространство параметризации SGM, признанное полезным для теоретических исследований и практического применения. Реализованная часть пространства параметризации g-моделей на текущий момент содержит 12 основных и 11 дополнительных параметров [2]. Основные параметры задают собственно математическую модель (число долей, вид свертки вершин при анализе расположения КЭПФ, отношения на ПФ и т.п.), а дополнительные определяют визуализацию (диапазон координат, расположение вершин, графические образы вершин, ребер и весов) и способ хранения модели. Модели могут сохраняться как непосредственно в виде взвешенного графа, так и в виде набора таблиц во встроенной БД результатов экспериментов. Из-за сложности параметризации в FSS применяется концепция работы с профилями. Профиль g-модели – совокупность используемых при ее построении атрибутированных базисов СД, параметров стратификации, параметров визуализации и сохранения моделей. Пользователю предлагаются несколько стандартных профилей и редактор профилей, включающий редактор базисов СД, причем среди базисов также выделены стандартные как наиболее популярные у исследователей. Рисунок 4 иллюстрирует алгоритмическую насыщенность комплекса.

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

На основе FSS впервые появилась возможность построения программных средств интеллектуального анализа структурных данных нового поколения. Исследуемые отношения эквивалентности и толерантности на основе системы моделей SGM заметно отличаются от большинства рассматриваемых в настоящее время и могут дополнять используемые методы анализа сходства ГМС [3]. Предлагаемые программные средства достигли достаточного уровня эффективности для широкого научного и практического применения. Примером практического применения может служить реализация нечеткого поиска (в том числе уточняемого) в базах структурной информации.

Литература

1. Кохов В.А. Концептуальные и математические модели сложности графов. М.: Изд-во МЭИ, 2002.

2. Незнанов А.А., Кохов В.А. Программные средства для построения и исследования моделей структурной сложности и сходства // Одиннадцатая национ. конф. по искусствен. интел. с междунар. участ. КИИ-2008: тр. конф. М.: ЛЕНАНД, 2008. Т. 1. С. 216–224.

3. Cook D.J., Holder L.B. Mining Graph Data. Wiley-Interscience, 2006.


Permanent link:
http://swsys.ru/index.php?page=article&id=2624&lang=en
Print version
Full issue in PDF (6.26Mb)
Download the cover in PDF (1.28Мб)
The article was published in issue no. № 4, 2010

Perhaps, you might be interested in the following articles of similar topics: