KMeans
KMeans是一种无监督学习聚类方法, 目的是发现数据中数据对象之间的关系，将数据进行分组，组内的相似性越大，组间的差别越大，则聚类效果越好。
无监督学习,也就是没有对应的标签,只有数据记录.通过KMeans聚类,可以将数据划分成一个簇,进而发现数据之间的关系.
[图片上传失败...(image-fa9971-1543240223005)]
原理
KMeans算法是将数据聚类成k个簇,其中每个
, 算法具体描述:
- 随机选择k个聚类质心点:
;
- 重复下面过程直到收敛{
对于每一个数据i,计算其属于的簇:
;
对于每个簇j,重新计算簇质心:
}
用语言描述来说,就是:随机确定k个初始点作为簇中心; 为每个数据分配簇[计算每条数据和簇中心的相似度,分配到最相似的簇上];根据簇中的数据点对每个簇中心进行更新.反复重复直到收敛为止.
伪代码:
创建k个点作为起始质心;
当任意一个点的簇分配结果发生改变时:
对数据集中的每个数据点:
对每个质心:
计算质心和当前数据点的相似度
将数据点分配到最近的质心所代表的簇上
对于每个簇,计算簇中所有点的均值,并将均值作为新的簇中心[质心]
存在问题及其处理方法
- 必须事先给出k(要生成的簇的数目),而且对初值敏感，对于不同的初始值，可能会导致不同结果。
- 不适合于发现非凸面形状的簇或者大小差别很大的簇。
- 对于“躁声”和孤立点数据是敏感的，因为簇的中心是通过计算数据的平均值得到的，这些数据的存在会使聚类的中心发生很大的偏移;
- 容易陷入到局部最优解.
对于局部最优解的问题,一方面可以像决策树一样,对最后生成的聚类效果进行"剪枝"处理,但有所不同,因为要保证簇数目不变,所有处理进行"剪枝处理"外,还需要"增枝处理",具体可以依据某种指标[SSE sum of square errors]选择指标最大的簇尝试划分, 然后选择两个进行合并,保证簇的数目不变.
另一方面,可以对kmeans进行优化处理,存在一种二分kMeans处理.
二分k均值:首先将所有数据看成一个簇,然后将该簇一分为二,之后选择其中一个簇继续划分, 如何选择簇取决于对其划分是否可以最大程度的降低SSE的值;然后反复重复,直到得到K个簇为止.
代码实现
github地址: repository
