14
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
Пробки, Google, Rambler и др. В системе Яндекс.Пробки накапливаются
статистические данные о загруженности конкретных участков дорог,
затем эти данные используются при планировании маршрутов. Однако
ни в этой системе, ни в аналогичных системах не анализируются сами
маршруты, вызывающие подобные затруднения. Такие знания необхо-
димо получать с применением более сложных методов анализа [3]. Для
этого требуется выработать методы решения и алгоритмы, а также реа-
лизовать на их основе программный комплекс для установления зако-
номерностей движения объектов на базе данных положений этих объек-
тов. Под закономерностями понимается часто повторяющиеся пере-
движения объекта с определенной периодичностью, так называемые
периодические шаблоны. Периодический шаблон представляют как не
непрерывные последовательности положений объекта, которые перио-
дически появляются в истории движения, так как не предполагается,
что объект посещает точно те же места в то же время в рамках периода.
Таким образом, шаблоны несколько размытые. Сформулированную за-
дачу можно отнести к задаче поиска последовательных шаблонов.
Модель периодического шаблона.
Траекторией объекта
S
назы-
вают последовательность длиной
n
пространственно-временных ко-
ординат:
0 0 1 1
1 1
{( ; ), ( ; ), ..., ( ;
)},
| |,
n n
S l t
l t
l
t
n S
− −
=
=
(1)
где
l
i
—
положение объекта в момент времени
t
i
,
выраженное в про-
странственных координатах.
Если разность временных меток одинакова, то последователь-
ность (1) представляют как
0 1
1
{ , , ...,
}.
n
S l l
l
−
=
Пусть
0 1
1
{ , , ...,
}
n
S l l
l
−
=
—
движение объекта;
T
—
период
(
например, день, неделя, месяц),
T n
.
Периодический сегмент
s
определяется подпоследовательностью
1
1
,
, ...,
i i
i T
l l
l
+
+ −
из последова-
тельности
S
,
причем остаток от деления
i
на
T
равен нулю. Таким об-
разом, сегменты начинаются в позициях 0,
T
,
(
)
1
n T T
− ⎢ ⎥ ⎣ ⎦
и имеется
m n T
= ⎢ ⎥ ⎣ ⎦
периодических сегментов в последовательности
S
(
если
n
не кратно
T
,
то все последние
n
mod
T
положений отбрасываются, и
длина
n
последовательности
S
уменьшается). Пусть
j
s
—
сегмент,
начиная с положения
для , 0
,
jT
l
S j m
≤ <
и
для
j
jT i
i
s l
+
=
, 0
.
i
i T
≤ <
Периодический шаблон
P
—
последовательность вида
0 1
1
, ,...,
T
r r r
−
длиной
T
,
i
r
—
пространственная область или вся про-
странственная вселенная. Длина шаблона
P
равна числу небесконеч-
ных регионов.
Сегмент
j
s
удовлетворяет шаблону
P
,
если для всех
,
*
i
i
r P r
∈ =
или
j
i
s
находится в пространственной области
i
r
.
Поддержкой
|P|
шаблона
P
называется число периодических сег-
ментов
s
из последовательности
S
,
удовлетворяющих данному шаблону.