基于输入点集求解k-Means聚类算法

摘要：

k-Means聚类是聚类划分中应用最广泛的一种方案,但是现在许多关于此问题的研究并没有给出近似比为常数的算法。本文给出了一个随机算法,该算法通过以不同概率选取初始k个点。保证了以一定概率分别属于不同最优聚类簇的k个点。以这k个点。作为初始中心点。对输入点。集进行交换分别执行局部搜索算法,证明了可得到期望近似比至多为2的解.实验结果表明该算法能够取得较优的近似解结果。

关键词： 质心点 聚类算法 聚类划分 搜索算法 局部搜索 输入点集

作者: 王守强 朱大铭 史士英

作者单位: 山东大学计算机科学与技术学院,济南,250010;山东交通学院信息工程系,济南,250023 山东大学计算机科学与技术学院,济南,250010 山东交通学院信息工程系,济南,250023

会议类型: 国内会议

会议名称: 第26届中国控制会议

会议地点: 湖南张家界

会议语种:中文

页码: 500-504

在线出版日期: 2007-07-26（万方平台首次上网日期，不代表论文的发表时间）