标题:基于最小聚类求解k-means问题算法
作者:王守强;朱大铭
作者机构:[王守强] 山东交通学院信息工程系, 济南, 山东 250023, 中国.;[朱大铭] 山东大学计算机科学与技术学院, 济南, 山东 250100, 中国 更多
通讯作者地址:[Wang, S.-Q] Department of Information Engineering, Shandong Jiaotong University, Jinan 250023, China
来源:通信学报
出版年:2010
卷:31
期:7
页码:46-52
关键词:随机算法; 聚类
摘要:针对每个划分子集要求至少满足一定数量点的k-means问题, 设计了该问题的随机近似算法. 给出一个样本子集, 证明了该样本子集至少以1/2的概率包含每个最优子集中至少一个点, 进一步设计近似度为2的随机算法. 设计了该问题的(1+epsilon)随机近似算法, 算法的成功概率至少为3/2~(k+2). 利用取样技术, 设计了k-means问题的局部搜索随机算法
收录类别:EI;CSCD;SCOPUS
Scopus被引频次:2
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-77955446491&partnerID=40&md5=b9a548ae0710db7ae502382de5f6e0e6
TOP