从d最近的聚类中心到n个点集的k

Question

我有一组'n‘数据点和'd’可能的聚类中心，这些都是先验已知的。我需要从这些'd‘聚类中心中选择“最佳”'k’(值'k‘也已知)，以便在这些'k’聚类中心上对'n‘数据点进行聚类，从而得到最小的总累积距离。

此外，与每个k选择的集群相关联的数据点的数量应该是软平衡的，但这不是硬要求。

我认为的一个近似解是首先对数据点进行盲目聚类(例如，高斯混合聚类和聚类数= k)，然后选择k个已知的聚类中心，使它们与GM聚类经验发现的聚类中心的累积距离最小化。或者，当然，总是有蛮力的方法，尝试所有可能的组合，把k从d中心取出来，然后计算集合的累积距离。

参数的大小，如果这可以帮助：

• n~10^2
• d~10^1
• k~10^1

NOTE1:非最优但快速的解决方案是首选的，因为这应该接近实时运行.

NOTE2:我目前正在使用Python，但我不一定需要罐装解决方案

非常感谢!

Answer 1

这是一个在O(d^2)时间复杂度中运行的贪婪算法，在实践中具有良好的性能。我无法证明这是最优的(可能不是)。

设d聚类中心是我们将要构建的图的顶点。对于它们中的每一个，找到其最近的一个，通过一个边将它们连接起来，并更新两个顶点的程度。该过程具有O(d^2)时间复杂度。在结束时，您将有一个表示图的邻接列表，以及一个指示每个顶点的程度的数组。

将顶点放在优先级队列中(以上一张图中的度作为优先级标准)。现在，迭代地运行以下过程:从优先级队列的顶部获取元素。将其标记为从图形中取出，将其插入k最佳集群集合中，并降低其所有邻域的程度。如果k个最佳簇的集合有k个元素，就停止这个过程。否则，继续。此过程具有O(d log d)时间复杂度。在它的最后，您将有一个集与k最好的集群。