В случае, если длины
S
1
и
S
2
не равны, выбираем между урезанием
длинной последовательности (вычисление минимума евклидовыхмер
среди возможныхподпоследовательностей длинной последовательно-
сти с короткой последовательностью) и добавлением нулей к короткой
последовательности. Зачастую ни один из этихвариантов не является
приемлемым. Наша метрика должна быть приспособлена для срав-
нения последовательностей вне зависимости от ихдлины, опираясь
лишь на похожести их элементов.
Значительные различия в сравниваемыхпоследовательностях, воз-
никающие на небольшихучастках, могут быть вызваны самыми раз-
ными причинами, например ошибкой сенсоров или ошибкой человека,
вводящего данные. Использование евклидовой метрики в этом случае
даст значительное расхождение. Искомая метрика должна уметь про-
пускать такие всплески (промахи) и давать небольшую разницу после-
довательностей, при условии, что в преобладающем множестве точек
последовательности совпадают.
Функция вычисления критерия должна быть одновременно доста-
точно выразительна (т.е. степень различия значений меры должна со-
ответствовать степени различий последовательностей) и в то же время
проста в вычислении, чтобы ее реализация не требовала значительных
вычислительныхресурсов.
Такие метрики, как Dynamic Time Warping (DTW) [6], Longest
Common Subsequence (LCSS) [2], подразумевают, что при сравне-
нии двухпоследовательностей каждая из нихявляется полноценным
экземпляром, который можно рассматривать как нечто целое. В нашем
случае необходимо добиться возможности работы с фрагментарными
последовательностями – сравнивать части с целым и получать адекват-
ные оценки похожести рассматриваемых траекторий. Такое свойство
метрики позволит извлекать сохраненные элементы, пользуясь лишь
частично определенными запросами.
Применяемые на сегодняшний день метрики не удовлетворяют
всем поставленным условиям. Например, евклидова метрика оказы-
вается непригодной для сравнения последовательностей, полученных
при различныхчастотахдискретизации. Функция расстояния, осно-
ванная на методе DTW, позволяет сопоставить две последовательно-
сти разной длины, но она излишне чувствительно к шумам. Функ-
ция расстояния, по которой вычисляют наибольшую общую последо-
вательность, наиболее устойчива к шумам и различным аберрациям
запроса, но не позволяет сравнивать фрагмент с целым, размеры ко-
торого значительно больше размеров фрагмента.
Рассмотрим алгоритм вычисления меры близости двухпоследо-
вательностей: последовательности-запроса
Q
и некоторой известной
последовательности
S
. Для этого введем ряд определений.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2007. № 2 107
