Scala中高效的近邻搜索

让这个坐标类与欧几里得距离

case class coord(x: Double, y: Double) {
  def dist(c: coord) = Math.sqrt( Math.pow(x-c.x, 2) + Math.pow(y-c.y, 2) ) 
}

并让坐标网格，例如

val grid = (1 to 25).map {_ => coord(Math.random*5, Math.random*5) }

然后对于任何给定的坐标

val x = coord(Math.random*5, Math.random*5)

离x最近的点是

val nearest = grid.sortWith( (p,q) => p.dist(x) < q.dist(x) )

因此前三个最接近的是CCD_ 2。

有没有一种方法可以使这些计算更具时间效率，特别是对于具有一百万点的网格的情况？

我不确定这是否有帮助（甚至是愚蠢的），但我想到了这个：

使用排序函数对网格中的所有元素进行排序，然后拾取第一个k元素。如果你考虑像递归合并排序这样的排序算法，你会得到这样的东西：

将收藏一分为二
在两半重复
合并已排序的两半

也许你可以根据自己的需要优化这样一个功能。合并部分通常会合并两半的所有元素，但您只对合并后的第一个k感兴趣。所以你只能合并，直到你有了k元素，然后忽略其他元素

因此，在最坏的情况下，当k >= n（n是网格的大小）时，您仍然只有合并排序的复杂性。O(n log n)老实说，我无法确定这个解决方案相对于k的复杂性。（目前太累了）

以下是该解决方案的一个示例实现（它肯定不是最优的，也不是通用的）：

def minK(seq: IndexedSeq[coord], x: coord, k: Int) = {
  val dist = (c: coord) => c.dist(x)
  def sort(seq: IndexedSeq[coord]): IndexedSeq[coord] = seq.size match {
    case 0 | 1 => seq
    case size => {
      val (left, right) = seq.splitAt(size / 2)
      merge(sort(left), sort(right))
    }
  }
  def merge(left: IndexedSeq[coord], right: IndexedSeq[coord]) = {
    val leftF = left.lift
    val rightF = right.lift
    val builder = IndexedSeq.newBuilder[coord]
    @tailrec
    def loop(leftIndex: Int = 0, rightIndex: Int = 0): Unit = {
      if (leftIndex + rightIndex < k) {
        (leftF(leftIndex), rightF(rightIndex)) match {
          case (Some(leftCoord), Some(rightCoord)) => {
            if (dist(leftCoord) < dist(rightCoord)) {
              builder += leftCoord
              loop(leftIndex + 1, rightIndex)
            } else {
              builder += rightCoord
              loop(leftIndex, rightIndex + 1)
            }
          }
          case (Some(leftCoord), None) => {
            builder += leftCoord
            loop(leftIndex + 1, rightIndex)
          }
          case (None, Some(rightCoord)) => {
            builder += rightCoord
            loop(leftIndex, rightIndex + 1)
          }
          case _ =>
        }
      }
    }
    loop()
    builder.result
  }
  sort(seq)
}

Profile您的代码，看看代价是什么。

排序的方式已经非常低效。

不要一直重新计算距离。这不是免费的——很可能你的程序99%的时间都花在计算距离上（使用探查器来找出！）

最后，您可以使用索引结构。对于欧几里得距离，您可能有最大的索引选择来加速查找最近的邻居。有k-d树，但我发现R树通常更快。如果你想玩这些，我推荐ELKI。它是一个用于数据挖掘的Java库（因此它也应该很容易从Scala中使用），并且它有大量的索引结构可供选择。

这一次做起来很有趣。

case class Coord(x: Double, y: Double) {
    def dist(c: Coord) = Math.sqrt(Math.pow(x - c.x, 2) + Math.pow(y - c.y, 2))
}
class CoordOrdering(x: Coord) extends Ordering[Coord] {
    def compare(a: Coord, b: Coord) = a.dist(x) compare b.dist(x)
}
def top[T](xs: Seq[T], n: Int)(implicit ord: Ordering[T]): Seq[T] = {
    // xs is an ordered sequence of n elements. insert returns xs with e inserted 
    // if it is less than anything currently in the sequence (and in that case, 
    // the last element is dropped) otherwise returns an unmodifed sequence
    def insert[T](xs: Seq[T], e: T)(implicit ord: Ordering[T]): Seq[T] = {
      val (l, r) = xs.span(x => ord.lt(x, e))
      (l ++ (e +: r)).take(n)
    }
    xs.drop(n).foldLeft(xs.take(n).sorted)(insert)
}

经过最低限度的测试。这样称呼它：

val grid = (1 to 250000).map { _ => Coord(Math.random * 5, Math.random * 5) }
val x = Coord(Math.random * 5, Math.random * 5)
top(grid, 3)(new CoordOrdering(x))

编辑：很容易将其扩展到（预先）计算一次的距离

val zippedGrid = grid map {_.dist(x)} zip grid  
object ZippedCoordOrdering extends Ordering[(Double, Coord)] {
   def compare(a:(Double, Coord), b:(Double, Coord)) = a._1 compare b._1
}
top(zippedGrid,3)(ZippedCoordOrdering).unzip._2

这里有一个使用R-树数据结构的算法。对于所描述的小数据集没有用处，但它可以很好地扩展到大量对象。

使用节点表示对象或R树边界框的有序列表。使用您想要的任何距离函数，顺序都是最接近的。维护插入时的订单。

通过在R树的根节点中插入边界框来初始化列表。

获取下一个最近的对象：

（1）从列表中删除第一个元素。

（2）如果它是一个对象，那么它就是最近的对象。

（3）如果它是R树的非叶节点的边界框，则根据该节点的子节点的距离，将代表该节点的所有边界框插入列表中的适当位置。

（4）如果是R树叶节点的边界框，则根据其距离插入该节点的子对象（对象，而不是其边界框）。

（5）返回步骤（1）。

这份名单仍然很短。前面将是我们感兴趣的附近对象，列表中稍后的节点将是表示更远对象集合的框。

这取决于exact还是approximation。

作为几个基准，例如http://www.slideshare.net/erikbern/approximate-nearest-neighbor-methods-and-vector-models-nyc-ml-meetup证明了CCD_ 12的近似是一个很好的解。

我写了ann4s，它是Annoy 的Scala实现

Annoy（Approximate Nearest Neighbors Oh Yeah）是一个带有Python绑定的C++库，用于搜索空间中靠近给定查询点的点。它还创建了基于只读文件的大型数据结构，这些数据结构被映射到内存中，以便许多进程可以共享相同的数据。

看看这个回购。

相关内容

最新更新

热门标签：