Почему использование собственной функции приближения в proxy::dist делает ее такой медленной в R?

Question

Я пытаюсь использовать proxy::dist функция с пользовательской матрицей расстояния, но то, что у меня сейчас, очень медленно.

Это воспроизводимый пример того, как я вызываю свою пользовательскую функцию:

set.seed(1)
test <- matrix(runif(4200), 60, 70)
train <- matrix(runif(4200), 60, 70)
dMatrix <- proxy::dist(x = test, y = train, method = customDTW,
                     by_rows = T, 
                     auto_convert_data_frames = T)

который должен рассчитать расстояние между каждым временным рядом в test матрица со всеми временными рядами в train матрица (каждая строка является временным рядом).

Моя пользовательская функция:

customDTW <- function(ts1, ts2){

  d <- dtw(ts1, ts2,
      dist.method = "Euclidean",
      window.type = "sakoechiba",
      window.size = 20
  )
  return(d$distance)
}

Проблема в том, что по сравнению с тем, когда я использую method="DTW"или даже в случае, когда я сам вычисляю матрицу расстояний, это происходит крайне медленно, и по мере увеличения длины временного ряда или их числа экспоненциально становится медленнее. Конечно, это связано с вложенным циклом, но меня удивляет масштаб эффекта. Должна быть еще одна причина, по которой я этого не вижу.

Мой вопрос заключается в том, как еще я мог бы реализовать свой customDTW чтобы сделать это быстрее, используя proxy::dist?

---

Это мой маленький эксперимент по времени выполнения:

Время выполнения для 60X7 (с помощью proxy::dist + customDTW)

user  system elapsed 
2.852   0.012   2.867

Время выполнения для 60X70 (с помощью proxy::dist + customDTW)

user  system elapsed 
5.384   0.000   5.382 

Время выполнения для 60X700 (с помощью proxy::dist + customDTW)

user  system elapsed 
509.088  18.652 529.115

Время выполнения для 60X700 (без использования proxy::dist)

user  system elapsed 
26.696   0.004  26.753

Answer 1

R является интерпретируемым языком, и под капотом он реализован на C. Прокси-пакет, насколько я понимаю, использует возможности интерпретации R изнутри C для вызова кода R несколько раз, но это все еще не может избежать интерпретации. накладные расходы, поэтому почти любая "чистая" реализация R будет медленнее.

Определение loop=TRUE регистрация функции с прокси означает, что вышеупомянутое произойдет (прокси будет интерпретировать код R несколько раз, чтобы заполнить матрицу расстояний). Если вы действительно хотите ускорить процесс, вам нужно реализовать саму заливку в C/C++ и зарегистрировать функцию с прокси с помощью loop=FALSE; это то, что делает dtwclust (между прочим).

Возможно, вы захотите взглянуть на пакет parallelDist, если хотите протестировать свои собственные пользовательские функции C/C++, даже если вы не хотите использовать распараллеливание.

Answer 2

DTW медленный по своей природе. Рассматривали ли вы попытки использовать dtwclust (параллельная реализация dtw)?

https://github.com/asardaes/dtwclust

https://cran.r-project.org/web/packages/dtwclust/vignettes/dtwclust.pdf

Answer 3

Это то, что, как я обнаружил, улучшает скорость, но все же не так быстро, как я ожидаю. (Любая другая идея по-прежнему очень приветствуется.)

Хитрость заключается в том, чтобы зарегистрировать пользовательскую функцию расстояния с proxy (т. е. Реестр близостей здесь), чтобы вы могли использовать его как встроенную меру расстояния. Итак, сначала:

proxy::pr_DB$set_entry(FUN = customDTW, names=c("customDTW"),
                         loop = TRUE, type = "metric", distance = TRUE)

и теперь вы можете использовать его, как если бы он уже был в proxy пакет.

dMatrix <- proxy::dist(x = test, y = train, method = "customDTW",
                         by_rows = T,
                         auto_convert_data_frames = T)

Примечание. Если вы хотите использовать этот метод, customDTW Метод должен иметь дело с одной парой временных рядов, а не со всеми. Итак customDTW будет выглядеть так:

customDTW2 <- function(ts1, ts2){

  d <- dtw(ts1, ts2,
      dist.method = "Euclidean",
      window.type = "sakoechiba",
      window.size = 20
  )
  return(d$distance)
}

Для получения дополнительной информации см. ?pr_DB,