快速找到远离牛群的动物的算法

Question

我正在开发一个模拟程序.有成群的动物(角马),在那群中,我需要找到一只远离牛群的动物.

在下图中,绿点远离牛群.我希望能够快速找到这些要点.

当然,有一个简单的算法来解决这个问题.计算每个点附近的点数,然后如果该邻域是空的(其中0点),那么我们知道这一点远离牛群.

问题是这个算法根本没有效率.我有一百万点,并且在每百万点上应用这个算法非常慢.

有什么东西会更快吗？也许用树木？

编辑@amit:我们想避免这种情况.A组在左上角绿点会被选择,即使他们应该不是,因为它不是一个单一的动物是从牛群离开,这是一组动物.我们只是寻找远离牛群的一只动物(不是一群人).

Answer 1

对于最近邻居查询,经常使用kd-tree.这将导致O(n log n)查询(一个查询在log(n)次n次查询中,并且构建kd-tree本身在O(n log n)中)我可以看到这对于一对夫妇来说非常快数百万点,并且有一些库已经非常有效(例如ANN).

此外,ANN代表"近似最近邻居",并且在不需要精确距离时甚至可以更快.因为在您的情况下,您只想检测第一个最近邻距离是大还是小,您可以设置一个相当高的阈值,这将使事情更快.

由此,您可以确定距离最近邻居的距离分布,并找出异常值.对所有这些距离进行排序以确定异常值再次为O(n log n).

Answer 2

我认为你正在寻找异常检测算法(这是一个无监督的机器学习问题).

我们的想法是找到与其他实例相比"行为"不正常的实例.

从这一个开始的视频集(来自Coursera中的在线机器学习课程)描述了问题以及如何很好地处理它.

编辑:
一个更简单的选择是找到所有点(动物)的平均值,并"选择" k距离它最远的动物(或者,选择距离某个阈值更远的所有点).

如果您有多个组,则可能需要先将它们聚类.一种方法是使用k-means聚类,并在每个组(集群)上应用上述方法之一.

Answer 3

因为你正在寻找一个孤动物,可以使用两个凸层为O(N日志N + AB*) O(N日志N),其中一个是第一船体的尺寸和b为第二大小船体.

1. 从位置列表创建凸包
2. 从位置列表中创建第二个凸包,不包括第一个船体中的那些.

外(第一)船体中的动物如果它的最近邻居足够远,则是"孤立的".最近的邻居是内壳和外壳中那个点(不是同一点)的壁橱点.在外壳的情况下,您可以通过检查到所考虑的点的左侧和右侧的点的距离来获得.因此大O中的a*b而不是(a + b)

如果你期望在牛群的"内部"动物之一被认为是分离的情况下(在这种情况下,内指的是任何动物并不能弥补外船体),那么以上方法可能不会工作.在这种情况下,您需要使用更复杂的方法.

如果a + b接近N,它也可能是低效的,因为它基本上是O(N ^ 2).虽然,在这种情况下,任何动物都不太可能是非常孤立的.

编辑:我还应该指出,有动态凸包结构,可以用来维持一个凸包,只需添加和删除点就可以移动点.这可能对实时更新有所帮助.

*这实际上是O(N),使用旋转卡尺.