0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

K-means的优缺点及改进

倩倩 来源:网络整理 2018-02-12 16:27 次阅读

K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。

k个初始类聚类中心点的选取对聚类结果具有较大的影响,因为在该算法第一步中是随机的选取任意k个对象作为初始聚类的中心,初始地代表一个簇。该算法在每次迭代中对数据集中剩余的每个对象,根据其与各个簇中心的距离将每个对象重新赋给最近的簇。当考察完所有数据对象后,一次迭代运算完成,新的聚类中心被计算出来。如果在一次迭代前后,J的值没有发生变化,说明算法已经收敛。

K-means的优缺点及改进

算法过程如下:

1)从N个文档随机选取K个文档作为质心

2)对剩余的每个文档测量其到每个质心的距离,并把它归到最近的质心的类

3)重新计算已经得到的各个类的质心

4)迭代2~3步直至新的质心与原质心相等或小于指定阈值,算法结束

具体如下:

输入:k, data[n];

(1) 选择k个初始中心点,例如c[0]=data[0],…c[k-1]=data[k-1];

(2) 对于data[0]….data[n],分别与c[0]…c[k-1]比较,假定与c[i]差值最少,就标记为i;

(3) 对于所有标记为i点,重新计算c[i]={ 所有标记为i的data[j]之和}/标记为i的个数;

(4) 重复(2)(3),直到所有c[i]值的变化小于给定阈值。

K-means的优缺点及改进

Kmeans算法的优缺点

K-means算法的优点是:首先,算法能根据较少的已知聚类样本的类别对树进行剪枝确定部分样本的分类;其次,为克服少量样本聚类的不准确性,该算法本身具有优化迭代功能,在已经求得的聚类上再次进行迭代修正剪枝确定部分样本的聚类,优化了初始监督学习样本分类不合理的地方;第三,由于只是针对部分小样本可以降低总的聚类时间复杂度。

K-means算法的缺点是:首先,在 K-means 算法中 K 是事先给定的,这个 K 值的选定是非常难以估计的。很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适;其次,在 K-means 算法中,首先需要根据初始聚类中心来确定一个初始划分,然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响,一旦初始值选择的不好,可能无法得到有效的聚类结果;最后,该算法需要不断地进行样本分类调整,不断地计算调整后的新的聚类中心,因此当数据量非常大时,算法的时间开销是非常大的。

K-means算法对于不同的初始值,可能会导致不同结果。解决方法:

1.多设置一些不同的初值,对比最后的运算结果,一直到结果趋于稳定结束

2.很多时候,事先并不知道给定的数据集应该分成多少个类别才最合适。通过类的自动合并和分裂,得到较为合理的类型数目 K,例如 ISODATA 算法。

K-means算法的其他改进算法如下:

1. k-modes 算法:实现对离散数据的快速聚类,保留了k-means算法的效率同时将k-means的应用范围扩大到离散数据。

2. k-Prototype算法:可以对离散与数值属性两种混合的数据进行聚类,在k-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。

K-means的优缺点及改进

大家接触的第一个聚类方法,十有八九都是K-means聚类啦。该算法十分容易理解,也很容易实现。其实几乎所有的机器学习和数据挖掘算法都有其优点和缺点。

(1)对于离群点和孤立点敏感;

(2)k值选择;

(3)初始聚类中心的选择;

(4)只能发现球状簇。

对于这4点呢的原因,读者可以自行思考下,不难理解。针对上述四个缺点,依次介绍改进措施。

改进1

首先针对(1),对于离群点和孤立点敏感,如何解决?提到过离群点检测的LOF算法,通过去除离群点后再聚类,可以减少离群点和孤立点对于聚类效果的影响。

改进2

k值的选择问题,在安徽大学李芳的硕士论文中提到了k-Means算法的k值自适应优化方法。下面将针对该方法进行总结。

首先该算法针对K-means算法的以下主要缺点进行了改进:

1)必须首先给出k(要生成的簇的数目),k值很难选择。事先并不知道给定的数据应该被分成什么类别才是最优的。

2)初始聚类中心的选择是K-means的一个问题。

李芳设计的算法思路是这样的:可以通过在一开始给定一个适合的数值给k,通过一次K-means算法得到一次聚类中心。对于得到的聚类中心,根据得到的k个聚类的距离情况,合并距离最近的类,因此聚类中心数减小,当将其用于下次聚类时,相应的聚类数目也减小了,最终得到合适数目的聚类数。可以通过一个评判值E来确定聚类数得到一个合适的位置停下来,而不继续合并聚类中心。重复上述循环,直至评判函数收敛为止,最终得到较优聚类数的聚类结果。

改进3

对初始聚类中心的选择的优化。一句话概括为:选择批次距离尽可能远的K个点。具体选择步骤如下。

首先随机选择一个点作为第一个初始类簇中心点,然后选择距离该点最远的那个点作为第二个初始类簇中心点,然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点,以此类推,直至选出K个初始类簇中心点。

对于该问题还有个解决方案。之前我也使用过。熟悉weka的同学应该知道weka中的聚类有一个算法叫Canopy算法。

选用层次聚类或者Canopy算法进行初始聚类,然后利用这些类簇的中心点作为KMeans算法初始类簇中心点。该方法对于k值的选择也是十分有效的。

改进4

只能获取球状簇的根本原因在于,距离度量的方式。在李荟娆的硕士论文K_means聚类方法的改进及其应用中提到了基于2种测度的改进,改进后,可以去发现非负、类椭圆形的数据。但是对于这一改进,个人认为,并没有很好的解决K-means在这一缺点的问题,如果数据集中有不规则的数据,往往通过基于密度的聚类算法更加适合,比如DESCAN算法。

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 聚类算法
    +关注

    关注

    2

    文章

    118

    浏览量

    12126
  • K-means
    +关注

    关注

    0

    文章

    28

    浏览量

    11293
收藏 人收藏

    评论

    相关推荐

    使用K-means压缩图像

    山东大学机器学习(实验六内容)—— K-Means
    发表于 08-28 09:25

    调用sklearn使用的k-means模型

    【python】调用sklearn使用k-means模型
    发表于 06-12 13:33

    K-Means有什么优缺点

    K-Means的主要优点是什么?K-Means的主要缺点是什么?
    发表于 06-10 06:14

    改进k-means聚类算法在供电企业CRM中的应用

    针对k-means算法存在的不足,提出了一种改进算法。 针对目前供电企业CRM系统的特点提出了用聚类分析方法进行客户群细分模型设计,通过实验验证了本文提出的k-means改进算法的高效
    发表于 03-01 15:28 15次下载

    Web文档聚类中k-means算法的改进

    Web文档聚类中k-means算法的改进 介绍了Web文档聚类中普遍使用的、基于分割的k-means算法,分析了k-means算法所使用的向量空间模型和基于距离的相似性度量的局限性,
    发表于 09-19 09:17 1055次阅读
    Web文档聚类中<b class='flag-5'>k-means</b>算法的<b class='flag-5'>改进</b>

    基于Hash改进k-means算法并行化设计

    挖掘其聚类关系,选取初始聚类中心,避免了传统k-means算法对随机选取初始聚类中心的敏感性,减少了k-means算法的迭代次数。又结合MapReduce框架将算法整体并行化,并通过Partition、Combine等机制加强了并行化程度和执行效率。实验表明,该算法不仅提
    发表于 11-24 14:24 2次下载
    基于Hash<b class='flag-5'>改进</b>的<b class='flag-5'>k-means</b>算法并行化设计

    基于密度的K-means算法在聚类数目中应用

    针对传统的K-means算法无法预先明确聚类数目,对初始聚类中心选取敏感且易受离群孤点影响导致聚类结果稳定性和准确性欠佳的问题,提出一种改进的基于密度的K-means算法。该算法首先基于轨迹数据分布
    发表于 11-25 11:35 0次下载

    K-Means算法改进及优化

    局部最优出现错误的聚类结果。针对传统的k-means算法初始聚类中心的缺点,本文提出了p-K-means算法,该算法采用了数学几何距离的方法改进k-
    发表于 12-05 18:32 0次下载
    <b class='flag-5'>K-Means</b>算法<b class='flag-5'>改进</b>及优化

    基于布谷鸟搜索的K-means聚类算法

    针对原始K-means聚类算法受初始聚类中心影响过大以及容易陷入局部最优的不足,提出一种基于改进布谷鸟搜索(cs)的K-means聚类算法(ACS-K-means)。其中,自适应CS(
    发表于 12-13 17:24 3次下载

    k-means算法原理解析

    对于K-Means算法,首先要注意的是k值的选择,一般来说,我们会根据对数据的先验经验选择一个合适的k值,如果没有什么先验知识,则可以通过交叉验证选择一个合适的k值。
    的头像 发表于 02-12 16:06 8339次阅读
    <b class='flag-5'>k-means</b>算法原理解析

    基于改进k-means算法的MANET异常检测方法

    针对移动自组网( MANET,mobile ad hoc networks)入侵检测过程中的攻击类型多样性和监测数据海量性问题,提出了一种基于改进k-means算法的MANET异常检测方法。通过引入
    发表于 03-06 15:18 0次下载

    K-Means算法的简单介绍

    K-Means是十大经典数据挖掘算法之一。K-Means和KNN(K邻近)看上去都是K打头,但却是不同种类的算法。kNN是监督学习中的分类算法,而K
    发表于 07-05 14:18 4917次阅读

    如何使用K-Means聚类算法改进的特征加权算法详细资料概述

    聚类分析是将研究对象分为相对同质的群组的统计分析威廉希尔官方网站 ,聚类分析的核心就是发现有用的对象簇。K-means聚类算法由于具有出色的速度和良好的可扩展性,一直备受广大学者的关注。然而,传统的K-means
    发表于 12-20 10:28 10次下载

    K-MEANS聚类算法概述及工作原理

    K-means 是一种聚类算法,且对于数据科学家而言,是简单且热门的无监督式机器学习(ML)算法之一。
    的头像 发表于 06-06 11:53 3993次阅读

    K-means聚类算法指南

    在聚类威廉希尔官方网站 领域中,K-means可能是最常见和经常使用的威廉希尔官方网站 之一。K-means使用迭代细化方法,基于用户定义的集群数量(由变量K表示)和数据集来产生其最终聚类。例如,如果将K设置为3
    的头像 发表于 10-28 14:25 1460次阅读