1. По последовательности
{
S
i
}
строим
{
R
i
}
;
2. Для каждого элемента
Q
i
∈ {
Q
i
}
проверяем:
a) принадлежит ли
Q
i
какому-либо
R
i
∈ {
R
i
}
, если принадлежит, то
запоминаем индексы этихрегионов (индексы текущего шага); eсли
принадлежность найдена, то увеличиваем значение меры близости на
величину WeightHit;
б) cравниваем индексы текущего шага с индексами прошлого шага.
Если оказывается, что индексы текущего следуют за индексами про-
шлого, то меру близости увеличиваем на величину WeightFollow.
В нашихчисленныхсравненияхзначения величин WeightHit и
WeightFollow выбираются равными 2 и 1 соответственно.
Описанный способ сравнения пространственно-временныхпо-
следовательностей удовлетворяет выдвинутым требованиям. Дей-
ствительно, ни разница частот дискретизации, ни разница в длинах
последовательностей не влияют на сравнение запроса с последова-
тельностью МОП, поскольку критическим для получения высокой
оценки является похожесть очертаний форм, а не длина или число
точек в исходной последовательности. Всплески, в отличие от евкли-
довой метрики и метрики DTW, не вносят значительныхизменений
в полученные веса, поскольку точки, выпавшие за пределы последо-
вательностей МОП, просто не учитываются. В случае, когда запрос
является незначительным фрагментом последовательности, предло-
женная процедура оказывается применимой, поскольку для вычисле-
ния веса не имеет значения время начала и время окончания последо-
вательности — важно лишь совпадение пространственныхкоординат
и повторение последовательности попадания точек в коридор, опре-
деляемой
n
-параллелепипедами. Если использовать предложенный
ранее алгоритм, то эффективность данной функции можно оценить
как
O
m
1
·
m
2
λ
, где
m
1
— длина
{
S
i
}
,
m
2
— длина
{
Q
i
}
, а
λ
—
диаметр разбиения
{
S
i
}
. Такая оценка справедлива при условии, что
операции проверки принадлежности региону и проверки следования
индексов регионов выполняются за время
O
(1)
. Далее покажем, что
такую оценку эффективности можно улучшить.
Численное сравнение выразительности критериев близости
последовательностей.
Оценим численно, насколько предложенная
функция близости выразительна для различныхпоследовательностей.
Такую оценку мы проведем согласно методике, предложенной Кео и
Касетти в работе [7], которая сводится к следующему. Пусть имеет-
ся множество
D
последовательностей
{
S
i
}
, для каждой из которых
явно задана принадлежность некоторому классу
C
j
. Каждому классу
принадлежит более одной последовательности. Тогда из множества
D
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2007. № 2 109
