Гибридный подход к кластеризации видеорядов различной длины
Рассмотрена задача кластеризации многомерных временных рядов (векторных и матричных) различной длины в условиях неизвестного количества классов и их взаимного пересечения. Предложен метод решения этой задачи на основе гибридизации иерархического агломеративного и нечеткого, основанного на центроидах...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2019 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/180784 |
| 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: | Гибридный подход к кластеризации видеорядов различной длины / С.В. Машталир, М.И. Столбовой, С.В. Яковлев // Проблемы управления и информатики. — 2019. — № 2. — С. 80-88. — Бібліогр.: 29 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859828677197430784 |
|---|---|
| author | Машталир, С.В. Столбовой, М.И. Яковлев, С.В. |
| author_facet | Машталир, С.В. Столбовой, М.И. Яковлев, С.В. |
| citation_txt | Гибридный подход к кластеризации видеорядов различной длины / С.В. Машталир, М.И. Столбовой, С.В. Яковлев // Проблемы управления и информатики. — 2019. — № 2. — С. 80-88. — Бібліогр.: 29 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Рассмотрена задача кластеризации многомерных временных рядов (векторных и матричных) различной длины в условиях неизвестного количества классов и их взаимного пересечения. Предложен метод решения этой задачи на основе гибридизации иерархического агломеративного и нечеткого, основанного на центроидах, подходов с использованием метрики Левенштейна. Процесс кластеризации сводится к последовательности элементарных операций над матрицей расстояний между анализируемыми исходными последовательностями. Развиваемый подход крайне прост с вычислительной точки зрения, позволяет решать задачи кластеризации временных рядов произвольной природы как в условиях неопределенности относительно количества классов данных, так и их формы и уровня взаимного пересечения.
Істотне збільшення обсягу даних, що підлягають аналізу і обробці, вимагає запровадження нових ефективних засобів і методів їх збору та зберігання. Особливо актуальною така задача стає при аналізі мультимедійних, зокрема, відеоданих, в силу їх значної надмірності. Один із шляхів зниження обсягу оброблюваної інформації — кластеризація/сегментація відеопослідовностей для виділення однорідних за змістом сегментів. При цьому виникає завдання вибору необхідної кількості кластерів як вихідної інформації. Стаття присвячена розробці гібридного методу кластеризації для аналізу відеопослідовностей різної довжини. Метод зберігає переваги і виключає недоліки агломеративної ієрархічної і нечіткої кластеризації. Для визначення подібності між сегментами відеопослідовностей використовується метрика Левенштейна, що дозволяє розраховувати відстані між багатовимірними послідовностями різної довжини. Критерієм завершення процесу кластеризації в цілому, і, відповідно, якість одержуваного результату визначається індексом Данна. Запропонований гібридний підхід до кластеризації відеопослідовностей відрізняється обчислювальною простотою реалізації і дозволяє вирішувати завдання аналізу багатовимірних часових рядів довільної природи в тому випадку, коли заздалегідь складно визначити необхідну кількість кластерів для розбиття і в умовах невизначеності щодо можливого їх перекриття, тобто в разі, коли результатом кластеризації є побудова покриття, а не розбиття даних.
A significant increase in the amount of data to be analyzed and processed requires the introduction of new efficient tools and methods for their collection and storage. This task is especially important when analyzing multimedia, in particular, video data, due to their great redundancy. One of the ways to reduce the amount of information processed is clustering / segmentation of video sequences to isolate parts that are homogeneous in content. This raises the problem of choosing the required number of clusters as source information. The article is devoted to the development of a hybrid clustering method for analyzing video sequences of various lengths. The method saves the advantages and eliminates the disadvantages of agglomerative hierarchical and fuzzy clusterings. To determine the similarity between segments of video sequences, the Levenshtein metric is used, which allows to calculate the distances between multidimensional sequences of different lengths. The criterion for the clustering process completion as a whole, and, accordingly, the result quality is determined by the Dunn index. The proposed hybrid approach to clustering video sequences is computationally simple to implement and allows solving the multidimensional time series analysis problems of arbitrary nature in the case when it is difficult to determine in advance the necessary number of clusters for splitting and under conditions of uncertainty about their possible overlap, i.e. in the case where the clustering result is the cover construction, and not data partitioning (exact cover construction).
|
| first_indexed | 2025-12-07T15:31:16Z |
| format | Article |
| fulltext |
© С.В. МАШТАЛИР, М.И. СТОЛБОВОЙ, С.В. ЯКОВЛЕВ, 2019
80 ISSN 0572-2691
МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ
УДК 004.93
С.В. Машталир, М.И. Столбовой, С.В. Яковлев
ГИБРИДНЫЙ ПОДХОД К КЛАСТЕРИЗАЦИИ
ВИДЕОРЯДОВ РАЗЛИЧНОЙ ДЛИНЫ
Ключевые слова: иерархическая кластеризация, нечеткая кластеризация, мно-
гомерные последовательности, видео, метрика.
Введение
Анализ данных любого вида является одним из приоритетных направлений
развития науки. При этом важное значение приобретает анализ визуальной ин-
формации. Особое место по сложности интерпретации среди такой информации
занимает анализ видеоданных, что связано, в первую очередь, с их большой избы-
точностью и слабой структурированностью. Поэтому одна из проблем анализа
видео — структурирование информации с выделением однородных сегментов и
ключевых кадров [1–3], что позволяет понизить размерность исходных данных и
упростить дальнейшую их обработку. Одним из решений этой задачи является
подход, связанный с сегментацией–кластеризацией видеоданных [4–6]. Задача
кластеризации данных в целом — одна из основных в общей проблеме интеллек-
туального анализа данных. В настоящее время разработано множество подходов,
методов и алгоритмов для ее решения: от сугубо эмпирических до строго матема-
тических [7–12]. При этом особое место занимает задача кластеризации времен-
ных рядов-последовательностей [13–15], когда исходная информация задается в
форме набора последовательностей
)},(...,),(...,),1({,...,,...,,, 21 Nxkxxxxxxx qqqqQq
где Nk ...,,2,1 — отсчеты дискретного времени, N — число этих отсчетов в
каждой из выборок ....,,2,1, Qqxq
Сложность такой задачи связана с тем, что наблюдения в каждой из выборок
)(kxq строго упорядочены и не подлежат перемещению. Задача существенно
усложняется, если обрабатываемые ряды — многомерные последовательности, т.е.
векторные — при ,))(...,),(...,),(()( T
1
N
qnqiqq Rkxkxkxkx либо матричные —
при ....,,2,1,...,,2,1,)}({)( 21, 21
viniRkxkx vn
iqiq Последняя ситуация до-
статочно часто возникает в задачах обработки видеопоследовательностей, когда
каждое отдельное изображение можно описать с помощью )( vn -матрицы ).(kxq
Результатом решения задачи кластеризации является разбиение исходного
массива данных на m кластеров–классов ,...,,, 21 mClClCl в каждом из которых
содержащиеся в них данные взаимно близки в смысле применяемой метрики
(метрического подхода).
Международный научно-технический журнал
«Проблемы управления и информатики», 2019, № 2 81
Следуя данному в [7] определению, методы кластеризации условно можно
разделить на два больших класса: иерархические и основанные на разбиениях.
Это не противоречит другим существующим подходам к кластеризации [9, 15].
В настоящее время наиболее популярны методы, основанные на разбиениях, бла-
годаря своей математической строгости, наглядности получаемых результатов,
развитому программному обеспечению. Ключевым понятием здесь являются цен-
троиды-прототипы — представители-образцы, вокруг которых группируются
данные каждого кластера. Наиболее характерными представителями этого класса
являются методы k-средних, k-гармонических средних, с-средних, k-медоидов,
отличающиеся типом используемой метрики и целевой функцией, оптимизируе-
мой в процессе решения задачи. Основной недостаток этого подхода — необхо-
димость априорного задания числа кластеров m, что часто ведет к многократному
решению задачи при разных значениях m. Этому классу принадлежит достаточно
громоздкий, с вычислительной точки зрения, метод x-средних [9].
Иерархические методы, которые делятся на агломеративные и дивизимные,
автоматически определяют оптимальное число кластеров путем попарного объ-
единения данных и последовательного «выращивания» кластеров либо последо-
вательного дробления исходной выборки на подкластеры до достижения требуе-
мой точности в смысле принятого критерия качества кластеризации. Иерархиче-
ские методы просты, наглядны, формируют кластеры произвольной формы, не
требуют, как правило, задания дополнительных параметров, хотя и несколько
громоздки в вычислительной реализации (имеют сложность
2( )).О Q Заметим, что
в [16] предложен метод иерархической агломеративной кластеризации больших
массивов изображений (матричных сигналов), продемонстрировавший свою эф-
фективность в решении ряда практических задач.
Оба подхода имеют свои преимущества и недостатки. Поэтому метод, объ-
единяющий в себе преимущества обоих подходов, весьма привлекателен с точки
зрения пользователя-практика.
Ситуация существенно усложняется, когда обрабатываемые последователь-
ности Qq xxxx ...,,...,,, 21 имеют разную длину ....,,...,,, 21 Qq NNNN В этом слу-
чае о расчете центроидов не может быть и речи, поскольку не ясно , какой долж-
на быть длина каждого центроида и насколько по длине отличаются центроиды
каждого кластера. В этой ситуации более предпочтительным представляется
использование иерархического агломеративного подхода, ключевым моментом
которого является выбор меры схожести между любыми двумя рядами из набо-
ра ,...,,...,,, 21 Qq xxxx на основе которой будет проводиться объединение отдель-
ных последовательностей в кластерах.
Оценка схожести–различия между многомерными
временными рядами разной длины
Пусть имеется два временных ряда: )},(...,),(...,),1({ NxkxxX ...),1({yY
)},(...,),(..., Myly ,MN где )(kx и )(ly — либо векторы, либо матрицы соот-
ветствующих размерностей. Необходимо определить меру близости между этими
последовательностями. Расстояние между любыми двумя наблюдениями можно
задать либо с помощью евклидовой метрики
,)(),(,))()(()()())(),((
1
222
n
i
n
ii Rlykxlykxlykxlykxd
либо сферической метрики
.)(),(,))()())(()((Sp))(),(( T2 vnRlykxlykxlykxlykxd
Для оценки схожести между временными рядами в настоящее время наиболее
популярна так называемая динамическая временная деформация (DTW) [17, 18] и
ее различные модификации [19–25]. В основе DTW лежит понятие искривленного
82 ISSN 0572-2691
пути (warping path) между точками )1(),1( yx и ),(),( MyNx для нахождения ко-
торого используется весьма громоздкая, с вычислительной точки зрения, проце-
дура динамического программирования. В результате ее реализации находится
оптимальный искривленный путь, который определяет расстояние между масси-
вами X и .Y
Заметим, что хотя DTW задает меру схожести, в основе которой лежат ев-
клидово и фробениусово расстояния, с математической точки зрения это не будет
метрикой.
Для оценки расстояния между временными рядами разной длины можно ис-
пользовать метрику Левенштейна [26], рассчитать которую применительно к рас-
сматриваемой задаче можно с помощью соотношений
)).(),((1))1(),1((
,1))1(),((
,1))(),1((
min
,0),min(если),,(max
))(),((
lykxlykxd
lykxd
lykxd
lklk
lykxd
L
L
L
L
Здесь ))(),(( lykxdL — расстояние между первыми k наблюдениями ...),1({xX
)}(...,),(..., Nxkx и l наблюдениями )}(...,),(...,),1({ MylyyY исходных рядов
.случаепротивномв1
),()(если,0
))(),((
lykx
lykxd
При этом расстояние между рядами в целом задается соотношением
)).(),((),( MyNxdMND LL
Несложно заметить значительное сходство между расчетом DTW и расстоя-
нием Левенштейна, в основе которого лежит соотношение, аналогичное процеду-
ре динамического программирования. При этом ),( MND — только мера близо-
сти, а ),( MNDL — метрика в математическом смысле этого понятия.
Процедура иерархической кластеризации
многомерных временных рядов разной длины
На основании рассмотренных мер сходства может быть построена процедура
иерархической агломеративной кластеризации, в основу которой положен доста-
точно эффективный и простой, с вычислительной точки зрения, алгоритм Эверит-
та [7, 8]. Пусть имеется массив ,...,,...,,, 21 Qq xxxx образованный Q многомер-
ными последовательностями разной длины. Построим )( QQ -матрицу расстоя-
ний ),( pqL xxD между всеми рядами, образующими этот массив. Ясно, что эта
матрица симметрична с неотрицательными элементами и нулевыми диагональ-
ными элементами.
На первом этапе процедуры формируется 2/Q кластеров, если Q — четное,
или 2/)1( Q кластеров, если Q — нечетное, путем попарного объединения
ближайших один к другому рядов .,, pqxx pq Таким образом формируется мас-
сив кластеров первого уровня ,(...,,...,,,
]1[
2/)1(
]1[
2/
]1[]1[
2
]1[
1 QQj ClClClClCl в этом случае
кластер состоит из одной последовательности.
На втором этапе, на основании матрицы расстояний, оценивается расстояние
между всеми сформированными кластерами ,
]1[
jCl при этом в качестве этого рас-
стояния берется минимальное расстояние между наблюдениями из разных классов:
Международный научно-технический журнал
«Проблемы управления и информатики», 2019, № 2 83
).,(min),(
]1[
]1[
,
]1[]1[
pqL
Clx
Clx
rjL xxDClClD
rp
jq
Далее попарно объединяются ближайшие один к другому кластеры, в резуль-
тате формируется массив кластеров второго уровня .
]2[
jCl Процесс продолжается
до формирования набора кластеров m-го уровня ,
][m
jCl удовлетворяющего приня-
тым требованиям к качеству кластеризации.
Качество кластеризации в рассматриваемой задаче удобно оценивать с по-
мощью индекса Данна (Dunn index) [9], который полностью основан на исходной
матрице расстояний. При этом на каждом уровне оценивается диаметр сформиро-
ванных кластеров, в качестве которого берется максимальное расстояние между
рядами, входящими в этот кластер:
).,(maxDiam
][
][
,
][
pqL
Clx
Clx
m
j xxDCl
m
rp
m
jq
Индекс Данна в рассматриваемой задаче для m-го уровня кластеризации за-
пишем в форме
,
Diammax
),(
minmin)(Du
][
,...,1
][][
,...,1,...,1
][
][
][][
m
j
Qj
m
r
m
jL
QjrQj
m
Cl
ClClD
Q
m
mm
где
][mQ — количество сформированных кластеров на m-м уровне.
Чем больше значение индекса Данна, тем выше качество кластеризации. По-
нятно, что если на m-м уровне значение индекса прекращает увеличиваться, т.е.
),(Du)(Du ]1[][ mm QQ
процесс кластеризации может быть остановлен, а значение ][mQ полагается ис-
тинным числом кластеров в исходной выборке ....,,...,,, 21 Qq xxxx
Кластеризация временных рядов разной длины
в случае пересекающихся классов
В реальных задачах достаточно часто возникает ситуация, когда кластеры,
образованные наблюдениями (последовательностями), взаимно перекрывают
один другого. Эта ситуация является предметом рассмотрения нечеткого кластер-
ного анализа временных рядов [13]. При этом предполагалось, что ряды имеют
одинаковую длину. Заметим также, что известные методы нечеткого кластерного
анализа используют прототипы-центроиды — взвешенные средние наблюдений в
каждом из сформированных классов.
Задачу нечеткой кластеризации в принятых обозначениях сформулируем как
задачу минимизации целевой функции
Q
q
Q
j
m
jq
m
jq
m
jq
m
cxDcxcxE
1 1
][][][
][
),(),()),((
при ограничениях ,1),(
][
1
][
mQ
j
m
jq cx где 0),(
][
m
jq cx — уровень нечеткой
принадлежности последовательности qx к кластеру ,
][m
jCl центроидом которого
является ;
][m
jc 0 — параметр фаззификации обычно равный двум в задачах,
84 ISSN 0572-2691
использующих евклидову (сферическую) метрику; ),(
][m
jq cxD — расстояние
между qx и центроидом ][m
jc в той же метрике.
Понятно, что в рассматриваемой задаче говорить о прототипах-центроидах
не приходится, вместо них можно использовать так называемые представители-
образцы [15], являющиеся, по сути, одним из наблюдений, наиболее характерным
для конкретного кластера.
В качестве такого представителя ][m
jx для кластера ][m
jCl может быть взята
последовательность ,qx минимально удаленная от всех других рядов, входящих в
этот кластер, т.е.
),,(minarg
][
][
][ 1,
][][
pqL
Q
pq
Clx
Clx
m
jq
m
j xxDClxx
m
j
m
jp
m
jq
где ][m
jQ — число наблюдений в j-м кластере m-го уровня. Тогда уровень принад-
лежности наблюдения px к кластеру ][m
jCl можно рассчитать с помощью просто-
го соотношения:
.
),(
),(
)),(
][
1
][1
][1
][
mQ
S
m
SpL
m
jpLm
jp
xxD
xxD
xx
Понятно, что если в процессе иерархической кластеризации последователь-
ность px была отнесена к кластеру ,
][m
jCl то и значение ),(
][m
jp xx должно быть
максимальным среди всех ....,,2,1, ][][ mm
S QSx
Далее рассмотрим общий пошаговый алгоритм процесса иерархической аг-
ломеративной нечеткой кластеризации многомерных временных рядов нечеткой
длины:
1) задаем исходные ряды Qq xxxx ...,,...,,, 21 и рассчитываем )( QQ — мат-
рицу расстояний;
2) формируем массив кластеров первого уровня на основе попарного объеди-
нения исходных рядов;
3) формируем массив кластеров следующего уровня на основе попарного
объединения кластеров предыдущего уровня;
4) рассчитываем индекс Данна для оценки качества кластеризации;
5) если качество не удовлетворяет, переходим к шагу 3, иначе — к шагу 6;
6) рассчитываем представители-образцы для каждого кластера последнего
уровня;
7) рассчитываем уровни принадлежности каждого наблюдения qx к клас-
теру .
][m
jCl
В заключение отметим простоту вычислительной реализации предлагаемого
подхода, сводящегося к последовательности элементарных арифметических опе-
раций над анализируемыми временными рядами.
Экспериментальные результаты сегментации
видеопоследовательностей
Для анализа предложенного подхода к сегментации-кластеризации много-
мерных данных использовались видео из документального цикла фильмов канала
Discovery — «Destroyed in Seconds». Преимуществом подобных данных является,
Международный научно-технический журнал
«Проблемы управления и информатики», 2019, № 2 85
в первую очередь, то, что, с одной стороны, на относительно небольших видеопо-
следовательностях происходит неоднократное изменение сцены, что дает воз-
можность сегментировать исходные данные на однородные по своим характери-
стикам области/кластеры. С другой стороны, достаточно большая размерность
видео позволяет утверждать о работоспособности предложенного алгоритма при
работе с большими объемами исходных данных. Два примера видеопоследова-
тельностей и их пространственных сегментаций, необходимых для формирования
массива векторных наблюдений X и соответствующей им матрицы расстояний,
представлены на рис. 1.
Рис. 1
Пример сегментации-кластеризации видеопоследовательности, представлен-
ной на рис. 1, показан на рис. 2. Из результатов видно, что в общей сложности ви-
деопоследовательность разбивается на три сегмента. При этом особенно ярко вы-
ражен переход между первым и вторым сегментами в районе 288–290 кадров ви-
деопоследовательности.
Рис. 2
Учитывая специфику предложенного алгоритма сегментации/кластеризации,
следовало оценить адекватность использования индекса Данна в качестве крите-
рия останова процесса агломерации данных. Для этого эксперту было предложено
разделить каждую из десяти видеопоследовательностей на участки, обладающие,
по его мнению, схожими характеристиками. В таблице приведены результаты
сегментации согласно алгоритму и мнению эксперта.
Таблица
Кадр исходного видео Количество кластеров/сегментов
по предложенному алгоритму
Количество кластеров/сегментов
по мнению эксперта
5 4
5 5
0
0,05
0,15
0,25
0,1
0,2
1 51 101 151 201 251 301 351 401 451
86 ISSN 0572-2691
Продолжение таблицы
3 3
5 5
4 4
6 5
3 3
5 4
5 5
4 4
Из таблицы видно, что в семи случаях из десяти предложенный алгоритм и
эксперт дали аналогичный результат, что может свидетельствовать о возможности
использования индекса Данна в качестве критерия завершения процесса объеди-
нения данных в кластеры.
Заключение
Рассмотрена задача кластеризации многомерных временных рядов (вектор-
ных и матричных) различной длины в условиях неизвестного количества классов
и их взаимного пересечения. Предложен метод решения этой задачи на основе
гибридизации иерархического агломеративного и нечеткого, основанного на цен-
троидах, подходов с использованием метрики Левенштейна. Процесс кластериза-
ции сводится к последовательности элементарных операций над матрицей рассто-
яний между анализируемыми исходными последовательностями. Следует отме-
тить, что предложенный подход является развитием идей, описанных в [27–29], и
логическим продолжением цикла работ, посвященных кластеризации/сегмента-
ции многомерных данных (на примере видеопоследовательностей) с помощью
динамической временной деформации [22–25].
Развиваемый подход крайне прост с вычислительной точки зрения, позволяет
решать задачи кластеризации временных рядов произвольной природы как в
условиях неопределенности относительно количества классов данных, так и их
формы и уровня взаимного пересечения.
Международный научно-технический журнал
«Проблемы управления и информатики», 2019, № 2 87
С.В. Машталір, М.І. Столбовий, С.В. Яковлев
ГІБРИДНИЙ ПІДХІД ДО КЛАСТЕРИЗАЦІЇ
ВІДЕОРЯДІВ РІЗНОЇ ДОВЖИНИ
Істотне збільшення обсягу даних, що підлягають аналізу і обробці, вимагає запрова-
дження нових ефективних засобів і методів їх збору та зберігання. Особливо актуа-
льною така задача стає при аналізі мультимедійних, зокрема, відеоданих, в силу їх
значної надмірності. Один із шляхів зниження обсягу оброблюваної інформації —
кластеризація/сегментація відеопослідовностей для виділення однорідних за зміс-
том сегментів. При цьому виникає завдання вибору необхідної кількості кластерів
як вихідної інформації. Стаття присвячена розробці гібридного методу класте-
ризації для аналізу відеопослідовностей різної довжини. Метод зберігає переваги і
виключає недоліки агломеративної ієрархічної і нечіткої кластеризації. Для визна-
чення подібності між сегментами відеопослідовностей використовується метрика
Левенштейна, що дозволяє розраховувати відстані між багатовимірними послідов-
ностями різної довжини. Критерієм завершення процесу кластеризації в цілому, і,
відповідно, якість одержуваного результату визначається індексом Данна. Запро-
понований гібридний підхід до кластеризації відеопослідовностей відрізняється
обчислювальною простотою реалізації і дозволяє вирішувати завдання аналізу
багатовимірних часових рядів довільної природи в тому випадку, коли заздале-
гідь складно визначити необхідну кількість кластерів для розбиття і в умовах
невизначеності щодо можливого їх перекриття, тобто в разі, коли результатом
кластеризації є побудова покриття, а не розбиття даних.
Ключові слова: ієрархічна кластеризація, нечітка кластеризація, багатовимірні
послідовності, відео, метрика.
S.V. Mashtalir, M.I. Stolbovoi, S.V. Yakovlev
HYBRID APPROACH TO CLUSTERING DIFFERENT
LENGTH VIDEOS
A significant increase in the amount of data to be analyzed and processed requires the
introduction of new efficient tools and methods for their collection and storage. This
task is especially important when analyzing multimedia, in particular, video data, due
to their great redundancy. One of the ways to reduce the amount of information pro-
cessed is clustering / segmentation of video sequences to isolate parts that are homo-
geneous in content. This raises the problem of choosing the required number of clus-
ters as source information. The article is devoted to the development of a hybrid clus-
tering method for analyzing video sequences of various lengths. The method saves
the advantages and eliminates the disadvantages of agglomerative hierarchical and
fuzzy clusterings. To determine the similarity between segments of video sequences,
the Levenshtein metric is used, which allows to calculate the distances between mul-
tidimensional sequences of different lengths. The criterion for the clustering process
completion as a whole, and, accordingly, the result quality is determined by the Dunn
index. The proposed hybrid approach to clustering video sequences is computationally
simple to implement and allows solving the multidimensional time series analysis prob-
lems of arbitrary nature in the case when it is difficult to determine in advance the neces-
sary number of clusters for splitting and under conditions of uncertainty about their possi-
ble overlap, i.e. in the case where the clustering result is the cover construction, and not da-
ta partitioning (exact cover construction).
Keywords: hierarchical clustering, fuzzy clustering, multidimensional sequences,
video, metric.
1. Basharat A., Zhai Y., Shah M. Content based video matching using spatiotemporal volumes. Computer
Vision and Image Understanding. 2008. 110. Р. 360–377. Doi.org/10.1016/j.cviu.2007.09.016.
2. Patel B.V., Meshram B.B. Content based video retrieval. The International Journal of Multimedia
& Its Applications (IJMA). 2012. 4, N 5. Р. 77–98. Doi.org/10,5121/iju.2012.3202.
3. Mashtalir S., Mikhnova O. Detecting significant changes in image sequences. Multimedia Foren-
sics and Security. Springer, Cham. 2017. Р. 161–191. Doi.org/10,5121/iju.2012.3202.
4. Petersohn C. Temporal video segmentation. Jorg Vogt Verlag. 2010. 273 p.
https://doi.org/10.1016/j.cviu.2007.09.016
https://arxiv.org/ct?url=https%3A%2F%2Fdx.doi.org%2F10.5121%252Fiju.2012.3202&v=92066e73
https://arxiv.org/ct?url=https%3A%2F%2Fdx.doi.org%2F10.5121%252Fiju.2012.3202&v=92066e73
88 ISSN 0572-2691
5. Dhiman P., Dhanda M. Video segmentation using FCM algorithm. International Journal of
Engineering Trends and Technology (IJETT). 2016. 36, N 2. Р. 106–110. Doi.org/10,14445/
22315381/IJETT-V36P220.
6. Kobylin O., Mashtalir S., Stolbovyi M. Video clustering via multidimensional time-series analy-
sis. Proceedings of the 9th International Conference on Information Management and Engineer-
ing. 2017. Spain, Barcelona. P. 60–63. Doi.org/10.1145 / 3149572.3149599.
7. Kaufman L., Rousseeuw P.J. Finding groups in data: An introduction to cluster analysis. Wiley, 2009.
8. Everitt B., Landau S., Leese M. Cluster analysis. Wiley. 2011. 321 p.
9. Dunn J.C. A Fuzzy relative of the ISODATA process and its use in detecting compact Well-
Separated clusters. Journal of Cybernetics and Systems Analysis. 1973. 3, N 3. P. 32–57.
Doi.org/10.1080/01969727308546046.
10. Hulianytskyi L., Malyshko S. Big data in information analytical system «NEWSCAPE». Data
Stream Mining &. Processing. Proc. IEEE First Int. Conf. on Data Stream Mining & Processing
(23-27 August 2016, Lviv, Ukraine). 2016. Р. 382–386. Doi.org/10.15407 / usim.2017.05.086.
11. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization prob-
lems. Springer Optimization Methods and its Applications. 2017. 130. Р. 239–250. Doi.org/10.
1007/978-3-319-68640-0_11.
12. Hulianytskyi L., Riasna I. Automatic classification method based on a fuzzy similarity relation.
Cybernetics and Systems Analysis. 2016. 52, N 1. Р. 30–37. Doi.org/10.1007/s10559-016-9796-3.
13. Abonyi J., Feil B. Cluster analysis for data mining and system identification. Basel : Birkhä user. 2007.
14. Liao T.W. Clustering of time series data. Pattern recognition. 2005. 38, N 11. Р. 1857–1874.
Doi.org/10.1016/j.patcog.2005.01.025.
15. Aggarwal C.C., Reddy C.K. Data clustering: algorithms and applications. Boca Raton : CRC
Press, 2014.
16. Богучарский С.И., Каграманян А.Г., Машталир С.В. Иерархическая агломеративная кла-
стеризация изображений в больших базах данных. Системи обробки інформації. 2014.
№ 8. С. 93–97.
17. Berndt D.J., Clifford S. Using dynamic time warping to find patterns in time series. Proc. of the 3rd In-
ternational Conference on Knowledge Discovery and Data Mining (AAAIWS'94). 1994. Р. 359–370.
18. Keogh E.J., Pazzani M.J. Scaling up dynamic time warping to massive datasets. European Con-
ference on Principles of Data Mining and Knowledge Discovery. 1999. Р. 1–11. Doi.org/10.
1007/978-3-540-48247-5_1.
19. Chu S., Keogh E., Hart D., Pazzani M. Iterative deepening dynamic time warping for time series.
Proc. 2nd SIAM International Conference on Data Mining (SDM-02). 2002. Doi.org/10.1137/
1.9781611972726.12.
20. Keogh E.J., Pazzani M.J. Scaling up dynamic time warping for data mining applications. Proc. of
the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
2000. Р. 285–289. Doi.org/10.1.1.11.5441.
21. Keogh E.J., Pazzani M.J. Derivative dynamic time warping. Proc. of the First SIAM International
Conference on Data Mining (SDM'2001), 2001. https://www.researchgate.net/publication/
319770645.
22. Mashtalir S.V., Stolbovyi M.I., Yakovlev S.V. Video sequences clustering by the k-harmonic means.
Cybernetics and Systems Analysis. 2019. 55, N 1. Р. 295–307. Doi.org/10.1007/s10559-019-00124-9.
23. Mashtalir S., Mashtalir V., Stolbovyi M. Video shot boundary detection via sequential clustering.
International Journal of Information Theories and Applications. 2017. 24, N 1. P. 50–59.
Doi.org/10.5815/ijisa.2017.11.02.
24. Hu Z., Mashtalir S.V., Tyshchenko O.K., Stolbovyi M.I. Clustering matrix sequences based on
the iterative dynamic time deformation procedure. International Journal of Intelligent Systems
and Applications. 2018. 10, N 7. P. 66–73. Doi.org/10.5815/ijisa.2018.07.07.
25. Hu Z., Mashtalir S.V., Tyshchenko O.K., Stolbovyi M.I. Video shots’ matching via various
length of multidimensional time sequences. International Journal of Intelligent Systems and Ap-
plications. 2018. 9, N 11. P. 10–16. Doi.org/10.5815/ijisa.2017.11.02.
26. Levenshtein V. Binary codes capable of correcting deletions, insertions and reversals. Dokl. Akad.
Nauk SSSR. 1965. 163, N 4. P. 845–848.
27. Mashtalir V.P., Yakovlev S.V. Point-set methods of clusterization of standard information. Cy-
bernetics and Systems Analysis . 2001. 37, N 3. Р. 295–307. Doi.org/10.1023/A:
1011985908177.
28. Gerasin S.N., Shlyakhov V.V., Yakovlev S.V. Set coverings and tolerance relations. Cy-
bernetics and Systems Analysis. 2008. 43, N 3. P. 333–340. Doi.org/10.1007/s10559-008-
9007-y.
29. Mashtalir V.P., Shlyakhov V.V., Yakovlev S.V. Group structures on quotient sets in classification
problems. Cybernetics and Systems Analysis. 2014. 50, N 4. P. 507–518. Doi.org/10.1007/
s10559-014-9639-z.
Получено 10.10.2018
https://doi.org/10.14445/22315381/IJETT-V36P220
https://doi.org/10.14445/22315381/IJETT-V36P220
https://dl.acm.org/citation.cfm?id=3149599
https://dl.acm.org/citation.cfm?id=3149599
https://doi.org/10.1145/3149572.3149599
http://books.google.com/books?hl=en&lr=&id=YeFQHiikNo0C&oi=fnd&pg=PR11&dq=info:0XirZwaVHE0J:scholar.google.com&ots=5Aqhy0KDvH&sig=TPTzUCIqC8hY4S9wcA4LMzdrd-A
https://link.springer.com/journal/10559
https://link.springer.com/book/10.1007/978-3-319-68640-0
https://link.springer.com/journal/10559
http://www.irbis-nbuv.gov.ua/cgi-bin/irbis_nbuv/cgiirbis_64.exe?C21COM=2&I21DBN=UJRN&P21DBN=UJRN&IMAGE_FILE_DOWNLOAD=1&Image_file_name=PDF/soi_2014_8_22.pdf
http://www.irbis-nbuv.gov.ua/cgi-bin/irbis_nbuv/cgiirbis_64.exe?C21COM=2&I21DBN=UJRN&P21DBN=UJRN&IMAGE_FILE_DOWNLOAD=1&Image_file_name=PDF/soi_2014_8_22.pdf
javascript:void(0)
https://www.researchgate.net/publication/319770645
https://www.researchgate.net/publication/319770645
http://www.scopus.com/source/sourceInfo.url?sourceId=12933&origin=resultslist
https://www.researchgate.net/profile/Oleksii_Tyshchenko/publication/326346039_Clustering_matrix_sequences_based_on_the_iterative_dynamic_time_deformation_procedure/links/5b4a7b1045851519b4bc7ddb/Clustering-matrix-sequences-based-on-the-iterative-dynamic-time-deformation-procedure.pdf
https://www.researchgate.net/profile/Oleksii_Tyshchenko/publication/326346039_Clustering_matrix_sequences_based_on_the_iterative_dynamic_time_deformation_procedure/links/5b4a7b1045851519b4bc7ddb/Clustering-matrix-sequences-based-on-the-iterative-dynamic-time-deformation-procedure.pdf
http://www.mecs-press.org/ijisa/ijisa-v9-n11/IJISA-V9-N11-2.pdf
http://www.mecs-press.org/ijisa/ijisa-v9-n11/IJISA-V9-N11-2.pdf
http://www.scopus.com/authid/detail.url?origin=resultslist&authorId=6507672782&zone=
http://www.scopus.com/authid/detail.url?origin=resultslist&authorId=7006718461&zone=
http://www.scopus.com/record/display.url?eid=2-s2.0-26944469458&origin=resultslist&sort=plf-f&src=s&st1=mashtalir%2cv&sid=D3BE1EA80464B4BE842EFCF27783F190.fM4vPBipdL1BpirDq5Cw%3a140&sot=b&sdt=b&sl=24&s=AUTHOR-NAME%28mashtalir%2cv%29&relpos=9&relpos=9&citeCnt=1&searchTerm=AUTHOR-NAME%28mashtalir%2Cv%29
http://www.scopus.com/source/sourceInfo.url?sourceId=12933&origin=resultslist
http://www.scopus.com/source/sourceInfo.url?sourceId=12933&origin=resultslist
|
| id | nasplib_isofts_kiev_ua-123456789-180784 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T15:31:16Z |
| publishDate | 2019 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Машталир, С.В. Столбовой, М.И. Яковлев, С.В. 2021-10-18T19:06:49Z 2021-10-18T19:06:49Z 2019 Гибридный подход к кластеризации видеорядов различной длины / С.В. Машталир, М.И. Столбовой, С.В. Яковлев // Проблемы управления и информатики. — 2019. — № 2. — С. 80-88. — Бібліогр.: 29 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/180784 004.93 Рассмотрена задача кластеризации многомерных временных рядов (векторных и матричных) различной длины в условиях неизвестного количества классов и их взаимного пересечения. Предложен метод решения этой задачи на основе гибридизации иерархического агломеративного и нечеткого, основанного на центроидах, подходов с использованием метрики Левенштейна. Процесс кластеризации сводится к последовательности элементарных операций над матрицей расстояний между анализируемыми исходными последовательностями. Развиваемый подход крайне прост с вычислительной точки зрения, позволяет решать задачи кластеризации временных рядов произвольной природы как в условиях неопределенности относительно количества классов данных, так и их формы и уровня взаимного пересечения. Істотне збільшення обсягу даних, що підлягають аналізу і обробці, вимагає запровадження нових ефективних засобів і методів їх збору та зберігання. Особливо актуальною така задача стає при аналізі мультимедійних, зокрема, відеоданих, в силу їх значної надмірності. Один із шляхів зниження обсягу оброблюваної інформації — кластеризація/сегментація відеопослідовностей для виділення однорідних за змістом сегментів. При цьому виникає завдання вибору необхідної кількості кластерів як вихідної інформації. Стаття присвячена розробці гібридного методу кластеризації для аналізу відеопослідовностей різної довжини. Метод зберігає переваги і виключає недоліки агломеративної ієрархічної і нечіткої кластеризації. Для визначення подібності між сегментами відеопослідовностей використовується метрика Левенштейна, що дозволяє розраховувати відстані між багатовимірними послідовностями різної довжини. Критерієм завершення процесу кластеризації в цілому, і, відповідно, якість одержуваного результату визначається індексом Данна. Запропонований гібридний підхід до кластеризації відеопослідовностей відрізняється обчислювальною простотою реалізації і дозволяє вирішувати завдання аналізу багатовимірних часових рядів довільної природи в тому випадку, коли заздалегідь складно визначити необхідну кількість кластерів для розбиття і в умовах невизначеності щодо можливого їх перекриття, тобто в разі, коли результатом кластеризації є побудова покриття, а не розбиття даних. A significant increase in the amount of data to be analyzed and processed requires the introduction of new efficient tools and methods for their collection and storage. This task is especially important when analyzing multimedia, in particular, video data, due to their great redundancy. One of the ways to reduce the amount of information processed is clustering / segmentation of video sequences to isolate parts that are homogeneous in content. This raises the problem of choosing the required number of clusters as source information. The article is devoted to the development of a hybrid clustering method for analyzing video sequences of various lengths. The method saves the advantages and eliminates the disadvantages of agglomerative hierarchical and fuzzy clusterings. To determine the similarity between segments of video sequences, the Levenshtein metric is used, which allows to calculate the distances between multidimensional sequences of different lengths. The criterion for the clustering process completion as a whole, and, accordingly, the result quality is determined by the Dunn index. The proposed hybrid approach to clustering video sequences is computationally simple to implement and allows solving the multidimensional time series analysis problems of arbitrary nature in the case when it is difficult to determine in advance the necessary number of clusters for splitting and under conditions of uncertainty about their possible overlap, i.e. in the case where the clustering result is the cover construction, and not data partitioning (exact cover construction). ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации Гибридный подход к кластеризации видеорядов различной длины Гібридний підхід до кластеризації відеорядів різної довжини Hybrid approach to clustering different length vide Article published earlier |
| spellingShingle | Гибридный подход к кластеризации видеорядов различной длины Машталир, С.В. Столбовой, М.И. Яковлев, С.В. Методы обработки информации |
| title | Гибридный подход к кластеризации видеорядов различной длины |
| title_alt | Гібридний підхід до кластеризації відеорядів різної довжини Hybrid approach to clustering different length vide |
| title_full | Гибридный подход к кластеризации видеорядов различной длины |
| title_fullStr | Гибридный подход к кластеризации видеорядов различной длины |
| title_full_unstemmed | Гибридный подход к кластеризации видеорядов различной длины |
| title_short | Гибридный подход к кластеризации видеорядов различной длины |
| title_sort | гибридный подход к кластеризации видеорядов различной длины |
| topic | Методы обработки информации |
| topic_facet | Методы обработки информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/180784 |
| work_keys_str_mv | AT maštalirsv gibridnyipodhodkklasterizaciivideorâdovrazličnoidliny AT stolbovoimi gibridnyipodhodkklasterizaciivideorâdovrazličnoidliny AT âkovlevsv gibridnyipodhodkklasterizaciivideorâdovrazličnoidliny AT maštalirsv gíbridniipídhíddoklasterizacíívídeorâdívríznoídovžini AT stolbovoimi gíbridniipídhíddoklasterizacíívídeorâdívríznoídovžini AT âkovlevsv gíbridniipídhíddoklasterizacíívídeorâdívríznoídovžini AT maštalirsv hybridapproachtoclusteringdifferentlengthvide AT stolbovoimi hybridapproachtoclusteringdifferentlengthvide AT âkovlevsv hybridapproachtoclusteringdifferentlengthvide |