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

摘要：

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

关键词：随机算法、k-means、聚类

所属期刊栏目：31

分类号：TP301.6(计算技术、计算机技术)

资助基金：山东省高校科技计划项目J08LI69

在线出版日期：2010-09-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：46-52