ДСМ-метод, Детальна інформація

T

V

X

v

x

¬

®

°

\x00B4

¶

Oe

O

Поняття схожості, що використовується в ДСМ-методі, представляє собою один з можливих способів синтезу кількох напрямків: об’єкти структуровані (тобто на них задано відношення “бути більш загальним”), а їх схожість задається через операцію з визначеними алгебраїчними властивостями, що індуцирують відношення толерантності (тобто рефлексивне та симетричне відношення) на об’єктах. Та навпаки, відношення толерантності (схожості) вільного (але фіксованого) числа об’єктів може бути взаємно-однозначно співставлено деякій операції, яка може бути операцією схожості на об’єктах в ДСМ-методі. Більш формально, нехай S – множина об’єктів, яка представляє деяку предметну область. Операція ? на парах об’єктів із S задає нижню напіврешітку, якщо для будь-яких об’єктів si, sj, sk з S мають місце співвідношення (1)–(4)

(1) si?si = si,

(2) si?sj = sj?si,

(3) (si?sj) ?sk = si?(sj?sk),

(4) si?s0 = s0, для деякого s0 з S, який називається порожнім об’єктом.

Поняття “порожнього об’єкта” може бути розширене до “множини порожніх об’єктів”. Такою може бути множина об’єктів із S, що включає s0 та замкнуте відносно операції ?. Множина порожніх об’єктів може інтерпретуватися як “несуттєва”, “неінформативна” схожість. Такою, наприклад, можна рахувати схожість графів хімічних молекул, максимальний загальний підграф яких є одна ланка вуглеводневого ланцюжка: —С—C—.

Напіврешіточна операція ? задає на множині S відношення поглинання L наступним чином: для si та sj з S, si + sj тоді і тільки тоді, коли sі ? sj = si.

Означення 1.

Операцію, що задовольняє властивостям (1)–(4), назвемо операцією схожості.

Означення 2.

Нехай – нижня напіврешітка, X ? s0 називається локальною схожістю об’єктів s1, …, sk (k = 2), якщо X = s1?…?sk.

Можна записати s1?…?sk замість s1?(¬s2?(…?sk)…), використовуючи властивості (1)–(3) операції схожості ?. Загалом, при визначенні операції схожості можна обійтися без властивості асоціативності (3), що дозволяє однозначно задавати схожість n об’єктів через попарні схожості. В такому випадку, однак, довелося б вводити нескінчене сімейство операцій схожості ?2, ?3, …, кожне з яких відноситься до певної кількості об’єктів. При цьому результат операції міг би залежати від порядку операндів.

Означення 3.

Нехай – нижня напіврешітка. Пара , де s1,…, sk(S, називається глобальною схожістю, якщо Х = s1?…?sk, тобто Х є локальна властивість об’єктів s1,…, sk та для будь-якого s(S\{s1,…, sk} має місце X ? s ? X. Так як k заздалегідь невідоме, то глобальна схожість не є відношенням, на відміну від локальної схожості. Помітимо, що відношення

def

R (x, y) ( (S \ {s0}) ( (S \ {s0}), (x, y) ( R = x ? y ? s0

Є відношенням толерантності, тобто воно рефлексивне ((х, х) ( R) та симетричне ((x, y) ( R ? (y, x) ( R). Тим самим операція ? задає бінарне відношення схожості, але не лише його. В силу асоціативності операції ? можна ввести наступне k-арне відношення Rk для довільного k. Rk ( (S \ {s0}) ( …( (S \ {s0}); (x1,… xk) ( Rk, якщо x1? … ?xk ? s0. Тоді відношення буде мати наступні властивості:

(x(S \ {s0}, (x,…x)(Rk (Re)