Дискретно-непрерывная математика (стр. 44 )

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

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

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

(17.2)

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

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

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

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

(17.4)

Тогда

(17.5)

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

(17.6)

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

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

(17.7)

и

(17.8)

что вместе с (17.2) и (17.3) доказывает транзитивность Эта обратная теорема позволяет синтезировать отношения подобия,

в то время как прямая теорема позволяет проводить анализ.

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

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

Рис. 17.1

Рис. 17.2

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

(17.9)

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

Рис. 17.3

Другой пример дан на рис. 17.4, где предполагается, что а и b [0,1] при а < b.

Рис. 17.4

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

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

Рис. 17.5

Рис. 17.6

Пример 2 (рис. 17.7 и 17.8). Этот пример — на транзитивное замыкание (рис. 16.2) отно­шения сходства (рис. 16.1).

Рис. 17.7

Рис. 17.8

Полученное здесь разложение мы сравним с тем, которое полу­чится в следующем примере (рис. 17.9 и 17.10).

Рис. 17.9

Рис. 17.10

Пример 3 (рис. 17.9 и 17.10). (Мах— •)-транзитивное замыкание отношения сходства на рис. 16.1 было представлено на рис. 16.6. Для этого на рис. 16.7 выписали матрицу (max — sum)-расстояний. В этом примере при декомпозиции на обычные графы расстояний

появятся нетранзитивные графы. Использование (max — •)-тран­зитивного замыкания в отношении сходства менее удобно по срав-

нению с использованием (max — min) тран­зитивного замыкания.

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

Pис. 17.11

Такая схема называется декомпозиционным деревом.

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

Pис. 17.12

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

(17.10)

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

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

0,7(0,8 (0,9(1{А, D}, 1{Е}), 0,9 (1 {В})), 0,8 (0,9(1 {С}))). (17.11)

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

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

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

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

(17.12)

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

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

1. Для каждой пары подсчитаем относи­тельное обобщенное расстояниеХемминга (или относительное евклидово расстояние ε (Аі, Аj) в зависимости от характера проблемы или даже какое-нибудь другое расстояние) что дает отно­шение несходства

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

(17.13)

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

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

(17.14)

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

(17.15)

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

(17.16)

и т. д.

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

Пример. Пусть Е — конечное универсальное множество с

card (Е) = 7; рассмотрим семь подмножеств или сообщений

i = 1, 2.....6.

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

(17.18)

Это дает отношение несходства(рис. 17.13, а).

Рис. 17.13

Затем с помощью (16.41) подсчитаем (min — тах)-транзитивное замыкание которое дает транзитивные расстояния δ (см. рис. 17.14 и 17.15).

Рис. 17.14