Здравствуйте! Подозреваю что уже достал тут некоторых людей своими вопросами про dtw и дистанции всякие но разница в нюансах настолько огромная что я вынужден снова просить о помощи.
Есть функция dtw из пакета с таким же названием
dtw(x, y=NULL, dist.method="Euclidean", step.pattern=symmetric2, window.type="none", keep.internals=FALSE, distance.only=FALSE, open.end=FALSE, open.begin=FALSE, ... )
В функции есть три метода расчета в матрице расстояний - symmetric1 , symmetric2 , asymmetric. Меня интересует метод вычисления расстояния в матрице под названием step.pattern=symmetric2
В документации по пакету описание довольно смазное
1. Well-known step patterns
These common transition types are used in quite a lot of implementations.
symmetric1 (or White-Neely) is the commonly used quasi-symmetric, no local constraint, non-normalizable. It is biased in favor of oblique steps. symmetric2 is normalizable, symmetric, with no local slope constraints. Since one diagonal step costs as much as the two equivalent steps along the sides, it can be normalized dividing by N+M (query+reference lengths).
В исходнике разобраться так и не смог, слишком я еще слаб в программировании.
У меня есть функция dtw на с++
#include <Rcpp.h>
using namespace Rcpp;
// [[Rcpp::export]]
double dtw_rcpp(const NumericVector& x, const NumericVector& y) {
size_t n = x.size(), m = y.size();
NumericMatrix res = no_init(n + 1, m + 1);
std::fill(res.begin(), res.end(), R_PosInf);
res(0, 0) = 0;
double cost = 0;
size_t w = std::abs(static_cast<int>(n - m));
for (size_t i = 1; i <= n; ++i) {
for (size_t j = std::max(1, static_cast<int>(i - w)); j <= std::min(m, i + w); ++j) {
cost = std::abs(x[i - 1] - y[j - 1]);
res(i, j) = cost + std::min(std::min(res(i - 1, j), res(i, j - 1)), res(i - 1, j - 1));
}
}
return res(n, m);
}
По тестам она аналогична dtw(x, y, step.pattern=symmetric1) из пакета dtw package. Подскажите пожалуйста что нужно изменить в моей с++ функции чтобы она стала аналогичной функции с dtw(x, y, step.pattern=symmetric2)
========================================================== =========Дописал...=======================================
Немного пообщался с автором пакета dtw и он дал ту самую нехитрую формулу расчета здесь
Я сделал функцию которая может считать как symmetric1 так и symmetric2
#include <Rcpp.h>
#include <numeric>
using namespace Rcpp;
// [[Rcpp::export]]
double cpp_dtw_dynamic(NumericVector x, NumericVector y, int symmetricType)
{
int n = x.size();
int m = y.size();
NumericMatrix results (n + 1, m + 1);
for(int i = 0; i <= n ; i++)
for(int j = 0; j <= m ; j++)
results(i, j) = 9999;//INT_MAX
results(0, 0) = 0;
int win = std::abs(n-m);
double cost = 0;
for(int i = 1 ; i <= n ; i++)
for(int j = std::max(1, i-win) ; j <= std::min(m, i+win) ; j++)
{
if (symmetricType == 1)
{
cost = std::abs(x[i-1] - y[j-1]);
results(i, j) = cost + std::min(std::min(results(i-1,j),results(i,j-1)),results(i-1,j-1));
}
else
{
cost = std::abs(x[i-1] - y[j-1]);
results(i, j) = std::min(std::min((results(i-1,j-1) + 2*cost), (results(i, j-1) + cost)), (results(i-1,j) + cost));
}
}
return results(n,m);
}
проверил на соответствие моей функции с встроенной.
library(dtw)
Rcpp::sourceCpp("C:/Users/TARAS/Desktop/DTWsym2.cpp")
n <- 50
ma <- matrix(ncol = 4,nrow = n)
for(i in 1:n){
x <- rnorm(20)
y <- rnorm(10)
# symmetric1
ma[i,1] <- dtw(x,y, distance.only = T,step.pattern = symmetric1)$distance
ma[i,2] <- cpp_dtw_dynamic(x,y,symmetricType = 1)
# symmetric2
ma[i,3] <- dtw(x,y, distance.only = T,step.pattern = symmetric2)$distance
ma[i,4] <- cpp_dtw_dynamic(x,y,symmetricType = 2)
}
par(mfrow=c(1:2))
plot(ma[,1] ,t="l" ,main = "symmetric1")
lines(ma[,2] ,col=2 )
plot(ma[,3] ,t="l" ,main = "symmetric2")
lines(ma[,4] ,col=2 )
результаты разнятся, почему так? все же по сути одинаково
Подозреваю что уже достал тут некоторых людей
– ничего страшного, задавайте дальше. Но постарайтесь, пожалуйста, делать вопросы лаконичнее. Оставляйте только тот код, который необходим (и достаточен) для воспроизведения проблемы. А иллюстрации добавляйте через встроенный инструмент редактора, так они гарантированно не исчезнут через какое-нибудь время.