从距离矩阵开始查找K个最近邻居

Question

我正在寻找一个良好优化的函数,它接受一个n X n距离矩阵并返回一个n X k矩阵k,其中第i行中第i个数据点的最近邻居的索引.

我找到了许多不同的R软件包让你做KNN,但它们似乎都包括距离计算以及同一函数中的排序算法.特别是,对于大多数例程,主要参数是原始数据矩阵,而不是距离矩阵.就我而言,我在混合变量类型上使用非标准距离,因此我需要将排序问题与距离计算分开.

这不是一个令人生畏的问题 - 我显然可以order在循环中使用函数来获得我想要的东西(参见下面的解决方案),但这远非最佳.例如,when 小的sort函数(小于11)变得更快,但遗憾的是只返回排序值而不是所需的索引.partial = 1:kk

Answer 1

尝试使用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

Answer 2

作为记录（我不会将此标记为答案），这是一个快速而肮脏的解决方案。假设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存储了相应的距离。