资源描述：
《基于网格的聚类方法研究软件毕业论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于网格的聚类方法研究软件毕业论文 摘要:已有的聚类算法对于发现任意形状的聚类和处理离群点效果不理想,分析了现有基于网格的聚类算法。使用网格方法的数据分析方法将空间划分为由(超)矩形网格单元组成的网格,然后在网格单元上进行聚类。最后,全文并提出基于网格的聚类需要进一步研究的方向。 关键词:数据挖掘;网格;聚类 1引言 数据挖掘是指从大型数据库或数据仓库中提取隐含的、未知的及有应用价值的信息或模式。它是数据库研究中的一个很有应用价值的领域,融合了数据库、机器学习、统计学等多个领域的理论和技术[1]。 聚类分析是数据挖掘中广为研究的课题之一,是从数据中寻找数据间的相似性,并依此对数
2、据进行分类,从而发现数据中隐含的有用信息或知识。目前已经提出了不少数据聚类算法,其中比较著名的有CLARANS[2]、BIRCH[3]、DBSCAN[4]和CLIQUE[5]等。但对于高维、大规模数据库的高效聚类分析仍然是一个有待研究的开放问题。 网格方法是空间数据处理中常用的将空间数据离散化的方法。基于网格的聚类算法由于易于增量实现和进行高维数据处理而被广泛应用于聚类算法中。研究人员已经提出了很多基于网格的聚类算法,包括STING[6],它利用了存储在网格单元中的统计信息;等分,即把AFIA[8]对CLIQUE进行了改进,为了减少聚类算法需要处理的网格单元数目,MAFIA将均匀划分网格中
3、每一维上数据分布密度相似的相邻段合并,由此得到一个不均匀划分的网格。这个网格在数据分布较均匀的区域划分粒度大,在数据分布不均匀的区域划分粒度小,这种不均匀划分网格的方法能够提高聚类的质量,被后续的许多算法所采用。 采用由底向上的网格划分方法的优点在于,它能通过对数据的一遍扫描,将数据压缩到一个网格数据结构内,并基于这个网格数据结构,发现任意形状的簇。此外,如果网格单元的粒度较小(即体积较小),那么得到的聚簇的精度较高,但是算法的复杂度较大。此外,由底向上的网格方法存在不适合处理高维数据的问题。在高维空间,数据的分布是非常稀疏的,网格方法失去其压缩作用,而且属于同一个簇的高密度网格单元也可能
4、不相连,这使聚类算法不能发现合理数目的簇。（lw.AsEac.编辑整理） 2.2自顶向下的划分方法 自顶向下的网格划分方法采取分治的策略(divideandconquerprinciple),对数据空间进行递归划分,使问题的规模不断减小。首先将原数据空间划分为几个较大的区域。对于每个得到的区域,划分过程反复执行,直到每个区域包含属于同一个簇的数据点,那么这些区域就是最终的网格单元。基于自顶向下网格方法的聚类算法直接将高密度网格单元识别为一个簇,或是将相连的高密度网格单元识别为簇。 OptiGrid[9]与CLTree[10]是两个典型的基于自顶向下网格划分方法的聚类算法。其中,Opti
5、Grid则是用空间数据分布的密度信息来选择最优划分。通过一个密度函数来决定切割平面,可以将数据空间划分为规则的或不规则单元,与传统的等间距的划分相比,可以用此来解决高维聚类的问题。而CLTree用划分后的信息增益来选取最优划分。 自顶向下划分方法的主要优点在于不需要用户指定划分参数,而是根据数据的分布对空间进行划分,因此这种划分更为合理。数据空间维度对自顶向下网格方法的影响较小,可以快速将大型高维数据集中的簇分隔开。这一类方法的计算复杂度与数据集大小和维度都呈线性关系适合于处理高维数据。由于划分是基于数据分布的,而通常认为噪音是在整个空间均匀分布的,所以自顶向下划分方法对噪音不敏感。但是,
6、由于这种方法得到的网格单元的体积远大于由底向上网格方法中的网格单元体积,因此方法产生的簇的描述精度比由底向上的网格方法得到的簇的描述精度要低。而且在自顶向下的划分过程中,同一个簇可能被划分到不同的区域中,最终得到的同一区域也可能包含不同的簇,这样就进一步降低了算法的正确度。这类划分方法的另一个缺点是它在划分过程中,需要对数据集进行多次扫描。 而由底向上划分方法在于只需对数据集进行一次线性扫描以及较高的簇的描述精度。因此,两类方法适用于不同的问题。前者适于处理高维数据集,后者能有效处理存取代价较大的超大型数据集与动态数据。（作文网zdash;个密集网格单元。 相对于稠密网格单元来说,大多数
7、的网格单元包含非常少甚至空的的数据,这一类网格单元被称为稀疏网格单元。大量的稀疏网格单元的存在会极大的降低聚类的速度,需要在聚类之前对稀疏网格单元进行处理,定义稀疏密度阈值为,当density>时,该网格单元是个稀疏单元。对于稀疏网格单元的处理方法一般采用压缩的方法或者直接删除的方法,如果需要保留稀疏网格单元用于后续处理,可以使用压缩的方法;如果在现有数据的基础之上直接聚类,可以删除稀疏网格单元,理论分
