Kmeans
基本原理
K-Mmeans算法使用贪心策略求得一个近似解,具体步骤如下:
- 在样本中随机选取k个样本点充当各个簇的中心点
[u_{1},u_{2}...u_{k}
]
- 计算所有样本点与各个簇中心之间的距离
[dist(x^{(i)},u_{i})
]
,然后把样本点划入最近的簇中
[x^{(i)}in u^{_{nearest}}
]
- 根据簇中已有的样本点,重新计算簇中心
[u_{i}: = frac{1}{left | c_{i}
ight |} sum_{xin C_{i}}x
]
- 重复2、3
K-means算法得到的聚类结果严重依赖与初始簇中心的选择,如果初始簇中心选择不好,就会陷入局部最优解,避免这种情况的简单方法是重复多次运行K-means算法,然后取一个平均结果。
Kmeans++
K-means算法初始中心点的选取,改进后的选取流程如下:
-
在数据集中随机选取一个样本点作为第一个簇中心C1
-
计算剩余样本点与已有聚类中心之间的最短距离(即与最近一个聚类中心的距离)
[D(x^{(i)})=min[dist(x^{(i)},C_{1}),dist(x^{(i)},C_{2}),...,dist(x^{(i)},C_{n})] ]计算每个样本被选为下一个聚类中心的概率:
[frac{D(x^{(i)})^{2}}{sum _{j in X } D(x^{(j)})} ] -
重复步骤二,知道选出 k 个聚类中心。
效率
K-means++ 能显著的改善分类结果的最终误差。
尽管计算初始点时花费了额外的时间,但是在迭代过程中,k-mean 本身能快速收敛,因此算法实际上降低了计算时间。
网上有人使用真实和合成的数据集测试了他们的方法,速度通常提高了 2 倍,对于某些数据集,误差提高了近 1000 倍。