学位论文 > 优秀研究生学位论文题录展示
基于Voronoi的平面数据的聚类分析
作 者: 向佐勇
导 师: 刘正才
学 校: 湘潭大学
专 业: 计算机应用技术
关键词: 聚类分析 点密度 网格 Voronoi图
分类号: TP301.6
类 型: 硕士论文
年 份: 2009年
下 载: 113次
引 用: 1次
阅 读: 论文下载
内容摘要
聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。论文首先总结了数据挖掘中的聚类算法,并着重分析了几种经典的聚类算法:KMeans、DBSCAN,CLIQUE,分析了它们的各自的优缺点及算法的各种改进措施。论文接着简要介绍了Voronoi图。作为计算几何中的一个重要分支,Voronoi具有很多优良的特性,特别是它的最近邻特性,因此它在诸多领域都有应用。而它的这个特性,与基于原型的聚类算法有着理论上的相似性,因此利用Voronoi图进行聚类是可行的。论文简要介绍了各种Voronoi图的构造方法,并给出了增量构造法的一般过程。为了利用Voronoi图进行聚类,必须构造封闭区域的Voronoi图。论文提出一种构造封闭区域的Voronoi图的方法:先在整个空间上构造Voronoi图,并构造出封闭区域(一般是矩形),然后找出Voronoi图中非封闭单元,然后循环一周求出这些非封闭单元与封闭曲线的交点,其它的单元不发生改变,这样就可以得到封闭区域上的Voronoi图。并可得到每个单元的顶点序列,还可以计算每个单元的面积。在着重分析了基于密度与网格的聚类算法的基础上,提出了基于Voronoi图的聚类算法。算法利用Voronoi图构建平面上不规则的网格,利用Voronoi图的最近邻特性将不同网格中的点归于不同的类。利用网格点密度来自动调整最终的聚类数,利用前后质心变化来调整Voronoi母点的位置,最终的Voronoi单元就是聚类结果。算法能自动确定聚类数,还能自动识别低密度点。实验证明,该算法能对平面上的数据点集进行有效的聚类,性能与改进的Kmeans算法Xmeans相当,比基于密度的聚类算法DBSCAN、Optics更有效,当实验数据集规模较大时优势较为明显。论文还运用改进的算法来解决一类应用地理信息进行规划决策的实际问题。论文最后对算法的进一步改进提出了一些思路。
|
全文目录
摘要 4-5 ABSTRACT 5-9 第1章 绪论 9-15 1.1 研究背景及意义 9 1.2 聚类定义与聚类算法的分类 9-11 1.2.1 聚类概念与聚类过程 9-10 1.2.2 聚类算法的类别 10-11 1.2.3 各种典型聚类算法简介 11 1.3 VORONOI 图 11-13 1.3.1 Voronoi 图的定义 11-12 1.3.2 Voronoi 图的特性 12-13 1.3.3 Voronoi 图的应用 13 1.4 本文的研究内容 13 1.5 论文的结构 13-15 第2章 几种经典的聚类算法 15-30 2.1 聚类算法 15-19 2.1.1 聚类分析 15-16 2.1.2 不同的簇类型 16-18 2.1.3 聚类算法的一般特性 18-19 2.1.4 数据特性 19 2.2 K 均值聚类算法 19-22 2.2.1 算法描述 20 2.2.2 算法的参数及复杂性 20-21 2.2.3 算法的优点与缺点 21 2.2.4 各种改进的k-均值聚类算法 21-22 2.3 基于密度的聚类算法-DBSCAN 22-24 2.3.1 根据基于中心的密度进行点分类 22-23 2.3.4 优点与缺点 23-24 2.3.5 算法的改进 24 2.4 基于网格与密度的聚类算法 24-28 2.4.1 基于网格与密度的基本的聚类算法 24-25 2.4.2 CLIQUE 算法 25-27 2.4.3 基于网格与密度的聚类算法的新进展 27-28 2.5 聚类算法的选择 28-29 2.6 小结 29-30 第3章 封闭区域VORONOI 图的构造 30-37 3.1 VORONOI 图的定义与相关概念 30-31 3.2 一些基本理论 31-32 3.3 增量法构造VORONOI 图 32-33 3.4 封闭区域VORONOI 图的构造 33-35 3.5 VORONOI 单元面积的计算 35-36 3.6 小结 36-37 第4章 基于VORONOI 图的平面数据的聚类分析 37-44 4.1 为什么要将VORONOI 图代替网格 37-39 4.1.1 网格的优点与缺点 37-38 4.1.2 用Voronoi 图代替网格 38-39 4.2 基于VORONOI 图的聚类算法 39-43 4.2.1 算法思想 39-40 4.2.2 算法 40-42 4.2.3 算法的复杂度分析 42 4.2.4 算法中的参数 42-43 4.3 小结 43-44 第5章 实验及分析 44-57 5.1 WEKA 简介 44 5.2 第一个实验例子 44-47 5.2.1 iris 简介 44-45 5.2.2 相关的对比算法及说明 45-46 5.2.3 实验结果对比 46 5.2.4 第一个实验结果分析 46-47 5.3 第二个对比实验 47-50 5.5 参数的设定 50-55 5.5.1 密度阈值的设置 50-52 5.5.2 质心变化终止值的设置 52-53 5.5.3 初始化参数 53-55 5.6 小结 55-57 第6章 算法在地理信息中的应用 57-61 6.1 问题的提出 57 6.2 问题的分析 57-58 6.3 改进的基于VORONOI 的平面数据的聚类分析 58-59 6.3.1 算法与问题的异同点 58 6.3.2 改进的Voronoi-Cluster 算法 58-59 6.4 实验 59-60 6.5 小结 60-61 第7章 算法改进及其展望 61-66 7.1 算法的伸缩性 61-62 7.2 引入核聚类思想 62-64 7.2.1 核聚类思想简介 62 7.2.2 相关定义与概念 62-63 7.2.3 将核函数引入Voronoi-Cluster 63-64 7.3 将算法从二维向多维空间扩展 64 7.4 初始化过程 64-65 7.5 其他 65 7.6 展望 65-66 结论 66-68 参考文献 68-72 致谢 72-73 附录A 攻读学位期间所发表的学术论文目录 73
|
相似论文
- 带有多项式基的径向点插值无网格方法的研究及应用,O241
- 联合编码调制技术中TCM与BICM方案性能研究,TN911.22
- BioLab面向生物计算服务的网格系统,TP399-C8
- 牡丹EST-SSR引物开发及其亲缘关系分析,S685.11
- 高血压前期证候特征研究,R259
- 大学生综合素质测评研究,G645.5
- 大豆品种对腐竹品质的影响及其品质评价体系的初步构建,TS214.2
- 21个荷花品种遗传多样性的ISSR分析,S682.32
- 基于聚类分析的P2P流量识别算法的研究,TP393.02
- 基于混合自适应遗传算法的动态网格调度问题研究,TP393.09
- 桃杂交后代(F1)幼苗光合效能评价,S662.1
- 南通市农业面源污染负荷研究与综合评价,X592
- 土壤环境功能区划研究,X321
- 基因表达谱数据聚类分析方法比较与大豆疫霉基因的网络构建,S435.651
- 大豆杂种优势及其遗传基础研究,S565.1
- 象草自交后代无性系的饲用价值及生物质能特性初步评价,S543.9
- 融合粒子群和蛙跳算法的模糊C-均值聚类算法研究,TP18
- 农业供应链系统网络平台的构建,S126
- 基于同化能力杂种优势早期评价的桃光合特性研究,S662.1
- 云南省直管县改革研究,D630
- 劳动保障监察网格化管理研究,F249.27
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com
|