python - 从列表中过滤掉附近的点

Question

我half-answered a question about finding clusters of mass in a bitmap .我说一半回答是因为我把它留在了一个条件下，我把位图中的所有点都按质量排序，然后留给读者过滤列表，从同一个簇中删除点。

然后，在考虑该步骤时，我发现解决方案并没有像我想象的那样突然出现在我面前。所以现在想请大家帮忙。我们有一个像这样的质量点列表(一个 Python 元组列表，但您可以用任何语言表示它):

[ (6, 2, 6.1580555555555554),
  (2, 1, 5.4861111111111107),
  (1, 1, 4.6736111111111107),
  (1, 4, 4.5938888888888885),
  (2, 0, 4.54),
  (1, 5, 4.4480555555555554),
  (4, 7, 4.4480555555555554),
  (5, 7, 4.4059637188208614),
  (4, 8, 4.3659637188208613),
  (1, 0, 4.3611111111111107),
  (5, 8, 4.3342191043083904),
  (5, 2, 4.119574829931973),
  ...
  (8, 8, 0.27611111111111108),
  (0, 8, 0.24138888888888888) ]

每个元组的形式是:

(x, y, mass)

注意这里的列表是排序的。如果您的解决方案不希望对它们进行排序，那完全没问题。

挑战，if you recall , 是寻找质量的主要簇。集群的数量未知。但是你知道位图的尺寸。有时，一个簇中的几个点的质量比下一个(大小)簇的中心大。所以我想做的是从质量更高的点出发，移除同一簇中的点(附近的点)。

当我尝试这个时，我最终不得不一遍又一遍地浏览列表的某些部分。我有一种感觉，我对此很愚蠢。你会怎么做？伪代码或真实代码。当然，如果您可以使用 Python 代码从我在该答案中留下的地方起飞，那么我可以更轻松地进行试验。

下一步是计算出位图中实际有多少簇。我仍在努力定义这个问题，所以我可能会带着一个关于它的问题回来。

编辑: 我应该澄清一下，我知道这个问题没有“正确”的答案。问题的名称是关键。我的集群的第一阶段已完成。 我正在寻找一种快速、准确-“足够”的方法来过滤掉附近的点。

如果您看到我如何使问题更清楚，请告诉我。

Answer 1

正如您所知，您正在寻求 ill-posed 的解决方案问题:不存在确定的解决方案。很好……这只会让它变得更有趣。你的问题是不适定的，主要是因为你不知道你想要多少个集群。聚类是机器学习的关键领域之一，多年来已经开发出许多方法。

正如 Arachnid 指出的那样，k-means算法往往是一个很好的算法，而且很容易实现。结果主要取决于最初的猜测和所需集群的数量。为了克服初始猜测问题，通常会使用随机初始化多次运行算法并选择最佳结果。您需要定义“最佳”的含义。一种衡量标准是每个点到其聚类中心的均方距离。如果你想自动猜测有多少个集群，你应该用整个范围内的集群运行算法。对于任何良好的“最佳”度量，更多的集群总是比更少的集群看起来更好，因此您需要一种方法来惩罚集群过多。 MDL维基百科上的讨论是一个很好的起点。

K-means 聚类基本上是最简单的 mixture model .有时升级到通过期望最大化学习的高斯混合(在刚刚给出的链接中描述)是有帮助的。这可能比 k-means 更稳健。理解它需要更多的努力，但是当你理解它时，它并不比 k-means 更难实现。

还有很多其他 clustering techniques例如凝聚聚类和谱聚类。凝聚集群很容易实现，但选择何时停止构建集群可能会很棘手。如果您进行凝聚聚类，您可能需要查看 kd trees用于更快的最近邻搜索。 smacl 的回答描述了一种使用 Voronoi 图进行凝聚聚类的稍微不同的方法。

有些模型可以自动为您选择集群数量，例如基于 Latent Dirichlet Allocation 的模型。 ，但他们更难正确理解一个工具。

您可能还想查看 mean-shift算法，看看它是否更接近您真正想要的。