KMeans聚类算法

作者: 七八音 | 来源:发表于2018-11-26 21:50 被阅读8次

    KMeans

    KMeans是一种无监督学习聚类方法, 目的是发现数据中数据对象之间的关系,将数据进行分组,组内的相似性越大,组间的差别越大,则聚类效果越好。

    无监督学习,也就是没有对应的标签,只有数据记录.通过KMeans聚类,可以将数据划分成一个簇,进而发现数据之间的关系.

    [图片上传失败...(image-fa9971-1543240223005)]

    原理

    KMeans算法是将数据{x^1, x^2 ,..., x^n}聚类成k个簇,其中每个x^i \in R^n, 算法具体描述:

    1. 随机选择k个聚类质心点:\mu_1, \mu_2, ..., \mu_k;
    2. 重复下面过程直到收敛{
      对于每一个数据i,计算其属于的簇:
      c^{(i)} := argmin_j||x^{(i)}-\mu_j||^2;
      对于每个簇j,重新计算簇质心:
      \mu_j=\frac{\sum_{i=1}^n1{(c^i==j)}x^i}{\sum_{i=1}^n1{(c^{(i)}=j)}}
      }

    用语言描述来说,就是:随机确定k个初始点作为簇中心; 为每个数据分配簇[计算每条数据和簇中心的相似度,分配到最相似的簇上];根据簇中的数据点对每个簇中心进行更新.反复重复直到收敛为止.

    伪代码:

    创建k个点作为起始质心;
    当任意一个点的簇分配结果发生改变时:
        对数据集中的每个数据点:
            对每个质心: 
                计算质心和当前数据点的相似度 
            将数据点分配到最近的质心所代表的簇上 
        对于每个簇,计算簇中所有点的均值,并将均值作为新的簇中心[质心]
    

    存在问题及其处理方法

    • 必须事先给出k(要生成的簇的数目),而且对初值敏感,对于不同的初始值,可能会导致不同结果。
    • 不适合于发现非凸面形状的簇或者大小差别很大的簇。
    • 对于“躁声”和孤立点数据是敏感的,因为簇的中心是通过计算数据的平均值得到的,这些数据的存在会使聚类的中心发生很大的偏移;
    • 容易陷入到局部最优解.

    对于局部最优解的问题,一方面可以像决策树一样,对最后生成的聚类效果进行"剪枝"处理,但有所不同,因为要保证簇数目不变,所有处理进行"剪枝处理"外,还需要"增枝处理",具体可以依据某种指标[SSE sum of square errors]选择指标最大的簇尝试划分, 然后选择两个进行合并,保证簇的数目不变.

    另一方面,可以对kmeans进行优化处理,存在一种二分kMeans处理.

    二分k均值:首先将所有数据看成一个簇,然后将该簇一分为二,之后选择其中一个簇继续划分, 如何选择簇取决于对其划分是否可以最大程度的降低SSE的值;然后反复重复,直到得到K个簇为止.

    代码实现

    github地址: repository

    相关文章

      网友评论

        本文标题:KMeans聚类算法

        本文链接:https://www.haomeiwen.com/subject/msbiqqtx.html