文档介绍：基于网格的聚类方法研究摘要:已有的聚类算法对于发现任意形状的聚类和处理离群点效果不理想,分析了现有基于网格的聚类算法。使用网格方法的数据分析方法将空间划分为由(超)矩形网格单元组成的网格,然后在网格单元上进行聚类。最后,总结全文并提出基于网格的聚类需要进一步研究的方向。关键词:数据挖掘;网格;聚类 1引言数据挖掘是指从大型数据库或数据仓库中提取隐含的、未知的及有应用价值的信息或模式。它是数据库研究中的一个很有应用价值的领域,融合了数据库、机器学习、统计学等多个领域的理论和技术[1]。聚类分析是数据挖掘中广为研究的课题之一,是从数据中寻找数据间的相似性,并依此对数据进行分类,从而发现数据中隐含的有用信息或知识。目前已经提出了不少数据聚类算法,其中比较著名的有CLARANS[2]、BIRCH[3]、DBSCAN[4]和CLIQUE[5]等。但对于高维、大规模数据库的高效聚类分析仍然是一个有待研究的开放问题。网格方法是空间数据处理中常用的将空间数据离散化的方法。基于网格的聚类算法由于易于增量实现和进行高维数据处理而被广泛应用于聚类算法中。研究人员已经提出了很多基于网格的聚类算法,包括STING[6],它利用了存储在网格单元中的统计信息;WaveCluster[7]它用一种小波转换方法来聚类数据对象;CLIQUE在高维数据空间中基于网格和密度的聚类方法等。本文对已有的基于网格的聚类算法进行了研究,从网格的表示,划分网格单元的方法,到统计网格内信息,搜索近邻网格单元,聚类超过指定阙值的网格单元的各个步骤进行了分析,最后对基于网格方法聚类的研究方向做了展望。 2网格的定义与划分网格的基本概念,设A1,A2,…,Ar是数据集O={O1,O2,…,On}中数据对象的r个属性的有界定义域,那W=A1×A2×…×Ar就是一个r维空间,将A1,A2,…,Ar看成是W的维(属性、字段),则对于一个包含n个数据点的r维空间中的数据集O={O1,O2,…,On},其中Oi={Oi1,Oi2,…,Oir}(i=1,2,…,n),Oi的第j个分量Oij∈Aj。将W的每一维M等分,即把W分割成个网格单元。基于网格聚类算法的第一步是划分网格结构,按搜索子空间的策略不同,主要有基于由底向上网格划分方法的算法和基于自顶向下网格划分方法的算法。 (即每维段数ki,1≤i≤d),将数据空间均匀划分为相等大小的网格单元,假设落入同一网格单元内的所有数据点都属于同一个簇,每个网格单元保存落入其内数据的统计信息,比如数据点个数,数据点之和。包含一定数目数据点的网格单元被称为高密度网格单元。 WaveCluster与CLIQUE是采用由底向上网格划分方法的代表性算法。WaveCluster处理低维空间数据,它的性能超越了BIRCH、CLARANS,与DBSCAN等优秀的聚类算法[15]。CLIQUE考虑了高维子空间聚类,但它的时间复杂度较高,需要用户指定全局密度阈值。算法MAFIA[8]对CLIQUE进行了改进,为了减少聚类算法需要处理的网格单元数目,MAFIA将均匀划分网格中每一维上数据分布密度相似的相邻段合并,由此得到一个不均匀划分的网格。这个网格在数据分布较均匀的区域划分粒度大,在数据分布不均匀的区域划分粒度小,这种不均匀划分网