评价网 > 科教论文 > 工学毕业论文 > 计算机软件论文 > 正文

基于网格的聚类方法研究软件毕业论文(2)

2013-05-08 18:11
　　自顶向下的网格划分方法采取分治的策略(divide and conquer principle),对数据空间进行递归划分,使问题的规模不断减小。首先将原数据空间划分为几个较大的区域。对于每个得到的区域,划分过程反复执行,直到每个区域包含属于同一个簇的数据点,那么这些区域就是最终的网格单元。基于自顶向下网格方法的聚类算法直接将高密度网格单元识别为一个簇,或是将相连的高密度网格单元识别为簇。
　　OptiGrid[9]与CLTree[10]是两个典型的基于自顶向下网格划分方法的聚类算法。其中, OptiGrid则是用空间数据分布的密度信息来选择最优划分。通过一个密度函数来决定切割平面,可以将数据空间划分为规则的或不规则单元,与传统的等间距的划分相比,可以用此来解决高维聚类的问题。而CLTree用划分后的信息增益来选取最优划分。
　　自顶向下划分方法的主要优点在于不需要用户指定划分参数,而是根据数据的分布对空间进行划分,因此这种划分更为合理。数据空间维度对自顶向下网格方法的影响较小,可以快速将大型高维数据集中的簇分隔开。这一类方法的计算复杂度与数据集大小和维度都呈线性关系适合于处理高维数据。由于划分是基于数据分布的,而通常认为噪音是在整个空间均匀分布的,所以自顶向下划分方法对噪音不敏感。但是,由于这种方法得到的网格单元的体积远大于由底向上网格方法中的网格单元体积,因此方法产生的簇的描述精度比由底向上的网格方法得到的簇的描述精度要低。而且在自顶向下的划分过程中,同一个簇可能被划分到不同的区域中,最终得到的同一区域也可能包含不同的簇,这样就进一步降低了算法的正确度。这类划分方法的另一个缺点是它在划分过程中,需要对数据集进行多次扫描。
　　而由底向上划分方法在于只需对数据集进行一次线性扫描以及较高的簇的描述精度。因此,两类方法适用于不同的问题。前者适于处理高维数据集,后者能有效处理存取代价较大的超大型数据集与动态数据。 （科教作文网http://zw.nseAc.com）
　　
　　3 基于网格的聚类过程
　　基于网格的聚类算法的基本过程是,首先将数据空间W划分为网格单元,将数据对象集O 映射到网格单元中,并计算每个单元的密度。根据用户输入的密度阈值MinPts 判断每个网格单元是否为高密度单元,由邻近的稠密单元组形成簇[11],。

 
　　算法1中的步骤1已经在上文详细说明,下面具体介绍步骤2-4的内容。
　　3.1 网格单元的密度
　　簇就是一个区域,该区域中的点的密度大于与之相邻的区域。在网格数据结构中,由于每个网格单元都有相同的体积,因此网格单元中数据点的密度即是落到单元中的点的个数。据此可以得到稠密网格单元的密度是,设在某一时刻t一个网格单元的密度为density,定义density=单元内的数据点数/数据空间中总的数据点数,设密度阈值为, 为用户输入的密度阙值,当density> 时,该网格单元是—个密集网格单元。
　　相对于稠密网格单元来说,大多数的网格单元包含非常少甚至空的的数据,这一类网格单元被称为稀疏网格单元。大量的稀疏网格单元的存在会极大的降低聚类的速度,需要在聚类之前对稀疏网格单元进行处理,定义稀疏密度阈值为,当density>时,该网格单元是—个稀疏单元。对于稀疏网格单元的处理方法一般采用压缩的方法或者直接删除的方法,如果需要保留稀疏网格单元用于后续处理,可以使用压缩的方法;如果在现有数据的基础之上直接聚类,可以删除稀疏网格单元,理论分析和实验证明删除稀疏网格单元并不影响聚类的质量[12]。

　　3.2 由稠密网格单元形成簇
　　 在基于网格的聚类算法中,根据以上分析,由邻接的稠密单元形成簇是相对直截了当的,这也是基于网格的方法的优点之一。但是需要首先定义邻接单元的含义。设n维空问中的存在任意两个网格单元U1和U2,当这两个网格单元在—个维上有交集或是具有一个公共面时,称它们为邻接网格单元。 本文来自中国科教评价网
　　在二维空间中,比较常使用的是4-connection相邻定义和8-connection相邻定义(如图1),4-connection更适合在聚类算法中使用。因为当寻找某个网格单元的邻居时,在4-connection定义下,一个网格单元只有2d个邻居,而在8-connection定义下,有3d-1个邻居,当数据维度d较大时,这个数目非常大。使用4-connection不仅参与计算的单元数目大为减少,而且单元增加与维数的关系由指数增长变为线性增长,所以能进一步减少算法运行所需的时间,具有较低的计算复杂度[13]。其外,只有在非常特殊的情况下,使用4-connection定义得到的聚类结果才会与使用8-connection定义得到的聚类结果不同[14],这是因为,当4-connection的网格单元是高密度网格单元时,四个对角线上的网格单元不论是否是高密度网格单元,都能被正确的聚类;只有当与对角线上的网格单元相邻的2个网格单元同时为空且该单元本身是高密度网格单元时,不能正确聚类,在划分网格时,通常都要求网格单元的大小远小于簇的大小,因此可以认为这种情况出现的可能很小。
　　 　　4 结论及展望