Кластеризация последовательностей видеоданных на основе гармонических k-средних
Работа посвящена сегментации кластеризации видеопоследовательностей с помощью анализа многомерных временных последовательностей. Предложен подход к использованию глубокой итеративной временной деформации совместно с матричным методом гармонических k-средних. Такая процедура сегментации кластеризации...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2019 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/180846 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Кластеризация последовательностей видеоданных на основе гармонических k-средних / С.В. Машталир, М.И. Столбовой, С.В. Яковлев // Кибернетика и системный анализ. — 2019. — Т. 55, № 2. — С. 36-43. — Бібліогр.: 22 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-180846 |
|---|---|
| record_format |
dspace |
| spelling |
Машталир, С.В. Столбовой, М.И. Яковлев, С.В. 2021-10-22T14:46:29Z 2021-10-22T14:46:29Z 2019 Кластеризация последовательностей видеоданных на основе гармонических k-средних / С.В. Машталир, М.И. Столбовой, С.В. Яковлев // Кибернетика и системный анализ. — 2019. — Т. 55, № 2. — С. 36-43. — Бібліогр.: 22 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/180846 004.93 Работа посвящена сегментации кластеризации видеопоследовательностей с помощью анализа многомерных временных последовательностей. Предложен подход к использованию глубокой итеративной временной деформации совместно с матричным методом гармонических k-средних. Такая процедура сегментации кластеризации в отличие от традиционного подхода нечувствительна к начальному выбору центроидов, что особенно удобно в условиях анализа произвольных данных больших объемов. Розглянуто сегментацію кластеризацію відеопослідовностей за допомогою аналізу багатовимірних часових послідовностей. Запропоновано підхід для використання глибокої ітеративної часової деформації разом з матричним методом гармонічних k-середніх. Така процедура сегментації кластеризації на відміну від традиційного підходу не є чутливою до початкового вибору центроїдів, що особливо зручно в умовах аналізу довільних даних великих обсягів. The study is devoted to segmentation–clustering of video sequences by the analysis of multidimensional time sequences. An approach is proposed for using an iterative deepening time warping in conjunction with the matrix harmonic k-means. This segmentation-clustering procedure, unlike the traditional approach, is insensitive to the initial centroids selection, which is especially useful in the analysis of arbitrary mass data. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кібернетика Кластеризация последовательностей видеоданных на основе гармонических k-средних Кластеризація послідовностей відеоданих на основі гармонічних k-середніх Video sequences clustering by the k-harmonic means Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Кластеризация последовательностей видеоданных на основе гармонических k-средних |
| spellingShingle |
Кластеризация последовательностей видеоданных на основе гармонических k-средних Машталир, С.В. Столбовой, М.И. Яковлев, С.В. Кібернетика |
| title_short |
Кластеризация последовательностей видеоданных на основе гармонических k-средних |
| title_full |
Кластеризация последовательностей видеоданных на основе гармонических k-средних |
| title_fullStr |
Кластеризация последовательностей видеоданных на основе гармонических k-средних |
| title_full_unstemmed |
Кластеризация последовательностей видеоданных на основе гармонических k-средних |
| title_sort |
кластеризация последовательностей видеоданных на основе гармонических k-средних |
| author |
Машталир, С.В. Столбовой, М.И. Яковлев, С.В. |
| author_facet |
Машталир, С.В. Столбовой, М.И. Яковлев, С.В. |
| topic |
Кібернетика |
| topic_facet |
Кібернетика |
| publishDate |
2019 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Кластеризація послідовностей відеоданих на основі гармонічних k-середніх Video sequences clustering by the k-harmonic means |
| description |
Работа посвящена сегментации кластеризации видеопоследовательностей с помощью анализа многомерных временных последовательностей. Предложен подход к использованию глубокой итеративной временной деформации совместно с матричным методом гармонических k-средних. Такая процедура сегментации кластеризации в отличие от традиционного подхода нечувствительна к начальному выбору центроидов, что особенно удобно в условиях анализа произвольных данных больших объемов.
Розглянуто сегментацію кластеризацію відеопослідовностей за допомогою аналізу багатовимірних часових послідовностей. Запропоновано підхід для використання глибокої ітеративної часової деформації разом з матричним методом гармонічних k-середніх. Така процедура сегментації кластеризації на відміну від традиційного підходу не є чутливою до початкового вибору центроїдів, що особливо зручно в умовах аналізу довільних даних великих обсягів.
The study is devoted to segmentation–clustering of video sequences by the analysis of multidimensional time sequences. An approach is proposed for using an iterative deepening time warping in conjunction with the matrix harmonic k-means. This segmentation-clustering procedure, unlike the traditional approach, is insensitive to the initial centroids selection, which is especially useful in the analysis of arbitrary mass data.
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/180846 |
| citation_txt |
Кластеризация последовательностей видеоданных на основе гармонических k-средних / С.В. Машталир, М.И. Столбовой, С.В. Яковлев // Кибернетика и системный анализ. — 2019. — Т. 55, № 2. — С. 36-43. — Бібліогр.: 22 назв. — рос. |
| work_keys_str_mv |
AT maštalirsv klasterizaciâposledovatelʹnosteivideodannyhnaosnovegarmoničeskihksrednih AT stolbovoimi klasterizaciâposledovatelʹnosteivideodannyhnaosnovegarmoničeskihksrednih AT âkovlevsv klasterizaciâposledovatelʹnosteivideodannyhnaosnovegarmoničeskihksrednih AT maštalirsv klasterizacíâposlídovnosteivídeodanihnaosnovígarmoníčnihkseredníh AT stolbovoimi klasterizacíâposlídovnosteivídeodanihnaosnovígarmoníčnihkseredníh AT âkovlevsv klasterizacíâposlídovnosteivídeodanihnaosnovígarmoníčnihkseredníh AT maštalirsv videosequencesclusteringbythekharmonicmeans AT stolbovoimi videosequencesclusteringbythekharmonicmeans AT âkovlevsv videosequencesclusteringbythekharmonicmeans |
| first_indexed |
2025-11-26T01:39:50Z |
| last_indexed |
2025-11-26T01:39:50Z |
| _version_ |
1850603898988920832 |
| fulltext |
ÓÄÊ 004.93
Ñ.Â. ÌÀØÒÀËÈÐ, Ì.È. ÑÒÎËÁÎÂÎÉ, Ñ.Â. ßÊÎÂËÅÂ
ÊËÀÑÒÅÐÈÇÀÖÈß ÏÎÑËÅÄÎÂÀÒÅËÜÍÎÑÒÅÉ ÂÈÄÅÎÄÀÍÍÛÕ
ÍÀ ÎÑÍÎÂÅ ÃÀÐÌÎÍÈ×ÅÑÊÈÕ k-ÑÐÅÄÍÈÕ
Àííîòàöèÿ. Ðàáîòà ïîñâÿùåíà ñåãìåíòàöèè–êëàñòåðèçàöèè âèäåîïîñëåäî-
âàòåëüíîñòåé ñ ïîìîùüþ àíàëèçà ìíîãîìåðíûõ âðåìåííûõ ïîñëåäîâàòåëü-
íîñòåé. Ïðåäëîæåí ïîäõîä ê èñïîëüçîâàíèþ ãëóáîêîé èòåðàòèâíîé âðåìåí-
íîé äåôîðìàöèè ñîâìåñòíî ñ ìàòðè÷íûì ìåòîäîì ãàðìîíè÷åñêèõ k-ñðåäíèõ.
Òàêàÿ ïðîöåäóðà ñåãìåíòàöèè–êëàñòåðèçàöèè â îòëè÷èå îò òðàäèöèîííîãî
ïîäõîäà íå÷óâñòâèòåëüíà ê íà÷àëüíîìó âûáîðó öåíòðîèäîâ, ÷òî îñîáåííî
óäîáíî â óñëîâèÿõ àíàëèçà ïðîèçâîëüíûõ äàííûõ áîëüøèõ îáúåìîâ.
Êëþ÷åâûå ñëîâà: ñåãìåíòàöèÿ, êëàñòåðèçàöèÿ, ìíîãîìåðíûå ïîñëåäîâà-
òåëüíîñòè, âèäåî, äèíàìè÷åñêàÿ äåôîðìàöèÿ.
ÂÂÅÄÅÍÈÅ
Çàäà÷à êëàñòåðèçàöèè è êëàññèôèêàöèè ìàññèâîâ íàáëþäåíèé çàíèìàåò âàæíîå
ìåñòî â Data Mining, à äëÿ åå ðåøåíèÿ íà ñåãîäíÿøíèé äåíü ñóùåñòâóåò ìíî-
æåñòâî ïîäõîäîâ, ìåòîäîâ è àëãîðèòìîâ, îñíîâàííûõ íà ñîîòâåòñòâóþùåì ìàòå-
ìàòè÷åñêîì àïïàðàòå ïðè ðàçëè÷íûõ àïðèîðíûõ ïðåäïîëîæåíèÿõ î ïðèðîäå äàí-
íûõ [1–6]. Îñîáîå ìåñòî ïðè ýòîì çàíèìàþò ìåòîäû, îñíîâàííûå íà ïðîòîòè-
ïàõ-öåíòðîèäàõ áëàãîäàðÿ ÿñíîé ôèçè÷åñêîé èíòåðïðåòàöèè è ïðîñòîé
÷èñëåííîé ðåàëèçàöèè, áàçèðóþùèåñÿ íà òåõ èëè èíûõ àëãîðèòìàõ îïòèìèçà-
öèè ñîîòâåòñòâóþùèõ êðèòåðèåâ êà÷åñòâà. Çäåñü ïðåæäå âñåãî îòìåòèì ïðîöå-
äóðû k-means, k-medoids, k-representatives, ñóùåñòâóþùèå êàê â ÷åòêèõ (crisp),
òàê è â íå÷åòêèõ (fuzzy) âàðèàíòàõ è ïîðîäèâøèå ìíîæåñòâî ìîäèôèêàöèé. Ýòè
ïðîöåäóðû îòëè÷àþòñÿ îäíà îò äðóãîé âèäîì èñïîëüçóåìîé ìåòðèêè, çàäàþùåé
ðàññòîÿíèå ìåæäó íàáëþäåíèÿìè èç èñõîäíîãî ìàññèâà, è âîçìîæíûìè ïðîòî-
òèïàìè-öåíòðîèäàìè. Íàèáîëåå ïîïóëÿðíûìè çäåñü ÿâëÿþòñÿ ïðîöåäóðû
k-means ïðè èñïîëüçîâàíèè åâêëèäîâîé ìåòðèêè. Ïðè ýòîì èñõîäíóþ çàäà÷ó
óäàåòñÿ ñâåñòè ê ñîîòâåòñòâóþùåìó êëàññó çàäà÷ êâàäðàòè÷íîé îïòèìèçàöèè.
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ïóñòü èñõîäíîé èíôîðìàöèåé ÿâëÿåòñÿ ìàññèâ âåêòîðíûõ íàáëþäåíèé
X x x x k x N� { }( ), ( ), , ( ), , ( )1 2 � � , x k x k x k x ki N( ) ( ( ), , ( ), , ( ))� 1 � �
T ,
ãäå k — íîìåð íàáëþäåíèé â èñõîäíîì ìàññèâå. Òîãäà èñõîäíàÿ çàäà÷à êëàñòåðè-
çàöèè ñâîäèòñÿ ê ïîèñêó íàáîðà öåíòðîèäîâ c cM1, ,� ; c c c cj j ji jN� ( , , , , )1 � �
T,
j M�1, , îáåñïå÷èâàþùèõ ìèíèìóì öåëåâîé ôóíêöèè:
E x k c u k x k c k x kj j j
j
M
k
N
j( ( ), ) ( ) | | ( ) | | ( )( ( )� � � �
��
�� 2
11
� c x k cj j
j
M
k
N
) ( ( ) ),T �
��
��
11
(1)
ãäå � j k( ) — óðîâåíü ÷åòêîé ïðèíàäëåæíîñòè k-ãî íàáëþäåíèÿ j-ìó êëàñòåðó.
Óðîâåíü ÷åòêîé ïðèíàäëåæíîñòè çàäàåòñÿ âûðàæåíèåì
� j k
x k j
( )
, ( )
�
1
0
åñëè ïðèíàäëåæèò -ìó êëàñòåðó,
â ïðîòèâíîì ñëó àå.�
�
�
�
(2)
 çàäà÷àõ íå÷åòêîé êëàñòåðèçàöèè óðîâåíü ïðèíàäëåæíîñòè ïðèíèìàåò çíà-
÷åíèÿ íà îòðåçêå
0 1� �� j k( ) (3)
36 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2
© Ñ.Â. Ìàøòàëèð, Ì.È. Ñòîëáîâîé, Ñ.Â. ßêîâëåâ, 2019
è óäîâëåòâîðÿåò óñëîâèþ
� j
j
M
k k N( ) , , ,
�
� � �
1
1 1 2 � . (4)
Çàäà÷à êëàñòåðèçàöèè ðåçêî óñëîæíÿåòñÿ â ñëó÷àå, åñëè îáðàáîòêå ïîäëåæàò
íå âåêòîðû, à ìàòðèöû
x k x k i n ii i( ) ( ) , , , , ; , , ,,� � �{ }
1 2 1 21 2 1 2� � � .
Òàêàÿ ñèòóàöèÿ âîçíèêàåò â çàäà÷àõ îáðàáîòêè èçîáðàæåíèé, êîãäà êëàñòåðèçà-
öèè ïîäëåæàò îòäåëüíûå êàäðû âèäåîïîñëåäîâàòåëüíîñòè. Åñòåñòâåííî, ìîæíî
îñóùåñòâèòü âåêòîðèçàöèþ ìàòðèöû x k( ), ïðåîáðàçîâàâ åå â ( )n�
1 -âåêòîð.
Îäíàêî â äàëüíåéøåì â ïðîöåññå ðåøåíèÿ çàäà÷è îïòèìèçàöèè ìîãóò âîçíèê-
íóòü òðóäíîñòè, ñâÿçàííûå ñ òàê íàçûâàåìûì ýôôåêòîì ïðîêëÿòèÿ ðàçìåðíî-
ñòè. Èìåííî ïîýòîìó åñòåñòâåííî ðàññìàòðèâàòü â êà÷åñòâå îáúåêòîâ êëàñòå-
ðèçàöèè íåïîñðåäñòâåííî ìàòðèöû x k( ), èñïîëüçóÿ âûðàæåíèÿ äëÿ íîðì
â ìàòðè÷íîé ôîðìå, ñîãëàñîâàííîé ñ âåêòîðíûìè ôîðìàìè ýòèõ íîðì.  ÷àñò-
íîñòè, â ñòàòüå [7] ââåäåí ìàòðè÷íûé àíàëîã k-means, à â [8] — ìàòðè÷íûé
àíàëîã fuzzy c-means, â îñíîâó êîòîðûõ áûëà ïîëîæåíà ñôåðè÷åñêàÿ íîðìà
Ôðîáåíèóñà. Ïðåäñòàâëÿåòñÿ öåëåñîîáðàçíûì äëÿ îáðàáîòêè èçîáðàæåíèé èñ-
ïîëüçîâàòü è äðóãèå íîðìû, îáåñïå÷èâàþùèå ïðîöåäóðå êëàñòåðèçàöèè íîâûå
ñïåöèôè÷åñêèå ñâîéñòâà [9].
ÌÀÒÐÈ×ÍÛÉ ÌÅÒÎÄ HARMONIC k-MEANS
Ðàçâèòèåì ìåòîäà k-means, èñïîëüçóþùèì åâêëèäîâó íîðìó, ÿâëÿåòñÿ ïðîöåäóðà
Harmonic k-means (HKM) [10–12], â îñíîâå êîòîðîé — ïîíÿòèå ãàðìîíè÷åñêîãî
ñðåäíåãî. Ãàðìîíè÷åñêèì ñðåäíèì äëÿ ñêàëÿðíîãî íàáîðà X x x� { ( ), ( ),1 2 �
� �, ( ), , ( )x k x N } ÿâëÿåòñÿ âûðàæåíèå
x
N
x k
H
k
N
�
�
�
� 1
1
( )
. (5)
 ìîíîãðàôèè [1] ïîêàçàíî, ÷òî ïðîöåäóðà ÍÊÌ ïðèâîäèò ê ðåçóëüòàòàì,
áëèçêèì ê òåì, êîòîðûå îáåñïå÷èâàþòñÿ k-means. Îäíàêî ýòà ïðîöåäóðà ãîðàçäî
ìåíåå ÷óâñòâèòåëüíà ê íà÷àëüíîìó çàäàíèþ öåíòðîèäîâ-ïðîòîòèïîâ, ÷òî îñîáåí-
íî âàæíî ïðè îáðàáîòêå áîëüøèõ ìàññèâîâ èíôîðìàöèè. Åñëè êðèòåðèé êà÷åñòâà
êëàñòåðèçàöèè âåêòîðíûõ íàáëþäåíèé äëÿ k-means èìååò âèä (1), òî öåëåâóþ
ôóíêöèþ äëÿ ÍÊÌ ìîæíî ïðåäñòàâèòü êàê
E x k c
M
x k c
j
jj
M
k
N
( ( ), )
| | ( ) | |
�
��
�
�
�
1
2
1
1
�
� ��
�
�
�
M
x k c x k cj jj
M
k
N
1
1
1
( ( ) ) ( ( ) )T
. (6)
Åñëè îáðàáàòûâàåìàÿ âûáîðêà X x x x k x N� { }( ), ( ), , ( ), , ( )1 2 � � îáðàçîâàíà
( )n
� -ìàòðèöàìè x k x ki i( ) ( ),� { }
1 2
, òî èñïîëüçîâàíèå íîðìû Ôðîáåíèóñà â (6)
ñîîòâåòñòâåííî ïðèâîäèò ê âûðàæåíèþ
E x k c
M
x k c
j
jj
M
k
N
( ( ), )
| | ( ) | |
�
��
�
�
�
1
2
1
1
�
� ��
�
�
�
M
x k c x k cj jj
M
k
N
1
1
1
Sp T(( ( ) )( ( ) ) )
, (7)
ãäå Sp ( )� — ñèìâîë ñëåäà ìàòðèöû, c j , j M�1 2, , ,� , — ìàòðè÷íûå ïðîòîòè-
ïû-öåíòðîèäû.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 37
Îïòèìèçàöèÿ öåëåâîé ôóíêöèè (6) ïîçâîëÿåò ïîëó÷èòü ñëåäóþùóþ îöåíêó [13]:
c
x k c x k c x
j
j
k
N
j
j
M
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
� �| | ( ) | | | | ( ) | |4
1
2
1
2
( )
| | ( ) | | | | ( ) | |
k
x k c x k cj
k
N
j
j
M
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
� �4
1
2
1
2
�
� � ��
� �
� �Sp SpT(( ( ) )( ( ) ) ) (( ( ) )(x k c x k c x k c xj j
k
N
j
M
j
2
1 1
( ) ) ) ( )
(( ( ) )( ( ) ) )
k c x k
x k c x k c
j
j j
�
�
�
�
�
�
�
�
� �
�
�
�
T
TSp
1
2
2
k
N
j
M
j jx k c x k c
� �
�
�
� � � �
�
�
�
�
�
�
�
1 1
1
2
Sp T(( ( ) )( ( ) ) )
. (8)
Ïðè ýòîì óðîâåíü íå÷åòêîé ïðèíàäëåæíîñòè íà îñíîâå (8) çàäàåòñÿ â âèäå
� j
j
j
j
M
j
k
x k c
x k c
x k c
( )
| | ( ) | |
| | ( ) | |
(( ( ) )
�
�
�
�
��
�
�
�
4
4
1
Sp ( ( ) ) )
(( ( ) )( ( ) ) )
x k c
x k c x k c
j
j j
j
M
�
� �
�
�
�
�
T
TSp
2
2
1
. (9)
Äàííàÿ îöåíêà áëèçêà ê îöåíêå ïðèíàäëåæíîñòè íà îñíîâå FCM [7]:
� j
j
j
j
M
k
x k c
x k c
( )
| | ( ) | |
| | ( ) | |
�
�
�
�
�
�
�
2
2
1
. (10)
Íåñëîæíî óâèäåòü, ÷òî ñ âû÷èñëèòåëüíîé òî÷êè çðåíèÿ ïðîöåäóðà ÍÊÌ ëèøü
íåíàìíîãî ñëîæíåå ñòàíäàðòíîãî ìåòîäà FCM. Ýòî îáúÿñíÿåòñÿ òåì, ÷òî âû÷èñëå-
íèå ñëåäà ìàòðèöû íå òðåáóåò çíà÷èòåëüíûõ âû÷èñëèòåëüíûõ ðåñóðñîâ, ÿâëÿÿñü
ëèíåéíîé ôóíêöèåé, è ñîîòâåòñòâåííî íå óâåëè÷èâàåò ñëîæíîñòè àëãîðèòìà.
ÊËÀÑÒÅÐÈÇÀÖÈß ÌÀÒÐÈ×ÍÛÕ ÏÎÑËÅÄÎÂÀÒÅËÜÍÎÑÒÅÉ
Ñ ÈÑÏÎËÜÇÎÂÀÍÈÅÌ HARMONIC k-MEANS
Çàäà÷à êëàñòåðèçàöèè ðåçêî óñëîæíÿåòñÿ, åñëè îáúåêòîì èññëåäîâàíèÿ ÿâëÿþò-
ñÿ íå îòäåëüíûå èçîáðàæåíèÿ, à èõ ïîñëåäîâàòåëüíîñòè, ïðåäñòàâëåííûå, íà-
ïðèìåð, âèäåîðÿäîì. Çàäà÷à ñåãìåíòàöèè è êëàñòåðèçàöèè äëÿ âåêòîðíûõ ïî-
ñëåäîâàòåëüíîñòåé ðàññìîòðåíà â [14, 15]. Ïðè ýòîì ïðåäïîëàãàëîñü, ÷òî
â ðàñïîðÿæåíèè èññëåäîâàòåëÿ èìååòñÿ åäèíñòâåííûé âðåìåííîé ðÿä, êîòîðûé
ðàçáèò íà îäíîðîäíûå ó÷àñòêè ñ ïîìîùüþ òåõ èëè èíûõ àëãîðèòìîâ íå÷åòêîé
êëàñòåðèçàöèè. Ñèòóàöèÿ ñóùåñòâåííî óñëîæíÿåòñÿ, åñëè îáðàáîòêå ïîäëåæèò
ìíîæåñòâî ðÿäîâ. Ïðè ýòîì íà ïåðâûé ïëàí âûíîñèòñÿ âîïðîñ îöåíêè ðàññòîÿ-
íèÿ ìåæäó ïîñëåäîâàòåëüíîñòÿìè ðàçëè÷íîé äëèíû. Çäåñü ìîæåò áûòü èñïîëü-
çîâàíà ïðîöåäóðà Dynamic Time Warping (DTW) [16]. Îäíàêî òàêîé êëàñòåðèçà-
öèè ìîãóò áûòü ïîäâåðãíóòû òîëüêî êîðîòêèå ïîñëåäîâàòåëüíîñòè [17, 18].
Åñëè îáðàáàòûâàåìûå ñèãíàëû ñîäåðæàò áîëüøîå ÷èñëî îòñ÷åòîâ (êàäðîâ âèäåî-
ïîñëåäîâàòåëüíîñòè), òî òàêîé ïîäõîä ñòàíîâèòñÿ íåýôôåêòèâíûì. Â ýòîé ñè-
òóàöèè âåñüìà ïîëåçíîé ìîæåò îêàçàòüñÿ ïðîöåäóðà Iterative Deepening Dyna-
mic Time Warping (IDDTW), îïèñàííàÿ â [19]. Îäíàêî åå ïðèìåíåíèå òðåáóåò
ñóùåñòâåííîé ìîäèôèêàöèè äëÿ ñëó÷àÿ, åñëè îáúåêòîì èññëåäîâàíèé ÿâëÿþòñÿ
äîñòàòî÷íî äëèííûå ìàòðè÷íûå âðåìåííûå ðÿäû.
Ñòàíäàðòíàÿ DTW îñíîâàíà íà âû÷èñëåíèè ðàññòîÿíèÿ (ñõîæåñòè) ìåæäó äâóìÿ
âðåìåííûìè ìàòðè÷íûìè ïîñëåäîâàòåëüíîñòÿìè: X x x x k x N� { }( ), ( ), , ( ), , ( )1 2 � � ,
38 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2
x k x ki i( ) ( ),� { }
1 2
, è Y y y x l x M� { }( ), ( ), , ( ), , ( )1 2 � � , y l y li i( ) ( ),� { }
1 2
, ïðè
N M� ñ èñïîëüçîâàíèåì ñôåðè÷åñêîé ìåòðèêè
d x k y l x k y l x k y l( ( ), ( )) ( ( ( ) ( ))( ( ) ( )) ) /� � �Sp T 1 2 (11)
ìåæäó äâóìÿ îòäåëüíûìè êàäðàìè ðÿäîâ X è Y .
Òàêèì îáðàçîì, èñõîäíîé èíôîðìàöèåé äëÿ ðàñ÷åòîâ ÿâëÿåòñÿ ( )N M
-ìàò-
ðèöà ðàññòîÿíèé (11) ìåæäó âñåìè îòñ÷åòàìè äâóõ ðÿäîâ.
 êà÷åñòâå ìåðû áëèçîñòè ðÿäîâ âûáèðàåòñÿ òàê íàçûâàåìûé îïòèìàëüíûé
èñêðèâëåííûé ïóòü (optimal warping path), êîòîðûé îáîçíà÷èì D N M( , ). Òàêîé
ïóòü ñòðîèòñÿ ñ ïîìîùüþ ïðîöåäóðû äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ:
D k l d x k y l D k l D k l D k l( , ) ( ( ), ( )) min ( , ), ( , ), ( ,� � � � � �{ 1 1 1 1)}, (12)
k N l M� �1 2 1 2, , , ; , , ,� � .
Î÷åâèäíî, ÷òî ïðè áîëüøèõ N è M èñïîëüçîâàíèå ìåòîäîâ äèíàìè÷åñêîãî
ïðîãðàììèðîâàíèÿ äëÿ ïîèñêà D N M( , ) ñòàíîâÿòñÿ íåýôôåêòèâíûì â ñèëó
áîëüøîé ðàçìåðíîñòè äàííîãî êëàññà çàäà÷.
Ïðåîäîëåòü ýòè òðóäíîñòè âîçìîæíî ñ ïîìîùüþ IDDTW, îäíàêî ïðè èñ-
ïîëüçîâàíèè ñòàíäàðòíîé ïðîöåäóðû òàêæå âîçíèêàþò ïðîáëåìû. Ïðè ýòîì èñ-
õîäíûå ðÿäû ðàçáèâàþòñÿ íà ÷åòûðå ó÷àñòêà (îòñ÷åòà), à íà êàæäîì èç íèõ ýòè
ïîñëåäîâàòåëüíîñòè çàìåíÿþòñÿ ñâîèìè ñðåäíèìè çíà÷åíèÿìè. Äàëåå ïðîâîäèò-
ñÿ ñòàíäàðòíîå îöåíèâàíèå ðàññòîÿíèÿ ìåæäó ìàòðè÷íûìè ðÿäàìè, ñîäåðæàùè-
ìè ïî ÷åòûðå îòñ÷åòà. Åñëè ïîëó÷àåìàÿ îöåíêà ðàññòîÿíèÿ íåóäîâëåòâîðèòåëüíà,
â ðàññìîòðåíèå ââîäèòñÿ 8, 16 è ò.ä. ó÷àñòêîâ. Ýòî îçíà÷àåò, ÷òî êîëè÷åñòâî
îòñ÷åòîâ âîçðàñòàåò â ãåîìåòðè÷åñêîé ïðîãðåññèè.
Äëÿ îïðåäåëåíèÿ ðàññòîÿíèÿ ìîæíî èñïîëüçîâàòü êàê âûðàæåíèå (12), òàê
è áîëåå ïðîñòóþ ñ âû÷èñëèòåëüíîé òî÷êè çðåíèÿ îöåíêó (11), ïîñêîëüêó â ïî-
ñëåäíåì ñëó÷àå ðàññìàòðèâàåòñÿ N N� �2 3, ,� ó÷àñòêîâ îáðàáàòûâàåìûõ ðÿäîâ,
à íå 2 N , ãäå N � 2 3, ,�
Òàêèì îáðàçîì, åñëè îáðàáîòêå ïîäëåæèò Q âðåìåííûõ ðÿäîâ x x xq Q1, , , ,� � ,
êàæäûé èç êîòîðûõ ñîäåðæèò N N Nq Q1, , , ,� � îòñ÷åòîâ, ïîëó÷àåì íàáîð ìàò-
ðè÷íûõ ïîñëåäîâàòåëüíîñòåé x x xq Q1, , , ,� � , ñîäåðæàùèõ ôèêñèðîâàííîå êî-
ëè÷åñòâî K îòñ÷åòîâ, ò.å.
x x x k x Kq q q q� { }( ), , ( ), , ( )1 � � , x k x kq qi i( ) ( ),� { }
1 2
.
Ïðè ýòîì êâàäðàò ðàññòîÿíèÿ ìåæäó ëþáûìè äâóìÿ îòñ÷åòàìè ðàçíûõ ðÿäîâ ñ
èñïîëüçîâàíèåì âûðàæåíèÿ (11) çàäàåòñÿ êàê
d x k y l x k y l x k y lq p q p q p
2 ( ( ), ( )) ( ( ) ( ))( ( ) ( ))� � �Sp T . (13)
Ðàññìàòðèâàÿ M öåíòðîèäîâ c j , j m�1 2, , ,� , â âèäå ( )n k
� -ìàòðèö ñ ýëå-
ìåíòàìè, ïîäëåæàùèìè îöåíèâàíèþ, ìîæíî ïðåäëîæèòü ñëåäóþùóþ ïðîöåäóðó
êëàñòåðèçàöèè ìàòðè÷íûõ âðåìåííûõ ðÿäîâ ïðîèçâîëüíîé äëèíû:
c
d x c d x c x
d x
j
q j
q
Q
q j
j
M
q
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �4
1
2
1
2
4
( , ) ( , )
( q j
q
Q
q j
j
M
c d x c, ) ( , )
�
�
�
�
� �
�
�
�
�
�
�
�
1
2
1
2
,
(14)
� j
q j
j
M
q j
q
d x c
d x c
( )
( , )
( , )
�
�
�
�
�
4
4
1
.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 39
Èìååì îáîáùåíèå ìåòîäà Harmonic k-means íà ñëó÷àé äëèííûõ ìàòðè÷íûõ
ïîñëåäîâàòåëüíîñòåé, ñîäåðæàùèõ ðàçíîå ÷èñëî îòñ÷åòîâ.
ÝÊÑÏÅÐÈÌÅÍÒÀËÜÍÛÅ ÐÅÇÓËÜÒÀÒÛ ÑÅÃÌÅÍÒÀÖÈÈ
ÂÈÄÅÎÏÎÑËÅÄÎÂÀÒÅËÜÍÎÑÒÅÉ
Àíàëèç ïðåäëîæåííîãî ïîäõîäà ê ñåãìåíòàöèè–êëàñòåðèçàöèè ìíîãîìåðíûõ
äàííûõ îñóùåñòâëÿåòñÿ ñ èñïîëüçîâàíèåì âèäåîðîëèêîâ èç äîêóìåíòàëüíîãî
öèêëà “Destroyed in Seconds” ôèëüìîâ êàíàëà Discovery. Âûáîð ïîäîáíûõ èñ-
õîäíûõ äàííûõ îáúÿñíÿåòñÿ òåì, ÷òî â ýòîì ñëó÷àå íà îòíîñèòåëüíî êîðîòêèõ
âèäåîïîñëåäîâàòåëüíîñòÿõ ïðîèñõîäèò íåîäíîêðàòíîå èçìåíåíèå ñöåíû êàê
èç-çà ñìåíû ðàêóðñà ñíèìàþùåé êàìåðû, òàê è èç-çà áûñòðûõ èçìåíåíèé, ïðî-
èñõîäÿùèõ â ðåçóëüòàòå íåêîåãî èíöèäåíòà (êàòàñòðîôû) â ýòèõ âèäåî.
Íà ðèñ. 1 äàí ïðèìåð âèäåîïîñëåäîâàòåëüíîñòåé è èõ ïðîñòðàíñòâåííûõ ñåã-
ìåíòàöèé, ïîëó÷åííûõ àâòîìàòè÷åñêè (áåç âìåøàòåëüñòâà ÷åëîâåêà), êîòîðûå
íåîáõîäèìû äëÿ ôîðìèðîâàíèÿ ìàññèâà âåêòîðíûõ íàáëþäåíèé X .
Òàêèì îáðàçîì, â êà÷åñòâå èñõîäíûõ äàííûõ äëÿ ýêñïåðèìåíòà âûñòóïàåò ìíî-
æåñòâî ðåçóëüòàòîâ ïðîñòðàíñòâåííûõ ñåãìåíòàöèé âèäåîïîñëåäîâàòåëüíîñòåé ðàçëè÷-
íîé äëèíû. Çäåñü êàæäàÿ ïîñëåäîâàòåëüíîñòü ñîäåðæèò ñîâîêóïíîñòü ñåãìåíòîâ, êîòî-
ðûå îáëàäàþò ñõîæèìè õàðàêòåðèñòèêàìè è ñëàáî êîððåëèðóò ñ ñîñåäíèìè ñåãìåíòàìè.
Ðàññìîòðèì ïðèìåð ñåãìåíòàöèè–êëàñòåðèçàöèè âèäåîïîñëåäîâàòåëüíîñòè,
ïðåäñòàâëåííîé íà ðèñ. 1. Â îáùåé ñëîæíîñòè âèäåîïîñëåäîâàòåëüíîñòü ðàçáèâàåòñÿ
íà ïÿòü ñåãìåíòîâ. Íà ðèñ. 2 äëÿ ÷åòûðåõ èç íèõ ïðèâåäåíû õàðàêòåðíûå êàäðû, îò-
êóäà âèäíî, íàñêîëüêî îòëè÷àþòñÿ ñåãìåíòû ìåæäó ñîáîé. Ïðè ýòîì êàæäûé ñåã-
ìåíò èìååò ñâîè çíà÷åíèÿ õàðàêòåðèñòèê, ïî êîòîðûì ôîðìèðóåòñÿ êëàñòåð. Çäåñü
N — íîìåð êàäðà âèäåîïîñëåäîâàòåëüíîñòè, D — ðàññòîÿíèå ìåæäó êàäðàìè.
Ñ ó÷åòîì òîãî, ÷òî â îñíîâå ïîäõîäà ê êëàñòåðèçàöèè ëåæèò Iterative
Deepening Dynamic Time Warping, íàìè ðàññìîòðåíà ñèòóàöèÿ ñðàâíåíèÿ äâóõ
âèäåîïîñëåäîâàòåëüíîñòåé ðàçíîé äëèíû (ðèñ. 3). Ñðàâíåíèå ðåçóëüòàòîâ êëàñòå-
ðèçàöèé–ñåãìåíòàöèé ïîçâîëÿåò ñäåëàòü âûâîä, ÷òî ïîèñê çíà÷åíèé õàðàêòåðè-
ñòèê âðåìåííîãî ðÿäà íå çàâèñèò îò åãî äëèíû. Òàê, â ñëó÷àå, êîãäà ñðàâíèâàå-
40 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2
Ðèñ. 1. Âèäåîïîñëåäîâàòåëüíîñòè è èõ ïðîñòðàíñòâåííûå ñåãìåíòàöèè
ìûé ðÿä ìåíüøåé äëèíû ÿâëÿåòñÿ ïîäìíîæåñòâîì èñõîäíîé ïîñëåäîâàòåëüíîñ-
òè, ïîëó÷àåì òå æå õàðàêòåðèñòèêè, ÷òî è â ñîîòâåòñòâóþùåì ìíîãîìåðíîì
âðåìåííîì ðÿäå áîëüøåé äëèíû. Òàêèì îáðàçîì, ïðåäëîæåííûé ïîäõîä ïîçâîëÿ-
åò ðàçáèâàòü âèäåîïîñëåäîâàòåëüíîñòè ðàçëè÷íîé äëèíû íà ñîâîêóïíîñòü êëàñ-
òåðîâ, ñîäåðæàùèõ ïîñëåäîâàòåëüíîñòè êàäðîâ ñ àíàëîãè÷íûìè õàðàêòåðèñòèêà-
ìè. Öåíòðîèä êëàñòåðà ïðè ýòîì ìîæåò ñëóæèòü êëþ÷åâûì êàäðîì ýòîãî
ñåãìåíòà. Ìîæíî óòâåðæäàòü, ÷òî ñîâîêóïíîñòü ïîëó÷åííûõ ïðåäëîæåííûì
ïîäõîäîì öåíòðîèäîâ áóäåò îïðåäåëÿòü âèäåîïîñëåäîâàòåëüíîñòü â öåëîì.
Ïðåäñòàâëÿåò èíòåðåñ ñðàâíåíèå ïðåäëîæåííîé ïðîöåäóðû ñ èçâåñòíûìè ìåòî-
äàìè êëàñòåðèçàöèè âèäåîäàííûõ. Îäíàêî áîëüøèíñòâî èññëåäîâàòåëåé, êàê ïðàâè-
ëî, ïðèâîäÿò äàííûå âû÷èñëèòåëüíûõ ýêñïåðèìåíòîâ áåç ïðåäîñòàâëåíèÿ êîíêðåò-
íîãî èñõîäíîãî âèäåîìàòåðèàëà è åãî õàðàêòåðèñòèê, îãðàíè÷èâàÿñü óêàçàíèåì
ëèøü îáùèõ äàííûõ. Ýòîò ôàêò äåëàåò íåêîððåêòíûìè ëþáûå ïðÿìûå ñðàâíåíèÿ
ðàáîòû àëãîðèòìîâ îñîáåííî ïðè àíàëèçå âèäåîäàííûõ ïðîèçâîëüíîé ïðèðîäû. Ïî-
ýòîìó â íàñòîÿùåé ñòàòüå îñíîâíîå âíèìàíèå óäåëåíî òåîðåòè÷åñêîìó îáîñíîâàíèþ
ýôôåêòèâíîñòè ïðåäëîæåííîãî ïîäõîäà è ýêñïåðèìåíòàëüíûì ïîäòâåðæäåíèåì åãî
ðàáîòîñïîñîáíîñòè. Â äàëüíåéøåì ïðåäïîëàãàåòñÿ îñóùåñòâèòü ñðàâíèòåëüíûé àíà-
ëèç èçâåñòíûõ ïîäõîäîâ íà îñíîâå âûáîðà òåñòîâûõ âèäåîäàííûõ.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 41
Ðèñ. 2. Âðåìåííàÿ ñåãìåíòàöèÿ âèäåîïîñëåäîâàòåëüíîñòè
N
D
Ðèñ. 3. Ñðàâíåíèå êëàñòåðèçàöèé–ñåãìåíòàöèé âèäåîïîñëåäîâàòåëüíîñòåé ðàçëè÷íîé äëèíû
D
D
N
N
ÇÀÊËÞ×ÅÍÈÅ
Ðàññìîòðåííûé ìåòîä êëàñòåðèçàöèè ìàòðè÷íûõ ïîñëåäîâàòåëüíîñòåé ïðîèç-
âîëüíîé äëèíû ÿâëÿåòñÿ ìîäèôèêàöèåé è îáîáùåíèåì ìåòîäà Harmonic
k-means. Äàííàÿ ïðîöåäóðà ïðåäíàçíà÷åíà äëÿ îáðàáîòêè (ñåãìåíòàöèè, îáíà-
ðóæåíèè èçìåíåíèé ñâîéñòâ, êëàñòåðèçàöèè áåç ó÷èòåëÿ) áîëüøèõ îáúåìîâ âè-
äåîäàííûõ è ñ âû÷èñëèòåëüíîé òî÷êè çðåíèÿ áîëåå ýôôåêòèâíà.  îòëè÷èå îò
òðàäèöèîííîãî ìåòîäà k-means â çàäà÷àõ âèäåîîáðàáîòêè ðàññìàòðèâàåìàÿ
ïðîöåäóðà íåêðèòè÷íà ê íà÷àëüíîìó âûáîðó ïðîòîòèïîâ-öåíòðîèäîâ è ïîçâî-
ëÿåò îñóùåñòâëÿòü êëàñòåðèçàöèþ äàííûõ â óñëîâèÿõ ïåðåêðûâàþùèõñÿ êëàñ-
ñîâ [20]. Ðåçóëüòàòû ïðåäñòàâëÿþò îñîáûé èíòåðåñ ïðè àíàëèçå âèäåîäàííûõ
ñ íå÷åòêî âûðàæåííûìè ïåðåõîäàìè ìåæäó ñöåíàìè. Òàêèì îáðàçîì, ïðåäî-
ñòàâëÿåòñÿ âîçìîæíîñòü ðàçðàáîòêè íîâûõ ïîäõîäîâ ïî áûñòðîìó êîíòåêñòíî-
ìó ïîèñêó â áàçàõ âèäåîäàííûõ ïðîèçâîëüíîé ïðèðîäû. Ïåðñïåêòèâíûì ïðè
îáðàáîòêå è êëàñòåðèçàöèè âèäåîäàííûõ ïðåäñòàâëÿåòñÿ òàêæå èñïîëüçîâàíèå
êîíôèãóðàöèîííûõ ïðîñòðàíñòâ ãåîìåòðè÷åñêèõ îáúåêòîâ [21, 22].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Gan G., Ma C., Wu J. Data clustering: Theory, algorithms and applications. Philadelphia: SIAM,
2007. 466 p.
2. Jain A.K., Dubes R.C. Algorithms for clustering data. Englewood Cliffs, N.J.: Prentice Hall, 1988.
320 p.
3. Olson D.L., Dursun D. Advanced data mining techniques. Berlin: Springer, 2008. 180 p.
4. Hulianytskyi L., Malyshko S. Big data in information analytical system “NEWSCAPE”. In: Data
Stream Mining & Processing: Proc. IEEE First Int. Conf. on Data Stream Mining & Processing
(23–27 August, 2016, Lviv, Ukraine) 2016. P. 382–386.
5. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization problems.
Optimization Methods and Applications. 2017. Vol. 130. P. 239–250.
6. Hulianytskyi L., Riasna I. Automatic classification method based on a fuzzy similarity relation.
Cybernetics and Systems Analysis. 2016. Vol. 52, N 1. P. 30–37.
7. Âåäìåäü À.Ã., Ìàøòàëèð Ñ.Â., Ñàêàëî Å.Ñ. Ìàòðè÷íûé àëãîðèòì ñàìîîáó÷åíèÿ êàðòû Êîõî-
íåíà â çàäà÷àõ îáðàáîòêè èçîáðàæåíèé. Ñèñòåìè óïðàâë³ííÿ, íàâ³ãàö³¿ òà çâ’ÿçêó. 2009.
Âèï. 1. Ñ. 188–192.
8. Bodyanskiy Ye., Volkova V., Skuratov M. Matrix neuro-fuzzy self-organizing clustering network.
Scientific Journal of Riga Technical University. Computer Science. Information Technology and
Management Science. 2011. Vol. 49. P. 54–58.
9. Mashtalir V.P., Yakovlev S.V. Point-set methods of clusterization of standard information.
Cybernetics and Systems Analysis. 2001. Vol. 37, N 3. P. 295–307.
10. Han J., Kamber M. Data mining: Concepts and techniques. San Francisco: Morgan Kaufmann, 2006. 26 p.
11. Xu R., Wunsch D. Survey of clustering algorithms. IEEE Transactions on Neural Networks. 2005.
Vol. 16, N 3. P. 645–678.
12. G��ung��or Z., ��Unler A. K-harmonic means data clustering with tabu-search method. Applied
Mathematical Modelling. 2008. Vol. 32, N 6. P. 1115–1125.
13. Zhang B., Hsu M., Dayal V. K-harmonic means: A spatial clustering algorithm with boosting. First
International Workshop on Temporal, Spatial and Spatio-Temporal Data Mining. London:
Springer-Verlag, 2000. P. 31–45.
14. Abonyi J., Feil B., Nemeth S., Arva P. Fuzzy clustering based segmentation of timeseries. Lecture
Notes in Computer Science. 2003. Vol. 2810. P. 275–285.
15. Liao T.W. Clustering of time series data: A survey. Pattern Recognition. 2005. Vol. 38, N 11.
P. 1857–1874.
16. Berndt D.J., Clifford J. Using dynamic time warping to find patterns in time series. In: Proc.
3rd International Conference on Knowledge Discovery and Data Mining. KDD Workshop, 1994.
P. 359–370.
42 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2
17. Setlak G., Bodyanskiy Y., Pliss I., Vynokurova O., Peleshko D., Kobylin I. Adaptive fuzzy
clustering of multivariate short time series with unevenly distributed observations based on matrix
neuro-fuzzy self-organizing network. Advances in Intelligent Systems and Computing. 2018.
Vol. 643. P. 308–315.
18. Bodyanskiy Y., Kobylin I., Rashkevych Y., Vynokurova O., Peleshko D. Hybrid fuzzy clustering
algorithm of unevenly and asynchronically spaced time series in computer engineering. In: Proc.
14th International Conference on Advanced Trends in Radioelectronics, Telecommunications and
Computer Engineering (20–24 February 2018, Lviv–Slavske, Ukraine). P. 930–935.
19. Chu S., Keogh E., Hart D., Pazzani M. Iterative deepening dynamic time warping for time series.
In: Proc. of the 2nd SIAM International Conference on Data Mining, 2002. P. 195–212.
20. Gerasin S.N., Shlyakhov V.V., Yakovlev S.V. Set coverings and tolerance relations. Cybernetics and
Systems Analysis. 2008. Vol. 43, N 3. P. 333–340.
21. Stoyan Y.G., Yakovlev S.V. Configuration space of geometric objects. Cybernetics and Systems
Analysis. 2018. Vol. 54, N 5. P. 716–726.
22. Yakovlev S.V. On some classes of spatial configurations of geometric objects and their
formalization. Journal of Automation and Information Sciences. 2018. Vol. 50, N 9. P. 38–50.
Íàä³éøëà äî ðåäàêö³¿ 26.07.2018.
Ñ.Â. Ìàøòàë³ð, Ì.². Ñòîëáîâèé, Ñ.Â. ßêîâëåâ
ÊËÀÑÒÅÐÈÇÀÖ²ß ÏÎÑ˲ÄÎÂÍÎÑÒÅÉ Â²ÄÅÎÄÀÍÈÕ ÍÀ ÎÑÍβ
ÃÀÐÌÎͲ×ÍÈÕ k-ÑÅÐÅÄͲÕ
Àíîòàö³ÿ. Ðîçãëÿíóòî ñåãìåíòàö³þ–êëàñòåðèçàö³þ â³äåîïîñë³äîâíîñòåé çà
äîïîìîãîþ àíàë³çó áàãàòîâèì³ðíèõ ÷àñîâèõ ïîñë³äîâíîñòåé. Çàïðîïîíîâàíî
ï³äõ³ä äëÿ âèêîðèñòàííÿ ãëèáîêî¿ ³òåðàòèâíî¿ ÷àñîâî¿ äåôîðìàö³¿ ðàçîì ç
ìàòðè÷íèì ìåòîäîì ãàðìîí³÷íèõ k-ñåðåäí³õ. Òàêà ïðîöåäóðà ñåãìåíòà-
ö³¿–êëàñòåðèçàö³¿ íà â³äì³íó â³ä òðàäèö³éíîãî ï³äõîäó íå º ÷óòëèâîþ äî ïî-
÷àòêîâîãî âèáîðó öåíòðî¿ä³â, ùî îñîáëèâî çðó÷íî â óìîâàõ àíàë³çó äîâ³ëü-
íèõ äàíèõ âåëèêèõ îáñÿã³â.
Êëþ÷îâ³ ñëîâà: ñåãìåíòàö³ÿ, êëàñòåðèçàö³ÿ, áàãàòîâèì³ðí³ ïîñë³äîâíîñò³,
â³äåî, äèíàì³÷íà äåôîðìàö³ÿ.
S.V. Mashtalir, M.I. Stolbovyi, S.V. Yakovlev
VIDEO SEQUENCES CLUSTERING BY THE k-HARMONIC MEANS
Abstract. The study is devoted to segmentation–clustering of video sequences
by the analysis of multidimensional time sequences. An approach is proposed
for using an iterative deepening time warping in conjunction with the matrix
harmonic k-means. This segmentation-clustering procedure, unlike the traditional
approach, is insensitive to the initial centroids selection, which is especially
useful in the analysis of arbitrary mass data.
Keywords: segmentation, clustering, multidimensional sequences, video,
dynamic warping.
Ìàøòàëèð Ñåðãåé Âëàäèìèðîâè÷,
äîêòîð òåõí. íàóê, ïðîôåññîð êàôåäðû Õàðüêîâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà ðàäèîýëåêòðîíèêè,
e-mail: sergii.mashtalir@nure.ua.
Ñòîëáîâîé Ìèõàèë Èâàíîâè÷,
àñïèðàíò Õàðüêîâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà ðàäèîýëåêòðîíèêè, e-mail: st.mihail92@gmail.com.
ßêîâëåâ Ñåðãåé Âñåâîëîäîâè÷,
äîêòîð ôèç.-ìàò. íàóê, ïðîôåññîð, ïðîôåññîð êàôåäðû Íàöèîíàëüíîãî àýðîêîñìè÷åñêîãî óíèâåðñèòåòà
èì. Í.Å. Æóêîâñêîãî «Õàðüêîâñêèé àâèàöèîííûé èíñòèòóò», e-mail: svsyak7@gmail.com.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 43
|