我试图实现knn算法，它对r中的一维向量进行运算，但与标准向量稍有不同，因为它在平局的情况下采用较小的元素（所以距离只是属性之间差异的绝对值）。更准确地说，我试图找到k个数字，它们是最接近给定数字的，如果有联系，我希望选择较小的数字。
听起来很简单，但是我的算法需要几秒钟才能完成，而类包中的算法（knn）则会立即输出一个答案（尽管在并列或随机元素的情况下需要所有元素）。我的是：
我抽取了一份培训样本，并越来越多地订购。
我取一个元素（一个数字）
2.5条并在训练样本中搜索它小于某个数字的第一个位置。
我从训练样本中抽取2k+1个数字——k在2.5中找到的一个数字的左边，k在右边（如果这个数字少于k，我会尽可能多地抽取）。
最后，我计算所选元素与我在2中所取元素的距离，并将它们与相应的元素逐渐排序（以便元素及其距离逐渐排序）
然后从4中创建的列表中获取k个第一元素。（所以没有两个有相同的距离）
但是，男孩，它需要6或7秒来完成…你有什么改进的想法吗（这不是一个R特定的问题，只是碰巧我在R中做的）。
编辑。代码：
dec <- function(u, x, k) {
## u is the training sample sorted increasingly
## x is an object for classification
## k is a knn parameter
knn <- list()
i <- 1
div <- 0
for (j in u) {
if (x < j) {
div <- 0
break
}
i <- i+1
}
if (div == 0) {
distances <- array(0,dim=c(2,k))
z <- 1
for (j in 1:k) {
distances[1,z] <- u[10000-j]
distances[2,z] <- abs(u[10000-j]-x)
}
} else {
end1 <- div+k
end2 <- div-k
if (div<k) {
distances <- array(0,dim=c(2,(div+k)))
a <- 1
for (j in u[1:end1]) {
distances[1,a] <- j
distances[2,a] <- abs(j-x)
a <- a+1
}
} else if (10000-div<k) {
distances <- array(0,dim=c(2,(1000-div+k)))
a <- 1
for (j in u[end2:10000]) {
distances[1,a] <- j
distances[2,a] <- abs(j-x)
a <- a+1
}
} else {
a <- 1
distances <- array(0,dim=c(2,(2*k+1)))
for (j in u[end1:end2]) {
distances[1,a] <- j
distances[2,a] <- abs(j-x)
a <- a+1
}
}
distances <- t(distances)
distances <- distances[ order( distances[,2], distances[,1]), ]
distances <- t(distances)
}
for (i in 1:k) {
if (i>1 && distances[1,i-1] != distances[1,i])
knn[i] <- distances[1,i]
}
## and sth later...
}
最佳答案
1d中的knn很简单。
越来越多地对价值观进行排序。要执行查询，请通过二分法搜索在排序的序列中定位值。然后，通过在任意一侧（较小或较大）的k次上步进到最接近的位置，找到k个最接近的值。
关于algorithm - 高效的knn算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36557208/