§ 2.7. Отношения сходства и различия

Симметричное (2.19) и рефлексивное (2.13) НО сходства являются аналогом обычного отношения толерантности (сходства) [22]. НО сходства обычно задаются с помощью матриц сходства, связи между объектами, либо с помощью неориентированных взвешенных графов. Матрицы сходства, для которых условия (2.19) и (2.13) имеют естественную интерпретацию, могут быть получены как в результате измерения некоторого физического параметра, отражающего связи между объектами, так и в результате опроса экспертов, которые для каждой пары объектов из X указывают их степень сходства в некоторой. шкале сравнений L [48]. Градации этой шкалы могут быть составлены из фраз русского языка, отражающих силу сходства между объектами и линейно упорядоченных между собой. Например, такая шкала может состоять из фраз типа: «очень сильное сходство», «сильное сходство», «сходство средней силы», «слабое сходство», «очень слабое сходство» и т. п.

Условие транзитивности для НО сходства обычно формулируют в виде

которое при определении операции композиции с помощью (2.8) приводит к условию транзитивности (2.24):

Транзитивность (2.35) обозначается па рис. 2.2, а как (Л)" транзитивность. Другие типы транзитивности получаются заменой операции Л в (2.35) на операцию уміюжения • или операцию Д. В первом случае предполагается, что L = [0, 1], и условие транзитивности

обозначается как (•)-транзитивность. Во втором случае в качестве L можно взять интервал вещественных чисел [О, М\ и операция Д в L будет определяться следующим образом:

Тогда (Л)-транзитивность определяется как

Свойства (•)-транзитивности обсуждаются в [52, 37, .38], а (Д)'транзитивность отношений сходства рассматривается в [26] в задачах кластерного анализа.

Наиболее интересными свойствами обладает (Л)-транзитивное отношение сходства S, которое является обобщением обычного отношения эквивалентности. Это отношение называется нечетким отношением эквивалентности или отношением подобия. Из теоремы 2.1 следует, что любоіі а-уровень НО эквивалентности является обычным отношением эквивалентности и, следовательно, определяет разбиение множества объектов X на непересекающиеся классы эквивалентности. Из вложенности а-уров- нен нечеткого отношения следует и вложенность разбиении множества X, соответствующих различным а-уровням, причем с уменьшением а происходит укрупнение классов эквивалентности «-уровней. Таким образом, НО эквивалентности задает иерархическую совокупность разбиений множества X на непере- секающиеся классы эквивалентности. Нетрудно установить связь, существующую между НО эквивалентности и иерархическими кластер-процедурами [52].

НО эквивалентности, в отличие от произвольного отношения сходства, определяет совокупность разбиений множества X на классы эквивалентности, благодаря тому, что условие транзитивности (2.35) накладывает довольно сильные ограничения на возможные значения степеней принадлежности S {х, у). Например, в случае, когда L является множеством вещественных чисел, отношение сходства S транзитивно тогда и только тогдз, когда для любых X, у, zeX из трех чисел S{x, у), S{y, z), S{z, х)

по крайней мере, два числа равны друг другу и по величине не превышают третьего.

Таким образом, отношение эквивалентности обладает многими полезными свойствами из-за своего довольно специфического вида. В практических задачах из исходного нетранзитивного отношения сходства S можно получить транзитивное отношение, применяя к S операцию транзитивного замыкания S. Для конечного X получим S = S"“‘, где п — число элементов множества X.

На рис. 2.3 приводятся примеры НО сходства, его транзитивного замыкания и декомпозиция полученного отношения на а-уровни.

Отношением различия D называется симметричное (2.19) и антирефлексивное (2.16) нечеткое отношение. Отношение различия D двойственно отношению сходства. В случае, когда L == [О, М\ эти отношения могут быть получены друг из друга

с помощью соотношения:

В случае, когда L = [О, 1], то (2.39) принимает вид:

что можно переписать в алгебраической форме следующим образом:

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

Ультраметрикой называется отношение различия, удовлетворяющее ультраметрическому неравенству:

Ясно, что условие (2.42) двойственно условию транзитивности (2.35). На рис. 2.2, а это условие транзитивности обозначено как (V)-транзитивность, а класс отношениіі различия, удовлетворяющих условию (2.42) обозначен как D^. В случае, когда L является множеством вещественных чисел, ультраметрика и НО эквивалентности могут быть получены друг из друга с помощью соотношения (2.39). Эта связь между НО эквивалентности и ультраметрикой была установлена в самых первых работах по НО [52, 48]. В [37, 32] для условия транзитивности (2.42) двойственным образом вводятся понятия транзитивного замыкания и т. п.

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

Метрикой называется отношение различия, удовлетворяющее неравенству треугольника:

которое обозначено на рис. 2.2, а как (+)-транзитивность D,. От метрики требуют обычно вынолненігя также условия сильной антирефлексивности (2.16), (2.18). Метрика, удовлетворяющая лишь простому условию антирефлексивности (2.16), называется обычно псевдометрикой. Двойственным но отноінению к метрике является (А)-транзитивное отношение сходства (2.38).

Двойственное условию (•)-транзитивности (2.36) условие (Ф)-транзитивности записывается как

Это условие транзитивности может рассматриваться для отношений различия, определенных при L = [О, 1].

Таким образом, отношения сходства и метрики оказываются в рамках теории НО тесно связанными между собой понятиями. Это позволяет применять методы, основанные па свойствах НО, к решению задач, в которых используется понятие метрики и наоборот.