基于聚类方法的计算机网格技术探析

【摘要】网格技术和应用将成为具有高性能处理、海量数据存储和大量仪器设备终端等特征的信息处理基础设施。通过它可以汇聚Internet中分散异构、动态变化的计算和信息资源，将其中不同组织和机构的资源数据空间化。网格技术的数据分析方法将多维空间数据划分为由（超）矩形网格单元组成的网格，然后在网格单元上进行聚类，以提取挖掘隐含的、未知但有应用价值的信息。本文以聚类算法为代表，对现有基于网格技术的进行了概述探析。

【关键词】数据挖掘；网格；聚类

0.引言

随着现代商业计算越来越复杂，技术上迫切需要低廉而数据处理能力超强的计算模式以进行从大型数据库或数据仓库中提取隐含的、未知的有应用价值的信息或模式，随之数据挖掘的概念应运而生。数据挖掘是数据库研究中的一个很有应用价值的领域，融合了数据库、机器学习、统计学等多个领域的理论和技术。

数据挖掘中，聚类分析方法是广为研究的课题之一，是从数据中寻找数据间的相似性，并依此对数据进行分类，从而发现数据中隐含的有用信息或知识。

网格方法是空间数据处理中常用的将空间数据离散化的方法。基于网格，聚类算法由于易于增量实现和进行高维数据处理而被广泛应用于网格技术中。本文对聚类算法、网格方法进行了概述分析。

1.网格的定义与划分

网格的基本概念，设N1，　N2，…，Nr是数据集D={D1，D2，…，Dn}中数据对象的r　个属性的有界定义域，那W=N1×N2×…×Nr　就是一个r　维空间，　将N1，N2，…，Nr看成是W的维（　属性、字段），则对于一个包含n　个数据点的r　维空间中的数据集D={D1，D2，…，Dn}，其中Di={Di1，Di2，…，Dir}（i=1，　2，…，n），Di　的第j　个分量Dij∈Nj。将W的每一维M等分，即把W分割成个网格单元。

聚类算法第一步是划分网格结构，按搜索子空间的策略不同，　主要有两种算法，一是由底向上网格划分方法的算法，另外一个是自顶向下网格划分方法的算法。

1.1由底向上的划分方法

由底向上的网格划分方法按照用户输入的划分参数（即每维段数ki，1≤i≤d），将数据空间均匀划分为相等大小的网格单元，假设落入同一网格单元内的所有数据点都属于同一个簇，每个网格单元保存落入其内数据的统计信息，比如数据点个数，数据点之和。包含数据点数据较多的网格单元被称为高密度网格单元。

采用由底向上的网格划分方法的优点在于，它能通过对数据的一遍扫描，将数据压缩到一个网格数据结构内，并基于这个网格数据结构，发现任意形状的簇。其缺点，如果网格单元的粒度较小（即体积较小），那么得到的聚簇的精度较高，但是算法的计算复杂度较大。此外，由底向上的网格方法存在不适合处理高维数据的问题。在高维空间，数据的分布是非常稀疏的，网格方法失去其压缩作用，而且属于同一个簇的高密度网格单元也可能不相连，这使聚类算法不能发现合理数目的簇。

1.2自顶向下的划分方法

自顶向下的网格划分方法采取分治的策略，对数据空间进行递归划分，使问题的规模不断减小。首先将原数据空间划分为几个较大的区域。对于每个得到的区域，划分过程反复执行，直到每个区域包含属于同一个簇的数据点，那么这些区域就是最终的网格单元。该算法直接将高密度网格单元识别为一个簇，或是将相连的高密度网格单元识别为簇。

自顶向下划分方法的主要优点在于不需要用户指定划分参数，而是根据数据的分布对空间进行划分，因此这种划分更为合理。数据空间维度对自顶向下网格方法的影响较小，可以快速将大型高维数据集中的簇分隔开。这一类方法的计算复杂度与数据集大小和维度都呈线性关系适合于处理高维数据。其缺点，由于划分是基于数据分布的，而通常认为噪音是在整个空间均匀分布的，所以自顶向下划分方法对噪音不敏感。但是，由于这种方法得到的网格单元的体积远大于由底向上网格方法中的网格单元体积，因此该方法产生的簇的描述精度比由底向上的网格方法得到的簇的描述精度要低。而且在自顶向下的划分过程中，同一个簇可能被划分到不同的区域中，最终得到的同一区域也可能包含不同的簇，这样就进一步降低了算法的正确度。这类划分方法的另一个缺点是它在划分过程中，需要对数据集进行多次扫描。

而由底向上划分方法在于只需对数据集进行一次线性扫描以及较高的簇的描述精度。因此，两类方法适用于不同的问题。前者适于处理高维数据集，后者能有效处理存取代价较大的超大型数据集与动态数据。

2.网格聚类过程

聚类算法的基本过程是，首先将数据空间W划分为网格单元，将对象指派到合适的单元，并计算每个单元的密度。以用户输入的密度阙值，删除低于密度阙值的稀疏网格单元，把邻近的高于密度阙值的稠密网格单元集中起来形成簇。

相对于稠密网格单元来说，大多数的网格单元包含非常少甚至空的的数据，这一类网格单元被称为稀疏网格单元。大量的稀疏网格单元的存在会极大的降低聚类的速度，需要在聚类之前对稀疏网格单元进行处理。

由稠密网格单元形成簇：

在该聚类算法中，根据以上分析，由邻接的稠密单元形成簇是相对直截了当的，这也是以网格方法为基础的优点之一。但是需要首先定义邻接单元的含义。设n维空问中的存在任意两个网格单元U1和U2，当这两个网格单元在—个维上有交集或是具有一个公共面时，称它们为邻接网格单元。

在二维空间中，比较常使用的是4-connection相邻定义（如图1-a）和8-connection相邻定义（如图1-b），4-connection更适合在聚类算法中使用。因为当寻找某个网格单元的邻居时，在4-connection定义下，一个网格单元只有2d个邻居，而在8-connection定义下，有3d-1个邻居，当数据维度d较大时，这个数目非常大。使用4-connection不仅参与计算的单元数目大为减少，而且单元增加与维数的关系由指数增长变为线性增长，具有较低的计算复杂度和较高的计算效率。

3.结论及展望

基于聚类方法的网格技术优点是它的处理速度快，由于该技术的速度与数据对象个数无直接相关，而是只依赖于数据空间中每个维上单元的个数，发现任意形状、任意大小的簇、计算结果与数据输入顺序无关、计算时间与数据量无关，同时不要求像k均值一样预先指定簇个数等。，基于聚类算法的网格技术也有其缺点，其输入参数对聚类结果影响比较大，且这些参数设置繁琐困难。当数据中有噪音时，需要加入特殊的处理，算法，才能保证聚类质量，而且，加入的算法对于数据维度的可伸缩性有较大影响。

本文对基于聚类方法的网格技术进行了分析和总结，包括网格的定义与划分方法、网格单元密度的确定、由邻接网格单元形成聚簇的聚类过程；最后对网格聚类方法优缺点进行了总结。　[科]

【参考文献】

［１］曹洪其，余岚，孙志挥.基于网格聚类技术的离群点挖掘算法[J].计算机工程，2006（6）.

［２］孙玉芬.基于网格方法的聚类算法研究[J].华中科技大学，2006.