基于改进的凝聚性和分离性的层次聚类算法

JournalofComputerResearchandDevelopmentISSN100021239ΠCN1121777ΠTP

45(Suppl1):202～206,2008

基于改进的凝聚性和分离性的层次聚类算法

郭景峰　赵玉艳　边伟峰　李　晶

(燕山大学信息科学与工程学院　秦皇岛　066004)(jfguo@ysu1edu1cn)

AHierarchicalClusteringAlgorithmBasedonImprovedClusterCohesionandSeparation

GuoJingfeng,ZhaoYuyan,BianWeifeng,andLiJing

(CollageofInformationScienceandEngineering,YanshanUniversity,Qinhuangdao066004)

Abstract　Theclusteringaboutrelationaldatabasesisanactivestudysubjectindatamining1Inthispaper,weintroduceaHierarchicalClusteringAlgorithmBasedonImprovedClusterCohesionandSeparation1First,thisalgorithmjoinseverytablethroughthetupleIDpropagation1Then,groupsobjectsintoalargenumberofrelativelysmallsub2clustersusingthesharednearestneighboralgorithmandtheimprovedclustercohesionalgorithm1Last,findthegenuineclustersbyrepeatedlycombiningthesesub2clustersusingtheimprovedclusterseparationalgorithm1TheexperimentshowstheefficiencyandscalabilityofthisapproachKeywords　sharednearestneighbor;relationaldatabase;hierarchicalclustering;cohesion;separation

摘　要　由于传统的数据聚类算法都是在单一表上进行,因此如何在多表中进行聚类是现在聚类分析的

一个新方向1提出了一种基于改进的凝聚性和分离性的层次聚类算法———ICCSH(ahierarchicalclusteringalgorithmbasedonimprovedclustercohesionandseparation),该算法首先通过ID传播把关系数据库中的各个表联系起来,再通过计算共享最近邻的相似度和改进的凝聚性算法将数据对象聚类为大量相对较小的子聚类,然后通过计算改进的簇间分离性合并子类来找到真正的结果簇1实验表明,该算法不仅运行时间相对较短,具有较强的可伸缩性,还可以得到较高精确的聚类结果1

关键词　共享最近邻;关系数据库;层次聚类;凝聚性;分离性中图法分类号　TP311

　　随着近年来计算机在各行各业的普及应用,人类生成和收集数据的能力在迅速提高,因此人们常说我们处于信息爆炸的时代,现在许多实际的应用,例如信用卡欺诈检测、贷款申请、基因数据分析等都涉及到存储在关系数据库中的多个表中的信息1而由于传统的数据聚类算法都是在单一表上进行,如果对多个表进行聚类,就需要通过连接或者聚合将多个表中的数据结合到一个表中来1但是,在结合的过程中会产生许多问题,例如语义或信息的丢失、数据冗余、结合之后产生的表太大等,使得直接进行

　收稿日期:2007-07-10

　基金项目:国家自然科学基金项目(60673136)

聚类十分困难1可见,传统的数据聚类算法有一定的局限性,这就需要产生一种新的方法对存储在多个表中的数据进行直接聚类,而关系聚类的提出正是为了解决这一问题[1]1

本文提出了一种基于改进的凝聚性和分离性的

层次聚类算法———ICCSH(ahierarchicalclusteringalgorithmbasedonimprovedclustercohesionandseparation)1该算法不仅具有较强的可伸缩性,并且

通过计算凝聚性进一步划分了簇,克服了Chameleon算法不能将已经错误的放在一起的对象分开这一局

郭景峰等:基于改进的凝聚性和分离性的层次聚类算法

203

限性1实验表明,该算法不仅运行时间相对较短,具有较强的可伸缩性,还可以得到较高精确的聚类结果1

1　相关工作

层次聚类方法递归地对对象进行合并或者分裂,直到满足某一终止条件1根据层次的分解方式不同,层次聚类方法可分为凝聚层次聚类和分裂层次聚类两种[2]1凝聚层次聚类采用自底向上策略进行聚类,它从单成员聚类开始,把它们逐渐合并成更大的聚类,在每一层中,相距最近的两个聚类被合并1相反,分裂层次聚类则采用自顶向下的策略,从包含所有对象的一个聚类开始,把它逐渐分解成更小的聚类1典型的层次方法有BIRCH算法CURE算法

[4]

[3]

对象之间的值得到它们的相似性1然而,在某些情

况下,使用这些相似度方法的聚类技术不能产生理想的聚类结果1例如,考虑如下文档集合,它包含取自报纸的不同版块的文章:娱乐、财经、国外、都市、国内、体育1这些文档可以看做高维空间中的向量,其中向量的每个分量(属性)记录词汇表中每个词在文档中的出现次数1对于这个例子(取自洛杉矶时报的文章的集合),表1给出了每个版块和整个文档集的平均余弦相似度:

表1　报纸的不同版块文档之间的相似度

版块娱乐财经国外都市国内体育所有版块平均余弦相似度

01032010300103001021010270103601014、

、ROCK算法

[5]

、Chameleon算法等1

[6]

本文提出的ICCSH算法与Chameleon算法有很多相似之处1Chameleon算法的主要思想是首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类,然后用一个凝聚的层次聚类算法通过反复的合并子类来找到真正的结果簇1这一算法的可伸缩性较差,并且不能将已经错误的放在一起的对象分开,针对这些不足,本文提出了基于改进的凝聚性和分离性的层次聚类算法———ICCSH1该算法不仅具有较强的可伸缩性,而且通过计算凝聚性进一步划分了簇,克服了Chameleon算法不能将已经错误的放在一起的对象分开这一局限性1

2　基于改进的凝聚性和分离性的层次聚类

算法(ICCSH)

　　本文提出了一种基于改进的凝聚性和分离性的层次聚类算法———ICCSH1该算法的主要思想是,首先通过ID传播把关系数据库中的各个表联系起来,再通过计算共享最近邻相似度和本文改进的凝聚性算法将数据对象聚类为大量相对较小的子聚类,然后通过计算改进的簇间分离性合并子类来找到真正的结果簇1

211　共享最近邻(SNN)相似度算法

两个对象之间的相似度(similarity)是这两个对象相似度程度的数值度量,因而,两个对象越相似,它们的相似度就越高1常用的计算相似度的方法有Jaccard系数、广义Jaccard系数、余弦相似度、皮尔

森相关系数等[7]1这些方法都是通过直接计算两个

每个文档与其最相似的文档(第1个最近邻)之

间的相似性高一些,平均为01391然而,同一类中对象之间低相似性的结果是,它们的最近邻也常常不在同一类1在产生表1的文档集合中,大约20%的文档都有不同类中的最近邻1一般来说,如果直接相似度低,则对于聚类,特别是凝聚层次聚类(最近的点放在一起,并且不能再分开),相似度将成为不可靠的指导1尽管如此,一个对象的大多数最近邻通常仍然属于同一个类1基于这一事实,本文引入了一种度量相似性的间接方法———共享最近邻相似度(sharednearestneighborsimilarity),这种方法在定义相似性度量时考虑了点的环境,即只要两个对象都在对方的最近邻列表中,共享最近邻相似度就是它们共享的近邻个数1算法1给出了这一方法的算法描述1

算法11计算共享最近邻相似性1①找出所有点的k2最近邻1

②if两个点x和y不是相互在对方的k2最近邻中,then

③　similarity(x,y)←0④else

⑤　similarity(x,y)←共享的近邻个数1⑥endif

对象之间SNN相似度的相似度图称做SNN相似度图(SNNsimilaritygraph)1图1给出了SNN相

204

计算机研究与发展　2008,45(增刊)

似度计算的图形解释1其中两个黑点都有8个最近

邻,相互包含1这些最近邻中的4个(灰色点)是共享的1因此这两个点之间的SNN相似度为41

性就相对越低,特殊地,当整个数据库中的对象划分为一个簇时凝聚性最好,当一个对象划分为一个簇时分离性最好1为了解决这一问题,我们把簇中的对象数也考虑在内,式(3),(4)分别是改进的凝聚性和分离性公式1其中,Ni和Nj分别指簇i和簇j中的对象数1

cohesion(Ci)=

x∈Ci,y∈Ci∑

similarity(x,y)

,(3)

图1　两个点之间的SNN相似的计算

Ni(Ni-1)Π2

212　改进的凝聚性和分离性算法

separation(Ci,Cj)=

传统的用于评估簇的各方面的评估度量有3

类:非监督的、监督的和相对的1而簇的有效性的非监督度量常常可以进一步分成两类:簇的凝聚性(clustercohesion)和簇的分离性(clusterseparation)1其中簇的凝聚性用于度量确定簇中对象如何密切相关,簇的分离性用于度量确定一个簇如何不同于其他簇[8]1

由于本文使用邻近度图表示对象之间的关系,因此,在这里我们只考虑基于图的凝聚性和分离性1对于基于图的簇,簇的凝聚性可以定义为连接簇内点的邻近度图中边的加权和(本文中边的权值是指边所关联的两个数据对象之间的相似度),如图2(a)所示1类似地,两个簇之间的分离性可以用从一个簇的点到另一个簇的点的边的加权和来度量,如图2(b)所示:

x∈Ci,y∈Cj∑

similarity(x,y)NiNj

,i≠j1

(4)

　　式(3),(4)分别除以簇i及簇i和簇j中的邻近图的边数,改善了凝聚性和分离性对对象数敏感的情况1

213　ID传播

由于传统的数据聚类算法都是在单一表上进行,如果要对多个表进行聚类,需要先将多个表连接成一个表,这样会产生数据丢失或数据冗余,导致最后的聚类结果不精确甚至错误,因此需要提出一种新的方法,可以直接在多个表中进行聚类分析1

2004年,Yin和Han等人在CrossMine分类算法文献[9]中,提出了一种新的方法—ID传播,解决了上面的问题,提高了算法的效率1ID传播技术的核心思想是,数据库中各关系之间只进行一次连接操作,无须像传统聚类技术那样要执行多次连接,在连接同时也无须物化连接结果1

由于原来的ID传播用于分类,本论文对其进行了一些修改,以使其适用于聚类1下面我们简单的介绍一下ID传播121311　基本定义

关系数据库由多个表组成,在此,我们定义其中一个表是目标关系表(例如图3中,目标关系表是Student),其余的表是非目标关系表1每一个关系表有一个主键、多个外键,每一个外键指向其他关系表的主键1

由于关系数据库中往往存在多个表,各个表之间的联系十分复杂,而在关系数据库中表与表之间的连接除了主键和外键之间的连接,其他的连接不能表示对象之间强的语义关系,因此,ID传播方法只考虑下面两种连接类型:

1)连接主键k和指向k的外键;

2)连接外键k1和k2,它们指向同一个主键k1例如图3中,连接Pubish.author2id和Register.student2id1

图2　凝聚性和分离性基于图的观点

从数学上讲,基于图的簇的凝聚性和分离性可以分别用式(1),(2)表示1其中,x,y是数据库中的

对象,Ci是簇的标号,即第i个簇,同样,Cj指第j个簇1

cohesion(Ci)=

x∈Ci,y∈Ci

∑

similarity(x,y),(1)

　separation(Ci,Cj)=

x∈Ci,y∈Cj

∑

similarity(x,y),i≠j1(2)

　　上面这两个公式是传统的计算簇的凝聚性和分离性的公式,从这两个公式可以看出,对于凝聚性,值越高越好,而对于分离性,值越低越好1然而,这两个公式存在着一个问题,即当簇中的对象越多时,这个簇的凝聚性就相对越高,而它与其他簇的分离

郭景峰等:基于改进的凝聚性和分离性的层次聚类算法

205

最小的一条边),重复④,直到所有簇中所含的对象数小于Minsize为止1

⑥计算簇间的分离性,合并分离性最小的簇1⑦重复⑥,直到簇的个数达到要求为止(即最终簇数k)1

在算法2中,前3步的目的是找到初始的簇,④,⑤步通过计算簇的凝聚性,将已经错误的放在一起的对象分开,⑥,⑦步通过计算簇间的分离性,合并相近的两个簇,产生最终的结果簇1

图3　SchemaoftheCSDeptdatabase

21312　ID传播

ID传播实际上是通过某个连接路径p=Rt

󰃞󰃜R1󰃞󰃜…󰃞󰃜Rk,把在目标关系表Rt中的元组与在其他关系表Rk中的元组连接起来1主要思想是,把目标元组的IDs从Rt沿着路径一个接一个地传递到关系表中,以便在连接路径上的每一个关系表Ri中的每一个元组t′与所有与t′相连的目标元组的IDs相联系1沿着连接路径传递完IDs后,IDs被存储在路径上的每一个关联表中,并且可以进一步传递给其他的关联表1

ID传播是一个灵活且有效的方法1IDs能很容易地从一个关系表传播到另一个关系表1这样做,使得位于不同关系表中的元组可以通过较少的冗余计算得到1由于IDs不需要太多额外的存储空间,因此所需的空间也比较小1214　基于改进的凝聚性和分离度的层次聚类算法

本文提出了基于改进的凝聚性和分离性的层次聚类算法———ICCSH,不仅具有较强的可伸缩性,并且通过计算凝聚性进一步划分了簇,克服了Chameleon算法不能将已经错误的放在一起的对象分开这一局限性1该算法的主要思想是,首先通过ID传播把关系数据库中的各个表联系起来,再通过共享最近邻算法和计算簇的凝聚性将数据对象聚类为大量相对较小的子聚类,然后通过计算簇间的分离性合并子类来找到真正的结果簇1该算法的描述如算法2所示1

算法21基于共享最近邻相似性的层次聚类1①通过ID传播把各个表联系起来1

②使用相似度阈值<,稀疏化SNN相似度1③找出稀疏化的SNN相似度图的连通分支(簇)1

④若簇中的对象数大于Minsize,则计算簇的凝聚性1

⑤分离凝聚性最小的簇(即断开该簇中相似性

这一算法涉及到3个参数:相似度阈值<、Minsize和最终簇数k1其中,Minsize用来控制最初聚类结果的粒度1一般来说,Minsize的值小于我们期望发现的簇的大小,另外,Minsize也不能设置得太小,否则会大大增加算法的执行时间,一般Minsize的值应设为整个数据量的1%～5%,相似度阈值和最终簇数则根据用户的具体需要设定1实验表明,对这3个参数的不同设定值,并不会对实验结果产生太大的影响13　实验结果在本节中,我们将描述基于改进的凝聚性和分离性的层次聚类算法———ICCSH的实验结果,并且同Chameleon算法进行比较1

在该实验中,我们使用CSDept数据库(如图4所示),该数据库中的数据由UIUC的CSDept1的网页资源收集得到,包含10个关系表和4505个元组1该实验运行时的硬件配置为,操作系统:WindowsXP;CPU:IntelPentium210GHz;内存512MB;硬盘60GHz1所需的参数设定为Minsize=3%,k=20,ICCSH中的相似度阈值<=2,Chameleon算

法中的α=2101在使用Chameleon算法中,先使用物理连接将所有的表连成一个表1图4和图5给出了随着元组数的增加,ICCSH和Chameleon算法在时间和精度上的变化1

图4　时间变化图

206

[3]

计算机研究与发展　2008,45(增刊)

TZhang,RRamakrishnan,MLivny1BIRCH:Anefficientdataclusteringmethodforverylargedatabases1ACMSIGMODInt’lConfonManagementofData,Montreal,Canada,1996[4]

SGuha,RRastogi,KShim1CURE:Anefficientclusteringalgorithmforlargedatabases1ACMSIGMODInt’lConfonManagementofData,NewYork,1998[5]

SGuha,RRastogi,KShim1ROCK:Arobustclusteringalgorithmforcategoricalattributes1The15thInt’lConfonDataEngineering,Sydney,Australia,1999[6]

GKarypis,EHan,VKumar1Chameleon:Hierarchicalclusteringusingdynamicmodeling1IEEEComputer,1999,32(8):68-75[7][8]

RuiXu,DonaldWunsch1Surveyofclusteringalgorithms1IEEETransonNeuralNetworks,2005,16(3):645-678YZhao,GKarypis1Empiricalandtheoreticalcomparisonsofselectedcriterionfunctionfordocumentclustering1MachineLearning,2004,55(3):311-331[9]

XYin,J

Han,J

Yang,

et

al1CrossMine:

图5　精确度变化图

由图4和图5可以看出,与Chameleon算法相

比,ICCSH不仅运行时间短,具有较强的可伸缩性,并且可以得到较高精确的聚类结果1

4　总　　结

聚类是数据挖掘中的一个活跃研究领域,在数据挖掘中已经开发出许多聚类算法[10]1但是由于传统的聚类算法只是在单一表中寻找相似的对象,而现在非常通用的关系数据库中通常都含有多个表,因此聚类算法的适应性、效率与最优解仍需要得到进一步的研究解决1现有聚类算法还需改进,使之具有增量聚类的能力,并具有较好的伸缩性及效率1本文提出的ICCSH对关系数据库中的表进行了虚拟连接,并且使用改进的计算凝聚性和分离性的公式,使得该算法不仅运行时间短,具有较强的可伸缩性,而且还可以得到较高精确的聚类结果1

参考

[1][2]

Efficient

classificationacrossmultipledatabaserelations12004Int’lConfonDataEngineering,Boston,2004[10]

QianWeining,ZhouAoying1Analyzingpopularclusteringalgorithmsfromdifferentviewpoints1软件学报,2002,13(8):1382-1394　　郭景峰　男,1962年生,博士,教授,主要研究方向为数据库理论及应用、数据挖掘技术、粗糙集理论及应用1　　赵玉艳　女,1982年生,硕士研究生,主要研究方向为数据挖掘、关系聚类(zyy-zuoye@1261com)1

　　边伟峰　男,1981年生,硕士研究生,主要研究方向为关系数据挖掘(bwfbwf1981@1631com)1

文献

　　李　晶　女,1982年生,硕士研究生,主要研究方向为关系数据挖掘(kysbs2005@sina1com)1

JiaweiHan,MichelineKamber1DataMining:ConceptsandTechniques1Beijing:ChinaMachinePress,2006

RichJRoiger,MichaelWGealz1数据挖掘基础教程1北京:

清华大学出版社,2003