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

• 作 者: 王守强 朱大铭
• 机 构: 山东交通学院信息工程系,山东大学计算机科学与技术学院
• 出 处: 通信学报
• 发表日期: 2010年07期
• 关键词: 随机算法 K-MEANS 聚类 randomized algorithm k-means clustering
• 基金项目: 山东省高校科技计划项目（J08LI69）

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