如何避免 KNN 搜索的 for 循环？

Question

我的目标是获得每个数据点的 k 个最近邻居。我想避免在查找中使用 for 循环并在每个 rdd_distance 点上同时使用其他东西，但我不知道该怎么做。

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 循环是否可行？

Answer 1

这段代码解决了你的问题（但是当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 个项目。

如何避免 KNN 搜索的 for 循环？

How can i avoid for loop for KNN search?

scala

apache-spark

rdd