受凸包约束的模拟退火聚类

论文摘要

由于K-均值聚类算法对初始点敏感、易陷入局部最小解,一些文献将模拟退火算法与K-均值聚类结合,利用模拟退火算法的全局最优性求解聚类最优。在这些文献中,邻域的搜索都是不加任何约束的随机生成过程,由于组合爆炸问题,这种不加约束的盲目搜索产生大量的劣解,跳出局部最优的概率非常低且收敛速度慢,占用了系统大量的时间。本文借助计算几何和离散数学等相关知识,对模拟退火过程中的邻域搜索策略进行了讨论。 首先分析了聚类最优解的几何意义:K-均值聚类迭代过程实际是Voronoi图之间的转换,停止条件是产生中心Voronoi图;基于最小误差准则函数的聚类最优解是中心Voronoi图。在此研究基础上,由凸包、Delaunay三角形等相关知识,提出了一类受凸包约束的模拟退火算法,这种算法要求邻域的生成满足凸约束条件,即各类子集生成的凸包互不相交。 本文提出的模拟退火聚类只对满足凸约束的邻域进行检测,缩小了搜索空间,增强了全局寻优能力,并显著提高了收敛速度。

论文目录

• 摘要
• Abstract
• 第一章 文献综述与课题选择
• 1.1 聚类分析的发展和现状
• 1.2 聚类分析的核心问题
• 1.3 K-均值聚类及其发展
• 1.4 模拟退火及模拟退火聚类概述
• 1.5 论文的研究内容及组织结构
• 1.5.1 论文的研究内容
• 1.5.2 论文组织结构
• 第二章 聚类问题的几何意义
• 2.1 凸包概念和算法
• 2.2 Delaynay三角网和Voronoi图
• 2.2.1 Delaunay三角网及其构建
• 2.2.2 Voronoi图及其构建
• 2.2.3 K-均值聚类的收敛性
• 2.2.4 聚类最优解的几何意义
• 第三章 受凸包约束的模拟退火聚类
• 3.1 模拟退火聚类研究现状
• 3.2 无约束的随机邻域搜索造成“组合爆炸”
• 3.3 受凸包约束的邻域生成规则
• 3.4 受凸包约束的模拟退火聚类
• 第四章 仿真实验
• 4.1 K-均值聚类迭代过程
• 4.2 无约束随机生成邻域的模拟退火聚类
• 4.3 受凸包约束的模拟退火聚类
• 4.4 仿真数据分析
• 第五章 总结与展望
• 参考文献
• 致谢