algorithm - 动态规划复杂性中的k-means？

Question

我们都知道 k-means 算法：它的复杂度为O( n * K * I * d ) 其中：

1. n = 点数
2. K = 聚类数
3. I = 迭代次数
4. d = 属性数

但我的问题是在动态编程中应用 K-means 时，我无法弄清楚它的复杂性。

简而言之，使用DP的 K-means 的想法如下：

• 计算邻近矩阵
• 让每个数据点成为一个簇
• 重复
  • 合并两个最近的集群
  • 更新邻近矩阵
• 直到只剩下一个集群

我试图为它找到一个伪代码，以便我可以尝试找出复杂性，但我做不到。

那么，我怎样才能找到它的复杂性呢？它可能是什么？

提前谢谢你们的任何回答。

Answer 1

您描述的算法不是具有动态编程的 k-means，而是一种称为凝聚聚类 的层次聚类。通常，凝聚聚类实现需要时间 (IIRC) O(n ³ d)，其中 n 是数据点的数量，d 是特征的数量。维基百科更深入地介绍了它的工作原理。

请注意，以这种方式找到的集群与您使用 k-means 获得的集群不同。凝聚聚类倾向于产生具有不同属性集的非常不同的聚类。

希望这可以帮助！