Найдите K ближайших соседей, начиная с матрицы расстояния

Я ищу хорошо оптимизированную функцию, которая принимает n X n матрицу расстояния и возвращает n X k матрицу с индексами k ближайших соседей i-го datapoint в i-й строке.

Я нахожу gazillion различные пакеты R которые позволяют вам делать KNN, но все они, похоже, include вычисления расстояния вместе с алгоритмом сортировки в пределах одной и той же функции. В частности, для большинства процедур основным аргументом является исходная matrix данных, а не matrix расстояний. В моем случае я использую нестандартное расстояние для смешанных типов переменных, поэтому мне нужно отделить проблему сортировки от вычислений расстояния.

Это не совсем сложная проблема – я, очевидно, мог бы просто использовать функцию order внутри цикла, чтобы получить то, что я хочу (см. Мое решение ниже), но это далеко не оптимально. Например, функция sort с partial = 1:k когда k мала (меньше 11), идет намного быстрее, но, к сожалению, возвращает только отсортированные значения, а не нужные индексы.

Попытайтесь использовать пакет FastKNN CRAN (хотя он недостаточно хорошо документирован). Он предлагает функцию k.nearest.neighbors где может быть задана произвольная matrix расстояний. Ниже приведен пример, который вычисляет необходимую матрицу.

 # arbitrary data train <- matrix(sample(c("a","b","c"),12,replace=TRUE), ncol=2) # nx 2 n = dim(train)[1] distMatrix <- matrix(runif(n^2,0,1),ncol=n) # nxn # matrix of neighbours k=3 nn = matrix(0,n,k) # nxk for (i in 1:n) nn[i,] = k.nearest.neighbors(i, distMatrix, k = k) 

Примечание. Вы всегда можете проверить список пакетов Cran для связанных функций Ctrl + F = 'knn': https://cran.r-project.org/web/packages/available_packages_by_name.html

Для записи (я не буду отмечать это как ответ), вот быстрое и грязное решение. Предположим, что sd.dist – специальная matrix расстояний. Пусть k.for.nn – число ближайших соседей.

 n = nrow(sd.dist) knn.mat = matrix(0, ncol = k.for.nn, nrow = n) knd.mat = knn.mat for(i in 1:n){ knn.mat[i,] = order(sd.dist[i,])[1:k.for.nn] knd.mat[i,] = sd.dist[i,knn.mat[i,]] } 

Теперь knn.mat – это matrix с индексами k ближайших соседей в каждой строке, и для удобства knd.mat сохраняет соответствующие расстояния.

Давайте будем гением компьютера.