基于最小聚类求解k-means问题算法

• 作者: 朱大铭 王守强
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: 随机算法 k-means 聚类
• 年，卷（期）: 2010,（7）
• 页码范围: 46-52
• 分类号: TP301.6
• 字数: 7247字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-436X.2010.07.007

摘要

针对每个划分子集要求至少满足一定数量点的k-means问题,设计了该问题的随机近似算法.给出一个样本子集,证明了该样本子集至少以1/2的概率包含每个最优子集中至少一个点,进一步设计近似度为2的随机算法.设计了该问题的(1+ε)随机近似算法,算法的成功概率至少为3/2k+2.利用取样技术,设计了k-means问题的局部搜索随机算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱大铭	山东大学计算机科学与技术学院	50	263	11.0	13.0
2	王守强	山东交通学院信息工程系	7	65	5.0	7.0