1、1基于网格的聚类方法研究【摘要】由于已有的聚类算法对于发现任意形状的聚类和处理离群点效果不理想，分析了现有基于网格的聚类算法。使用网格方法的数据分析方法将空间划分为由（超）矩形网格单元组成的网格，然后在网格单元上进行聚类，最后提出基于网格的聚类需要进一步研究的方向。 【关键词】数据挖掘；网格；聚类 1 引言 数据挖掘指从大型数据库或数据仓库中提取隐含的、未知的及有应用价值的信息或模式。它是数据库研究中的一个很有应用价值的领域，融合了数据库、机器学习、统计学等多个领域的理论和技术。 数据挖掘中广为研究的课题之一是聚类分析，从数据中寻找数据间的相似性，并依此对数据进行分类，从而发现数据中隐含的有用
2、信息或知识。目前已经提出了不少著名的数据聚类算法，有CLARANS、BIRCH、DBSCAN 和 CLIQUE 等。但对于高维、大规模数据库的高效聚类分析仍然是一个有待研究的开放问题。 空间数据处理中常用的将空间数据离散化的方法是网格方法。由于易于增量实现和进行高维数据处理而广泛应用聚类算法。研究人员已经提出了很多基于网格的聚类算法，包括利用了存储在网格单元中的统计信息的 STING；用一种小波转换方法来聚类数据对象的 WaveCluster；在高维数据空间中基于网格和密度的聚类方的 CLIQUE 法等。 2本文分析了从网格的表示，划分网格单元的方法，到统计网格内信息，搜索近邻网格单元，聚类超
3、过指定阙值的网格单元的各个步骤，对已有的基于网格的聚类算法进行了研究，最后展望了基于网格方法聚类的研究方向。 2 网格的定义与划分 网格的基本概念，设 A1，A2，Ar 是数据集 O=O1，O2，On中数据对象的 r 个属性的有界定义域，那 W=A1A2Ar 就是一个 r维空间，将 A1，A2，Ar 看成是 W 的维（属性、字段） ，则对于一个包含 n 个数据点的 r 维空间中的数据集 O=O1，O2，On，其中Oi=Oi1，Oi2，Oir（i=1，2，n） ，Oi 的第 j 个分量OijAj。将 W 的每一维 M 等分，即把 W 分割成个网格单元。 基于网格聚类算法的第一步是划分网格结构，按
4、搜索子空间的策略不同，主要有两种算法：一种基于由底向上网格划分方法的算法，另一种是基于自顶向下网格划分方法的。 2.1 由底向上的划分方法 由底向上的网格划分方法按照用户输入的划分参数（即每维段数ki，1id） ，将数据空间均匀划分为相等大小的网格单元，假设落入同一网格单元内的所有数据点都属于同一个簇，落入其内数据的统计信息由每个网格单元保存，比如数据点个数与数据点之和，包含一定数目数据点的网格单元被称为高密度网格单元。 2.2 自顶向下的划分方法 自顶向下的网格划分方法采取分治的策略（divideand conquer 3principle） ，对数据空间进行递归划分，使问题的规模不断减小。
5、首先将原数据空间划分为几个较大的区域。对于每个得到的区域，划分过程反复执行，直到每个区域包含属于同一个簇的数据点，那么这些区域就是最终的网格单元。基于自顶向下网格方法的聚类算法直接将高密度网格单元识别为一个簇，或是将相连的高密度网格单元识别为簇。 3 基于网格的聚类过程 3.1 网格单元的密度 簇就是一个区域，该区域中的点的密度大于与之相邻的区域。在网格数据结构中，由于每个网格单元都有相同的体积，因此网格单元中数据点的密度即是落到单元中的点的个数。据此可以得到稠密网格单元的密度是，设在某一时刻 t 一个网格单元的密度为 density，定义density=单元内的数据点数/数据空间中总的数据点
6、数，设密度阈值为，为用户输入的密度阙值，当 density时，该网格单元是个密集网格单元。 相对于稠密网格单元来说，大多数的网格单元包含非常少甚至空的的数据，这一类网格单元被称为稀疏网格单元。对于稀疏网格单元的处理方法一般采用压缩的方法或者直接删除的方法，如果需要保留稀疏网格单元用于后续处理，可以使用压缩的方法；如果在现有数据的基础之上直接聚类，可以删除稀疏网格单元，理论分析和实验证明删除稀疏网格单元并不影响聚类的质量。 3.2 由稠密网格单元形成簇 在基于网格的聚类算法中，根据以上分析，由邻接的稠密单元形成4簇是相对直截了当的，这也是基于网格的方法的优点之一。但是需要首先定义邻接单元的含义。
7、设 n 维空问中的存在任意两个网格单元 U1 和U2，当这两个网格单元在个维上有交集或是具有一个公共面时，称它们为邻接网格单元。 在二维空间中，比较常使用的是 4-connection 相邻定义和 8-connection 相邻定义，4-connection 更适合在聚类算法中使用。因为当寻找某个网格单元的邻居时，在 4-connection 定义下，一个网格单元只有 2d 个邻居，而在 8-connection 定义下，有 3d-1 个邻居，当数据维度d 较大时，这个数目非常大。使用 4-connection 不仅参与计算的单元数目大为减少，而且单元增加与维数的关系由指数增长变为线性增长，所
8、以能进一步减少算法运行所需的时间，具有较低的计算复杂度。其外，只有在非常特殊的情况下，使用 4-connection 定义得到的聚类结果才会与使用 8-connection 定义得到的聚类结果不同，这是因为，当 4-connection 的网格单元是高密度网格单元时，四个对角线上的网格单元不论是否是高密度网格单元，都能被正确的聚类；只有当与对角线上的网格单元相邻的 2 个网格单元同时为空且该单元本身是高密度网格单元时，不能正确聚类，在划分网格时，通常都要求网格单元的大小远小于簇的大小，因此可以认为这种情况出现的可能很小。 4 结论及展望 基于网格聚类方法的优点是它的处理速度快，因为其速度与数据
9、对象的个数无关，而只依赖于数据空间中每个维上单元的个数，发现任意形状、任意大小的簇、计算结果与数据输入顺序无关、计算时间与数据5量无关，同时不要求像 k 均值一样预先指定簇个数等。但是，基于网格方法的聚类算法的输入参数对聚类结果影响较大，而且这些参数较难设置。当数据中有噪音时，如果不加特殊处理，算法的聚类质量会很差。而且，算法对于数据维度的可伸缩性较差。 基于网格的聚类方法目前还存在一些急需解决的问题，主要有以下几点：（1）当簇具有不同的密度时，全局的密度参数不能有效发现这样的簇，需要开发具有可变密度参数的算法。 （2）对于不同类型数据的聚类问题，比如对于高维数据，网格的数据将急剧增加，需要有
10、效地技术发现近邻单元。 （3）当数据集的规模巨大以及数据具有地理分布特性时，需要开发有效的并行算法来提高处理的速度。 （4）对现有网格算法的优化，从不同方面提高网格算法的有效性。比如开发稀疏网格的压缩算法、密度相似网格的合并算法等。 参考文献： 1CHENMS，HAN Jiawei，YUPS.Datamining：an overviewfrom a database perspectiveJ.IEEE Trans on Knwledge and Data Eng.1996，8（6）：866-883 2NGRT，HANJ.Efficient and effective clustering methods for spatial data miningC.Proc of the 20th VLDB Conference.Chile，Santia.1994：144-155 3ZHANGT，RAMAKRISHNANR，LIVNYM.An efficient data clustering method for very large databasesC.Proc of ACM SIGMOD International Conference on Management of 6Data.NewYork：ACM Press，1996：103-114
