我正在尝试实现 knn 算法,该算法对 R 中的一维向量进行操作,但它与标准算法略有不同,因为它在平局的情况下采用较小的元素(因此距离是只是属性之间差异的绝对值)。更准确地说,我试图找到与给定数字最接近的 k 个数字,如果有平局,我希望选择较小的数字。
听起来很简单,但我的算法需要几秒钟才能完成,而类包 (knn) 中的算法会立即输出答案(尽管它需要所有元素以防平局或随机元素)...我的以下:
- 我对训练样本进行抽样并对其进行越来越多的排序。
- 我取一个元素(一个数字) 2.5.并搜索第一个小于训练样本中某个数字的位置。
- 我从训练样本中取出 2k+1 个数字——k 在 2.5 中找到的数字的左边,k 在右边(如果这样的数字少于 k,我会尽可能多地取出)。
- 最后,我计算了所选元素与我在 2 中采用的元素的距离,并将它们与相应的元素一起递增排序(以便元素及其距离递增排序)
- 然后我从 4 中创建的列表中取出第 k 个元素。(这样没有两个元素的距离相同)
但是 child ,完成需要 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...
}
最佳答案
一维的 kNN 很简单。
对值进行递增排序。要执行查询,请通过二分法搜索在已排序的序列中定位值。然后通过步进到任一侧(更小或更大)最接近的值 k 次,找到 k 个最接近的值。
关于algorithm - 高效的knn算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36557208/