一种基于K-Means局部最优性的高效聚类算法

• 作者: LEI Xiao-Feng LIN Fan 夏征义 谢昆青
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: K-MeanSCAN 基于密度 K-Means 聚类 连通性
• 年，卷（期）: 2008,（7）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 1683-1692
• 页数: 10页
• 分类号: TP18
• 字数: 7472字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2008.01683

摘要

K-Means聚类算法只能保证收敛到局部最优,从而导致聚类结果对初始代表点的选择非常敏感.许多研究工作都着力于降低这种敏感性.然而,K-Means的局部最优和结果敏感性却构成了K-MeanSCAN聚类算法的基础.K-MeanSCAN算法对数据集进行多次采样和K-Means预聚类以产生多组不同的聚类结果,来自不同聚类结果的子簇之间必然会存在交集.算法的核心思想是,利用这些交集构造出关于子簇的加权连通图,并根据连通性合并子簇.理论和实验证明,K-MeanScan算法可以在很大程度上提高聚类结果的质量和算法的效率.