初始聚类中心的选择对k-means算法的效果有非常显著的影响,不合适的初始聚类中心可能导致:
1,算法收敛速度降低
2,更大的可能使聚类结果收敛到一个较差的局部最小值
3,某些簇最后是个空集(样本量较小时这种情况经常出现)
经典的k-means算法的初始聚类中心是随机选取的,这种方式有两种不足:
1,某些初始聚类中心可能离群体太远,如下图
2,有的聚类中心可能相互之间隔得太近
为了克服这些缺点,比较流行的方法是maxmin法,即:
首先随机选择一个点作为第一个初始类簇中心点,然后选择距离该点最远的那个点作为第二个初始类簇中心点,然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点,以此类推,直至选出K个初始类簇中心点。网上介绍的大部分是这个方法。http://www.sciencedirect.com/science/article/pii/S0957417412008767更推荐其他更好的方法,今天介绍其中一个。
step1:将从数据集中抽取J个较小的子集
step2:利用经典的k-means算法(随机选择初始聚类中心)对
step3:
step4:分别以CM_i为初始聚类中心,再次利用经典的k-means算法对
step5:计算
感兴趣的可以去看原文,地址:https://xue.glgoo.org/scholar?hl=zh-CN&as_sdt=0%2C5&q=Refining+Initial+Points+for+K-Means+Clustering&btnG=