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

摘要：

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

关键词： k-means聚类 最小聚类划分 质心点 ε质心点 近似算法 随机取样

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

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

会议类型: 国内会议

会议名称: 2007全国理论计算机科学学术年会

会议地点: 南宁

会议语种:中文

页码: 26-30

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