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

《基于聚类方法的计算机网格技术探析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、【摘要】网格技术和应用将成为具有高性能处理、海量数据存储和人量仪器设备终端等特征的信息处理基础设施。通过它可以汇聚Internet屮分散异构、动态变化的计算和信息资源，将其中不同组织和机构的资源数据空间化。网格技术的数据分析方法将多维空间数据划分为山（超）矩形网格单元纟II成的网格，然后在网格单元上进行聚类，以提取挖掘隐含的、未知但有应用价值的信息。本文以聚类算法为代表，対现有基于网格技术的进行了概述探析。中国论文网【关键词】数据挖掘；网格；聚类0.引言随着现代商业计算越来越复杂，技术上迫切需耍低廉而数据处理能力超强的计算模式

2、以进行从大型数据库或数据仓库中提取隐含的、耒知的有应用价值的信息或模式，随Z数据挖掘的概念应运而生。数据挖掘是数据库研究中的一个很有应用价值的领域，融合了数据库、机器学习、统计学等多个领域的理论和技术。数据挖掘中，聚类分析方法是广为研究的课题之一，是从数据中寻找数据间的相似性，并依此对数据进行分类，从而发现数据中隐含的有川信息或知识。网格方法是空间数据处理中常用的将空间数据离散化的方法。基于网格，聚类算法山于易于增量实现和进行高维数据处理而被广泛应用于网格技术中。本文对聚类算法、网格方法进行了概述分析。1.网格的定义与划分网格

3、的基本概念，设Nl,N2,…，Nr是数据集D={D1,D2,…，Dn}中数据对象的r个属性的有界定义域，那W=NlXN2X-XNr就是一个r维空间，将Nl,N2,…，Nr看成是W的隹（属性、字段），则对于一个包含n个数据点的r维空间中的数据集D二{D1,D2,…，Dn},其中Di={Dil,Di2,…，Dir}（i=l,2,…，n）,Di的第j个分量DijeNjo将W的每一维M等分，即把W分割成个网格单元。聚类算法第一步是划分网格结构，按搜索子空间的策略不同，主要有两种算法，一是由底向上网格划分方法的算法，另外一个是自顶向下网

4、格划分方法的算法。1.1

5、+1底向上的划分方法山底向上的网格划分方法按照用八输入的划分参数（即每维段数ki,lWiWd）,将数据空间均匀划分为相等人小的网格单元，假设落入同一网格单元内的所有数据点都属于同一个簇，每个网格单元保存落入其内数据的统计信息，比如数据点个数，数据点之和。包含数据点数据较多的网格单元被称为高密度网格单元。采用山底向上的网格划分方法的优点在于，它能通过对数据的一•遍扫描，将数据压缩到—•个网格数据结构内，并基于这个网格数据结构，发现任意形状的簇。其缺点，如果网格单元的粒度较小（即体积较小），那么得到的聚簇

6、的精度较高，但是算法的计算复杂度较人。此外，由底向上的网格方法存在不适合处理高维数据的问题。在高维空间，数据的分布是非常稀疏的，网格方法失去其压缩作用，而且属于同一个簇的高密度网格单元也可能不相连，这使聚类算法不能发现合理数目的簇。1.2白顶向下的划分方法IT顶向下的网格划分方法采取分治的策略，对数据空间进行递归划分，使问题的规模不断减小。首先将原数据空间划分为儿个较人的区域。对于每个得到的区域，划分过程反复执行，直到每个区域包含属于同一个簇的数据点，那么这些区域就是最终的网格单元。该算法直接将高密度网格单元识别为一个簇，或是

7、将相连的高密度网格单元识别为簇。自顶向下划分方法的主要优点在于不需要用八指定划分参数，而是根据数据的分布对空间进行划分，因此这种划分更为合理。数据空间维度对自顶向下网格方法的影响较小，可以快速将人型高维数据集屮的簇分隔开。这一类方法的计算复杂度与数据集人小和维度都呈线性关系适合于处理高维数据。其缺点，山于划分是基于数据分布的，而通常认为噪音是在整个空间均匀分布的，所以自顶向下划分方法对噪音不敏感。但是，由于这种方法得到的网格单元的体积远大于由底向上网格方法中的网格单元体积，因此该方法产牛的簇的描述精度比山底向上的网格方法得到的

8、簇的描述精度要低。而且在自顶向下的划分过程中，同一个簇可能被划分到不同的区域中，最终得到的同一区域也可能包含不同的簇，这样就进一步降低了算法的正确度。这类划分方法的另一个缺点是它在划分过程中，需要对数据集进行多次扫描。而由底向上划分方法在于只需对数据集进行--次线性扫描以及较高的簇的描述精度。凶此，两类方法适用于不同的问题。前者适于处理高维数据集，斤者能有效处理存取代价较人的超大型数据集与动态数据。2•网格聚类过程聚类算法的基木过程是，首先将数据空间W划分为网格单元，将对象指派到合适的单元,并计算每个单元的密度。以用户输入的密

9、度阙值，删除低于密度阙值的稀疏网格单元，把邻近的高于密度阙值的稠密网格单元集中起来形成簇。相对于稠密网格单元来说，人多数的网格单元包含非常少甚至空的的数据，这一类网格单元被称为稀疏网格单元。人量的稀疏网格卩元的存在会极人的降低聚类的速度，需要在聚类之前对稀疏网格单元进行处理。