数据挖掘之各种聚类算法的比较 (转载)

 转载:%40126/blog/static/48972522201092254141315/   聚类的目标是使同一类对象的相似度尽可能地大;不同类对象之间的相似度尽可能地小。目前聚类的方法很多,根据基本思想的不同,大致可以将聚类算法分为五大类:层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自 数据挖掘中的聚类分析研究综述 这篇论文。 1、层次聚类算法 1.1聚合聚类 1.1.1相似度依据距离不同:Single-Link:最近距离、Complete-Link:最远距离、Average-Link:平均距离 1.1.2最具代表性算法

1)CURE算法

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

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

2)ROCK算法

特点:对CURE算法的改进

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

3)CHAMELEON算法

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

1.2分解聚类 1.3优缺点

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

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

 

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)

3K-Medioids算法

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

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

4K-Means算法

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

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzxgsw.html