基于网格方法的聚类算法研究

基于网格方法的聚类算法研究

ID:13371344

大小:1.25 MB

页数:112页

时间:2018-07-22

基于网格方法的聚类算法研究_第1页
基于网格方法的聚类算法研究_第2页
基于网格方法的聚类算法研究_第3页
基于网格方法的聚类算法研究_第4页
基于网格方法的聚类算法研究_第5页
资源描述:

《基于网格方法的聚类算法研究》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、华中科技大学博士学位论文基于网格方法的聚类算法研究姓名:孙玉芬申请学位级别:博士专业:计算机软件与理论指导教师:卢炎生20061107摘要随着信息技术在各个领域的普及,各种应用每天产生的数据量呈指数级增长。如何有效处理这些数据,从中提取有用的知识,是迫切需要解决的问题。数据挖掘的任务是从大型数据集中提取知识。聚类分析是数据挖掘中的一项主要技术,它将物理对象或抽象对象的集合分组成为由类似的对象组成的多个簇。网格方法在空间数据分析、索引,和聚类中都有应用。使用网格方法的数据分析方法将空间划分为由(超)矩形网格单元组成的网格,然后在网格单元上进行各种分析。数据空间

2、可以以多种方式划分成网格,其中以简单的树形网格划分和p×p网格划分用得最多。通过将同一网格单元内的数据的信息用它们的统计信息替代,网格可以直观地将数据压缩。网格单元的压缩功能与微簇和抗体对数据的压缩有很多相似之处,但是它们也具有很多不同的性质。使用网格单元、微簇,和抗体的聚类算法对压缩单元的生成和管理采用了不同的策略。利用网格的空间划分特征和网格内信息的可加性,基于网格方法的算法可以以多种方式进行并行化。现有的基于网格方法的聚类算法都假设落入同一个网格单元的数据点属于同一个簇,这个假设并不总是成立。设计了一个新的基于网格的数据压缩方法,这个压缩方法只有在能确认

3、一组数据都属于同一个簇时,才对这组数据进行压缩。在网格数据结构中,完全位于一个簇内部的网格单元内的数据可以肯定都属于这个簇。基于对空间中网格单元与簇的关系的观察,新的数据压缩方法采用不均匀的网格划分方法,对簇内部的网格单元采用较大的粒度,进行安全的数据压缩。对簇边缘的网格单元采用较小的粒度,提高簇的描述精度。基于新的数据压缩方法,设计了一个聚类算法SGRIDS。此算法基于网格单元内数据的密度,判断网格单元的位置。算法SGRIDS能通过对数据集的一次扫描,I以较高精度快速找到大型空间数据集中的簇。由于网格单元的大小不再影响数据压缩质量,此算法的聚类质量受网格单元

4、粒度影响较小。而通过保存记录簇的形状的边缘点,算法能以较高精度描述簇的形状。SGRIDS的计算复杂度为O(N),它对超大型空间数据集具有好的可伸缩性,能发现数据集中任意形状的簇,并且不受数据输入顺序的影响。实验表明,SGRIDS的聚类质量比经典算法WaveCluster好,算法对网格划分参数的敏感度比WaveCluster低。流数据挖掘是当前数据挖掘领域研究的热点。流数据在线流入的特征对聚类算法提出了多个新的要求,其中最基本的是只能对数据作一次线性扫描。为满足这些要求,流数据聚类算法通常使用概要数据结构对数据进行在线压缩。提出一个使用网格数据结构作为概要数据结

5、构的算法GCHDS处理高维数据流。算法采用一个简单的启发式方法,通过分析数据在每维投影的分布,选择对聚类分析有用的维来降低数据空间的维度。在真实数据集上的实验分析验证了算法的正确度与运行效率。实验表明,GCHDS的聚类性能比VLDB文章中的算法HPStream好。GSCDS是一个聚类高维数据流的子空间聚类算法。此算法结合由底向上的网格划分方法和自顶向下的网格划分方法,能快速、有效地处理高维数据流。GSCDS使用均匀划分的网格在线压缩数据流数据。在此网格数据结构上,使用自顶向下的网格划分方法将数据中的簇分隔开,并将每个簇与相应的子空间及区域相关联。然后,算法将各

6、子空间中相连的网格单元识别为簇,得到精确的簇的描述。最后,算法检查是否有簇需要被合并,从而消除自顶向下网格划分方法所引入的错误。对算法的复杂度分析以及在多个数据集上所做的性能分析实验都验证了此算法的计算效率和有效性。关键词:聚类;网格方法;数据压缩;数据流;子空间聚类IIAbstractAstheinformationtechnologieshavebeenusedwidelyinmanyfieldsofhumanlife,thedatagainedfromthesefieldsgrowsexponentiallyeveryday.Howtoextractkn

7、owledgefromthesedataisaproblemthatshouldbesolved.Theaimofdataminingistoextractknowledgefromlargedatasets.Clusteringanalysisisamaintechniqueofdatamining.Itpartitionsdataobjectsintoclustersthatarecomposedbysimilarobjects.Gridhasbeenusedinspatialdataanalysis,index,andclustering.Grid-ba

8、seddataanalysismeth

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。