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

被引：3

作者：

宗瑜 ^{[1
,2
]}

金萍 ^{[3
]}

李明楚 ^{[1
]}

机构：

[1] 大连理工大学软件学院

[2] 澳大利亚维多利亚大学信息应用中心

[3] 皖西学院计算机科学与技术系

来源：

计算机工程与应用 | 2009年 / 14期

关键词：

聚类; K-means算法; 启发式算法; 骨架初始解;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：49 / 52

页数：4

共 8 条

[1] 二次分配问题的骨架分析与算法设计 [J].

江贺 ;

张宪超 ;

陈国良 ;

李明楚 .

中国科学(E辑:信息科学), 2008, (02) :209-222

[2] 聚类算法研究 [J].

孙吉贵 ;

刘杰 ;

赵连宇 .

软件学报, 2008, (01) :48-61

[3] 图的二分问题唯一全局最优解实例与骨架计算复杂性 [J].

江贺 ;

张宪超 ;

陈国良 .

科学通报, 2007, (17) :2077-2081

[4] 求解TSP问题的多级归约算法 [J].

邹鹏 ;

周智 ;

陈国良 ;

顾钧 .

软件学报, 2003, (01) :35-42

[5]

Clustering Large Graphs via the Singular Value Decomposition[J] . P. Drineas,A. Frieze,R. Kannan,S. Vempala,V. Vinay.Machine Learning . 2004 (1)

[6] Cluster center initialization algorithm for K-means clustering [J].

Khan, SS ;

Ahmad, A .

PATTERN RECOGNITION LETTERS, 2004, 25 (11) :1293-1302

[7] New methods for the initialisation of clusters [J].

AlDaoud, MB ;

Roberts, SA .

PATTERN RECOGNITION LETTERS, 1996, 17 (05) :451-455

[8]

Initialization of cluster refinement algorithms:a review and comparative study. He J,Lan M,Tan C L,et al. Proceedings of In-ternational Joint Conference on Neural Networks（IJCNN） . 2004

← 1 →