Kmeans

作者: 小幸运Q | 来源:发表于2019-12-11 16:24 被阅读0次

    K-means与kNN虽然都是以k打头,但却是两类算法——kNN为监督学习中的分类算法,而k-means则是非监督学习中的聚类算法;二者相同之处:均利用近邻信息来标注类别,都需要提前得知有多少种类。

    • 步骤:

    先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了,每个聚类的聚类中心会根据聚类中现有的对象被重新计算(利用簇重心调整聚类中心)。这个过程将不断重复直到满足某个终止条件。终止条件可以是以下任何一个:
    1)没有(或最小数目)对象被重新分配给不同的聚类。
    2)没有(或最小数目)聚类中心再发生变化。
    3)误差平方和局部最小。


    • 误差函数:

    以平方误差和(sum of the squared error, SSE)作为聚类的目标函数,同时也可以衡量不同聚类结果好坏的指标:
    SSE=\sum\limits_{i=1}^{k} \sum_{x\in C_{i}} dist(x, c_i)

    image.png

    缺点:

    k-means是局部最优的,容易受到初始质心的影响;比如在下图中,因选择初始质心不恰当而造成次优的聚类结果(SSE较大):

    image.png

    同时,k值的选取也会直接影响聚类结果,最优聚类的k值应与样本数据本身的结构信息相吻合,而这种结构信息是很难去掌握,因此选取最优k值是非常困难的。


    解决方法:

    为了解决上述存在缺点,在基本k-means的基础上发展而来二分 (bisecting) k-means,其主要思想:一个大cluster进行分裂后可以得到两个小的cluster;为了得到k个cluster,可进行k-1次分裂。算法流程如下:

    初始只有一个cluster包含所有样本点;
    repeat:
        从待分裂的clusters中选择一个进行二元分裂,所选的cluster应使得SSE最小;
    until 有k个cluster
    

    上述算法流程中,为从待分裂的clusters中求得局部最优解,可以采取暴力方法:依次对每个待分裂的cluster进行二元分裂(bisect)以求得最优分裂。二分k-means算法聚类过程如图:

    image.png

    相关文章

      网友评论

          本文标题:Kmeans

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