Формализация алгоритма классификации объектов
Рассмотрен алгоритм классификации объектов по критерию максимума дискриминантных функций, особенностью которого является параллельная обработка по столбцам матрицы, составленной из элементов дискриминантных функций. Приведено представление данного алгоритма в терминах системы алгоритмических алгебр...
Збережено в:
| Дата: | 2015 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/124910 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Формализация алгоритма классификации объектов / Т.Б. Мартынюк, А.В. Кожемяко, Л.М. Куперштейн // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 95-101. — Бібліогр.: 24 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124910 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1249102017-10-12T03:02:55Z Формализация алгоритма классификации объектов Мартынюк, Т.Б. Кожемяко, А.В. Куперштейн, Л.М. Системный анализ Рассмотрен алгоритм классификации объектов по критерию максимума дискриминантных функций, особенностью которого является параллельная обработка по столбцам матрицы, составленной из элементов дискриминантных функций. Приведено представление данного алгоритма в терминах системы алгоритмических алгебр В.М. Глушкова. Розглянуто алгоритм класифікації об’єктів за критерієм максимуму дискримінантних функцій, особливістю якого є паралельна обробка за стовпцями матриці, що складається з елементів дискримінантних функцій. Наведено запис цього алгоритму в термінах системи алгоритмічних алгебр В.М. Глушкова. An algorithm for object classification using the criterion of the maximum of discriminat functions is considered. A special feature of this algorithm is parallel processing over the columns of the matrix that consists of elements of the discriminant functions. This algorithm is represented in terms of Glushkov’s system of algorithmic algebras. 2015 Article Формализация алгоритма классификации объектов / Т.Б. Мартынюк, А.В. Кожемяко, Л.М. Куперштейн // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 95-101. — Бібліогр.: 24 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124910 004.93’1 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
2015 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124910 |
| citation_txt |
Формализация алгоритма классификации объектов / Т.Б. Мартынюк, А.В. Кожемяко, Л.М. Куперштейн // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 95-101. — Бібліогр.: 24 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT martynûktb formalizaciâalgoritmaklassifikaciiobʺektov AT kožemâkoav formalizaciâalgoritmaklassifikaciiobʺektov AT kuperštejnlm formalizaciâalgoritmaklassifikaciiobʺektov |
| first_indexed |
2025-07-09T02:15:09Z |
| last_indexed |
2025-07-09T02:15:09Z |
| _version_ |
1837133788982804480 |
| fulltext |
ÓÄÊ 004.93’1
Ò.Á. ÌÀÐÒÛÍÞÊ, À.Â. ÊÎÆÅÌßÊÎ, Ë.Ì. ÊÓÏÅÐØÒÅÉÍ
ÔÎÐÌÀËÈÇÀÖÈß ÀËÃÎÐÈÒÌÀ ÊËÀÑÑÈÔÈÊÀÖÈÈ ÎÁÚÅÊÒÎÂ
Àííîòàöèÿ. Ðàññìîòðåí àëãîðèòì êëàññèôèêàöèè îáúåêòîâ ïî êðèòåðèþ ìàêñèìóìà äèñ-
êðèìèíàíòíûõ ôóíêöèé, îñîáåííîñòüþ êîòîðîãî ÿâëÿåòñÿ ïàðàëëåëüíàÿ îáðàáîòêà ïî
ñòîëáöàì ìàòðèöû, ñîñòàâëåííîé èç ýëåìåíòîâ äèñêðèìèíàíòíûõ ôóíêöèé. Ïðèâåäåíî
ïðåäñòàâëåíèå äàííîãî àëãîðèòìà â òåðìèíàõ ñèñòåìû àëãîðèòìè÷åñêèõ àëãåáð Â.Ì. Ãëóøêîâà.
Êëþ÷åâûå ñëîâà: êëàññèôèêàöèÿ îáúåêòîâ, ñèñòåìà àëãîðèòìè÷åñêèõ àëãåáð Â.Ì. Ãëóø-
êîâà, îáðàáîòêà ïî ðàçíîñòíûì ñðåçàì, äèñêðèìèíàíòíàÿ ôóíêöèÿ.
ÂÂÅÄÅÍÈÅ
 ðÿäå ôóíäàìåíòàëüíûõ ðàáîò äîñòàòî÷íî ïîäðîáíî îïèñàíû íå òîëüêî áàçî-
âûå ïîëîæåíèÿ ñèñòåì àëãîðèòìè÷åñêèõ àëãåáð (ÑÀÀ) Â.Ì. Ãëóøêîâà [1–5],
íî è òåîðåòè÷åñêèå îñíîâû ôîðìèðîâàíèÿ èõ ðàçíîâèäíîñòåé è êëîíîâ, à òàê-
æå ïðåäëîæåíû âàðèàíòû èñïîëüçîâàíèÿ áàçèñà ÑÀÀ Â.Ì. Ãëóøêîâà äëÿ
ïðåäñòàâëåíèÿ êîíêðåòíûõ àëãîðèòìîâ îáðàáîòêè èíôîðìàöèè [6–11]. Ýòè
ïóáëèêàöèè ïðîäîëæàþò öèêë ðàáîò, ñâÿçàííûõ ñ ñîðòèðîâêîé ìàññèâîâ äàí-
íûõ [10, 12–15] è ñ äðóãèìè âèäàìè ìóëüòèîáðàáîòêè, íàïðèìåð ñ ìóëüòèîá-
ðàáîòêîé âåêòîðíûõ ìàññèâîâ äàííûõ ïî ðàçíîñòíûì ñðåçàì (ÐÑ) [16]. Ïðè
ýòîì â [17] â áàçèñå ìîäèôèöèðîâàííîé ÑÀÀ Â.Ì. Ãëóøêîâà ïðåäñòàâëåíû
âàðèàíòû ìíîãîîïåðàíäíîãî ñóììèðîâàíèÿ (ñâåðòêè) ýëåìåíòîâ âåêòîðíîãî
ìàññèâà ïî ÐÑ, à òàêæå â êà÷åñòâå ðàñøèðåíèÿ òàêîé îáðàáîòêè — âàðèàíòû
ïîðîãîâîé îáðàáîòêè âåêòîðíîãî ìàññèâà ïî ÐÑ äëÿ ðåàëèçàöèè ìîäåëè ïîðî-
ãîâîãî íåéðîíà [18, 19].
 íàñòîÿùåé ñòàòüå íà áàçå ÐÑ ïðåäëîæåí àëãîðèòì êëàññèôèêàöèè îáúåê-
òîâ, ïðåäïîëàãàþùèé ïàðàëëåëüíóþ îáðàáîòêó ýëåìåíòîâ ìàòðèöû âçâåøåííûõ
êîìïîíåíò âõîäíîãî âåêòîðà ïðèçíàêîâ, ÷òî ðàñøèðÿåò ôóíêöèîíàëüíûå âîç-
ìîæíîñòè ïðîöåññà êëàññèôèêàöèè çà ñ÷åò ôîðìèðîâàíèÿ îäíîâðåìåííî ñ âåêòî-
ðîì êëàññèôèêàöèè âåêòîðà ðàíãîâ äèñêðèìèíàíòíûõ ôóíêöèé [20]. Ïðåä-
ñòàâëåí óñîâåðøåíñòâîâàííûé àëãîðèòì êëàññèôèêàöèè îáúåêòîâ â òåðìèíàõ
ÑÀÀ Â.Ì. Ãëóøêîâà.
Öåëüþ ðàáîòû ÿâëÿåòñÿ ðàñêðûòèå ôóíêöèîíàëüíûõ âîçìîæíîñòåé êîì-
ïàêòíîãî îïèñàíèÿ â òåðìèíàõ ÑÀÀ Â.Ì. Ãëóøêîâà àëãîðèòìà êëàññèôèêàöèè
îáúåêòîâ íà áàçå ÐÑ.
ÎÑÎÁÅÍÍÎÑÒÈ ÎÁÐÀÁÎÒÊÈ ÏÎ ÐÑ ÝËÅÌÅÍÒÎÂ ÄÈÑÊÐÈÌÈÍÀÍÒÍÛÕ ÔÓÍÊÖÈÉ
Äèñêðèìèíàíòíûå ôóíêöèè (ÄÔ) ïðåäñòàâëÿþò ñîáîé ðàçäåëÿþùèå ôóíêöèè
ìåæäó îáëàñòÿìè (êîíôèãóðàöèÿìè) êëàññîâ â ïðîñòðàíñòâå ïðèçíàêîâ îáúåêòîâ
(îáðàçîâ) ïðè èõ êëàññèôèêàöèè [21]. Ïî ïðèçíàêó ìàêñèìóìà îäíîé èç m ÄÔ,
ãäå m — êîëè÷åñòâî êëàññîâ, îïðåäåëÿåòñÿ ïðèíàäëåæíîñòü ðàñïîçíàâàåìîãî îá-
ðàçà, ïðåäñòàâëåííîãî âõîäíûì âåêòîðîì ïðèçíàêîâ, ê êîíêðåòíîìó êëàññó [22].
Òàêèì îáðàçîì, åñëè ñôîðìèðîâàíû m ÄÔ âèäà
g X w x w x w x
g X w
n n
m m
1 11 1 12 2 1
1
( ) ,
( )
� � � �
�
�
���������������
x w x w xm mn n1 2 2� � �
�
�
�
�
�
� ,
(1)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 95
� Ò.Á. Ìàðòûíþê, À.Â. Êîæåìÿêî, Ë.Ì. Êóïåðøòåéí, 2015
èëè
g X w xi ij j
j
n
( ) �
�
1
,
(2)
ãäå x j — j-ÿ êîìïîíåíòà âõîäíîãî âåêòîðà X ïðèçíàêîâ îáðàçà, wij — âåñ
âõîæäåíèÿ j-é êîìïîíåíòû â i-é êëàññ Ñi , i m�1, , òî ðåøàþùåå ïðàâèëî êëàñ-
ñèôèêàöèè ïî êðèòåðèþ ìàêñèìóìà ÄÔ ìîæíî ïðåäñòàâèòü êàê â [22, 23],
à èìåííî X Ck
, åñëè g X g X k mk
i
i( ) max ( ), , .� �1
 ðàáîòå [20] ïðåäëîæåíî íå ôîðìèðîâàòü âñå m ÄÔ (1) ñ ïîñëåäóþùèì
îïðåäåëåíèåì ìàêñèìàëüíîé ñðåäè íèõ, à ñôîðìèðîâàòü ìàòðèöó A 0 èç ýëåìåí-
òîâ (ñëàãàåìûõ) m ÄÔ (1) ñ äàëüíåéøåé èõ îáðàáîòêîé ïàðàëëåëüíî ïî ñòîëáöàì,
ïîñêîëüêó îíè ñîñòîÿò èç îäíîèìåííûõ ýëåìåíòîâ — ñëàãàåìûõ ÄÔ (1). Òàêàÿ
ïàðàëëåëüíàÿ îáðàáîòêà ïî ñòîëáöàì ìàòðèöû A 0 ïðàâîìî÷íà, ïîñêîëüêó ëþáîé
ñóììå âèäà (2) ïðèñóùè ñâîéñòâà êîììóòàòèâíîñòè è àññîöèàòèâíîñòè [24]. Òà-
êèì îáðàçîì, îïðåäåëèòü ìàêñèìàëüíóþ èç m ñóìì âèäà (1) ìîæíî â ïðîöåññå
îäíîâðåìåííîãî èõ óìåíüøåíèÿ íà âåëè÷èíó îáùåé ñîñòàâëÿþùåé, êîòîðóþ
ôîðìèðóþò ìèíèìàëüíûå ýëåìåíòû â êàæäîì ñòîëáöå òåêóùåé ìàòðèöû A t
â t-ì öèêëå îáðàáîòêè, ãäå t N�1, . Ïðè ýòîì â ïðîöåññå ïîñëåäîâàòåëüíîãî îáíó-
ëåíèÿ ñîîòâåòñòâóþùèõ ñòðîê èñõîäíîé ìàòðèöû A 0 ìîæíî îïðåäåëèòü ðàíãè
ÄÔ, íà÷èíàÿ ñ ïåðâîé ïî m-þ.
 ðåçóëüòàòå àëãîðèòì êëàññèôèêàöèè îáúåêòîâ ïî òàêîìó ïðèíöèïó îáðà-
áîòêè ýëåìåíòîâ ÄÔ ïðåäñòàâèì ñëåäóþùèì îáðàçîì. Èñõîäíûìè äàííûìè ÿâ-
ëÿþòñÿ: âåêòîð âõîäíûõ ñèãíàëîâ X x j� { }; ìàòðèöà âåñîâ W wij� { }; âåêòîð
êëàññèôèêàöèè P pi� { }; êëàññû C Ci� { }, ãäå j — ðàçìåðíîñòü âåêòîðà Õ
{ }j N�1, , i — êîëè÷åñòâî êëàññîâ Ñ { }i m�1, .
Øàã 1. Ôîðìèðîâàíèå ìàòðèöû A0 âçâåøåííûõ âõîäíûõ ñèãíàëîâ x j âèäà
A 0
11
0
12
0
1
0
1
0
2
0 0
1
0
0
� �
a a a
a a a
A
A
n
m m mn m
�
� � � �
�
� , (3)
ïðè÷åì ýòè âõîäíûå ñèãíàëû êàê ýëåìåíòû aij
0 ìàòðèöû A 0 âû÷èñëÿþòñÿ
a w xij ij j
0 � � ; ïðèñâîåíèå åäèíè÷íîãî çíà÷åíèÿ âñåì ýëåìåíòàì pi âåêòîðà êëàñ-
ñèôèêàöèè P, ò.å. P � ( ... )11 1 T .
Øàã 2. Âûäåëåíèå ìèíèìàëüíûõ ýëåìåíòîâ q j
t îäíîâðåìåííî âî âñåõ
ñòîëáöàõ òåêóùåé ìàòðèöû A t�1
q a t Nj
t
i
ij
t� ��min , ,{ }1 1 , (4)
ãäå N — êîëè÷åñòâî öèêëîâ êëàññèôèêàöèè.
Øàã 3. Âû÷èñëåíèå ðàçíîñòíûõ ñðåçîâ A j
t îäíîâðåìåííî âî âñåõ ñòîëáöàõ
òåêóùåé ìàòðèöû A t�1 è ôîðìèðîâàíèå íåóïîðÿäî÷åííîé ìàòðèöû A t ñëåäóþ-
ùèì îáðàçîì:
A t
t t
n
t
m
t
m
t
mn
t
a a a
a a a
�
11 12 1
1 2
�
� � � �
�
, (5)
96 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
ïðè÷åì
a a q j nij
t
ij
t
j
t� � ��1 1, , ; (6)
ïðîâåðêà óñëîâèÿ ðàâåíñòâà íóëþ õîòÿ áû îäíîé èç ñòðîê íåóïîðÿäî÷åííîé
ìàòðèöû A t âèäà
� �A k m
k
t 0 1, , , (7)
à òàêæå óñëîâèÿ ðàâåíñòâà íóëþ âñåõ ñòðîê íåóïîðÿäî÷åííîé ìàòðèöû A t
� � �A i mi
t 0 1, , . (8)
Åñëè âûïîëíÿåòñÿ óñëîâèå (7), òî ïåðåõîäèì ê øàãó 4, à åñëè (8), òî —
ê øàãó 5.
Øàã 4. Ïðîäâèæåíèå ñ îáìåíîì (òðàíñïîçèöèÿ) âïðàâî ê êðàéíèì ñòîëáöàì
íóëåâûõ ýëåìåíòîâ aij
t â êàæäîé ñòðîêå íåóïîðÿäî÷åííîé ìàòðèöû A t (5) è ôîð-
ìèðîâàíèå óïîðÿäî÷åííîé ìàòðèöû A t ñëåäóþùèì îáðàçîì:
A Tr A i mi
t
i
t� �
�
2 1( ), , ; (9)
îäíîâðåìåííîå îáíóëåíèå k-ãî ýëåìåíòà pk âåêòîðà P, ñîîòâåòñòâóþùåãî îá-
íóëåííîé ñòðîêå A
k
t (7); ìàñêèðîâàíèå âñåõ íóëåâûõ ýëåìåíòîâ a
kj
t k-é îáíó-
ëåííîé ñòðîêè óïîðÿäî÷åííîé ìàòðèöû A t è ïåðåõîä ê øàãó 2.
Øàã 5. Ñîõðàíåíèå åäèíè÷íîãî çíà÷åíèÿ l-ãî ýëåìåíòà pl âåêòîðà P, ñîîò-
âåòñòâóþùåãî ïîñëåäíåé îáíóëåííîé ñòðîêå A
l
N â N -ì öèêëå; çàâåðøåíèå ïðî-
öåññà êëàññèôèêàöèè.
Òàêèì îáðàçîì, åäèíè÷íîå çíà÷åíèå l-ãî ýëåìåíòà pl âåêòîðà P îçíà÷àåò, ÷òî
âõîäíîé îáúåêò, çàäàííûé âåêòîðîì X åãî ïðèçíàêîâ, ïðèíàäëåæèò l-ìó êëàññó
Cl , ò.å. ( | , , )X p l m Cl l� � �1 1 .
Öèêë ïðîöåññà êëàññèôèêàöèè îñóùåñòâëÿåòñÿ çà øàãè 2–4. Â òàáë. 1 ïðèâå-
äåí ïðèìåð ðåàëèçàöèè ïðåäñòàâëåííîãî àëãîðèòìà êëàññèôèêàöèè, íà÷èíàÿ
ñ øàãà 2, äëÿ èñõîäíîé ìàòðèöû À 0 ðàçìåðà 3 3� âèäà
À 0
2 3 6
4 6 2
5 1 8
� .
Íà øàãå 2, êðîìå òåêóùåé ìàòðèöû À t�1, äëÿ t-ãî öèêëà óêàçàí âåêòîð ìèíè-
ìàëüíûõ ýëåìåíòîâ q j
t äëÿ êàæäîãî åå ñòîëáöà. Ïðî÷åðêàìè (ñì. òàáë. 1) îáî-
çíà÷åíû íóëåâûå ýëåìåíòû ïîëíîñòüþ îáíóëåííîé ñòðîêè ìàòðèöû, êîòîðûå
â äàëüíåéøåì íå îáðàáàòûâàþòñÿ. Åäèíè÷íîå çíà÷åíèå ýëåìåíòà ð3 âåêòîðà Ð
â äàííîì ñëó÷àå ñîîòâåòñòâóåò ìàêñèìàëüíîé ÄÔ g X3 ( ).
ÐÀÑØÈÐÅÍÈÅ ÁÀÇÈÑÀ ÑÀÀ Â.Ì. ÃËÓØÊÎÂÀ
Ïàðàëëåëüíàÿ îáðàáîòêà ïî ñòðîêàì è ñòîëáöàì ìàòðèöû A t òðåáóåò ââåäåíèÿ
äâóõ ðàçìå÷åííûõ ìàññèâîâ. Ðàññìîòðèì èõ:
� ðàçìå÷åííûé ìàññèâ ýëåìåíòîâ ( , ..., )a a an1 2 â âèäå âåêòîð-ñòðîêè
M a a ar n� � �ÏË 1 2 *, ãäå ÏË è * — ñïåöèàëüíûå ìàðêåðû, îáîçíà÷àþùèå ñî-
îòâåòñòâåííî ëåâóþ è ïðàâóþ ãðàíèöó ýòîãî ìàññèâà, � — óêàçàòåëü, n — ðàçìåð-
íîñòü ìàññèâà;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 97
� ðàçìå÷åííûé ìàññèâ ýëåìåíòîâ ( , ..., )a a am1 2 â âèäå âåêòîð-ñòîëáöà
M a a añ m� � �ÏË 1 2 *.
 êà÷åñòâå áàçèñíûõ îïåðàòîðîâ ïðèíÿòû ñëåäóþùèå [10, 12, 13]:
� ÓÑÒ( )Z — îïåðàòîð óñòàíîâêè ïîñëåäîâàòåëüíîñòè Z óêàçàòåëåé V è ìàð-
êåðîâ W, ãäå Z V W
�( );
� ÍÐÓ — îïåðàòîð íà÷àëüíîé ðàññòàíîâêè óêàçàòåëåé;
� ÔÈÍ — îïåðàòîð çàâåðøåíèÿ ðàáîòû ðåãóëÿðíîé ñõåìû;
� ÂÛÂ( )R — îïåðàòîð âûâîäà ðåçóëüòàòà;
�
�
C — îïåðàòîð ñäâèãà óêàçàòåëÿ � íà îäèí ýëåìåíò âïðàâî;
� ÒÐÀÍÑÏ( , )l r — ïåðåñòàíîâêà ñîñåäíèõ ýëåìåíòîâ l è r ìàññèâà M r .
Êðîìå òîãî, äàëåå èñïîëüçîâàíû òàêèå ëîãè÷åñêèå îïåðàöèè [7, 10, 12, 13],
êàê äèçúþíêöèÿ � �� , êîíüþíêöèÿ � �� , îòðèöàíèå �, êîìïîçèöèÿ A B�
(ò.å. ïîñëåäîâàòåëüíîå âûïîëíåíèå îïåðàòîðîâ A è B), àëüòåðíàòèâà [ ]� ( )A B�
(ò.å. åñëè �, òî A, èíà÷å B) è öèêë [ ]� { }A (ò.å. åñëè � ëîæíîå, òî A, ïðè � èñòèí-
íîì — êîíåö öèêëà), à òàêæå èñïîëüçóþòñÿ ñëåäóþùèå áàçèñíûå óñëîâèÿ: l r�
èñòèííîå ïðè âûïîëíåíèè óêàçàííîãî ñîîòíîøåíèÿ äëÿ ñîñåäíèõ ýëåìåíòîâ l è r
ìàññèâà è d(*) èñòèííîå ïðè äîñòèæåíèè óêàçàòåëÿ � ìàðêåðà *.
Îñîáåííîñòüþ ïðåäëîæåííîé îáðàáîòêè ýëåìåíòîâ ìàòðèöû ïî ÐÑ ÿâëÿåòñÿ
ëåâîñòîðîííÿÿ îáðàáîòêà ýëåìåíòîâ ìàññèâîâ M r è M c â ðåçóëüòàòå öèêëè÷åñ-
êîãî ñäâèãà óêàçàòåëÿ � ñëåâà íàïðàâî.
Ñ ó÷åòîì îñîáåííîñòè ïàðàëëåëüíîé îáðàáîòêè ìàññèâîâ äàííûõ ïî ÐÑ
îáîñíîâàííûìè ÿâëÿþòñÿ ñëåäóþùèå äîïîëíåíèÿ ê áàçèñíûì îïåðàòîðàì
è óñëîâèÿì:
� ÂÛ×( , )M q — îïåðàòîð ïàðàëëåëüíîãî âû÷èòàíèÿ èç âñåõ ýëåìåíòîâ ìàñ-
ñèâà M ýëåìåíòà q;
� ÍÓË( , )a an1 — îïåðàòîð îáíóëåíèÿ îäíîãî èç ýëåìåíòîâ ìàññèâà M ;
98 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
Öèêëû
Øàã 2 Øàã 3 Øàã 4
Âåêòîð PÒåêóùàÿ ìàòðèöà
A t � 1
Íåóïîðÿäî÷åííàÿ
ìàòðèöà A t
Óïîðÿäî÷åííàÿ
ìàòðèöà A t
1
2 3 6
4 6 2
5 1 8
[ ]2 1 2
0 2 4
2 5 0
3 0 6
2 4 0
2 5 0
3 6 0
0
0
0
�
�
�
�
�
�
�
�
�
�
2
2 4 0
2 5 0
3 6 0
[ ]2 4 0
0 0 0
0 1 0
1 2 0
0 0 0
1 0 0
1 2 0
0
0
0
�
�
�
�
�
�
�
�
�
�
3
� � �
1 0 0
1 2 0
[ ]1 0 0
� � �
0 0 0
0 2 0
� � �
0 0 0
2 0 0
0
0
0
�
�
�
�
�
�
�
�
�
�
4
� � �
� � �
2 0 0
[ ]2 0 0
� � �
� � �
0 0 0
� � �
� � �
� � �
0
0
1
�
�
�
�
�
�
�
�
�
�
Ò à á ë è ö à 1
� � èñòèííîå ïðè âûïîëíåíèè óñëîâèÿ íàõîæäåíèÿ íóëåâûõ ýëåìåíòîâ
â êðàéíèõ ïðàâûõ ïîçèöèÿõ ìàññèâà M r ;
� �k èñòèííîå ïðè âûïîëíåíèè óñëîâèÿ (7);
� � èñòèííîå ïðè âûïîëíåíèè óñëîâèÿ (8).
ÇÀÏÈÑÜ ÀËÃÎÐÈÒÌÀ ÊËÀÑÑÈÔÈÊÀÖÈÈ ÎÁÚÅÊÒÎÂ
 ÒÅÐÌÈÍÀÕ ÑÀÀ Â.Ì. ÃËÓØÊÎÂÀ
 êà÷åñòâå áàçîâûõ îïåðàöèé ïðåäëîæåííîãî àëãîðèòìà êëàññèôèêàöèè èñ-
ïîëüçóþòñÿ ñëåäóþùèå:
� âûäåëåíèå ìèíèìàëüíîãî ýëåìåíòà q j
t (4) â âåêòîðíîì ìàññèâå A j
t�1, ãäå
j n�1, ;
� âû÷èñëåíèå ÐÑ A j
t ñ ýëåìåíòàìè aij
t (6);
� ïðîäâèæåíèå ñ îáìåíîì (òðàíñïîçèöèÿ) âïðàâî ê êðàéíèì ïîçèöèÿì íóëå-
âûõ ýëåìåíòîâ â âåêòîðíîì ìàññèâå Ai
t (9) , ãäå i m�1, .
Ýòè áàçîâûå îïåðàöèè ìîæíî çàïèñàòü â âèäå ñîñòàâíûõ îïåðàòîðîâ ñëåäó-
þùèì îáðàçîì:
� cîñòàâíîé îïåðàòîð âûäåëåíèÿ ìèíèìàëüíîãî ýëåìåíòà ñðåäè ýëåìåíòîâ
( , )a a Am j
t
1
1PC � , îáîçíà÷åííûé êàê ìàññèâ M cj :
ÌÈÍ { ÓÑÒ ÓÑÒ Cj ma a d l r l r( , ):: [ (*)] [ ]( (min ) (min )1 � � � � �
�
)�
� � � � �[min ]( (min min) (min )r rÓÑÒ ÓÑÒ C}
�
, (10)
ñ ïîìîùüþ êîòîðîãî ðåàëèçóåòñÿ ïîñëåäîâàòåëüíîå âûäåëåíèå ìèíèìàëüíîãî
ýëåìåíòà â êàæäîé ïàðå (min, )r ñîñåäíèõ ýëåìåíòîâ ìàññèâà ( , )a an1 , íà÷èíàÿ
ñ ïåðâîé ïàðû ( , )l r , ñî ñäâèãîì íà îäèí ýëåìåíò âïðàâî ïî ìàññèâó è ñ óñòà-
íîâêîé (íàçíà÷åíèåì) ýëåìåíòó min îäíîãî èç äâóõ çíà÷åíèé;
� cîñòàâíîé îïåðàòîð âû÷èñëåíèÿ PC A j
t , êîòîðûé òàêæå ìîæíî îáîçíà÷èòü
êàê ìàññèâ M cj :
ÑÐÅÇ ÍÐÓ ÌÈÍ ÂÛj m j ma a a a( , ):: ( , )1 1� � � × j M( , min) (11)
ñ ó÷åòîì îäíîãî îïåðàòîðà ïîñëåäîâàòåëüíîãî äåéñòâèÿ ÌÈÍ j ma a( , )1 (10) è îä-
íîãî îïåðàòîðà ïàðàëëåëüíîãî äåéñòâèÿ ÂÛ× j M( , min) â êàæäîì ìàññèâå M cj ;
� cîñòàâíîé îïåðàòîð òðàíñïîçèöèè íóëåâûõ ýëåìåíòîâ â ìàññèâå Ài
t ,
îáîçíà÷åííûé êàê ìàññèâ M ri :
ÒÐÀÍÑ {ÒÐÀÍÑÏ C}i n ia a l r( , ):: [ ] ( , )1 � �
�
, (12)
ñ ïîìîùüþ êîòîðîãî ðåàëèçóåòñÿ ïîñëåäîâàòåëüíîå ïðîäâèæåíèå ñ îáìåíîì
â ñîñåäíèõ ïàðàõ (òðàíñïîçèöèÿ) íóëåâûõ ýëåìåíòîâ âïðàâî ê êðàéíèì ïîçè-
öèÿì â êàæäîì ìàññèâå M ri .
Òàêèì îáðàçîì, îïèñàííûé ðàíåå àëãîðèòì êëàññèôèêàöèè íà áàçå ÐÑ, íà÷è-
íàÿ ñ øàãà 2, ìîæíî çàïèñàòü ñëåäóþùèì îáðàçîì:
ÊËÀÑÑ ÑÐÅÇ ÍÓË( , ):: [ ] ( , ) [ ]( ( , )x x a a p pn
j
n
m k m1
1
1 1� � �
�
� �
� � �
�
ÒÐÀÍÑ } ÂÛÂ ÔÈÍ
i
m
na a P
1
1( , )) ( ) . (13)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 99
 çàïèñè (13) ñ ó÷åòîì íåîáõîäèìîñòè âûïîëíåíèÿ îïåðàöèè ôîðìèðîâàíèÿ
ñðåçîâ ÐÑ ïàðàëëåëüíî ïî âñåì n ñòîëáöàì ìàòðèöû A t è îïåðàöèè òðàíñïîçè-
öèè ïàðàëëåëüíî ïî âñåì m ñòðîêàì ìàòðèöû A t èñïîëüçîâàíî ñëåäóþùåå ïðåä-
ñòàâëåíèå ïðîöåññîâ ïàðàëëåëüíîé îáðàáîòêè:
� ÑÐÅÇ
j
n
ma a
�1
1( , ) — ïàðàëëåëüíîå âûïîëíåíèå îïåðàòîðà ÑÐÅÇ j ma a( , )1 (11)
ïî âñåì n ñòîìëáöàì M cj ;
� ÒÐÀÍÑ
i
m
na a
�1
1( , ) — ïàðàëëåëüíîå âûïîëíåíèå îïåðàòîðà ÒÐÀÍÑi na a( , )1
(12) ïî âñåì m ñòðîêàì M ri .
Êðîìå òîãî, â çàïèñè (13) îïåðàòîð ÂÛÂ( )P èñïîëüçóåòñÿ äëÿ âûâîäà ðå-
çóëüòàòà ïðîöåññà êëàññèôèêàöèè, à èìåííî âåêòîðà P ñ îäíèì åäèíè÷íûì ýëå-
ìåíòîì pl â ñîîòâåòñòâèè ñ øàãîì 5 àëãîðèòìà. Ïðè çàïèñè àëãîðèòìà êëàññèôè-
êàöèè â âèäå (13) ïðåäïîëàãàåòñÿ, ÷òî ïåðâîíà÷àëüíàÿ ìàòðèöà A 0 âèäà (3)
ñôîðìèðîâàíà äî íà÷àëà îïèñûâàåìîãî ïðîöåññà.
Àíàëèç ñîñòàâíîãî îïåðàòîðà âû÷èñëåíèÿ ÐÑ âèäà ÑÐÅÇ j ma a( , )1 (11) ïî-
çâîëÿåò ïðåäïîëîæèòü åãî ìîäèôèêàöèþ çà ñ÷åò ñîâìåùåíèÿ âûïîëíåíèÿ îïåðà-
òîðîâ ÌÈÍ j ma a( , )1 è ÂÛ× j M( , min), íàïðèìåð ñ èñïîëüçîâàíèåì îïåðàöèè
äåêðåìåíòà íàä âñåìè ýëåìåíòàìè ( , )a am1 , íî â êàæäîì ñòîëáöå M cj ïàðàëëåëü-
íî. Ýòî çíà÷èòåëüíî óñêîðèò ðåàëèçàöèþ îïåðàòîðà ÑÐÅÇ j ma a( , )1 .
ÇÀÊËÞ×ÅÍÈÅ
Àíàëèç çàïèñè àëãîðèòìà êëàññèôèêàöèè íà áàçå ôîðìèðîâàíèÿ ÐÑ â òåðìè-
íàõ ÑÀÀ Â.Ì. Ãëóøêîâà ïîäòâåðäèë êîìïàêòíîñòü ïðåäñòàâëåíèÿ ïðè òàêîì
ïîäõîäå è âîçìîæíîñòü äàëüíåéøåãî óñîâåðøåíñòâîâàíèÿ ìåòîäà îáðàáîòêè äâó-
ìåðíûõ (ìàòðè÷íûõ) ìàññèâîâ äàííûõ ïî ÐÑ, à òàêæå ôóíêöèîíàëüíóþ ìîù-
íîñòü áàçèñà ÑÀÀ Â.Ì. Ãëóøêîâà, ÷òî ïîçâîëÿåò îïèñûâàòü â åãî òåðìèíàõ
ñëîæíûå àëãîðèòìû, â äàííîì ñëó÷àå àëãîðèòì êëàññèôèêàöèè îáúåêòîâ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ö å é ò ë è í Ã . Å . Ââåäåíèå â àëãîðèòìèêó. — Ê.: Ñôåðà, 1998. — 310 ñ.
2. Ö å é ò ë è í à . Å . Àëãåáðàè÷åñêàÿ àëãîðèòìèêà: òåîðèÿ è ïðèëîæåíèÿ // Êèáåðíåòèêà è ñèñ-
òåìíûé àíàëèç. — 2003. — ¹ 1. — Ñ. 8–18.
3. À í ä î í Ô . È . , Ä î ð î ø å í ê î À . Å . , Ö å é ò ë è í Ã . Å . , ß ö å í ê î Å . À .
Àëãåáðîàëãîðèòìè÷åñêèå ìîäåëè è ìåòîäû ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ. — Êèåâ:
Àêàäåìïåðèîäèêà, 2007. — 671 ñ.
4. À í ä î í Ô . È . , Ä î ð î ø å í ê î À . Å . , Æ å ð å á Ê . À . Ïðîãðàììèðîâàíèå âûñîêîïðîèçâî-
äèòåëüíûõ ïàðàëëåëüíûõ âû÷èñëåíèé: ôîðìàëüíûå ìîäåëè è ãðàôè÷åñêèå óñêîðèòåëè // Êè-
áåðíåòèêà è ñèñòåìíûé àíàëèç. — 2011. — ¹ 4. — Ñ. 176–187.
5. À í ä î í Ô . È . , Ä î ð î ø å í ê î À . Å . , Á å ê å ò î â À . Ã . , È î â ÷ å â Â . À . , ß ö å í -
ê î Å . À . Èíñòðóìåíòàëüíûå ñðåäñòâà àâòîìàòèçàöèè ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ íà
îñíîâå àëãåáðû àëãîðèòìîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2015. — ¹ 1. —
Ñ. 162–170.
6. Ö å é ò ë è í Ã . Å . , À ì î í ñ À . À . , Ã î ë î â è í Î . Â . , Ç ó á ö î â À . Þ . Èíòåãðèðîâàííûé
èíñòðóìåíòàðèé ïðîåêòèðîâàíèÿ è ñèíòåçà êëàññîâ àëãîðèòìîâ è ïðîãðàìì // Êèáåðíåòèêà è
ñèñòåìíûé àíàëèç. — 2000. — ¹ 3. — Ñ. 165–169.
100 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5
7. Ö å é ò ë è í Ã . Å . Àëãåáðû Ãëóøêîâà è òåîðèÿ êëîíîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
2003. — ¹ 4. — Ñ. 48–58.
8. Áî ð è ñ î â Å . Ñ . Ïîëóàâòîìàòè÷åñêàÿ ñèñòåìà äåêîìïîçèöèè ïîñëåäîâàòåëüíûõ ïðîãðàìì
äëÿ ïàðàëëåëüíûõ âû÷èñëèòåëåé ñ ðàñïðåäåëåííîé ïàìÿòüþ // Êèáåðíåòèêà è ñèñòåìíûé àíà-
ëèç. — 2004. — ¹ 3. — Ñ. 139–150.
9. Ö å é ò ë è í Ã . Å . , È â à í î â Å . À . Ñïåöèàëèçèðîâàííûå èíôîðìàöèîííûå òåõíîëîãèè äëÿ
ëèö ñ ôèçè÷åñêèìè îãðàíè÷åíèÿìè // Óïðàâëÿþùèå ñèñòåìû è ìàøèíû. — 2008. — ¹ 5. —
Ñ. 62–69.
10. Ö å é ò ë è í Ã . Å . Òðàíñôîðìàöèîííàÿ ñâîäèìîñòü è ñèíòåç àëãîðèòìîâ è ïðîãðàìì ñèìâîëü-
íîé îáðàáîòêè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2006. — ¹ 5. — Ñ. 165–173.
11. Î â ñ ÿ ê  . Ê . , Î â ñ ÿ ê Î .  . Ïîð³âíÿëüíèé àíàë³ç àëãåáðè÷íèõ ìåòîä³â çàïèñó àëãîðèòì³â
// Îá÷èñëþâàëüí³ ìåòîäè ³ ñèñòåìè ïåðåòâîðåííÿ ³íôîðìàö³¿: ²² íàóê.-òåõí. êîíô., 4–5 æîâòíÿ
2012 ð.: Çá. íàóê. ïðàöü. — Ëüâ³â: ÔÌI ÍÀÍÓ, 2012. — Ñ. 117–119.
12. Ö å é ò ë è í Ã . Å . Ïðîåêòèðîâàíèå ïîñëåäîâàòåëüíûõ àëãîðèòìîâ ñîðòèðîâêè: êëàññèôèêà-
öèÿ, òðàíñôîðìàöèÿ, ñèíòåç // Ïðîãðàììèðîâàíèå. — 1989. — ¹ 3. — Ñ. 3–24.
13. Ö å é ò ë è í Ã . Å . Ðàñïàðàëëåëèâàíèå àëãîðèòìîâ ñîðòèðîâêè // Êèáåðíåòèêà. — 1989. —
¹ 6. — Ñ. 67–74.
14. Ê î æ å ì ÿ ê î Â . Ï . , Ì à ð ò û í þ ê Ò . Á . , Õ î ì þ ê Â . Â . Îñîáåííîñòè ñòðóêòóðíîãî ïðî-
ãðàììèðîâàíèÿ ñèíõðîííûõ àëãîðèòìîâ ñîðòèðîâêè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
2006. — ¹ 5. — Ñ. 122–133.
15. ß ö å í ê î Å . À . Ðåãóëÿðíûå ñõåìû àëãîðèòìîâ àäðåñíîé ñîðòèðîâêè è ïîèñêà // Óïðàâëÿþ-
ùèå ñèñòåìû è ìàøèíû. — 2004. — ¹ 5. — Ñ. 61–66.
16. Ì à ð ò è í þ ê Ò . Á . Ðåêóðñèâí³ àëãîðèòìè áàãàòîîïåðàíäíî¿ îáðîáêè ³íôîðìàö³¿. Ìîíî-
ãðàô³ÿ. — ³ííèöÿ: ÓͲÂÅÐÑÓ̖³ííèöÿ, 2000. — 216 ñ.
17. Ì à ð ò û í þ ê Ò . Á . , Õ î ì þ ê Â . Â . Ìóëüòèîáðàáîòêà ìàññèâîâ äàííûõ ïî ðàçíîñòíûì
ñðåçàì // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2011. — ¹ 6. — Ñ. 132–137.
18. Ì à ð ò û í þ ê Ò . Á . Ìîäåëü ïîðîãîâîãî íåéðîíà íà îñíîâå ïàðàëëåëüíîé îáðàáîòêè ïî ðàç-
íîñòíûì ñðåçàì // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2005. — ¹ 4. — Ñ. 78–89.
19. Â à ñ þ ð à À . Ñ . , Ì à ð ò è í þ ê Ò . Á . , Ê ó ï å ð ø ò å é í Ë . Ì . Ìåòîäè òà çàñîáè íåéðî-
ïîä³áíî¿ îáðîáêè äàíèõ äëÿ ñèñòåì êåðóâàííÿ. Ìîíîãðàô³ÿ. — ³ííèöÿ: ÓͲÂÅÐÑÓ̖³ííè-
öÿ, 2008. — 175 ñ.
20. Ì à ð ò û í þ ê Ò . Á . , Á ó ä à À . Ã . , Õ î ì þ ê Â . Â . , Ê î æ å ì ÿ ê î À . Â . , Ê ó ï å ð -
ø ò å é í Ë . Ì . Êëàññèôèêàòîð áèîìåäèöèíñêèõ ñèãíàëîâ // Èñêóññòâåííûé èíòåëëåêò. —
2010. — ¹ 3. — Ñ. 88–95.
21. à î ð å ë è ê À . Ë . , Ñ ê ð è ï ê è í  . À . Ìåòîäû ðàñïîçíàâàíèÿ: ó÷åá. ïîñîáèå. — 3-å èçä. —
Ì.: Âûñø. øê., 1989. — 232 ñ.
22. Ä è ñ ê ð è ì è í à í ò í û é àíàëèç. — http:// www.statsoft.ru/home/textbook/modules/stdiscan.html
23. Ä è ñ ê ð è ì è í à í ò í û å ôóíêöèè äëÿ êëàññèôèêàöèè ìíîãîìåðíûõ îáúåêòîâ. — http://www
uran.donetsk.ua/~masters/2005/kita/kapustina/library/disc_an2.html.
24. Ç ó á ÷ ó ê  . È . , Ñ è ã î ð ñ ê è é  . Ï . , Ø ê ó ð î À . Í . Ñïðàâî÷íèê ïî öèôðîâîé ñõåìî-
òåõíèêå / Ê.: Òåõíèêà, 1990. — 448 ñ.
Ïîñòóïèëà 22.12.2014
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 101
|