18
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
1)
построить дерево максимальных подшаблонов
Tr
и файл шаблонов
F
2)
отсортировать
F
по
P`.id
и соединить с узлами
Tr
3)
для каждого
k:=T
уменьшая до 2
4)
для каждого шаблона
P`
на уровне
k
дерева
Tr
,
5)
`,длина( ``)
1
| `|:
`.счетчик
| ``|
P`` P
P k
P P
P
⊃
= +
=
+ ∑
6)
если
|
`|
min_ sup
P m
≥
то
7)
`` `
:
``.идентификаторы
cand
P P
Ρ
P
⊇
= ∪
8)
проверить_шаблон
(
, ,
min_ sup)
cand
P L
9)
если
Ρ
изменился, то
10)
удалить из
P
` все идентификаторы,
11)
входящие в новые шаблоны
Ρ
12)
если нераспределенных идентификаторов <m min_sup то
13)
вернуть
Ρ
14)
вернуть
Ρ
Существует алгоритм STPMine 2-V2, который аналогичен алгорит-
му STPMine 2, за исключением отсутствия в данном алгоритме провер-
ки шаблонов и переиндексации сегментов (строки 8—12). Вследствие
этого алгоритм менее точен и может содержать неверные шаблоны,
регионы шаблонов совпадают с регионами частых одношаблонов, по-
лученных на первом шаге. Однако алгоритм STPMine 2-V2 работает
значительно быстрее описанных выше двух алгоритмов.
Результаты сравнения существующих алгоритмов.
Един-
ственным алгоритмом, который находит все шаблоны, является
STPMine 1, но он обладает очень низкой скоростью работы и высо-
кой ресурсоемкостью. Алгоритм STPMine 2 более быстрый алгоритм,
однако он определяет только максимальные шаблоны, тем самым
менее частые, но не менее полезные знания (шаблоны) могут быть
пропущены. Алгоритм STPMine 2-V2 применим там, где важна ско-
рость работы, чем качество полученных результатов. Для описанной
задачи ни один из данных алгоритмов не подходит. Кроме того, рас-
смотренные алгоритмы не устойчивы к сдвигам и неточностям во
времени. Например, в следующей последовательности этот же шаб-
лон может повторяться с небольшим сдвигом по времени как для
всего шаблона, так и отдельные его регионы. Такие шаблоны не смо-
гут быть найдены. Необходимо проводить доработку модели поиска
периодических шаблонов и разрабатывать новый метод, использова-
ние которого позволит соответствовать требованиям по производи-
тельности и качеству поиска.
Заключение.
В статье были рассмотрены проблема выявления
наиболее часто используемых маршрутов с заданной периодично-
стью, а также существующие программные комплексы. Описана
модель периодически повторяющихся шаблонов в пространственно-
временных данных, предложено общее решение и сформирована
задача нахождения частых периодически повторяющихся шаблонов.
Проанализированы существующие алгоритмы, выявлены их недо-
статки и обоснована необходимость разработки нового решения.