如何避免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搜索循環？

回答

相關問題