主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
雷小锋,谢昆青,林 帆,夏征义.一种基于K-Means局部最优性的高效聚类算法.软件学报,2008,19(7):1683-1692
一种基于K-Means局部最优性的高效聚类算法
An Efficient Clustering Algorithm Based on Local Optimality of K-Means
投稿时间:2006-10-09  修订日期:2007-07-17
DOI:
中文关键词:  K-MeanSCAN  基于密度  K-Means  聚类  连通性
英文关键词:K-MeanSCAN  density-based  K-Means  clustering  connectivity
基金项目:Supported by the National High-Tech Research and Development Plan of China under Grant No.2006AA12Z217 (国家高技术研究发展计划(863)); the Foundation of China University of Mining and Technology under Grant No.OD080313 (中国矿业大学科技基金)
作者单位
雷小锋 北京大学 信息科学技术学院智能科学系/视觉与听觉国家重点实验室,北京 100871
中国矿业大学 计算机学院,江苏 徐州 221116 
谢昆青 北京大学 信息科学技术学院智能科学系/视觉与听觉国家重点实验室,北京 100871 
林 帆 北京大学 信息科学技术学院智能科学系/视觉与听觉国家重点实验室,北京 100871 
夏征义 中国人民解放军总后勤部 后勤科学研究所,北京 100071 
摘要点击次数: 3716
全文下载次数: 5384
中文摘要:
      K-Means聚类算法只能保证收敛到局部最优,从而导致聚类结果对初始代表点的选择非常敏感.许多研究工作都着力于降低这种敏感性.然而,K-Means的局部最优和结果敏感性却构成了K-MeanSCAN聚类算法的基础.K-MeanSCAN算法对数据集进行多次采样和K-Means预聚类以产生多组不同的聚类结果,来自不同聚类结果的子簇之间必然会存在交集.算法的核心思想是,利用这些交集构造出关于子簇的加权连通图,并根据连通性合并子簇.理论和实验证明,K-MeanScan算法可以在很大程度上提高聚类结果的质量和算法的效率.
英文摘要:
      K-Means is the most popular clustering algorithm with the convergence to one of numerous local minima, which results in much sensitivity to initial representatives. Many researches are made to overcome the sensitivity of K-Means algorithm. However, this paper proposes a novel clustering algorithm called K-MeanSCAN by means of the local optimality and sensitivity of K-Means. The core idea is to build the connectivity between sub-clusters based on the multiple clustering results of K-Means, where these clustering results are distinct because of local optimality and sensitivity of K-Means. Then a weighted connected graph of the sub-clusters is constructed using the connectivity, and the sub-clusters are merged by the graph search algorithm. Theoretic analysis and experimental demonstrations show that K-MeanSCAN outperforms existing algorithms in clustering quality and efficiency.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利