基于网格的聚类方法研究

1、基于网格的聚类方法研究摘要:已有的聚类算法对于发现任意形状的聚类和处理离群点效果不理想,分析了现有基于网格的聚类算法。使用网格方法的数据分析方法将空间划分为由(超)矩形网格单元组成的网格,然后在网格单元上进展聚类。最后,总结全文并提出基于网格的聚类需要进一步研究的方向。关键词:数据挖掘;网格;聚类1引言数据挖掘是指从大型数据库或数据仓库中提取隐含的、未知的及有应用价值的信息或形式。它是数据库研究中的一个很有应用价值的领域,交融了数据库、机器学习、统计学等多个领域的理论和技术1。聚类分析是数据挖掘中广为研究的课题之一,是从数据中寻找数据间的相似性,并依此对数据进展分类,从而发现数据中隐含的有用信

2、息或知识。目前已经提出了不少数据聚类算法,其中比拟著名的有larans2、birh3、dbsan4和lique5等。但对于高维、大规模数据库的高效聚类分析仍然是一个有待研究的开放问题。网格方法是空间数据处理中常用的将空间数据离散化的方法。基于网格的聚类算法由于易于增量实现和进展高维数据处理而被广泛应用于聚类算法中。研究人员已经提出了很多基于网格的聚类算法,包括sting6,它利用了存储在网格单元中的统计信息;aveluster7它用一种小波转换方法来聚类数据对象;lique在高维数据空间中基于网格和密度的聚类方法等。本文对已有的基于网格的聚类算法进展了研究,从网格的表示,划分网格单元的方法,到

3、统计网格内信息,搜索近邻网格单元,聚类超过指定阙值的网格单元的各个步骤进展了分析,最后对基于网格方法聚类的研究方向做了展望。2网格的定义与划分网格的根本概念,设a1,a2,ar是数据集=1,2,n中数据对象的r个属性的有界定义域,那=a1a2ar就是一个r维空间,将a1,a2,ar看成是的维(属性、字段),那么对于一个包含n个数据点的r维空间中的数据集=1,2,n,其中i=i1,i2,ir(i=1,2,n),i的第j个分量ijaj。将的每一维等分,即把分割成个网格单元。基于网格聚类算法的第一步是划分网格构造,按搜索子空间的策略不同,主要有基于由底向上网格划分方法的算法和基于自顶向下网格划分方法

4、的算法。2.1由底向上的划分方法由底向上的网格划分方法按照用户输入的划分参数(即每维段数ki,1id),将数据空间均匀划分为相等大小的网格单元,假设落入同一网格单元内的所有数据点都属于同一个簇,每个网格单元保存落入其内数据的统计信息,比方数据点个数,数据点之和。包含一定数目数据点的网格单元被称为高密度网格单元。aveluster与lique是采用由底向上网格划分方法的代表性算法。aveluster处理低维空间数据,它的性能超越了birh、larans,与dbsan等优秀的聚类算法15。lique考虑了高维子空间聚类,但它的时间复杂度较高,需要用户指定全局密度阈值。算法afia8对lique进展

5、了改良,为了减少聚类算法需要处理的网格单元数目,afia将均匀划分网格中每一维上数据分布密度相似的相邻段合并,由此得到一个不均匀划分的网格。这个网格在数据分布较均匀的区域划分粒度大,在数据分布不均匀的区域划分粒度小,这种不均匀划分网格的方法可以进步聚类的质量,被后续的许多算法所采用。采用由底向上的网格划分方法的优点在于,它能通过对数据的一遍扫描,将数据压缩到一个网格数据构造内,并基于这个网格数据构造,发现任意形状的簇。此外,假如网格单元的粒度较小(即体积较小),那么得到的聚簇的精度较高,但是算法的计算复杂度较大。此外,由底向上的网格方法存在不合适处理高维数据的问题。在高维空间,数据的分布是非常

6、稀疏的,网格方法失去其压缩作用,而且属于同一个簇的高密度网格单元也可能不相连,这使聚类算法不能发现合理数目的簇。2.2自顶向下的划分方法自顶向下的网格划分方法采取分治的策略(divideandnquerpriniple),对数据空间进展递归划分,使问题的规模不断减校首先将原数据空间划分为几个较大的区域。对于每个得到的区域,划分过程反复执行,直到每个区域包含属于同一个簇的数据点,那么这些区域就是最终的网格单元。基于自顶向下网格方法的聚类算法直接将高密度网格单元识别为一个簇,或是将相连的高密度网格单元识别为簇。ptigrid9与ltree10是两个典型的基于自顶向下网格划分方法的聚类算法。其中,p

7、tigrid那么是用空间数据分布的密度信息来选择最优划分。通过一个密度函数来决定切割平面,可以将数据空间划分为规那么的或不规那么单元,与传统的等间距的划分相比,可以用此来解决高维聚类的问题。而ltree用划分后的信息增益来选取最优划分。自顶向下划分方法的主要优点在于不需要用户指定划分参数,而是根据数据的分布对空间进展划分,因此这种划分更为合理。数据空间维度对自顶向下网格方法的影响较小,可以快速将大型高维数据集中的簇分隔开。这一类方法的计算复杂度与数据集大小和维度都呈线性关系合适于处理高维数据。由于划分是基于数据分布的,而通常认为噪音是在整个空间均匀分布的,所以自顶向下划分方法对噪音不敏感。但是

8、,由于这种方法得到的网格单元的体积远大于由底向上网格方法中的网格单元体积,因此方法产生的簇的描绘精度比由底向上的网格方法得到的簇的描绘精度要低。而且在自顶向下的划分过程中,同一个簇可能被划分到不同的区域中,最终得到的同一区域也可能包含不同的簇,这样就进一步降低了算法的正确度。这类划分方法的另一个缺点是它在划分过程中,需要对数据集进展屡次扫描。而由底向上划分方法在于只需对数据集进展一次线性扫描以及较高的簇的描绘精度。因此,两类方法适用于不同的问题。前者适于处理高维数据集,后者能有效处理存取代价较大的超大型数据集与动态数据。3基于网格的聚类过程基于网格的聚类算法的根本过程是,首先将数据空间划分为网

9、格单元,将数据对象集映射到网格单元中,并计算每个单元的密度。根据用户输入的密度阈值inpts判断每个网格单元是否为高密度单元,由邻近的稠密单元组形成簇11,如表1。算法1中的步骤1已经在上文详细说明,下面详细介绍步骤2-4的内容。3.1网格单元的密度簇就是一个区域,该区域中的点的密度大于与之相邻的区域。在网格数据构造中,由于每个网格单元都有一样的体积,因此网格单元中数据点的密度即是落到单元中的点的个数。据此可以得到稠密网格单元的密度是,设在某一时刻t一个网格单元的密度为density,定义density=单元内的数据点数/数据空间中总的数据点数,设密度阈值为,为用户输入的密度阙值,当densi

10、ty时,该网格单元是个密集网格单元。相对于稠密网格单元来说,大多数的网格单元包含非常少甚至空的的数据,这一类网格单元被称为稀疏网格单元。大量的稀疏网格单元的存在会极大的降低聚类的速度,需要在聚类之前对稀疏网格单元进展处理,定义稀疏密度阈值为,当density时,该网格单元是个稀疏单元。对于稀疏网格单元的处理方法一般采用压缩的方法或者直接删除的方法,假如需要保存稀疏网格单元用于后续处理,可以使用压缩的方法;假如在现有数据的根底之上直接聚类,可以删除稀疏网格单元,理论分析和实验证明删除稀疏网格单元并不影响聚类的质量12。3.2由稠密网格单元形成簇在基于网格的聚类算法中,根据以上分析,由邻接的稠密单

11、元形成簇是相对直截了当的,这也是基于网格的方法的优点之一。但是需要首先定义邻接单元的含义。设n维空问中的存在任意两个网格单元u1和u2,当这两个网格单元在个维上有交集或是具有一个公共面时,称它们为邻接网格单元。在二维空间中,比拟常使用的是4-nnetin相邻定义和8-nnetin相邻定义(如图1),4-nnetin更合适在聚类算法中使用。因为当寻找某个网格单元的邻居时,在4-nnetin定义下,一个网格单元只有2d个邻居,而在8-nnetin定义下,有3d-1个邻居,当数据维度d较大时,这个数目非常大。使用4-nnetin不仅参与计算的单元数目大为减少,而且单元增加与维数的关系由指数增长变为线

12、性增长,所以能进一步减少算法运行所需的时间,具有较低的计算复杂度13。其外,只有在非常特殊的情况下,使用4-nnetin定义得到的聚类结果才会与使用8-nnetin定义得到的聚类结果不同14,这是因为,当4-nnetin的网格单元是高密度网格单元时,四个对角线上的网格单元不管是否是高密度网格单元,都能被正确的聚类;只有当与对角线上的网格单元相邻的2个网格单元同时为空且该单元本身是高密度网格单元时,不能正确聚类,在划分网格时,通常都要求网格单元的大小远小于簇的大小,因此可以认为这种情况出现的可能很校4结论及展望基于网格聚类方法的优点是它的处理速度快,因为其速度与数据对象的个数无关,而只依赖于数据

13、空间中每个维上单元的个数,发现任意形状、任意大小的簇、计算结果与数据输入顺序无关、计算时间与数据量无关,同时不要求像k均值一样预先指定簇个数等。但是,基于网格方法的聚类算法的输入参数对聚类结果影响较大,而且这些参数较难设置。当数据中有噪音时,假如不加特殊处理,算法的聚类质量会很差。而且,算法对于数据维度的可伸缩性较差。基于网格的聚类方法目前还存在一些急需解决的问题,主要有以下几点:(1)当簇具有不同的密度时,全局的密度参数不能有效发现这样的簇,需要开发具有可变密度参数的算法。(2)对于不同类型数据的聚类问题,比方对于高维数据,网格的数据将急剧增加,需要有效地技术发现近邻单元。(3)当数据集的规

14、模宏大以及数据具有地理分布特性时,需要开发有效的并行算法来进步处理的速度。(4)对现有网格算法的优化,从不同方面进步网格算法的有效性。比方开发稀疏网格的压缩算法、密度相似网格的合并算法等。本文对基于网格的聚类方法的已有研究进展了分析和总结,包括网格的定义与划分方法、网格单元密度确实定、由邻接网格单元形成聚簇的聚类过程;最后对网格聚类方法优点与局限性进展总结,在已有研究分析的根底上,提出后续需要重点解决的问题。参考文献1hens,hanjiaei,yups.dataining:anverviefradatabaseperspetivej.ieeetransnknledgeanddataeng.1

15、996,8(6):866-883.2ngrt,hanj.effiientandeffetivelusteringethdsfrspatialdataining.prfthe20thvldbnferene.hile,santia.1994:144-155.3zhangt,raakrishnanr,livny.aneffiientdatalusteringethdfrverylargedatabases.prfasigdinternatinalnferenenanageentfdata.neyrk:apress,1996:103-114.4ester,kriegelhp,sanderj.adens

16、itybasedalgrithfrdisveringlustersinlargespatialdatabasesithnise.prfthe2ndinternatinalnferenenknledgedisveringindatabasesanddataining.regn,1996:122-128.5agraalr,gehrkej,gunplsd.autatisubspaelusteringfhighdiensinaldatafrdatainingappliatins.prfasigdinternatinalnferenenanageentfdata.neyrk:apress,1998:94

17、-105.6ang,yangj,untzr.sting:astatistialinfratingridapprahtspatialdataining.in:preedingsfthe23rdvldbnferene.athens,greee,1997.186-195.7sheikhleslaig,hatterjees,zhanga.aveluster:aulti-reslutinlusteringapprahfrverylargespatialdatabases.in:preedingsfthe24thvldbnferene.neyrk,usa,1998.428-439.8gils,nagesh

18、h,hudharya.afia:effiientandsalablesubspaelusteringfrverylargedatasets.tehnialreprtn.pd-tr-9906-010,enterfrparallelanddistributedputing,1999.9hinneburga,keida.ptialgrid-lustring:tardsbreakingtheursefdiensinalityinhigh-diensinallustering.in:preedingsfthe25thvldbnferene.1999.506-517.10liub,xiay,yups.lusteringthrughdeisintreenstrutin.in:preedingsftheninthinternatinalnfereneninfratinandknledgeanageent.2000.20-29.11pang-ningtan,ihaelste