ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
15
Пусть минимальная поддержка min_sup
будет действительным чис-
лом из диапазона значений (0; 1]. Тогда шаблон
P
называется
частым
шаблоном
,
если его поддержка
|P|
больше минимальной
m
min_sup.
Каждая область
i
r
в шаблоне
P
является
правильной
,
если мно-
жество положений
{
|
}
j
P
j
P
i
i
R s s S
=
∈
формирует
плотный кластер
[4].
Шаблон
P
называется правильным, если все его не небесконеч-
ные регионы правильны.
Задача поиска периодически повторяющихся шаблонов зак-
лючается в поиске всех правильных периодических шаблонов
P
в
последовательности
S
,
которые являются частыми и неизбыточными
по отношению к минимальной поддержке min_sup
.
В качестве общего метода решения этой задачи предложено ис-
пользовать:
1)
дискретизацию точек в пространственно-временной системе
координат с заданным интервалом времени. Таким образом, для
каждой точки имеем последовательность координат;
2)
разделение последовательности движения каждого объекта на
множество последовательностей с длиной, равной периоду, для
которого находятся шаблоны;
3)
кластеризация точек в пространстве для выделения значимых
регионов и нивелирования колебаний при определении координат;
4)
поиск периодически повторяющихся последовательностей и
их валидация, если это необходимо;
5)
визуализация результата.
Рассмотрим нахождение частых шаблонов единичной длины, за-
тем — существующих алгоритмов поиска периодических шаблонов,
в которых в качестве параметра принимается набор частых шаблонов
единичной длины.
Для поиска шаблонов единичной длины можно применять сле-
дующую методологию. Последовательность
S
разбивается на
T
про-
странственных наборов данных, по одному на каждый отступ в пери-
од
T
(
часть
а
рисунка). Другими словами, положения
{ ,
, ...,
i i T
l l
+
( 1)
}
i m T
l
+ −
образуют множество
i
R
(
часть
б
рисунка) для каждого
0 .
i T
≤ <
Каждому положению присваивается идентификатор
[0;
1]
j
m
∈ −
сегмента, содержащего его.
Следует отметить, что плотный кластер
r
в наборе данных
i
R
(
часть
б
рисунка) соответствует частому шаблону, у которого на
i
-
м
месте
r
,
а на остальных символ «
*
».
Чтобы определить плотные клас-
теры, необходимо использовать алгоритм кластеризации по плот-
ности, например DBSCAN [5]. Кластеры с числом точек меньшим
(
min sup)
m _
α α
=
отбрасываются как нечастые. Оригинальный алго-
ритм DBSCAN имеет квадратичную вычислительную стоимость отно-
сительно числа точек для кластеризации, поэтому алгоритм, основан-
ный на хешировании, используется для уменьшения стоимости [6].