聚类分析中几种算法的比较
将数据库中的对象进行聚类是聚类分析的基本操作,其准则是使属于同一类的个体间距离尽可能小,而不同类个体间距离尽可能大,为了找到效率高、通用性强的聚 类方法人们从不同角度提出了近百种聚类方法,典型的有K-means方法、K-medoids方法、CLARANS方法,BIRCH方法等,这些算法适用 于特定的问题及用户。本文综合提出了评价聚类算法好坏的5个标准,基于这5个标准,对数据挖掘中常用聚类方法作了比较分析,以便于人们更容易、更快捷地找 到一种适用于特定问题及用户的聚类算法。
聚类算法研究及比较框架
聚类算法一般有五种方法,最主要的是划分方法和层次方法两种。划分聚类算法通过优化评价函数把数据集分割为K个部分,它需要K作为
输人参数。典型的分割聚类算法有K-means算法,
K-medoids算法、CLARANS算法。层次聚类由不同层次的分割聚类组成,层次之间的分割具有嵌套的关系。它不需要输入参数,这是它优于分割聚类
算法的一个明显的优点,其缺点是终止条件必须具体指定。典型的分层聚类算法有BIRCH算法、DBSCAN算法和CURE算法等。
对各聚类算法的比较研究基于以下5个标准:
① 是否适用于大数据量,算法的效率是否满足大数据量高复杂性的要求;
② 是否能应付不同的数据类型,能否处理符号属性;
③ 是否能发现不同类型的聚类;
④ 是否能应付脏数据或异常数据;
⑤ 是否对数据的输入顺序不敏感。
下面将在该框架下对各聚类算法作分析比较。
数据挖掘常用聚类算法比较分析
3.1 K-pototypes算法
K-pototypes算法结合了K-means方法和根据K-means方法改进的能够处理符号属性的K-modes方法,同K-means方法相比,K-pototypes 算法能够处理符号属性。
3.2 CLARANS算法(划分方法)
CLARANS算法即随机搜索聚类算法,是一种分割聚类方法。它首先随机选择一个点作为当前点,然后随机检查它周围不超过参数Maxneighbor
个的一些邻接点,假如找到一个比它更好的邻接点,则把它移人该邻接点,否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量,直至所找
到的局部最小量数目达到用户要求为止。该算法要求聚类的对象必须都预先调人内存,并且需多次扫描数据集,这对大数据量而言,无论时间复杂度还是空间复杂度
都相当大。虽通过引人R-树结构对其性能进行改善,使之能够处理基于磁盘的大型数据库,但R*-树的构造和维护代价太大。该算法对脏数据和异常数据不敏
感,但对数据物人顺序异常敏感,且只能处理凸形或球形边界聚类。
3.3 BIRCH算法(层次方法)
BIRCH算法即平衡迭代削减聚类法,其核心是用一个聚类特征3元组表示一个簇的有关信息,从而使一簇点的表示可用对应的聚类特征,而不必用具体的一
组点来表示。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。BIRCH算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运
算。算法的聚类特征树是一个具有两个参数分枝因子B和类直径T的高度平衡树。分枝因子规定了树的每个节点子女的最多个数,而类直径体现了对一类点的直径大
小的限制即这些点在多大范围内可以聚为一类,非叶子结点为它的子女的最大关键字,可以根据这些关键字进行插人索引,它总结了其子女的信息。
聚类特征树可以动态构造,因此不要求所有数据读人内存,而可以在外存上逐个读人。新的数据项总是插人到树中与该数据距离最近的叶子中。如果插人后使得
该叶子的直径大于类直径T,则把该叶子节点分裂。其它叶子结点也需要检查是否超过分枝因子来判断其分裂与否,直至该数据插入到叶子中,并且满足不超过类直
径,而每个非叶子节点的子女个数不大于分枝因子。算法还可以通过改变类直径修改特征树大小,控制其占内存容量。
BIRCH算法通过一次扫描就可以进行较好的聚类,由此可见,该算法适合于大数据量。对于给定的M兆内存空间,其空间复杂度为O(M),时间间复杂度
为O(dNBlnB(M/P)).其中d为维数,N为节点数,P为内存页的大小,B为由P决定的分枝因子。I/O花费与数据量成线性关系。BIRCH算法
只适用于类的分布呈凸形及球形的情况,并且由于BIRCH算法需提供正确的聚类个数和簇直径限制,对不可视的高维数据不可行。
3.4 CURE算法(层次方法)
CURE算法即使用代表点的聚类方法。该算法先把每个数据点看成一类,然后合并距离最近的类直至类个数为所要求的个数为止。CURE算法将传统对类的
表示方法进行了改进,回避了用所有点或用中心和半径来表示一个类,而是从每一个类中抽取固定数量、分布较好的点作为描述此类的代表点,并将这些点乘以一个
适当的收缩因子,使它们更靠近类的中心点。将一个类用代表点表示,使得类的外延可以向非球形的形状扩展,从而可调整类的形状以表达那些非球形的类。另外,
收缩因子的使用减小了嗓音对聚类的影响。CURE算法采用随机抽样与分割相结合的办法来提高算法的空间和时间效率,并且在算法中用了堆和K-d树结构来提
高算法效率。
3.5 DBSCAN算法(基于密度的方法)
DBSCAN算法即基于密度的聚类算法。该算法利用类的密度连通性可以快速发现任意形状的类。其基本思想是:对于一个类中的每个对象,在其给定半径的
领域中包含的对象不能少于某一给定的最小数目。在DBSCAN算法中,发现一个类的过程是基于这样的事实:一个类能够被其中的任意一个核心对象所确定。为
了发现一个类,DBSCAN先从对象集D中找到任意一对象P,并查找D中关于关径Eps和最小对象数Minpts的从P密度可达的所有对象。如果P是核心
对象,即半径为Eps的P的邻域中包含的对象不少于Minpts,则根据算法,可以找到一个关于参数Eps和Minpts的类。如果P是一个边界点,则半
径为Eps的P邻域包含的对象少于Minpts,P被暂时标注为噪声点。然后,DBSCAN处理D中的下一个对象。
密度可达对象的获取是通过不断执行区域查询来实现的。一个区域查询返回指定区域中的所有对象。为了有效地执行区域查询,DBSCAN算法使用了空间查
询R-树结构。在进行聚类前,必须建立针对所有数据的R*-树。另外,DBSCAN要求用户指定一个全局参数Eps(为了减少计算量,预先确定参数
Minpts)。为了确定取值,DBSCAN计算任意对象与它的第k个最临近的对象之间的距离。然后,根据求得的距离由小到大排序,并绘出排序后的图,称
做k-dist图。k-dist图中的横坐标表示数据对象与它的第k个最近的对象间的距离;纵坐标为对应于某一k-dist距离值的数据对象的个数。
R*-树的建立和k-dist图的绘制非常消耗时间。此外,为了得到较好的聚类结果,用户必须根据k-dist图,通过试探选定一个比较合适的Eps值。
DBSCAN算法不进行任何的预处理而直接对整个数据集进行聚类操作。当数据量非常大时,就必须有大内存量支持,I/O消耗也非常大。其时间复杂度为
O(nlogn)(n为数据量),聚类过程的大部分时间用在区域查询操作上。DBSCAN算法对参数Eps及Minpts非常敏感,且这两个参数很难确定。
3.6 CLIQUE算法(综合了基于密度和基于网格的算法)
CLIQUE算法即自动子空间聚类算法。该算法利用自顶向上方法求出各个子空间的聚类单元。CLUQUE算法主要用于找出在高维数据空间中存在的低维
聚类。为了求出d维空间聚类,必须组合给出所有d-1维子空间的聚类,导致其算法的空间和时间效率都较低,而且要求用户输入两个参数:数据取值空间等间隔
距离和密度阔值。这2个参数与样木数据紧密相关,用户一般难以确定。CLIQUE算法对数据输人顺序不敏感。
4 总结
基于上述分析,我们得到各聚类算法的比较结果,结论如下:
算法 算法效率 适合的数据类型 发现的聚类类型 对脏数据或异常数据的敏感性 对数据输入顺序的敏感性
BIRCH 高 数值 凸形或球形 不敏感 不太敏感
DBSCAN 一般 数值 任意形状 敏感 敏感
CURE 较高 数值 任意形状 不敏感 不太敏感
K-poto 一般 数值和符号 凸形或球形 敏感 一般
CLARANS 较低 数值 凸形或球形 不敏感 非常敏感
CUQUE 较低 数值 凸形或球形 一般 不敏感
由于每个方法都有其特点和不同的适用领域,在数据挖掘中,用户应该根据实际需要选择恰当的聚类算法。
数据分析咨询请扫描二维码
CDA数据分析师在中国航信高科技产业园进行了面向测试度量的数据分析培训课程,培训人数近2 ...
2024-05-01CDA数据分析师走进深圳迈瑞生物医疗电子股份有限公司,在迈瑞总部展开了为期两天的培训,本次课程参训人员线上及线下近百人, ...
2024-05-01CDA数据分析师在合肥市对合肥阳光新能源科技有限公司开展了为期8天的企业内训。 合肥阳光新能源科技 ...
2024-05-01CDA数据分析师走进海尔大学,进行了《数据治理与数据中台建设的道与术》专题培训,培训现场爆满,近百人参加了此次培训。 ...
2024-05-01在中国银行苏州分行培训中心开始数据分析师培训,此次培训课程共10天内容,包括Excel、MySQL、概率论与数理统计、SPSS等内容, ...
2024-05-01从实际的业务需求出发,结合行业的典型应用特点,围绕实际的商业问题,探讨数据挖掘、机器学习模型在金融领域的应用,包括获客、信用评分、细分画像、交叉销售、反欺诈、违规识别、时序预测、运筹优化、流程挖掘九个方面,形成 ...
2024-05-01本次培训课程为线上+线下的模式,由于学员编程能力不一、部分学员没有编程基础,故提供统计学、python基 ...
2024-05-01华夏银行信用卡中心-机器学习培训 1、课程亮点 取材于业界一流企业和顶级咨询公司的行业实践;已经被证明是人人 ...
2024-05-01主 题:数据中台建设及数据分析应用主题分享 1. 数据中台市场洞察 2. 主流数据中台产品比较 3. 某企业数据中 ...
2024-05-01围绕“数据驱动”战略,全力打造我行 300 人数字化人才梯队,着力培养数字化管理人才、大数据专业团队 ...
2024-05-01在当今数据驱动的商业环境中,数据分析成为了企业决策的重要依据。通过对大量数据的收集、处理和分析,企业能够更好地理解市场 ...
2024-04-29在人工智能(AI)的世界里,提示词(Prompt)是一种强大的工具,它能够引导AI按照用户的需求产生特定的输出。本文将深入探讨AI ...
2024-04-29CDA立足未来职场,拓展前沿视野——对外经贸大学保险学院举办“三全育人大讲堂”分享行业最新动态。 ...
2024-04-294月2日,CDA数据分析师创始发起人兼协会理事长赵坚毅博士受邀在浙江万里学院举办了一场以“数字化能力在职场中的作用” ...
2024-04-29随机森林(Random Forests)现在机器学习中比较火的一个算法,是一种基于Bagging的集成学习方法,能够很好地处理分类和回归的问 ...
2022-12-23方差分析是数据分析中常用的一种统计分析方法,接下来让我们简单了解一下方差分析的基本思想和原理吧。 方差分析(Analysis ...
2022-12-23来源:关于数据分析与可视化 关于streamlit-aggrid 数据排序 表格样式的调整 数据 ...
2022-08-03作者:麦叔 定义 「把上面晦涩的概念汇成一句话就是:」 ❝ 回调函数就是一个被作为参 ...
2022-08-03现今,高学历人群日益增多,物以稀为贵的高学历光环淡去。无论本科生还是研究生,甚至博士生,求职竞争力都大不如前,就业压力越来越大。
2022-06-01某家企业10个人面试,有9个本科生……如何脱颖而出,除得体的举止和良好的沟通力外,证书成重要筹码,这也是很多人考证的关键所在。
2022-04-14