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

Question

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

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

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

K-means使用DP的思想简而言之如下:

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

我试图为它找到一个伪代码，这样我就可以尝试找出它的复杂性，但我找不到。

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

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

Answer 1

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

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

希望这对您有所帮助!