我在很多 K-means 实现中看到过,比如 VLFeat k-means或 OpenCV k-means ,基本上有两种选择起始质心的方法:
- 随机
- 在 K-Means++ 之后算法
但是,我不知道在哪些情况下哪个更好,尤其是因为启动方法被认为很重要。你能帮我理解这一点吗?
最佳答案
理论上,k-means++ 要好得多。它是一种偏向随机抽样,更喜欢彼此距离较远的点,并避免接近的点。随机初始化可能不吉利,选择附近的中心。
因此从理论上讲,k-means++ 应该需要更少的迭代次数,并且更有可能找到全局最优值。
但是,k-means++ 并非完全“免费”,在我的实验中,我没有发现两者与更高级的 k-means 算法之间有任何系统差异。 k-means++ 需要 O(k n) 计算——大约一次完整迭代的成本。但是有改进的 k-means 算法,其迭代次数远少于此。使用这些算法,k-means++ 可能花费总运行时间的 10-20%(教科书 k-means 通常不到 1%)。
我想我现在更喜欢简单的随机初始化,尝试多次,每次尝试 10 次迭代以优化样本,然后只用最好的继续。
关于algorithm - k-means++ vs 初始中心随机,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38497982/