Encontre K vizinhos mais próximos, a partir de uma matriz de distância

Estou procurando uma function bem otimizada que aceite uma matriz de distância n X n e retorne uma matriz n X k com os índices dos k vizinhos mais próximos do i-ésimo ponto de dados na linha i.

Eu acho um gazilhão de pacotes R diferentes que permitem fazer KNN, mas todos eles parecem include os cálculos de distância, juntamente com o algoritmo de sorting dentro da mesma function. Em particular, para a maioria das rotinas, o argumento principal é a matriz de dados original, não uma matriz de distância. No meu caso, estou usando uma distância fora do padrão nos tipos de variables ​​mistas, portanto, preciso separar o problema de sorting dos cálculos de distância.

Este não é exatamente um problema assustador – eu obviamente poderia usar apenas a function order dentro de um loop para obter o que eu quero (veja minha solução abaixo), mas isso está longe de ser ideal. Por exemplo, a function de sort com partial = 1:k quando k é pequena (menor que 11) é muito mais rápida, mas infelizmente retorna apenas valores classificados em vez dos índices desejados.

Tente usar o pacote FastKNN CRAN (embora não esteja bem documentado). Ele oferece a function k.nearest.neighbors , onde uma matriz de distância arbitrária pode ser fornecida. Abaixo você tem um exemplo que calcula a matriz que você precisa.

 # 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: Você sempre pode verificar a lista de pacotes Cran para funções relacionadas Ctrl + F = 'knn': https://cran.r-project.org/web/packages/available_packages_by_name.html

Para o registro (não vou marcar isso como a resposta), aqui está uma solução rápida e suja. Suponha que sd.dist seja a matriz de distância especial. Suponha que k.for.nn seja o número de vizinhos mais próximos.

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

Agora knn.mat é a matriz com os índices dos k vizinhos mais próximos em cada linha e, por conveniência, knd.mat armazena as distâncias correspondentes.

Intereting Posts