Encuentra K vecinos más cercanos, comenzando desde una matriz de distancia

Estoy buscando una función bien optimizada que acepte una matriz de distancia n X n y devuelva una matriz n X k con los índices de los k vecinos más cercanos al i-ésimo punto de datos en la i-ésima fila.

Encuentro un montón de diferentes paquetes R que te permiten hacer KNN, pero todos parecen incluir los cálculos de distancia junto con el algoritmo de ordenación dentro de la misma función. En particular, para la mayoría de las rutinas, el argumento principal es la matriz de datos original, no una matriz de distancia. En mi caso, estoy usando una distancia no estándar en tipos de variables mixtas, por lo que necesito separar el problema de clasificación de los cálculos de distancia.

Esto no es exactamente un problema desalentador: obviamente podría usar la función de order dentro de un ciclo para obtener lo que quiero (ver mi solución a continuación), pero esto dista mucho de ser óptimo. Por ejemplo, la función de sort con partial = 1:k cuando k es pequeña (menos de 11) va mucho más rápido, pero desafortunadamente devuelve solo valores ordenados en lugar de los índices deseados.

Intente utilizar el paquete FastKNN CRAN (aunque no está bien documentado). Ofrece k.nearest.neighbors función donde se puede dar una matriz de distancia arbitraria. A continuación tienes un ejemplo que calcula la matriz que necesitas.

 # 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) 

Aviso: siempre puede verificar la lista de paquetes de Cran para funciones relacionadas con Ctrl + F = 'knn': https://cran.r-project.org/web/packages/available_packages_by_name.html

Para el registro (no marcaré esto como la respuesta), aquí hay una solución rápida y sucia. Supongamos que sd.dist es la matriz de distancia especial. Supongamos que k.for.nn es el número de vecinos más cercanos.

 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,]] } 

Ahora knn.mat es la matriz con los índices de los k vecinos más cercanos en cada fila, y por conveniencia knd.mat almacena las distancias correspondientes.