Параметры и принципы действия различных систем могут быть связаны по выбранному признаку между собой разного рода отношениями. Если, допустим, нас интересует влияние цены услуги на её востребованность, то данная связь может быть описана отношением типа «влияет», «сильно влияет», «слабо влияет», и т.д. В этом случае довольно «дискретных» объектов для описания может не хватить. Для многих прикладных задач теории автоматов, распознавания образов, принятия решений и т.д. имеет смысл обобщить понятие отношения между объектами на нечёткий случай. При этом модель, вполне возможно, будет более адекватно описывать систему, позволяя проводить качественный анализ систем без потери пороговой информации, в связи с появлением новых типов отношений: подобие, сходство, несходство, ...

Понятие нечёткого отношения (связи, ассоциации, взаимосвязи, соотношения — синонимы), наряду с понятием нечёткого множества, относится к фундаментальным основам всей теории нечётких множеств. В добавок к тому, что они сами по себе имеют прикладное значение, на их основе определяется целый ряд дополнительных понятий, используемых для построения нечётких моделей более сложных систем.

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

(извиняюсь)

Определение

Как и в случае с нечётким множеством (НМ), нечёткое отношение обобщает понятие привычного нам обычного отношения в (наивной) теории множеств. А многие понятия, введённые для отношений далее, будут схожи с соответствующими понятиями для НМ.

Введём понятия нечёткого отношения и рассмотрим его свойства.

Нечётким 2-арным (бинарным) отношением $inline$ на универсальном множестве $U = U_1 \times U_2$ называется нечёткое подмножество декартова произведения $U_1 \times U_2$ , которое характеризуется функцией принадлежности $\mu_R(x, y) : U_1 \times U_2 \mapsto [0, 1], x \in U_1, y \in U_2$ . Или другой способ записи:

$R = \bigcup_{(x, y) \in U_1 \times U_2} \mu_R(x, y) / (x, y)$

В общем случае n-арное отношение есть нечёткое подмножество $inline$ n-арного декартова произведения.

Стоит отметить, что в приложениях теории нечёткого отношения часто оказывается удобным вместо промежутка $inline$ брать какую-либо общую структуру (множество вещественных чисел, множество лингвистических переменных и т.д.). Мы же в дальнейшем будем использовать именно промежуток $inline$ . При этом $\mu_R(x, y)$ характеризует субъективную степень соответствия пары $inline$ отношению $xRy \Leftrightarrow (x, y) \in R$ . Среди важных оговорок также скажу, что свойства и теоремы для бинарных отношений легко экстраполируются на n-арные случаи.

Существует несколько способов задания отношений.

Словесное;
Непосредственное перечисление всех пар $inline$ и соответствующих им $\mu_R(x_i, y_j)$ ;
Матрицей $||\mu_R(x_i, y_j)||$ ;
С помощью графа $\widetilde{G} = (\widetilde{U}, \widetilde{V})$ , где $\widetilde{U} = \left\{ u_n \right\}, n \in \mathbb{N}$ — множество вершин, а $\widetilde{V} = \left\{ \rangle \mu_{\widetilde{R}}(u_i, u_j) / (u_i, u_j) \langle, \mu_{\widetilde{R}}(u_i, u_j) > 0 \right\}$ — множество нечётких дуг. (в данном случае волнистая линия над символом подчёркивает, что мы говорим о нечёткой теории. Далее, как и в начале, я буду опускать его, ибо мне лень набирать xD)

Графические представления зачастую делают буквально очевидными некоторые из свойств нечётких отношений.

Пример

Пусть на множестве $inline$ определено нечёткое отношение $inline$ «намного больше» ( x>>y ). Тогда матрица этого отношения и граф будут иметь вид соответственно:

Характеристики

Далее будет подразумеваться $inline$ — нечёткие бинарные отношения в $U_1 \times U_2, x \in U_1, y \in U_2$

Носителем нечёткого отношения $inline$ на множестве $inline$ называется такое подмножество декартова произведения $U_1 \times U_2$ :

$supp(R) = \left\{ (x, y): \mu_R(x, y) > 0, (x, y) \in U_1 \times U_2 \right\}$

Одно из нечётких отношений $inline$ содержится в нечётком отношении $inline$ , если

$\forall (x, y) \Rightarrow \mu_R(x, y) \leq \mu_S(x, y)$

Первая проекция (просто проекция) нечёткого бинарного отношения определяется функцией принадлежности:

$\mu_R^{(1)}(x, y) = max_y(\mu_R(x, y))$

Вторая проекция определяется как:

$\mu_R^{(2)}(x, y) = max_x(\mu_R(x, y))$

Глобальная проекция нечёткого множества $inline$ есть вторая проекция первой проекции или наоборот:

$h(R) = max_x(max_y(\mu_R(x, y))) = max_y(max_x(\mu_R(x, y)))$

Отношение нормально, если $inline$ , иначе — субнормально.

Дополнением нечёткого отношения $inline$ является такой $\bar{R}$ , что:

$\mu_{\bar{R}}(x, y) = 1 - \mu_R(x, y)$

Чётким отношением, близким к нечёткому $inline$ называют такое чёткое отношение $R_{ч} | \mu_{R_ч}(x, y) = \begin{cases}0, & \mu_R(x, y) < 0.5 \\ 1, & \mu_R(x, y) > 0.5 \\ 0 или 1, & \mu_R(x, y) = 0.5 \end{cases}.$ Принято считать, что при характеристической функции нечёткого отношения равной 0.5 функция для близкого будет равна 0.

Обратным отношением к $inline$ называют такое отношение $R^{-1}$ , что $\mu_{R^{-1}}(x, y) = \mu_R(y, x).$ Матрица отношения $R^{-1}$ в таком случае будет транспонированной матрицей $inline$ .

Операции

Объединение и пересечение:

$\mu_{R \cup S}(x, y) = max(\mu_R(x, y), \mu_S(x, y));\\ \mu_{R \cap S}(x, y) = min(\mu_R(x, y), \mu_S(x, y))$

. Множество всех нечётких отношений образует дистрибутивную решётку по отношению к операциям объединения и пересечения; и из выполнения тождеств идемпотенции, коммутативности, ассоциативности, поглощения и дистрибутивности для решётки $inline$ следует выполнение этих тождеств для всех отношений.

В логике, основанной на теории обычных множеств, высказывание вроде «числа x и y очень близкие или/и очень различные» должно быть сокращено до «числа x и y очень близкие или очень различные». Однако в теории нечётких множеств первое высказывание вполне логично; оно выражает тот факт, что связка «и» интерпретируема при очень малых значениях функции принадлежности, когда об x и y нельзя сказать ни что они очень близки, ни что они очень отличаются друг от друга. Этот пример хорошо иллюстрирует гибкость высказываний, присущую настоящей логике.

Алгебраическое произведение: $\mu_{R \cdot S}(x, y) = \mu_R(x, y) \cdot \mu_S(x, y)$ ; алгебраическая сумма: $\mu_{R + S}(x, y) = \mu_R(x, y) + \mu_S(x, y) - \mu_R(x, y) \cdot \mu_S(x, y)$ .

Как и в случае нечётких множеств, нечёткое отношение можно декомпозировать на специальным образом устроенную систему обычных отношений и наоборот. Такая декомпозиция и синтез производится с помощью подмножеств $\alpha$ -уровня нечёткого отношения. Это может помочь в прикладных задачах, выручает при доказательстве теорем и экономит в некоторых ситуациях вычислительные ресурсы машин. Подмножеством альфа-уровня называется обычное подмножество $R_{\alpha} = \left\{ (x, y): \mu_R(x, y) \geq \alpha \right\}$ . Достаточно очевидно, что $\alpha_1 \geq \alpha_2 \Rightarrow R_{\alpha_1} \subset R_{\alpha_2}$ .

С этим связано одно очень важное утверждение (формально теорема) о декомпозиции. Любое отношение $inline$ можно представить в форме $R = max_{\alpha}(\alpha \times R_{\alpha})$ .

Композиция отношений

Важное значение в теории нечётких множеств имеет композиция нечётких отношений. Как и в случае с действиями с НМ, композицию можно определить многими способами. Одним из наиболее общих способов является (Max-*)-композиция. Однако, здесь я рассмотрю лишь 3 наиболее употребляемые.

max-min композиция (максиминная композиция): $RS : \mu_{RS}(x, z) = max_{y \in U}(min(\mu_R(x, y), \mu_S(y, z)))$ . Наиболее часто используется.
min-max композиция (минимаксная композиция): $R \circ S : \mu_{R \circ S}(x, z) = min_{y \in U}(max(\mu_R(x, y), \mu_S(y, z)))$ .
max-• композиция (максимультипликативная композиция): $R * S : sup_{y \in U}(\mu_R(x, y) \cdot \mu_S(y, z))$ .

Пример

Пусть имеются два отношения $inline$ на $inline$ , состоящем из двух элементов. Матрицы отношений: $\mu_A(x, y) = \begin{bmatrix}0.2 & 0.6 \\0.5 & 0.8 \end{bmatrix}, \\ \mu_B(x, y) = \begin{bmatrix}0.5 & 0.7 \\0.3 & 1 \end{bmatrix}$

Тогда композиции этих отношений быдут соответственно:

$\mu_{AB}(x, y) = \begin{bmatrix}0.3 & 0.6 \\0.5 & 0.8 \end{bmatrix}$ ;
$\mu_{A \circ B}(x, y) = \begin{bmatrix}0.5 & 0.7 \\0.5 & 0.7 \end{bmatrix}$ ;
$\mu_{A * B}(x, y) = \begin{bmatrix}0.18 & 0.6 \\0.25 & 0.8 \end{bmatrix}$ .

Свойства

Среди множества отношений выделяют особые классы. Классы множеств демаркируют свойствами:

Рефлексивность: $\mu_R(x, x) = 1, \forall (x, x) \in U$ ;

Слабая рефлексивность: $\mu_R(x, y) \leq \mu_R(x, x)$ ;

Сильная рефлексивность: $\mu_R(x, x) = 1, \mu_R(x, y) < 1$ ;

Антиреflexxивность: $\mu_R(x, x) = 0, \forall (x, x) \in U$ ;

Симметричность: $\mu_R(x, y) = \mu_R(y, x)$ ;

Антисимметричность: $\mu_R(x, y) \neq \mu_R(y, x) \vee_{(или)} \mu_R(x, y) = \mu_R(y, x) = 0$ ;

Совершенная антисимметричность: $x \neq y, \mu_R(x, y) > 0 \Rightarrow \mu_R(y, x) = 0$ ;

Транзитивность: $\mu_R(x, z) \geq max_y(min(\mu_R(x, y), \mu_R(y, z)))$ .

… На самом деле эти и остальная куча классов нужны для вывода специфичных для конкретного класса теорем. Не вижу смысла рассматривать их подробно здесь.

Пробный пример

Пусть в гипотетической игре имеются 2 NPC-квестодателя, назовём их $inline$ и $inline$ . Каждый из них требует, чтобы вы принесли ему волчьи хвосты. Из разговоров других NPC игрок узнаёт стратегии приёма предметов каждого из квестодателей:

$inline$ Если хвостов мало, то вероятность сдачи квеста малая, иначе не малая.

$inline$ Если хвостов не мало, то вероятность сдачи квеста большая, иначе — небольшая.

По условиям задачи, игроку из разговоров местных жителей также известны некоторые понятия, используемые в стратегиях:

«Мало волчьих хвостов» $inline$

«Малая вероятность» $inline$

«Большая вероятность» $inline$

Игрок в инвентаре персонажа после долгого гринда имеет не очень мало волчьих хвостов. Вопрос: у какого из двух NPC большая вероятность закрыть квест?

Решение

Для начала определим вспомогательные функции, которые могут понадобиться в связи с условием:

def very(arr: List[set]):
    return [(elem[0]**2, elem[1]) for elem in arr]


def no(arr: List[set]):
    return [(1 - elem[0], elem[1]) for elem in arr]


def attitude(a: List[set], b: List[set], func = lambda x, y: min(x, y)):
    return [[func(i[0], j[0]) for j in b] for i in a]


def attitude_unite(a: List[List], b: List[List]):
    return [[max(a[i][j], b[i][j]) for j in range(len(a[i]))] for i in range(len(a))]


def composition(a: List[List], b: List[List]):
    result = [[0 for j in range(len(b[0]))] for i in range(len(a))]

    for x in range(len(a)):
        for z in range(len(b[0])):
            maximum = min(a[x][0], b[0][z])

            for y in range(0, len(a[0])):
                if maximum < min(a[x][y], b[y][z]):
                    maximum = min(a[x][y], b[y][z])
            
            result[x][z] = maximum

    return result


def index_plus(a: List[List]):
    maximum = max([elem[1] for elem in a])
    result = 0
    for i in range(len(a)):
        result += a[i][0] * (a[i][1] + maximum) / 2

    return result


def ranking_index(a: List[List], b: List[List]):
    return index_plus(a) - index_plus(b)

В качестве нечётких множеств используются списки кортежей, в качестве матриц — списки строк-списков. Все функции должны быть понятны и знакомы, за исключением, вполне вероятно, index_plus и ranking_index. Эти две функции реализуют индекс ранжирования для двух нечётких множеств. В общем виде этот индекс ранжирования (используемый в данной статье; на самом деле индекс ранжирования нечётких множеств может быть определён иначе, это отдельная тема для статей и исследований) выглядит так:

$H(A, B) = H_+(A) - H_+(B), \\ где \ H_+(X) = \int_{0}^{1}M(X_0)dX, \\ M(X_0) = \frac{(inf_{x \in X_0}(x) + sup_{x \in X_0}(x)) }{2}.$

$inline$ и $inline$ — нечёткие множества. Начнём решение. Для начала следует определить используемые нечёткие величины и отношения:

A = [(0.8, 3), (0.4, 15), (0.3, 30)]
B = [(0.1, 0.9), (0.5, 0.5), (0.8, 0.1)]
C = [(0.8, 0.9), (0.5, 0.5), (0.3, 0.2)]

Пусть $inline$ — «не очень мало». $"Не \ очень \ мало" = \overline{"очень \ мало"} = \overline{CON("мало")}.$ Для нужд последующих вычислений преобразуем полученный результат к матрице 1 на 3 только со значением функции принадлежности в ячейках:

x = no(very(A))
x = [[elem[0] for elem in x]]

Обозначим общую стратегию NPC $inline$ переменной R1. Из условия $R_1 = A \times B \ \cup \ \overline{A} \times \overline{B}$ :

AonB = attitude(A, B)
notAonnotB = attitude(no(A), no(B))
R1 = attitude_unite(AonB, notAonnotB)

В итоге рассчитаем вектор $inline$ , полученный композицией входного вектора (количества хвостов) с отношением $inline$ .

y1 = composition(x, R1)
print('y1 = ', y1)
# >> y1 =  [[0.63, 0.3599999999999999, 0.3599999999999999]]

Те же процедуры соответственно выполним для второго квестодателя:

notAonC = attitude(no(A), C)
AonnotC = attitude(A, no(C))
R2 = attitude_unite(notAonC, AonnotC)
y2 = composition(x, R2)
print('y2 = ', y2)
# >> y2 =  [[0.5599999999999999, 0.3599999999999999, 0.3599999999999999]]

Восстановим из полученных векторов $inline$ и $inline$ нечёткие множества с соответствующими им значениями вероятности:

y1 = [(y1[0][i], B[i][1]) for i in range(len(y1[0]))]
y2 = [(y2[0][i], C[i][1]) for i in range(len(y2[0]))]

Теперь у нас есть возможность посчитать индекс ранжирования для этих двух векторов и узнать приоритетного для сдачи игроком квеста NPC:

print('index = ', ranking_index(y1, y2))
# >> index =  -0.020000000000000018

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

А на сегодня всё.

Нечёткая математика. Отношения и волчьи хвосты