基于模拟退火的K调和均值聚类算法.pdfVIP

计 算 机 系 统 应 用 2011 年 第 20 卷 第 7 期 基于模拟退火的K 调和均值聚类算法① 刘国丽，甄晓敏 (河北工业大学 计算机科学与软件学院，天津 300401) 摘 要：K 均值算法是最通用的划分聚类算法，然而它有高度依赖初始值和收敛于局部最小的缺点，K 调和均值 算法采用数据点与所有聚类中心的距离的调和平均替代了数据点与聚类中心的最小距离，解决了 K 均值算法对 初值敏感的问题。这样虽然解决初始值敏感问题，局部最小收敛问题仍然存在。为了获得全局最优解，提出一 种新的算法：基于模拟退火算法的 K 调和均值聚类。该算法将一种优秀的随机有哪些信誉好的足球投注网站算法——模拟退火算法引入 K 调和均值聚类，来解决局部最小收敛的问题，并将改进后的算法用于 IRIS 数据集的聚类分析，聚类结果与 K 均值算法结果对比，证明了改进算法的优越性。 关键词：聚类；K 均值；调和均值；模拟退火；局部最小 K-Harmonic Means Clustering with Simulated Annealing LIU Guo-Li, ZHEN Xiao-Min (Department of Computer Science and Software, Hebei University of Technology, Tianjin 300401, China) Abstract: K-means algorithm is a frequently-used methods of partition clustering. However, it greatly depends on the initial values and converges to local minimum. In K-harmonic means clustering, harmonic means fuction which apply distance from the data point to all clustering centers is used to solves the problem that clustering result is sensitive to the initial valve instead of the minimum distance. Although the problem above is solved, the problem converged to local minimum is still existed. In order to obtain a glonal optimal solution, in this paper, a new algorithm called K-harmonic means clustering algorithm with simulated annealing was proposed. This alhorithm is introduced into simulated annealing to solve the the problems of local minimum. Then the algorithm was used to analyse IRIS dataset and get a conclution that the new algorithm get a glonal optimal solution and reached a desired effect. Key words: clustering; K-means; K-Harmonic means; simulated annealing; local minimum 1 引言 （SA ）算法相结合而成的新算法，这种新算法称为基 K 均值（KM ）算法是一种简单高效的聚类算法， 于模拟退火的 K 调和均值（SAKHM ）聚类算法。 实际应用价值很高，因此很多学者对 K 均值算法的研 究非常感兴趣，他们试图从不同的角度来改善 K 均值 2 K调和均值聚类算法 算法，使它能够有更好的效果。现在已经有了许多对 2.1 K 均值算法 K 均值改进的方法，有基于密度蚂蚁思想的 K 均值算