k-means 订阅
k均值聚类算法(k-means clustering algorithm)是一种迭代求解的聚类分析算法,其步骤是,预将数据分为K组,则随机选取K个对象作为初始的聚类中心,然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本,聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小。 展开全文
k均值聚类算法(k-means clustering algorithm)是一种迭代求解的聚类分析算法,其步骤是,预将数据分为K组,则随机选取K个对象作为初始的聚类中心,然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本,聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小。
信息
提出时间
1967年
提出者
James MacQueen
类    型
聚类算法
中文名
K均值聚类算法
应    用
数据分析,信号处理,机器学习
外文名
k-means clustering algorithm
K均值聚类算法定义
聚类是一个将数据集中在某些方面相似的数据成员进行分类组织的过程,聚类就是一种发现这种内在结构的技术,聚类技术经常被称为无监督学习。k均值聚类是最著名的划分聚类算法,由于简洁和效率使得他成为所有聚类算法中最广泛使用的。给定一个数据点集合和需要的聚类数目k,k由用户指定,k均值算法根据某个距离函数反复把数据分入k个聚类中。
收起全文
精华内容
下载资源
问答
  • K-Means 系列:K-Means,二分K-MeansK-Means++,K-Meansll,canopy算法,MiniBatchK-Means算法。 K-Means系列聚类算法原理:https://www.cnblogs.com/pinard/p/6164214.html 用scikit-learn学习K-Means聚类:...

    K-Means 系列:K-Means,二分K-Means,K-Means++,K-Meansll,canopy算法,MiniBatchK-Means算法。

     

    K-Means系列聚类算法原理: https://www.cnblogs.com/pinard/p/6164214.html

    用scikit-learn学习K-Means聚类https://www.cnblogs.com/pinard/p/6169370.html

    • 一个是传统的K-Means算法,对应的类是KMeans。
    • 另一个是基于采样的Mini Batch K-Means算法

    聚类算法 一句话概括:

    • K-means:(1)初始化K个类别中心,(2)用样本均值更新类别中心
    • 二分K-means:不断选择较大的簇,用k-means一分为二
    • K-means++:任选一个节点为第一个簇中心,然后依次选择距离已有簇较远的点为下一个簇中心。
    • Canopy:列表获取节点,根据大小圈,判断是否属于某一个簇,不属于就新建一个簇。
    • Mini-Batch-K-means:采样一部分样本用k-means进行聚类,然后不断批量添加新样本,对簇中心进行更新。

    面试题:

    (1)K-means 和KNN 的区别:

    k-means是聚类(无监督学习),先定好k个类别,然后随机确定k个坐标(聚类中心),各点离哪个坐标近就算做哪类,然后不停算平均值求出中心,直到稳定,聚类完成。有训练的过程。
    knn = k nearest neighbor是分类(监督学习),定好k直接把待分类点周边最近的k个点计数,数量多的那类定为待分类点的类别。无训练的过程。Ref:https://blog.csdn.net/Saphon/article/details/98357271

     

    一、传统K-Means算法

    1. 步骤

    2. 优缺点

    二、K-Means算法衍生

    1、二分k-means算法

      二分k-means算法是分层聚类(Hierarchical clustering)的一种,分层聚类是聚类分析中常用的方法。
    分层聚类的策略一般有两种:

    • 聚合。这是一种自底向上的方法,每一个观察者初始化本身为一类,然后两两结合
    • 分裂。这是一种自顶向下的方法,所有观察者初始化为一类,然后递归地分裂它们

      二分k-means算法是分裂法的一种。

    (1)优点:

        二分k-means算法是k-means算法的改进算法,解决K-Means算法对初始簇心比较敏感的问题,二分K-Means算法是一种弱化初始质心的一种算法,相比k-means算法,它有如下优点:

    • 二分k-means算法可以加速k-means算法的执行速度,因为它的相似度计算少了???
    • 能够克服k-means收敛于局部最小的缺点

    (2)思路步骤:

    • 将所有样本数据作为一个簇放到一个队列中。
    • 从队列中选择一个簇进行K-means算法划分,划分为两个子簇,并将子簇添加到队列中。
    • 循环迭代第二步操作,直到中止条件达到(聚簇数量、最小平方误差、迭代次数等)。
    • 队列中的簇就是最终的分类簇集合。

    从队列中选择划分聚簇的规则一般有两种方式;分别如下:

    • 对所有簇计算误差和SSE(SSE也可以认为是距离函数的一种变种),选择SSE最大的聚簇进行划分操作(优选这种策略)。
    • 选择样本数据量最多的簇进行划分操作:

      以上过程隐含着一个原则是:因为聚类的误差平方和能够衡量聚类性能,该值越小表示数据点越接近于它们的质心,聚类效果就越好。
    所以我们就需要对误差平方和最大的簇进行再一次的划分,因为误差平方和越大,表示该簇聚类越不好,越有可能是多个簇被当成一个簇了,所以我们首先需要对这个簇进行划分。

    (3) 二分k-means的源码分析

    参考: https://blog.csdn.net/BaiHuaXiu123/article/details/54883099

               https://www.jianshu.com/p/f0727880c9c0

    2、K-Means++算法

    解决K-Means算法对初始簇心比较敏感的问题,K-Means++算法和K-Means算法的区别主要在于初始的K个中心点的选择方面,K-Means算法使用随机给定的方式,K-Means++算法采用下列步骤给定K个初始质点:

    1、从数据集中任选一个节点作为第一个聚类中心。
    2、对数据集中的每个点x,计算x到所有已有聚类中心点的距离和D(X),基于D(X)采用线性概率选择出下一个聚类中心点(距离较远的一个点成为新增的一个聚类中心点)。
    3、重复步骤2直到找到k个聚类中心点。

    缺点:由于聚类中心点选择过程中的内在有序性,在扩展方面存在着性能方面的问题(第k个聚类中心点的选择依赖前k-1个聚类中心点的值)

    另一种选择簇中心的方法: https://www.cnblogs.com/pinard/p/6164214.html

           虽然k-means++算法可以确定地初始化聚类中心,但是从可扩展性来看,它存在一个缺点,那就是它内在的有序性特性:得到 k 个聚类中心必须遍历数据集 k 次,下一个中心点的选择依赖于已经选择的中心点。 针对这种缺陷,k-means||算法提供了解决方法。

    3、K-Means||算法 ()

    解决K-Means++算法缺点而产生的一种算法;主要思路是改变每次遍历时候的取样规则,并非按照K-Means++算法每次遍历只获取一个样本,而是每次获取K个样本,重复该取样操作O(logn)次(n是样本的个数),然后再将这些抽样出来的样本聚类出K个点,最后使用这K个点作为K-Means算法的初始聚簇中心点。实践证明:一般5次重复采用就可以保证一个比较好的聚簇中心点。

    梳理步骤:

    • 1、在N个样本中抽K个样本,一共抽logn次,形成一个新的样本集,一共有Klogn个数据。
    • 2、在新数据集中使用K-Means算法,找到K个聚簇中心。
    • 3、把这K个聚簇中心放到最初的样本集中,作为初始聚簇中心。
    • 4、原数据集根据上述初始聚簇中心,再用K-Means算法计算出最终的聚簇。

    4、Canopy算法

    (1)步骤:Canopy算法属于一种“粗”聚类算法,执行速度较快,但精度较低,算法执行步骤如下:

    • 1、给定样本列表L=x1,x,2...,xm以及先验值r1和r2(r1>r2);(先验值 - 自己猜的,人为定义的值)
    • 2、从列表L中获取一个节点P,计算P到所有聚簇中心点的距离(如果不存在聚簇中心,那么此时点P形成一个新的聚簇),并选择出最小距离D(P,aj);
    • 3、如果距离D小于r1,表示该节点属于该聚簇,添加到该聚簇列表中。
    • 4、如果距离D小于r2,表示该节点不仅仅属于该聚簇,还表示和当前聚簇中心点非常近,所以将该聚簇的中心点设置为P,并将P从列表L中删除。
    • 5、如果距离D大于r1,那么节点P形成一个新的聚簇。
    • 6、直到列表L中的元素数据不再有变化或者元素数量为0的时候,结束循环操作。

       Canopy算法得到的最终结果的值,聚簇之间是可能存在重叠的,但是不会存在某个对象不属于任何聚簇的情况。

    (2)Canopy算法常用应用场景:

    由于K-Means算法存在初始聚簇中心点敏感的问题,常用使用Canopy+K-Means算法混合形式进行模型构建。
    1、先使用canopy算法进行“粗”聚类得到K个聚类中心点。
    2、K-Means算法使用Canopy算法得到的K个聚类中心点作为初始中心点,进行“细”聚类。

    (3)优缺点:
    1、执行速度快(先进行了一次聚簇中心点选择的预处理);
    2、不需要给定K值,应用场景多。
    3、能够缓解K-Means算法对于初始聚类中心点敏感的问题。

    5、Mini Batch K-Means

    Mini Batch K-Means算法是K-Means算法的一种优化变种,采用小规模的数据子集(每次训练使用的数据集是在训练算法的时候随机抽取的数据子集)减少计算时间,同时试图优化目标函数;Mini Batch K-Means算法可以减少K-Means算法的收敛时间,而且产生的结果效果只是略差于标准K-Means算法。

    算法步骤如下:
    1、首先抽取部分数据集,使用K-Means算法构建出K个聚簇点的模型。
    2、继续抽取训练数据集中的部分数据集样本数据,并将其添加到模型中,分配给距离最近的聚簇中心点。
    3、更新聚簇的中心点值。
    4、循环迭代第二步和第三步操作,直到中心点稳定或者达到迭代次数,停止计算操作。

     

    参考: https://blog.csdn.net/weixin_33726318/article/details/89588860


     

    展开全文
  • K-Means 二维数据 聚类分析 数据样本及聚类要求 二维数据曼哈顿距离计算 K-Means 算法 步骤 第一次迭代 : 步骤 ( 1 ) 中心点初始化 第一次迭代 : 步骤 ( 2 ) 计算距离 第一次迭代 : 步骤 ( 3 ) 聚类分组 第二次迭代 ...



    K-Means 二维数据 聚类分析 数据样本及聚类要求



    数据样本及聚类要求 :


    ① 数据样本 : 数据集样本为 66 个点 , A1(2,4)A_1 ( 2 , 4 ) , A2(3,7)A_2 ( 3 , 7 ) , B1(5,8)B_1 ( 5 , 8 ) , B2(9,5)B_2 ( 9 , 5 ) , C1(6,2)C_1 ( 6 , 2 ) , C2(4,9)C_2 ( 4 , 9 ) ;

    ② 聚类个数 : 分为 33 个聚类 ;

    ③ 距离计算方式 : 使用 曼哈顿距离 , 计算样本之间的相似度 ; 曼哈顿距离的计算方式是 两个维度的数据差绝对值 相加 ;

    ④ 中心点初始值 : 选取 A1,B1,C1A_1 , B_1 , C_1 三个样本为聚类的初始值 , 这是实点 ; 如果选取非样本的点作为初始值 , 就是虚点 ;

    ⑤ 要求 : 使用 K-Means 算法迭代 22 次 ;

    ⑥ 中心值精度 : 计算过程中中心值小数向下取整 ;



    二维数据曼哈顿距离计算



    1 . 曼哈顿距离 公式如下 :


    d(i,j)=xi1xj1+xi2xj2++xipxjpd(i, j) = | x_{i1} - x_{j1} | + | x_{i2} - x_{j2} | + \cdots + | x_{ip} - x_{jp} |


    d(i,j)d(i, j) 表示两个样本之间的距离 , 曼哈顿距离 ;

    pp 表示属性的个数 , 每个样本有 pp 个属性 ;

    iijj 表示两个 样本的索引值 , 取值范围是 {1,2,,q}\{1 , 2, \cdots , q\} ;

    xipxjpx_{ip} - x_{jp} 表示两个样本 第 pp 个属性值 的差值 , xi1xj1x_{i1} - x_{j1} 表示两个样本 第 11 个属性值 的差值 , xi2xj2x_{i2} - x_{j2} 表示两个样本 第 22 个属性值 的差值 ;


    2 . 曼哈顿距离图示 : 曼哈顿的街道都是横平竖直的 , 从 AA 点到 BB 点 , 一般就是其 xx 轴坐标差 加上其 yy 轴坐标差 , 即 x+yx + y ;

    在这里插入图片描述


    3 . 本题目中的样本距离计算示例 : 两个样本的曼哈顿距离是 xx 属性差的绝对值 , 加上 yy 属性差的绝对值 , 之和 ;


    计算 A1(2,4)A_1 ( 2 , 4 ) , A2(3,7)A_2 ( 3 , 7 ) 的距离 :


    d(A1,A2)=23+47=4d(A_1 , A_2) = | 2 - 3 | + |4 - 7| = 4


    A1A_1 样本与 A2A_2 样本之间的距离是 44 ;



    K-Means 算法 步骤



    K-Means 算法 步骤 : 给定数据集 XX , 该数据集有 nn 个样本 , 将其分成 KK 个聚类 ;


    ① 中心点初始化 : KK 个聚类分组选择初始的中心点 , 这些中心点称为 Means ; 可以依据经验 , 也可以随意选择 ;

    ② 计算距离 : 计算 nn 个对象与 KK 个中心点 的距离 ; ( 共计算 n×Kn \times K 次 )

    ③ 聚类分组 : 每个对象与 KK 个中心点的值已计算出 , 将每个对象分配给距离其最近的中心点对应的聚类 ;

    ④ 计算中心点 : 根据聚类分组中的样本 , 计算每个聚类的中心点 ;

    ⑤ 迭代直至收敛 : 迭代执行 ② ③ ④ 步骤 , 直到 聚类算法收敛 , 即 中心点 和 分组 经过多少次迭代都不再改变 , 也就是本次计算的中心点与上一次的中心点一样 ;



    第一次迭代 : 步骤 ( 1 ) 中心点初始化



    初始化中心点 : 33 个聚类的中心点 , 在题目中已经给出 ;


    ① 聚类 11 中心点 : A1(2,4)A_1 ( 2 , 4 ) ;

    ② 聚类 22 中心点 : B1(5,8)B_1 ( 5 , 8 ) ;

    ③ 聚类 33 中心点 : C1(6,2)C_1 ( 6 , 2 ) ;



    第一次迭代 : 步骤 ( 2 ) 计算距离



    距离计算次数 : 这里需要计算所有的样本 , 与所有的中心点的距离 , 每个样本都需要计算与 33 个中心点的距离 , 共需要计算 6×3=186 \times 3 = 18 次 ;


    数据样本 : A1(2,4)A_1 ( 2 , 4 ) , A2(3,7)A_2 ( 3 , 7 ) , B1(5,8)B_1 ( 5 , 8 ) , B2(9,5)B_2 ( 9 , 5 ) , C1(6,2)C_1 ( 6 , 2 ) , C2(4,9)C_2 ( 4 , 9 )




    1 . 计算 A1(2,4)A_1 ( 2 , 4 ) 与 三个中心点 {A1,B1,C1}\{ A_1 , B_1 , C_1 \} 之间的距离 :


    A1(2,4)A_1 ( 2 , 4 )A1(2,4)A_1 ( 2 , 4 ) 的距离 : ( 最小 )

    d(A1,A1)=22+44=0d(A_1 , A_1) = | 2-2 | + | 4-4 | = 0


    A1(2,4)A_1 ( 2 , 4 )B1(5,8)B_1 ( 5 , 8 ) 的距离 :

    d(A1,B1)=25+48=7d(A_1 , B_1) = | 2-5 | + | 4-8 | = 7


    A1(2,4)A_1 ( 2 , 4 )C1(6,2)C_1 ( 6 , 2 ) 的距离 :

    d(A1,C1)=26+42=6d(A_1 , C_1) = | 2-6 | + | 4-2 | = 6


    A1(2,4)A_1 ( 2 , 4 )A1(2,4)A_1 ( 2 , 4 ) 的距离最小 ;



    2 . 计算 A2(3,7)A_2 ( 3 , 7 ) 与 三个中心点 {A1,B1,C1}\{ A_1 , B_1 , C_1 \} 之间的距离 :


    A2(3,7)A_2 ( 3 , 7 )A1(2,4)A_1 ( 2 , 4 ) 的距离 :

    d(A2,A1)=32+74=4d(A_2 , A_1) = | 3-2 | + | 7-4 | = 4


    A2(3,7)A_2 ( 3 , 7 )B1(5,8)B_1 ( 5 , 8 ) 的距离 : ( 最小 )

    d(A2,B1)=35+78=3d(A_2 , B_1) = | 3-5 | + | 7-8 | = 3


    A2(3,7)A_2 ( 3 , 7 )C1(6,2)C_1 ( 6 , 2 ) 的距离 :

    d(A2,C1)=36+72=8d(A_2 , C_1) = | 3-6 | + | 7-2 | = 8


    A2(3,7)A_2 ( 3 , 7 )B1(5,8)B_1 ( 5 , 8 ) 的距离最小 ;



    3 . 计算 B1(5,8)B_1 ( 5 , 8 ) 与 三个中心点 {A1,B1,C1}\{ A_1 , B_1 , C_1 \} 之间的距离 :


    B1(5,8)B_1 ( 5 , 8 )A1(2,4)A_1 ( 2 , 4 ) 的距离 :

    d(B1,A1)=52+84=7d(B_1 , A_1) = | 5 -2 | + | 8 -4 | = 7


    B1(5,8)B_1 ( 5 , 8 )B1(5,8)B_1 ( 5 , 8 ) 的距离 : ( 最小 )

    d(B1,B1)=55+88=0d(B_1 , B_1) = | 5 -5 | + | 8 -8 | = 0


    B1(5,8)B_1 ( 5 , 8 )C1(6,2)C_1 ( 6 , 2 ) 的距离 :

    d(B1,C1)=56+82=7d(B_1 , C_1) = | 5 -6 | + | 8 -2 | = 7


    B1(5,8)B_1 ( 5 , 8 )B1(5,8)B_1 ( 5 , 8 ) 的距离最小 ;



    4 . 计算 B2(9,5)B_2 ( 9 , 5 ) 与 三个中心点 {A1,B1,C1}\{ A_1 , B_1 , C_1 \} 之间的距离 :


    B2(9,5)B_2 ( 9 , 5 )A1(2,4)A_1 ( 2 , 4 ) 的距离 :

    d(B2,A1)=92+54=8d(B_2 , A_1) = | 9 -2 | + | 5 -4 | = 8


    B2(9,5)B_2 ( 9 , 5 )B1(5,8)B_1 ( 5 , 8 ) 的距离 :

    d(B2,B1)=95+58=7d(B_2 , B_1) = | 9 -5 | + | 5 -8 | = 7


    B2(9,5)B_2 ( 9 , 5 )C1(6,2)C_1 ( 6 , 2 ) 的距离 : ( 最小 )

    d(B2,C1)=96+52=6d(B_2 , C_1) = | 9 -6 | + | 5 -2 | = 6


    B2(9,5)B_2 ( 9 , 5 )C1(6,2)C_1 ( 6 , 2 ) 的距离最小 ;



    5 . 计算 C1(6,2)C_1 ( 6 , 2 ) 与 三个中心点 {A1,B1,C1}\{ A_1 , B_1 , C_1 \} 之间的距离 :


    C1(6,2)C_1 ( 6 , 2 )A1(2,4)A_1 ( 2 , 4 ) 的距离 :

    d(C1,A1)=62+24=6d(C_1 , A_1) = | 6 -2 | + | 2 -4 | = 6


    C1(6,2)C_1 ( 6 , 2 )B1(5,8)B_1 ( 5 , 8 ) 的距离 :

    d(C1,B1)=65+28=7d(C_1 , B_1) = | 6 -5 | + | 2 -8 | = 7


    C1(6,2)C_1 ( 6 , 2 )C1(6,2)C_1 ( 6 , 2 ) 的距离 : ( 最小 )

    d(C1,C1)=66+22=0d(C_1 , C_1) = | 6 -6 | + | 2 -2 | = 0


    C1(6,2)C_1 ( 6 , 2 )C1(6,2)C_1 ( 6 , 2 ) 的距离最小 ;



    6 . 计算 C2(4,9)C_2 ( 4 , 9 ) 与 三个中心点 {A1,B1,C1}\{ A_1 , B_1 , C_1 \} 之间的距离 :


    C2(4,9)C_2 ( 4 , 9 )A1(2,4)A_1 ( 2 , 4 ) 的距离 :

    d(C2,A1)=42+94=7d(C_2 , A_1) = | 4 -2 | + | 9 -4 | = 7


    C2(4,9)C_2 ( 4 , 9 )B1(5,8)B_1 ( 5 , 8 ) 的距离 : ( 最小 )

    d(C2,B1)=45+98=2d(C_2 , B_1) = | 4 -5 | + | 9 -8 | = 2


    C2(4,9)C_2 ( 4 , 9 )C1(6,2)C_1 ( 6 , 2 ) 的距离 :

    d(C2,C1)=46+92=9d(C_2 , C_1) = | 4 -6 | + | 9 -2 | = 9


    C2(4,9)C_2 ( 4 , 9 )B1(5,8)B_1 ( 5 , 8 ) 的距离最小 ;



    8 . 生成距离表格 : 将上面计算的内容总结到如下表格中 ;


    A1(2,4)A_1 ( 2 , 4 ) A2(3,7)A_2 ( 3 , 7 ) B1(5,8)B_1 ( 5 , 8 ) B2(9,5)B_2 ( 9 , 5 ) C1(6,2)C_1 ( 6 , 2 ) C2(4,9)C_2 ( 4 , 9 )
    A1(2,4)A_1 ( 2 , 4 ) 00 44 77 88 66 77
    B1(5,8)B_1 ( 5 , 8 ) 77 33 00 77 77 22
    C1(6,2)C_1 ( 6 , 2 ) 66 88 77 66 00 99


    第一次迭代 : 步骤 ( 3 ) 聚类分组



    1 . 聚类分组 : 根据计算出的 , 每个样本与 33 个中心点的距离 , 将样本划分到 距离该样本最近的中心点 对应的分组中 ;


    A1(2,4)A_1 ( 2 , 4 ) A2(3,7)A_2 ( 3 , 7 ) B1(5,8)B_1 ( 5 , 8 ) B2(9,5)B_2 ( 9 , 5 ) C1(6,2)C_1 ( 6 , 2 ) C2(4,9)C_2 ( 4 , 9 )
    A1(2,4)A_1 ( 2 , 4 ) 00 44 77 88 66 77
    B1(5,8)B_1 ( 5 , 8 ) 77 33 00 77 77 22
    C1(6,2)C_1 ( 6 , 2 ) 66 88 77 66 00 99

    2 . 根据表格中的距离 , 为每个样本分组 :


    A1(2,4)A_1 ( 2 , 4 ) 距离 A1(2,4)A_1 ( 2 , 4 ) 中心点最近 , 划分到 聚类 11 中 ;

    A2(3,7)A_2 ( 3 , 7 ) 距离 B1(5,8)B_1 ( 5 , 8 ) 中心点最近 , 划分到 聚类 22 中 ;

    B1(5,8)B_1 ( 5 , 8 ) 距离 B1(5,8)B_1 ( 5 , 8 ) 中心点最近 , 划分到 聚类 22 中 ;

    B2(9,5)B_2 ( 9 , 5 ) 距离 C1(6,2)C_1 ( 6 , 2 ) 中心点最近 , 划分到 聚类 33 中 ;

    C1(6,2)C_1 ( 6 , 2 ) 距离 C1(6,2)C_1 ( 6 , 2 ) 中心点最近 , 划分到 聚类 33 中 ;

    C2(4,9)C_2 ( 4 , 9 ) 距离 B1(5,8)B_1 ( 5 , 8 ) 中心点最近 , 划分到 聚类 22 中 ;


    3 . 最终的聚类分组为 :


    ① 聚类 11 : {A1}\{ A_1 \}

    ② 聚类 22 : {A2,B1,C2}\{ A_2 , B_1 , C_2 \}

    ③ 聚类 33 : {B2,C1}\{ B_2 , C_1 \}



    第二次迭代 : 步骤 ( 1 ) 中心点初始化



    A1(2,4)A_1 ( 2 , 4 ) , A2(3,7)A_2 ( 3 , 7 ) , B1(5,8)B_1 ( 5 , 8 ) , B2(9,5)B_2 ( 9 , 5 ) , C1(6,2)C_1 ( 6 , 2 ) , C2(4,9)C_2 ( 4 , 9 )

    1 . 聚类 11 中心点计算 : 计算 {A1(2,4)}\{ A_1 ( 2 , 4 ) \} 中心点


    1=(2,4)聚类 1 中心点 = ( 2 , 4 )


    2 . 聚类 22 中心点计算 : 计算 {A2(3,7),B1(5,8),C2(4,9)}\{ A_2 ( 3 , 7 ) , B_1 ( 5 , 8 ) , C_2( 4 , 9 ) \} 中心点


    2=(3+5+43,7+8+93)=(4,8)聚类 2 中心点 = ( \frac{3 + 5 + 4}{3} , \frac{7 + 8 + 9}{3}) = ( 4 , 8 )


    3 . 聚类 33 中心点计算 : 计算 {B2(9,5),C1(6,2)}\{ B_2( 9 , 5 ) , C_1 ( 6 , 2 ) \} 中心点


    3=(9+62,5+22)=(7,3)聚类 3 中心点 = ( \frac{9 + 6 }{2} , \frac{5 + 2}{2}) = ( 7 , 3 )




    第二次迭代 : 步骤 ( 2 ) 计算距离



    计算 66 个点 , 到 33 个中心点的距离 , 33 个中心点分别是 {(2,4),(4,8),(7,3)}\{ ( 2 , 4 ) , ( 4 , 8 ) , ( 7 , 3 ) \} , 直接将两个点的曼哈顿距离填在对应的表格中 ;


    如 : 第 11 行 , 第 22 列 :

    A1(2,4)A_1 ( 2 , 4 ) 样本 与 (4,8)( 4 , 8 ) 聚类 22 中心点的 曼哈顿距离 是 66 , 计算过程如下 :


    A1(2,4)(4,8)=24+48=6A_1 ( 2 , 4 ) 与 ( 4 , 8 ) 两点曼哈顿距离 = | 2 - 4 | + | 4 - 8 | = 6


    A1(2,4)A_1 ( 2 , 4 ) A2(3,7)A_2 ( 3 , 7 ) B1(5,8)B_1 ( 5 , 8 ) B2(9,5)B_2 ( 9 , 5 ) C1(6,2)C_1 ( 6 , 2 ) C2(4,9)C_2 ( 4 , 9 )
    (2,4)( 2 , 4 ) 00 44 77 88 66 77
    (4,8)( 4 , 8 ) 66 22 11 88 88 11
    (7,3)( 7 , 3 ) 66 88 77 44 22 99


    第二次迭代 : 步骤 ( 3 ) 聚类分组



    1 . 聚类分组 : 根据计算出的 , 每个样本与 33 个中心点的距离 , 将样本划分到 距离该样本最近的中心点 对应的分组中 ;


    A1(2,4)A_1 ( 2 , 4 ) A2(3,7)A_2 ( 3 , 7 ) B1(5,8)B_1 ( 5 , 8 ) B2(9,5)B_2 ( 9 , 5 ) C1(6,2)C_1 ( 6 , 2 ) C2(4,9)C_2 ( 4 , 9 )
    (2,4)( 2 , 4 ) 00 44 77 88 66 77
    (4,8)( 4 , 8 ) 66 22 11 88 88 11
    (7,3)( 7 , 3 ) 66 88 77 44 22 99

    2 . 根据表格中的距离 , 为每个样本分组 :


    A1(2,4)A_1 ( 2 , 4 ) 距离 (2,4)( 2 , 4 ) 中心点最近 , 划分到 聚类 11 中 ;

    A2(3,7)A_2 ( 3 , 7 ) 距离 (4,8)( 4 , 8 ) 中心点最近 , 划分到 聚类 22 中 ;

    B1(5,8)B_1 ( 5 , 8 ) 距离 (4,8)( 4 , 8 ) 中心点最近 , 划分到 聚类 22 中 ;

    B2(9,5)B_2 ( 9 , 5 ) 距离 (7,3)( 7 , 3 ) 中心点最近 , 划分到 聚类 33 中 ;

    C1(6,2)C_1 ( 6 , 2 ) 距离 (7,3)( 7 , 3 ) 中心点最近 , 划分到 聚类 33 中 ;

    C2(4,9)C_2 ( 4 , 9 ) 距离 (4,8)( 4 , 8 ) 中心点最近 , 划分到 聚类 22 中 ;


    3 . 最终的聚类分组为 :


    ① 聚类 11 : {A1}\{ A_1 \}

    ② 聚类 22 : {A2,B1,C2}\{ A_2 , B_1 , C_2 \}

    ③ 聚类 33 : {B2,C1}\{ B_2 , C_1 \}



    第二次迭代的聚类分组 , 与第一次迭代的聚类分组 , 没有改变 , 说明聚类算法分析结果已经收敛 , 该聚类结果就是最终的结果 ;



    K-Means 迭代总结




    1 . 第一次迭代 :


    ① 设置中心点 : 设置了 33 个初始中心点 , A1(2,4)A_1 ( 2 , 4 ) 对应聚类 11 中心点 , B1(5,8)B_1 ( 5 , 8 ) 对应聚类 22 中心点 , C1(6,2)C_1 ( 6 , 2 ) 对应聚类 33 中心点 ;

    ② 计算中心点距离 : 然后就算 66 个样本距离这 33 个中心点的距离 ;

    ③ 根据距离聚类分组 : 每个样本取距离最近的 11 个中心点 , 将该样本分类成该中心点对应的聚类分组 , 聚类分组结果是 , 聚类 11 : {A1}\{ A_1 \} , 聚类 22 : {A2,B1,C2}\{ A_2 , B_1 , C_2 \} , 聚类 33 : {B2,C1}\{ B_2 , C_1 \} ;



    2 . 第二次迭代 :


    ① 计算中心点 : 根据第一次迭代的聚类分组结果计算 33 个中心点 , (2,4)( 2 , 4 ) 对应聚类 11 中心点 , $( 4 , 8 ) $ 对应聚类 22 中心点 , (7,3)( 7 , 3 ) 对应聚类 33 中心点 ;

    ② 计算中心点距离 : 然后就算 66 个样本距离这 33 个中心点的距离 ;

    ③ 根据距离聚类分组 : 每个样本取距离最近的 11 个中心点 , 将该样本分类成该中心点对应的聚类分组 , 聚类分组结果是 , 聚类 11 : {A1}\{ A_1 \} , 聚类 22 : {A2,B1,C2}\{ A_2 , B_1 , C_2 \} , 聚类 33 : {B2,C1}\{ B_2 , C_1 \} ;



    3 . 最终结果 : 经过 22 次迭代 , 发现 , 根据最初选择中心点 , 进行聚类分组的结果 , 就是最终的结果 , 迭代 22 次的分组结果相同 , 说明聚类算法已经收敛 , 此时的聚类结果就是最终结果 , 聚类算法终止 ;



    K-Means 初始中心点选择方案



    1 . 初始中心点选择 :


    ① 初始种子 : 初始的中心点 , 又称为种子 , 如果种子选择的好 , 迭代的次数就会非常少 , 迭代的最少次数为 22 , 如上面的示例 ;

    ② 种子选择影响 : 初始种子选择的好坏 , 即影响算法收敛的速度 , 又影响聚类结果的质量 ; 选择的好 , 迭代 22 次 , 算法收敛 , 得到最终结果 , 并且聚类效果很好 ; 选择的不好 , 迭代很多次才收敛 , 并且聚类效果很差 ;


    2 . 初始中心点选择方案 :


    ① 随机选择 ;

    ② 使用已知聚类算法的结果 ;

    ③ 爬山算法 : K-Means 采用的是爬山算法 , 只找局部最优的中心点 ;



    K-Means 算法优缺点



    1 . K-Means 算法优点 :


    ① 算法可扩展性高 : 算法复杂度随数据量增加 , 而线性增加 ;

    ② 算法的复杂度 : K-Means 的算法复杂度是 O(tkn)O(tkn) , nn 是数据样本个数 , kk 是聚类分组的个数 , tt 是迭代次数 , tt 一般不超过 nn ;


    2 . K-Means 算法缺点 :


    ③ 事先必须设定聚类个数 : K-Means 的聚类分组的个数, 必须事先确定 , 有些应用场景中 , 事先是不知道聚类个数的 ;

    ④ 有些中心点难以确定 : 有些数据类型的中心点不好确定 , 如字符型的数据 , 离散型数据 , 布尔值数据 等 ;

    ⑤ 鲁棒性差 : 对于数据样本中的噪音数据 , 异常数据 , 不能有效的排除这些数据的干扰 ;

    ⑥ 局限性 : 只能处理凸状 , 或 球状分布的样本数据 , 对于 凹形分布 的样本数据 , 无法有效的进行聚类分析 ;



    K-Means 算法变种



    1 . K-Means 方法有很多变种 :


    ① K_Modes : 处理离散型的属性值 , 如字符型数据等 ;

    ② K-Prototypes : 处理 离散型 或 连续型 的属性 ;

    ③ K-Medoids : 其计算中心点不是使用算术平均值 , 其使用的是中间值 ;


    2 . K-Means 变种算法 与 k-Means 算法的区别与联系 :


    ① 原理相同 : 这些变种算法 与 K-Means 算法原理基本相同 ;

    ② 中心点选择不同 : 变种算法 与 原算法 最初的中心点选择不同 ;

    ③ 距离计算方式不同 : K-Means 使用曼哈顿距离 , 变种算法可能使用 欧几里得距离 , 明科斯基距离 , 边际距离 等 ;

    ④ 计算聚类中心点策略不同 : K-Means 算法中使用算术平均 , 有的使用中间值 ;

    展开全文
  • 03 聚类算法 - K-means聚类04 聚类算法 - 代码案例一 - K-means聚类 三、K-Means算法衍生 1、二分K-Means算法 解决K-Means算法对__初始簇心__比较敏感的问题,二分K-Means算法是一种弱化初始质心的一种算法,__具体...

    03 聚类算法 - K-means聚类
    04 聚类算法 - 代码案例一 - K-means聚类

    三、K-Means算法衍生

    1、二分K-Means算法

    解决K-Means算法对__初始簇心__比较敏感的问题,二分K-Means算法是一种弱化初始质心的一种算法,__具体思路步骤如下__:

    1、将所有样本数据作为一个簇放到一个队列中。
    2、从队列中选择一个簇进行K-means算法划分,划分为两个子簇,并将子簇添加到队列中。
    3、循环迭代第二步操作,直到中止条件达到(聚簇数量、最小平方误差、迭代次数等)。
    4、队列中的簇就是最终的分类簇集合。

    从队列中选择划分聚簇的规则一般有两种方式;分别如下:

    1、对所有簇计算误差和SSE(SSE也可以认为是距离函数的一种变种),选择SSE最大的聚簇进行划分操作(优选这种策略)。
    2、选择样本数据量最多的簇进行划分操作:

    公式

    几何意义


    2、K-Means++算法

    解决K-Means算法对初始簇心比较敏感的问题,K-Means++算法和K-Means算法的区别主要在于__初始的K个中心点__的选择方面,K-Means算法使用随机给定的方式,K-Means++算法采用下列步骤给定K个初始质点:

    1、从数据集中任选一个节点作为第一个聚类中心。
    2、对数据集中的每个点x,计算x到所有已有聚类中心点的距离和D(X),基于D(X)采用线性概率选择出下一个聚类中心点(距离较远的一个点成为新增的一个聚类中心点)。
    3、重复步骤2直到找到k个聚类中心点。

    __缺点:__由于聚类中心点选择过程中的内在有序性,在扩展方面存在着性能方面的问题(第k个聚类中心点的选择依赖前k-1个聚类中心点的值)

    几何意义


    3、K-Means||算法

    解决K-Means++算法缺点而产生的一种算法;主要思路是改变每次遍历时候的取样规则,并非按照K-Means++算法每次遍历只获取一个样本,而是每次获取K个样本,重复该取样操作O(logn)次__(n是样本的个数)__,然后再将这些抽样出来的样本聚类出K个点,最后使用这K个点作为K-Means算法的初始聚簇中心点。实践证明:一般5次重复采用就可以保证一个比较好的聚簇中心点。

    梳理步骤:
    1、在N个样本中抽K个样本,一共抽logn次,形成一个新的样本集,一共有Klogn个数据。
    2、在新数据集中使用K-Means算法,找到K个聚簇中心。
    3、把这K个聚簇中心放到最初的样本集中,作为初始聚簇中心。
    4、原数据集根据上述初始聚簇中心,再用K-Means算法计算出最终的聚簇。


    4、Canopy算法

    Canopy算法属于一种“粗”聚类算法,执行速度较快,但精度较低,__算法执行步骤如下__:

    1、给定样本列表L=x1,x,2...,xm以及先验值r1和r2(r1>r2);__(先验值 - 自己猜的,人为定义的值)__;
    2、从列表L中获取一个节点P,计算P到所有聚簇中心点的距离(如果不存在聚簇中心,那么此时点P形成一个新的聚簇),并选择出最小距离D(P,aj);
    3、如果距离D小于r1,表示该节点属于该聚簇,添加到该聚簇列表中。
    4、如果距离D小于r2,表示该节点不仅仅属于该聚簇,还表示和当前聚簇中心点非常近,所以将该聚簇的中心点设置为P,并将P从列表L中删除。
    5、如果距离D大于r1,那么节点P形成一个新的聚簇。
    6、直到列表L中的元素数据不再有变化或者元素数量为0的时候,结束循环操作。

    分析步骤

    注意上图中修改一个地方:
    本质上,列表中离得近的元素都删了。如果节点P生成了一个新的中心节点,也应该被删除掉。因为这些点已经变成了聚簇中心。


    Canopy算法得到的最终结果的值,聚簇之间是可能存在重叠的,但是不会存在
    某个对象不属于任何聚簇的情况。

    几何意义


    Canopy算法过程图形说明:

    Canopy图形说明

    Canopy算法常用应用场景:

    由于K-Means算法存在初始聚簇中心点敏感的问题,常用使用Canopy+K-Means算法混合形式进行模型构建。
    1、先使用canopy算法进行“粗”聚类得到K个聚类中心点。
    2、K-Means算法使用Canopy算法得到的K个聚类中心点作为初始中心点,进行“细”聚类。

    优点:
    1、执行速度快(先进行了一次聚簇中心点选择的预处理);
    2、不需要给定K值,应用场景多。
    3、能够缓解K-Means算法对于初始聚类中心点敏感的问题。


    5、Mini Batch K-Means

    Mini Batch K-Means算法是K-Means算法的一种优化变种,采用__小规模的数据子集__(每次训练使用的数据集是在训练算法的时候随机抽取的数据子集)__减少计算时间__,同时试图优化目标函数;Mini Batch K-Means算法可以减少K-Means算法的收敛时间,而且产生的结果效果只是略差于标准K-Means算法。

    算法步骤如下:
    1、首先抽取部分数据集,使用K-Means算法构建出K个聚簇点的模型。
    2、继续抽取训练数据集中的部分数据集样本数据,并将其添加到模型中,分配给距离最近的聚簇中心点。
    3、更新聚簇的中心点值。
    4、循环迭代第二步和第三步操作,直到中心点稳定或者达到迭代次数,停止计算操作。

    06 聚类算法 - 代码案例二 - K-Means算法和Mini Batch K-Means算法比较

    展开全文
  • k-means-u *算法 非本地跳转和贪婪重试可改善k-means ++聚类 该存储库包含建议的k-means-u和k-mean-u *算法的示例python代码。 快速开始 克隆存储库: git clone https://github.com/gittar/k-means-u-star cd主...
  • k-meansk-means++,核k-means

    千次阅读 2019-08-30 20:16:47
    通过绘制K-means代价函数与聚类数目K的关系图,选取直线拐点处的K值作为最佳的聚类中心数目。 但最好还是从实际问题出发,人工指定比较合理的K值,通过多次随机初始化聚类中心选取比较满意的结果。 k-means++算法 ...

    先说一下欧氏距离
    二维空间公式:
    在这里插入图片描述
    三维空间的公式:
    在这里插入图片描述
    n维空间的公式
    在这里插入图片描述

    经典k-means算法

    在这里插入图片描述
    关于聚类中心数目(K值)的选取,方法为:Elbow Method:
    通过绘制K-means代价函数与聚类数目K的关系图,选取直线拐点处的K值作为最佳的聚类中心数目。
    但最好还是从实际问题出发,人工指定比较合理的K值,通过多次随机初始化聚类中心选取比较满意的结果。

    k-means++算法

    在这里插入图片描述
    注意:轮盘法。

    核k-means算法

    核k-means:就是将数据点都投影到了一个高维的特征空间中(为了凸显不同样本中的差异),然后再在这个高维的特征空间中,进行传统的k-means聚类。
    输入:所有数据点A,聚类个数k
    输出:k个聚类中心点
    1:输入数据通过核函数映射到高维空间得到矩阵B
    2:对B进行标准k-均值聚类

    展开全文
  • 上一篇文章中,我在最后有说到,K-means算法由于初始“聚类中心”点是随机选取的,因此最终求得的簇的划分与随机选取的“聚类中心”有关,也就是说,可能会造成多种 k 个簇的划分情况。这是因为K-means算法收敛到了...
  • TW-Co-k-means:用于多视图聚类的两级加权协作k-means
  • I . 基于划分的聚类方法 II . K-Means 算法 简介 III . K-Means 算法 步骤 IV . K-Means 方法的评分函数 V . K-Means 算法 图示
  • 文章目录6.5 算法优化学习目标1 Canopy算法配合初始聚类1.1 Canopy算法配合初始聚类实现流程1.2 Canopy算法的优缺点2 K-means++3 二分k-means4 k-medoids(k-中心聚类算法)5 Kernel k-means(了解)6 ISODATA(了解...
  • 一、k-means 1、简述 K-Means是一种无监督学习算法。算法的思想很简单,对于给定的样本集,按照样本之间的距离大小,将样本集划分为K个簇。让簇内的点尽量紧密的连在一起,而让簇间的距离尽量的大。 2、K-means算法...
  • 机器学习 - K-MeansK-Means++ 以及 ISOData K-Means K-Means++ ISOData K-Means 与 KNN 比较
  • K-means聚类算法和模糊C-means聚类算法

    万次阅读 多人点赞 2018-02-05 21:16:47
    K-means聚类算法和模糊C-means聚类算法 1.K-means聚类算法 K-means算法是硬聚类算法,是典型的基于原型的目标函数聚类方法的代表,它是数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代...
  • K-means聚类算法的三种改进(K-means++,ISODATA,Kernel K-means)介绍与对比 转自:https://www.cnblogs.com/yixuan-xu/p/6272208.html   一、概述       在本篇文章中将对...
  • K-Means-from-scratch:从零开始实施K-Means聚类算法,并与Scikit学习模型进行比较
  • K-Means

    2019-05-16 20:39:47
    K-Means K-Means的工作原理: 随机选取K个点作为初始的类中心点 将每个点分配到最近的类中心点,然后重新计算每个类的中心点 重复第二步,直到类不发生变化,或达到最大迭代次数 K-Means的引用: from sklearn....
  • 一、k-means:在大数据的条件下,会耗费大量的时间和内存。优化k-means的建议:1、减少聚类的数目K。因为,每个样本都要跟类中心计算距离。2、减少样本的特征维度。比如说,通过PCA等进行降维。3、考察其他的聚类...
  • K-meansK-means++(基于python实现)

    千次阅读 2020-06-15 13:21:42
    K-meansK-means++原理相对简单,直接引用了下文中的内容: https://www.cnblogs.com/yixuan-xu/p/6272208.html 本文重点是基于python实现了K-meansK-means++算法,并做了测试。 一、K-means 二、K-means++...
  • k-means 优缺点:**  1.算法快速、简单;  2.对大数据集有较高的效率并且是可伸缩性的;  3.时间复杂度近于线性,而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是O(n×k×t) ,其中n代表数据集中对象的...
  • K-meansK-means++

    千次阅读 2019-03-11 15:34:24
    一、概述 在本篇文章中将对聚类算法(K-means,K-means++)进行详细介绍,并利用数据集来真实地反映这算法之间的区别。 首先需要明确的是上述算法都属于"...K-meansK-means++:原始K-means算法最开...
  • K-means算法研究综述

    万次阅读 2017-03-18 10:33:39
    K-means算法研究综述 聚类被认为是机器学习中最常使用的技术之一, 它历史悠久、应用广泛,几乎应用于环境学、医学、生物学、天文学、经济学等各个领域。其中K-means是最为常用的聚类算法。现在我们来详细介绍一下K-...
  • ML之Clustering之K-meansK-means算法简介、应用、经典案例之详细攻略 目录 K-means算法简介 1、K-means算法适用的数据类型​ 2、K-Means算法的全局最优解和局部最优解的比较 1、K-means算法的过程及其...
  • 遗传k-means 遗传算法 演化算法 聚类算法 k-means 遗传k-means 遗传算法 演化算法 聚类算法 k-means 遗传k-means 遗传算法 演化算法 聚类算法 k-means
  • K-means

    千次阅读 2018-06-29 17:00:26
    # K均值算法(K-means)聚类 ## 【关键词】K个种子,均值 ## 一、K-means算法原理 聚类的概念:一种无监督的学习,事先不知道类别,自动将相似的对象归到同一个簇中。 K-Means算法是一种聚类...
  • 聚类模型:K-Means 聚类(clustering)属于无监督学习(unsupervised learning) 无类别标记 在线 demo:http://syskall.com/kmeans.js K-Means算法 数据挖掘十大经典算法之一 算法接收参数k;然后将样本点划分...
  • 文章目录聚类算法学习目标6.5 算法优化1 Canopy算法配合初始聚类1.1 Canopy算法配合初始聚类实现流程1.2 Canopy算法的优缺点2 K-means++3 二分k-means4 k-medoids(k-中心聚类算法)5 Kernel k-means(了解)6 ...
  • HeitorTerra-Algoritmos-De-IA_Fuzzy-C-Means_KNN_K-Means-e-Decision-Tree
  • 03 聚类算法 - K-means聚类04 聚类算法 - 代码案例一 - K-means聚类05 聚类算法 - 二分K-MeansK-Means++、K-Means||、Canopy、Mini Batch K-Means算法 常规操作: import time import numpy as np import ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,815
精华内容 7,926
关键字:

k-means