известия ран. теория и системы управления, 2012, № 5, с. 82-101
= ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ =
удк 519.17:004.9
ДВА ПОДХОДА К ОПРЕДЕЛЕНИЮ СХОДСТВА ОРГРАФОВ
© 2012 г. В. А. Кохов
Москва, НИУ ВШЭ Поступила в редакцию 26.12.11 г., после доработки 16.01.12 г.
Рассмотрен подход к решению задачи определения сходства с применением максимального общего фрагмента двух графов. Выделены его основные недостатки. Предложены два новых подхода к решению задачи определения сходства орграфов: обобщенный подструктурно-метрический и использующий стратифицированную систему матричных моделей сложности орграфа. Сформулированы новые характеристики для исследования сходства орграфов. Дана формализованная постановка оригинальной задачи по вычислению сходства расположения фрагментов в орграфе с учетом количественных и качественных характеристик фрагментов орграфа. Создана методология, включающая две системы методов решения задачи. Первая система методов учитывает точное, а вторая — приближенное расположение фрагментов в орграфе. Выделен новый класс задач — вычисление сходства орграфов с учетом сходства расположения фрагментов указанного типа. Приведен пример решения задачи поиска семантических сетей, наиболее сходных с сетью-шаблоном.
Введение. Сходство структур систем является ключевым понятием в реализации правдоподобных рассуждений, структурном распознавании образов, интеллектуальном анализе данных, обработке высказываний на естественных языках и других областях искусственного интеллекта. Сходство — основная операция при поисках в базах структурных данных (семантический wеЬ-поиск документов) и знаний, представленных семантическими сетями. Это определяет актуальность и значимость разработки моделей, методов и программных средств для вычисления меры сходства структурированных нечисловых объектов (графов, сетей, орграфов и др.) [1, 2]. Одним из подходов к количественному определению сходства объектов выступает подструктурный метрический подход (ПМ-подход) [3, 4]. Он нашел применение в следующих системах: 1) компьютерного зрения и робототехники [5]; 2) распознавания видеоизображений [6]; 3) химической и биоинформатики [7—9]; 4) структурной информатики [10]; 5) семантического поиска электронных текстовых документов [11].
Концепция ПМ-подхода базируется на использовании максимальных общих фрагментов двух графов, вычислении подграфовой метрики (расстояния между графами) или коэффициента сходства. Ниже предложены два новых подхода к решению задачи вычисления сходства орграфов. Первый подход (трансграфовый) основан на построении трансграфов. Трансграфы являются надграфами орграфов и множество их вершин взаимнооднозначно отображает множество фрагментов орграфа с сохранением симметрии их расположения. Далее используется концепция подструктурного метрического подхода в применении к трансграфам с получением более точного результата сходства. Во втором подходе дана оригинальная система моделей сложности орграфа. На основе модели выполняется иерархический анализ сходства орграфов с учетом: 1) количественных и качественных характеристик фрагментов орграфов; 2) расположения фрагментов в орграфах; 3) сходства расположения фрагментов в орграфах. Переход с одного уровня анализа сходства на другой приводит к уточнению результатов сходства.
При характеризации трансграфов орграфов матричными моделями сложности имеем возможность применять второй подход и эффективно вычислять сходство по первому подходу с некоторой потерей точности получаемых результатов. С другой стороны, с помощью операции пересечения матриц достроек фрагментов, на основе которых строится матрица сложности, возможно эффективно использовать концепцию ПМ-подхода в методах второго подхода с некоторой потерей точности получаемых результатов. Оба подхода вместе образуют методологию решения задач определения сходства орграфов с учетом как точного (первый подход), так и приближенного (второй подход) расположения и сходства расположения фрагментов. В рамках методологии созданы алгоритмы для решения трех новых классов задач вычисления сходства: 1) сходство расположения фрагментов в орграфе; 2) сходство орграфов с учетом расположения фрагментов; 3) сходство орграфов с учетом сходства расположения фрагментов [10].
1. Основные определения. Пусть задан орграф О = (У, Е) с числом вершинр = \У\ и дуг q = |Е|. Порожденный подграф орграфа получается при удалении одной или нескольких вершин и инцидентных к ним дуг. Если из орграфа удалять одну или несколько дуг, то в результате построим подграф (ниже фрагмент) орграфа. Два орграфа О1 = (Уь Е1) и О2 = (У2, Е2) изоморфны (О1 ~ О2), если
3Ф: (У о У2) & е У! [(V^,) е Ех о (<р(^),ф(^)) е Е2]),
где ф(^), ф(у^) е У2. Орграф О1 = (Уъ Е{) изоморфно вкладывается в орграф О2 = (У2, Е2) как порожденный подграф О1 с 5О2 (фрагмент, О1 с О2), если в орграфе О2 есть порожденный подграф (фрагмент) О* = (У*, Е*), для которого выполняется условие О* ~ Ох. Под максимальным общим фрагментом (МСЕ) (порожденным подграфом, МС&) двух орграфов О1, О2 понимаем орграф О*, для которого справедливы условия: а) О* с О1 и О* с О2 (О* с 5О1 и О* с SО2); Ь) не существует большего О* по числу дуг (вершин) фрагмента (подграфа) в орграфе О1, для которого выполняется условие а).
Множество всех изоморфизмов орграфа на себя образует группу по умножению подстановок ф и обозначается через Ли'(О), порядок группы — через \Ли'(О) |. Под числом канонических изоморфных вложений О* в О будем понимать величину, определяемую следующим образом: w(О*, О) = = Ж(О*,С)/|АШ(0*), где ЩО*, О) — число всех изоморфных вложений О* в О. Пусть g — изоморфизм орграфа на себя, т.е. автоморфизм орграфа. Орбитой вершины V е У называется подмножество ©( Аи'( О), V) вершин У орграфа О, которые могут быть отображены на вершину V:
ЩАШ(О),^) = {V* е У: е АШ(О)) & = V)}.
Орбиты вершин орграфа О определяют разбиение множества вершин орграфа на классы их эквивалентного расположения. Пусть построены группыЛи'(О{), Ли'(О2) и g¡,gk е АШ(Ог). Орграфы О1 и О2 имеют изоморфные группы (ЛШ(ОХ) ~ Ли'(О2)), если выполняется следующее условие:
ЗН: Аи'(О1) о Аи'О) Уgi,gk е АШ(О1)[к^1 * gk) = Н^д * )], где Н^{),Н^к) е АШО).
Абстрактный тип ' — произвольный орграф, определенный с точностью до изоморфизма. Группу его вершинных автоморфизмов обозначим через Ли'('), множество всех канонических
изоморфных вложений абстрактного типа 'в орграф О — через Г'(О) = {//,/2,..., /'т}, \Е'(О)\ — количество фрагментов типа ', а п'(О) — число типов фрагментов в орграфе О. Если на множестве вершин типа фрагмента ' и орграфа О задана нумерация, то фрагмент /' орграфа О может быть
представлен помеченными фрагментами /", когда каждой вершине типа фрагмента ' сопоставляется номер вершины орграфа О, которой она соответствует при вложении. Число помеченных фрагментов, представляющих один и тот же фрагмент О, равно |Аи'(')|.
ПустьЛи''(О) является индуцированным представлением группыЛи'(О) и определяет симметрию расположения фрагментов типа ' в О. Под t-автоморфизмом орграфа О будем понимать подстановку £ на множестве г"(О) помеченных фрагментов типа ' орграфа О (или канонических изоморфных вложений), индуцированную некоторым вершинным автоморфизмом g орграфа О.
В процессе индуцирования помеченный фрагмент /' е Г1'(О), заданный каноническим изоморфным вложением (V!, v2, ..., V,) орграфа О, переходит в помеченный фрагмент /11 е Г1'(О), канонический вид которого получен канонизацией вложения (иь и2, ., ип), где ui=g( V ,), /= 1,..., п, п - число вершин фрагмента типа '. Группой '-автоморфизмов О (Ли' '(О) или '-группой) будет группа подстановок, носителем которой является все множество '-автоморфизмов для данного ', а групповой операцией — операция произведения подстановок. Тот факт, что множество '-автоморфизмов образует группу, непосредственно следует из свойствЛи'(О). Степень '-группы \Р'(О)\ равна числу канонических изоморфных вложений абстрактного типа ' в орграф О, а порядок меньше или равен порядку Ли'(О). Последнее обосновано тем, что два различных нетождественных вершинных автоморфизма могут индуцировать один и тот же '-автоморфизм. Все понятия, связанные с анализом Ли''(О), определяются аналогично понятиям, связанным с анализом Ли'(О) (например, орбиты '-группы). Орбиты '-группы точно характеризуют симметрию расположения фрагментов типа ' в орграфе О.
Основным инструментом при решении задачи сходства-различия орграфов (расположения фрагментов в орграфе) по второму подходу является использование инвариантов орграфа (инвариантов, характеризующих расположение фрагментов в О). Обозначим множество всех орграфов через Ш. Пусть Я — отношение "быть изоморфными" орграфами, а Q — непустое множество с отношением эквивалентности т (множество чисел, векторов, матриц, орграфов и т.д.). Функция Ш, заданная на множестве Ш и принимающая значения в Q, называется инвариантом орграфа О, если справедливо условие
е Ш [в,(Я)о] ^ т(о1)(т)т(в])].
Графы О, О] называются /^-эквивалентными (в(Ш)в;), если Шв)(т)Ш(в;-), инвариант Ш — полным инвариантом орграфа, если выполняется условие
VG,Gj е Ш [IN(Gl)(x)IN(GJ) ^ Gl(R)GJ
Под чувствительностью инварианта орграфа О в множестве Т с Ш будем понимать отношение вида а(Ш, К) = | Т(Ш)|/| Т(К)|, где |Т(/¥)| — число классов /^-эквивалентности орграфов, а |Т(Я)| — число неизоморфных орграфов в множестве Т. Чувствительность инварианта определяет точность решения задачи различения орграфов в множестве Т. Границей вырождаемости инварианта Ш в множестве Т с Ш называется наименьшее число вершин в О е Т, при котором инвариант Ш становится неполным. Инвариантом, характеризующим расположение фрагмента /" типа t, называется функция т(/1'), заданная на множестве Г"(в), принимающая значения в Q и удовлетворяющая условию V/,",/1}- е [/■"(£,'')/]■ ^ т()(т)т(/'/)]), где £/ — отношение эквивалентности "принадлежать одной и той же орбите ^группы". Аналогично понятиям, связанным с инвариантом орграфа, вводятся понятия для инварианта т(/"). Все неопределяемые ниже понятия можно найти в [12].
2. Обобщенный ПМ-подход к определению сходства ор
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.