基于Voronoi的平面数据的聚类分析

论文摘要

聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。论文首先总结了数据挖掘中的聚类算法,并着重分析了几种经典的聚类算法:KMeans、DBSCAN,CLIQUE,分析了它们的各自的优缺点及算法的各种改进措施。论文接着简要介绍了Voronoi图。作为计算几何中的一个重要分支,Voronoi具有很多优良的特性,特别是它的最近邻特性,因此它在诸多领域都有应用。而它的这个特性,与基于原型的聚类算法有着理论上的相似性,因此利用Voronoi图进行聚类是可行的。论文简要介绍了各种Voronoi图的构造方法,并给出了增量构造法的一般过程。为了利用Voronoi图进行聚类,必须构造封闭区域的Voronoi图。论文提出一种构造封闭区域的Voronoi图的方法:先在整个空间上构造Voronoi图,并构造出封闭区域(一般是矩形),然后找出Voronoi图中非封闭单元,然后循环一周求出这些非封闭单元与封闭曲线的交点,其它的单元不发生改变,这样就可以得到封闭区域上的Voronoi图。并可得到每个单元的顶点序列,还可以计算每个单元的面积。在着重分析了基于密度与网格的聚类算法的基础上,提出了基于Voronoi图的聚类算法。算法利用Voronoi图构建平面上不规则的网格,利用Voronoi图的最近邻特性将不同网格中的点归于不同的类。利用网格点密度来自动调整最终的聚类数,利用前后质心变化来调整Voronoi母点的位置,最终的Voronoi单元就是聚类结果。算法能自动确定聚类数,还能自动识别低密度点。实验证明,该算法能对平面上的数据点集进行有效的聚类,性能与改进的Kmeans算法Xmeans相当,比基于密度的聚类算法DBSCAN、Optics更有效,当实验数据集规模较大时优势较为明显。论文还运用改进的算法来解决一类应用地理信息进行规划决策的实际问题。论文最后对算法的进一步改进提出了一些思路。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 聚类定义与聚类算法的分类
• 1.2.1 聚类概念与聚类过程
• 1.2.2 聚类算法的类别
• 1.2.3 各种典型聚类算法简介
• 1.3 VORONOI 图
• 1.3.1 Voronoi 图的定义
• 1.3.2 Voronoi 图的特性
• 1.3.3 Voronoi 图的应用
• 1.4 本文的研究内容
• 1.5 论文的结构
• 第2章 几种经典的聚类算法
• 2.1 聚类算法
• 2.1.1 聚类分析
• 2.1.2 不同的簇类型
• 2.1.3 聚类算法的一般特性
• 2.1.4 数据特性
• 2.2 K 均值聚类算法
• 2.2.1 算法描述
• 2.2.2 算法的参数及复杂性
• 2.2.3 算法的优点与缺点
• 2.2.4 各种改进的k-均值聚类算法
• 2.3 基于密度的聚类算法-DBSCAN
• 2.3.1 根据基于中心的密度进行点分类
• 2.3.4 优点与缺点
• 2.3.5 算法的改进
• 2.4 基于网格与密度的聚类算法
• 2.4.1 基于网格与密度的基本的聚类算法
• 2.4.2 CLIQUE 算法
• 2.4.3 基于网格与密度的聚类算法的新进展
• 2.5 聚类算法的选择
• 2.6 小结
• 第3章 封闭区域VORONOI 图的构造
• 3.1 VORONOI 图的定义与相关概念
• 3.2 一些基本理论
• 3.3 增量法构造VORONOI 图
• 3.4 封闭区域VORONOI 图的构造
• 3.5 VORONOI 单元面积的计算
• 3.6 小结
• 第4章 基于VORONOI 图的平面数据的聚类分析
• 4.1 为什么要将VORONOI 图代替网格
• 4.1.1 网格的优点与缺点
• 4.1.2 用Voronoi 图代替网格
• 4.2 基于VORONOI 图的聚类算法
• 4.2.1 算法思想
• 4.2.2 算法
• 4.2.3 算法的复杂度分析
• 4.2.4 算法中的参数
• 4.3 小结
• 第5章 实验及分析
• 5.1 WEKA 简介
• 5.2 第一个实验例子
• 5.2.1 iris 简介
• 5.2.2 相关的对比算法及说明
• 5.2.3 实验结果对比
• 5.2.4 第一个实验结果分析
• 5.3 第二个对比实验
• 5.5 参数的设定
• 5.5.1 密度阈值的设置
• 5.5.2 质心变化终止值的设置
• 5.5.3 初始化参数
• 5.6 小结
• 第6章 算法在地理信息中的应用
• 6.1 问题的提出
• 6.2 问题的分析
• 6.3 改进的基于VORONOI 的平面数据的聚类分析
• 6.3.1 算法与问题的异同点
• 6.3.2 改进的Voronoi-Cluster 算法
• 6.4 实验
• 6.5 小结
• 第7章 算法改进及其展望
• 7.1 算法的伸缩性
• 7.2 引入核聚类思想
• 7.2.1 核聚类思想简介
• 7.2.2 相关定义与概念
• 7.2.3 将核函数引入Voronoi-Cluster
• 7.3 将算法从二维向多维空间扩展
• 7.4 初始化过程
• 7.5 其他
• 7.6 展望
• 结论
• 参考文献
• 致谢
• 附录A 攻读学位期间所发表的学术论文目录