php - 有效地对节点进行分组？

Question

虽然大多数问题都是关于基于相似性（pidgeonholes）对节点进行分组，但我想仅根据节点的接近程度对节点进行分组。

我有大量密集的节点集合——可能有数百万。在屏幕上，它们占据了一定的空间，因此可以认为它们具有大小。

我要做的是将这些节点有效地分组为单个包含节点，无论是在处理时间还是在每个容器收集更多节点方面。

我目前的尝试要么太慢，要么不起作用，但都是基于我想到的相同解决方案：通过随机获取一个节点及其周围的节点并将它们分组来计算很多可能的容器，然后选择最有效的容器。

你的想法是什么，不是特别用任何语言，但我将为此使用 PHP 或 JavaScript。

Edit

我忘了提到节点将被流式传输，因此它需要接受无限的节点，将它们放入容器中，创建新容器甚至根据需要删除它们，最多可容纳数百万个容器。那将是最理想的。

score 1 · Accepted Answer

这个问题称为聚类。您有一组节点和一个m计算任意两个节点之间距离的函数。您现在搜索集群，以使每个集群内所有节点之间的所有距离之和最小。

有一些简单的算法可以做到这一点。搜索k-Means和k-Medoid例如。这两个与您的方法非常相似。更有效的版本是CLARANS算法 [NH94]。我没有为你找到任何好的资源，但你去：

名称中的“k”是集群的数量。对于这 3 种算法，您必须先验地指定集群的数量。

对于不同的方法，请参阅DBSCAN算法。您不需要此算法的集群数量，但您必须提供有关节点的其他一些知识。维基百科文章很好地解释了这一点。:-)

1 回答 1