专栏首页数据科学与人工智能【机器学习】聚类算法总结

【机器学习】聚类算法总结

类的目标是使同一类对象的相似度尽可能地小;不同类对象之间的相似度尽可能地大。目前聚类的方法很多,根据基本思想的不同,大致可以将聚类算法分为五大类:层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。以下内容摘自《数据挖掘中的聚类分析研究综述》。

1、层次聚类算法

1.1 聚合聚类

1.1.1相似度依据距离不同:Single-Link:最近距离、Complete-Link:最远距离、Average-Link:平均距离

1.1.2 最具代表性算法

1)CURE算法

特点:固定数目有代表性的点共同代表类

优点:识别形状复杂,大小不一的聚类,过滤孤立点

2)ROCK算法

特点:对CURE算法的改进

优点:同上,并适用于类别属性的数据

3)CHAMELEON算法

特点:利用了动态建模技术

1.2 优缺点

优点:适用于任意形状和任意属性的数据集;灵活控制不同层次的聚类粒度,强聚类能力

缺点:大大延长了算法的执行时间,不能回溯处理

2、分割聚类算法

2.1 基于密度的聚类

2.1.1特点

将密度足够大的相邻区域连接,能有效处理异常数据,主要用于对空间数据的聚类

2.1.2典型算法

1)DBSCAN:不断生长足够高密度的区域

2)DENCLUE:根据数据点在属性空间中的密度进行聚类,密度和网格与处理的结合

3)OPTICS、DBCLASD、CURD:均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进

2.2 基于网格的聚类

2.2.1特点

利用属性空间的多维网格数据结构,将空间划分为有限数目的单元以构成网格结构;

1)优点:处理时间与数据对象的数目无关,与数据的输入顺序无关,可以处理任意类型的数据

2)缺点:处理时间与每维空间所划分的单元数相关,一定程度上降低了聚类的质量和准确性

2.2.2典型算法

1)STING:基于网格多分辨率,将空间划分为方形单元,对应不同分辨率

2)STING+:改进STING,用于处理动态进化的空间数据

3)CLIQUE:结合网格和密度聚类的思想,能处理大规模高维度数据

4)WaveCluster:以信号处理思想为基础

2.3 基于图论的聚类

2.3.1特点

转换为组合优化问题,并利用图论和相关启发式算法来解决,构造数据集的最小生成数,再逐步删除最长边

1)优点:不需要进行相似度的计算

2.3.2两个主要的应用形式

1)基于超图的划分

2)基于光谱的图划分

2.4基于平方误差的迭代重分配聚类

2.4.1思想

逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解

2.4.2具体算法

1)概率聚类算法

期望最大化、能够处理异构数据、能够处理具有复杂结构的记录、能够连续处理成批的数据、具有在线处理能力、产生的聚类结果易于解释

2)最近邻聚类算法——共享最近邻算法SNN

特点:结合基于密度方法和ROCK思想,保留K最近邻简化相似矩阵和个数

不足:时间复杂度提高到了O(N^2)

3)K-Medioids算法

特点:用类中的某个点来代表该聚类

优点:能处理任意类型的属性;对异常数据不敏感

4)K-Means算法

1》特点:聚类中心用各类别中所有数据的平均值表示

2》原始K-Means算法的缺陷:结果好坏依赖于对初始聚类中心的选择、容易陷入局部最优解、对K值的选择没有准则可依循、对异常数据较为敏感、只能处理数值属性的数据、聚类结构可能不平衡

3》K-Means的变体

Bradley和Fayyad等:降低对中心的依赖,能适用于大规模数据集

Dhillon等:调整迭代过程中重新计算中心方法,提高性能

Zhang等:权值软分配调整迭代优化过程

Sarafis:将遗传算法应用于目标函数构建中

Berkh in等:应用扩展到了分布式聚类

还有:采用图论的划分思想,平衡聚类结果,将原始算法中的目标函数对应于一个各向同性的高斯混合模型

5)优缺点

优点:应用最为广泛;收敛速度快;能扩展以用于大规模的数据集

缺点:倾向于识别凸形分布、大小相近、密度相近的聚类;中心选择和噪声聚类对结果影响大

3、基于约束的聚类算法

3.1约束

对个体对象的约束、对聚类参数的约束;均来自相关领域的经验知识

3.2重要应用

对存在障碍数据的二维空间按数据进行聚类,如COD(Clustering with Obstructed Distance):用两点之间的障碍距离取代了一般的欧式距离

3.3不足

通常只能处理特定应用领域中的特定需求

4、用于高维数据的聚类算法

4.1困难来源因素

1)无关属性的出现使数据失去了聚类的趋势

2)区分界限变得模糊

4.2解决方法

1)对原始数据降维

2)子空间聚类

CACTUS:对原始空间在二维平面上的投影

CLIQUE:结合基于密度和网格的聚类思想,借鉴Apriori算法

3)联合聚类技术

特点:对数据点和属性同时进行聚类

文本:基于双向划分图及其最小分割的代数学方法

4.3不足:不可避免地带来了原始数据信息的损失和聚类准确性的降低

5、机器学习中的聚类算法

5.1两个方法

1)人工神经网络方法

自组织映射:向量化方法,递增逐一处理;映射至二维平面,实现可视化

基于投影自适应谐振理论的人工神经网络聚类

2)基于进化理论的方法

缺陷:依赖于一些经验参数的选取,并具有较高的计算复杂度

模拟退火:微扰因子;遗传算法(选择、交叉、变异)

5.2优缺点

优点:利用相应的启发式算法获得较高质量的聚类结果

缺点:计算复杂度较高,结果依赖于对某些经验参数的选择

本文分享自微信公众号 - 数据科学与人工智能(DS_AI_shujuren)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2015-10-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【算法】聚类算法

    小编邀请您,先思考: 1 有哪些算法可以聚类?各自有什么特点? 2 聚类算法的效果如何评价? 1 定义 聚类是数据挖掘中的概念,就是按照某个特定标准(如距离)把...

    陆勤_数据人网
  • 【数据挖掘】聚类算法总结

    一、层次聚类 1、层次聚类的原理及分类 1)层次法(Hierarchicalmethods)先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后,再计算...

    陆勤_数据人网
  • 【知识】图解机器学习

    每当提到机器学习,大家总是被其中的各种各样的算法和方法搞晕,觉得无从下手。确实,机器学习的各种套路确实不少,但是如果掌握了正确的路径和方法,其实还是有迹可循的,...

    陆勤_数据人网
  • 推荐|数据科学家需要了解的5大聚类算法

    IT派 - {技术青年圈} 持续关注互联网、大数据、人工智能领域 聚类是一种涉及数据点分组的机器学习技术。给定一个数据点集,则可利用聚类算法将每个数据点分类...

    IT派
  • 《机器学习》笔记-聚类(9)

    机器学习算法工程师
  • 机器学习算法之聚类算法

    "If you set your goals ridiculously high and it's a failure, you will fail above...

    小闫同学啊
  • R语言从入门到精通:Day15(聚类分析)

    聚类分析是一种数据归约技术,旨在揭露一个数据集中观测值的子集。它可以把大量的观测值归约为若干个类。

    用户6317549
  • 【AIDL专栏】方以类聚,物以群分,吉凶生矣 | 于剑:聚类理论与算法选讲

    聚类的思想起源非常早,中国可以追溯到《周易·系辞上》中的“方以类聚,物以群分,吉凶生矣”。但聚类的算法却是上世纪50年代才出现,这是因为聚类依赖于数据,数据量小...

    马上科普尚尚
  • SAS用K-Means 聚类最优k值的选取和分析

    坐在餐馆的用餐者。假设餐厅中有两个桌子。桌子1中的人可能彼此相关,可能是一组家庭成员或同事。

    拓端
  • R语言之实现K-mean聚类算法

    聚类算法作为无监督的学习方法,在不给出Y的情况下对所有的样本进行聚类。以动态聚类为基础的K均值聚类方法是其中最简单而又有深度的一种方法。K均值的好处是我们可以在...

    一粒沙

扫码关注云+社区

领取腾讯云代金券