从列表中过滤掉附近的点

我半回答了一个关于在位图中找到质量簇的问题.我说半答案是因为我把它放在一个条件下,我将位图中的所有点按质量分类并留给读者来过滤从同一个簇中删除点的列表.

然后在考虑这一步时,我发现解决方案并没有像我想象的那样跳出来.所以现在我要求你们帮忙.我们有一个像这样的质量点的列表(一个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)

请注意,列表在此处排序.如果您的解决方案更喜欢不对它们进行排序,那就完全没问题了.

如果你还记得,那么挑战就是找到主要的质量集群.群集的数量尚不清楚.但是你知道位图的尺寸.有时,群集中的多个点的质量大于下一个(大小)群集的中心.所以我想做的是从更高质量的点开始并移除同一簇中的点(附近的点).

当我尝试这个时,我最终不得不一遍又一遍地浏览列表的一部分.我有一种感觉,我只是愚蠢.你会怎么做？伪代码或真实代码.当然,如果你能用Python代码从我离开的那个地方起飞,我就更容易进行实验.

下一步是弄清楚位图中确实有多少个簇.我仍然在努力定义这个问题所以我可能会回答一个问题.

编辑:我应该澄清,我知道这个问题没有"正确"的答案.问题的名称是关键.完成了我的聚类的第一阶段.我正在寻找一种快速,准确 - "足够"的方法来过滤掉附近的点.

如果你知道如何让问题更清楚,请告诉我.

你知道,你要求解决一个不适定的问题:没有明确的解决方案.那很好......它只是让它变得更有趣.您的问题不合适主要是因为您不知道您想要多少个群集.聚类是机器学习的关键领域之一,多年来已经开发了很多方法.

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

K均值聚类基本上是最简单的混合模型.有时升级到通过期望最大化学习的高斯混合体(在刚刚给出的链接中描述)是有帮助的.这比k-means更强大.理解它需要花费更多的精力,但是当你这样做时,它并不比k-means更难实现.

还有许多其他聚类技术,如凝聚聚类和谱聚类.集合式集群很容易实现,但选择何时停止构建集群可能会非常棘手.如果您进行凝聚聚类,您可能希望查看kd树以获得更快的最近邻搜索.smacl的答案描述了使用Voronoi图进行凝聚聚类的一种略微不同的方法.

有些模型可以自动为您选择聚类数量,例如基于Latent Dirichlet Allocation的聚类数量,但是正确理解工具要困难得多.

您可能还想查看均值平移算法,看它是否更接近您真正想要的.