Гусев Л.А., Смирнова И.М. Размытые множества Теория и приложения (обзор) //Автоматика и телемеханика, 1973. - № 5. - С. 66-85.
УДК 519.5
РАЗМЫТЫЕ МНОЖЕСТВА
ТЕОРИЯ И ПРИЛОЖЕНИЯ
(Обзор)
Л. А. ГУСЕВ, И. М. СМИРНОВА
(Москва)
Излагаются основные понятия теории размытых множеств, разработанной Задэ и получившей развитие в ряде зарубежных работ. Приводится ряд определений теории размытых множеств, теории размытых языков и грамматик, размытых алгоритмов и автоматов. Описываются некоторые попытки применения методов теории размытых множеств к задачам теории управления, обучения, автоматической классификации.
Введение
В теории информации, лингвистике, в задачах обучения, автоматической классификации, принятия решений, построения систем управления в 'во многих иных областях имеет место ситуация, когда объекты исследования, условия задачи и цели не могут быть описаны точно. Неточность измерения и, как следствие, нечеткость описания реальных объектов является естественной; однако, несмотря да такую нечеткость, в реальных ситуациях обычно удается получать определенное представление об этих объектах и решать поставленные задачи.
Обычно неточность и неопределенность считаются статистическими,.
случайными характеристиками и учитываются при помощи методов теории вероятностей. В реальных же ситуациях источником неточности часто является не только наличие случайных величин, но и принципиальная невозможность оперировать точными данными вследствие сложности системы, неточности ограничений и целей. При этом в задачах появляются классы объектов, не имеющие четких границ; нечеткость таких классов выражается в том, что элемент может не только принадлежать или не принадлежать некоторому классу, но возможны также и промежуточные степени принадлежности.
В качестве примера таких классов можно привести класс натуральных
чисел, «значительно» превосходящих некоторое число 2У, или же класс действительных чисел, приближенно равных числу N. Оба эти класса, очевидно, не являются точно заданными множествами из-за наличия в их определениях терминов «значительно» и «приближенно». То же можно сказать о классе всех высоких, или молодых, или талантливых людей.
В работах [1—15] введены основные понятия, построены основы теории нечетких или размытых множеств (гнггу йо^а) и намечены основы
направления приложения этой теории.
В реальных ситуациях, особенно в проблемах классификации изображений, размытость является скорее правилом, чем исключением. Можло предполагать, что теория размытых множеств может быть применена в этих
66
^''"^^^^^««•ХВ.У.^Эрг-Я!'''»!"!"»^.)- -,1;^ .
ситуациях по меньшей мере так же, а может быть, более успешно, чем . методы, которые используются сейчас. Основные понятия и определения теории размытых множеств приводятся в следующем разделе.
1. Основные определения
Задэ определяет размытое множество как отображение множества Х на единичный интервал. Имеется в виду следующее.
Пусть Х — некоторое множество Х = {ж}. Размытое множество 8 на Х задается функцией принадлежности р,в : Х ->- [0,1], которая ставит в соответствие каждому х^Х действительное число в интервале [0, 1] *.
Число р,э (ж) называется степенью принадлежности х размытому множеству 8. Чем ближе значение р,в (х) к единице, тем выше степень принадлежности х к 8. Функция принадлежности является, очевидно, обобщением характеристической функции обычной теории множеств, принимающей лишь два значения: 1 для элементов, принадлежащих множеству, и 0 для элементов, не принадлежащих множеству 8. В случае дискретных множеств Х применяется запись размытого множества 8 как множества пар:
5-{(ж,^(ж))}.
Например, для класса чисел, значительно превосходящих число N == 10, может быть выбрана функция принадлежности
(ж-10)2 / Некоторые значения этой функции таковы:
МЮ) =0; ^(50) »0,6; ^(100) »0,9; М500) » I.
При этом размытое множество 8 может быть записано как множество пар:
5 ={..., (10; 0),..., (50,0,6)....,(100; 0,9)...., (500; 1),...}.
В общем случае выбор функции принадлежности ЦаО^) субъективен и основан на частичной информации, имеющейся в каждом отдельном случае (подробнее об этом см. в разделе 4). у '
Следующим шагом в построении теории размытых множеств является определение операций над размытыми множествами, аналогичных операциям для обычных («неразмытых») множеств; Вводимые операции, перечисленные ниже, с одной стороны, имеют общие черты с соответствующими операциями классической теории множеств, переходя в них в предельном случае, когда функция принадлежности принимает лишь два значения 0 и 1; с другой стороны, эти операции обладают определенной спецификой и, в известной степени, определены произвольно. Ниже приводятся определения основных операций над размытыми множествами.
Эквивалентность. Два размытых множества А и В эквивалентны (4 = В) тогда и только тогда, когда для всех х <= Х имеет место
|1д(ж) = Цв(д).
Включение. Размытое множество А содержится в размытом множестве 5, или, иначе, является подмножеством множества В (А <= В) тогда и только тогда, когда для всех х<=Х имеет место ^(.х) ^ р,в(ж).
Например, размытое множество А всех целых чисел, значительно превосходящих число 10, функция принадлежности которого определена выражением (1.1), содержится в множестве В (является подмножеством множества В) целых чисел, значительно превосходящих 1, функция ^в(а") ко-
* Гоген в 1966 г. расширил понятие размытого множества, введя более общее понятие—Ь-размытое множество, для которого [Хе : Х-»-2<, причем интервал Ь может быть отличен от [0,1] (см. [16—18]),
5* Ш
торого задана выражением
-I
,1.2) ^)-(1+^^)'
10
Очевидно, что \1л(х) ^ ^в(х). _ Дополнение. Размытое множество 8 является дополнением размытого
множества 8, если |Аа (ж) == 1 — ^а (ж).
Например, для множества В из предыдущего примера дополнением будет множество В чисел, не отличающихся значительно от единицы, для
которого
(/у _ -П2 \-1
(1.3) ^(х)= ^+{х-^ •
Для определения следующих двух основных операций объединения и пересечения используется характерная для теории размытых множеств
операция отыскания максимума или минимума.
Объединение. Объединение Л и В двух размытых множеств А и В определяется как наименьшее размытое множество, содержащее оба множества А и В. Функция принадлежности множества А и В определяется
выражением (1.4) ^Аив(ж) ==тах (^(ж), ^в(ж)).
Пересечение. Пересечение А П В двух размытых множеств А и В определяется как наибольшее размытое множество, являющееся одновременно подмножеством обоих этих множеств. Функция принадлежности множества
А П В выражается формулой
' \ —— /" (т\ ^(х}}.
(1.5)
Ц'Апд(ж) ==тш (р,А(а;),р,в(ж)).
•Часто используется
также сокращенная запись
^лив(ж)
= (Ал(-с) V ^в(ж), ^Апв(а-) = ил (ж) Д ив (ж),
(1.6)
где вместо 'операторов шах и наш вводятся соответственно символы
УиЛ*.
В работе [19] формулы (1.4) и (1.5) для объединения и пересечения
размытых множеств обоснованы следующими соображениями.
Множества А I) В, А П В должны определяться только через исходные
множества А и В. Это означает, что функции принадлежности илив(ж),
.^лг[в(,х) зависят только от \Ил(х) и Цв(ж), т. е. ' - '•'-. /^\ „,(т\\
(1.7)
\^А[\в{Х) —— ^\\ЛА\Л1, у.ы\~, 1 .
Относительно функций / и § делаются следующие естественные предположения:
1. У и § — неубывающие функции своих аргументов.
2. / и § симметричны, т. е. /(аг,у) ==/(у,ж) и §(х, у} =2 §(у,х). ^
3. Да;, ж) и ё{х,х) —строго возрастающие функции х.
4. Дж, у) ^ тш (ж, у) и ^(ж, у) ^ тах (ж, у).
5.Д1,1)=1, ^(0,0)=0.
6. Логически эквивалентные выражения должны иметь одинаковые
функции принадлежности, например
«
[ААп(вис) \х) = (1(Апв)и(Апс)(-с).
* Встречаются также обозначения П иц (см., например, [18]).
68
При этих предположениях, естественность которых иллюстрируется примерами, операции (1.4) и (1.5) определяются однозначно. В предельном случае, когда функции принадлежности р,л и [Ав принимают лишь значения 0 и 1 (т. е. множества 4 и В не являются размытыми), формулы (1.4) и (1.5) совпадают с обычными теоретико-множественными операциями объединения и пересечения.
В [19] показано, что операция дополнения при сделанных выше предположениях относительно функции принадлежности и некоторых дополнительных предположениях о характере самой операции не является столь же хорошо аргументированной и выбор этой функции, вообще говоря, произволен.
Алгебраическое произведение АВ размытых множеств А и В определяется следующим образом:
(1.8) р-Ав(ж) = (АА(ж)-|Ад(а;).
Для алгебраической суммы А® В функция принадлежности выражается формулой
ц.А®в(ж) = [1А(ж) + ^в(ж) — и,А(а;)р,в(а:).
Размытое множество А называется выпуклым, если для любой пары элементов из Х функция принадлежности р,л(ж) удовлетворяет условию
М^+ (1-^)у) >тт(цА(ж),1АА(у)) (О^Х^1).
Размытое множество называется вогнутым, если выпукло его дополнение.
В [15] дается определение понятия центральной тени размытого множества. Пусть рй и Я — соответственно точка и гиперплоскость в Е", а Ь — прямая, проходящая через ро и пересекающая Н в точке х. Центральная тень размытого множества А на гиперплоскость Я есть размытое множество на Я, функция принадлежности которого [ан (ж) определяется следующим образом:
(1.9) ^ы(ж)==тах(АА(г/), же Я,
цн(ж)=0, хФН.
Частным случаем центральной тени является ортогональная тень, т. е. центральная тень для случая, когда точка ра удалена от гиперплоскости Я на бесконечное расстояние.
В [15] рассматриваются тени объединения и пересечения размытых множеств, устанавливается инвариантность свойства выпуклости размытого множества при проецировании, решается задача определения размытого множества по совокупности его теней.
В теории конечных автоматов, алгоритмов, языков и грамматик имеет большое значение операция отношения. В основе размытых аналогов этих объектов лежит операция размытого отношения двух или более размытых множеств.
Понятие размытого отношения введено в работе [8]. Размытое п-арное отношение Н в пространстве X» Х Ха X.. .X Х„ есть размытое множество и == {(а-1, Жг,..., а;„), р,н(ж1, Жг,..., ж»)}, ж,. е X», Хг е Ха,..., ж„ е Х„, кото^-рое характеризуется функцией п переменных и,в, ассоциирующей каждой упорядоченной . га-ке (жц Жа,..., Хц) степень ее принадлежности Р-в (а"1, а;г,.,., ж„) множеству Д.
Пример. Пус'я> Х = У == Е1 — множество точек действительной прямой. Тогда К == {{х, у, (Ад (ж, у)) \х > у} будет размытым отношением в плоскости Х Х У == Е2. Функция принадлежности, характеризующая это мно-
жество, может быть выбрана, например, так:
/ 10 \-* „ * (1.10) ^(а;.у)=^1+. _ .) приа;>у, у^О,
^в(ж, у) ==0приа;< у.
Поскольку размытые отношения являются размытыми множествами, для них могут быть определены соответствующие операции дополнения,
объединения, пересечения и т. д.
При рассмотрении размытых конечных автоматов и грамматик существенно используется операция произведения или композиции А ° В двух отношении А и В [8, 20]. Пусть А и В—бинарные отношения в пространстве XXX. 'Композиция А" В определяется как размытое отношение в Х Х X, функция принадлежности которого может быть выражена через функции принадлежности каждого из отношений А и В следующим образом *:
<1.11) ^Аов(ж<,а:э)==тах1шп(р,А(а:„у), (Ав(у,Ж1)), У^Х,
V
(1.12) ЦА.в(Я(,ж,)=тш1аах(|АА(а;<,у),Цв(у,а;э)), у <= X.
V
Первое из этих определений дано Задэ в [8], второе—в работе [20]. Они используются равноправно для построения различных типов автоматов и грамматик [18, 20, 211. В случае, когда в основу построения тех или иных объектов кладется операция композиции ", т. е. операция «максими-на», соответствующие объекты называют иногда «пессимистическими»;
если же за основу берется операция «минимакса», объекты называют
«оптимистическими» (см., например, [21—23]).
В [18] вводится понятие уровневого множества, которое используется
для установления связи между размытыми и неразмытыми множествами
при изучении размытых грамматик и автоматов.
Пусть А — размытое множество на множестве X. Для параметра
\е [0,1] определяется ^-уровневое множество А\ как неразмытое множество, включающее все те элементы множества X, степень принадлежности которых множеству А больше или равна ^, т. е. а). = [х\ [ла^) > К}. Множества а), образуют вложенную систему подмножеств множества X, при-
чем К ^ К' -ч- 4». с Лу.
Показано, что размытое множество А может быть записано в форме
(1.13) Д=и?.А. (0<Х<1),
>,
где под произведением ка), понимается приписывание степени принадлежности Х каждому элементу неразмытого множества Ли.
Введение понятия размытого множества и формализация основных операций на языке размытых множеств приводит естественным образом к идее обобщения классической теории множеств для размытых множеств. Возникает задача: найти «размытые» аналоги теорем классической теории множеств. Ряд работ посвящен развитию алгебраических аспектов теории размытых множеств ,(см. [8, 16, 18—24]), соотношениям между алгеброй размытых множеств и классической алгеброй множеств, а также некоторым вопросам топологии размытых пространств [25, 26].
В [27] изучается размытое бинарное отношение Д на XXX, которое
является рефлексивным и симметричным:
/- -\ — 1 „,/г 7^ == ив(.у,а:), х,уб=Х.
уи^уА^/л.*.-^.-^——__ .
\лк{х, х) " 1, ^д(а;, у) = р,в(у, х), х, у е X.
* Более общими являются выражения (см., например, [20]);
р.аов (.я, X)) = зир 1шп(щ {жг, у}, р,а ({/, X)}), у<==Х, »
Щ*д (.Я, X)) «в= 1п! шах (р.а (ая, у), Ив (у, а<)), У 1= X.
» . '
70
-арная композиция этого отношения определяется путем повторяого денения выражения (1.11)
Цй~.д.'Г.Тй (а", У) == И в» (а;» У) = шах тш (Ря (ж, .Г!), (ай (Ж1, а-а), ...
•——^— х„я„.„..х„
...,(Ан(а;п-г,у)).
Из цепочки неравенств 0 ^ Цд < р,я2 < ... ^ 1 следует существование едела
|1.14) Мп(х,у)^Ит^(х,у).
р^ ' ' п-»-со
1 В [28] изучается отношение Мц{х, у)\ в частности показано, что уров-
рвевое множество {(х,у) \Мц(х,у) ^ К} определяет отношение Л», (не раз-
рсйтое!), являющееся отношением эквивалентности.
В работе [18] отношения эквивалентности, подобия,, упорядочивания юбщаются для размытых множеств. Основное содержание работы состав-ввт исследование размытых отношений подобия и упорядочивания, кото-не являются размытыми транзитивными отношениями., Работы [29, 30] являются теоретическими работами, посвященными
Изучению размытой логики. По аналогии со степенью принадлежности,
|в размытой логике вводится истинностная функция
|1Л5) Г(4)е[0,1],
|где А — элемент множества высказываний 8. Делаются сопоставления раз-|мытой и обычной (не размытой) логик, исследуются вопросы выводимости |й непротиворечивости в размытой логике. В [29] доказывается важная Цгворема, позволяющая делать оценку истинностной функции следствия, | исходя из величин истинностных функций аксиом. | Работа [31] также связана с исследованием размытой логики, но носит |<>олее прикладной характер.
I В [32] рассматриваются размытые множества, зависящие от времени. ^Исследуются некоторые вопросы топологии и проектирования таких множеств, изучаются зависящие от времени отношения, по-видимому, представляющие Интерес в задачах автоматической классификации и планирования. '