k-means++算法在以下两个方面能够帮助原始的k-means算法:
- 原始的k-means算法在输入数据规模上存在超多项式的最坏运行时间,而k-means++声称其为O(log k)。
- 相对于最优聚类,找到的近似结果可能会导致目标函数表现不太理想。
但是,k-means++有什么缺点呢?我们应该总是使用它来替代k-means吗?
k-means++算法在以下两个方面能够帮助原始的k-means算法:
但是,k-means++有什么缺点呢?我们应该总是使用它来替代k-means吗?
虽然不是你的问题,但是对于大型数据集,任何kmeans方法都可以进行简单的加速:
1)首先在sqrt(N)个点的随机样本上运行k-means
2)然后从这些中心运行完整的k-means。
我发现对于N 10000、k 20的情况,与kmeans++相比,这种方法快5-10倍,并且结果相似。它的有效性取决于sqrt(N)样本是否能够近似整体,以及N、dim、k、ninit、delta等因素...
你的N(数据点数)、dim(特征数)和k是多少?
用户N、dim、k、数据噪声、度量标准等范围巨大...更不用说缺乏公共基准,使得比较方法变得困难。
附加:Python代码kmeans()和kmeanssample()在SO上这里,欢迎评论。