Stable Initialization Scheme for K-Means Clustering  

作　　者：XU Junling XU Baowen ZHANG Weifeng ZHANG Wei HOU Jun 

机构地区：[1]School of Computer Science and Engineering, Southeast University, Nanjing 211189, Jiangsu, China [2]State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, Hubei, China [3]Department of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210003, Jiangsu, China

出　　处：《Wuhan University Journal of Natural Sciences》2009年第1期24-28,共5页武汉大学学报（自然科学英文版）

基　　金：Supported by the National Natural Science Foundation of China (60503020, 60503033, 60703086);the Natural Science Foundation of Jiangsu Province (BK2006094);the Opening Foundation of Jiangsu Key Labo-ratory of Computer Information Processing Technology in Soochow University ( KJS0714);the Research Foundation of Nanjing University of Posts and Telecommunications (NY207052, NY207082)

摘　　要：Though K-means is very popular for general clustering, its performance, which generally converges to numerous local minima, depends highly on initial cluster centers. In this paper a novel initialization scheme to select initial cluster centers for K-means clustering is proposed. This algorithm is based on reverse nearest neighbor （RNN） search which retrieves all points in a given data set whose nearest neighbor is a given query point. The initial cluster centers computed using this methodology are found to be very close to the desired cluster centers for iterative clustering algorithms. This procedure is applicable to clustering algorithms for continuous data. The application of the proposed algorithm to K-means clustering algorithm is demonstrated. An experiment is carried out on several popular datasets and the results show the advantages of the proposed method.Though K-means is very popular for general clustering, its performance, which generally converges to numerous local minima, depends highly on initial cluster centers. In this paper a novel initialization scheme to select initial cluster centers for K-means clustering is proposed. This algorithm is based on reverse nearest neighbor （RNN） search which retrieves all points in a given data set whose nearest neighbor is a given query point. The initial cluster centers computed using this methodology are found to be very close to the desired cluster centers for iterative clustering algorithms. This procedure is applicable to clustering algorithms for continuous data. The application of the proposed algorithm to K-means clustering algorithm is demonstrated. An experiment is carried out on several popular datasets and the results show the advantages of the proposed method.

关 键 词：CLUSTERING unsupervised learning K-MEANS INITIALIZATION 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]