Метод нечеткой кластеризации
Рассматривается метод нечеткой кластеризации при условии, что дополнение нечеткого отношения сходства является метрикой. На базе введения понятий пороговой нормы и пороговой конормы решается задача разбиения исследуемого множества на непересекающиеся кластеры. Предлагаемый метод отличается от методо...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84593 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Метод нечеткой кластеризации / И.И. Рясная // Компьютерная математика: сб. науч. тр. — 2010. — № 2. — С. 113-123. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859915086333739008 |
|---|---|
| author | Рясная, И.И. |
| author_facet | Рясная, И.И. |
| citation_txt | Метод нечеткой кластеризации / И.И. Рясная // Компьютерная математика: сб. науч. тр. — 2010. — № 2. — С. 113-123. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Рассматривается метод нечеткой кластеризации при условии, что дополнение нечеткого отношения сходства является метрикой. На базе введения понятий пороговой нормы и пороговой конормы решается задача разбиения исследуемого множества на непересекающиеся кластеры. Предлагаемый метод отличается от методов кластеризации, использующих нечеткое отношение эквивалентности, тем, что позволяет создавать более быстрые алгоритмы построения кластеров.
Розглянуто метод нечіткої кластеризації за умови, що доповнення нечіткого відношення схожості є метрикою. На основі введення понять норм та конорм з порогом розв’язується задача розбиття множини, що досліджується, на кластери, які не перетинаються. Запропонований метод відрізняється від методів, що використовують нечітке відношення еквівалентності тим, що дозволяє створювати більш швидкі алгоритми для побудови кластерів.
The method of fuzzy clustering is examined under the condition that a complement of fuzzy similarity relation is a metric. On the basis of definition of concepts of threshold norm and threshold conorm, the problem of set partitioning on nonintersecting clusters is solved. The method proposed differs from the methods using the fuzzy equivalence relation by the fact that it allows to create faster algorithms of construction of clusters.
|
| first_indexed | 2025-12-07T16:04:52Z |
| format | Article |
| fulltext |
113
Рассматривается метод нечет-
кой кластеризации при условии,
что дополнение нечеткого отно-
шения сходства является метри-
кой. На базе введения понятий по-
роговой нормы и пороговой конор-
мы решается задача разбиения
исследуемого множества на не-
пересекающиеся кластеры. Пред-
лагаемый метод отличается от
методов кластеризации, исполь-
зующих нечеткое отношение эк-
вивалентности, тем, что позволя-
ет создавать более быстрые алго-
ритмы построения кластеров.
И.И. Рясная, 2010
ÓÄÊ 519.8
È.È. ÐßÑÍÀß
ÌÅÒÎÄ ÍÅ×ÅÒÊÎÉ ÊËÀÑÒÅÐÈÇÀÖÈÈ
Введение. Методы нечеткой кластеризации с
использованием аппроксимационного под-
хода при условии, что дополнение нечеткого
отношения сходства является метрикой на
исследуемом конечном множестве, рассмат-
риваются в [1]. Для решения задачи класте-
ризации в метрическом пространстве исполь-
зуется транзитивное замыкание нечеткого
отношения сходства, порождающее ультра-
метрику [2]. Однако в [3] отмечено, что клас-
сы эквивалентности, полученные на основе
транзитивного замыкания, не всегда подда-
ются содержательной интерпретации из-за
специфических свойств ультраметрики.
В данной статье показано, что в метриче-
ском пространстве на базе введения понятий
пороговой нормы и пороговой конормы
можно, не используя операцию транзитивно-
го замыкания, решить задачу разбиения ис-
следуемого множества на непересекающиеся
кластеры. Для упрощения записи формул
будем, как правило, использовать одни и те
же символы для обозначения нечетких мно-
жеств и функций принадлежности этих не-
четких множеств (символ ◊ означает конец
доказательства леммы или теоремы). Для не-
четких множеств символы ∪ и ∩ соот-
ветствуют применению стандартных опера-
ций объединения ( max ) и пересечения ( min )
этих множеств.
Определения, теоремы, описание мето-
да. Пусть τ – нечеткое отношение сходства
на конечном множестве X , т. е. рефлексив-
ное и симметричное нечеткое бинарное отно-
шение. Функция принадлежности нечеткого
отношения сходства удовлетворяет
условиям ( , ) 1 ,x x x Хτ = ∀ ∈ ( , ) ( , )x y y xτ = τ
И.И. РЯСНАЯ
Компьютерная математика. 2010, № 2 114
,х у Х∀ ∈ . Элементы ,x y Х∈ называются сходными, если ( ), 0x yτ > , т. е. пара
( ),x y ∈τ . Для несходных элементов ( ),x y ∉τ или ( ), 0x yτ = . Для нечеткого
отношения сходства на конечном множестве X существует пара элементов, для
которой значение сходства минимально ( ) min,x yτ = α , min0 1< α ≤ .
Дополнение нечеткого отношения сходства ρ = τ называется нечетким от-
ношением несходства, функция принадлежности которого удовлетворяет усло-
виям: ( ) ( ), 1 ,x y x yρ = − τ , ( ), 0x xρ = х Х∀ ∈ , ( ) ( ), ,x y y xρ = ρ ,х у Х∀ ∈ . Для
сходных элементов ,x y Х∈ – ( ), 1x yρ < , для несходных – ( ), 1x yρ = .
Определение 1. Нечеткое подмножество xC множества X , x X∈ , функция
принадлежности которого ( )( ) ,xc y x y= τ , y X∈ , назовем xC -кластером.
В матричном представлении отношения сходства ( )xc y – строка матрицы,
соответствующая элементу x Х∈ .
Определение 2. Нечетким отношением сходства уровня α , [ ]0,1α∈ , назо-
вем нечеткое отношение сходства ( )ατ , функция принадлежности которого
,х у Х∀ ∈ удовлетворяет следующим условиям:
( ) ( ) ( ) ( )
( )
, , если , ,
,
0, если , .
x y x y
x y
x y
α τ τ ≥ ατ = τ < α
(1)
Нетрудно видеть, что ( ) ( ) ( ), ,x y x yατ ≤ τ , т.е. ( )ατ ⊆ τ . Если выбрать
minα ≤ α , то ( )ατ = τ , если 1α = , то ( )ατ – диагональное отношение.
Определение 3. Нечеткое подмножество ( )
xC α множества X , x X∈ ,
[ ]0,1α∈ , функция принадлежности которого ( ) ( ) ( )( ) ,xc y x yα α= τ , y X∈ , назо-
вем ( )
xC α -кластером.
Как известно [4], носителем нечеткого подмножества A X⊆ называется
множество supp ( ){ }| 0AA x x= µ > , где ( )A xµ – функция принадлежности не-
четкого подмножества A .
Лемма 1. Если 1 2α > α , то ( ) ( )1 2α ατ ⊆ τ , ( ) ( )1 2
x xC Cα α⊆ и supp ( )1
xC α ⊆
⊆ supp ( )2
xC α .
Доказательство следует из теоремы о разложении нечетких множеств [3].
Определение 4. Элементы ,x y X∈ назовем α -сходными, если ( ) ( ),x y α∈ τ .
Лемма 2. Если два элемента ,x y X∈ α -сходны, то они входят в носитель
общего для них кластера.
МЕТОД НЕЧЕТКОЙ КЛАСТЕРИЗАЦИИ
Компьютерная математика. 2010, № 2 115
Доказательство леммы очевидно: существует, как минимум, два таких кла-
стера ( )
xC α и ( )
yC α . Обратная лемма неверна.
Множество нечетких подмножеств B={ }iB называется нечетким покрытием
множества A , если ii
B A=∪ [5].
Лемма 3. Множество нечетких кластеров ( ) ( ){ }|xC x Xα α= ∈C , [ ]0,1α∈ ,
является нечетким покрытием множества X :
( )
хx X
C Xα
∈
=∪ . (2)
Доказательство. Если 1α = , то ( )1
xx С∈ х Х∀ ∈ , и равенство (2) выполня-
ется. В соответствии с леммой 1, если 1α < , то ( ) ( )1
х xC С
α ⊇ , и равенство (2) тем
более выполняется. ◊
Определение 5. Нечетким отношением несходства уровня δ , [ ]0,1δ∈ , на-
зовем нечеткое отношение несходства ( )δρ , функция принадлежности которого
,х у Х∀ ∈ удовлетворяет условиям
( ) ( ) ( ) ( )
( )
, , если , ,
,
1, если , .
x y x y
x y
x y
δ ρ ρ ≤ δρ = ρ > δ
(3)
Очевидно, что ( ) ( ) ( ), ,x y x yδρ ≥ ρ , т.е. ( )δρ ⊇ ρ . Если 1δ = − α , то согласно
(1), (3) следует, что ( ) ( ),x yατ + ( ) ( ),x yδρ =1.
Треугольной нормой называется функция [ ] [ ] [ ]: 0,1 0,1 0,1T × → , удовлетво-
ряющая условиям монотонности, ассоциативности и коммутативности, а также
( )0,0 0T = , ( )1,T a a= [4].
Треугольной конормой называется функция [ ] [ ] [ ]: 0,1 0,1 0,1S × → , удовле-
творяющая условиям монотонности, ассоциативности и коммутативности, а так-
же ( )1,1 1S = , ( )0,S a a= [4].
Для двойственных треугольных норм и конорм имеет место равенство
( ) ( ), 1 ,1 1T a b S a b+ − − = . (4)
Определение 6. Пороговой треугольной нормой или треугольной нормой с
порогом α , [ ]0,1α∈ , назовем функцию
( ) ( ) ( ) ( )
( )
, , если , ,
,
0, если , ,
T a b T a b
T a b
T a b
α ≥ α= < α
(5)
где ( ),T a b – треугольная норма.
И.И. РЯСНАЯ
Компьютерная математика. 2010, № 2 116
Функция ( )T α удовлетворяет условиям монотонности, ассоциативности и
коммутативности, а также ( ) ( )0,0 0T α = и, если a ≥ α , то ( ) ( )1,T a aα = , иначе
( ) ( )1, 0T aα = . Кроме того, ( ) ( ) ( ), ,T a b T a bα ≤ , если 1 2α > α , то
( ) ( ) ( ) ( )1 2, ,T a b T a bα α≤ .
Определение 7. Пороговой треугольной конормой или треугольной конор-
мой с порогом ,δ [ ]0,1δ∈ , назовем функцию
( ) ( ) ( ) ( )
( )
, , если , ,
,
1, если , ,
S a b S a b
S a b
S a b
δ ≤ δ= > δ
(6)
где ( ),S a b – треугольная конорма.
Функция ( )S δ удовлетворяет условиям монотонности, ассоциативности и
коммутативности, а также ( ) ( )1,1 1S δ = и, если a ≤ δ , то ( ) ( )0,S a aδ = , иначе
( ) ( )0, 1S aδ = . Очевидно, что ( ) ( ) ( ), ,S a b S a bδ≤ . Если 1 2δ > δ , то
( ) ( ) ( ) ( )1 2, ,S a b S a bδ δ≤ .
Лемма 4. Если T и S – двойственные треугольные норма и конорма, соот-
ветственно, и 1δ = − α , то пороговые треугольные норма ( )T α и конорма ( )S δ
также двойственные:
( ) ( ) ( ) ( ), 1 ,1 1T a b S a bα δ+ − − = . (7)
Доказательство. Согласно (4)–(6), для ( ),T a b ≥ α , ( )1 ,1 1S a b− − ≤ − α = δ ,
следовательно, ( ) ( ) ( ) ( ) ( ) ( ), , 1 1 ,1 1 1 ,1T a b T a b S a b S a bα δ= = − − − = − − − , т.е.
( ) ( ) ( ) ( ), 1 ,1 1T a b S a bα δ+ − − = . Если ( ),T a b < α , то ( ) ( ),T a bα =0, а ( )1 ,T a b− =
( )1 ,1S a b= − − > δ , т.е. ( ) ( )1 ,1 1S a bδ − − = и равенство (7) также выполняется.◊
В дальнейшем полагаем, что 1δ = − α .
Для конормы Лукасевича ( ), min (1, )LS a b a b= + пороговая треугольная ко-
норма вычисляется следующим образом:
( ) ( ) , если ,
,
1, если .L
a b a b
S a b
a b
δ + + ≤ δ
= + > δ
(8)
Определение 8. Функцию принадлежности ( ),x yρ отношения несходства
будем называть LS -метрикой на X , если
( ) ( ) ( )( ), min , , ,L
z
x y S x z z yρ = ρ ρ .
МЕТОД НЕЧЕТКОЙ КЛАСТЕРИЗАЦИИ
Компьютерная математика. 2010, № 2 117
Иначе говоря,
( ) ( )( ) ( ) ( )( ) ( ), , , , , , ,L LS x z z y S x y y y x yρ ρ ≥ ρ ρ = ρ . (9)
Обозначим ( , )LS a b как ⊕ , тогда из (9) получим неравенство треугольника
( ) ( ) ( ), , ,x z z y x yρ ⊕ ρ ≥ ρ . (10)
Теорема 1. Если ( ),x yρ – LS -метрика, то ( ) ( ),x yδρ – метрика по порого-
вой треугольной конорме ( )
L
S
δ
.
Доказательство. Следует доказать, что, если выполняется условие (10), то
( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ), , , , , , ,L LS x z z y S x y y y x y
δ δδ δ δ δ δρ ρ ≥ ρ ρ = ρ . (11)
Рассмотрим возможные случаи.
а) Если ( ) ( ), ,x z z yρ + ρ > δ , то, поскольку ( ) ( ) ( ), ,x y x yδρ ≤ ρ , согласно (8)
( ) ( ) ( ) ( ) ( )( ), , , 1LS x z z y
δ δ δρ ρ = . Если ( ),x yρ ≤ δ , то ( ) ( ) ( ), ,x y x yδρ = ρ , и условие
(11) выполняется. Если ( ),x yρ > δ , то ( ) ( ), 1x yδρ = , и условие (11) также вы-
полняется.
б) Если ( ) ( ), ,x z z yρ + ρ ≤ δ , то ( ),x zρ ≤ δ и ( ),z yρ ≤ δ , а, согласно (10),
( ),x yρ ≤ δ . Из (3) следует, что ( ) ( ) ( ), ,x z x zδρ = ρ , ( ) ( ) ( ), ,z y z yδρ = ρ ,
( ) ( ) ( ), ,x y x yδρ = ρ , тогда ( ) ( ) ( ) ( ) ( )( ) ( ) ( )( ), , , , , ,LLS x z z y S x z z y
δ δ δρ ρ = ρ ρ ≥
( ),x y≥ ρ = ( ) ( ),x yδρ . ◊
Метрику по пороговой треугольной конорме ( )
L
S
δ
будем называть
( )
L
S
δ
-метрикой.
Далее полагаем, что ( ),x yρ – LS -метрика, тогда ( ) ( ),x yδρ – ( )
L
S
δ
-метрика.
Определение 9. Расстоянием на множестве нечетких кластеров C =
={ }|xC x X∈ назовем такую функцию [ ]: 0,1d × →C C , что
( ) ( ) ( ) ( )( ), 1 min 1 ,1x y x L x y
z
d C C c y S c z c z= − = − − , (12)
где ( ),LS a b – конорма Лукасевича.
Функция d – симметрична и антирефлексивна, а условие (11) порождает
ограничение, представляющее собой аналог неравенства треугольника
( ) ( )( ) ( ) ( )( ) ( )1 ,1 1 ,1 1L x y L x y xS c z c z S c y c y c y− − ≥ − − = − . (13)
И.И. РЯСНАЯ
Компьютерная математика. 2010, № 2 118
Пусть ( ) ,xx Cξ = ( )1
xC x−ξ = , , xx X C∈ ∈C .
Лемма 5. Биекция ξ между метрическим пространством ( ),X ρ и метриче-
ским пространством ( ),dC является изометрией.
Доказательство. Так как ( ) ( )1 ,xc z x z− = ρ , ( ) ( )1 ,yc z y z− = ρ , ( )1 xc y− =
( ),x y= ρ , то (13) можно, с учетом симметричности отношения несходства, запи-
сать как ( ) ( )( ) ( ) ( )( ) ( ), , , , , , ,L LS x z z y S x y y y x yρ ρ ≥ ρ ρ = ρ , что в точности сов-
падает с (9). Следовательно, ( ) ( ), ,x yd C C x y= ρ , где ( ),x yρ – LS -метрика.◊
Определим биективное отображение ( ): X α
αξ → C следующим образом:
x X∀ ∈ ( ) ( )
xx C α
αξ = и ( ) ( )
xC α α∀ ∈C обратное отображение ( )( )1
xC xα−
αξ = .
Лемма 6. Биекция αξ между метрическим пространством ( )( ),X δρ и мет-
рическим пространством ( )( ), dαC , где расстояние ( ) ( )( ) ( ) ( ), 1x y xd C C c yα α α= −
( ) ( ) ( ),x yC Cα α α∀ ∈C , является изометрией.
Иначе говоря, ( ) ( )( ) ( ) ( ), ,x yd C C x yα α δ= ρ , где ( ) ( ),x yδρ – ( )
LS
δ
-метрика.
Доказательство аналогично доказательству леммы 5.
Определение 10. Кластеры ( ) ( ) ( ),x yC Cα α α∈C , ,x y X∈ , назовем соседними,
если расстояние между ними ( ) ( )( ),x yd C Cα α ≤ δ , где 1δ = − α .
Если ( )
xC α , ( )
yC α – соседние кластеры, то ( )supp xy C α∈ , ( )supp yx C α∈ . Если
кластеры ( ) ( ),x yC Cα α не являются соседними, то ( ) ( )( ), 1x yd C Cα α = .
Определение 11. Множество кластеров xO = ( ) ( ){ }| supp ,y xC y C y xα α∈ ≠
назовем δ -окрестностью кластера ( )
xC α .
Очевидно, что ( )
y xC α∀ ∈O ( ) ( )( ),x yd C Cα α ≤ δ , т. е. любой из этих кластеров
является соседним с кластером ( )
xC α .
Определение 12. Кластеры ( ) ( ) ( ),x yC Cα α α∈C , ,x y X∈ , назовем смежными,
если ( ) ( )( ),x yC Cα α ≠ ∅∩ , а расстояние между ними ( ) ( )( ), 1.x yd C Cα α =
МЕТОД НЕЧЕТКОЙ КЛАСТЕРИЗАЦИИ
Компьютерная математика. 2010, № 2 119
Для смежных кластеров существует хотя бы один общий соседний кластер
( )
zC α , такой, что ( ) ( )( )supp ,suppx yz C Cα α∈∩ .
Если ( ) ( )( ),x yC Cα α ≠ ∅∩ , то эти кластеры – либо соседние, либо смежные.
Определение 13. Кластеры ( ) ( ) ( ),x yC С
α α α∈C назовем связанными, если су-
ществует такая совокупность кластеров ( ) ( )
0
,x zC C
αα = ( )
1
,zC
α
( )
2
,zC
α
…, ( )
1nzC
−
α
,
( ) ( )
n yzC C
α α= , что ( ) ( )( )0 1
,z zC C
α α ≠ ∅∩ , ( ) ( )( )1 2
,z zC C
α α ≠ ∅∩ ,…, ( ) ( )( )1
,
n nz zC C
−
α α ≠ ∅∩ ;
( )
izC
α ∈ ( )αC , { }0,...,i n∈ .
Очевидно, что соседние и смежные кластеры являются связанными. Однако
связанные кластеры не являются, в общем случае, соседними или смежными.
Лемма 7. Между связанными кластерами ( ) ( ) ( ),x yC С
α α α∈C существует
путь, в котором расстояние между кластерами не превышает δ в метрике ( )
LS
δ
.
Другими словами, такой путь проходит через соседние кластеры. Назовем
такой путь δ -связным.
Доказательство. Пусть 1n = (определение (13)), тогда ( ) ( )( ),x yC Cα α ≠ ∅∩ .
Кластеры ( )
xC α , ( )
yC α – соседние или смежные. В первом случае
( ) ( )( ),x yd C Cα α ≤ δ . Во втором случае существует общий соседний кластер ( )
zC α ,
такой, что ( )
z xC α ∈O и ( )
z yC α ∈O , ( )supp xz C α∈ , ( )supp yz C α∈ . Иначе говоря,
( ) ( )( ),x zd C Cα α ≤ δ , ( ) ( )( ),z yd C Cα α ≤ δ , и путь между кластерами ( ) ( ),x yC С
α α –
δ -связный. Если кластеры ( ) ( )
0 xzC C
α α= и ( )
1kzС
−
α
, k n< , связаны, то аналогично
доказывается существование δ -связного пути между кластерами ( ) ( )
1
,
k kz zC С
−
α α
,
т.е. кластеры ( ) ( )
0
,
kz zC С
α α
связаны. По индукции следует наличие δ -связного пу-
ти для k n= . ◊
Если между двумя кластерами не существует δ -связного пути, то эти кла-
стеры назовем несвязанными.
Определение 14. Связным предклассом назовем множество кластеров
( ){ }xC α , в котором любые два кластеры связаны.
И.И. РЯСНАЯ
Компьютерная математика. 2010, № 2 120
Другими словами, между любыми двумя элементами связного предкласса
существует δ -связный путь. Очевидно, что множество кластеров xO представ-
ляет собой связный предкласс.
Определение 15. Связным классом или ∆ -кластером назовем максималь-
ный предкласс.
Пусть | |N X= .
Теорема 2. Множество ∆ -кластеров { }
1
m
j j=
= ∆ΣΣΣΣ , 2 m N≤ ≤ , представляет
собой разбиение множества ( )αC .
Доказательство. Предположим, что ∆ -кластеры пересекаются, т. е.
( ), ,i j i j∆ ∆ ≠ ∅ ≠∩ , { }, 1,...,i j m∈ , тогда существует кластер ( )
zC α ∈ ( ),i j∆ ∆∩
и кластеры ,i j∆ ∆ оказываются связанными, т.е. не являются максимальными
предклассами, что противоречит определению 15. Обозначим | |j jk∆ = , 1,j m= .
Если jk =1, то кластер j∆ содержит только один элемент. Так как
( ) ( )
x jC α α∀ ∈ ∃∆ ∈C ΣΣΣΣ и ( ) ( )
j xC α α∀∆ ∈ ∃ ∈CΣΣΣΣ , то ( )
1
m
j
j
α
=
∆ = C∪ и
1
m
j
j
k N
=
=∑ . ◊
Назовем D -кластерами множества вида ( )( ) ( ){ }1| ,j x x jD x x C Cα α−
α= = ξ ∈ ∆ .
Теорема 3. Объединение носителей кластеров ( ) ( )
xC α α∈C , входящих в
один и тот же кластер j∆ , { }1,...,j m∈ , порождает классы эквивалентности на
множестве X , которые представляют собой D -кластеры, а множество этих кла-
стеров ( )
xC α является нечетким покрытием соответствующего кластера jD .
Доказательство. Поскольку j∆ – максимальный предкласс, { }1,...,j m∈ , то
z∀ ( )
( )
supp
x j
x
C
C
α
α
∈∆
∈ ∪ ( )
z jC α∃ ∈ ∆ , т.е. ( ) ( )( )1 |z z jz C Cα α−
α= ξ ∈∆ . Следователь-
но, ( )
( )
supp
x j
x j
C
C D
α
α
∈∆
=∪ , | | | |j jD∆ = , ( )
( )
x j
x j
C
C D
α
α
∈∆
=∪ . Согласно теореме 2
множество { }
1
m
j j=
∆ – разбиение множества ( )αC , а между элементами jx D∈ и
кластерами ( )
x jC α ∈∆ существует взаимно-однозначное соответствие. Поэтому
( ),i jD D = ∅∩ , i j≠ , { }, 1,...,i j m∈ ,
1
m
jj
D X
=
=∪ . Таким образом, множество
МЕТОД НЕЧЕТКОЙ КЛАСТЕРИЗАЦИИ
Компьютерная математика. 2010, № 2 121
( ){ }j xC α∆ = – нечеткое покрытие кластера jD , а множество { }
1
m
j j
D
=
– разбие-
ние множества X . Обозначим DR отношение эквивалентности, порождаемое
множеством непересекающихся кластеров { }
1
m
j j
D
=
, а отношение эквивалентно-
сти, порождаемое множеством непересекающихся кластеров { }
1
m
j j=
∆ , – R∆ .
Тогда ( ) ( ) ( )( ), ,D x yR x y R C Cα α
∆⇔ .◊
Определим на множестве ( )αC отношение θ , такое, что ( ) ( ) ( ),x yC Cα α α∀ ∈C
функция принадлежности ( ) ( )( ),x yC Cα αθ = ( ) ( )( )1 ,x yd C Cα α− . Отношение θ – сим-
метрично и рефлексивно, т. е. представляет собой нечеткое отношение сходства.
Вышеизложенное позволяет сформулировать следующую теорему, выра-
жающую сущность предлагаемого метода кластеризации.
Теорема 4. Биективное отображение αξ представляет собой изоморфизм
систем ( ) ( ), , , DX Rα δτ ρ и ( ) , , ,d Rα
∆θC .
Доказательство. Согласно лемме 6 имеет место равенство ( ) ( ),x yδρ =
( ) ( )( ),x yd C Cα α= , тогда из определения отношения θ следует ( ) ( ),x yατ =
( ) ( )( ),x yC Cα α= θ . Из теоремы 3 следует, что ( ) ( ) ( )( ), ,D x yR x y R C Cα α
∆= .◊
Опишем кратко предлагаемый метод кластеризации. Задачу кластеризации
считаем решенной, когда число кластеров 2m ≥ . Практический интерес пред-
ставляет исследование связи между структурой и количеством ∆ -кластеров, ко-
торая изменяется в зависимости от значения порога α . Для проведения такого
исследования задается набор пороговых значений 1 2 ... nα < α < < α , где
1 minα ≥ α , 1nα < . Для каждого значения порога α строится множество класте-
ров ( ) ( ){ }|xC x Xα α= ∈C и на основе объединения носителей связанных класте-
ров ( )
xC α строится множество кластеров { }jD . Поскольку между кластерами
jD и j∆ существует взаимно-однозначное соответствие, то кластер jD содер-
жит перечень (имена) кластеров ( )
xC α , входящих в кластер j∆ . Характеристиче-
ское свойство D -кластеров и ∆ -кластеров состоит в существовании пути между
любыми элементами одного и того же кластера, в котором расстояние между
И.И. РЯСНАЯ
Компьютерная математика. 2010, № 2 122
соседними элементами не превышает заданного значения δ , 1δ = − α , и отсут-
ствии такого пути между элементами различных кластеров.
Представляет интерес сравнить вышерассмотренный метод кластеризации и
метод кластеризации на базе нечеткого отношения эквивалентности.
Пусть
( )α
τɵ – нечеткое отношение эквивалентности, полученное путем
max min− транзитивного замыкания нечеткого отношения сходства ( )ατ , а
ɵ ( )δ
ρ – дополнение нечеткого отношения эквивалентности, 1α = − δ , ɵ
( ) ( ),x y
δ
ρ =
( ) ( )1 ,x y
α
= − τɵ .
Нетрудно показать, что min max− транзитивное замыкание отношения не-
сходства ( )δρ равно ( )ˆ δρ .
Теорема 5. Классы эквивалентности множества уровня α нечеткого отно-
шения эквивалентности
( )α
τɵ представляют собой D -кластеры на множестве X .
Доказательство. Пусть ,x y K∈ , где K – класс эквивалентности, тогда
( ) ( ),x y
α
τ ≥ αɵ и ɵ
( ) ( ),x y
δ
ρ ≤ δ . Аналогично [3] нетрудно показать, что построе-
ние min max− транзитивного замыкания отношения несходства ( )δρ , представ-
ленного в виде конечного нечеткого графа, эквивалентно вычислению длины
путей с помощью операции max и выбору пути с помощью операции min . Не-
равенство ɵ
( ) ( ),x y
δ
ρ ≤ δ означает существование δ -связного пути между этими
элементами в метрическом пространстве ( )( , )X δρ . Для любых трех элементов
, ,x y z X∈ из ɵ
( ) ( ),x y
δ
ρ ≤ δ и ɵ
( ) ( ),y z
δ
ρ ≤ δ следует, что ɵ
( )
( , )x z
δ
ρ ≤ δ . Следова-
тельно, между этими элементами существует δ -связный путь в пространстве
( )( , )X δρ , т.е. , ,x y z K∈ . По индукции следует, что δ -связный путь существует
между всеми элементами, принадлежащими K . Следовательно, класс эквива-
лентности K представляет собой D -кластер на множестве X . ◊
Сравним вычислительную сложность алгоритмов построения классов экви-
валентности отношения
( )α
τɵ и D -кластеров на множестве X . Так как вычисли-
тельная сложность построения D -кластеров по матрице ( ) ( ),x yατ и классов
эквивалентности по матрице
( ) ( ),x y
α
τɵ одинакова, а для построения матрицы
( ) ( ),x y
α
τɵ требуется ( )4O N операций, то алгоритм построения D -кластеров
оказывается существенно более быстродействующим.
МЕТОД НЕЧЕТКОЙ КЛАСТЕРИЗАЦИИ
Компьютерная математика. 2010, № 2 123
Заключение. Предлагаемый метод кластеризации базируется на том, что
дополнение нечеткого отношения сходства (отношение несходства) является
метрикой. Использование набора пороговых значений сходства позволяет по-
строить систему вложенных кластеров, на основе которой можно проводить
дальнейший анализ исследуемого множества. Данный метод отличается от ме-
тодов кластеризации на основе нечеткого отношения эквивалентности тем, что
позволяет разрабатывать более быстрые алгоритмы построения кластеров.
І.І. Рясна
МЕТОД НЕЧІТКОЇ КЛАСТЕРИЗАЦІЇ
Розглянуто метод нечіткої кластеризації за умови, що доповнення нечіткого відношення схо-
жості є метрикою. На основі введення понять норм та конорм з порогом розв’язується задача
розбиття множини, що досліджується, на кластери, які не перетинаються. Запропонований
метод відрізняється від методів, що використовують нечітке відношення еквівалентності тим,
що дозволяє створювати більш швидкі алгоритми для побудови кластерів.
I.I. Rjasnaja
FUZZY CLUSTERING METHOD
The method of fuzzy clustering is examined under the condition that a complement of fuzzy similar-
ity relation is a metric. On the basis of definition of concepts of threshold norm and threshold
conorm, the problem of set partitioning on nonintersecting clusters is solved. The method proposed
differs from the methods using the fuzzy equivalence relation by the fact that it allows to create
faster algorithms of construction of clusters.
1. Руспини Э.Г. Последние достижения в нечетком кластер-анализе // Нечеткие множества и
теория возможностей. Последние достижения. − М.: Радио и связь, 1986. − С. 114−132.
2. Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Методы и модели анализа
данных: OLAP и Data Mining. – СПб.: БХВ-Петербург, 2004. – 336 с.
3. Кофман А. Введение в теорию нечетких множеств. − М.: Радио и связь, 1982. − 432 с.
4. Нечеткие множества в моделях управления и искусственного интеллекта / Под ред.
Д.А. Поспелова. − М.: Наука, 1986. − 312 с.
5. Леоненков А. Нечеткое моделирование в среде MATLAB и fuzzyTECH. − Санкт-Петер-
бург: БХВ−Петербург, 2003. − 724 с.
Получено 15.04.2010
Oá àâòîðå:
Рясная Ирина Ивановна,
научный сотрудник Института кибернетики имени В.М. Глушкова НАН Украины.
|
| id | nasplib_isofts_kiev_ua-123456789-84593 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T16:04:52Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Рясная, И.И. 2015-07-10T17:40:00Z 2015-07-10T17:40:00Z 2010 Метод нечеткой кластеризации / И.И. Рясная // Компьютерная математика: сб. науч. тр. — 2010. — № 2. — С. 113-123. — Бібліогр.: 5 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84593 519.8 Рассматривается метод нечеткой кластеризации при условии, что дополнение нечеткого отношения сходства является метрикой. На базе введения понятий пороговой нормы и пороговой конормы решается задача разбиения исследуемого множества на непересекающиеся кластеры. Предлагаемый метод отличается от методов кластеризации, использующих нечеткое отношение эквивалентности, тем, что позволяет создавать более быстрые алгоритмы построения кластеров. Розглянуто метод нечіткої кластеризації за умови, що доповнення нечіткого відношення схожості є метрикою. На основі введення понять норм та конорм з порогом розв’язується задача розбиття множини, що досліджується, на кластери, які не перетинаються. Запропонований метод відрізняється від методів, що використовують нечітке відношення еквівалентності тим, що дозволяє створювати більш швидкі алгоритми для побудови кластерів. The method of fuzzy clustering is examined under the condition that a complement of fuzzy similarity relation is a metric. On the basis of definition of concepts of threshold norm and threshold conorm, the problem of set partitioning on nonintersecting clusters is solved. The method proposed differs from the methods using the fuzzy equivalence relation by the fact that it allows to create faster algorithms of construction of clusters. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Оптимизация вычислений Метод нечеткой кластеризации Метод нечіткої кластеризації Fuzzy clustering method Article published earlier |
| spellingShingle | Метод нечеткой кластеризации Рясная, И.И. Оптимизация вычислений |
| title | Метод нечеткой кластеризации |
| title_alt | Метод нечіткої кластеризації Fuzzy clustering method |
| title_full | Метод нечеткой кластеризации |
| title_fullStr | Метод нечеткой кластеризации |
| title_full_unstemmed | Метод нечеткой кластеризации |
| title_short | Метод нечеткой кластеризации |
| title_sort | метод нечеткой кластеризации |
| topic | Оптимизация вычислений |
| topic_facet | Оптимизация вычислений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84593 |
| work_keys_str_mv | AT râsnaâii metodnečetkoiklasterizacii AT râsnaâii metodnečítkoíklasterizacíí AT râsnaâii fuzzyclusteringmethod |