高效knn算法
高效knn算法
提问于 2016-04-11 19:07:58
我试图实现knn算法，该算法在R中对一维向量进行运算，但与标准的knn算法稍有不同，因为它在有领带的情况下使用较小的元素(因此距离只是属性之间差值的绝对值)。更准确地说，我试图找出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...
}回答 1
Stack Overflow用户
回答已采纳
发布于 2016-04-11 19:27:33
1D中的kNN很简单。
对价值进行排序。若要执行查询，请通过双分类搜索在排序序列中定位值。然后，通过向两边(较小或更大)的k次上最接近的值移动，找到k最接近的值。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36557208
复制相关文章
相似问题
腾讯云开发者
