从距离矩阵开始查找K个最近的邻居
我正在寻找一个良好优化的函数，它接受一个n X n距离矩阵，并返回一个n X k矩阵，其中第i行中第i个数据点的k最近邻居的索引。
我发现了一个gazillion不同的R包，可以让你做KNN，但它们似乎都包含了同一个函数内的排序算法和距离计算。 特别是，对于大多数例程来说，主要参数是原始数据矩阵，而不是距离矩阵。 就我而言，我在混合变量类型上使用非标准距离，所以我需要将距离计算中的排序问题分开。
这并不是一个令人生畏的问题 - 我显然可以在循环内部使用order函数来获得我想要的（请参阅下面的解决方案），但这远非最佳。 例如，当k很小（小于11）时， partial = 1:k的sort函数快得多，但不幸的是只返回排序值而不是所需的索引。
尝试使用FastKNN CRAN软件包（尽管它没有很好的记录）。 它提供k.nearest.neighbors函数，可以给出任意距离矩阵。 下面你有一个计算你需要的矩阵的例子。
# arbitrary data
train <- matrix(sample(c("a","b","c"),12,replace=TRUE), ncol=2) # n x 2
n = dim(train)[1]
distMatrix <- matrix(runif(n^2,0,1),ncol=n) # n x n
# matrix of neighbours
k=3
nn = matrix(0,n,k) # n x k
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是特殊的距离矩阵。 假设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是每行中具有k最近邻居索引的矩阵，为了方便， knd.mat存储了相应的距离。
上一篇: Find K nearest neighbors, starting from a distance matrix