计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (14): 49-52.DOI: 10.3778/j.issn.1002-8331.2009.14.013

• 研究、探讨 • 上一篇    下一篇

BK-means:骨架初始解K-means

宗 瑜1,2,金 萍3,李明楚1   

  1. 1.大连理工大学 软件学院,辽宁 大连 116621
    2.澳大利亚维多利亚大学 信息应用中心,VIC 8001
    3.皖西学院 计算机科学与技术系,安徽 六安 237012
  • 收稿日期:2008-12-19 修回日期:2009-02-25 出版日期:2009-05-11 发布日期:2009-05-11
  • 通讯作者: 宗 瑜

BK-means:Backbone initialization K-means

ZONG Yu1,2,JIN Ping3,LI Ming-chu1   

  1. 1.School of Software,Dalian University of Technology,Dalian,Liaoning 116621,China
    2.Centre for Applied Informatics,Victoria University,VIC 8001,Melbourne Australia
    3.Department of Computer Science and Technology,West Anhui University,Liu’an,Anhui 237012,China
  • Received:2008-12-19 Revised:2009-02-25 Online:2009-05-11 Published:2009-05-11
  • Contact: ZONG Yu

摘要: K-means是典型的启发式聚类算法,容易受到初始解的影响而无法获得高质量的聚类结果。骨架是近年来启发式算法设计的研究热点,它是指所有全局最优解中相同的部分,对于提高启发式算法性能具有重要意义。给出的骨架初始解K-means算法(BK-means)的基本思想是:首先利用K-means算法得到一组局部最优解(聚类结果),通过对局部最优解求交得到骨架簇。利用骨架簇构造骨架初始解及新的搜索空间。最后以骨架初始解引导K-means算法在新的搜索空间中搜索聚类结果。在15组仿真数据集和4组实际数据集上的实验结果表明,BK-means算法具有获得高内聚、高分离的聚类结果能力。

关键词: 聚类, K-means算法, 启发式算法, 骨架初始解

Abstract: K-means is one of classical heuristic clustering algorithm,which is sensitive to initialization and may not produce ideal optimal results.In recent years,the backbone(the shared common parts of all optimal solutions) has attracted many interests in heuristic algorithm design,due to its impact on improving the performance of heuristic algorithms.In this paper,a backbone initialization K-means(BK-means) algorithm is proposed.The main idea is to find out the backbone cluster which is the intersection of several local suboptimal solutions obtained by run K-means algorithm several times,then generate a backbone initialization and new search space.Finally,K-means is run again on the new search space with the backbone initialization.Experiments on 15 synthesis and 4 real datasets show that BK-means has significant effects for improving the quality of clustering.

Key words: clustering, K-means algorithm, heuristic algorithm, backbone initialization