Альтернативы методу динамического деформирования времени (DTW)

Question

Я изучаю методы сравнения данных временных рядов. Одним из найденных алгоритмов, используемых для сопоставления данных этого типа, является алгоритм DTW (динамическое изменение времени).

Данные у меня есть, напоминают следующую структуру (это может быть один путь):

Path Event  Time   Location (x,y) 
    1  1  2:30:02    1,5 
    1  2  2:30:04    2,7 
    1  3  2:30:06    4,4 
... 
... 

Теперь, мне было интересно, есть ли другие алгоритмы, которые будут пригодны, чтобы найти ближайший матч за данный дорожка.

Answer 1

Если два пути имеют одинаковую длину, скажем, п, то они на самом деле указывает в 2n-мерном пространстве. Первое местоположение определяет первые два измерения, второе местоположение определяет следующие два измерения и так далее. Например, если мы просто возьмем три точки в вашем примере, путь может быть представлен как единственная 6-мерная точка (1, 5, 2, 7, 4, 4). Если мы хотим сравнить это с другим трехточечным путем, мы можем вычислить либо евклидову дистанцию ​​(квадратный корень из суммы квадратов расстояний между измерениями между двумя точками), либо расстояние Манхэттена (сумма разностей по размерности).

Например, пусковой путь, который остается на (0, 0) для всех трех времен, становится 6-мерной точкой (0, 0, 0, 0, 0, 0). Тогда евклидово расстояние между этой точкой и вашим примером будет sqrt((1-0)^2 + (5-0)^2 + (2-0)^2 + (7-0)^2 + (4-0)^2 + (4-0)^2) = sqrt(111) = 10.54. Расстояние Манхэттена - abs(1-0) + abs(5-0) + abs(2-0) + abs(7-0) + abs(4-0) + abs(4-0) = 23. Такая разница между метриками не является чем-то необычным, поскольку расстояние Манхэттена доказуемо не менее велико, чем евклидово расстояние.

Конечно, одна из проблем с этим подходом заключается в том, что не все пути будут иметь одинаковую длину. Тем не менее, вы можете легко отрезать длинный путь до той же длины, что и более короткий путь, или считать, что более короткие из двух путей остаются в одном и том же месте или перемещаются в одном направлении после завершения измерений, пока оба пути не будут иметь одинаковую длину , Любой подход приведет к некоторым неточностям, но независимо от того, что вы делаете, вам приходится иметь дело с тем фактом, что вам не хватает данных на коротком пути и что-то нужно компенсировать.

EDIT:

Предполагая, что path1 и path2 являются List<Tuple<int, int>> объекты, содержащие точки, мы можем отсечь длинный список, чтобы соответствовать более короткий список, как:

// Enumerable.Zip stops when it finishes one of the sequences 
List<Tuple<int, int, int, int>> matchingPoints = Enumerable.Zip(path1, path2, 
    (tupl1, tupl2) => 
     Tuple.Create(tupl1.Item1, tupl1.Item2, tupl2.Item1, tupl2.Item2)); 

Затем, вы можете используйте следующий код, чтобы найти Манхэттенское расстояние:

int manhattanDistance = matchingPoints 
    .Sum(tupl => Math.Abs(tupl.Item1 - tupl.Item3) 
       + Math.Abs(tupl.Item2 - tupl.Item4)); 

При тех же предположениях, что и для Манхэттенского расстояния, мы можем генерировать евклидово расстояние, как:

int euclideanDistanceSquared = matchingPoints 
    .Sum(tupl => Math.Pow(tupl.Item1 - tupl.Item3, 2) 
       + Math.Pow(tupl.Item2 - tupl.Item4, 2)); 
double euclideanDistance = Math.Sqrt(euclideanDistanceSquared); 

Answer 2

Там другой вопрос here, которые могли бы иметь некоторую помощь. Если у вас уже есть заданный путь, вы можете найти ближайшую совпадение, используя алгоритм межсетевого расстояния; с другой стороны, если вы действительно хотите решить проблему распознавания образов, вам может понадобиться узнать больше о расстоянии Левенштейна и Elastic Matching (из Википедии: «Эластичное сопоставление можно определить как проблему оптимизации двумерного деформирования соответствующие пиксели между подвергнутыми изображениями ».

Answer 3

Ключевое слово, которое вы ищете, это« (несогласие »).

Euclidean Distance (ED), на который ссылается Адам Михалцин (первый ответ), легко вычислим и как-то отражает естественное понимание расстояния слова на естественном языке. Тем не менее, при сравнении двух временных рядов следует использовать DTW, особенно когда они применяются к данным реального мира.

1) ED может применяться только к серии одинаковой длины. Поэтому, когда точки отсутствуют, ED просто не является вычислимым (если не разрезать другую последовательность, тем самым теряя больше информации).

2) ED не допускает смещения во времени или временного деформирования, противоположного всем алгоритмам, основанным на DTW.

Таким образом, ED не является реальной альтернативой DTW, поскольку требования и ограничения намного выше. Но чтобы ответить на ваш вопрос, я хочу порекомендовать вам эту лекцию:

временных рядов кластерную - обзор десятилетия Саида Aghabozorgi Али Сейед Shirkhorshidi, Teh Ин Вах http://www.sciencedirect.com/science/article/pii/S0306437915000733

Эта статья дает общее представление о (dis-), которые используются в кластеризации временных рядов. Здесь немного выдержки, чтобы мотивировать на самом деле читает газету: