15

我正在开发一个模拟程序。有成群的动物（角马），在那个畜群中，我需要能够找到一种远离畜群的动物。

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

绿点远离牛群

当然，有一个简单的算法可以解决这个问题。计算每个点的邻域中的点数，然后如果该邻域为空（其中为 0 点），则我们知道该点远离牛群。

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

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

编辑@amit：我们想避免这种情况。左角的一组绿点会被选中，尽管它们不应该被选中，因为远离牛群的不是单一的动物，而是一群动物。我们只是在寻找远离牛群（而不是一群）的单一动物。

一群远离牛群的绿点

4

8 回答 8

7

对于最近邻查询，经常使用 kd-trees。这将导致 O(n log n) 查询（一个查询在 log(n) 乘以 n 个查询中，并且构建 kd-tree 本身在 O(n log n) 中），我可以看到这对一对夫妇来说工作得非常快数百万个点，并且有些库也已经非常高效（例如ANN）。

此外，ANN 代表“近似最近邻”，在不需要精确距离时可以更快。由于在您的情况下，您只想检测第一个最近邻距离是大还是小，您可以设置一个相当高的阈值，这会使事情变得更快。

由此，您可以确定每个最近邻居的距离分布，并找到异常值。对所有这些距离进行排序以确定异常值又是 O(n log n)。

于 2012-12-27T23:33:22.213 回答
6

我认为您正在寻找异常检测算法（这是一个无监督的机器学习问题）。

这个想法是找到与其他实例相比“表现”不正常的实例。

以这个开头的一组视频（来自 Coursera 的在线机器学习课程）描述了这个问题以及如何很好地解决它。

编辑：
一个更简单的替代方法是找到所有点（动物）的平均值，并“选择”k离它最远的动物（或者，所有与某个阈值距离更大的点）。

如果您有多个组，您可能希望首先对它们进行聚类。一种方法是使用k-means clustering，并在每个组（集群）上应用上述方法之一。

于 2012-12-27T10:52:29.833 回答
5

由于您正在寻找一只孤独的动物，您可以使用两个凸层来处理O(N log N + ab*) O(N log N)，其中 a 是第一个外壳的大小，b 是第二个外壳的大小船体。

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

如果最近的邻居足够远，则外部（第一个）船体中的动物被“隔离”。最近的邻居是内壳和外壳中该点的最近点（不是同一点）。在外壳的情况下，您可能只需检查到所考虑点的左右点的距离即可。因此大 O 中的 a*b 而不是 a(a+b)

如果您预计牛群的“内部”动物之一被认为是孤立的（在这种情况下，内部是指不构成外壳的任何动物），那么上述方法可能不起作用。在这种情况下，您需要使用更复杂的方法。

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

编辑：我还应该指出，有动态凸包结构可用于维护一个凸包，只需添加和删除点即可在其中移动点。这可能对实时更新有所帮助。

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

于 2012-12-28T10:47:08.817 回答
4

这是一个简单的想法。（聚类方法）

根据 x,y 值将您的动物放在一个网格中。如果您不想检测到错误的异常值，您可以使用两个网格。在这个例子中，我使用了两个用黑色和蓝色线条表示的网格容器。

网格

异常值定义为：an animals which is alone in both it's blue and black grid.

您保留网格索引和网格中包含的动物之间的引用。

迭代动物并使用它们的 x,y 值将它们放入网格中。然后迭代黑色网格。当网格内容为 1 时，通过黑色网格内的动物找到蓝色网格参考。检查蓝色网格的内容。如果为 1，则该动物为异常值。

运行时间应该很快。

n: number of animals
b: size of black grid

把动物放在格子里O(n)。迭代黑色网格是O(b)

这O(n) + O(b)总共提供了构建信息和定位异常值。

定位异常值需要O(b)时间。如果您的网格足够小，这将确保非常快的运行时间。

上图应说明两个异常值。

实现应该相对简单。您可以使用基于网格的策略变体，使用不同的网格布局或使用更多的网格容器。

编辑： 这种方法与本文中描述的不计算距离的单元格方法有些相关。http://www.slac.stanford.edu/cgi-wrap/getdoc/slac-r-186.pdf 此方法不会排除所有案例的错误检测异常值。要获得更完美的解决方案（对于地图上所有可能的动物位置），您必须添加从一个单元格中检测到的 1 个动物到相邻单元格内容的距离计算。你可以在这里阅读更多关于它的信息。

于 2012-12-28T01:24:54.143 回答
3

您可以尝试基于三角测量的聚类方法：

  1. 形成数据集的Delaunay 三角剖分。有有效的算法可以做到这一点，例如提供性能的CGAL和Triangle 。O(|V|*log(|V|))

  2. 对于集合中的每个顶点，通过扫描附加边的列表来计算“长度测量”，记录每个顶点的最小边长。这应该是O(|V|+|E|)。（您也可以使用平方边长，以避免取平方根！）

  3. 根据上面计算的“长度测量”选择顶点。如何做到这一点将取决于您如何将“远离”的群体分类。几种可能性：

    • 一种简单的方法是仅使用静态长度容差，以便任何顶点在其长度测量值超过此值时都将被归类为“远离”。这将是一个O(|V|)考验。

    • 更复杂的方法也是可能的，例如基于三角剖分中所有边缘的平均边缘长度的因子设置长度容差 - 这将根据畜群的平均分布来缩放容差。这将是一个O(|V|+|E|)考验。

这种方法的一个优点是它应该对在主集群之外具有小“子群”的牛群具有鲁棒性（根据您的第二个示例）。

于 2012-12-27T23:47:09.347 回答
3

为了加快此类查询，请使用空间索引结构。

kd-trees、quadtrees、R-trees、grids 只是您的一些选择。

在这样的索引结构中，您可以快速找到最近的邻居。最近的（第二近的，第三近的）邻居比其他奶牛远得多的奶牛可能是您正在寻找的异常值。

选择哪种索引结构可能是最大的挑战。在进行模拟时，可以有效更新的东西可能是最好的。kd-trees 不能很好地更新，但需要时不时地重建（如果你巧妙地实现它，重建应该很快）。R*-trees 可能最适合重建，但它们实际上是要存储在硬盘上。

我认为为内存模拟提供最佳性能的只是grids。您可以尝试不同的网格大小，选择最适合的。另外，它们允许一些非常好的优化：在有奶牛的网格单元中n，到最近的 n-1 头奶牛的距离最多为sqrt(w*w+h*h)，其中w和h是您的网格距离。所以你可能不需要真正查看那些有“足够”奶牛的细胞。n对您来说可能低至 3。现在在只有一头牛的网格单元中，它还不需要是异常值。它可能就在一个非常满的相邻单元的边缘。但是这样的细胞应该不会很多，你可以很容易地检查这些奶牛。

于 2012-12-30T12:42:44.347 回答
1

这个怎么样：

  1. 在 X 方向对您的动物进行分类。
  2. 查找远离其前后元素的 X 值
  3. 这些是孤独的人的候选人。
  4. 对 Y 方向重复相同的操作

两个列表（X 和 Y）中的候选人肯定是分开的。对于仅存在于一个列表中的候选人来说，这也是几乎可以肯定的。

排序的复杂度为 O(n log n)，扫描的复杂度为 O(n)。我怀疑你可以在不透露数据结构的情况下做得更好。

步骤 1 也可以通过使用复杂度为 O(n) 的桶或基数排序来解决

如果您可以维护这两个排序列表，我会为每只动物添加一个属性“lonley”。当您不断地遍历您的动物时，您只需通过检查其在已排序 X/Y 数组中当前位置左右元素的距离来更新“lonley”状态。

于 2012-12-27T11:22:33.817 回答
0

这是一个简单的线性时间过程：

假设在任何给定时间只有一个牛群，请将您的动物的位置视为来自双变量（正态？）分布的样本。以线性时间计算总体的均值和标准差。以线性时间计算平均值与每只动物之间的马氏距离。t正如@amit 所建议的那样，任何超过某个阈值的动物都不是牛群。您可以设置该阈值。一种可能的选择是手工制作一些示例并使用它们来调整值，这很容易，因为马氏距离是尺度不变的。我的直觉是 3 是一个很好的起点——距离平均值超过 3 个标准差的任何东西都是异常值。

于 2013-01-06T16:08:38.847 回答