An initialization method for the K-Means algorithm using neighborhood model

被引:171
作者
Cao, Fuyuan [1 ,2 ]
Liang, Jiye [1 ,2 ]
Jiang, Guang [3 ]
机构
[1] Shanxi Univ, Sch Comp & Informat Technol, Taiyuan 030006, Shanxi, Peoples R China
[2] Minist Educ, Key Lab Computat Intelligence & Chinese Informat, Taiyuan 030006, Peoples R China
[3] Chinese Acad Sci, Key Lab Intelligent Informat Proc, Inst Comp Technol, Beijing 100190, Peoples R China
基金
中国国家自然科学基金;
关键词
Neighborhood model; Initial cluster centers; Cohesion degree; Coupling degree; K-Means clustering algorithm;
D O I
10.1016/j.camwa.2009.04.017
中图分类号
O29 [应用数学];
学科分类号
070104 [应用数学];
摘要
As a simple clustering method, the traditional K-Means algorithm has been widely discussed and applied in pattern recognition and machine learning. However, the K-Means algorithm could not guarantee unique clustering result because initial cluster centers are chosen randomly. In this paper, the cohesion degree of the neighborhood of an object and the coupling degree between neighborhoods of objects are defined based on the neighborhood-based rough set model. Furthermore, a new initialization method is proposed, and the corresponding time complexity is analyzed as well. We study the influence of the three norms on clustering, and compare the clustering results of the K-means with the three different initialization methods. The experimental results illustrate the effectiveness of the proposed method. (C) 2009 Elsevier Ltd. All rights reserved.
引用
收藏
页码:474 / 483
页数:10
相关论文
共 31 条
[1]
[Anonymous], P 14 C UNC ART INT
[2]
[Anonymous], 2010, UCI Machine Learning Repository
[3]
Bradley PS, 1997, ADV NEUR IN, V9, P368
[4]
BRADLEY PS, 1998, P 15 INT C MACH LEAR, P91
[5]
BRENDAN JF, 2007, SCIENCE, V315, P972, DOI DOI 10.1126/SCIENCE.1136800
[6]
LOF: Identifying density-based local outliers [J].
Breunig, MM ;
Kriegel, HP ;
Ng, RT ;
Sander, J .
SIGMOD RECORD, 2000, 29 (02) :93-104
[7]
Rough set-based clustering with refinement using Shannon's entropy theory [J].
Chen, Chun-Bao ;
Wang, Li-Ya .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2006, 52 (10-11) :1563-1576
[8]
Duda R.O., 1973, Pattern Classification and Scene Analysis
[9]
Iterative optimization and simplification of hierarchical clusterings [J].
Fisher, D .
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 1996, 4 :147-179
[10]
Fisher D. H., 1987, Machine Learning, V2, P139, DOI 10.1007/BF00114265