close

Вход

Забыли?

вход по аккаунту

?

Исследование свойств отношений нечеткой близости объектов в информационных интеллектуальных системах.

код для вставкиСкачать
УДК 681.3
Ю.В. УЛЬЯНОВСКАЯ
ИССЛЕДОВАНИЕ СВОЙСТВ ОТНОШЕНИЙ НЕЧЕТКОЙ
БЛИЗОСТИ ОБЪЕКТОВ В ИНФОРМАЦИОННЫХ
ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ
Рассматриваются нечеткие отношения близости объектов на основе нечеткой близости, нечеткого включения и нечеткой общности ситуаций для проведения идентификации в
интеллектуальных системах c учетом возможности изменения информации об объектах во
времени. Для каждого отношения исследуются его свойства. На основе проведенных исследований делается вывод о типе отношения.
1. Актуальность задачи
В основе работ большинства систем искусственного интеллекта заложены знания экспертов, которые формализуются с помощью методов инженерии знаний. При первоначальном формировании базы знаний очень важным является вопрос о методах получения и
обработки экспертной информации, характер которой влияет на выбор модели представления знаний, метода обработки и формализации знаний и на структуру базы знаний в целом.
Процесс получения знаний от экспертов включает несколько этапов: подбор экспертов, их
опрос, обработка экспертных оценок. Экспертную оценку объектов можно рассматривать
как процесс получения экспертной информации с помощью измерений. Сами объекты при
этом могут быть описаны с помощью как качественных, так и количественных данных.
Для принятия решений в системах искусственного интеллекта при идентификации объектов
важно не только сравнивать их между собой, но и знать, во сколько раз и на сколько
условных единиц один объект предпочтительнее другого [1]. Решение этой задачи выполняется путем применения того или иного метода получения качественных или количественных оценок. При этом необходимо не только получить экспертную оценку, но и
провести ранжирование альтернатив, разбиение их на классы эквивалентности, определить
сравнительную предпочтительность альтернатив путем построения отношений на их множестве. Это порождает задачу проверки таких свойств как транзитивность, симметричность и других свойств отношений. В зависимости от этого на множестве альтернатив
могут быть заданы отношения различных типов [2].
2. Основные направления исследований
Решение сформулированной выше задачи происходит в нескольких направлениях. Экспертная информация о большинстве предметных областей является совокупностью качественных и количественных оценок и характеризуется неполнотой и нечеткостью. Если
оценки эксперта носят качественный характер, то для описания связей применяются
отношения линейного или частичного порядка, эквивалентности, толерантности, а иногда и
произвольные отношения, не обладающие такими свойствами, как связность, транзитивность и т.д. Если экспертная информация содержит количественные оценки, используются
метризованные отношения соответствующего типа [2]. В работе [3] рассматриваются
81
методы обработки экспертной информации для определения степени близости объектов в
зависимости от ее типа. Для количественной экспертной информации проведен анализ мер
близости в зависимости от типа шкалы, в которой проводились измерения. Для качественной информации проведен анализ степеней нечеткой близости ситуаций и построены отношения нечеткого включения, нечеткого равенства и нечеткой общности с учетом изменения информации.
Целью данной работы является исследование свойств отношений нечеткой близости
объектов, а именно нечеткого включения, нечеткого равенства и нечеткой общности с
учетом изменения информации об объектах во времени и определение типов указанных
отношений.
3. Исследование свойств отношений нечеткой близости объектов
Предметные области, с которыми работают экспертные системы, весьма разнообразны. Полностью описать факты, правила и взаимосвязи в предметной области не всегда
возможно. Это порождает проблему неполноты и неточности данных. При использовании в
описании качественных характеристик возникает необходимость в обработке нечетких
данных с применением лингвистических переменных. Решение сформулированных задач
возможно с помощью аппарата нечетких множеств. Пусть х – объект, оцениваемый
экспертами, описывается совокупностью признаков Ξ = {ξ1 , ξ 2 ,..., ξ n } . Пусть признаки
ξi ∈ Ξ относятся к одному из трех типов: числовому, булевому или лингвистическому.
Каждый лингвистический атрибут ξ i , (i ∈ I = {1,..., N}) описывается соответствующей
лингвистической переменной
ξi , Ξ i , D i , где
Ξ i = {ξi1 , ξi2 ,..., ξin } - терм-множество линг-
вистической переменной ξ i (набор лингвистических значений признака), m i – число
значений признака, D i – базовое множество признака ξ i . Для описания термов
ξ ij ( j ∈ L = {1,2,..., m i }) , соответствующих значениям признака ξ i , используются нечеткие
~
~
i
переменные 〈 ξij , Di , Cij 〉 , т.е. значение ξ j описывается нечетким множеством C ij в базо~
вом множестве D i : Cij = {〈µ i (d ) / d〉} , d ∈ D i . Таким образом, в терминах теории нечетких
C
множеств каждый объект x ∈j X можно представить в виде:
x = {〈µ x (ξi ) / ξi 〉} , ξi ∈ Ξ ,
(1)
где µ x (ξ i ) = {〈µ µ x (ξi ) (ξ ij ) / ξ ij 〉} , j∈ L , i ∈ I . Для признаков ξ i булевого типа µ x (ξi ) ∈ {0;1} .
Признаки ξ i могут изменяться во времени постепенно либо скачкообразно [3]. Учитывая это, введем коэффициент t i , характеризующий изменения во времени значения ξ i -го
признака. В связи с этим каждый признак охарактеризуем следующими параметрами:
µ x (ξij ) – функция принадлежности, которая показывает, в какой мере значение ξ ij признака
ξ i характеризует объект х; t i – коэффициент изменения во времени значения ξ i -го
признака.
Как отмечалось выше, одной из задач, которые решают экспертные системы, является
задача идентификации, при решении которой необходимо определить степень близости
объектов. Пусть системе необходимо идентифицировать объект у через определение
степени его близости к объекту х, хранящемуся в базе знаний экспертной системы.
Предположим, что все признаки, которые характеризуют идентифицируемые объекты x и
y, являются хорошо определенными. Признак ξi считается плохо определенным для х,
i
j
если ∃ ξ j ∈ Ξ i : µ µ x ( ξi ) (ξ i ) ∈ (1 − T, T ) , где Т – некоторый порог значимости [2]. Данное
утверждение имеет смысл при Т ≥ 0,5.
Результатом сравнения объектов между собой может быть их полное или частичное
совпадение. В зависимости от количества совпадающих признаков между объектами
выполняется отношение нечеткого равенства, нечеткого включения и нечеткой общности.
Учитывая, что признаки, на основании которых проводятся сравнения объектов, могут
82
изменяться во времени, достоверность идентификации снижается. Может возникнуть две
ситуации. В первом случае значение всех признаков определены, при этом они могут
совпадать либо полностью, либо частично. Во втором случае часть признаков может быть
не определена. Рассмотрим первый случай. Степень нечеткой близости объектов определим через степень нечеткого равенства µ( x , y) , при этом равенство ξi признака определим через степень равенства его значений:
µ( x , y) = µ(µ ~x (ξ i ), µ ~y (ξ i )) = &
(µ µ x ( ξi ) (ξ ij ) ↔ µ µ y ( ξi ) (ξ ij )) .
i
ξ j∈ξ i
(2)
Учитывая коэффициент изменения во времени t i , степень нечеткого равенства объектов вычислим следующим образом [3]:
µ( x , y) = & µ(µ ~x (ξ i ), µ ~y (ξ i )) = & µ(min{1 − t i , µ ~x (ξ i )}, µ ~y (ξ i )) .
ξ i ∈Ξ
ξi ∈Ξ
(3)
Если ∃ξ i : 0 < t i , то степень достоверности определения меры сходства принимается
равной минимальной степени достоверности равенства изменяющихся признаков, которая
в свою очередь определяется при помощи коэффициента t i изменения признака ξ i во
времени.
Определяя таким образом степень равенства ситуаций х и y, ненулевое значение
функции принадлежности µ( x , y) получим в том случае, когда будут совпадать все
значения атрибутов булевого типа.
Пусть при сравнении объектов х и y часть признаков не равны между собой. Через q
обозначим количество нечетко неравных признаков. В этом случае степень нечеткой
близости определим через нечеткую (n-q) общность k n − q ( x , y) следующим образом:
k n −q ( x , y) = & Q µ(min{1 − t i , µ ~x (ξ i )}, µ ~y (ξ i )) ,
ξi ∈Ξ \ Ξ
(4)
Q
| Ξ Q |≤ q , ξ k ∈ Ξ ⇔ µ(µ x (ξ k ), µ y (ξ k )) ≤ R , где R – некоторое пороговое, наперед заданное
значение: R ∈ [0;1] .
При определении (n-q) общности х и y не учитываем признаки, значения которых
нечетко не равны для х и y. При Ξ Q = 0 объекты нечетко равны.
Рассмотрим второй случай. Пусть значения части признаков объекта y не определены.
Тогда число признаков, описывающих x , больше, чем число признаков, характеризующих
y . Воспользуемся формулой нечеткого включения:
ν( y, x ) = & ν(µ ~y (ξ i ), µ ~x (ξ i )) ,
ξi ∈Ξ
где ν(µ ~y (ξi ), µ ~x (ξi )) =
& (µ
ξij∈ ξi
µ y ( ξi )
(5)
(ξij ) → µ µx (ξi ) (ξij )) и является степенью включения не-
четного множества µ y (ξi ) в нечетное множество µ x (ξi ) . Учитывая изменение признака во
времени, формула (5) принимает вид
ν ( y, x ) = & ν (µ ~y (ξ i ), min{1 − t i , µ ~x (ξ i )) .
ξ i ∈Ξ
(6)
Будем предполагать, что объекты нечетко близки, если соответствующая мера близости больше некоторого порогового значения Т. Введенные выше меры близости для
объектов с изменяющимися признаками могут быть рассмотрены как нечеткие отношения. Как и для четких отношений, тип нечеткого отношения определяется совокупностью
его свойств. К основным свойствам отношений относятся свойства рефлексивности, антирефлексивности, симметричности, несимметричности, антисимметричности, транзитивности, связности. Основными типами отношений являются отношения порядка, толерантности, эквивалентности, доминирования. Для нечетких отношений вводится понятие степени,
отражающее их нечеткость.
83
( ~)
~ = Х, F . В работе [2] вводятся следуюПусть дано произвольное нечеткое отношение ϕ
щие определения степени отношений.
~)
Степенью рефлексивности α(ϕ
ref называется величина, определяемая выражением
( )
~ = Х, ~
Отношение ϕ
F
~) = & µ x, x
α (ϕ
ref
F
.
x∈ X
(7)
~ ) ≥0,5 , нечетко
называется нечетко рефлексивным, если α(ϕ
ref
~ ) = 0,5 , то отношение ϕ
~ называется реф~ ) ≤0,5 . Если α(ϕ
нерефлексивным, если α(ϕ
ref
ref
лексивно индифферентным.
Степенью антирефлексивности называется величина
~ ) = & (¬µ x , x ) = ¬ ( ∨ µ x , x )
β(ϕ
ref
F
F
.
x∈ X
x∈ X
(8)
~ называется нечетко антирефлексивным, если β(ϕ
~)
Отношение ϕ
ref ≥ 0,5, и нечетко
~
~
неантирефлексивным, если β(ϕ) ref ≤ 0,5. При β(ϕ) ref =0,5 оно антирефлексивно индифферентно.
~
Степенью симметричности α(ϕ) sym называется величина
(
)
~)
α (ϕ
sym = & µ F x , y ↔ µ F y, x .
x∈ X
x ≠y
~
~ называется нечетко симметричным, если α(ϕ)
Отношение ϕ
sym ≥ 0,5, и нечетко несим~
~
метричным, если α(ϕ) sym ≤ 0,5. При α(ϕ) sym =0,5 – симметрично индифферентным.
~)
Степенью антиссимеричности β(ϕ
называется величина
sym
~
(9)
β(ϕ) sym = & ¬(µ F x, y & µ F y, x ) .
x , y∈ X
x ≠y
~ называется нечетко антисимметричным, если β(ϕ
~)
Отношение ϕ
sym ≥ 0,5, и нечетко
~
~
~
(
)
β
ϕ
неасимметричным, если
sym ≤ 0,5. В случае, если β(ϕ)sym =0,5, отношение ϕ называется
антисимметрично индифферентным.
~ называется величина
~ ) отношения ϕ
Степенью транзитивности α(ϕ
tr
~) =
α (ϕ
tr
⎛⎛
⎜ ⎜⎜∨ (µ F x , y & µ F y, z ) → µ F x , z
x , y, z∈ X⎜⎝ ⎝ y
&
x ≠ y ≠z
⎞⎞
⎟⎟ ⎟⎟
⎠⎠
(10)
~ называется нечетко транзитивным, если α (ϕ
~)
Отношение ϕ
tr ≥ 0,5, нечетко нетранзи~
~ ) =0,5.
тивным, если α(ϕ) tr ≤ 0,5, транзитивно индифферентным, если α(ϕ
tr
Пусть X = {~x1, ~x 2 ,..., ~x N } есть некоторое множество типовых ситуаций. Покажем, что
~
~
отношение нечеткого включения δ = (X, F) является отношением нечеткого нестрогого
порядка, т.е. является рефлексивным, антисимметричным и транзитивным. При этом
~
F=
µ
F
~
xi , ~
xj / ~
xi , ~
xj
является отношением нечеткого включения, µ ~x i , ~x j = ν ~x i , ~x j ,
F
ν ~
xi , ~
xj
определяется выражением (6).
~
~
~
Для доказательства достаточно показать, что α (δ )ref & β(δ )sym & α (δ )tr ≥0,5 или, с уче~
том вида отношения δ
~
~
~
α (δ )ref & β(δ )sym & α (δ )tr ≥Т .
~
(11)
Покажем, что α (δ )ref ≥Т . С учетом выражений (5) и (7) необходимо показать, что ∀ ~х ∈ Х
справедливо ν (~х , ~х ) ≥Т . С учетом выражения способа определения нечеткого включения
( ( )
{(
) ( )}) .
х, ~
х ) = & ν µ x ξi , min 1 - t i , µ x ξi
можем записать: ν (~
ξi ∈ Ξ
84
( ( ) ( ))
Необходимо показать, что & ν µ x ξ i , µ x ξ i ≥Т . С учетом (1) и (2) требуется
ξ i∈ Ξ
показать, что ∀ξ j ∈ ξi :
i
¬µ µ x (ξi ) (ξ ij ) ∨ min{1 - t i , µ µ x (ξi ) (ξ ij )} ≥Т .
(12)
Пусть t i ≥ T , тогда 1 − t i ≤ T . По условию хорошо определенной ситуации
µ µ x (ξi ) (ξ ij ) < 1 − Т , или µ µ x (ξi ) (ξ ij ) > Т . Если µ µ x (ξi ) (ξ ij ) < 1 − Т , то ¬µ µ x (ξi ) (ξ ij ) > Т и нераi
i
венство (12) выполняется. Если µ µ x (ξi ) (ξ j ) > Т , то ¬µ µ x (ξi ) (ξ j ) < Т и неравенство не
выполняется.
i
i
Пусть t i ≤ T , тогда 1 − t i ≥ T . Если µ µ x (ξi ) (ξ j ) < 1 − Т , то ¬µ µ x (ξi ) (ξ j ) > Т и неравенство
i
(12) выполняется благодаря левой части дизъюнкции. Если µ µ x (ξi ) (ξ j ) > Т ,
i
i
то ¬µ µ x (ξi ) (ξ j ) < 1 − Т а min{1 − t i , µ µ x (ξi ) (ξ j )} ≥ Т и неравенство выполняется благодаря
правой части. Таким образом, неравенство (10) выполняется, когда t i ≤ T при любом
~
значении µ x (ξi ) , либо когда t i ≥ T и µ x (ξi ) ≤ 1 − T . Неравенство α δ ref ≥ Т доказано. Тем
самым доказано, что отношение нечеткого включения является рефлексивным при t i ≤ T
или при t i ≥ T и µ x (ξi ) ≤ 1 − T .
()
Докажем,
~
β( δ )sym =
&
x i , x j ∈X
xi ≠ x j
что
(
()
~
β δ sym ≥ Т .
В
соответствии
)
~
¬ µ F x i , x j & µ F x j , x i , или β( δ )sym =
((
&
x i , x j∈X
xi ≠x j
с
выражением
(
)
¬ ν x i , x j & ν x j , x i , т.е. не-
) )
обходимо показать, что ∀ xi,xj: xi,xj ∈ X, xi ≠ xj ¬ ν x i , x j & ν x j , x i ≥ T .
((
Неравенство ¬ ν x i , x j & ν x j , x i
(7)
) ≥ T ) эквивалентно (ν x , x
i
j
)
& ν x j , x i ≤ 1 − T . По-
скольку при определении выражения (6) предполагалось, что (∀~x i , ~x j ∈ X) , имеет место
xi и ~
xi ⊆ ~
x j ) → (~
xi ⊄ ~
x j )) . Иначе ~
утверждение ((i ≠ j & ~
x j нужно воспринимать как одну
ситуацию. Отсюда следует, что если ν x i , x j ≥ T , то ν x j , x i ≤ 1 − T , и наоборот. Следова-
(
)
тельно, можем сделать вывод, что неравенство ν x i , x j & ν x j , x i ≤ 1 − T выполняется всегда.
(~ )tr ≥ Т .
Докажем, что α δ
~
Аналогично проведенным выше доказательствам с учетом
вида отношения δ необходимо показать, что ∀ x,y ∈ X, x ≠ y, ∃ z ∈ X: x ≠ z, z ≠ y, для которого (ν x , y ≥ T & ν y, z ≥ T ) → ν x , z ≥ T .
Выражение (ν x, y ≥ T & ν y, z ≥ T ) эквивалентно выражению (ν x, y & ν y, z ) ≥ T . С учетом (5) и (6) последнее неравенство имеет вид
(µ x (ξi ) → min{(1 − t i ), µ y (ξi )})& (µ y (ξi ) → min{(1 − t i ), µ z (ξi )}) ≥ T .
(13).
Проведя рассуждения, аналогичные доказательству рефлексивности, получим, что данное неравенство, а вместе с ним и нечеткая транзитивность выполняется, если t i ≤ T и
µ x (ξi ) ≤ 1 − T , либо если t i ≥ T и µ x (ξi ) ≤ 1 − T .
Учитывая, ограничения, при которых отношение удовлетворяет свойству рефлексивнос~
~
ти, можем сделать вывод, что отношение нечеткого включения δ = (Х, F) является отношением нечеткого нестрогого порядка при t i ≤ T и µ x (ξi ) ≤ 1 − T .
( )
~ = S, ~
Нечеткое отношение ϕ
F , где
85
{
~
F= µ
F
},
~
xi , ~
xj / ~
xi , ~
xj
(14)
~ ~
~ ~
является отношением нечеткого равенства, если µ F x i , x j = µ x i , x j .
( )
~ = Х, ~
Покажем, что отношение нечеткого равенства ϕ
F является отношением нечеткой
{
~
эквивалентности. При этом F = µ ~x i , ~x j / ~x i , ~x j
F
} является отношением нечеткого равен-
ства, если µ F ~x i , ~x j = µ ~x i , ~x j , µ ~x i , ~x j определяется выражениями (2),(3).
Отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Для доказательства нечеткой эквивалентности необходимо доказать,
~
~
~
~
что α(ϕ)ref & α(ϕ)sym & α(ϕ)tr ≥ 0,5 или, с учетом вида отношения ϕ
~ ) & α(ϕ
~)
~
α(ϕ
ref
sym & α (ϕ)tr ≥ T .
(15)
~) ≥ T
~ можем запи. С учетом выражений (7) и вида отношения ϕ
Покажем, что α(ϕ
ref
~ ) = & µ( x , x ) . Необходимо показать, что ∀~
х ∈ Х справедливо µ(~
сать, что α(ϕ
х, ~
х) ≥ T . С
ref
~
x∈X
~
~
µ(min{(1 − t ), µ (ξ )}, µ (ξ ))
учетом способа определения нечеткого равенства µ( х , х ) =
&
ξi∈Ξ
i
x
i
х
i
необходимо показать & µ(min{(1 − t i ), µ x (ξi )}, µ х (ξi )) ≥ T . Это эквивалентно утверждению,
ξ i ∈Ξ
что ( ∀ξ ∈ ξi ):
i
j
(¬ min((1 − t i ), µ µ x (ξi ) (ξ ij )) ∨ µ µ х (ξi ) (ξ ij )) ∧ (min((1 − t i ), µ µ x (ξi ) (ξ ij )) ∨ ¬µ µ х (ξi ) (ξ ij )) ≥ T .(16)
(~ )
Неравенство (16) выполняется при µ µ х (ξi ) (ξij ) ≤ 1-Т. Таким образом, α δ ref ≥ T при
любом ti и µ µ х (ξ i ) (ξij ) ≤ 1 − T .
~
Проверим выполнение неравенства α(ϕ)sym ≥ T . Учитывая (10), имеем
~)
α (ϕ
sym = & (¬µ F x , y ∨ µ F y, x ) = &
x , y∈X
x≠y
x , y∈X
x≠y
(¬µ(х, у) ∨ µ( у, х ))
.
Необходимо, чтобы ¬µ( х , у) ∨ µ( у, х ) ≥ T . Последнее неравенство выполняется для любых t i .
(~ )
Аналогично доказывается, что α δ tr ≥ T . Это доказывает, что отношение (2), где µ
определяется выражением (3), является отношением эквивалентности при ограничениях на
t i . Необходимо отметить, что если Т=0,5, то рассмотренные выше ограничения на t i
снимаются.
Рассмотрим отношение нечеткой общности ситуаций. Нечеткое отношение называется
xi , ~
x j = k n - q (~
xi , ~
x j ), где ~x i , ~x j ∈ X . Поскольку
отношением (n-q)- общности, если µ ~F ~
∀~
xi , ~
xj ∈X :µ
~
xi , ~
x j ≤k n - q (~
xi , ~
x j ), то α(~τ ) ref ≥ α(ϕ~ ) ref и α(~τ )sym ≥ α(ϕ~ )sym , где ϕ~ -отноше-
ние нечеткого равенства, можем сделать вывод, что α(~τ ) ref ≥ T , α(~τ )sym ≥ T . Это в свою
~
очередь обозначает, что отношение τ = (S, F) является нечетко рефлексивным и нечетко
~
симметричным, степень толерантности α(~τ ) ref & α(~τ )sym ≥ T и τ = (S, F) является отношением нечеткой толерантности.
Выводы
Проанализированы свойства отношений нечеткой близости объектов. Показано, что при
определенных ограничениях на параметр ti отношение нечеткого включения является
отношением нечеткого нестрогого порядка. Это дает возможность решить поставленную
задачу идентификации объектов путем организации на множестве Х иерархии типовых
86
объектов. Для разбиения множества Х на классы нечеткой эквивалентности необходимо
~ = ( Х, ~
применить к объектам множества Х отношение нечеткого равенства ϕ
F) , которое,
как было показано в работе, является отношением нечеткой эквивалентности при ограничениях на ti. При этом в один класс будут входить нечетко равные между собой объекты,
которые, с учетом порога Т, можно считать одним объектом. Для полного описания
объектов необходимо не только знать их признаки, но и выбрать соответствующую шкалу
для их измерения. Поскольку между основными типами шкал и отношениями существует
непосредственная связь, перспективным является построение шкал с учетом типов отношений в рассматриваемой предметной области.
Список литературы: 1. Ульяновська Ю. Аналіз основних аспектів побудови інтелектуальної автоматизованої системи ідентифікації творів мистецтва // Вісник Академії митної служби України. 2002. №1. С.
70-74. 2. Литвак Б.Г. Экспертная информация. Методы получения и анализа. М.: Радио и связь, 1982.
184 с. 3. Мороз Б.И., Ульяновская Ю.В. Анализ мер близости объектов для различных типов экспертной
информации // АСУ и приборы автоматики. 2008. Вып 144. С. 194-198.
Поступила в редколлегию 22.05.2011
Ульяновская Юлия Викторовна, доцент кафедры информационных систем и технологий
Академии таможенной службы Украины. Научные интересы: экспертные системы, методы работы с нечеткими данными, экспертные оценки. Адрес: Украина, 49000, Днепропетровск, ул. Рогалёва, 8, тел.: (0562) 45-21-68.
87
Документ
Категория
Без категории
Просмотров
6
Размер файла
450 Кб
Теги
нечеткой, интеллектуальной, информационные, объектов, система, отношений, свойства, близость, исследование
1/--страниц
Пожаловаться на содержимое документа