数据挖掘中聚类算法比较研究

鞍山钢铁学院学报

Journal of Anshan Institute of I.&S.T echnology

V ol.24N o.5

Oct.,2001数据挖掘中聚类算法比较研究

张红云,石　阳,马　垣

(鞍山钢铁学院计算机科学与工程学院,辽宁鞍山　114002)

摘　要:聚类算法是数据挖掘中的核心技术,虽然聚类算法已被广泛深入的研究,但其应用在数据挖掘领域时间不长,其间产生了许多不同的适用于数据挖掘的聚类算法,但这些算法仅适用于特定的问题及用户.为了更好的使用这些算法,综合提出了评价聚类算法好坏的5个标准,基于这5个标准,对数据挖掘中近几年提出的常用聚类方法作了比较分析,以利于人们更容易、更快速的找到一种适用于特定问题的聚类算法.

关键词:数据挖掘;聚类算法;数据库

中图分类号:TP182　文献标识码:A　文章编号:1000Ο1654(2001)05Ο03Ο05

　　把数据库中的对象集合分割成一组类是数据挖掘的基本操作,(无监督)、聚合和分割、剖析、数据缩减、预测等.其准则是使得属于同一类别的个体间距离尽可能小,不同类别间距离尽可能大.为了找到一个效率高且通用性强的聚类方法,长期以来,人们从不同角度提出了近百种聚类方法.典型的有K-menas方法,K-medoids方法、C LARAN方法、BIRCH方法、DBSC AN方法和C URE方法等.这些算法仅适用于特定的问题及用户.为了更好的使用这些算法,本文综合提出了评价聚类算法好坏的5个标准,基于这5个标准,对数据挖掘中近几年提出的常用聚类方法作了比较分析,以利于人更容易、更快速的找到一种适用于特定问题及用户的聚类算法.

1　数据挖掘中聚类研究及比较框架

　　现存的聚类算法一般分为分割和分层两种.分割聚类算法通过优化一个评价函数把数据集分割为K个部分(K为聚类个数),需要K作为输入参数.典型的分割聚类算法有K-means算法、K-medoids算法、C LARANS算法(K-medoids算法的改进);分层聚类是由不同层次的分割聚类组成,层次之间的分割具有嵌套的关系,不需要K作为输入参数.这是优于分割聚类算法的一个明显的优点,缺点是终止条件必须被具体指定,典型的分层聚类算法是BIRCH算法、DBSC AN算法和C URE算法.

　　在数据挖掘中,最近提出的一阶逻辑决策树可用作分层聚类,一个层次上的所有节点定义了一个例子的分布,并且一个节点的所有子节点定义了相应于那个节点的所有例子的分布.

　　本文对聚类各方法的比较研究基于以下5个标准:(1)是否适用于大数据量,算法的效率要满足大数据集的大数据量、高复杂性、高增量的要求;(2)是否能应付不同的数据类型,至少能处理数值属性和符号属性;(3)是否能发现不同类型的聚类;(4)是否能应付脏数据或异常数据;(5)是否对数据的输入顺序不敏感.

　　下面将在该框架下对各聚类方法作分析比较.

2　数据挖掘领域中常用的聚类方法

211　BIRCH算法(平衡迭代削减聚类法)

　　BIRCH算法的核心是用一个聚类特征三元组CF总结了一个簇个体的有关信息,从而使一簇点的表示可以用对应的聚类特征,而不必用具体的一组点来表示,通过构造满足分支因子和簇直径的聚

收稿日期:2001-06-28.

作者简介:张红云(1973-),女,江苏常州人,讲师.

类特征树来求聚类.描述如下:

　　对于一具有N 个d 维数据点的类{ x i }(i =1,2,…,N ),它的聚类特征向量定义为:

CF =(N ,LS ,SS )

(1)其中N 为类中点的个数;LS 表示N 个点的线性和∑N

i =1x i ,反映了类的重心,SS 为N 个点的平方和∑N i =1 x i 2,反映了类直径大小.

　　此外,对于聚类特征有如下定理.

　　定理1　假设CF 1=(N 1,LS 1,SS 1)与CF 2=(N 2,LS 2,SS 2)分别为两个类的聚类特征,则两个类合并后形成的新类特征为

CF 1+C F 2=N 1+N 2,LS 1+LS 2,SS 1+SS 2(2)

　　该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算.

　　算法的聚类特征树是一个具有两个参数分枝因子B 和类直径T 的高度平衡树.分枝因子规定了树的每个节点子女的最多个数,而类直径体现了对一类点的直径大小的,即这些点在多大范围内可以聚为一类,非叶子结点为它的子女中的最大关键字,可以根据这些关键字进行插入索引,它总结了其子女的信息.

　　聚类特征树可以动态构造,因此不要求所有数据读入内存,而可在外存上逐个读入数据项.新的数据项总是插入到树中与该数据距离最近的叶子中.如果插入后使得该叶子的直径大于类直径T ,则把该叶子节点.其它叶子结点也需要检查是否超过分枝因子来判断其与否,直至该数据插入到叶子中,并且满足不超过类直径,而每个非叶子节点的子女个数不大于分枝因子.可以通过改变类直径大小,修改特征树大小来控制其占内存容量.

　　BIRCH 算法通过一次扫描就可以进行较好的聚类,由此可见,该算法适合于大型数据库.对于给定的M 兆内存空间,其空间复杂度为O (M ),时间复杂度为O dNB ln B M

P ,其中d 为维数,N 为节点数,

P 为内存页的大小,B 为由P 决定的分支因子,I/O 花费与数据库成线性关系.但BIRCH 算法只适用于类的分布呈凸形及球形等情况,并且由于BIRCH 算法需提供正确的聚类个数和簇直径,对不可视的高维数据是不行的.

212　C URE 算法(使用代表点的聚类方法)

　　该算法首先把每个数据点看成一类,然后再合并距离最近的类直至聚类个数为所要求的个数为止.它对传统聚类方法中对类的表示方法进行了改进,回避了用所有点或简单地用中心和半径这样单一条件来表示一个类,而是从每个类中抽取固定数量、分布较好的点作为描述此类的代表点,并将这些点乘以一个适当的收缩因子,使它们更靠近类的中心点.将一个类用多个代表点来表示,就使得聚类的外延可以向非球形的形状扩展,从而可调整聚类的形状以表达那些非球形的类.另外,收缩因子的使用减小了噪音对聚类的影响.同时,C URE 算法采用随机抽样与分割相结合的办法来提高算法的空间和时间效率,并且在该算法中用了堆和K -d 树结构来提高算法效率.

213　DBSC AN 算法(基于高密度的聚类算法)

　　该算法利用类的高密度连通性可以快速发现任意形状的类.其基本思想是:对于一个类中的每个对象,在其给定半径的领域中包含的对象不能少于某一给定的最小数目.在DBSC AN 中,发现一类的过程是基于这样的事实:一个类能够被其中的任意一个核心对象所确定.为了发现一个类,DBSC AN 先从对象集D 中找到任意一对象P ,并查找D 中关于R 和P min 的从P 密度可达的所有对象(其中R 为半径,P min 为最小对象数).如果P 是核心对象,也就是说,半径为R 的P 的领域中包含的对象不少于P min ,则根据算法,可以找到一个关于参数R 和P min 的类.如果P 是一个边界点,则半径为R 的P 领域包含的对

・563・第5期　　　　　　　　张红云,等:数据挖掘中聚类算法比较研究

象数小于P min ,则没有对象从P 密度可达,P 被暂时标注为噪声点,然后,DBSC AN 处理数据库D 中的下一个对象.

　　密度可达对象的获取是通过不断执行区域查询来实现.一个区域查询返回指定区域中的所有对象.为了有效地执行区域查询,DBSC AN 算法使用了空间查询中R 3Ο树结构.在进行聚类前,必须建立针对所有数据的R 3Ο树.另外,DBSC AN 要求用户指定一个全局参数R (为了减少计算量,预先确定参数P min ),为了确定R 值,DBSC AN 计算任意对象与它的第k 个最临近的对象之间的距离.然后,根据求得的距离由小到大进行排序,并给出排序后的图,称做k -dist 图.k -dist 图中的横坐标表示数据对象与它的第k 个最近的对象间的距离;纵坐标则为对应于某一k -dist 距离值的数据对象的个数.R 3Ο树的建立k -dist 图的绘制是非常消耗时间的过程.此外,为了得到较好的聚类结果,用户必须根据k -dist 图,通过试探选定一个比较合适的k -dist 值,即R 值.再就是,DBSC AN 不进行任何的预处理而直接对整个库进行聚类操作.当数据库非常大时,就必须有大内存量支持,I/O 消耗也非常大.其时间复杂度为O (N log N )(N 为数据库中包含对象数目),聚类过程的大部分时间用在区域查询操作上.DBSC AN 对R 及P min 非常敏感,且这两个参数很难确定.

214　K -pototypes 算法

　　该算法结合了K -means 方法和根据K -means 方法改进的能够处理符号属性的K -m odes 方法.K -po 2totypes 算法如下:

　　(1)X ,Y 其属性为A r 1,A r 2,…,A r p ,A c p +1,…,A c m ,其中属性A r 1,A r 2,…,A r p 为数值属性,A c p +1,…,A c m 为

符号属性,则测量它们不相似性的度量如下

d (X ,Y )=

∑P j =1(x j -y j )2+γ∑m

j =p+1δ(x j ,y j )(3)

前一部分基于欧式距离,后一部分基于海明距离,从而既可处理数值属性又可处理符号属性.　　(2)给定一个例子的集合Z 和一个整数k (k ≤n ),该算法将Z 分割为k 个聚类并使得在每个聚类中所有值与该聚类中心距离的总和最小.(每个聚类的聚类中心是每个聚类的均值).该过程可以被描述为如下数学问题

min Q P (W ,Q )=∑k l =1∑n i =1w i ,l ∑p j =1(z i ,j -q l ,j )2+γ∑n i =1w i ,l ∑m

j =p+1δ(z i ,j ,q l ,j )(4)

其中γ为平衡K -means 和K -m odes 的一个参数,W 是一个N ×K 分割矩阵,用以表示每个例子在哪个聚类中,通常它的每一行和为1,Q ={Q 1,Q 2,…,Q K }是聚类结果的集合.

215　C LARANS 算法(随机搜索聚类算法)

　　C LARANS 算法是一种分割而非分层的聚类方法.它首先随机选择一个点作为当前点,然后随机检查它周围不超过参数Maxneighbor 个的一些邻接点,假如找到一个比它更好的邻接点,则把它移入邻接点,否则把该点作为局部最小量.然后,再随机选择一个点来寻找另一个局部最小量,直到所找到的局部最小量数目达到用户要求为止.该算法要求聚类的对象必须预先都调入内存,并且需扫描多次数据库,这对大型数据库而言,无论从时间复杂度还是空间复杂度而言,都是不太适用的.虽后来通过引入R 3Ο树结构对其性能进行改善,使之能够处理基于磁盘的大型数据库,但R 3Ο树的构造和维护代价太大.虽然该算法对脏数据和异常数据不敏感,但对数据输顺序异常敏感,且只能处理凸形或球形边界聚类.216　C LI QUE 算法(自动子空间聚类算法)

　　C LI QUE 算法利用自顶向上方法求出各个子空间的聚类单元.C LI QUE 算法主要用于找出高维数据空间中存在的低维聚类.为了求出d 维空间聚类,则必须组合给出所有d -1维子空间的聚类,导致其算法的空间和时间效率都较低,而且要求用户输入两个参数:数据聚值空间等间隔距离ξ和密度阈值τ.这些数据与样本数据紧密相关,用户一般难以确定.但它对数据的不同顺序不敏感.

・

663・　　　　　　　　　　　　　　鞍山钢铁学院学报　　　　　　　　　　　　　　第24卷

3　结　论

　　基于上述分析,得到聚类各个方法的比较结果,如表1所示.

表1　聚类算法比较

T ab.1　Clustering Method C om paris on

算法效率

适合的数据类型发现的聚类类型对脏数据开异常数据的敏感性对数据输入顺序的敏感性BIRCH

高数值凸形或球形不敏感不太敏感DBSCAN

一般数值任意形状敏感敏感CURE

较高数值任意形状不敏感不太敏感K -prototypes 一般数值和符号

凸形或球形敏感一般C LARANS 较低数值

凸形域球形不敏感非常敏感C LIQUE

较低数值凸形或球形一般不敏感　　由表1可得如下结论:(1)从算法效率、对脏数据或异常数据的敏感性及数据输入顺序的敏感性考虑,BIRCH 算法最好;(2)BIRCH ,C URE 和C LARANS 脏数据或异常数据的不敏感性,但只能发现凸形或球形的聚类;(3)只有K -prototypes 能处理数值和符号的数据;(4)DBSC AN 和C UREC 能发现任意形状的类.

　　由于每个方法都有其优缺点和不同的适用领域,在数据挖掘中,用户应该根据实际需要选择恰当的聚类算法.

参考文献:

[1]　ZH ANG T ,RAM AK RISH NAN R ,LI VNYM.BIRCH :An E fficient Data Clustering Method for very Large Database[A].In :Proc of

the AC M SIG M OD Int ’s C on f on Management of Data[C].M ontreal Canada :AC M Press ,1996.83-94.

[2]　S ANDER F ,ESTER M ,K RIEGE L HP ,X UX.The Alg orithm G DBSC AN and its Applications.Data M ining and K nowledge Discov 2

ery[J ].K LUWER Academic Publishers ,1998,2:178-192.

[3]　Ng RT ,C A LBERS ON J.E fficient and E ffective Clustering Methods for S patial Data M ining[A ].In :P orc of the V LDB C on ference

[C].Santiag o ,Chile ,1994.144-155.

[4]　边肇祺,张学工.模式识别(第二版).聚类技术[M].北京:清华大学出版社,1999.235-247.

[5]　GEHRKE J ,AG RAW A L R ,G UNOPU LOS D.Automatic Subspace Clustering of High Dimensional Data for Data M ining Appli 2

caitons[J ].AC M SI M OD ,1998,72(2):94-105.

[6]　CHRIST OPHER J ,PHI LIP K.Chan ,Systems for K nowledge Discovery in Databases IEEE T tans[J ].On K nowledge and Data Engi 2

neering ,1993,5(6):903-913.

[7]　BET UR V ,DAS ARAEHY.Data M ining and K nowledge Discovery :Theory ,T ool ,and T echnology Ⅱ[A ].Orlando ,Florida 2000

SPIE -The International S ociety for Optical Engineering[C],2000.259-2.

[8]　K RZY SZT OF J Cios ,WIT O LD Pedrycz ,ROM AN W S wingiarski.Data M ining Mehods for K nowledge Discovery [M ].London :

K LUWER AC DE MIC ,1998.1-20.

[9]　M ARTI N Ester ,H ANS -PETER K riegel ,JORG Sander.Incremental Clustering for M ining in a Data Warehousing Environment[A].

Ahsish G upta ,Oded Shmueli ,Jennifer Widom.Proceedings of the T wenty -F ourth Internatal C on ference on Very Large Databses

[C].NEW Y ork :NY US A ,1998.323-333.

[10]　ESTER M ,K RIEGE L H -P ,S ANDER J.A Density -Based Alg orithm for Discovery Clusters in Large S patial Databases with N oise

[A].Proc 2nd Int C on f On K nowledge Discovery and Data M ining[C].P ortland OR ,1996.226-231.

[下转第371页]

・763・第5期　　　　　　　　张红云,等:数据挖掘中聚类算法比较研究

　　各方格的填挖土方量见图3,汇总结果

V e =285m 3

V f =-291m

3ΔV =285-291=6m 3

填挖方基本平衡.

　　实践证明,利用上述公式进行设计面为斜坡面的场地平整时的重心高程和重心定位,是有效的实用公式,对减少土方施工时的盲目性极为有效,而一般资料未见说明,所以值得推广.

参考文献:

[1]　工厂建设测量手册编写组.工厂建设测量手册[M].北京:测绘出版社,1990.363-365.

[2]　邵自修.工程测量[M].北京:冶金工业出版社,1992.83-85.

[3]　石世支.非平行断面的土方量计算[J ].测绘通报,1998(8):26-27.

Locating Center of G ravity of I nclined Construction Field under Levelling

Y ANG Tie-li ,BAI Ping

(High Professional Institute ,Anshan Institute of I.&S.T echnology ,Anshan 114002,China )

Abstract :In ordinary case ,it si not enough to determined the elevation and position of construction field ’s center of gravity for regular shape yard has been considered only.The paper described the theory with determined the irregular shape construction field ’s elevation and the center of gravity for inclined plane yard with coordinating and each square ’s area with weigh ,at last ,the paper give examles of using method of this theory.

K ey Words :sm oothen field ;incline plane ;center of gravity

(R eceived July 11,2001)

[上接第367页]

Comparison of Clustering Methods in Data Mining

ZH ANG Hong-yun ,SHI Yang ,MA yuan

(School of C om puter Science and Engineering ,Anshan Institute of I.&S.T echnology ,Anshan 114002,China )

Abstract :Clustering method is the core technology in data mining.Clustering method has been studied very deeply ,but the time it is used in the field of data mining is not very long.During which occurred many different clustering methods that suit data mining ,however these methods are only suited to special problems and users.In order to use these methods better ,the paper puts forwad five standards according to which we can evaluate these clustering meth 2ods.We com pared and analyzed these clustering methods on the basis of these standards to facilitate finding a clus 2tering m othod that suits a particular problem.

K ey Words :data mining ;clustering method ;database

(R eceived June 28,2001)・173・第5期　　　　　　　　杨铁利,等:斜坡面建筑场地平整时的重心定位