基于最小聚类划分的K-means聚类(1+ε)近似算法

• 作者: 史士英 朱大铭 王守强
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: k-means 聚类 质心点 ε质心点
• 年，卷（期）: 2008,（z1）
• 所属期刊栏目: 算法:设计与分析
• 页码范围: 26-30
• 页数: 5页
• 分类号: TP301
• 字数: 4796字
• 语种: 中文

摘要

k-means聚类算法是解决聚类问题的一个常用方法.近年来,国外许多学者对该问题的近似常数算法和(1+ε)近似算法进行了研究.利用Kumar等人随机取样技术对于基于最小聚类划分k-means提出一个(1+ε)随机近似算法.该算法利用随机取样技术从集合中求出部分取样点,再对随机取样点进行组合找出每个聚类的部分点,将该部分点的质心点作为相应子聚类簇的质心点.通过多次运行该算法可以以较高概率求出k-means聚类的1+ε近似值.

作者信息

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