子空间聚类改进算法研究综述

　　第27卷　第5期

文章编号:1006-9348(2010)05-0174-04

计　算　机　仿　真

2010年5月　　

子空间聚类改进算法研究综述

李　霞

1,2

,徐树维

2

(1.同济大学建筑与城市规划学院,上海200092;2.河南大学计算中心,河南开封475001)

摘要:高维数据聚类是聚类技术的难点和重点,子空间聚类是实现高维数据集聚类的有效途径。CLIQUE算法是最早提出的基于密度和网格的子空间聚类算法,自动子空间聚类算法的实用性和高效性,带来了子空间聚类算法的空前发展。深入分析CLIQUE算法的优点和局限性;介绍了一些近几年提出的子空间聚类算法,并针对CLIQUE,聚类的效率和精确性得到了提高;关键词:数据挖掘;聚类;高位数据集;子空间中图分类号:TP311　　文献标识码:A

ingAlgorithms

ResearchBasedonCLIQUE

LIXia

1,2

,XUShu-wei

2

(1.CollegeofArchitectureandUrbanPlanning,TongjiUniversity,Shanghai200092,China;

2.ComputerCenter,HenanUniversity,KaifengHenan475001,China)

ABSTRACT:Theclusteringofhighdimensionaldataisakeyprobleminclusteringmethods.Subspaceclusteringisaneffectiveapproachtorealizeclusteringinhighdimensionaldata.Asapioneerdensityandgridbasedclusteringal2gorithm,CLIQUEalgorithmhas,withitspracticalityandhighefficiency,greatlyfacilitatedthedevelopmentofsub2spaceclusteringalgorithm.?Thispaper?analyzesindepththeadvantagesandlimitationsofCLIQUEalgorithmandintroducesseveralsubspaceclusteringalgorithms?putforwardinrecentyearswhichhaveallbeen?updatedto?ad2dressthelimitationsofCLIQUEalgorithmandthereforeimprovedtheefficiencyandaccuracyforclustering.?Inad2dition,thispaperalsodiscussesthedevelopmenttrendofsubspaceclusteringalgorithm.KEYWORDS:Datamining;Clustering;Highdimensionaldatasets;Subspace

1　引言

所谓聚类,就是将一个数据集中的数据进行分组,使得每一组内的数据尽可能相似而不同组内的数据尽可能不同。聚类分析是一项重要的研究课题,在数据挖掘、模式识别、统计数据分析、自然语言理解等领域都有广泛的应用前景。聚类分析同时也是一个具有很强挑战性的领域,它的一些潜在应用对算法提出了特别的要求

[1]

SCAN等。由于高维数据的稀疏性、空空间现象以及维度

[4]

效应的影响,在高维数据空间中使用传统算法会遇到以下问题:①随着维数增长,聚类的时间和空间复杂度迅速上升从而导致算法的性能下降;②高维数据集中存在大量无关的属性,并且在这些不相关的维上十分稀疏,这就使得在所有维中存在簇的可能性几乎为零,所以传统的聚类算法不适合对高维数据进行聚类;③距离函数难于定义,聚类操作的基础是数据对象之间相似性的度量,相似度高的对象归为一类。但在高维情况下距离函数失效,因此必须通过重新定义合适的距离函数或相似性度量函数以避开“维度效应”的影响。

子空间聚类是针对大规模高维数据聚类的有效方法。近年来,国内外的研究大多集中在算法的创新与改进,提出了众多的子空间聚类算法,很少有研究者对这些算法作细致的比较和分析。本文从最具代表性的CLIQUE算法入手,以对CLIQUE算法局限性的改进为基础,将近年来提出的新的子空间聚类算法进行了分类介绍和分析。这些分析研究对

:可扩展性、处理不同数据

类型的能力、发现具有任意形状的聚类的能力、输入参数对领域知识的最小限度的依赖性、能够处理异常数据的能力、数据输入顺序对聚类结果的不敏感性、处理高维数据的能力、基于约束的聚类以及聚类结果的可解释性和可用性。

迄今为止,仅仅数据库界的研究人员就已经提出了不少数据聚类算法,比较著名的有CLARANS、BIRCH

[2]

[3]

、DB2

基金项目:河南省教育厅自然科学研究计划项目(2009B50004)收稿日期:2009-03-21　修回日期:2009-04-29

—174—

今后进一步改进CLIQUE算法以及提出新的子空间聚类算法提供了依据和指导。

②发现类:子空间搜索的目的是发现k维空间及其子空间中的密集单元格,将这些密集单元格组成的集合记做D,类发现的目的就是要将D中互相连接的密集单元格聚集在一起,形成q个类D1,D2,…,Dq。CLIQUE算法采用深度优先搜索算法完成类发现,从D中任选一个密集单元格作为当前子空间,为它分配一个类ID,然后分别在不同的维上寻找与当前子空间相邻的单元格,判断该单元格是否为密集的,如果是,则为它们分配同一个类ID,并将该密集单元格作为当前子空间,重复以上过程;如果不是,则从D中任选未访问过的密集单元格,重复以上过程直到所有密集单元格都打上类标签;

③描述类。

2.3.CIQ2　子空间聚类算法CLIQUE

2.1　算法分析

对于高维空间,由于点在空间中的分布比较分散,不太容易形成支持度较高的聚类。所以考虑在某一个子空间中执行聚类分析的任务,而那个子空间会成为要分析的对象,聚类也只能在从低维到高维的迭代过程中自动产生的。为了使计算点的密度的方法简单一些,将数据空间分割成网格

(grid)状(通常是将数据空间中的每一维划分成相同的区间

数来做到的,这就意味着每一个单元具有相同的“体积”,这样单元中点密度的计算可以转换成简单的点计数),然后将落到某个单元中点的个数当成这个单元的密度(density)这时可以指定一个密度阈值,该阈值时,就说这)(cluster)2.2　基本原理

,CL,并且,所有搜索限,而不是引入新的维度,这有利于产生可解释的聚类结果,对于大型数据库中的高维数据的聚类非常有效。它具有如下优点:①它随输入数据的大小线性地扩展,当数据维数增加时具有良好的可伸缩性;②对数据输入顺序不敏感,且无需假设任何规范的数据分布;③聚类结果以简洁的DNF范式表达,具有良好的可解释性。

但是CLIQUE不能自动去除孤立点,并且由于方法大大简化,它也存在着很多的局限性,主要是以下几个方面:①

CLIQUE算法采用固定划分网格的方法,这一方面很容易破

定理1如果S是k维空间的一个类中的数据点集合,那么将S映射到k-1维空间得到S′,则S′将是k-1维空间某个类的子集。

定理2如果S是k-1维空间的数据点集合,但S不属于任何类,那么如果将S扩展到k维空间得到S′,则S′也不可能属于任何类。

定理1和定理2还可以描述为:若一个k维单元是密集的,则其在k-1维空间上的投影也是密集的;若给定的k-1维单元是非密集的,则其在k维空间上的投影必是不密集

坏密集区域的边缘,降低最终结果的准确性,另一方面会导致可能有某一聚类被人为地分割成多个区域,而在覆盖相连的密集单元时又将其相连。使得划分单元的数目增加,在高维情况下,相邻单元的数量以指数级增长,降低了聚类算法的效率;②CLIQUE算法利用最小描述长度技术来进行剪枝,以减少候选密集单元的数目。但是,利用这种技术可能会剪掉一些密集单元,对最终的聚类结果造成影响;③算法中很多步骤都大大简化,以及很多步骤用的是近似算法,因此聚类结果的精确性可能会降低。

的。在高维空间子空间中进行聚类时,可以利用该性质进行“剪枝”,其用法类似于发现关联规则的Apriori算法。一个类是指连接的密集单元的最大集合。

2.3　CLIQUE算法分析2.3.1　CLIQUE算法概述

[5]

CLIQUE(ClusteringInQuest)是IBM的Almaden研究

中心数据挖掘课题的研究成果,是最早的子空间聚类算法。

CLIQUE算法采用了基于网格和密度的方法,能够发现最高

3　改进的子空间聚类算法

近几年的一些新的研究都着眼于对以前算法的进一步改进和寻找新的聚类途径,但是没有一种算法能满足所有的标准,因此,对数据聚类的进一步改进和创新算法仍然任重道远。本文介绍一些针对以上提出的CLIQUE算法的局限性进行改进的新算法。

3.1　基于网格划分的改进

维空间及其子空间存在的类。该算法分为3个步骤:

①子空间搜索:CLIQUE算法采用自底向上法,首先扫描数据库,找出1维空间中的密集单位格,然后根据(k-1)维的密集单位格生成k维空间密集单位格的候选集,该候选集是k维空间密集单位格集合的超集,有关候选集的生成方式详情见文献[6]。得到k维密集单元格的候选集Ck后,逐个查看Ck中的密集单元格在(k-1)维上的映射是否包含于

Ck-1,对于那些在(k-1)维上的映射不被Ck-1包含的密集单

子空间聚类的效率和质量在很大程度上取决于网格划分的精度,网格划分得越精细,聚类效果越好,但同时算法的效率也就越低。因此,构造好的网格划分方法能够显著改进聚类的效率和精度。

3.1.1　MAFIA算法的自适应网格技术

GoilSanjay等提出的MAFIA算法

[7]

元格,根据定理1从Ck中删除以减少下一轮生成候选集的计算量。同时CLIQUE采取基于MDL(minimaldescription

length)的剪枝策略删除某些“兴趣度不大”的子空间,该方法

能够提高算法效率;的网格大小是根据

—175—

数据的分布特性动态调整的,而不是固定的。为减少聚类算法需要处理的网格单元数目,MAFIA将均匀划分网格中每一维上数据分布密度相似的相邻段合并,产生一个不均匀划分的网格。这个网格在数据分布较均匀的区域划分粒度大,在数据分布不均匀的区域划分粒度小,这样可以提高算法的效率和聚类的精度。MAFIA算法利用一种叫做自适应网格划分(AdaptiveGrids)的技术进行网格划分,显著减少了每维上分割的单元数量和候选聚类区域集的数目,同时消除了用于子空间检测的剪枝技术。

如图1所示,CLIQUE所采用的平均分割网格方法将会在聚类发现的每一步过程中,比MAFIA采用的自适应网格划分方法产生更多的候选聚类项集。CLIQUE采用贪心算法来生成相连密集单元的最小覆盖,产生DNF范式。不过在减小复杂度的同时降低了聚类的精度。

则该区间被认为是某一聚类在该维上的投影区间,即一维的聚类区域。

3.1.3　其他基于网格划分的改进算法

文献[10]提出的算法采用单一维边界识别方法区分类:在每一维上都可以通过数据投影的稀疏区域来寻找类的边界,故首先将数据集的每一维在数域上进行等间距的网格划分。通过密度阈值来得到稀疏单元,将相邻的稀疏单元连接起来构成全域范围的稀疏区域。接下来去掉数域两端的区域得到内含边界的稀疏区域,选取这些区域的中点作为类的边界。CGDCP算法[11]在生成凝聚点之后,对数据空重新划分网格单元,,。扩展[],使聚类边界得以很[13]是在每个一维子空间上,将样,利用最优分割区间算法将样本进行区间分割。由此根据样本的分布特性进行分割得到的区间将比等宽分割得到的区间更精确数目更少。对获得的最优分割区间,再采用基于数据集划分的聚类发现算法,得到基于子空间的聚类。

上述算法对子空间网格划分的改进都可以有效地减少候选密集单元的数目,同时省去了覆盖相邻密度单元的步骤,从而加速了算法的执行效率,增强聚类维数升高时算法的可伸缩性,同时也由于更加精确地刻画类边界,提高了聚类结果的精确性。

3.2　基于剪枝方法的改进

CLIQUE算法采用MDL方法对候选密集单元剪枝,这种

图1　(a)固定网格划分(b)自适应网格划分

MAFIA采用的自适应网格划分技术完全根据数据的分

布特性,减少了分割区间数目。MAFIA不需要生成最小覆盖的过程,其结果为DNF范式。

3.1.2　O-cluster算法的最优区间划分技术

Milenova等提出的O-cluster算法

[8]

采用了基于空间数

方法可能剪掉某些重要的密集单元,从而造成聚类的丢失。很多算法都针对CLIQUE算法的剪枝技术进行了改进,以提高聚类的精度。

3.2.1　省略剪枝步骤的算法

据分布的密度信息来选择最优区间划分技术划分网格。

确定区间分割的原则:①必须在样本密度较低的地方进行分割;②每一个分割必须尽可能地将不同聚类分开。第一个限制保证了不会将一个聚类分割到多个区间,第二个限制保证了每一个分割对聚类都是有贡献的。

最优分割区间的大小依赖于样本数据在这一维上的分布特性。根据文献[9],可以得到能够较精确反映分布特性的最少间隔数目,用以建立直方图。对于每一个直方图,采用爬山的方法,从第1个间隔开始,相邻间隔内的样本数进行比较,如果第j个间隔内的样本数小于等于第j+1个间隔内的样本数,则是在爬山,否则是在下山。通过以上方法,确定下一个山谷位置。针对夹在一对山峰中间的每一个山谷,将进行下面的假设检验:

222

χ=2(Vobs-Vexp)/Vexp≥χα,1

一些算法由于采用改进的网格划分技术使得候选密集区域集大大减少,聚类过程中不需要剪枝也能得到较好的聚类速度,聚类精度也得到了提高。3.1中提到的MAFIA、CG2

DCP、OpCluster等算法都省略了对候选密度区域集进行剪枝

的步骤。

3.2.2　改进剪枝方法的算法

CON-CLIQUE(CONstrainedCLIQUE)

[14]

带约束条件的

聚类,是指将特定的领域知识以“约束”的形式表达,并嵌入到聚类过程中的方法,旨在使其能够处理实例对约束条件。算法的基本思路是将约束条件同CLIQUE算法的反单调性质结合起来,共同用于对候选聚类进行“剪枝”操作,减少

CLIQUE算法搜索过程中的“盲目性”,提高其效率和聚类质

(1)

式中,值Vobs等于直方图中山谷的取值,值Vexp等于直方图中山谷取值和较低那个山峰取值的平均值。在实际运用

2

中,通常取95%置信水平(χ.843)。0.05,1=3

量,这对于聚类能更好地应用到现实生活中是很必要的工作。

文献[10]提出了一种基于竞争的修剪方式。基于竞争的修剪主要达到两个目的:①把对聚类生成无贡献的维排

针对满足式(1)的每一个山谷进行有效分割,引入最小密度阈值ρ。对于每一个区间,若其密度大于等于密度阈值,

—176—

除。该方法通过边界识别得到位于各维的类投影,只存在一

个类投影的维对聚类的生成是无贡献的,可以将它修剪掉;②把不能增加贡献的维排除。在搜索过程中会存在一些维与另一些维或者维的组合对聚类生成的贡献相同。对于与单一维的等贡献维可以采取静态的修剪策略,而对于与维的组合是等贡献的维则可以采取动态的修剪策略。最终目的是要得到较好的计算复杂性并生成可完全描述类的最大子空间。显然,这种修剪技术对聚类结果几乎不会造成任何的信息损失。

文献[15]提出了一种基于双向搜索策略的CAHD算法对频繁项目及进行剪枝。一般发现频繁项目集的算法仅利用定理1来剪枝候选项目集,这决定了它们必须使用单向的自底向上搜索策略,而利用定理2可以对数据空间进行自顶向下的搜索,为了尽快发现频繁项目集,算法CAHD采用了[4]　MEster,HPKriegel,JSander,XXu.Adensitybasedalgorithm

fordiscoveringclustersinlargespatialdatabaseswithnoise[C].Proceedingsofthe2ndInternationalConferenceonKnowledgeDis2coveryandDataMining.Portland:AAAIPress,1996.226-231.[5]　RAgrawal,JGehrke,DGunopolos,PRaghavan.Automaticsub2

spaceclusteringofhighdimensionaldatafordataminingapplica2tion[C].ProceedingsoftheACMSIGMODInternationalConfer2enceonManagementofData.Seattle:ACMPress,1998.94-105.

[6]　RakeshAgrawal,RamakrishnanSrikant.Fastalgorithmsformin2

ingassociationrulesinlargedatabases[C].Procofthe20thInt’lConfonVeryLargeDataBases・SanMorganKauf2mann,1994487-499.

[7]l.MAFIA:Efficient

SubspaceDataSets[R].CPDC-TR-9906-019,CenterforandDistributedComputing,NorthwesternUniversity,1999.

[8]　MPWand.Data-basedchoiceofhistogrambinwidth[J].The

AmericanStatistical,1996,51(1):59-64.

[9]　BLMilenova,MMCampos.O-Cluster:Scalableclusteringof

largehighdimensionaldatasets[C].Procof2002IEEEInterna2tionalConferenceonDataMining(ICDM’02)[C].MaebashiCit2y,Japan,2002.290-297.

[10]　何虎翼,姚莉秀,沈红斌,杨杰.一种新的自空间聚类算法

[J].上海交通大学学报,2007,41(5):813-817.

[11]　陈卓,孟庆春,魏振钢,任丽婕,窦金凤.一种基于网格和密度

4　总结

目前聚类算法向着处理更高维数据、更大型数据库的方向发展,算法之间的融合更加紧密。随着聚类分析对象数据集规模的急剧增大,改进现有算法以获得满意的效率受到越来越多的重视,对大规模、高维数据库的高效聚类分析依然是个有待研究的开放问题。本文对CLIQUE算法的聚类功能的优缺点及各种改进算法进行了重点、详细的阐述和对比,并详细介绍和分析了近年来提出的一些子空间聚类新算法,这些新算法努力把静态的聚类推向动态的、适应性强的、带约束条件的及与生活联系紧密的聚类。根据这些新算法的仿真结果,与CLIQUE算法相比,主要优点在于①聚类结果对输入参数敏感性降低;②聚类的效率提高;③聚类效果改善。深入分析和研究CLIQUE算法及其改进算法,开发效率更高的子空间聚类新算法,对解决大规模高维数据的聚类问题具有指导意义。参考文献:

[1]　JiaweiHan,MichelineKamber.数据挖掘:概念与技术[M].北

凝聚点的快速聚类算法[J].哈尔滨工业大学学报,2005,27

(12):1654～1657.

[12]　王生生,刘大有,曹斌,刘杰.一种高维空间数据的子空间聚

类算法[J].计算机应用,2005,25(11):2615-2617.

[13]　周晓云,孙志挥,张柏礼.一种大规模高维数据集的高校聚类

算法[J].应用科学学报,2006,24(4):396-400.

[14]　冯兴杰,黄亚楼.带约束条件的聚类算法研究[J].计算机工

程与应用,2005(7):12-15.

[15]　谢坤武,毕晓玲,叶斌.基于单元区域的高维数据聚类算法

[J].计算机研究与发展,2007,44(9):1618-

1623.

京:机械工业出版社,2001.

[2]　TNgRaymond,JiaweiHan.

Efficientandeffectiveclustering

methodsforspatialdatamining[C].Procofthe20thVLDBCon2ference.Chile,Santiago:[s.n.],1994.144-155.

[3]　TZhang,RRamakrishnan,MLivny.BIRCH:Anefficientdata

clusteringmethodforverylargedatabases[C].Procofthe1996ACMSIGMODInt’lConfonManagementofData[C].Montreal,ACMPress,1996.103-114.

[作者简介]

李　霞(1974-),女(汉族),河南开封人,副教授,

博士生,主要研究领域为数据挖掘与可视化技术;

徐树维(1969-),男(汉族),河南开封人,讲师,博

士生,主要研究领域为网络信息管理技术与信息系统。

—177—

　　第27卷　第5期

文章编号:1006-9348(2010)05-0174-04

计　算　机　仿　真

2010年5月　　

子空间聚类改进算法研究综述

李　霞

1,2

,徐树维

2

(1.同济大学建筑与城市规划学院,上海200092;2.河南大学计算中心,河南开封475001)

摘要:高维数据聚类是聚类技术的难点和重点,子空间聚类是实现高维数据集聚类的有效途径。CLIQUE算法是最早提出的基于密度和网格的子空间聚类算法,自动子空间聚类算法的实用性和高效性,带来了子空间聚类算法的空前发展。深入分析CLIQUE算法的优点和局限性;介绍了一些近几年提出的子空间聚类算法,并针对CLIQUE,聚类的效率和精确性得到了提高;关键词:数据挖掘;聚类;高位数据集;子空间中图分类号:TP311　　文献标识码:A

ingAlgorithms

ResearchBasedonCLIQUE

LIXia

1,2

,XUShu-wei

2

(1.CollegeofArchitectureandUrbanPlanning,TongjiUniversity,Shanghai200092,China;

2.ComputerCenter,HenanUniversity,KaifengHenan475001,China)

ABSTRACT:Theclusteringofhighdimensionaldataisakeyprobleminclusteringmethods.Subspaceclusteringisaneffectiveapproachtorealizeclusteringinhighdimensionaldata.Asapioneerdensityandgridbasedclusteringal2gorithm,CLIQUEalgorithmhas,withitspracticalityandhighefficiency,greatlyfacilitatedthedevelopmentofsub2spaceclusteringalgorithm.?Thispaper?analyzesindepththeadvantagesandlimitationsofCLIQUEalgorithmandintroducesseveralsubspaceclusteringalgorithms?putforwardinrecentyearswhichhaveallbeen?updatedto?ad2dressthelimitationsofCLIQUEalgorithmandthereforeimprovedtheefficiencyandaccuracyforclustering.?Inad2dition,thispaperalsodiscussesthedevelopmenttrendofsubspaceclusteringalgorithm.KEYWORDS:Datamining;Clustering;Highdimensionaldatasets;Subspace

1　引言

所谓聚类,就是将一个数据集中的数据进行分组,使得每一组内的数据尽可能相似而不同组内的数据尽可能不同。聚类分析是一项重要的研究课题,在数据挖掘、模式识别、统计数据分析、自然语言理解等领域都有广泛的应用前景。聚类分析同时也是一个具有很强挑战性的领域,它的一些潜在应用对算法提出了特别的要求

[1]

SCAN等。由于高维数据的稀疏性、空空间现象以及维度

[4]

效应的影响,在高维数据空间中使用传统算法会遇到以下问题:①随着维数增长,聚类的时间和空间复杂度迅速上升从而导致算法的性能下降;②高维数据集中存在大量无关的属性,并且在这些不相关的维上十分稀疏,这就使得在所有维中存在簇的可能性几乎为零,所以传统的聚类算法不适合对高维数据进行聚类;③距离函数难于定义,聚类操作的基础是数据对象之间相似性的度量,相似度高的对象归为一类。但在高维情况下距离函数失效,因此必须通过重新定义合适的距离函数或相似性度量函数以避开“维度效应”的影响。

子空间聚类是针对大规模高维数据聚类的有效方法。近年来,国内外的研究大多集中在算法的创新与改进,提出了众多的子空间聚类算法,很少有研究者对这些算法作细致的比较和分析。本文从最具代表性的CLIQUE算法入手,以对CLIQUE算法局限性的改进为基础,将近年来提出的新的子空间聚类算法进行了分类介绍和分析。这些分析研究对

:可扩展性、处理不同数据

类型的能力、发现具有任意形状的聚类的能力、输入参数对领域知识的最小限度的依赖性、能够处理异常数据的能力、数据输入顺序对聚类结果的不敏感性、处理高维数据的能力、基于约束的聚类以及聚类结果的可解释性和可用性。

迄今为止,仅仅数据库界的研究人员就已经提出了不少数据聚类算法,比较著名的有CLARANS、BIRCH

[2]

[3]

、DB2

基金项目:河南省教育厅自然科学研究计划项目(2009B50004)收稿日期:2009-03-21　修回日期:2009-04-29

—174—

今后进一步改进CLIQUE算法以及提出新的子空间聚类算法提供了依据和指导。

②发现类:子空间搜索的目的是发现k维空间及其子空间中的密集单元格,将这些密集单元格组成的集合记做D,类发现的目的就是要将D中互相连接的密集单元格聚集在一起,形成q个类D1,D2,…,Dq。CLIQUE算法采用深度优先搜索算法完成类发现,从D中任选一个密集单元格作为当前子空间,为它分配一个类ID,然后分别在不同的维上寻找与当前子空间相邻的单元格,判断该单元格是否为密集的,如果是,则为它们分配同一个类ID,并将该密集单元格作为当前子空间,重复以上过程;如果不是,则从D中任选未访问过的密集单元格,重复以上过程直到所有密集单元格都打上类标签;

③描述类。

2.3.CIQ2　子空间聚类算法CLIQUE

2.1　算法分析

对于高维空间,由于点在空间中的分布比较分散,不太容易形成支持度较高的聚类。所以考虑在某一个子空间中执行聚类分析的任务,而那个子空间会成为要分析的对象,聚类也只能在从低维到高维的迭代过程中自动产生的。为了使计算点的密度的方法简单一些,将数据空间分割成网格

(grid)状(通常是将数据空间中的每一维划分成相同的区间

数来做到的,这就意味着每一个单元具有相同的“体积”,这样单元中点密度的计算可以转换成简单的点计数),然后将落到某个单元中点的个数当成这个单元的密度(density)这时可以指定一个密度阈值,该阈值时,就说这)(cluster)2.2　基本原理

,CL,并且,所有搜索限,而不是引入新的维度,这有利于产生可解释的聚类结果,对于大型数据库中的高维数据的聚类非常有效。它具有如下优点:①它随输入数据的大小线性地扩展,当数据维数增加时具有良好的可伸缩性;②对数据输入顺序不敏感,且无需假设任何规范的数据分布;③聚类结果以简洁的DNF范式表达,具有良好的可解释性。

但是CLIQUE不能自动去除孤立点,并且由于方法大大简化,它也存在着很多的局限性,主要是以下几个方面:①

CLIQUE算法采用固定划分网格的方法,这一方面很容易破

定理1如果S是k维空间的一个类中的数据点集合,那么将S映射到k-1维空间得到S′,则S′将是k-1维空间某个类的子集。

定理2如果S是k-1维空间的数据点集合,但S不属于任何类,那么如果将S扩展到k维空间得到S′,则S′也不可能属于任何类。

定理1和定理2还可以描述为:若一个k维单元是密集的,则其在k-1维空间上的投影也是密集的;若给定的k-1维单元是非密集的,则其在k维空间上的投影必是不密集

坏密集区域的边缘,降低最终结果的准确性,另一方面会导致可能有某一聚类被人为地分割成多个区域,而在覆盖相连的密集单元时又将其相连。使得划分单元的数目增加,在高维情况下,相邻单元的数量以指数级增长,降低了聚类算法的效率;②CLIQUE算法利用最小描述长度技术来进行剪枝,以减少候选密集单元的数目。但是,利用这种技术可能会剪掉一些密集单元,对最终的聚类结果造成影响;③算法中很多步骤都大大简化,以及很多步骤用的是近似算法,因此聚类结果的精确性可能会降低。

的。在高维空间子空间中进行聚类时,可以利用该性质进行“剪枝”,其用法类似于发现关联规则的Apriori算法。一个类是指连接的密集单元的最大集合。

2.3　CLIQUE算法分析2.3.1　CLIQUE算法概述

[5]

CLIQUE(ClusteringInQuest)是IBM的Almaden研究

中心数据挖掘课题的研究成果,是最早的子空间聚类算法。

CLIQUE算法采用了基于网格和密度的方法,能够发现最高

3　改进的子空间聚类算法

近几年的一些新的研究都着眼于对以前算法的进一步改进和寻找新的聚类途径,但是没有一种算法能满足所有的标准,因此,对数据聚类的进一步改进和创新算法仍然任重道远。本文介绍一些针对以上提出的CLIQUE算法的局限性进行改进的新算法。

3.1　基于网格划分的改进

维空间及其子空间存在的类。该算法分为3个步骤:

①子空间搜索:CLIQUE算法采用自底向上法,首先扫描数据库,找出1维空间中的密集单位格,然后根据(k-1)维的密集单位格生成k维空间密集单位格的候选集,该候选集是k维空间密集单位格集合的超集,有关候选集的生成方式详情见文献[6]。得到k维密集单元格的候选集Ck后,逐个查看Ck中的密集单元格在(k-1)维上的映射是否包含于

Ck-1,对于那些在(k-1)维上的映射不被Ck-1包含的密集单

子空间聚类的效率和质量在很大程度上取决于网格划分的精度,网格划分得越精细,聚类效果越好,但同时算法的效率也就越低。因此,构造好的网格划分方法能够显著改进聚类的效率和精度。

3.1.1　MAFIA算法的自适应网格技术

GoilSanjay等提出的MAFIA算法

[7]

元格,根据定理1从Ck中删除以减少下一轮生成候选集的计算量。同时CLIQUE采取基于MDL(minimaldescription

length)的剪枝策略删除某些“兴趣度不大”的子空间,该方法

能够提高算法效率;的网格大小是根据

—175—

数据的分布特性动态调整的,而不是固定的。为减少聚类算法需要处理的网格单元数目,MAFIA将均匀划分网格中每一维上数据分布密度相似的相邻段合并,产生一个不均匀划分的网格。这个网格在数据分布较均匀的区域划分粒度大,在数据分布不均匀的区域划分粒度小,这样可以提高算法的效率和聚类的精度。MAFIA算法利用一种叫做自适应网格划分(AdaptiveGrids)的技术进行网格划分,显著减少了每维上分割的单元数量和候选聚类区域集的数目,同时消除了用于子空间检测的剪枝技术。

如图1所示,CLIQUE所采用的平均分割网格方法将会在聚类发现的每一步过程中,比MAFIA采用的自适应网格划分方法产生更多的候选聚类项集。CLIQUE采用贪心算法来生成相连密集单元的最小覆盖,产生DNF范式。不过在减小复杂度的同时降低了聚类的精度。

则该区间被认为是某一聚类在该维上的投影区间,即一维的聚类区域。

3.1.3　其他基于网格划分的改进算法

文献[10]提出的算法采用单一维边界识别方法区分类:在每一维上都可以通过数据投影的稀疏区域来寻找类的边界,故首先将数据集的每一维在数域上进行等间距的网格划分。通过密度阈值来得到稀疏单元,将相邻的稀疏单元连接起来构成全域范围的稀疏区域。接下来去掉数域两端的区域得到内含边界的稀疏区域,选取这些区域的中点作为类的边界。CGDCP算法[11]在生成凝聚点之后,对数据空重新划分网格单元,,。扩展[],使聚类边界得以很[13]是在每个一维子空间上,将样,利用最优分割区间算法将样本进行区间分割。由此根据样本的分布特性进行分割得到的区间将比等宽分割得到的区间更精确数目更少。对获得的最优分割区间,再采用基于数据集划分的聚类发现算法,得到基于子空间的聚类。

上述算法对子空间网格划分的改进都可以有效地减少候选密集单元的数目,同时省去了覆盖相邻密度单元的步骤,从而加速了算法的执行效率,增强聚类维数升高时算法的可伸缩性,同时也由于更加精确地刻画类边界,提高了聚类结果的精确性。

3.2　基于剪枝方法的改进

CLIQUE算法采用MDL方法对候选密集单元剪枝,这种

图1　(a)固定网格划分(b)自适应网格划分

MAFIA采用的自适应网格划分技术完全根据数据的分

布特性,减少了分割区间数目。MAFIA不需要生成最小覆盖的过程,其结果为DNF范式。

3.1.2　O-cluster算法的最优区间划分技术

Milenova等提出的O-cluster算法

[8]

采用了基于空间数

方法可能剪掉某些重要的密集单元,从而造成聚类的丢失。很多算法都针对CLIQUE算法的剪枝技术进行了改进,以提高聚类的精度。

3.2.1　省略剪枝步骤的算法

据分布的密度信息来选择最优区间划分技术划分网格。

确定区间分割的原则:①必须在样本密度较低的地方进行分割;②每一个分割必须尽可能地将不同聚类分开。第一个限制保证了不会将一个聚类分割到多个区间,第二个限制保证了每一个分割对聚类都是有贡献的。

最优分割区间的大小依赖于样本数据在这一维上的分布特性。根据文献[9],可以得到能够较精确反映分布特性的最少间隔数目,用以建立直方图。对于每一个直方图,采用爬山的方法,从第1个间隔开始,相邻间隔内的样本数进行比较,如果第j个间隔内的样本数小于等于第j+1个间隔内的样本数,则是在爬山,否则是在下山。通过以上方法,确定下一个山谷位置。针对夹在一对山峰中间的每一个山谷,将进行下面的假设检验:

222

χ=2(Vobs-Vexp)/Vexp≥χα,1

一些算法由于采用改进的网格划分技术使得候选密集区域集大大减少,聚类过程中不需要剪枝也能得到较好的聚类速度,聚类精度也得到了提高。3.1中提到的MAFIA、CG2

DCP、OpCluster等算法都省略了对候选密度区域集进行剪枝

的步骤。

3.2.2　改进剪枝方法的算法

CON-CLIQUE(CONstrainedCLIQUE)

[14]

带约束条件的

聚类,是指将特定的领域知识以“约束”的形式表达,并嵌入到聚类过程中的方法,旨在使其能够处理实例对约束条件。算法的基本思路是将约束条件同CLIQUE算法的反单调性质结合起来,共同用于对候选聚类进行“剪枝”操作,减少

CLIQUE算法搜索过程中的“盲目性”,提高其效率和聚类质

(1)

式中,值Vobs等于直方图中山谷的取值,值Vexp等于直方图中山谷取值和较低那个山峰取值的平均值。在实际运用

2

中,通常取95%置信水平(χ.843)。0.05,1=3

量,这对于聚类能更好地应用到现实生活中是很必要的工作。

文献[10]提出了一种基于竞争的修剪方式。基于竞争的修剪主要达到两个目的:①把对聚类生成无贡献的维排

针对满足式(1)的每一个山谷进行有效分割,引入最小密度阈值ρ。对于每一个区间,若其密度大于等于密度阈值,

—176—

除。该方法通过边界识别得到位于各维的类投影,只存在一

个类投影的维对聚类的生成是无贡献的,可以将它修剪掉;②把不能增加贡献的维排除。在搜索过程中会存在一些维与另一些维或者维的组合对聚类生成的贡献相同。对于与单一维的等贡献维可以采取静态的修剪策略,而对于与维的组合是等贡献的维则可以采取动态的修剪策略。最终目的是要得到较好的计算复杂性并生成可完全描述类的最大子空间。显然,这种修剪技术对聚类结果几乎不会造成任何的信息损失。

文献[15]提出了一种基于双向搜索策略的CAHD算法对频繁项目及进行剪枝。一般发现频繁项目集的算法仅利用定理1来剪枝候选项目集,这决定了它们必须使用单向的自底向上搜索策略,而利用定理2可以对数据空间进行自顶向下的搜索,为了尽快发现频繁项目集,算法CAHD采用了[4]　MEster,HPKriegel,JSander,XXu.Adensitybasedalgorithm

fordiscoveringclustersinlargespatialdatabaseswithnoise[C].Proceedingsofthe2ndInternationalConferenceonKnowledgeDis2coveryandDataMining.Portland:AAAIPress,1996.226-231.[5]　RAgrawal,JGehrke,DGunopolos,PRaghavan.Automaticsub2

spaceclusteringofhighdimensionaldatafordataminingapplica2tion[C].ProceedingsoftheACMSIGMODInternationalConfer2enceonManagementofData.Seattle:ACMPress,1998.94-105.

[6]　RakeshAgrawal,RamakrishnanSrikant.Fastalgorithmsformin2

ingassociationrulesinlargedatabases[C].Procofthe20thInt’lConfonVeryLargeDataBases・SanMorganKauf2mann,1994487-499.

[7]l.MAFIA:Efficient

SubspaceDataSets[R].CPDC-TR-9906-019,CenterforandDistributedComputing,NorthwesternUniversity,1999.

[8]　MPWand.Data-basedchoiceofhistogrambinwidth[J].The

AmericanStatistical,1996,51(1):59-64.

[9]　BLMilenova,MMCampos.O-Cluster:Scalableclusteringof

largehighdimensionaldatasets[C].Procof2002IEEEInterna2tionalConferenceonDataMining(ICDM’02)[C].MaebashiCit2y,Japan,2002.290-297.

[10]　何虎翼,姚莉秀,沈红斌,杨杰.一种新的自空间聚类算法

[J].上海交通大学学报,2007,41(5):813-817.

[11]　陈卓,孟庆春,魏振钢,任丽婕,窦金凤.一种基于网格和密度

4　总结

目前聚类算法向着处理更高维数据、更大型数据库的方向发展,算法之间的融合更加紧密。随着聚类分析对象数据集规模的急剧增大,改进现有算法以获得满意的效率受到越来越多的重视,对大规模、高维数据库的高效聚类分析依然是个有待研究的开放问题。本文对CLIQUE算法的聚类功能的优缺点及各种改进算法进行了重点、详细的阐述和对比,并详细介绍和分析了近年来提出的一些子空间聚类新算法,这些新算法努力把静态的聚类推向动态的、适应性强的、带约束条件的及与生活联系紧密的聚类。根据这些新算法的仿真结果,与CLIQUE算法相比,主要优点在于①聚类结果对输入参数敏感性降低;②聚类的效率提高;③聚类效果改善。深入分析和研究CLIQUE算法及其改进算法,开发效率更高的子空间聚类新算法,对解决大规模高维数据的聚类问题具有指导意义。参考文献:

[1]　JiaweiHan,MichelineKamber.数据挖掘:概念与技术[M].北

凝聚点的快速聚类算法[J].哈尔滨工业大学学报,2005,27

(12):1654～1657.

[12]　王生生,刘大有,曹斌,刘杰.一种高维空间数据的子空间聚

类算法[J].计算机应用,2005,25(11):2615-2617.

[13]　周晓云,孙志挥,张柏礼.一种大规模高维数据集的高校聚类

算法[J].应用科学学报,2006,24(4):396-400.

[14]　冯兴杰,黄亚楼.带约束条件的聚类算法研究[J].计算机工

程与应用,2005(7):12-15.

[15]　谢坤武,毕晓玲,叶斌.基于单元区域的高维数据聚类算法

[J].计算机研究与发展,2007,44(9):1618-

1623.

京:机械工业出版社,2001.

[2]　TNgRaymond,JiaweiHan.

Efficientandeffectiveclustering

methodsforspatialdatamining[C].Procofthe20thVLDBCon2ference.Chile,Santiago:[s.n.],1994.144-155.

[3]　TZhang,RRamakrishnan,MLivny.BIRCH:Anefficientdata

clusteringmethodforverylargedatabases[C].Procofthe1996ACMSIGMODInt’lConfonManagementofData[C].Montreal,ACMPress,1996.103-114.

[作者简介]

李　霞(1974-),女(汉族),河南开封人,副教授,

博士生,主要研究领域为数据挖掘与可视化技术;

徐树维(1969-),男(汉族),河南开封人,讲师,博

士生,主要研究领域为网络信息管理技术与信息系统。

—177—