k-means聚类问题的改进近似算法

• 作者: 史士英 朱大铭 王守强
• 来源期刊: 山东大学学报：工学版
• 学科: 工学
• 关键词: 算法 聚类 概率 质心点
• 年，卷（期）: 2011,（4）
• 页码范围: 125-132
• 分类号: TP301.6
• 语种: 中文

摘要

研究了Ostrovsky给出k-means问题的（1＋ε）-近似算法,针对算法中取样参数小的以及枚举数量大的不足,证明了可以选择一个更大的取样参数减小取样点集,基于随机算法,提出新的枚举策略减少枚举数量。本文分析了算法的成功概率。改进算法的期望时间复杂度为O（2O（kα2/ε）dn）,其中d、n分别为问题实例的空间维数和输入点个数,α是小于1的分隔系数。算法的成功概率为121-e-21εk（1-O（α））。与Ostrovsky给出的算法相比,算法的运算效率得到很大的提高。

作者信息

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