27. Некоторые свойства отношений подобия и сходства

Теорема декомпозиции для отношения подобия. Пусть  - отношение подобия в . Тогда  можно разложить так:

, ,                   (27.1)

при

,

где  - отношения эквивалентности в смысле обычной теории множеств и  обозначает, что все элементы обычного отношения  умножаются на .

Доказательство. Во-первых, , откуда следует, что  при ; следовательно,  обладает свойством рефлексивности.

Во-вторых, положив ,  получим, что  и в силу симметрии . Следовательно,  обладает свойством симметрии.

В-третьих, для всех  предположим, что  и ; тогда  и ; следовательно, по транзитивности  и  транзитивно.

Поскольку  рефлексивно, симметрично и транзитивно, то  - отношение эквивалентности.

Справедлива и обратная теорема.

Обратная теорема. Если  не пусто,  и

,                       (27.2)

тогда  - рефлексивное нечеткое отношение.

С другой стороны, обращаясь к (13.31), можно записать

.                      (27.3)

Очевидно, что из симметричности каждого  вытекает симметрия .

Наконец, пусть

 и .                    (27.4)

Тогда

 и .                   (27.5)

Как следствие получаем

,                       (27.6)

поскольку  транзитивно.

Следовательно,

                     (27.7)

и

,                     (27.8)

что вместе с (27.2) и (27.3) доказывает транзитивность .

Эта обратная теорема позволяет синтезировать отношения подобия, в то время как прямая теорема позволяет проводить анализ.

Интересное замечание. Как следует из этой теоремы, обычное отношение, ближайшее к отношению подобия, есть отношение эквивалентности. Это становится очевидным, если рассмотреть, что представляет собой , когда .

Примеры. Посмотрим, как проводится анализ отношения, представленного на рис. 20.1. Декомпозиция этого отношения показана на рис. 27.1.

Рис. 27.1.

Рассмотрим пример синтеза. Пусть четыре отношения эквивалентности последовательно содержат друг друга (рис. 27.2).

Рис. 27.2.

Тогда имеем

.                      (27.9)

Результат показан на рис. 27.3.

Рис. 27.3.

Другой пример дан на рис. 27.4, где предполагается, что  и  при .

Рис. 27.4.

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

Пример 1. На рис. 27.5 показано отношение различия. На рис. 27.6 представлены транзитивные графы, соответствующие разным расстояниям.

Рис. 27.5.

Рис. 27.6.

Пример 2 (рис. 27.7 и 27.8). Этот пример - на транзитивное замыкание (рис. 26.2) отношения сходства (рис. 26.1). Полученное здесь разложение мы сравним с тем, которое получится в следующем примере (рис. 27.9 и 27.10).

Рис. 27.7.

Рис. 27.8.

Пример 3 (рис. 27.9 и 27.10). (Мах-)-транзитивное замыкание отношения сходства на рис. 26.1 было представлено на рис. 26.6. Для этого на рис. 26.7 выписали матрицу (max-sum)-расстояний. В этом примере при декомпозиции на обычные графы расстояний появятся нетранзитивные графы. Использование (max-)-транзитивного замыкания в отношении сходства менее удобно по сравнению с использованием (mах-min) транзитивного замыкания.

Рис. 27.9.

Рис. 27.10.

Декомпозиционное дерево. Читатель, внимательно изучивший рис. 27.1, заметит, что по мере того, как  последовательно принимает значения 0,7; 0,8; 0,9 и 1, разбиение  на классы эквивалентности включает все больше и больше частей. Это разложение было проведено по древовидной схеме (рис. 27.11). Такая схема называется декомпозиционным деревом.

Рис. 27.11.

Другой пример разложения для данных рис. 27.4 приведен на рис. 27.12.

Рис. 27.12.

Можно проверить, что два элемента  и , принадлежащие , должны принадлежать одному и тому же классу -уровня, если и только если

.                       (27.10)

Это декомпозиционное дерево хорошо отражает структуру отношения подобия или, если хотите, группировки элементов, построенные с использованием их транзитивных расстояний от других элементов.

Деревья можно представлять различными способами. Используя лингвистические обозначения, дерево на рис. 27.11 можно записать в следующем виде:

.                      (27.11)

Такое использование круглых скобок не слишком удобно.

Можно также использовать польское обозначение, собирая вершины в «кучи». Дерево на рис. 27.11 будет тогда записано в виде такой последовательности:

Выбор транзитивно ближайших сообщений. Нечеткое подмножество можно рассматривать как сообщение, которое вместо того, чтобы быть бинарным, оказалось нечетким.

Рассмотрим обычное множество  нечетких подмножеств , принадлежащих одному и тому же универсальному множеству :

.                        (27.12)

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

Будем действовать следующим образом (и попутно объяснять, что понимается под «транзитивно ближайшим»).

1. Для каждой пары , , подсчитаем относительное обобщенное расстояние Хемминга , что дает отношение несходства .

2. Вычисляем (min-mах)-транзитивное замыкание [определенное в (26.41)]. Полученное отношение  дает (min-mах)-транзитивное расстояние

.                     (27.13)

3. Затем раскладываем  согласно (27.1) и получаем следующие обычные подмножества :

транзитивно ближайшие сообщения, для которых

;                     (27.14)

транзитивно ближайшие сообщения, для которых

;                      (27.15)

транзитивно ближайшие сообщения, для которых

               (27.16)

и т. д.

4. Строим соответствующее декомпозиционное дерево.

Пример. Пусть  - конечное универсальное множество с ; рассмотрим семь подмножеств или сообщений , .

                       (27.17)

Теперь подсчитаем относительное обобщенное расстояние Хемминга:

.                (27.18)

Это дает отношение несходства  (рис. 27.13,а). Затем с помощью (26.41) подсчитаем (min-mах)-транзитивное замыкание , которое дает транзитивные расстояния  (см. рис. 27.14 и 27.15).

Рис. 27.13.

Рис. 27.14.

Рис. 27.15.

Важное замечание о сущности транзитивного расстояния. В зависимости от характера решаемой проблемы (min-max)-транзитивное замыкание матрицы расстояний может не иметь значения в практических приложениях. Рассмотрим пример. Имеем следующие четыре сообщения:

Относительные обобщенные расстояния Хемминга для этих сообщений приведены на рис. 27.16, представляющем матрицу отношения несходства . На рис. 27.17 подсчитано (min-mах)-замыкание , т. е. . Теперь видно, что все эти сообщения являются транзитивно равноотстоящими.

Рис. 27.16.

Рис. 27.17.

Такое понимание (min-mах)-транзитивного расстояния может показаться неприемлемым в числовых приложениях. Но относительное обобщенное расстояние Хемминга транзитивно для обычной (min-sum)-операции, т. е.

,              (27.19)

а так как  - это расстояние, то

.                   (27.20)

К тем же выводам приводит рассмотрение относительного евклидова расстояния.

Таким образом, каждое отношение , задающее относительное обобщенное расстояние Хемминга (или относительное евклидово расстояние), есть отношение, совпадающее со своим собственным обычным (min-sum)-транзитивным замыканием. Заметим, что правая часть (27.19) может принять значение больше 1, так как здесь производится обычное сложение, но это ничего не меняет, поскольку член слева по построению всегда принадлежит .

Как будет показано ниже, разложение по уровням относительно значений, содержащихся в отношении несходства, дальше будет давать не классы эквивалентности, а максимальные подотношения.

Обычное (min-sum)-различие. Декомпозиция на максимальные подотношения. Отношение (27.19) можно рассматривать как отношение различия, которое можно назвать обычным (min-sum)-различием. Как видно в примере на рис. 27.19, для расстояний  ( произвольное) не получаются обычные графы, подграфы которых устанавливают классы эквивалентности. Иногда можно использовать менее строгое понятие, довольно интересное при различных операциях - понятие максимальных подотношений, которые могут быть как пересекающимися, так и непересекающимися.

Обратимся к рис. 27.19 и рассмотрим более подробно обычный симметричный граф, соответствующий . На рис. 27.18 мы изобразили этот обычный граф и выделили три максимальных подотношения или полных обычных графа, каждый из которых устанавливает отношение эквивалентности. Для каждого из этих подотношений расстояние каждого элемента до другого меньше или равно 0,42 и свойство (27.19) подтверждается. В общем случае такое разложение нельзя сделать без подходящего алгоритма; два таких алгоритма приводятся в приложении В.

Рис. 27.18.

Рис. 27.19.

Замечание. Обычное (min-sum)-различие недвойственно обычному (max-)-подобию. Двойственным к первому из этих отношений будет алгебраическое (min-sum)-различие [см. 26.23)].

Рассмотрим полностью разобранный пример, в котором появляются максимальные подотношения.

Пример. Разложим отношение различия, заданное рис. 27.13,а (см. декомпозицию на рис. 27.19).

Наконец, можно также использовать алгебраическую  (min-sum)-транзитивность для того, чтобы получить разложение на максимальные подотношения.

Сравнивая рис. 27.14 и 27.19, можно увидеть преимущества и недостатки использования (min-mах)-транзитивности, с одной стороны, и (min-sum)-транзитивности - с другой. Первая дает классы эквивалентности, которые появляются последовательно в зависимости от величины , интерпретация которой очень спорная. Вторая транзитивность дает только максимальные подотношения, в общем случае непересекающиеся; однако ее интерпретация бесспорна, особенно когда речь идет о приложениях в области классификации структур.