Контейнерные средства кластеризации и классификации сигналов
Контейнерні засоби кластеризації та класифікаії сигналів застосовуються при синтезі систем розпізнавання образів. Використання властивостей псевдообернених операцій та еліпсоідальних контейнерів дозволяє сформувати зручні для використання правила класифікації сигналів в системах розпізнавання образі...
Saved in:
| Date: | 2009 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Series: | Кибернетика и системный анализ |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/44406 |
| 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: | Контейнерные средства кластеризации и классификации сигналов / Н.Ф. Кириченко, А.С. Корлюк, Ю.Г. Кривонос // Кибернетика и системный анализ. — 2009. — № 5. — С. 111-118. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-44406 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-444062025-02-09T11:45:31Z Контейнерные средства кластеризации и классификации сигналов Контейнерні засоби кластеризації та класифікації сигналів Container methods of clustering and classification of signals Кириченко, Н.Ф. Корлюк, А.С. Кривонос, Ю.Г. Системный анализ Контейнерні засоби кластеризації та класифікаії сигналів застосовуються при синтезі систем розпізнавання образів. Використання властивостей псевдообернених операцій та еліпсоідальних контейнерів дозволяє сформувати зручні для використання правила класифікації сигналів в системах розпізнавання образів. Container methods of clustering and classification of signals are used in synthesizing pattern recognition systems. The use of properties of pseudoreverse operations and generalized ellipsoidal containers allows one to form signal classification rules suitable in pattern recognition systems. 2009 Article Контейнерные средства кластеризации и классификации сигналов / Н.Ф. Кириченко, А.С. Корлюк, Ю.Г. Кривонос // Кибернетика и системный анализ. — 2009. — № 5. — С. 111-118. — Бібліогр.: 7 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44406 519.685.3 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Кириченко, Н.Ф. Корлюк, А.С. Кривонос, Ю.Г. Контейнерные средства кластеризации и классификации сигналов Кибернетика и системный анализ |
| description |
Контейнерні засоби кластеризації та класифікаії сигналів застосовуються при синтезі систем розпізнавання образів. Використання властивостей псевдообернених операцій та еліпсоідальних контейнерів дозволяє сформувати зручні для використання правила класифікації сигналів в системах розпізнавання образів. |
| format |
Article |
| author |
Кириченко, Н.Ф. Корлюк, А.С. Кривонос, Ю.Г. |
| author_facet |
Кириченко, Н.Ф. Корлюк, А.С. Кривонос, Ю.Г. |
| author_sort |
Кириченко, Н.Ф. |
| title |
Контейнерные средства кластеризации и классификации сигналов |
| title_short |
Контейнерные средства кластеризации и классификации сигналов |
| title_full |
Контейнерные средства кластеризации и классификации сигналов |
| title_fullStr |
Контейнерные средства кластеризации и классификации сигналов |
| title_full_unstemmed |
Контейнерные средства кластеризации и классификации сигналов |
| title_sort |
контейнерные средства кластеризации и классификации сигналов |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2009 |
| topic_facet |
Системный анализ |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/44406 |
| citation_txt |
Контейнерные средства кластеризации и классификации сигналов / Н.Ф. Кириченко, А.С. Корлюк, Ю.Г. Кривонос // Кибернетика и системный анализ. — 2009. — № 5. — С. 111-118. — Бібліогр.: 7 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT kiričenkonf kontejnernyesredstvaklasterizaciiiklassifikaciisignalov AT korlûkas kontejnernyesredstvaklasterizaciiiklassifikaciisignalov AT krivonosûg kontejnernyesredstvaklasterizaciiiklassifikaciisignalov AT kiričenkonf kontejnernízasobiklasterizacíítaklasifíkacíísignalív AT korlûkas kontejnernízasobiklasterizacíítaklasifíkacíísignalív AT krivonosûg kontejnernízasobiklasterizacíítaklasifíkacíísignalív AT kiričenkonf containermethodsofclusteringandclassificationofsignals AT korlûkas containermethodsofclusteringandclassificationofsignals AT krivonosûg containermethodsofclusteringandclassificationofsignals |
| first_indexed |
2025-11-25T22:41:31Z |
| last_indexed |
2025-11-25T22:41:31Z |
| _version_ |
1849803924593180672 |
| fulltext |
ÓÄÊ: 519.685.3
Í.Ô. ÊÈÐÈ×ÅÍÊÎ , À.Ñ. ÊÎÐËÞÊ, Þ.Ã. ÊÐÈÂÎÍÎÑ
ÊÎÍÒÅÉÍÅÐÍÛÅ ÑÐÅÄÑÒÂÀ ÊËÀÑÒÅÐÈÇÀÖÈÈ
È ÊËÀÑÑÈÔÈÊÀÖÈÈ ÑÈÃÍÀËÎÂ
Êëþ÷åâûå ñëîâà: êîíòåéíåðíàÿ êëàñòåðèçàöèÿ, ïðîñòðàíñòâî ïðèçíàêîâ, ïðî-
åêöèîííàÿ ìàòðèöà.
ÂÂÅÄÅÍÈÅ
 ðàáîòàõ [1, 2] ïðåäëîæåíû ñðåäñòâà êëàññèôèêàöèè óëüòðàçâóêîâûõ ñèãíàëîâ,
áàçèðóþùèåñÿ íà èñïîëüçîâàíèè ñâîéñòâ ìíîãîìåðíûõ ñôåð â Lp ïðîñòðàíñòâàõ,
êîòîðûå ïîëó÷èëè íàçâàíèå êîíòåéíåðîâ.  äàííîé ðàáîòå ýòè èäåè ïîñòðîåíèÿ
êîíòåéíåðîâ â ïðîñòðàíñòâå ïðèçíàêîâ ðàçâèâàþòñÿ â íàïðàâëåíèè ôîðìèðîâà-
íèÿ êîíòåéíåðîâ â âèäå ìíîãîìåðíûõ ýëëèïñîèäîâ, îïðåäåëåííûõ íà îñíîâå
âçâåøåííûõ ïðîåêöèîííûõ ìàòðèö. Èçâåñòíûå ñâîéñòâà ýòèõ ìàòðèö ïîçâîëèëè
ïî-íîâîìó âçãëÿíóòü íà ðåøåíèå ïðîáëåìû êëàñòåðèçàöèè è êëàññèôèêàöèè ñèã-
íàëîâ â ïðîñòðàíñòâå èíôîðìàöèîííûõ ïðèçíàêîâ.
1. ÂÇÂÅØÅÍÍÛÅ ÏÐÎÅÊÖÈÎÍÍÛÅ ÌÀÒÐÈÖÛ È ÈÕ ÂÎÇÌÓÙÅÍÈß
Ðàññìîòðèì â m-ìåðíîì ïðîñòðàíñòâå ïðèçíàêîâ äëÿ ñèãíàëîâ ìíîæåñòâî òî÷åê
x j R j nm( ) , ,� � 1 . Òîãäà äëÿ ìàòðèöû èìååì
~
(~( ) ~( )), ~( ) ( ) , � ( )X x x n x j x j x x
n
x j
j
n
� � � �
�
�1
1
1
� � �
�
.
(1)
Èññëåäóåì íåêîòîðûå ñâîéñòâà ñëåäóþùåé ìàòðèöû:
R X X XT T
(
~
)
~ ~
� � � , (2)
ãäå
~
X � — ïñåâäîèíâåðñíàÿ ìàòðèöà, ñîîòâåòñòâóþùàÿ ìàòðèöå
~
X .
Èñïîëüçîâàíèå ñèíãóëÿðíîãî ïðåäñòàâëåíèÿ ìàòðèöû
~
,X u j j
T
j
j
r
�
�
� � �
1
r X� rank
~
, ãäå u j j
T
j� � — ñîáñòâåííûå âåêòîðû è çíà÷åíèÿ ñîîòâåòñòâåííî ñîîòíî-
øåíèé
~~
,
~ ~
,XX u u X XT
j j j
T
j j j� �� � � �2 2
u u i j r si
T
j ij i
T
j ij r� � � � � � �� � � � � � �, , , , ,1
1
2
2
2 2 ,
äàåò âîçìîæíîñòü óñòàíîâèòü âàæíûå ãåîìåòðè÷åñêèå ñâîéñòâà ýòèõ âåêòîðîâ è
çíà÷åíèé.
Ñâîéñòâî 1. Êàæäîå ñîáñòâåííîå çíà÷åíèå � j
2 ìàòðèöû
~~
XX T ÿâëÿåòñÿ ñóììîé
êâàäðàòîâ ïðîåêöèé âåêòîðîâ ~( )x j íà îðò u j , ò.å.
� j
T
i
n
x j u j j r2 2
1
1� �
�
� (~ ( ) ( )) , , .
(3)
Ñâîéñòâî 2. R X T(
~
) — âçâåøåííàÿ ïðîåêöèîííàÿ ìàòðèöà, â êîòîðîé äëÿ ïðî-
èçâîëüíîãî âåêòîðà x R m� îáåñïå÷èâàåò íàõîæäåíèå âçâåøåííîé ïðîåêöèè âåêòî-
ðà x x� � íà ëèíåéíóþ îáîëî÷êó, íàòÿíóòóþ íà âåêòîðû ~( ), ,x j j n� 1 , ò.å.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 111
© Í.Ô. Êèðè÷åíêî , À.Ñ. Êîðëþê, Þ.Ã. Êðèâîíîñ, 2009
R X u u u u x i u jT
j j
T
j j j
T T
i
n
j
(
~
) ~ ( ) ( )� �
�
�
�
�
�
�
�
�
�
�� 2
1
2
1
r
j
r
��
�1
, (4)
( � ) (
~
)( � ) (( � ) )x x R X x x x x uT T T
j j
j
r
� � � � �
�
� 2 2
1
� ,
(5)
ãäå � j
�2 — ñîîòâåòñòâóþùèå âåñîâûå êîýôôèöèåíòû, à � ( ).x
n
x j
j
n
�
�
�
1
1
Ñâîéñòâî 3. Ñóììà êâàäðàòîâ âçâåøåííûõ ïðîåêöèé âåêòîðîâ ~( )x j ÿâëÿåòñÿ
ðàíãîì ìàòðèöû
~
X , ò.å. èìååò ìåñòî ñîîòíîøåíèå
~ ( ) (
~
) ~( ) ~ ( ) ~( )(x i R X x i x i u u x iT T T
j
j
r
i
n
i
n
j
T�
���
���
111
~ ( ) )x k uT
j
k
n
�
�� �
1
2
� �
�
�
��
� ��( ~ ( ) ) ~ ( ) )
j
r
T
j
T
j
k
n
i
n
x i u x k u r
1
2 2
11
.
(6)
Ñâîéñòâî 4. Ïðè ðàñøèðåíèè ìàòðèöû
~
X íîâûì âåêòîð-ñòîëáöîì x n( )� 1 áåç
èçìåíåíèÿ �x èìåþò ìåñòî ðåêóððåíòíûå ñîîòíîøåíèÿ:
1) ïðè âûïîëíåíèè íåðàâåíñòâà ~ ( ) (
~
) ~( )x n Z X x nT T� � �1 1 0 , ò.å. äëÿ ëèíåéíî
íåçàâèñèìîãî âåêòîðà ~( )x n � 1 îò âåêòîð-ñòîëáöîâ ìàòðèöû
~
X
R X x n T((
~ ~( ))� � �1
� �
� � � �
R X
Z X x n x n R X R X x nT
T T T T
(
~
)
(
~
) ~( ) ~ ( ) (
~
) (
~
) ~( ) ~1 1 1 x n Z X
x n Z X x n
T T
T T
( ) (
~
)
~ ( ) (
~
) ~( )
�
� �
�
1
1 1
�
� � �
� �
1 1 1
1 1
~ ( ) (
~
) ~( )
~ ( ) (~ ) ~( )
(
~x n R X x n
x n Z x x n
Z X
T T
T T
T ) ~( ) ~ ( ) (
~
)x n x n Z XT T� �1 1 ;
(7)
2) äëÿ ëèíåéíî-çàâèñèìîãî âåêòîðà ~( )x n � 1 îò âåêòîðîâ ~( ), , ~( )x x n1 � , ò.å.
~ ( ) (
~
)~( )x n Z X x nT T� � �1 1 0 ,
R X x n R X
R X x n x n R XT T
T T T
((
~ ~( ) ) (
~
)
(
~
) ~( ) ~ ( ) (
~
)
� � � �
� �
1
1 1
1 1 1� � �~ ( ) (
~ ~( )
.
x n R X x nT T
(8)
Ñâîéñòâî 5. Ïðè èçúÿòèè èç ìàòðèöû
~
X âåêòîð-ñòîëáöà ~( )x i áåç èçìåíåíèé �x
âûïîëíÿþòñÿ ñëåäóþùèå ðåêóððåíòíûå ñîîòíîøåíèÿ:
1) ïðè ïîíèæåíèè ðàíãà ìàòðèöû
~
X ïîñëå èçúÿòèÿ èç íåå ñòîëáöà ~( )x i , ò.å. ïðè
âûïîëíåíèè óñëîâèÿ 1 0� � ��~ ( )
~
(
~
)x i X e z XT
i ii
T
, ei — åäèíè÷íûé îðò â R n ,
z Xii (
~
) — äèàãîíàëüíûé ýëåìåíò ìàòðèöû Z X I Z Zn(
~
)
~ ~
� � �
R X I
X e e X
X e
R X Ii m
i i
T
i
T
T
T
(
~
)
~ ~
| |
~
| |
(
~
)( ) � �
�
�
�
�
�
� �
� 2
m
i i
T
i
X e e X
X e
T
T
�
�
�
�
�
�
� �
�
~ ~
| |
~
| |2
, (9)
~
(~( ) ~( ) ~( ) ~( ))( )X x x i x i x ni � � �1 1 1��� � � � � ;
2) ïðè ñîõðàíåíèè ðàíãà ìàòðèöû
~
X ïîñëå èçúÿòèÿ èç íåå ñòîëáöà ~( )x i , ò.å. ïðè
âûïîëíåíèè óñëîâèÿ
1 0� � ��~ ( )
~
(
~
)x i X e z XT
i ii
T
, R X R X
X e e X
X e
i
T T i i
T
i
T
T
(
~
) (
~
)
~ ~
| |
~
| |
( )
� �
� �
� 2
. (10)
112 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
Ñâîéñòâî 6. Ïðè èçìåíåíèè âåêòîðà �x íà � �x x� � , ò.å. äëÿ ìàòðèöû
~
�X xJ n
T� �
èìåþò ìåñòî ñîîòíîøåíèÿ
R X J x R A
b A a
R A ab AT
n
T
T T
T T(
~
) ( ) ( ( )� � �
�
��� 1
1
1 1
1
1
� �
�
�
�
� �A ba R A
a R A a
b A a
A bb A
T TT T
T T
T
T
1 1
1
1
2 1 1
1
( ))
( )
( )
,
(11)
a x b X XJ J Rn n
n� � � �
�
�
�
�
�
�
�
��� �,
~ ~
, ,
1
1
�
R A R X
R X aa R X
k
A X xJ ZT T
T T T
n
T( ) (
~
)
(
~
) (
~
)
| | | |
,
~
� (
1 2 1� � � � �
~
)X ,
| | | | (
~
)
(
~
)
,
~
�
(
~
)
| | (
k a R X a
J Z X J
k X x
Z X J
Z
T T
n
T
n
n2 1
� � � � �� � ~
) | |
.
X J n
2
Çäåñü ïðåäïîëàãàåòñÿ âûïîëíåíèå óñëîâèé îáùíîñòè ïîëîæåíèÿ
J X x x R X x J Z X Jn
T T T
n
T
n
~
(
~
) (
~
)� � � �� � �
� � �
1. (12)
Ñïðàâåäëèâîñòü ñâîéñòâ 1–6 âûòåêàåò èç ôîðìóë Ãðåâèëÿ è èõ îáðàùåíèÿ è òåî-
ðåìû îá àíàëèòè÷åñêîì ïðåäñòàâëåíèè âîçìóùåíèé ïñåâäîèíâåðñíûõ ìàòðèö [5].
2. ÝËËÈÏÑÎÈÄÍÛÅ ÊÎÍÒÅÉÍÅÐÛ Â ÏÐÎÑÒÐÀÍÑÒÂÅ ÏÐÈÇÍÀÊÎÂ
 ðàáîòàõ [3, 4] ðàññìîòðåíî ñðåäñòâî êëàññèôèêàöèè ýõî-ñèãíàëîâ, îñíîâàííîå
íà ôîðìèðîâàíèè ñïåöèàëüíûõ ìíîæåñòâ â ïðîñòðàíñòâå ïðèçíàêîâ òèïà ñôåð lp
ïðîñòðàíñòâà. Ýòè ìíîæåñòâà ïîëó÷èëè íàçâàíèå êîíòåéíåðîâ. Çäåñü ïðåäëàãàåò-
ñÿ ðàçâèòèå èäåè êîíòåéíåðíîãî îïèñàíèÿ ñîîòâåòñòâóþùèõ ìíîæåñòâ â ïðî-
ñòðàíñòâå ïðèçíàêîâ äëÿ òî÷åê, ïðèíàäëåæàùèõ ê îäíîìó è òîìó æå êëàñòåðó
èëè êëàññó. Ïðè ýòîì ôîðìó êîíòåéíåðîâ áóäåì âûáèðàòü â âèäå ýëëèïñîèäîâ
â ìíîãîìåðíîì ïðîñòðàíñòâå. Äëÿ ìíîæåñòâà òî÷åê (1) ðàññìîòðèì ýëëèïñîè-
äàëüíûé öèëèíäð â R, ñîäåðæàùèé ýòè òî÷êè:
( � ) (
~
)( � )x x R X x x dT T� � � 2 . (13)
Çäåñü âåëè÷èíó d 2 ìîæíî îïðåäåëèòü êàê ìèíèìàëüíîå ïîëîæèòåëüíîå ÷èñëî,
ïðè êîòîðîì
x j x x x R X x x dT T( ) : ( � ) (
~
)( � )� � � �{ 2 ,
ò.å.
d x j R X x j
j n
T T2
1
�
�
max ~ ( ) (
~
) ~( ).
,
(14)
Ñîãëàñíî ñîîòíîøåíèþ (6) ýòà âåëè÷èíà óäîâëåòâîðÿåò íåðàâåíñòâó
rank rank
~ ~ ( ) (
~
) ~( ) ,
~
X d
n
x j R X x j
r
n
r XT T
j
n
� � � �
�
�2
1
1
,
è áóäåò ìåíüøå èëè ðàâíî åäèíèöå â òîì ñëó÷àå, êîãäà
~ ( ) (
~
) ~( ) , ,x j R X x j d j nT T � �2 1 .
Åñëè r m� , òî (13) ÿâëÿåòñÿ ýëëèïñîèäîì â R m . Äëÿ òåõ ñëó÷àåâ, êîãäà r m� ,
áóäåì èñïîëüçîâàòü ýëëèïñîèäû, ñêîíñòðóèðîâàííûå ñ ïîìîùüþ ñðåäñòâà ðåãóëÿ-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 113
ðèçàöèè, â âèäå
( � ) (
~
) (
~
))( � ) ,x x R X
d d
Z X x xT T� � � �
1 1
1
2 2 2�
(15)
ãäå � �2 2� .
 ñèëó îïðåäåëåíèé ìàòðèö R X T(
~
) è Z X(
~
) ÿâëÿþòñÿ ñïðàâåäëèâûìè ñîîòíî-
øåíèÿìè
x j x x x K X x x j n K X R XT T( ) :( � ) (
~
)( � ) , , , (
~
) (
~
� � � � � �{ } }� �1 1 ) (
~
)
1 1
2 2 2d d
Z X�
�
, (16)
òàê êàê èìåþò ìåñòî ôîðìóëû äëÿ îáðàòíûõ ìàòðèö
R X XXT T� �1 (
~
)
~~
ïðè r m� ; (17)
K X d XX d Z XT
� �� � �1 2 2 2(
~
)
~
(
~
) ïðè r m� , (18)
â ñïðàâåäëèâîñòè êîòîðûõ ëåãêî óáåäèòñÿ ñ ïîìîùüþ SVD-ïðåäñòàâëåíèÿ ìàò-
ðèö. Íåñëîæíî âû÷èñëèòü ìàêñèìóì ëèíåéíûõ îïåðàöèé òàêîãî òèïà ýëëèïñîèä-
íûõ ìíîæåñòâ ïðè r m� :
max ( � ) ( (
~
) ) (
~~
)c x x d c R X c d c XX cT T T T T� � ��2 1
1
2 2
1
2 , (19)
x x x x R X x x dT� � � �{ }: ( � ) (
~
)( � ) 2 ,
ïðè r m�
max ( � ) (
~~
(
~
) ) ,c x x d c XX d Z X cT T T� � �2 2
1
2� (20)
x x x x K X x x� � � �{ }:( � ) (
~
)( � )� 1 .
Äëÿ äâóõ ýëëèïñîèäíûõ êîíòåéíåðîâ
{ } rankx d x x R X x x X mT: ( �( )) (
~
( ))( �( )) ,
~
( )
1
2 1 1 1 1 1� � � � � , (21)
{ } rankx d x x R X x x X mT: ( � ( )) (
~
( ))( �( )) ,
~
( )
2
2 2 2 2 1 2� � � � � , (22)
ñôîðìèðîâàííûõ ñîîòâåòñòâåííî òî÷êàìè x i x in( ), , ( )1 1� è x j x jn( ), , ( )1 2� ,
óñëîâèÿ ñóùåñòâîâàíèÿ ðàçäåëÿþùåé èõ ëèíåéíîé ïîëîñû ñâîäèòñÿ ê óñëîâèþ
ñóùåñòâîâàíèÿ òàêîãî âåêòîðà c R cm� �, | | | | 1, äëÿ êîòîðîãî èìååò ìåñòî íåðà-
âåíñòâî
c x x d c X X c d c X XT T T T T( �( ) �( )) (
~
( )
~
( ) ) (
~
( )
~
2 1 1 1 21
1
2
2� � � ( ) )2 0
1
2c � , (23)
à ìàêñèìàëüíàÿ øèðèíà ðàçäåëÿþùåé ïîëîñû äëÿ ýòèõ êîíòåéíåðîâ äîñòèãàåòñÿ
ïðè c âûáðàííîãî ñîãëàñíî óñëîâèþ îïòèìàëüíîñòè
c c X X d c X X c
c
T T T
opt {� � �
�
max ( � ( ) � ( )) (
~
( )
~
( ) )
|| || 1
12 1 1 1
1
2
2
1
22 2� d c X X cT T(
~
( )
~
( ) ) }. (24)
Àíàëîãè÷íî ïðåäñòàâëÿþòñÿ ñâîéñòâà ðàçäåëèìîñòè ýëëèïñîèäàëüíûõ êîíòåé-
íåðîâ è ïðè áîëåå «îáåäíåííûõ» äàííûõ, äëÿ êîòîðûõ rank
~
( ), ,X j j � 1 2 , ìåíüøå
m , ñ èñïîëüçîâàíèåì ìàòðèö K X j j� (
~
( )), ,� 1 2 , ò.å. óñëîâèþ (23) ñîîòâåòñòâóåò
íåðàâåíñòâî
c X X d c X X Z X cT T T( � ( ) � ( )) ( (
~
( )
~
( ) (
~
( )) )2 1 1 1 11 1
2
1
2� � � ��
� � �d c X X Z X cT T
2 2
2
1
22 2 2 0( (
~
( )
~
( ) (
~
( )) )� , (25)
à óñëîâèþ îïòèìàëüíîñòè (24) — óñëîâèå
c c X X d c X X
c
T T T
opt {� � �
�
arg max ( � ( ) � ( )) ( (
~
( )
~
(
|| || 1
12 1 1 1 1
1
2
1
2) (
~
( )) )� �� Z X c
114 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
� �d c X X Z X cT T
2 2
2
1
22 2 2( (
~
( )
~
( ) (
~
( )) )� }. (26)
3. ÊÎÍÒÅÉÍÅÐÍÀß ÊËÀÑÒÅÐÈÇÀÖÈß ÑÈÃÍÀËÎÂ
È ÔÎÐÌÈÐÎÂÀÍÈÅ ÄÅÐÅÂÀ ÊËÀÑÒÅÐÎÂ
Ïóñòü x x m( ), , ( )1 � — òî÷êè (âåêòîðû x j R m( )� ) â ïðîñòðàíñòâå ïðèçíàêîâ, ñîîò-
âåòñòâóþùèå ðàçëè÷íûì îáúåêòàì èëè ïðîöåññàì, êîòîðûå íåîáõîäèìî êëàñòåðèçî-
âàòü. Íàïðèìåð, x( )1 ñîîòâåòñòâóåò èçîáðàæåíèþ áóêâû À, x( )2 — Á, x n( ) — ß. Íå-
îáõîäèìî ïî íåêîòîðîìó ïðèíöèïó ïîäîáèÿ îáúåäèíèòü ÷àñòü ýòèõ âåêòîðîâ â îäíó
ñîâîêóïíîñòü (êëàñòåð), à îñòàâøóþñÿ — âî âòîðîé êëàñòåð, çàòåì ïîñëåäîâàòåëüíî
îñóùåñòâëÿòü ýòè æå ðàçáèåíèÿ äëÿ êëàñòåðîâ, îðãàíèçîâàâ, òàêèì îáðàçîì, äèõî-
òîìíîå äåðåâî êëàñòåðèçàöèè èñõîäíûõ äàííûõ. Íàèáîëåå ïðîñòîå ñðåäñòâî òàêîé
êëàñòåðèçàöèè ïðåäñòàâëÿåò ñîáîé èçâåñòíûé àëãîðèòì K-ñðåäíèõ [5, 6], èñïîëüçó-
þùèé èäåþ îáúåäèíåíèÿ òî÷åê ïî ìèíèìàëüíîìó åâêëèäîâîìó ðàññòîÿíèþ îò òî-
÷åê äî öåíòðîâ êëàñòåðîâ. Ýòîò àëãîðèòì èìååò ñëåäóþùèé âèä:
1) îïðåäåëèòü ïåðâîíà÷àëüíûå öåíòðîèäû êëàñòåðîâ x x k( ), , ( )1 � ;
2) íàéòè áëèæàéøèå ïî åâêëèäîâîìó ðàññòîÿíèþ òî÷êè ê êàæäîìó öåíòðîèäó;
3) ïåðåñ÷èòàòü öåíòðîèäû;
4) åñëè âñå òî÷êè îòíåñåíû ê êëàñòåðàì è öåíòðîèäû íå èçìåíèëèñü — íà âû-
õîä, èíà÷å — íà øàã 2.
Çäåñü ïðåäëàãàåòñÿ ðàçâèòèå èäåè Ê-ñðåäíèõ ñ ó÷åòîì âû÷èñëåíèÿ ðàññòîÿíèÿ
ïî ñïåöèàëüíîé ìåðå, êîòîðóþ ôîðìèðóþò ñàìè òî÷êè èëè äðóãèå ñîâîêóïíîñòè,
âîçíèêàþùèå â ïðîöåññå âûïîëíåíèÿ àëãîðèòìà. Ýòà ìåðà ó÷èòûâàåò ïëîòíîñòü è
ôàêòîðíóþ ñòðóêòóðó ñîîòâåòñòâóþùåãî ïîäìíîæåñòâà òî÷åê, ÷òî äàëåå ïîëîæè-
òåëüíî ïðîÿâëÿåòñÿ íà êà÷åñòâå êàê êëàñòåðèçàöèè, òàê è ðàñïîçíàâàíèÿ ñèãíàëîâ.
Èòàê, îïèøåì ïîäõîä ôîðìèðîâàíèÿ êëàñòåðîâ. Ïóñòü èçíà÷àëüíî ðàññìàòðèâàå-
ìûå òî÷êè x j j n( ), ,� 1 , â ïðîñòðàíñòâå ïðèçíàêîâ óæå ðàçáèòû íà äâà êëàñòåðà (íà-
ïðèìåð, ñ ïîìîùüþ àëãîðèòìà 2-ñåðäíèõ): D x x i k nk1 11� �{ }: ( ), , è
D x x i k nk2 21� �{ }: ( ), , . Äëÿ ýòèõ ïîäìíîæåñòâ D1 è D2 îïðåäåëèì ñîîòâåòñòâåí-
íî ìàòðèöû
~
( )X 1 ,
~
( )X 2 ñîãëàñíî îïåðàöèÿì, ââåäåííûì â ïðåäûäóùåì ðàçäåëå, ò.å.
~
( ) (~( ) ~( )),
~
( ) (~( ) ~( ))X x i x i X x j x jn n1 21 11 2
� �� � � � � � ,
~( ) ( ) �( ), ~( ) ( ) ( ), , , ,x i x i x x j x j x k n s nk k s s� � � � � �1 2 1 11 2 ,
�( ) ( ), �( ) ( )x
n
x i x
n
x jk
k
n
s
s
n
1
1
2
1
1 1 2 1
1 2
� �
� �
� � .
Áóäåì ïðåäïîëàãàòü, ÷òî n1 è n2 èìåþò íàñòîëüêî áîëüøèå çíà÷åíèÿ, ÷òî âåê-
òîðû ~( ), ,x i k nk � 1 1 , è ñîîòâåòñòâåííî ~( ), ,x j s ns � 1 2 , îáëàäàþò ñâîéñòâîì
rank rank
~
( ) ,
~
( )X m X m1 2� � . (27)
Òîãäà ñîãëàñíî ñâîéñòâàì âçâåøåííûõ ïðîåêöèîííûõ ìàòðèö [7] èìåþò ìåñòî
ñîîòíîøåíèÿ
x i x
d
x x R X x xk
T T( ) : ( �( )) (
~
( ))( �( ))� � � �
�
�
�
��
�
�
�1
1 1 1 1
1
2
��
�, ,k n1 1,
x j x
d
x x R X x xs
T T( ) : ( �( )) (
~
( ))( �( ))� � � �
�
�
�
��
�
�
�1
2 2 2 1
2
2
��
�, ,s n1 2 .
(28)
Ãåîìåòðè÷åñêàÿ èíòåðïðåòàöèÿ äëÿ m � 2 ýòèõ ñîîòíîøåíèé ïðèâåäåíà íà
ðèñ 1. Çäåñü
d x i x
k n
k
T
1
1 1
1� � �
�
max ( ( ) �( ))
,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 115
� �R X x i xT
k(
~
( ))( ( ) ( ))1 1 ,
d x j x
s n
s
T
2
1 2
2� � �
�
max ( ( ) �( ))
,
� �R X x j xT
s(
~
( ))( ( ) ( ))2 2 ,
R X X XT T
(
~
( ))
~
( )
~
( ),1 1 1� � �
R X X XT T
(
~
( ))
~
( )
~
( )2 2 2� � � .
Òîãäà â êà÷åñòâå ìåðû ðàññòîÿíèÿ îò íåêî-
òîðîé òî÷êè x R m� äî ìíîæåñòâà
� j j, ,� 1 2 , áóäåì ðàññìàòðèâàòü âìåñòî åâ-
êëèäîâîãî ðàññòîÿíèÿ âåëè÷èíó
�( , ) (( �( )) (
~
( ))( �( ))x
d
x x j R X j x x jj
j
T T� � � �
1
1
2 . (29)
Ýòî ïîçâîëÿåò ðåîðãàíèçîâàòü ïðèíàäëåæíîñòü òî÷åê x j j n( ), ,� 1 , ìíîæåñòâàì D1
è D2 , ò.å. åñëè íåêîòîðàÿ òî÷êà x j( ) óäîâëåòâîðÿåò óñëîâèþ
� �( ( ), ) ( ( ), ),x j x j� �1 2� (30)
áóäåì åå îòíîñèòü ê ìíîæåñòâó òî÷åê D1, è åñëè
� �( ( ), ) ( ( ), )x j x j� �1 2� , (31)
òî x j( ) îòñûëàåì â ìíîæåñòâî D2 . Òàêèì îáðàçîì, àëãîðèòì ôîðìèðîâàíèÿ
êëàñòåðîâ íà îñíîâàíèè èñïîëüçîâàíèÿ ìíîæåñòâ-êîíòåéíåðîâ èìååò ñëåäóþùåå
ïðåäñòàâëåíèå:
1) ñôîðìèðîâàòü êëàñòåðû D1 è D2 ;
2) ïåðåñ÷èòàòü öåíòðîèäû ñîãëàñíî (29);
3) ïåðåéòè íà øàã 2, ïîêà åñòü íåïåðåñ÷èòàííûå òî÷êè, èíà÷å — íà âûõîä,
åñëè óñëîâèÿ � �( ( ), ) ( ( ), )x j x j� �1 2� , � �( ( ), ) ( ( ), )x j x j� �1 2� âûïîëíèëèñü.
Ìàòðèöû R X R XT T(
~
( )), (
~
( ))1 2 ïðèîáðåòàþò ðåêóððåíòíóþ ôîðìó òðàíñôîð-
ìàöèè ñîãëàñíî ôîðìóëàì (7)–(11) ïðè ïåðåìåùåíèè íåêîòîðîé òî÷êè x j( ) èç ìíî-
æåñòâà D1 â D2 èëè èç D2 â D1 çà ñ÷åò èçúÿòèÿ èëè ïîïîëíåíèÿ èç ìàòðèö
~
( )X 1 ,
~
( )X 2 ñîîòâåòñòâóþùåãî âåêòîðà è èçìåíåíèÿ âåêòîðîâ �( )x 1 è �( )x 2 .
Åñëè óñëîâèÿ (27) íå âûïîëíÿþòñÿ, ÷òî áûâàåò âåñüìà ðåäêî ïðè ðåøåíèè êîð-
ðåêòíûõ ïðèêëàäíûõ çàäà÷, òî â ýòîì ñëó÷àå âìåñòî ìàòðèöû R X j jT(
~
( )), ,� 1 2 ,
ñëåäóåò èñïîëüçîâàòü ìàòðèöó K X j jT
� (
~
( )), ,� 1 2 , îïðåäåëåíèÿ êîòîðûõ ïðèâåäå-
íî â ïðåäûäóùåì ðàçäåëå ñòàòüè. Ñëåäóåò çàìåòèòü, ÷òî ôîðìóëû ðåêóððåíòíîãî
ïðåäñòàâëåíèÿ òðàíñôîðìàöèè ìàòðèö Z X j jT(
~
( )), ,� 1 2 , òîæå íåñëîæíî ïîëó÷èòü
íà îñíîâàíèè ôîðìóë âîçìóùåíèÿ ïñåâäîîáðàòíûõ ìàòðèö.
4. ÊÎÍÒÅÉÍÅÐÍÀß ÊËÀÑÑÈÔÈÊÀÖÈß ÑÈÃÍÀËÎÂ
È ÐÅÊÓÐÐÅÍÒÍÛÅ ÀËÃÎÐÈÒÌÛ ÎÁÓ×ÅÍÈß ÏÐÀÂÈË ÊËÀÑÑÈÔÈÊÀÖÈÈ
Îïèñàííûå âûøå ñâîéñòâà ýëëèïñîèäàëüíûõ êîíòåéíåðîâ ïîçâîëÿþò ñôîðìèðî-
âàòü óäîáíûå äëÿ èñïîëüçîâàíèÿ ïðàâèëà êëàññèôèêàöèè ñèãíàëîâ â ñèñòåìàõ
ðàñïîçíàâàíèÿ îáðàçîâ. Ðàññìîòðèì îïèñàíèÿ òàêèõ ïðàâèë íà ïðèìåðå äâóõ
êëàññîâ, íå îãðàíè÷èâàÿ îáùíîñòü ïîäîáíûõ ðàññóæäåíèé äëÿ äðóãèõ êëàññîâ.
Ïóñòü â ïðîñòðàíñòâå R m ïðèçíàêîâ çàäàíà îáó÷àþùàÿ ïîñëåäîâàòåëüíîñòü
x j j n( ), ,� 1 , ãäå x i k nk( ), ,� 1 1, ÿâëÿþùàÿñÿ ïðåäñòàâèòåëÿìè 1-ãî êëàññà è
x j s ns( ); ,� 1 2 , — ïðåäñòàâèòåëÿìè 2-ãî êëàññà. Îáðàçîâàâ äëÿ 1- è 2-ãî êëàññîâ
ýëëèïñîèäàëüíûå êîíòåéíåðû
V x d x x R X x xT T
1 1
2 1 1 1 1( ) ( ( )) (
~
( ))( ( ))� � � �� , (32)
116 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5
Ðèñ. 1
u2 1( )
u1 2( )
u1 1( )
u2 2( )
D2
D1
V x d x x R X x xT T
2 2
2 2 2 2 1( ) ( ( )) (
~
( ))( ( ))� � � �� , (33)
íåîáõîäèìî ïðîâåñòè àíàëèç íåïåðåñåêàåìîñòè ýòèõ êîíòåéíåðîâ. Ýòî ìîæíî
îñóùåñòâèòü ñîãëàñíî óñëîâèþ (23) èëè â ïðîöåññå ïðîâåðêè âûïîëíåíèÿ
óñëîâèé
x i x V x k nk( ) : ( ) , ,� � �{ }2 11 1 , (34)
x j x V x s ns( ) : ( ) , , .� � �{ }1 21 1 (35)
Åñòåñòâåííî, ñîîòíîøåíèÿ (34) è (35) âûñòóïàþò ëèøü íåîáõîäèìûìè óñëîâè-
ÿìè íåïåðåñåêàåìîñòè ýëëèïñîèäàëüíûõ êîíòåéíåðîâ (32) è (33), îäíàêî åñëè
V x j s ns1 21( ( )) , ,� �� , (36)
V x i k nk2 11( ( )) , , ,� �� (37)
ãäå � ñóùåñòâåííî áîëüøå åäèíèöû, òî ýòè óñëîâèÿ ïðàêòè÷åñêè îáåñïå÷àò íåïå-
ðåñåêàåìîñòü êîíòåéíåðîâ. Çäåñü äëÿ ïðîñòîòû èçëîæåíèÿ ïðåäïîëàãàåòñÿ ïîëíî-
òà äàííûõ â îáó÷àþùåé ïîñëåäîâàòåëüíîñòè, ò.å. det R X j jT(
~
( )) , ,� �0 1 2 .
 ïðîòèâíîì ñëó÷àå ïðè îïðåäåëåíèè ôóíêöèé V x V x1 2( ), ( ) âìåñòî ìàòðèö
R X jT(
~
( )) íåîáõîäèìî ïðèìåíèòü ðåãóëÿðèçîâàííûå ìàòðèöû K X j� (
~
( )) . Åñëè
ýëëèïñîèäàëüíûå êîíòåéíåðû ïåðåñåêàþòñÿ, òî ìîæíî âîñïîëüçîâàòüñÿ ñðå-
äñòâîì ïîñëåäîâàòåëüíîé ôèëüòðàöèè íàèáîëåå íåðàçëè÷èìûõ îáúåêòîâ x j( ) èç
ïåðâîãî è âòîðîãî êîíòåéíåðîâ, ðåîðãàíèçîâàâ êîíòåéíåðû ñ ïîìîùüþ ðåêóððåí-
òíûõ ñîîòíîøåíèé, ïðåäëîæåííûõ âî âòîðîì ðàçäåëå ýòîé ñòàòüè.  ñâîþ î÷å-
ðåäü, äëÿ èçúÿòûõ ýëåìåíòîâ ïðåäëàãàåòñÿ îñóùåñòâèòü ñâîþ ñèñòåìó äâóõêîí-
òåéíåðíîé êëàññèôèêàöèè. Àëãîðèòì ìîæíî ïðåäñòàâèòü ïîñëåäîâàòåëüíîñòüþ
òàêèõ øàãîâ:
1) ñôîðìèðîâàòü êîíòåéíåðû V1 è V2 ;
2) ïðîâåðèòü íåïåðåñåêàåìîñòü êîíòåéíåðîâ ñîãëàñíî (36), (37);
3) ïðèìåíèòü ðåêóððåíòûå ôîðìóëû è ïåðåéòè íà 2 ñ íîâûìè çíà÷åíèÿìè òî-
÷åê, åñëè êîíòåéíåðû ïåðåñåêàþòñÿ, èíà÷å — íà âûõîä.
ÇÀÊËÞ×ÅÍÈÅ
 äàííîé ðàáîòå îïèñàíû êîíòåéíåðíûå ñðåäñòâà êëàñòåðèçàöèè è êëàññèôèêà-
öèè ñèãíàëîâ, êîòîðûå ìîãóò èñïîëüçîâàòüñÿ äëÿ ðåøåíèÿ çàäà÷ êëàñòåðèçàöèè è
êëàññèôèêàöèè ìàññèâà òåêñòîâûõ ïå÷àòíûõ äîêóìåíòîâ, óëüòðàçâóêîâûõ ñèãíà-
ëîâ, ãðàôè÷åñêèõ îáðàçîâ è ò.ä. Âûâåäåíû ïðàâèëà êëàññèôèêàöèè ñèãíàëîâ
â ñèñòåìàõ ðàñïîçíàâàíèÿ îáðàçîâ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ê è ð è ÷ å í ê î Ì . Ô . Ê ó ö Ð î ì à í ( Ñ Ø À ) , Ë å ï å õ à Ì . Ï . Ìíîæèíè ïðèíàëåæíîñò³ â
çàäà÷àõ êëàñèô³êàö³¿ ñèãíàë³â // Ï’ÿòà Âñåóêð. ì³æíàð. êîíô. ÓêðÎÁÐÀÇ‘2000. ²í-ò ê³áåðíåòèêè
ÍÀÍÓ. — Êè¿â. — 2000. — Ñ. 83–87.
2. Ê è ð è ÷ å í ê î Í . Ô . , Ê ó ö Ð î ì à í ( Ñ Ø À ) , Ë å ï å õ à Í . Ï . Ðàñïîçíàâàíèå òðåõìåðíûõ
îáúåêòîâ ïî óëüòðàçâóêîâûì ýõî-ñèãíàëàì // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 1999. — ¹ 5.
— Ñ. 110–122.
3. Ê è ð è ÷ å í ê î Ì . Ô . , Ê ó ö Ð î ì à í ( Ñ Ø À ) , Ë å ï å õ à Ì . Ï . Àëãîðèòìè ðîçï³çíàâàííÿ
îá’ºêò³â óëüòðàçâóêîâèìè ñîíàðàìè // Òåîð³ÿ îá÷èñëåíü: Çá. íàóê. ïðàöü. — Êè¿â: ²í-ò ê³áåðíåòèêè
ÍÀÍÓ. — 1999. — Ñ. 196–200.
4. Ê î ò î â À . , Ê ð à ñ è ë ü í è ê î â Í . Êëàñòåðèçàöèÿ äàííûõ. [Ýëåêòðîí. ðåñóðñ] — 2006. http://
logic.pdmi.ras.ru/~yura/internet/02ia-seminar.ppt
5. Ê è ð è ÷ å í ê î Í . Ô . , Ä î í ÷ å í ê î  . Ñ . Ìíîæåñòâà è ðàññòîÿíèÿ ñîîòâåòñòâèÿ â çàäà÷àõ
êëàñòåðèçàèè: ãèïåðïëîñêîñòè // Intern. Book Series “Inform. Sci. and Comput.” — 2001. — Ñ. 155–164.
6. Ê è ð è ÷ å í ê î Í . Ô . , Ä î í ÷ å í ê î  . Ñ . Ïñåâäîîáðàùåíèÿ â çàäà÷àõ êëàñòåðèçàöèè // Êèáåðíå-
òèêà è ñèñòåìíûé àíàëèç. — 2007. — ¹ 4. — Ñ. 73–92.
7. Ê è ð è ÷ å í ê î Í . Ô . , Ë å ï å õ à Í . Ï . Ïðèìåíåíèå ïñåâäîîáðàòíûõ è ïðîåêöèîííûõ ìàòðèö
â ïðèìåíåíèè ê èññëåäîâàíèþ çàäà÷ óïðàâëåíèÿ, íàáëþäåíèÿ è èäåíòèôèêàöèè // Òàì æå. — 2002. —
¹ 4. — Ñ. 107–124.
Ïîñòóïèëà 11.03.2009
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 5 117
|