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

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

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

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

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

обозначается как -транзитивность. Во втором случае в качестве можно взять интервал вещественных чисел и операция А в будет определяться следующим образом:

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

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

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

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

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

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

Рис. 2.3. Декомпозиция нечеткого отношения на a-уровни: a — исходное отношение сходства S; б — транзитивное замыкание S; в — классы эквивалентности

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

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

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

В случае, когда то (2.39) принимает вид:

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

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

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

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

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

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

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

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

Это условие транзитивности может рассматриваться для отношений различия, определенных при

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