如何避免KNN搜索循环？

我的目标是让每个数据点的k个最近邻居。我想避免在查找时使用for循环，并在每个rdd_distance点上同时使用其他的东西，但我无法弄清楚如何执行此操作。如何避免KNN搜索循环？

parsedData = RDD[Object] 
//Object have an id and a vector as attribute 
//sqdist1 output is a Double 

var rdd_distance = parsedData.cartesian(parsedData) 
    .flatMap { case (x,y) => 
    if(x.get_id != y.get_id) 
     Some((x.get_id,(y.get_id,sqdist1(x.get_vector,y.get_vector)))) 
    else None 
    } 
for(ind1 <- 1 to size) { 
    val ind2 = ind1.toString 
    val tab1 = rdd_distance.lookup(ind2) 
    val rdd_knn0 = sc.parallelize(tab1) 
    val tab_knn = rdd_knn0.takeOrdered(k)(Ordering[(Double)].on(x=>x._2)) 
}

这是可能的，而不使用for循环查找？

来源

2015-06-26 KyBe

看看这个https://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data – abalcerek

此代码解决了您的问题（但效率很低，当parsedData的数量很大时）。

rdd_distance.groupByKey().map { 
    case (x, iterable) => 
     x -> iterable.toSeq.sortBy(_._2).take(k) 
    }

所以这是更合适的解决方案。

import org.apache.spark.mllib.rdd.MLPairRDDFunctions._  

rdd_distance.topByKey(k)(Ordering.by(-_._2)) // because smaller is better.

请注意，此代码包括Spark 1.4.0。如果您使用的是早期版本，请改用此代码https://github.com/apache/spark/blob/master/mllib/src/main/scala/org/apache/spark/mllib/rdd/MLPairRDDFunctions.scala

topBykey的想法是使用BoundedPriorityQueue与aggregateByKey，它保留了前k项。

来源

2015-06-26 13:10:20 emeth

不幸的是，parsedData很大，我想避免groupByKey这就是，在我读的，没有足够的性能。 – KyBe

对，所以你需要看看'topByKey'。 – emeth

是否有一个等价物给我minByKey而不是topByKey，或者这是通过（-_._ 2）来实现的。 – KyBe

如何避免KNN搜索循环？

回答

相关问题