Нечеткие отношения

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

Основные определения

Теория нечетких отношений находит также приложение в задачах, в которых традиционно применяется теория обычных (четких) отношений. Как правило, аппарат теории четких отношений используется при качественном анализе взаимосвязей между объектами исследуемой системы, когда связи носят дихотомический характер и могут быть проинтерпретированы в терминах "связь присутствует", "связь отсутствует", либо когда методы количественного анализа взаимосвязей по каким-либо причинам неприменимы и взаимосвязи искусственно приводятся к дихотомическому виду. Например, когда величина связи между объектами принимает значения из ранговой шкалы, выбор порога на силу связи позволяет преобразовать связь к требуемому виду. Однако, подобный подход, позволяя проводить качественный анализ систем, приводит к потере информации о силе связей между объектами либо требует проведения вычислений при разных порогах на силу связей. Этого недостатка лишены методы анализа данных, основанные на теории нечетких отношений, которые позволяют проводить качественный анализ систем с учетом различия в силе связей между объектами системы.

Обычное неразмытое $$n$$ -арное отношение $$R$$ определяется как подмножество декартова произведения $$n$$ множеств$$R \subseteq X_1 \times X_2 \times \ldots \times X_n .$$

Подобно нечеткому множеству, нечеткое отношение можно задать с помощью его функции принадлежности$$\mu _R :X_1 \times \ldots \times X_n \to L,\vspace{-2mm}$$ где в общем случае будем считать, что $$L$$ — это полная дистрибутивная решетка. Таким образом, $$L$$ — это частично упорядоченное множество, в котором любое непустое подмножество имеет наибольшую нижнюю и наименьшую верхнюю грани и операции пересечения и объединения в $$L$$ удовлетворяют законам дистрибутивности. Все операции над нечеткими отношениями определяются с помощью этих операций из $$L$$. Например, если в качестве $$L$$ взять ограниченное множество вещественных чисел, то операциями пересечения и объединения в $$L$$ будут, соответственно, операции $$\min$$ и $$\max$$, и эти операции будут определять и операции над нечеткими отношениями.

Далее мы ограничимся рассмотрением лишь бинарных нечетких отношений, являющихся отображением на отрезок $$[0,1]$$, т.е. $$\mu _R \colon X \times Y \to \left[ {0,1} \right]$$.

Если множества $$X$$ и $$Y$$ конечны, нечеткое отношение $$R$$ между $$X$$ и $$Y$$ можно представить с помощью его матрицы отношения, первой строке и первому столбцу которой ставятся в соответствие элементы множеств $$X$$ и $$Y$$, а на пересечении строки $$x$$ и столбца $$y$$ помещается элемент $$\mu_{R}(x,y)$$ (см. табл.2.1).

В случае, когда множества $$X$$ и $$Y$$ совпадают, нечеткое отношение $$R$$ называют нечетким отношением на множестве X.

В случае конечных или счетных универсальных множеств очевидна интерпретация нечеткого отношения в виде взвешенного графа, в котором каждая пара вершин $$(x,y)$$ из $$X\times Y$$ соединяется ребром с весом $$R(x,y)$$.

Пример. Пусть $$X={x_{1},x_{2}}$$ и $$Y={y_{1},y_{2},y_{3}}$$, тогда нечеткий граф, изображенный на рис рис. 2.1, задает некоторое нечеткое отношение $$R\hm\subset X\times Y$$.

Операции над нечеткими отношениями

Объединение и пересечение нечетких отношений определяется следующим образом:$$\begin{gathered} \forall x \in X\;\forall y \in Y\quad \quad R \cup S\;(x,y) = R(x,y) \vee S(x,y) , \\ \forall x \in X\;\forall y \in Y\quad \quad R \cap S\;(x,y) = R(x,y) \wedge S(x,y) \end{gathered}$$

Отношение включения $$\(R \subseteq S\)$$ для нечетких отношений определяется с помощью отношения частичного порядка на $$L$$:$$\forall x \in X\;\forall y \in Y\quad \quad R \subseteq S\; \Leftrightarrow R(x,y) \leqslant S(x,y) .$$

Множество $$\(\rho \,(X \times Y)\)$$ всех нечетких отношений между $$X$$ и $$Y$$ образует дистрибутивную решетку по отношению к операциям объединения и пересечения и удовлетворяет следующим тождествам:

1. Идемпотентность:$$R \cap R = R,\quad R \cup R = R .$$

2. Коммутативность:$$R \cap S = S \cap R,\quad R \cup S = S \cup R .$$

3. Ассоциативность:$$R \cap (S \cap T) = (R \cap S) \cap T,\quad R \cup (S \cup T) = (R \cup S) \cup T .$$

4. Дистрибутивность:$$R \cap (S \cup T) = (R \cap S) \cup (R \cap T),\quad R \cup (S \cap T) = (R \cup S) \cap (R \cup T) .$$

Выполнение этих тождеств для $$\(\rho \,(X \times Y)\)$$ следует из выполнения соответствующих тождеств для решетки $$L$$. В $$\(\rho \,(X \times Y)\)$$ выполняется также следующее соотношение:$$S \subseteq T\quad \Rightarrow \quad R \cup S \subseteq R \cup T,\quad R \cap S \subseteq R \cap T .$$

Из полноты решетки $$L$$ следует, что она обладает наименьшим 0 и наибольшим I элементами. Эти элементы определяют, соответственно, пустое и универсальное нечеткие отношения:$$\forall x\,\forall y\;\Theta (x,y) = 0,\quad \quad \forall x\,\forall y\;U(x,y) = I .$$

Следующее соотношение определяет композицию $$\(R \circ S\)$$ нечетких отношений $$R$$ и $$S$$:$$\forall x \in X\;\,\forall z \in Z\quad R \circ S(x,z) = \mathop \vee \limits_{y \in Y} \left( {R(x,y) \wedge S(y,z)} \right) .$$

Здесь $$\(\mathop \vee \limits_{y \in Y}\)$$ обозначает наименьшую верхнюю грань множества элементов $$\(\left( {R(x,y) \wedge S(y,z)} \right)\)$$, где $$y$$ пробегает все значения из $$Y$$. В силу полноты $$L$$ эта операция всегда определена.

Существуют и другие варианты операции композиции, которые определяются с помощью дополнительных операций, выводимых в $$L$$. В зависимости от того, является ли $$L$$ множеством векторов, множеством лингвистических переменных или множеством чисел, эти дополнительные операции будут иметь соответствующий вид. Например, если $$L$$ является множеством действительных чисел, то операция $$\( \wedge\)$$ может быть заменена на операцию взятия среднего арифметического, что дает другое определение операции композиции:$$\forall x \in X\;\forall z \in Z\quad R \circ S(x,y) = \bigvee \limits_{y \in Y} \left( {0,5(R(x,y) + S(y,z))} \right) .$$

В случае $$\(L = \left[ {0,1} \right]\)$$ мы имеем$$\forall x \in X\;\forall z \in Z\quad \mu _{R \circ S} (x,z) = \bigvee \limits_{e \in Y} (\mu _R (x,y) \wedge \mu _S (x,y)) .$$

Замена операции $$\( \wedge\)$$ на операцию умножения дает следующее определение композиции: $$\( \forall x \in X\,\forall z \in Z\ \mu _{R \circ S} (x,z) = \mathop \vee \limits_{e \in Y} (\mu _R (x,y) {\cdot} \mu _S (x,y)) .\)$$

Нечеткое отношение $$E$$ такое, что$$E(x,y) = \left\{ {\begin{array}{*{20}c} {I,} {\t{\char229}\t{\char241}\t{\char235}\t{\char232}\;x = y,} \\ 0 {\t{\char226}\;\t{\char239}\t{\char240}\t{\char238}\t{\char242}\t{\char232}\t{\char226}\t{\char237}\t{\char238}\t{\char236}\;\t{\char241}\t{\char235}\t{\char243}\t{\char247}\t{\char224}\t{\char229}.} \\ \end{array} } \right.$$ играет по отношению к операции композиции роль единицы: $$\(E \circ R = {R \circ E} = R\)$$. В теории четких отношений отношение Е называется отношением равенства.

Для любого нечеткого отношения $$R$$ определяется также обратное отношение $$\(R^{ - 1}\)$$:$$\forall x,y \in X\quad R^{ - 1} (x,y) = R(y,x) .$$

Свойства нечетких отношений

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

1. Рефлексивность:$$E \subseteq R,\quad \quad \quad \forall x \in X\quad R(x,x) = I .$$

2. Слабая рефлексивность:$$\forall x,y \in X\quad R(x,y) \leqslant R(x,x) .$$

3. Сильная рефлексивность:$$\forall x,y \in X\quad R(x,y) < I .$$

4. Антирефлексивность:$$R \cap E = \varnothing \quad \quad \quad \forall x \in X\quad R(x,x) = 0 .$$

5. Слабая антирефлексивность:$$\forall x,y \in X\quad R(x,x) \leqslant R(x,y) .$$

6. Сильная антирефлексивность:$$\forall x,y \in X\quad 0 < R(x,y) .$$

7. Симметричность:$$R = R^{ - 1} ,\quad \quad \quad \forall x,y \in X\quad R(x,y) = R(y,x) .$$

8. Антисимметричность:$$R \cap R^{ - 1} \subseteq E,\quad \quad \quad \forall x,y \in X(x \ne y)\quad R(x,y) \wedge R(y,x) = 0 .$$

9. Асимметричность:$$R \cap R^{ - 1} = \varnothing ,\quad \quad \quad \forall x,y \in X\quad R(x,y) \wedge R(y,x) = 0 .$$

10. Сильная линейность:$$R \cup R^{ - 1} = U,\quad \quad \quad \forall x,y \in X\quad R(x,y) \vee R(y,x) = I .$$

11. Слабая линейность:$$\forall x,y \in X\quad R(x,y) \vee R(y,x) > 0 .$$

12. Транзитивность:$$R \supseteq R \circ R,\quad \quad \quad \forall x,y,z \in X\quad R(x,z) \geqslant R(x,y) \wedge R(y,z) .$$

Декомпозиция нечетких отношений

Одно из важнейших свойств нечетких отношений заключается в том, что они могут быть представлены в виде совокупности обычных отношений, причем могут быть упорядочены по включению, представляя собой иерархическую совокупность отношений. Разложение нечеткого отношения на совокупность обыкновенных отношений основано на понятии $$\alpha$$ -уровня нечеткого отношения. Здесь для простоты будем полагать, что $$L$$ линейно упорядочено.

$$\alpha$$ -уровнем нечеткого отношения $$R$$ называется обычное отношение $$\(R_\alpha\)$$, определяемое для всех $$\alpha>0$$ следующим образом:$$R_\alpha = \left\{ {(x,y) \in X^2 |R(x,y) \geqslant \alpha } \right\} .$$

Очевидно, что $$\alpha$$ -уровни нечетких отношений удовлетворяют соотношению:$$\alpha \leqslant \beta \quad \Rightarrow \quad R_\alpha \supseteq R_\beta ,$$ представляя собой совокупность вложенных друг в друга отношений.

Теорема. Нечеткое отношение $$R$$ обладает каким-либо свойством из перечисленных (кроме сильной рефлексивности, сильной антирефлексивности, слабой линейности) тогда и только тогда, если этим свойством обладают все его $$\alpha$$ -уровни.

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

Нечеткое отношение $$R$$ может быть представлено в следующем виде:$$R = \mathop \cup \limits_\alpha \,\alpha R_\alpha ,$$ где отношения $$\(\alpha R_\alpha\)$$ определяются следующим образом:$$\alpha R_\alpha (x,y) = \left\{ {\begin{array}{*{20}c} {\alpha ,} {\t{\char229}\t{\char241}\t{\char235}\t{\char232}\;R_\alpha (x,y) = 1,} \\ 0 {\t{\char226}\;\t{\char239}\t{\char240}\t{\char238}\t{\char242}\t{\char232}\t{\char226}\t{\char237}\t{\char238}\t{\char236}\;\t{\char241}\t{\char235}\t{\char243}\t{\char247}\t{\char224}\t{\char229}.} \\ \end{array} } \right.$$

Кроме всех вышеописанных свойств, выполняющихся для всех $$\alpha$$ -уровней, могут быть определены аналогичные свойства, выполняющиеся только для одного или нескольких $$\alpha$$ -уровней. Приведем примеры таких $$\alpha$$ -свойств, предполагая, что элемент $$\alpha$$ фиксированный:

$$\alpha$$ -симметричность$$\forall x,y \in X\quad R(x,y) \geqslant \alpha \quad \Rightarrow \quad R(y,x) \geqslant \alpha ;$$

$$\alpha$$ -транзитивность$$\forall x,y,z \in X\quad R(x,y) \geqslant \alpha ,R(y,z) \geqslant \alpha \quad \Rightarrow \quad R(x,z) \geqslant R(x,y) \wedge R(y,x) .$$

Аналогично могут быть определены и другие $$\alpha$$ -свойства. Они могут рассматриваться в задачах, в которых вводится порог на силу отношения $$R$$ либо ищется такое $$\alpha$$, при котором $$\(R_\alpha\)$$ обладает требуемым свойством.

Транзитивное замыкание нечетких отношений

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

Транзитивным замыканием отношения $$R$$ называется отношение $$\(\hat R\)$$, определяемое следующим образом:$$\hat R = R^1 \cup R^2 \cup \ldots \cup R^k \cup \ldots ,$$ где отношения $$\(R^k\)$$ определяются рекурсивно:$$R^1 = R,\quad R^k = R^{k - 1} \circ R,\;\;k = 2,3,4,\ldots .$$

Теорема. Транзитивное замыкание $$\(\hat R\)$$ любого нечеткого отношения $$R$$ транзитивно и является наименьшим транзитивным отношением, включающим $$R$$ , т.е. $$\(R \subseteq \hat R\)$$ , и для любого транзитивного отношения $$T$$ , такого, что $$\(R \subseteq T\)$$ , следует $$\(\hat R \subseteq T\)$$.

Как следствие из данной теоремы получаем, что $$R$$ транзитивно тогда и только тогда, если $$\(R = \hat R\)$$.

Если множество $$X$$ содержит $$n$$ элементов, то имеем$$\hat R = R^1 \cup R^2 \cup \ldots \cup R^n.$$

В случае, когда $$R$$ рефлексивно, имеем$$R \subseteq R^1 \subseteq \ldots \subseteq R^{n - 1} = R^n = R^{n + 1} = \ldots$$

Весьма полезным фактором является то, что $$\alpha$$ -уровень транзитивного замыкания нечеткого отношения $$R$$ совпадает с транзитивным замыканием соответствующего $$\alpha$$ -уровня:$$(\hat R)_\alpha = (\hat R_\alpha ),\quad \quad \t{\char228}\t{\char235}\t{\char255}\;\t{\char226}\t{\char241}\t{\char229}\t{\char245}\quad \alpha \ne 0.$$

Заметим, что при транзитивном замыкании нечеткого отношения $$R$$ в общем случае сохраняются лишь некоторые свойства отношения $$R$$. Такими свойствами являются рефлексивность, симметричность, линейность и транзитивность.

Проекции нечетких отношений

Важную роль в теории нечетких множеств играет понятие проекции нечеткого отношения. Дадим определение проекции бинарного нечеткого отношения.

Пусть $$\mu_{Q}(x,y)$$ — функция принадлежности нечеткого отношения в $${U\times V}$$. Проекции $$Q_{U}$$ и $$Q_{V}$$ отношения $$Q$$ на $$U$$ и $$V$$ — есть множества в $$U$$ и $$V$$ с функцией принадлежности вида$$\begin{gathered} \mu _{Q_U } (x) = \mathop {\sup }\limits_V \;\mu _Q (x,y), \\ \mu _{Q_V } (y) = \mathop {\sup }\limits_U \;\mu _Q (x,y). \\ \end{gathered}$$

Условной проекцией нечеткого отношения $$Q$$ на $$U$$, при произвольном фиксированном $$y_{0}\in V$$, называется множество $$P_{U}$$ с функцией принадлежности вида $$\(\mu _{P_U } (x|y_0 ) = \mu _Q (x,y_0 )\)$$.

Аналогично определяется условная проекция на $$V$$ при заданном $$x_{0}\in U$$:$$\mu _{P_V } (y|x_0 ) = \mu _Q (x_0 ,y).$$

Из данного определения видно, что проекции $$Q_{U}$$ и $$Q_{V}$$ не влияют на условные проекции $$P_{U}$$ и $$P_{V}$$, соответственно. Дадим далее определение, которое учитывает их взаимосвязь.

Условные проекции второго типа определяются следующим образом:$$\begin{gathered} \mu _{P_U } (x|y_0 ) = \frac{{\mu _Q (x,y_0 )}} {{\mu _{Q_V } (y_0 )}},\quad \mu _{Q_V } (y_0 ) > 0, \\ \mu _{P_U } (y|x_0 ) = \frac{{\mu _Q (x_0 ,y)}} {{\mu _{Q_U } (x_0 )}},\quad \mu _{Q_U } (x_0 ) > 0. \\ \end{gathered}$$

Если $$\(\mu _{Q_V } (y_0 ) = 0\)$$ или $$\(\mu _{Q_U } (x_0 ) = 0\)$$, то полагаем, соответственно, что $$\(\mu _{P_U } (x|y_0 ) = 0\)$$ или $$\(\mu _{P_U } (y|x_0 ) = 0\)$$.

Заметим, что условные проекции первого типа содержатся в соответствующих проекциях второго типа.

Пусть $$U$$ и $$V$$ — базовые множества, $$Q$$ — нечеткое отношение в $$U\times V$$ и $$Q_{U}$$ и $$Q_{V}$$ — его проекции на $$U$$ и $$V$$, соответственно.

Нечеткие множества $$Q_{U}$$ и $$Q_{V}$$ называются независимыми, если$$Q= Q_{U}\times Q_{V}.$$

Следовательно, они независимы по первому типу, если$$\mu _Q (x,y) = \mu _{Q_U } (x) \wedge \mu _{Q_V } (y),$$ и независимы по второму типу, если$$\mu _Q (x,y) = \mu _{Q_U } (x) \cdot \mu _{Q_V } (y).$$

В противном случае проекции $$Q_{U}$$ и $$Q_{V}$$ являются зависимыми (соответствующего типа).

Независимость второго типа можно интерпретировать следующим образом. Данные соотношения с учетом производильности $$x_{0}$$ и $$u_{0}$$ перепишем в виде$$\begin{gathered} \mu _Q (x,y) = \mu _{P_U } (x|y)\mu _{Q_V^{} } (y), \\ \mu _Q (x,y) = \mu _{P_V } (y|x)\mu _{Q_U^{} } (x). \\ \end{gathered}$$