16
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
а
б
Траектория, разбитая на сегменты и регионы:
a
—
декомпозиция по периоду;
б
—
плотные кластеры среди множества
R
i
,
i =
1, …, 6;
1
,
2
,
3
—
первый, второй и третий дни соответственно
Рассмотрим поуровневый подход «снизу вверх», предложенный в
алгоритме STPMine 1. Начиная с шаблонов единичной длины, в та-
ком подходе применяется вариация алгоритма априори (apriori —
TID) для нахождения более длинных последовательностей. Входны-
ми данными для алгоритма является набор частых однопоследова-
тельностей [7, 8]. Пары
<
1
P
,
2
P
>
шаблонов длиной
k
− 1 из
1
k
L
−
с их
первыми
k
− 2 небесконечными областями, находящимися в одина-
ковых позициях, и разными не небесконечными
k
− 1 позициями об-
разуют кандидат в шаблон длиной
k
(
строки 4—6). Для каждого кан-
дидата
cand
P
осуществляется соединение множеств по идентифика-
тору сегмента между
1
P
и
2
P
.
Если число сегментов, удовлетворяю-
щих обоим шаблонам, равно минимальной поддержке, происходит
проверка, являются ли регионы шаблона
cand
P
по-прежнему класте-
рами. После того, как все шаблоны длиной
k
найдены, определяются
шаблоны следующего уровня до тех пор, пока еще есть шаблоны на
данном уровне, и еще есть уровни.
Псевдокод алгоритма выглядит следующим образом:
1)
k
:
=2
2)
пока
(
1
0
k
L
k T
−
≠ ∧ <
)
3)
: 0;
k
L
=
4)
для каждой пары
1 2
1
( , )
k
P P L
−
∈
5)
такой, что
1 2
,
P P
совпадают по первым
k
– 2