Помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек
Розглянуто метод нечітких зв'язаних точок (Fuzzy Joint Points - FJP), в якому нечіткість кластеризації полягає в детальності врахування властивостей елементів під час формування множин схожих елементів. На підставі цього підходу запропоновано новий перешкодостійкий варіант алгоритму FJP. Дослід...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/71930 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек / Э.Н. Насибов // Кибернетика и системный анализ. — 2008. — № 1. — С. 10-22. — Бібліогр.: 14 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-71930 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-719302014-12-15T03:01:41Z Помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек Насибов, Э.Н. Кибернетика Розглянуто метод нечітких зв'язаних точок (Fuzzy Joint Points - FJP), в якому нечіткість кластеризації полягає в детальності врахування властивостей елементів під час формування множин схожих елементів. На підставі цього підходу запропоновано новий перешкодостійкий варіант алгоритму FJP. Досліджено властивості алгоритму FJP і доведено достатню умову для коректного розпізнавання прихованої структури класів, що є в наявності. 2008 Article Помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек / Э.Н. Насибов // Кибернетика и системный анализ. — 2008. — № 1. — С. 10-22. — Бібліогр.: 14 назв. — рос. http://dspace.nbuv.gov.ua/handle/123456789/71930 519.8 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Насибов, Э.Н. Помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек Кибернетика и системный анализ |
| description |
Розглянуто метод нечітких зв'язаних точок (Fuzzy Joint Points - FJP), в якому нечіткість кластеризації полягає в детальності врахування властивостей елементів під час формування множин схожих елементів. На підставі цього підходу запропоновано новий перешкодостійкий варіант алгоритму FJP. Досліджено властивості алгоритму FJP і доведено достатню умову для коректного розпізнавання прихованої структури класів, що є в наявності. |
| format |
Article |
| author |
Насибов, Э.Н. |
| author_facet |
Насибов, Э.Н. |
| author_sort |
Насибов, Э.Н. |
| title |
Помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек |
| title_short |
Помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек |
| title_full |
Помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек |
| title_fullStr |
Помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек |
| title_full_unstemmed |
Помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек |
| title_sort |
помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2008 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/71930 |
| citation_txt |
Помехоустойчивый алгоритм решения проблемы нечеткой кластеризации на базе метода нечетких связанных точек / Э.Н. Насибов // Кибернетика и системный анализ. — 2008. — № 1. — С. 10-22. — Бібліогр.: 14 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT nasibovén pomehoustojčivyjalgoritmrešeniâproblemynečetkojklasterizaciinabazemetodanečetkihsvâzannyhtoček |
| first_indexed |
2025-07-05T20:49:50Z |
| last_indexed |
2025-07-05T20:49:50Z |
| _version_ |
1836841530724188160 |
| fulltext |
ÓÄÊ 519.8
Ý.Í. ÍÀÑÈÁÎÂ
ÏÎÌÅÕÎÓÑÒÎÉ×ÈÂÛÉ ÀËÃÎÐÈÒÌ ÐÅØÅÍÈß ÏÐÎÁËÅÌÛ
ÍÅ×ÅÒÊÎÉ ÊËÀÑÒÅÐÈÇÀÖÈÈ ÍÀ ÁÀÇÅ ÌÅÒÎÄÀ ÍÅ×ÅÒÊÈÕ
ÑÂßÇÀÍÍÛÕ ÒÎ×ÅÊ
Êëþ÷åâûå ñëîâà: êëàñòåðèçàöèÿ, íå÷åòêèå ñâÿçàííûå òî÷êè (FJP), íå÷åòêîå
ñâÿçàííîå ìíîæåñòâî, ïîìåõîóñòîé÷èâîñòü.
ÂÂÅÄÅÍÈÅ
Çàäà÷à êëàñòåðèçàöèè ÿâëÿåòñÿ îäíîé èç îñíîâíûõ çàäà÷, èñïîëüçóåìûõ â
ñîâðåìåííîé òåõíîëîãèè èíòåëëåêòóàëüíîé îáðàáîòêè äàííûõ ñ ïðèìåíåíèåì
êîìïüþòåðîâ [1, 2]. Îáùàÿ ôèëîñîôèÿ êëàñòåðèçàöèè áàçèðóåòñÿ íà ðàçáèåíèè
èñõîäíîãî ìàññèâà äàííûõ íà ãîìîãåííûå (ñõîæèå) êëàññû îòíîñèòåëüíî
áëèçîñòè ñâîéñòâ. Ïðè ýòîì ýëåìåíòû â îäíîì êëàññå ÿâëÿþòñÿ ìàêñèìàëüíî
áëèçêèìè, à ýëåìåíòû â ðàçëè÷íûõ êëàññàõ ÿâëÿþòñÿ ìàêñèìàëüíî äàëåêèìè
ïî îòíîøåíèþ îäèí ê äðóãîìó.
 êëàññè÷åñêîé çàäà÷å êëàñòåðèçàöèè ãðàíèöû êëàññîâ ÿâëÿþòñÿ ÷åòêèìè è
ëþáîé ýëåìåíò ìîæåò ïðèíàäëåæàòü òîëüêî îäíîìó èç èìåþùèõñÿ êëàññîâ.
Îäíàêî íà ïðàêòèêå ãðàíèöû ìåæäó êëàññàìè, êàê ïðàâèëî, íå ìîãóò áûòü
îïðåäåëåíû ÷åòêî è íåêîòîðûå ýëåìåíòû ìîãóò îäíîâðåìåííî ïðèíàäëåæàòü
ðàçëè÷íûì êëàññàì ñ îòëè÷íûìè îò íóëÿ ñòåïåíÿìè ïðèíàäëåæíîñòåé.  òàêèõ
ñëó÷àÿõ àäåêâàòíîñòü çàäà÷è êëàñòåðèçàöèè, ïîäîáíî çàäà÷å èäåíòèôèêàöèè
[3–5], ìîæåò áûòü ïîâûøåíà ñ ïðèìåíåíèåì òåîðèè íå÷åòêèõ ìíîæåñòâ [2].  íà-
ñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ äðóãàÿ êîíöåïöèÿ çàäà÷è êëàñòåðèçàöèè — ñ èñ-
ïîëüçîâàíèåì òàê íàçûâàåìîãî ìåòîäà íå÷åòêèõ ñâÿçàííûõ òî÷åê (Fuzzy Joint
Points — FJP) [6]. Îñíîâíîå îòëè÷èå òàêîãî ìåòîäà çàêëþ÷àåòñÿ â òîì, ÷òî
ïîíÿòèå ðàçìûòîñòè êëàñòåðèçàöèè ðàññìàòðèâàåòñÿ ñ èåðàðõè÷åñêîé òî÷êè
çðåíèÿ. À èìåííî íå÷åòêîñòü êëàñòåðèçàöèè ïîíèìàåòñÿ â òîì ñìûñëå, íàñêîëüêî
äåòàëüíî ðàññìàòðèâàþòñÿ ñâîéñòâà ýëåìåíòîâ ïðè ôîðìèðîâàíèè ìíîæåñòâà
ñõîæèõ ýëåìåíòîâ. Ïîíÿòíî, ÷òî ÷åì áîëåå äåòàëüíî ðàññìàòðèâàþòñÿ ñâîéñòâà,
òåì áîëüøå îòëè÷èé âûÿâëÿåòñÿ ìåæäó ýëåìåíòàìè. Åñëè ñâîéñòâà
ðàññìàòðèâàþòñÿ áîëåå ðàçìûòî, ò.å. íå âäàâàÿñü â äåòàëè, òî ýëåìåíòû èìåþò
áîëüøå ñõîæåñòè.  òàêîì ñëó÷àå ðàçìûòîñòü êëàñòåðèçàöèè îïðåäåëÿåòñÿ
«äåòàëüíîñòüþ» ó÷åòà èññëåäóåìûõ ñâîéñòâ. Òîãäà ïðè ìèíèìàëüíîé ñòåïåíè
ðàçìûòîñòè âñå ýëåìåíòû â êàêîé-òî ñòåïåíè áóäóò îòëè÷àòüñÿ îäèí îò
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 10
© Ý.Í. Íàñèáîâ, 2008
äðóãîãî è êàæäûé ýëåìåíò äîëæåí ðàññìàòðèâàòüñÿ êàê îòäåëüíûé êëàññ, à
ïðè ìàêñèìàëüíîé ñòåïåíè ðàçìûòîñòè âñå ýëåìåíòû áóäóò ïîõîæè îäèí íà
äðóãîãî è, ñëåäîâàòåëüíî, âñå îíè áóäóò ïðèíàäëåæèòü îäíîìó êëàññó. Ïðè
êàêîé-òî ñòåïåíè ðàçìûòîñòè ìåæäó 0 è 1 íåêîòîðûå ýëåìåíòû ñ áëèçêèìè
ñâîéñòâàìè áóäóò ïîõîæè îäèí íà äðóãîãî è ïðèíàäëåæàòü îäíîìó è òîìó æå
êëàññó, à áîëåå óäàëåííûå ýëåìåíòû áóäóò ïðèíàäëåæàòü ðàçëè÷íûì êëàññàì.
Îñíîâíûìè âîïðîñàìè â ïðîáëåìå îïðåäåëåíèÿ íå÷åòêîé êëàñòåðèçàöèè
ÿâëÿþòñÿ: à) íàõîæäåíèå îïòèìàëüíîãî êîëè÷åñòâà ãîìîãåííûõ êëàññîâ;
á) ôîðìèðîâàíèå íà÷àëüíîãî ðàçáèåíèÿ èñõîäíûõ ýëåìåíòîâ íà êëàññû; â)
íåïîñðåäñòâåííûå àëãîðèòìû êëàñòåðèçàöèè ñ èòåðàòèâíûì óëó÷øåíèåì ðàçáèåíèÿ.
Ñóùåñòâóåò äîñòàòî÷íîå ÷èñëî ïóáëèêàöèé ïî óêàçàííûì âîïðîñàì [7–11].
Ñðåäè ðàññìîòðåííûõ ìåòîäîâ íàèáîëåå ÷àñòî èñïîëüçóþòñÿ ìåòîä áëèæàéùèõ
K-ñîñåäåé (K-Nearest Neighbors — KNN) è ìåòîä õîëìîâ (Mountain Method)
[8–10]. Îäíàêî îíè èìåþò íåêîòîðûå íåäîñòàòêè. Òàê, â ìåòîäå KNN òðåáóåòñÿ
çàðàíåå çàäàâàòü êîëè÷åñòâî êëàñòåðîâ, êðîìå òîãî, ðàçáèåíèå ÿâëÿåòñÿ
äîñòàòî÷íî ãðóáûì. Îñíîâíûì íåäîñòàòêîì ìåòîäà õîëìîâ — ñëîæíîñòü ïðè åãî
âû÷èñëåíèè.
Ðàññìîòðåííûé â íàñòîÿùåé ñòàòüå ìåòîä FJP ñâîáîäåí îò âûøåïåðå÷èñëåí-
íûõ íåäîñòàòêîâ [6]. Îäíèì èç ïðåèìóùåñòâ óêàçàííîãî ìåòîäà — ñóùåñòâîâà-
íèå ìåõàíèçìà àâòîìàòè÷åñêîãî íàõîæäåíèÿ êîëè÷åñòâà êëàññîâ, êîòîðûé
îòñóòñòâóåò â áîëüøèíñòâå äðóãèõ àëãîðèòìîâ èåðàðõè÷åñêîé êëàñòåðèçàöèè.
Ýòîò ìåòîä ìîæåò òàêæå ðàñïîçíàâàòü îòäåëåííûå ýëåìåíòû êàê îòäåëüíûå
êëàññû, ÷òî ñâèäåòåëüñòâóåò â ïîëüçó ìåòîäà FJP, ïîñêîëüêó óäàëåííûå îò ìàññû
ýëåìåíòû ìîãóò áûòü íå èãíîðèðîâàíû êàê òî÷êè øóìà, à ðàññìîòðåíû êàê
ñàìîñòîÿòåëüíûå èíäèâèäóàëüíûå êëàññû. Ýòî ìîæåò èìåòü çíà÷åíèå, íàïðèìåð,
ïðè èññëåäîâàíèè â îáëàñòè ìåäèöèíû, áèîëîãèè è ò.ï., ãäå àíîìàëüíûå ñëó÷àè
èìåþò îïðåäåëåííûé èíòåðåñ. Â íàñòîÿùåé ñòàòüå èññëåäóåòñÿ óñëîâèå
êîððåêòíîãî ðàñïîçíàâàíèÿ êëàññîâ àëãîðèòìîì FJP è ïðåäëàãàåòñÿ
ïîìåõîóñòîé÷èâûé âàðèàíò ýòîãî àëãîðèòìà, â êîòîðîì åãî ÷óâñòâèòåëüíîñòü ê
øóìó ìîæåò áûòü îòðåãóëèðîâàíà.
1. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ïóñòü èìååòñÿ ìíîæåñòâî òî÷åê X x x xn� { }1 2, , . . ., , ãäå x E i ni
p� �, ,1 .
Òðåáóåòñÿ ðàçäåëèòü ìíîæåñòâî X íà ãîìîãåííûå êëàññû, ò.å. ïðîèçâåñòè
êëàñòåðèçàöèþ ìíîæåñòâà X . Äðóãèìè ñëîâàìè, òðåáóåòñÿ âû÷èñëèòü
ïîäìíîæåñòâà X X X k1 2, , . . ., òàêèå, ÷òî
� � � ��i j X Xi j (1)
è
i
k
iX X
�
�
1
� .
(2)
Îòìåòèì, ÷òî ïîäìíîæåñòâà X X X k1 2, , . . ., ÿâëÿþòñÿ ìíîæåñòâàìè â
êëàññè÷åñêîì ñìûñëå, ò.å. áåç íå÷åòêîñòè.
Êîëè÷åñòâî êëàññîâ k çàðàíåå íåèçâåñòíî. Ïîýòîìó òðåáóåòñÿ òàêæå
îïðåäåëèòü êîëè÷åñòâî êëàññîâ, àäåêâàòíî îòðàæàþùåå ñòðóêòóðó äàííûõ.
 ðàññìàòðèâàåìîì ñëó÷àå ïîäõîäÿùåå çíà÷åíèå k áóäåò îïðåäåëÿòüñÿ íà îñíîâå
îïòèìàëüíîñòè íåêîòîðîé ôóíêöèè, áàçèðóþùåéñÿ íà ìàêñèìàëüíîñòè
ìåæêëàññîâûõ ðàññòîÿíèé.
Êàê áûëî ñêàçàíî âî ââåäåíèè, ýëåìåíòû âíóòðè îäíîãî êëàññà äîëæíû áûòü
ðàñïîëîæåíû ìàêñèìàëüíî áëèçêî, à ðàçëè÷íûå êëàññû äîëæíû ðàñïîëàãàòüñÿ
11 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
êàê ìîæíî äàëüøå îäèí îò äðóãîãî. Ïðè ýòîì áëèçîñòü ýëåìåíòîâ ìîæåò
îïðåäåëÿòüñÿ íà îñíîâå ðàçëè÷íûõ ìåòðèê. Îòìåòèì, ÷òî áîëüøèíñòâî ìåòîäîâ
êëàñòåðèçàöèè íà áàçå äèñòàíöèè èñïîëüçóþò êëàññè÷åñêóþ ýâêëèäîâó
äèñòàíöèþ, ò.å. äèñòàíöèÿ ìåæäó îáû÷íûìè òî÷êàìè a è b p-ìåðíîãî
ïðîñòðàíñòâà E p îïðåäåëÿåòñÿ êàê
d a b a b
i
p
i i( , ) ( )� �
�
1
2 .
(3)
Ñëåäóåò îòìåòèòü, ÷òî ñóùåñòâóþò òàêæå ìåòîäû, ãäå èñïîëüçóþòñÿ äðóãèå
áîëåå îáîáùåííûå äèñòàíöèè. Íàïðèìåð, â [12] ðàññìàòðèâàåòñÿ ïðîáëåìà
êëàñòåðèçàöèè ñ ïðèìåíåíèåì àëãîðèòìà íå÷åòêîé êëàñòåðèçàöèè (Fuzzy
c-Means — FCM) íà áàçå ìàñøòàáèðóåìîé ïî íàïðàâëåíèÿì äèñòàíöèè è
äåìîíñòðèðóþòñÿ íåêîòîðûå ïðåèìóùåñòâà òàêîé äèñòàíöèè. Îäíàêî â
íàñòîÿùåé ñòàòüå áóäåì èñïîëüçîâàòü äèñòàíöèþ â ñìûñëå (3).
2. ÍÅ×ÅÒÊÈÅ ÑÂßÇÀÍÍÛÅ ÒÎ×ÊÈ È ÈÕ ÑÂÎÉÑÒÂÀ
Îáîçíà÷èì F E p( ) ìíîæåñòâî âñåõ íå÷åòêèõ ïîäìíîæåñòâ ïðîñòðàíñòâà E p .
Ïóñòü �A
pE: [ , ]
0 1 îáîçíà÷àåò ôóíêöèþ ïðèíàäëåæíîñòè íå÷åòêîãî
ìíîæåñòâà A F E p� ( ).
Ñíà÷àëà íàïîìíèì íåêîòîðûå ïîíÿòèÿ, ââåäåííûå â ðàáîòå [6].
Îïðåäåëåíèå 1. Íå÷åòêîé òî÷êîé êîíóñíîé ôîðìû A a R F E p� �( , ) ( )
ïðîñòðàíñòâà E p áóäåì íàçûâàòü íå÷åòêîå ìíîæåñòâî (ðèñ. 1), ôóíêöèÿ
ïðèíàäëåæíîñòè êîòîðîãî îïðåäåëÿåòñÿ êàê
�A x
d x a
R
d x a R
( )
( , )
( , ) ,� � �
�
�
�
��
1
0 â ïðîòèâíîì ñëó àå
(4)
Çäåñü a E p� ÿâëÿåòñÿ öåíòðîì íå÷åòêîé òî÷êè A, à R E� 1 ÿâëÿåòñÿ ðàäèóñîì
åãî íîñèòåëÿ supp A, ãäå supp { }A x E xp
A� � �| ( ) .� 0 Î÷åâèäíî, ÷òî
�-óðîâíåâîå ìíîæåñòâî íå÷åòêîé òî÷êè êîíóñíîé ôîðìû A a R� ( , ) áóäåò
ìíîæåñòâî â êëàññè÷åñêîì ñìûñëå
A x E x x E d x a Rp
A
p
� � � �� � � � � � � �{ } { }| ( ) | ( , ) ( )1 (5)
Äàëåå áóäåì óïîòðåáëÿòü
ñîêðàùåííûé òåðìèí «íå÷åòêàÿ
òî÷êà», ïîäðàçóìåâàÿ ïðè ýòîì
íå÷åòêóþ òî÷êó êîíóñíîé
ôîðìû (•, )R , îïðåäåëåííóþ
êàê (4).
Ïóñòü A a R� ( , ) è
B b R� ( , ) — íå÷åòêèå òî÷êè èç
ìíîæåñòâà X F E p� ( ).
Îïðåäåëèì íå÷åòêîå
îòíîøåíèå T X X: [ , ]�
0 1
ìåæäó ýëåìåíòàìè ìíîæåñòâà
X , ñòåïåíü âûïîëíåíèÿ
êîòîðîãî îïðåäåëÿåòñÿ êàê
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 12
Ðèñ. 1. Íå÷åòêàÿ òî÷êà êîíóñíîé ôîðìû A a R� �( , )
� P E( )2 â ïðîñòðàíñòâå E2
T A B
d a b
R
( , )
( , )
, ,� �
�
�
�
�
�
max 1
2
0
(6)
ãäå a E p� è b E p� ÿâëÿþòñÿ öåíòðàìè íå÷åòêèõ òî÷åê A è B ñîîòâåòñòâåííî
(ðèñ. 2). Èç îòíîøåíèÿ (6) ñëåäóåò, ÷òî ïðè T A B( , ) ( , ]� 0 1 ñïðàâåäëèâî
ðàâåíñòâî
d a b R T A B( , ) ( ( , ))� �2 1 . (7)
Ïîíÿòíî, ÷òî îòíîøåíèå T ÿâëÿåòñÿ ðåôëåêñèâíûì, ò.å. � �A X
âûïîëíÿåòñÿ ðàâåíñòâî T A A( , ) �1.
Îïðåäåëåíèå 2. Ïóñòü A è B
ÿâëÿþòñÿ íå÷åòêèìè òî÷êàìè èç
ìíîæåñòâà X F E p� ( ). Åñëè ïðè
ôèêñèðîâàííîì çíà÷åíèè ��( , ]0 1
óäîâëåòâîðÿåòñÿ íåðàâåíñòâî
T A B( , ) � �, (8)
òî òî÷êè A è B íàçîâåì
�-ñîñåäíèìè íå÷åòêèìè
òî÷êàìè: A B~ � (ñì. ðèñ. 2).
Îïðåäåëåíèå 3.Åñëè ïðè
ôèêñèðîâàííîì çíà÷åíèè
��( , ]0 1 ìåæäó íå÷åòêèìè
òî÷êàìè A è B èìååòñÿ
ïîñëåäîâàòåëüíîñòü íå÷åòêèõ
�-ñîñåäíèõ òî÷åê C C kk1 0, . . ., , � , ò.å.
A C C C C Ck k~ , ~ , . . ., ~� � �
1 1 2 1� è C Bk ~ � ,
òî íå÷åòêèå òî÷êè A è B íàçîâåì íå÷åòêèìè �-ñâÿçàííûìè òî÷êàìè.
Îïðåäåëåíèå 4. Ïóñòü X F E p� ( ) ÿâëÿåòñÿ ìíîæåñòâîì íå÷åòêèõ òî÷åê.
Åñëè ïðè ôèêñèðîâàííîì çíà÷åíèè ��( , ]0 1 äëÿ ëþáûõ A B X, � íå÷åòêèå òî÷êè
A è B ÿâëÿþòñÿ �-ñâÿçàííûìè, òî ìíîæåñòâî X íàçîâåì íå÷åòêèì �-ñâÿçàííûì
ìíîæåñòâîì.
Ëåììà 1.Äëÿ òîãî ÷òîáû ïðè ôèêñèðîâàííîì ��( , ]0 1 íå÷åòêèå òî÷êè
A a R� ( , ) è B b R� ( , ) áûëè �-ñîñåäíèìè, íåîáõîäèìî è äîñòàòî÷íî âûïîëíåíèå
íåðàâåíñòâà
d a b R( , ) ( )� �2 1 � , (9)
ãäå d a b( , ) — ðàññòîÿíèå ìåæäó öåíòðàìè íå÷åòêèõ òî÷åê A è B.
Ëåììà 2. Äëÿ òîãî ÷òîáû äëÿ íåêîòîðîãî ��( , ]0 1 íå÷åòêèå òî÷êè A è B
áûëè �-ñîñåäíèìè, íåîáõîäèìî è äîñòàòî÷íî âûïîëíåíèå îòíîøåíèÿ
A B� �� ��. (10)
Äîêàçàòåëüñòâà ýòèõ óòâåðæäåíèé èìåþòñÿ â ðàáîòå [6].
Ïóñòü îòíîøåíèå � : [ , ]T X X�
0 1 ÿâëÿåòñÿ òðàíçèòèâíûì çàìûêàíèåì
íå÷åòêîãî îòíîøåíèÿ T X X: [ , ]�
0 1 . Ïðè îïðåäåëåíèè òðàíçèòèâíîãî
çàìûêàíèÿ áóäåì ïðåäïîëîãàòü êëàññè÷åñêóþ max–min-êîìïîçèöèþ íå÷åòêèõ
îòíîøåíèé. Ñëåäóþùàÿ òåîðåìà çàäàåò ìåòîä îïðåäåëåíèÿ �-ñâÿçàííîñòè ìåæäó
ëþáûìè çàäàííûìè íå÷åòêèìè òî÷êàìè.
Òåîðåìà 1. Íåáõîäèìûì è äîñòàòî÷íûì óñëîâèåì �-ñâÿçàííîñòè ëþáûõ
13 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
Ðèñ. 2. Íå÷åòêèå �-ñîñåäíèå òî÷êì A a R� ( , ) è B b R� ( , )
â ïðîñòðàòñòâå E2
íå÷åòêèõ òî÷åê A B X, � êîíå÷íîãî ìíîæåñòâà X ïðè ôèêñèðîâàííîì ��( , ]0 1
ÿâëÿåòñÿ íåðàâåíñòâî
� ( , )T A B � �. (11)
Äîêàçàòåëüñòâî òåîðåìû èìååòñÿ â ðàáîòå [6].
3. ÏÎÌÅÕÎÓÑÒÎÉ×ÈÂÛÉ ÀËÃÎÐÈÒÌ ÌÅÒÎÄÀ ÍÅ×ÅÒÊÈÕ ÑÂßÇÀÍÍÛÕ ÒÎ×ÅÊ
Äëÿ ðåøåíèÿ çàäà÷è (1), (2) ïðåäëàãàåòñÿ ñëåäóþùèé àëãîðèòì, ÿâëÿþùèéñÿ
ïîìåõîóñòîé÷èâûì âàðèàíòîì àëãîðèòìà íå÷åòêèõ ñâÿçàííûõ òî÷åê (Fuzzy
Joint Points — FJP), èçëîæåííîãî â ðàáîòå [6]. Ýòîò àëãîðèòì âû÷èñëÿåò
ïîäõîäÿùåå çíà÷åíèå ÷åòêîñòè �, ñîîòâåòñòâóþùåå êîëè÷åñòâî êëàññîâ k, à
òàêæå ðàçáèåíèå èñõîäíîãî ìíîæåñòâà X x x xn� { }1 2, , . . ., íà êëàññû
X X X k1 2, , . . ., , óäîâëåòâîðÿþùèå îòíîøåíèÿì (1) è (2). Ïðè ýòîì
X X X k1 2, , . . ., ÿâëÿþòñÿ íå÷åòêèìè �-ñâÿçàííûìè ìíîæåñòâàìè.Ïóñòü N x( )
— íå÷åòêîå ñîñåäñòâî çàäàííîé òî÷êè x X� íà îñíîâå îòíîøåíèÿ T , ò.å.
N x y T x y y X( ) ( , ( , ))|� �{ } (12)
N x y X T x y( , ) | ( , )� �1 1� � �{ } (13)
ÿâëÿåòñÿ �1-óðîâíåâûì ìíîæåñòâîì íå÷åòêîãî ìíîæåñòâà N x( ), ò.å. íå÷åòêèì
�1-ñîñåäñòâîì òî÷êè x X� .
Îïðåäåëåíèå 5. Òî÷êà x X� íàçûâàåòñÿ òî÷êîé øóìà ñ ïàðàìåòðàìè � �1 2,
äëÿ çàäàííûõ �1 0� è �2 0� , åñëè óäîâëåòâîðÿåòñÿ íåðàâåíñòâî card N x( , )� �1 2� ,
ãäå card N x T x y
y N x
( , ) ( , )
( , )
�
�
1
1
�
�
ÿâëÿåòñÿ íå÷åòêîé ìîùíîñòüþ ìíîæåñòâà
N x( , )�1 .
Ïðåäëîæåííûé íèæå àëãîðèòì FJP ÿâëÿåòñÿ ïîìåõîóñòîé÷èâûì. Åñëè â
äàííîì àëãîðèòìå äëÿ çàäàííîé òî÷êè íå÷åòêàÿ ìîùíîñòü åãî íå÷åòêîãî
�1-ñîñåäñòâà ìåíüøå �2 , òî ýòà òî÷êà âîñïðèíèìàåòñÿ â êà÷åñòâå øóìà. Îòìåòèì,
÷òî íàñòðîéêîé ïàðàìåòðîâ �1 è �2 ìîæíî ðåãóëèðîâàòü ÷óâñòâèòåëüíîñòü
àëãîðèòìà FJP ê ïîìåõàì. Î÷åâèäíî, ÷òî ïðèíèìàÿ �2 0� , ìîæíî çàãëóøèòü
ïîìåõîóñòîé÷èâîñòü àëãîðèòìà.
Ïîìåõîóñòîé÷èâûé FJP-àëãîðèòì
Øàã 1 . Âû÷èñëèòü d d x x i j n d dij i j
i j n
ij: ( , ), , , ; : ;
, ,
� � �
�
1
1
max max
�: ,
, ,
� �
�
0 01
1
min
i j n
ijd . Óñòàíîâèòü çíà÷åíèÿ �1 è �2 . Ïóñòü � 0 1:� .
Øàã 2.Âû÷èñëèòü íå÷åòêîå îòíîøåíèå T
d
d
i j nij
ij
: , , ,� � �1 1
max
.
Øàã 3.Âûçâàòü ïðîöåäóðó NoiseFilter( , )� �1 2 äëÿ ðàçáèåíèÿ èñõîäíîãî
ìíîæåñòâà X íà ÿäðî X core è øóì X noise , ò.å. X X Xcore noise� � ,
X Xcore noise� ��. Âû÷èñëèòü òðàíçèòèâíîå çàìûêàíèå �T îòíîøåíèÿ T íà
ìíîæåñòâå X core .
Øàã 4.Ïóñòü nc — êîëè÷åñòâî ýëåìåíòîâ X core; îáîçíà÷èòü:
y x i n t k ni i c c: , , ; : ; :� � � �1 1 .
Øàã 5. Âû÷èñëèòü d y y d x x x y x yi j i j( , ) ( , )| ,� � � � �� � ��min{ }, i j k, ,�1 ;
d d y yt
i j
i j: ( , )�
�
min ; �
�
t
td
d
: ,� �
�
�
�
�
�
�
max
max
1 0 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 14
Øàã 6. Âûçâàòü ïðîöåäóðó Clusters t( )� äëÿ âû÷èñëåíèÿ íå÷åòêèõ � t -
ñâÿçàííûõ ìíîæåñòâ X X X k1 2, , . . ., ñ íå÷åòêèìè òî÷êàìè êîíóñíîé ôîðìû
x
d
i ni c, , ,max
2
1
�
�
!
"
# � , è äëÿ îïðåäåëåíèÿ êîëè÷åñòâà k ýòèõ ìíîæåñòâ äëÿ
çàäàííîãî çíà÷åíèÿ � t .
Øàã 7.Åñëè k �1, òî îáîçíà÷èòü y Xi
i:� , i k�1, ; t t� �1è ïåðåéòè íà øàã 5.
Åñëè k �1, òî ïåðåéòè íà øàã 8.
Øàã 8. Âû÷èñëèòü $� � �i i i:� � � 1, i t z
i t
i� � �
� �
0 1
0 1
, ; :
,
arg max $� ;
� � �:� �z .
Øàã 9. Âûçâàòü ïðîöåäóðó Clusters( )� ñ ïàðàìåòðîì �.
Øàã 10. � — îïòèìàëüíîå çíà÷åíèå óðîâíÿ ÷åòêîñòè êëàñòåðèçàöèè; k —
îïòèìàëüíîå êîëè÷åñòâî êëàñòåðîâ; X X k1, . . ., — îïòèìàëüíîå ðàçáèåíèå
ìíîæåñòâà X .
Øàã 11. Äëÿ êàæäîãî ýëåìåíòà x X noise� ïîâòîðèòü øàã 12.
Øàã 12. Âû÷èñëèòü k dist x X k kk* ( , )| , . . .,� �arg min{ }1 ; ýëåìåíò x îòíåñòè
ê ìíîæåñòâó X k*
.
End.
Ïðîöåäóðà NoiseFilter( , )� �1 2 èñïîëüçóåòñÿ äëÿ ðàçáèåíèÿ èñõîäíîãî
ìíîæåñòâà X íà äâà íåïåðåñåêàþùèåñÿ ìíîæåñòâà ÿäðà X core è øóìà X noise , ò.å.
X X X X Xcore noise core noise� � � ��, .
ÏðîöåäóðàNoiseFilter( , )� �1 2 :
Âõîäíûå ïàðàìåòðû: �1 è �2 .
Âûõîäíûå ïàðàìåòðû:ìíîæåñòâà X core è X noise .
Øàã 1.Ïóñòü X x x xn% { }1 2, , . . ., ÿâëÿåòñÿ ìíîæåñòâîì èñõîäíûõ òî÷åê,
X noise ��.
Øàã 2.Äëÿ êàæäîé òî÷êè x X� ïîâòîðèòü øàãè 3 è 4.
Øàã 3. Âû÷èñëèòü card N x T x y
y N x
( , ) ( , )
( , )
�
�
1
1
�
�
.
Øàã 4. Åñëè cardN x( , )� �1 2� , òî x ïîìåòèòü êàê òî÷êó øóìà:
X X xnoise noise:� �{ }.
Øàã 5.Îáîçíà÷èòü X X Xcore noise: \� .
Øàã 6. Âîçâðàòèòü ìíîæåñòâà X core è X noise .
End.
Ïðîöåäóðà Clusters(�) ðàçáèâàåò ìíîæåñòâî X x x xn� { }1 2, , . . ., íà íå÷åòêèå
�-ñâÿçàííûå ìíîæåñòâà äëÿ âõîäíîãî ïàðàìåòðà �, âîçâðàùàåò ýòè ìíîæåñòâà è
êîëè÷åñòâî ýòèõ ìíîæåñòâ.
Ïðîöåäóðà Clusters(�):
Âõîäíîé ïàðàìåòð:�.
Âûõîäíûå ïàðàìåòðû:ìíîæåñòâà X X X k1 2, , . . ., , îòðàæàþùèå ãîìîãåí-
íûå êëàññû íå÷åòêèõ �-ñâÿçàííûõ òî÷åê; k — êîëè÷åñòâî ýòèõ êëàññîâ.
Øàã 1. S X x x xn: , , . . .,� � { }1 2 ; k :�1.
15 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
Øàã 2. Âûáèðàòü ýëåìåíò A S� ìíîæåñòâà S . Îáðàçîâàòü ìíîæåñòâà:
X B S T A Bk : | � ( , )� � �{ }� ; S S k: \� .
Øàã 3. Åñëè S ��, òî îáîçíà÷èòü k k:� �1 è ïåðåéòè ê øàãó 2; â ïðîòèâíîì
ñëó÷àå ïåðåéòè ê øàãó 4.
Øàã 4. Âîçâðàòèòü ìíîæåñòâà X X X k1 2, , . . ., è êîëè÷åñòâî k ýòèõ
ìíîæåñòâ.
End.
Îòìåòèì, ÷òî â àëãîðèòìå FJP äëÿ íîðìàëèçàöèè íå÷åòêîãî îòíîøåíèÿ
T X X: [ , ]�
0 1 ðàäèóñ ðàññìàòðèâàåìûõ íå÷åòêèõ òî÷åê ïðåäïîëàãàåòñÿ â âèäå
R
d x x x x X di j i j
�
�
%
max{ }
max
( , ) | ,
.
2 2
Òàêèì îáðàçîì, � �A B X, ñòåïåíü âûïîëíåíèÿ îòíîøåíèÿ T îïðåäåëèòñÿ
êàê
T A B
d a b
d
( , )
( , )
;� �1
max
(14)
ñëåäîâàòåëüíî, d a b d T A B( , ) ( ( , ))� �max 1 .
Ïóñòü X k , k t�1, , — ãîìîãåííûå êëàññû, ñôîðìèðîâàííûå â ðåçóëüòàòå
êëàñòåðèçàöèè. Çàäàäèì ñëåäóþùèå îáîçíà÷åíèÿ (ñì. ðèñ. 3):
d d T x y
k
in
x y Xk
� � �
�
max
,
( min � ( , ))1 ,
d din
k k
in
max max� ,
d d X Xout
i j
i j
min
min�
�
( , ),
d d X Xout
i j
i j
max max�
�
( , ),
ãäå �T — òðàíçèòèâíîå çàìûêàíèå
îòíîøåíèÿ T .
Êðèòåðèé äëÿ íàõîæäåíèÿ
îïòèìàëüíîé ñòðóêòóðû êëàññîâ
îñíîâûâàåòñÿ íà ìàêñèìàëüíîñòè
øèðîòû èçìåíåíèÿ �-óðîâíåé, äëÿ
êîòîðûõ êîëè÷åñòâî êëàññîâ íå ìåíÿåòñÿ. Äðóãèìè ñëîâàìè, â êà÷åñòâå
îïòèìàëüíîé ïðèíèìàåòñÿ ñòðóêòóðà êëàññîâ, äëÿ êîòîðîé óäîâëåòâîðÿåòñÿ
V d dFJP
out in% �
min max max. (15)
 òàáë. 1 òàêæå îòðàæåíû äðóãèå ñóùåñòâóþùèå â ëèòåðàòóðå îñíîâíûå
êðèòåðèè îïðåäåëåíèÿ îïòèìàëüíîãî êîëè÷åñòâà êëàññîâ ïðè êëàñòåðèçàöèè [7].
Ïðè ýòîì èñïîëüçîâàíû ñëåäóþùèå îáîçíà÷åíèÿ: uij — ñòåïåíü ïðèíàäëåæíîñòè
ýëåìåíòà x j ê i-ìó êëàññó, vi — öåíòð êëàññà i, �( )ui — äèàìåòð êëàññà i, mX —
öåíòð ìíîæåñòâà âñåõ òî÷åê X .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 16
Ðèñ. 3. Ðàñïîëîæåíèå ãîìîãåííûõ ìíîæåñòâ,
âûçûâàåìûõ àëãîðèòìîì FJP
Ò à á ë è ö à 1 . Êðèòåðèè äëÿ îïðåäåëåíèÿ îïòèìàëüíîãî êîëè÷åñòâà êëàññîâ
Íàçâàíèå êðèòåðèÿ Ôóíêöèîíàëüíîå âûðàæåíèå
Íàèëó÷øàÿ
êëàñòåðèçàöèÿ
Êîýôôèöèåíò ðàçáèåíèÿ
(Partition coefficient)
V
n
uPC
i
c
j
n
ij
�
� �
1
1 1
2
max( , , )V U cPC
Ýíòðîïèÿ êëàñòåðèçàöèè
(Classification entropy)
V
n
u uCE
i
c
j
n
ij a ij� �
� �
1
1 1
log min ( , , )V U cCE
Êðèòåðèè Ôóêóÿíî–Ñóãåíî
(Fukuyamo-Sugeno criteria)
V u d x v d m vFS
i
c
j
n
ij
m
j i X im
� �
� �
1 1
2 2[ ( , ) ( , )] min ( , , )V U cFS
Èíäåêñ ðàçäåëåíèÿ
(Separation index)
V
d u u
u
SI
i k k i
i k
i
i
�
�
max min
min
,
( , )
( )�
max( , )V USI
Êðèòåðèé FJP
(FJP criteria)
V d dFJP
out in
� �
min max max( , )V UFJP
Ïðèâåäåííàÿ íèæå òåîðåìà îïðåäåëÿåò äîñòàòî÷íîå óñëîâèå êîððåêòíîé
êëàñòåðèçàöèè äàííûõ ñ ïîìîùüþ àëãîðèòìà FJP.
Òåîðåìà 2.Åñëè èìååòñÿ íåêîòîðàÿ ñêðûòàÿ ñòðóêòóðà ìíîæåñòâà X ñ
âîçìîæíûì ðàçáèåíèåì (1), (2), óäîâëåòâîðÿþùèì ñîîòíåøåíèÿì
d
d
d d
d
in
out
out in
out
max
min
min max
max
� �
�1
2
, (16)
òî àëãîðèòì FJP ðàñïîçíàåò ýòî ðàçáèåíèå êàê îïòèìàëüíîå.
Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî èìååòñÿ ñêðûòàÿ ñòðóêòóðà ñ âîçìîæíûì
ðàçáèåíèåì, óäîâëåòâîðÿþùèì ñîîòíîøåíèÿì (16). Çíà÷åíèÿ �, ïîëó÷åííûå â ðå-
çóëüòàòå öèêëè÷åñêîãî ïðèìåíåíèÿ øàãîâ 5–7 ïîìåõîóñòîé÷èâîãî àëãîðèòìà FJP,
îáîçíà÷èì � � �0 1, , . . ., t . Ñîãëàñíî ôîðìóëå (7) êàæäîìó çíà÷åíèþ ñòåïåíåé
� i i t, ,� 0 , ñîîòâåòñòâóåò íåêîòîðîå çíà÷åíèå ðàäèóñà îêðóæíîñòè, êîòîðîå
îïðåäåëÿåò �-óðîâíåâîå ìíîæåñòâî. Ïî óòâåðæäåíèþ ëåììû 2 ïåðåñå÷åíèÿìè ýòèõ
�-óðîâíåâûõ ìíîæåñòâ îïðåäåëÿåòñÿ ìíîæåñòâî �-ñîñåäíèõ íå÷åòêèõ òî÷åê äëÿ
çàäàííîé ñòåïåíè. Êàê âèäíî èç ôîðìóëû (7), ñ óìåíüøåíèåì ñòåïåíè � � T A B( , )
ðàäèóñ ýòèõ îêðóæíîñòåé óâåëè÷èâàåòñÿ.
Ïîíÿòíî, ÷òî åñëè àëãîðèòìîì FJP ïîëó÷åíî íåêîòîðîå ðàçáèåíèå
ìíîæåñòâà X , òî âûïîëíÿåòñÿ íåðàâåíñòâî
d d din out out
max min max� �
è íåò òàêèõ òî÷åê x y X, � , ÷òîáû âûïîëíÿëîñü íåðàâåíñòâî
d d x y din out
max min
� �( , ) .
Ñëåäîâàòåëüíî, â ïîñëåäîâàòåëüíîñòè çíà÷åíèé ñòåïåíåé � i , i t� 0, ,
ñãåíåðèðîâàííûõ øàãîì 5 ïîìåõîóñòîé÷èâîãî àëãîðèòìà FJP, íåêîòîðûå
ïîñëåäîâàòåëüíûå çíà÷åíèÿ � z è � z � 1 áóäóò ñîîòâåòñòâîâàòü çíà÷åíèÿì
äèñòàíöèé d in
max è d out
min
. Çíà÷åíèÿ ñòåïåíåé îòíîøåíèÿ T , ñîîòâåòñòâóþùèå
çíà÷åíèÿì ðàññòîÿíèé 0 0� d , d din out
max min
, è d out
max , îáîçíà÷èì ÷åðåç 1 0 1 2� � � �, ,
è � 3 ñîîòâåòñòâåííî.
Ñîãëàñíî øàãàì 8–10 äëÿ òîãî ÷òîáû àëãîðèòì FJP âûäàâàë ïðåäïîëîãàåìîå
17 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
âûøå ðàçáèåíèå â êà÷åñòâå îïòèìàëüíîãî, äîëæíî âûïîëíÿòüñÿ ðàâåíñòâî
� � � � � �1 2
1
0 1
� � � � ��
� �
$ $z z z
i t
imax
,
.
Ïðåäïîëîæèì, ÷òî íåðàâåíñòâà (16) âûïîëíÿþòñÿ. Ñíà÷àëà ðàññìîòðèì ïåðâóþ
÷àñòü ýòèõ íåðàâåíñòâ. Ïóñòü óäîâëåòâîðÿåòñÿ íåðàâåíñòâî
d
d
in
out
max
min
�
1
2
. Îòñþäà,
ó÷èòûâàÿ d0 0� , ìîæíî çàïèñàòü ñëåäóþùóþ öåïî÷êó íåðàâåíñòâ:
2 0d d d d d d d din out in out in in
max min max min max max m
�
� �
� �
in max
out ind� . (17)
Ñ ó÷åòîì îòíîøåíèÿ (14) èìååì
� �0 1 01 1� � �
�
�
!
"
## � �
�
�
!
"
#
#
�
d
d
d
d
din in
max
max
max
max � d
d
0
max
è
� �1 2 1 1� � �
�
�
!
"
#
#
� �
�
�
!
"
#
#
�
d
d
d
d
din out
max
max
min
max
min max
max
out ind
d
�
. (18)
Ñîãëàñíî (17) ïîëó÷àåì, ÷òî
� � � �0 1 1 2� � � .
Òîãäà � �� � � �i j, [ , ]1 0 ñïðàâåäëèâî íåðàâåíñòâî
| |� � � � � �i j� � � � �0 1 1 2 .
Ñëåäîâàòåëüíî, � ��� � � �i i, [ , ]1
1 0 ñïðàâåäëèâî íåðàâåíñòâî
� � � �i i� � �� 1
1 2 . (19)
Äàëåå ðàññìîòðèì âòîðóþ ÷àñòü íåðàâåíñòâà (16). Ïóñòü âûïîëíÿåòñÿ
íåðàâåíñòâî
1
2
�
�d d
d
out in
out
min max
max
.
Îòñþäà âûòåêàåò
d d dout out in
max min max� �2( ).
Ñëåäîâàòåëüíî,
d d d d d dout out out in out in
max min min max min max� � � � �2 ,
ò.å.
d d d dout out out in
max min min max� � � . (20)
Ïåðåõîäÿ íà îòíîøåíèå T , ìîæíî çàïèñàòü
� �2 3 1 1� � �
�
�
!
"
#
#
� �
�
�
!
"
#
#
�
d
d
d
d
out out
min
max
max
max
d d
d
out out
max min
max
�
. (21)
Ó÷èòûâàÿ ðàâåíñòâà (21) è (18), èç íåðàâåíñòâà (20) ïîëó÷àåì
� � � �2 3 1 2� � � . Òîãäà � �� � � �i j, [ , ]3 2 ñïðàâåäëèâî íåðàâåíñòâî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 18
| |� � � � � �i j� � � � �2 3 1 2 .
Ñëåäîâàòåëüíî, � ��� � � �i i, [ , ]1
3 2 ñïðàâåäëèâî íåðàâåíñòâî
� � � �i i� � �� 1
1 2 . (22)
Òàêèì îáðàçîì, èç (19) è (22) ñëåäóåò, ÷òî
� � �1 2
0 1
� �
� �
max
i t
i
,
$ .
Ýòèì çàâåðøàåòñÿ äîêàçàòåëüñòâî òåîðåìû.
Îòìåòèì, ÷òî äîêàçàííàÿ âûøå òåîðåìà èìååò íåïîñðåäñòâåííîå îòíîøåíèå
ê ïðîñòîìó àëãîðèòìó FJP, ïðåäëîæåííîìó â [6]. Äëÿ ïîìåõîóñòîé÷èâîãî
âàðèàíòà àëãîðèòìà FJP, ïðåäëîæåííîãî â íàñòîÿùåé ñòàòüå, óñëîâèÿ òåîðåìû 2
äîëæíû âûïîëíÿòüñÿ òîëüêî äëÿ òî÷åê ÿäåð êëàññîâ.
4. ÂÛ×ÈÑËÈÒÅËÜÍÛÅ ÝÊÑÏÅÐÈÌÅÍÒÛ
Ïîâåäåíèå ïîìåõîóñòîé÷èâîñòè àëãîðèòìà FJP è êîððåêòíîñòü åãî ðàáîòû áóäåì
äåìîíñòðèðîâàòü íà áàçàõ äàííûõ ñ ðàçëè÷íûìè êîíôèãóðàöèÿìè, ïðåäñòàâëåííû-
ìè â [13]. Èñïîëüçóåìûå àëãîðèòìû çàïðîãðàììèðîâàíû íà ÿçûêå Ñ++ äëÿ ïåðñî-
íàëüíûõ êîìïüþòåðîâ òèïà Pentium IV è ïðîâåäåíû âû÷èñëèòåëüíûå ýêñïåðèìåí-
òû. Íà ðèñ. 4–6 îòðàæåíû ðåçóëüòàòû ðàáîòû ïðîãðàìì, ãäå òî÷êè ÿäåð êëàññîâ
ïîêàçàíû öèôðàìè 0, 1, 2, à òî÷êè øóìà — áîëåå æèðíûìè êâàäðàòàìè. Òàê êàê
êëàññû ñìåøàíû ìíîæåñòâàìè òî÷åê ïîìåõà, ðàáîòà àëãîðèòìà FJP áåç ìåõàíèçìà
ïîìåõîóñòîé÷èâîñòè (ñì. [6]) áóäåò äàâàòü íåêîððåêòíûå ðåçóëüòàòû. Êàê âèäíî
èç ðèñ. 4–6, ðåçóëüòàò ïðåäëîæåííîãî â íàñòîÿùåé ñòàòüå ïîìåõîóñòîé÷èâîãî
âàðèàíòà àëãîðèòìà FJP ÿâëÿåòñÿ êîððåêòíûì. Îòìåòèì, ÷òî ïðè ðàáîòå
àëãîðèòìà ñíà÷àëà îïðåäåëÿþòñÿ ÿäðà êëàññîâ, à çàòåì êàæäàÿ òî÷êà øóìà
ïåðåäàåòñÿ áëèæàéøåìó ÿäðó.
19 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
Ðèñ. 4. Ðåçóëüòàò êëàñòåðèçàöèè ÁÄ-1 ñ ïàðàìåòðàìè � �1 20 9 0 2� �, , , , ãäå ïîëó÷åíî
îïòèìàëüíîå çíà÷åíèå � � 0 9208,
Äàííûå ñ íåñáàëàíñèðîâàííûì ðàñïðåäåëåíèåì (ÁÄ-1). Âíà÷àëå
ðàññìîòðèì áàçó äàííûõ ñ êëàññàìè, ñóùåñòâåííî ðàçëè÷àþùèìèñÿ ïî
êîëè÷åñòâó òî÷åê. Ðåçóëüòàò êëàñòåðèçàöèè ïîìåõîóñòîé÷èâûì àëãîðèòìîì FJP
ñ ïàðàìåòðàìè � �1 209 02� �. , . , ãäå ïîëó÷åíî îïòèìàëüíîå çíà÷åíèå � � 09208. ,
ôèêñèðóåò ðèñ. 4.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 20
Ðèñ. 5. Ðåçóëüòàò êëàñòåðèçàöèè ÁÄ-2 ñ ïàðàìåòðàìè � �1 20 9 0 45� �, , , , ãäå ïîëó÷åíî
îïòèìàëüíîå çíà÷åíèå � � 0 9787,
Ðèñ. 6. Ðåçóëüòàò êëàñòåðèçàöèè ÁÄ-2 ñ ïàðàìåòðàìè � �1 20 9 0 3� �, , , , ãäå ïîëó÷åíî
îïòèìàëüíîå çíà÷åíèå � � 0 9405,
Äàííûå ñ ýëëèïòè÷åñêèìè ðàñïðåäåëåíèÿìè (ÁÄ-2). Íà ðèñ. 5 îòðàæåíà
áàçà äàííûõ, ãäå êëàññû èìåþò ïðèáëèçèòåëüíî îäèíàêîâûå ðàçìåðû
ñ ýëëèïòè÷åñêèìè ôîðìàìè è ïðèâåäåí ðåçóëüòàò ðàáîòû àëãîðèòìà ñ
ïàðàìåòðàìè � �1 209 0 45� �. , . , ãäå ïîëó÷åíî îïòèìàëüíîå çíà÷åíèå � � 09787. .
Äàííûå ñ ëèíåéíî íåðàçäåëèìûì ðàñïðåäåëåíèåì (ÁÄ-3). Ðàññìîòðèì
áàçó äàííûõ ñ êîíôèãóðàöèåé, ãäå êëàññû íå ìîãóò áûòü ðàçäåëåíû ïðÿìîé
ëèíèåé. Ðåçóëüòàò ðàáîòû ïîìåõîóñòîé÷èâîãî àëãîðèòìà FJP äëÿ ÁÄ-3 ñ
ïàðàìåòðàìè � �1 209 03� �. , . , ãäå ïîëó÷åíî îïòèìàëüíîå çíà÷åíèå � � 09465. ,
îòðàæåí íà ðèñ. 6.
Âèçóàëüíîå íàáëþäåíèå ðàñïîëîæåíèÿ äàííûõ íà ðèñ. 4–6 ïîäòâåðæäàåò
ñïðàâåäëèâîñòü êîëè÷åñòâà êëàññîâ è èõ ñòðóêòóðó, ðàñïîçíàâàåìûõ àëãîðèòìîì
FJP. Îòìåòèì, ÷òî, êàê ïðàâèëî, êëàññè÷åñêèé àëãîðèòì êëàñòåðèçàöèè FCM
(Fuzzy c-Means) äàåò íåàäåêâàòíûå ðåçóëüòàòû ïðè êëàñòåðèçàöèè áàç äàííûõ
òèïà ÁÄ-1 è ÁÄ-3 [14].
ÇÀÊËÞ×ÅÍÈÅ
 íàñòîÿùåé ñòàòüå áûë ïðåäëîæåí ïîìåõîóñòîé÷èâûé âàðèàíò àëãîðèòìà
FJP. Êàê áûëî ïîêàçàíî, îñíîâíûì äîñòîèíñòâîì ïðåäëîæåííîãî àëãîðèòìà
ÿâëÿåòñÿ âîçìîæíîñòü ðåãóëèðîâêè ïîìåõîóñòîé÷èâîñòè êëàñòåðèçàöèè è
àâòîìàòè÷åñêîãî îïðåäåëåíèÿ êîëè÷åñòâà êëàññîâ. Áûëè èñïîëüçîâàíû ïîíÿòèÿ
íå÷åòêîé òî÷êè êîíóñíîé ôîðìû, íå÷åòêèõ �-ñîñåäíèõ è íå÷åòêèõ
�-ñâÿçàííûõ òî÷åê, ïðîâåäåíû èññëåäîâàíèÿ íåêîòîðûõ ñâîéñòâ îòíîñèòåëüíî
ýòèõ ïîíÿòèé. Äîêàçàíî äîñòàòî÷íîå óñëîâèå ïðàâèëüíîãî ðàñïîçíàâàíèÿ
àëãîðèòìîì FJP èìåþùåéñÿ ñêðûòîé ñòðóêòóðû ðàñïîëîæåíèÿ êëàññîâ ïðè
êëàñòåðèçàöèè.
Îòìåòèì, ÷òî ðàññìîòðåííûé àëãîðèòì ìîæåò áûòü èñïîëüçîâàí êàê â êà÷åñòâå
ïîäãîòîâèòåëüíîãî ýòàïà êëàññè÷åñêîãî àëãîðèòìà íå÷åòêîé êëàñòåðèçàöèè FCM
äëÿ îïðåäåëåíèÿ íà÷àëüíûõ êëàññîâ è èõ êîëè÷åñòâà, òàê â êà÷åñòâå
ñàìîñòîÿòåëüíîãî àëãîðèòìà êëàñòåðèçàöèè è ðàñïîçíàâàíèÿ îáðàçîâ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. H a n J . , K a m b e r M . Data mining: concepts and techniques. — San Diego: Acad. Press, 2001.
— 550 p.
2. D u m i t r e s c u D . , L a z z e r i n i B . , J a i n L . C . Fuzzy sets and their application to clustering
and training. — New York: CRC Press LLC, 2000. — 622 p.
3. Í à ñ è á î â Ý . Í . Èäåíòèôèêàöèÿ ñîñòîÿíèé ñëîæíûõ ñèñòåì ñ îöåíêîé äîïóñòèìîé
ïîãðåøíîñòè èçìåðåíèé ïðè íå÷åòêîé èíôîðìàöèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
2002. — 38, ¹ 1. — Ñ. 63–71.
4. Í à ñ è á î â Ý . Í . Îá îäíîé çàäà÷å èäåíòèôèêàöèè ñîñòîÿíèé ñèñòåìû ïî íå÷åòêèì
çíà÷åíèÿì èíôîðìàòèâíûõ ïðèçíàêîâ // Àâòîìàòèêà è âû÷èñë. òåõíèêà. — 2002. — 36,
¹ 2. — Ñ. 33–40.
5. N a s i b o v E . N . , U l u t a g a y G . Program tools for fuzzy clustering analysis // Proc. Intern. Sci-
entific Conf. «Inform. Tech. and Telecomm. in Educ. and Science». — Antalya (Turkey), 2006. —
Ð. 195–197.
6. Í à ñ è á î â Ý . Í . , Ó ë ó ò à ã à é Ã . Íîâûé ïîäõîä ê ïðîáëåìå êëàñòåðèçàöèè ñ
èñïîëüçîâàíèåì ìåòîäà íå÷åòêèõ ñâÿçàííûõ òî÷åê // Àâòîìàòèêà è âû÷èñë. òåõíèêà. — 2005.
— 39, ¹ 6. — Ñ. 11–21.
7. P a l N . R . , B e z d e k J . C . On cluster validity for the fuzzy C-means model // IEEE Trans. on
Fuzzy Systems. — 1995. — 3, N 3. — Ð. 370–379.
8. Z a h i d N . , A b o u e l a l a O . , L i m o u r i M . , E s s a i d A . Fuzzy clustering based on K-near-
21 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1
est-neighbours rule // Fuzzy Sets and Systems. — 2001. — 120. — Ð. 239–247.
9. V e l t h u i z e n R . P . , H a l l L . O . , C l a r k e L . P . , S i l b i g e r M . L . An investigation of
mountain method clustering for large data sets // Pattern Recognition. — 1997. — 30, N 7. —
Ð. 1121–1135.
10. Y a g e r R . R . , F i l e v D . P . Approximate clustering via the mountain method // IEEE Trans. on
Systems, Man and Cybernetics. — 1994. — 24, N 8. — Ð. 1279–1284.
11. D u n n J . C . A fuzzy relative of the ISODATA process and its use in detecting compact well-sepa-
rated clusters // Cybernetics. — 1973. — 3, N 3. — Ð. 32–57.
12. H a m m a h R . E . , C u r r a n J . H . On distance measures for the fuzzy K-means algorithm for
joint data // Rock Mech. Rock Eng. — 1999. — 32, N 1. — Ð. 1–27.
13. T a o C . W . Unsupervised fuzzy clustering with multi-center clusters // Fuzzy Sets and Systems. —
2002. — 128. — Ð. 305–322.
14. B e n s a i d A . M . , H a l l L . O . , B e z d e k J . C . e t a l . Validity-Guided (Re)clustering with
applications to image segmentation // IEEE Trans. on Fuzzy Systems. — 1996. — 4, N 2. —
Ð. 112–123.
Ïîñòóïèëà 08.02.2006
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 1 22
|