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