K-means聚类算法的三种改进(K-means++,ISODATA,Kernel K-means)介绍与对比

这篇具有很好参考价值的文章主要介绍了K-means聚类算法的三种改进(K-means++,ISODATA,Kernel K-means)介绍与对比。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 

目录

 一、概述

二、经典K-means算法

三、K-means++算法

四、ISODATA算法

六、数据集测试


 一、概述

      在本篇文章中将对四种聚类算法(K-means,K-means++,ISODATA和Kernel K-means)进行详细介绍,并利用数据集来真实地反映这四种算法之间的区别。

      首先需要明确的是上述四种算法都属于"硬聚类”算法,即数据集中每一个样本都是被100%确定得分到某一个类别中。与之相对的"软聚类”可以理解为每个样本是以一定的概率被分到某一个类别中。

      先简要阐述下上述四种算法之间的关系,已经了解过经典K-means算法的读者应该会有所体会。没有了解过K-means的读者可以先看下面的经典K-means算法介绍再回来看这部分。

     (1) K-means与K-means++:原始K-means算法最开始随机选取数据集中K个点作为聚类中心,而K-means++按照如下的思想选取K个聚类中心:假设已经选取了n个初始聚类中心(0<n<K),则在选取第n+1个聚类中心时:距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。在选取第一个聚类中心(n=1)时同样通过随机的方法。可以说这也符合我们的直觉:聚类中心当然是互相离得越远越好。这个改进虽然直观简单,但是却非常得有效。

      (2) K-means与ISODATA:ISODATA的全称是迭代自组织数据分析法。在K-means中,K的值需要预先人为地确定,并且在整个算法过程中无法更改。而当遇到高维度、海量的数据集时,人们往往很难准确地估计出K的大小。ISODATA就是针对这个问题进行了改进,它的思想也很直观:当属于某个类别的样本数过少时把这个类别去除,当属于某个类别的样本数过多、分散程度较大时把这个类别分为两个子类别。

      (3) K-means与Kernel K-means:传统K-means采用欧式距离进行样本间的相似度度量,显然并不是所有的数据集都适用于这种度量方式。参照支持向量机中核函数的思想,将所有样本映射到另外一个特征空间中再进行聚类,就有可能改善聚类效果。本文不对Kernel K-means进行详细介绍。

      可以看到,上述三种针对K-means的改进分别是从不同的角度出发的,因此都非常具有代表意义。目前应用广泛的应该还是K-means++算法(例如2016年底的NIPS上也有针对K-means++的改进,感兴趣的读者可以进一步学习https://papers.nips.cc/paper/6478-fast-and-provably-good-seedings-for-k-means)。

二、经典K-means算法

    算法描述如下,非常清晰易懂。经典K-means算法应该是每个无监督学习教程开头都会讲的内容,故不再多费口舌说一遍了。

kmeans聚类改进,Algorithm,聚类,算法,kmeans

图1. 经典K-means算法

      值得一提的是关于聚类中心数目(K值)的选取,的确存在一种可行的方法,叫做Elbow Method:通过绘制K-means代价函数与聚类数目K的关系图,选取直线拐点处的K值作为最佳的聚类中心数目。但在这边不做过多的介绍,因为上述方法中的拐点在实际情况中是很少出现的。比较提倡的做法还是从实际问题出发,人工指定比较合理的K值,通过多次随机初始化聚类中心选取比较满意的结果。

三、K-means++算法

      2007年由D. Arthur等人提出的K-means++针对图1中的第一步做了改进。可以直观地将这改进理解成这K个初始聚类中心相互之间应该分得越开越好。整个算法的描述如下图所示:

kmeans聚类改进,Algorithm,聚类,算法,kmeans

    图2. K-means++算法

      下面结合一个简单的例子说明K-means++是如何选取初始聚类中心的。数据集中共有8个样本,分布以及对应序号如下图所示:

kmeans聚类改进,Algorithm,聚类,算法,kmeans

图3. K-means++示例

      假设经过图2的步骤一后6号点被选择为第一个初始聚类中心,那在进行步骤二时每个样本的D(x)和被选择为第二个聚类中心的概率如下表所示:

kmeans聚类改进,Algorithm,聚类,算法,kmeans

    其中的P(x)就是每个样本被选为下一个聚类中心的概率。最后一行的Sum是概率P(x)的累加和,用于轮盘法选择出第二个聚类中心。方法是随机产生出一个0~1之间的随机数,判断它属于哪个区间,那么该区间对应的序号就是被选择出来的第二个聚类中心了。例如1号点的区间为[0,0.2),2号点的区间为[0.2, 0.525)。

      从上表可以直观的看到第二个初始聚类中心是1号,2号,3号,4号中的一个的概率为0.9。而这4个点正好是离第一个初始聚类中心6号点较远的四个点。这也验证了K-means的改进思想:即离当前已有聚类中心较远的点有更大的概率被选为下一个聚类中心。可以看到,该例的K值取2是比较合适的。当K值大于2时,每个样本会有多个距离,需要取最小的那个距离作为D(x)

四、ISODATA算法

     放在最后也是最复杂的就是ISODATA算法。正如之前所述,K-means和K-means++的聚类中心数K是固定不变的。而ISODATA算法在运行过程中能够根据各个类别的实际情况进行两种操作来调整聚类中心数K:(1)分裂操作,对应着增加聚类中心数;(2)合并操作,对应着减少聚类中心数。

    下面首先给出ISODATA算法的输入(输入的数据和迭代次数不再单独介绍):

      [1] 预期的聚类中心数目Ko:虽然在ISODATA运行过程中聚类中心数目是可变的,但还是需要由用户指定一个参考标准。事实上,该算法的聚类中心数目变动范围也由Ko决定。具体地,最终输出的聚类中心数目范围是 [Ko/2, 2Ko]。

      [2] 每个类所要求的最少样本数目Nmin:用于判断当某个类别所包含样本分散程度较大时是否可以进行分裂操作。如果分裂后会导致某个子类别所包含样本数目小于Nmin,就不会对该类别进行分裂操作。

      [3] 最大方差Sigma:用于衡量某个类别中样本的分散程度。当样本的分散程度超过这个值时,则有可能进行分裂操作(注意同时需要满足[2]中所述的条件)。

      [4] 两个类别对应聚类中心之间所允许最小距离dmin:如果两个类别靠得非常近(即这两个类别对应聚类中心之间的距离非常小),则需要对这两个类别进行合并操作。是否进行合并的阈值就是由dmin决定。

      相信很多人看完上述输入的介绍后对ISODATA算法的流程已经有所猜测了。的确,ISODATA算法的原理非常直观,不过由于它和其他两个方法相比需要额外指定较多的参数,并且某些参数同样很难准确指定出一个较合理的值,因此ISODATA算法在实际过程中并没有K-means++受欢迎。

      首先给出ISODATA算法主体部分的描述,如下图所示:

kmeans聚类改进,Algorithm,聚类,算法,kmeans

图4. ISODATA算法的主体部分

     上面描述中没有说明清楚的是第5步中的分裂操作和第6步中的合并操作。下面首先介绍合并操作:

kmeans聚类改进,Algorithm,聚类,算法,kmeans

图5. ISODATA算法的合并操作

     最后是ISODATA算法中的分裂操作。

kmeans聚类改进,Algorithm,聚类,算法,kmeans

图6. ISODATA算法的分裂操作

      最后,针对ISODATA算法总结一下:该算法能够在聚类过程中根据各个类所包含样本的实际情况动态调整聚类中心的数目。如果某个类中样本分散程度较大(通过方差进行衡量)并且样本数量较大,则对其进行分裂操作;如果某两个类别靠得比较近(通过聚类中心的距离衡量),则对它们进行合并操作。

       可能没有表述清楚的地方是ISODATA-分裂操作的第1步和第2步。同样地以图三所示数据集为例,假设最初1,2,3,4,5,6,8号被分到了同一个类中,执行第1步和第2步结果如下所示:

kmeans聚类改进,Algorithm,聚类,算法,kmeans

      而在正确分类情况下(即1,2,3,4为一类;5,6,7,8为一类),方差为0.33。因此,目前的方差远大于理想的方差,ISODATA算法就很有可能对其进行分裂操作。

五、聚类算法源代码

      我已经将上述三种算法整合成一个Matlab函数Clustering.m。读者可以直接使用该函数对数据集进行聚类。由于代码比较长,而且代码插件还不怎么会用,就不在文中介绍了。需要使用的读者可以点击下面的链接下载使用(欢迎Star和Fork,之后会不定期补充新的算法和优化的):

GitHub - xuyxu/Clustering: Clustering / Subspace Clustering Algorithms on MATLAB

     使用方式非常简单,目前支持三种形式的输入,分别对应着上面的三种算法:

     [centroid, result] = Clustering(data, ‘kmeans’, k , iteration);

     [centroid, result] = Clustering(data, ‘kmeans++’, k , iteration);

     [centroid, result] =

   Clustering(data, ‘isodata’, desired_k , iteration, minimum_n, maximum_variance, minimum_d);

      其中的输入data是一个矩阵,每一行代表数据集中的一个样本。其他输入的意义与上面的算法描述中一一对应。输出的centroid是聚类中心的位置,result是每个样本所对应的类别索引。

六、数据集测试

      最后以一个简单的满足二维高斯分布的数据集为例,展示上述三种算法的聚类结果,如下图所示。

kmeans聚类改进,Algorithm,聚类,算法,kmeans

图7. 一个简单数据集上三种算法的聚类效果(绿色加号代表聚类中心位置)

引用参考:

K-means聚类算法的三种改进(K-means++,ISODATA,Kernel K-means)介绍与对比https://www.cnblogs.com/yixuan-xu/p/6272208.html文章来源地址https://www.toymoban.com/news/detail-817600.html

到了这里,关于K-means聚类算法的三种改进(K-means++,ISODATA,Kernel K-means)介绍与对比的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • K-means聚类算法原理及实现

    1.1概念 聚类分析,也称为分割分析或分类分析,可将样本数据分成一个个组(即簇)。同一簇中的对象是相似的,不同簇中的对象则明显不同。 Statistics and Machine Learning Toolbox™ 提供了几种聚类方法和相似性度量(也称为距离度量)来创建簇。此外,簇计算可以按照不同的计

    2024年03月18日
    浏览(41)
  • K-means++聚类算法(matlab实现)

    K-means++算法:K-means++算法是K-means算法的改进版,其在选择初始质心时采用了一种更加聪明的方法,能够有效地避免局部最优解。具体来说,K-means++算法的初始质心是根据距离数据点最远的原则来选择的,这样可以保证初始质心的分布更加广泛,从而使得算法更容易找到全局最

    2024年02月07日
    浏览(96)
  • 机器学习之K-means聚类算法

    目录 K-means聚类算法 算法流程 优点 缺点 随机点聚类 人脸聚类 旋转物体聚类 K-means聚类算法是一种无监督的学习方法,通过对样本数据进行分组来发现数据内在的结构。K-means的基本思想是将n个实例分成k个簇,使得同一簇内数据相似度高而不同簇之间数据相似度低。 K-means的

    2024年02月11日
    浏览(42)
  • K-means聚类算法及Python代码实现

    K-means聚类算法(事先数据并没有类别之分!所有的数据都是一样的) 1、概述 K-means算法是集简单和经典于一身的 基于距离的聚类算法 采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。 该算法认为类簇是由距离靠近的对象组成的,因此把得到

    2023年04月24日
    浏览(45)
  • 传统机器学习(三)聚类算法K-means(一)

    K-Means算法是无监督的聚类算法,它实现起来比较简单,聚类效果也不错,因此应用很广泛。K-Means基于欧式距离认为两个目标距离越近,相似度越大。 1.1.1 算法流程 (1)图a表达了初始的数据集, 假设k=2; (2)在图b中,随机选择两个k类的对应的类别质心,即图中的红色质

    2023年04月15日
    浏览(41)
  • K-means聚类算法(附Python实现代码)

    本文的代码与数据地址已上传至github:https://github.com/helloWorldchn/MachineLearning 1、基于划分的聚类 划分算法的思想是,将给定待挖掘数据集中的数据对象划分成K组(k≤N,N代表数据集中对象数目),每一组表示一个聚类的簇。并且要满足任何一个数据对象仅可以属于一个聚类,

    2024年02月07日
    浏览(43)
  • K-Means(K-均值)聚类算法理论和实战

    目录 K-Means 算法 K-Means 术语 K 值如何确定 K-Means 场景 美国总统大选摇争取摆选民 电商平台用户分层 给亚洲球队做聚类 ​编辑 其他场景 K-Means 工作流程 K-Means 开发流程 K-Means的底层代码实现 K-Means 的评价标准 对于 n 个样本点来说,根据距离公式(如欧式距离)去计 算它们的

    2024年02月11日
    浏览(36)
  • 【机器学习】K-means聚类算法:原理、应用与优化

    一、引言 1、简述聚类分析的重要性及其在机器学习中的应用   聚类分析,作为机器学习领域中的一种无监督学习方法,在数据探索与知识发现过程中扮演着举足轻重的角色。它能够在没有先验知识或标签信息的情况下,通过挖掘数据中的内在结构和规律,将数据对象自动

    2024年04月13日
    浏览(46)
  • K-means聚类算法原理、步骤、评价指标和实现

    1、聚类 聚类与分类不同,聚类分析分通过分析大量含有一定规律但杂乱数据,得到数据间内在的逻辑,将杂乱的数据按照所得的数据规律划分成不同的种类。K-measn、DBSCAN和层次是当前广泛使用的三种聚类方法。以下对三种方法进行分析,选择适合的聚类方法。 方法 K-means

    2024年02月07日
    浏览(56)
  • 【聚类算法】带你轻松搞懂K-means聚类(含代码以及详细解释)

    聚类是一个将数据集中 在某些方面相似的数据成员 进行分类组织的过程,聚类就是一种发现这种内在结构的技术,聚类技术经常被称为 无监督学习 。 k均值聚类是最著名的划分聚类算法,由于简洁和效率使得他成为所有聚类算法中最广泛使用的。给定一个数据点集合和需要

    2024年02月01日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包