26. Отношения сходства

Отношение , такое, что

1)  (рефлексивность),                       (26.1)

2)  (симметрия),                 (26.2)

называется отношением сходства.

Пример 1. На рис. 26.1 приведен пример отношения сходства.

Рис. 26.1.

Пример 2. Отношение (16.12)

, ,                  (26.3)

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

(Min-mах)-расстояние на отношении сходства. Если  есть отношение сходства, то его транзитивное замыкание  есть отношение подобия. В таком случае понятие (min-mах)-расстояния, порожденного  , можно определить через расстояние, порожденное :

.                  (26.4)

Пример 1. Рассмотрим пример на рис. 26.1. С помощью композиционной формулы (17.3) мы подсчитали транзитивное замыкание , изображенное на рис. 26.2.

Рис. 26.2.

Далее определили  такое, что

.                  (26.5)

Отношение  изображено на рис. 26.3.

Рис. 26.3.

Наконец, имеем

                   (26.6)

и т. д.

Пример 2. Рассмотрим отношение сходства , определенное как

, , .              (26.7)

Это отношение представлено на рис. 26.4.

Рис. 26.4.

Подсчитав

,                      (26.8)

получим отношение, представленное на рис. 26.5. В таком случае имеем

               (26.9)

Рис. 26.5.

Следовательно, можно заключить, что

               (26.10)

Заметим, что, если в (26.7) считать, что

 и ,                  (26.11)

то получим

             (26.12)

для всех  и . Однако здесь нет парадокса, поскольку расстояние между  и  бесконечно мало и того же порядка, что и . Конечно, если расстоянию придать некоторый другой смысл, чем придаваемый рассмотренному здесь (min-mах)-расстоянию, то это заключение следует пересмотреть.

(Мах-)-транзитивное замыкание для отношения сходства. Пусть  - отношение сходства. В некоторых случаях предпочтительнее измерять расстояние между элементами с помощью (mах -)-оператора вместо (mах-min)-оператора, т. е. вместо (13.2) использовать (13.19):

.                     (26.13)

(Mах-)-транзитивное замыкание отношения определяется как

,                      (26.14)

где

, .                   (26.15)

Точка над  и  напоминает нам, что мы имеем дело с (max-)-композицией.

Рассмотрим пример. Напомним, что для отношения на рис. 26.1 мы подсчитали  и  на рис. 26.2 и 26.3. На рис. 26.6 можно увидеть, как определялись .

Замечания к вычислению . В (18.19) мы видели, что

,                 (26.16)

хотя обратное утверждение неверно.

Теорема 2 из § 17 (равенство (17.13)) также справедлива для (mах-)-операции. Для некоторого конкретного  имеем

.                     (26.17)

В случае, когда  есть отношение сходства, аналогично имеем

.                    (26.18)

(Min-sum)-расстояние на отношении сходства. (Min-sum)-расстоянием будем называть величину

.                       (26.19)

Но сначала следует установить, удовлетворяет ли эта функция аксиомам расстояния (25.17) - (25.20).

(25.17) удовлетворяется априори, поскольку .

(25.18) удовлетворяется априори, поскольку отношение  симметрично.

(25.20) удовлетворяется априори, поскольку отношение  рефлексивно, откуда следует, что .

Остается показать, что это расстояние действительно обладает свойством (25.19). Мы поступим так же, как это было сделано для (25.5)-(25.9). Имеем

,                       (26.20)

отсюда, следуя (8.23),

                    (26.21)

Это дает

,                   (26.22)

,                      (26.23)

где  есть алгебраическая сумма, определенная формулой (12.42). Теперь видно, что для (mах-sum)-оператора определенно удовлетворяется свойство (25.19).

Пример 1. Рассмотрим опять пример на рис. 26.1. На рис. 26.6 мы подсчитали (mах- )-транзитивное замыкание, т. е. . Теперь (min-sum)-расстояния будут задаваться отношением , для которого

.              (26.24)

Рис. 26.6.

На рис. 26.7 представлены (min-sum)-расстояния между различными элементами. Так,;  .

Рис. 26.7.

Пример 2. Вернемся к примеру на рис. 26.5. (Мах-)-композиция немедленно показывает, что

.                      (26.25)

Отношение  представлено на рис. 26.8. Очевидно, что

,                     (26.26)

и, как следствие,

.                      (26.27)

Рис. 26.8.

Замечание. Представляется, что  дает в практическом отношении лучшее расстояние, чем , это может оказаться очень важным для всего, что связано с проблемами сходства, и объясняет наш интерес к (min-sum)-расстоянию. Однако, как мы увидим на рис. 27.10, декомпозиция на обычные частичные графы дальше невозможна.

Теорема 1. Пусть  - отношение сходства. Тогда всегда справедливо включение

,                     (26.28)

т. е.

.               (26.29)

Доказательство. По условию (mах-min)-транзитивности имеем

.                     (26.30)

По условию (max-)-транзитивности имеем

.                       (26.31)

Но согласно (18.18)

,                      (26.32)

откуда следует

,                       (26.33)

т. е.

,                      (26.34)

где, напоминаем,  обозначает (max-)-композицию, а  обозначает (max-min)-композицию.

Отсюда

                      (26.35)

и, следовательно,

.                     (26.36)

Отношение несходства. Отношение , такое, что

1)  (антирефлексивность),               (26.37)

2)  (симметрия),                 (26.38)

называется отношением несходства (рис. 26.9).

Рис. 26.9.

Рассмотрим некоторые очевидные свойства. Если  - отношение сходства, то  - отношение несходства и наоборот.

Теорема 2. Если  есть (max-min)-транзитивное замыкание отношения сходства , то  есть (min-max)-транзитивное замыкание соответствующего отношения несходства.

Доказательство. (Мах-min)-транзитивное замыкание выражается посредством (17.8) и (17.3); таким образом,

                       (26.39)

и

.                 (26.40)

Тогда (min-max)-транзитивное замыкание запишем в виде

                        (26.41)

и

.                 (26.42)

Пусть  - отношение сходства,  - отношение подобия,  - отношение несходства и  - отношение различия. Покажем, что

.                      (26.43)

В (25.4)-(25.8) мы уже показали, что если  (max-min)-транзитивно, то и  (min-mах)-транзитивно.

Покажем теперь, что

                      (26.44)

Для проверки этого поступим так же, как в (25.4) - (25.8):

,                 (26.45)

                  (26.46)

Это доказывает (26.44).

Теперь запишем

   (26.47)

далее, используя теорему Де Моргана, получаем

и, наконец, согласно (26.44)

.

Рассмотрим пример. Возьмем опять отношение сходства, представленное на рис. 26.1, для которого соответствующее отношение подобия представлено на рис. 26.2, а матрица расстояний - на рис. 26.3. Мы встретимся с этими отношениями еще раз при расчетах, которыми заканчивается нахождение  на рис. 26.10,г-з.

Рис. 26.10.

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

Теорема 3. Пусть  есть (mах-min)-транзитивное замыкание некоторого нечеткого отношения  и  - (min-max)-транзитивное замыкание . Тогда

.                      (26.48)

Это утверждение можно сформулировать и так: можно переставить порядок операций  и , но при этом  заменяется на  (и наоборот) .

С учетом этого читатель может искать другие интересные свойства, связанные с (max-min)- и (min-maх)-транзитивными замыканиями, которые он может характеризовать как дуальные, не боясь упреков в использовании этого слова.