Граф-модели для анализа сходства структур систем на основе обобщенного подструктурного подхода

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

Государственный Университет-Высшая школа экономики

ГРАФ-МОДЕЛИ ДЛЯ АНАЛИЗА СХОДСТВА СТРУКТУР СИСТЕМ НА ОСНОВЕ ОБОБЩЕННОГО ПОДСТРУКТУРНОГО ПОДХОДА

В.А. Кохов

В.В. Кохов

Москва

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

Понятие «структурное сходство» систем является ключевым в интеллектуальном анализе данных, реализации правдоподобных рассуждений, обработке высказываний на естественных языках и других областях искусственного интеллекта. Сходство является ключевой операцией при поисках в базах структурных данных (семантический web-поиск электронных документов в Интернете) и знаний, представленных семантическими сетями. Это определяет актуальность и значимость разработки моделей, методов и программных средств для определения сходства структурированных нечисловых объектов (графов, орграфов, мультиграфов, семантических сетей и пр.) [Финн, 1991; Кузнецов, 1996].

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

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

Подструктурный подход к анализу сходства орграфов
и его недостатки

Пусть задан орграф G=(V,E) с числом вершин p=V и дуг q=E. Порожденный подграф орграфа получается при удалении вершин и инцидентных к ним дуг. Если из орграфа удалять дуги, то в результате получаем фрагмент орграфа. Два орграфа G1=(V1,E1) и G2=(V2,E2) изоморфны (G1G2), если

:(V1V2)(vi,vjV1 [(vi,vj)E1 ((vi),(vj))E2]),

где (vi),(vj)V2.

Множество всех изоморфизмов орграфа на себя образует группу Aut(G). Орграф G1=(V1,E1) изоморфно вкладывается в орграф G2=(V2,E2) как порожденный подграф G1SG2 (фрагмент, G1G2), если в орграфе G2 есть порожденный подграф (фрагмент) G*=(V*,E*), для которого справедливо отношение G*G1. Под максимальным общим фрагментом (MCF) (порожденным подграфом, MCS) орграфов G1,G2 понимаем орграф G*, для которого справедливы условия: (1) G*G1 и G*G2 (G*SG1 и G*SG2); (2) не существует большего G* по числу дуг (вершин) фрагмента (подграфа) в орграфе G1, для которого выполняется условие (1).

В орграфе следует различать три вида порожденных подграфов: слабо связный; односторонне связный; сильно связный. Ниже будем рассматривать в качестве порожденных подграфов (фрагментов) орграфов слабо связные порожденные подграфы. Все не определенные ниже понятия можно найти в книге [Нечепуренко, 1990].

В основе ПП лежит использование максимального общего фрагмента (MCF) двух орграфов [Bunke et al., 1998]. Величина сходства зависит от размера (числа вершин и/или дуг) MCF относительно размеров сравниваемых орграфов. Обычно меры расстояния (D) и коэффициенты сходства (MSI) между орграфами G1 и G2, используемые в качестве результатов, вычисляются по формулам [Bunke et al., 1998]:

D(G1,G2)=F(G1) + F(G2) 2 (MCF(G1,G2));

MSI(G1,G2)=F(MCF(G1,G2)2/(F(G1)F(G2)),

где F характеризует размер орграфа.

Две основные постановки задачи следуют из использования порождённого подграфа (MCS и D1, MCI1) или фрагмента (MCF и D2, MSI2) орграфа. В первом случае F(G) = p(G) (число вершин), во втором - F(G) = p(G)+q(G). Под результатом решения задачи определения попарного различения (сходства) набора их K орграфов будем понимать полный граф с K вершинами, каждое ребро которого {vi,vj} взвешено значением расстояния D(Gi,Gj ) (индекса сходства MSI (Gi,Gj)). Чем шире разнообразие значений расстояний D(Gi,Gj ) (MSI(Gi,Gj)), тем больше возможностей для решения задачи кластеризации анализируемых орграфов. Ниже в качестве одного из главных критериев развития ПП выберем возможность расширения границ кластеризации (сходства).

Определение 1. Чувствительностью решения задачи различения пар орграфов в множестве из N орграфов по инварианту IN относительно MCF при построении графа попарного различения орграфов называется отношение вида (IN(D), MCF)=KL(IN(D))/(N(N1)/2), где KL(IN(D)) обозначает число классов IN-эквивалентности пар орграфов по значениям расстояния D.

Определение 2. Чувствительностью решения задачи определения сходства пар орграфов в множестве из N орграфов по инварианту IN относительно MCF при построении графа попарного сходства орграфов называется отношение вида (IN(MSI), MCF)=KL(IN(MSI))/(N(N1)/2), где KL(IN(MSI)) обозначает число классов IN-эквивалентности пар орграфов по значениям индекса сходства MSI.

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

На основе анализа ПП и результатов объемных вычислительных экспериментов (проанализировано сходство более 21 000 000 орграфов) выделим его недостатки: (1) NP-полнота задачи определения MCF (MCS) двух орграфов [Гэри, 1982]; (2) жесткая детерминированность - полученное значение метрики или коэффициента сходства нельзя далее уточнять; (3) малая «чувствительность» (значение (IN(D), MCS)) при определении кластеров орграфов с одинаковым числом вершин; (4) подход не учитывает в явном виде расположение фрагментов в структуре орграфа.

Несмотря на выделенные недостатки, ПП нашел широкое применение в химической и биологической информатике [Raymond, 2002]. Ниже приводится метод построения трансграфа путей для орграфа G (Сgp(G)), позволивший устранить перечисленные выше (2-4) недостатки ПП. Можно устранить и основной недостаток ПП, если при некоторой потере точности результатов, использовать базовые модели для характеризации орграфов и трансграфов [Кохов, 2002]. Трансграфы путей являются наиболее актуальными для исследования сходства орграфами, что обосновано следующими причинами: (1) любые орграфы включают пути; (2) пути отражают как локальные (пути малой длины), так и глобальные (пути большой длины) свойства орграфов; (3) пути наиболее легко конструктивно перечислимые фрагменты в сравнении с другими фрагментами орграфа; (4) пути относятся к классу монотонно наращиваемых по сложности структурных базисов для характеризации орграфов; (5) в базисе путей естественным образом задается строгий порядок по длине пути.

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

Алгоритм построения цветных трансграфов путей (Сgp(G)) для G=(V,E) включает 7 шагов: (1) исходный орграф G является Сgp(G) для путей длины 0; (2) для G cтроим 1-гомеоморфное расширение и получим Сgp(G) для путей длины 1. Новые вершины viVP1 отображают пути длины 1 в G. Ориентация дуг определена в направлении дуги исходного орграфа; (3) каждую пару новых вершин vi,vj соединим дугой (vi,vj), если ГviГvj ; (4) объединение путей, соответствующих новым вершинам, порождает путь на единицу большей длины, чем длины объединяемых путей; (5) строим 1-гомеоморфное расширение новых дуг, порождая новые вершины, как пути длины 2 исходного орграфа G; (6) повторяем выполнение п.3 и п.4 до тех пор, пока порождаются новые дуги, соответствующие путям исходного орграфа G; (7) вершинам построенного орграфа приписываем цвет, номер которого равен длине пути. В результате, построена Сgp-модель первого или второго вида.

Если в Сgp-модели сохранить дуги исходного G=(V,E), то получим Сgp+-модель. Аналогично строятся цветные трансграфы путей-подграфов (Сgps-модели и Сgps+-модели). Если цвета вершин в Сgp(G) (Сgp+(G)) не учитывать, то такой орграф будем называть трансграфом цепей (трансграфом цепей плюс) и обозначать через gp(G) (gp+(G)).

Обозначим через gp+(G/pj) (gp+(G/p0j)) трансграф путей, построенный для всех путей длины j (от 0 до длины j включительно) в орграфе G. На рис. 1 приведены примеры трансграфов путей для G1,G2,G3.

Рис. 1. Примеры трансграфов путей для G1,G2,G3

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

Утверждение 1. Группа автоморфизмов вершин Сgp+(G) для орграфа G изоморфна группе автоморфизмов вершин орграфа G.

Утверждение 2. Группа автоморфизмов вершин gp+(G) для орграфа G изоморфна группе автоморфизмов вершин орграфа G.

Утверждение 3. Группа автоморфизмов вершин цветного трансграфа путей cgp(G) для орграфа G не изоморфна группе автоморфизмов вершин орграфа G. стратификация граф подструктурный

Утверждение 4. Количество путей N(Tp) в ордереве Tp на p вершинах равно числу вершин трансграфа путей gp+(Tp) и не превышает величины p(p+1)/2.

1. Обобщенный подструктурный подход к анализу сходства орграфов

Использование, расширяемой по длинам путей системы страт gp+(G):

<gp(G/p0), gp+(G/p01), gp+(G/p02),…, gp+(G/p0j),…, gp+(G/p0(p-1))>

приводит к новым аспектам исследования сходства по ПП с учетом расположения путей тех длин, которые интересуют исследователя. Так как анализируемые орграфы являются gp+-моделями для цепей длины 0, то ПП является частным случаем обобщенного подструктурного подхода. Использование системы страт gp+(G) при построении gp+-моделей орграфов позволяет уточнять результаты анализа их сходства. На рис. 2 (рис. 3) приведены графики изменения значений расстояний D1 (индексов сходства MSI1) для пар орграфов G1G3 при последовательном построении gp+-моделей для длин путей от 0 до 4.

Таким образом, ОПП впервые позволяет анализировать тенденции изменения значений расстояний (индексов сходства) при наращивании длин путей и выявлять границу по длине пути для установления максимального значения чувствительности (IN(D1)) ((IN(MSI1))).

Использование предложенных трансграфов путей позволяет вводить новые характеристики для исследования сходства орграфов относительно используемых систем страт трансграфов:

где dср среднее значение D, ср индекс среднего значения MSI для пар орграфов.

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

Алгоритм построения по графу G=(V,E) его трансграфа цепей (Сgс(G)) включает 7 шагов и аналогичен алгоритму построения трансграфов путей. Отличие заключено в отсутствии учета ориентации, так как вместо дуг анализируются цепи графа G. На рис. 4 приведены три графа, а на рис. 5 их цветные трансграфы цепей Cgc(G/p0-4). На рис. 5 вершины Cgc(G), расположенные на одном и том же уровне, имеют одинаковый цвет.

Рис. 4. Графы G1 , G2 , G3

В табл. 1 приведены результаты определения значений D1 и MSI1 для G1G3 по ПП (значения выше главной диагонали) и по ОПП (значения ниже главной диагонали). Сравнивая эти результаты, видим, что при длине цепей равной 3 имеем Максимальное значение чувствительности различения б(IN(D1), MCS) получено при использовании gc(G/p0-3).

Рис. 5. Цветные трансграфы цепей Cgc(G/p0-4)

Табл. 1.

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

Утверждение 5. Группа автоморфизмов вершин цветного трансграфа цепей Сgc(G) для графа G изоморфна группе автоморфизмов вершин графа G, то есть Aut(G)Aut(Сgc+(G)).

Утверждение 6. Группа автоморфизмов вершин трансграфа цепей gc(G) для графа G изоморфна группе автоморфизмов вершин графа G, то есть Aut(G)Aut(gc+(G)). Единственное исключение составляет граф P3.

Заметим, что деревья представляют наибольший интерес при построении Сgc-моделей, так как число цепей в них растет полиномиально и вычислительная сложность алгоритма построения Сgc-моделей имеет полиномиальный рост от числа вершин.

Пример анализа сходства графов по ПП и ОПП

В табл. 2 (выше главной диагонали) приведены результаты определения D1 по ПП и (dсрЧ10) (ниже главной диагонали) по ОПП для всех деревьев на 7 вершинах. При значении чувствительности (IN(D1), MCS) различения значений по D1 для ПП, равной 0,054 (3 класса пар деревьев), мы получили значение 0,545 (30 классов пар деревьев) для ОПП. Заметим, что результаты ПП не позволили провести кластеризацию анализируемых деревьев, ввиду низкой чувствительности по (IN(D1), MCS). На основе ОПП кластеризацию провести удалось.

Табл. 2.

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

Рис. 6. Результаты кластеризации деревьев на основе ОПП

При кластеризации последовательно удалялись ребра, значения веса (расстояния) которых, превышали соответственно следующие границы 96; 84; 80; 72; 64; 60.

Следует выделить, что с целью существенного повышения эффективности применения обобщенного подструктурного подхода к анализу сходства, но с некоторой потерей точности, необходимо заменить экспоненциальный по вычислительной сложности алгоритм определения максимального общего подграфа для cgp-моделей на эффективный (полиномиальный по вычислительной сложности) алгоритм определения максимального изоморфного пересечения b(gs)-моделей [Кохов, 2002].

Заключение

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

Обобщенный подструктурный подход к анализу сходства графовых моделей систем программно реализован в АСНИ «GMW» и используется в учебном процессе МЭИ (ТУ), ГУ-ВШЭ, научных исследованиях ВИНИТИ и ИВМиМГ СО РАН (г. Новосибирск).

Список литературы

1. [Гэри, 1982] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., Мир, 1982.

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

3. [Кохов, 2008] Кохов В.А. Граф-модели для анализа сходства структур систем на основе их сложности // Труды 11-ой национальная конференция по искусственному интеллекту с международным участием. КИИ-2008. В 3-х т. Том 3. - М.: Физматлит, 2008.

4. [Кузнецов и др., 1996] Кузнецов С.О.,Финн В.К. О модели обучения и классификации, основанной на операции сходства. //Обозрение Прикладной и Промышленной Математики 3, №1, 1996.

5. [Нечепуренко, 1990] Нечепуренко М.И., Попков В.К., Кохов В.А. и др. Алгоритмы и программы решения задач на графах и сетях. - Новосибирск: Наука, 1990.

6. [Финн, 1991] Финн В.К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ. // Итоги науки и техники, сер. «Информатика», Т.15. 1991.

7. [Bunke and oth, 1998] Bunke H. and Shearer K. A graph distance metric based on maximal common subgraph, Pattern Recognition Letters, Vol. 19, №. 3-4, 1998.

8. [Raymond, 2002] Raymond J. W., Gardiner E. J., Willett P. RASCAL: Calculation of graph similarity using maximum common edge subgraphs. //Computer Journal, vol. 45, №6, 2002.

Размещено на Allbest.ru