基于网格的聚类方法研究
基于网格的聚类方法研究
【摘要】由于已有的聚类算法对于发现任意形状的聚类和处理离群点效果不理想，分析了现有基于网格的聚类算法。使用网格方法的数据分析方法将空间划分为由（超）矩形网格单元组成的网格，然后在网格单元上进行聚类，最后提出基于网格的聚类需要进一步研究的方向。
【关键词】数据挖掘；网格；聚类
1 引言
数据挖掘指从大型数据库或数据仓库中提取隐含的、未知的及有应用价值的信息或模式。它是数据库研究中的一个很有应用价值的领域，融合了数据库、机器学习、统计学等多个领域的理论和技术。
数据挖掘中广为研究的课题之一是聚类分析，从数据中寻找数据间的相似性，并依此对数据进行分类，从而发现数据中隐含的有用信息或知识。目前已经提出了不少著名的数据聚类算法，有CLARANS 、BIRCH 、DBSCAN 和CLIQUE 等。但对于高维、大规模数据库的高效聚类分析仍然是一个有待研究的开放问题。
空间数据处理中常用的将空间数据离散化的方法是网格方法。由于易于增量实现和进行高维数据处理而广泛应用聚类算法。研究人员已经提出了很多基于网格的聚类算法，包括利用了存储在网格单元中的统计信息的STING ；用一种小波转换方法来聚类数据对象的WaveCluster ；在高维数据空间中基于网格和密度的聚类方的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 分割成个网格单元。
基于网格聚类算法的第一步是划分网格结构，按搜索子空间的策略不同，主要有两种算法：一种基于由底向上网格划分方法的算法，另一种是基于自顶向下网格划分方法的。