Initialization for K-means clustering using Voronoi diagram

被引：42

作者：

Reddy, Damodar ^{[1
]}

Jana, Prasanta K. ^{[1
]}

机构：

[1] Indian Sch Mines, Dept Comp Sci & Engn, Dhanbad 826004, Bihar, India

来源：

2ND INTERNATIONAL CONFERENCE ON COMPUTER, COMMUNICATION, CONTROL AND INFORMATION TECHNOLOGY (C3IT-2012) | 2012年 / 4卷

关键词：

Clustering; K-means; improved K-means; Voronoi diagram; error rate;

D O I：

10.1016/j.protcy.2012.05.061

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

K-Means algorithm is one of the famous partitioning clustering techniques that has been studied extensively. However, the major problem with this method that it cannot ensure the global optimum results due to the random selection of initial cluster centers. In this paper, we present a novel method that selects the initial cluster centers with the help of Voronoi diagram constructed from the given set of data points. The initial cluster centers are effectively selected from those points which lie on the boundary of higher radius Voronoi circles. As a result, the proposed method automates the selection of the initial cluster centers to supply them for K-means. The proposed method is experimented on various artificial (hand-made) as well as real world data sets of various dimensions. It is observed that it is able to produce better clustering results than the traditional K-means and the improved K-means. (C) 2011 Published by Elsevier Ltd. Selection and/or peer-review under responsibility of C3IT

引用

页码：395 / 400

页数：6

共 11 条

[1] New methods for the initialisation of clusters
AlDaoud, MB
Roberts, SA
[J]. PATTERN RECOGNITION LETTERS, 1996, 17 (05) : 451 - 455
[2] An evolutionary technique based on K-Means algorithm for optimal clustering in RN
Bandyopadhyay, S
Maulik, U
[J]. INFORMATION SCIENCES, 2002, 146 (1-4) : 221 - 237
[3] An initialization method for the K-Means algorithm using neighborhood model
Cao, Fuyuan
Liang, Jiye
Jiang, Guang
[J]. COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2009, 58 (03) : 474 - 483
[4] Herding and clustering in economics: The Yule-Zipf-Simon model
Garibaldi U.
Costantini D.
Donadio S.
Viarengo P.
[J]. Computational Economics, 2006, 27 (1) : 115 - 134
[5] Geraci F, 2007, LECT NOTES COMPUT SC, V4561, P606
[6] Jain A. K., 1988, Algorithms for Clustering Data
[7] Cluster center initialization algorithm for K-means clustering
Khan, SS
Ahmad, A
[J]. PATTERN RECOGNITION LETTERS, 2004, 25 (11) : 1293 - 1302
[8] Liu Z, 2011, J FUTURE GENERATION
[9] Hierarchical initialization approach for K-Means clustering
Lu, J. F.
Tang, J. B.
Tang, Z. M.
Yang, J. Y.
[J]. PATTERN RECOGNITION LETTERS, 2008, 29 (06) : 787 - 795
[10] Preparata Franco P, 1985, Computational Geometry: An Introduction

← 1 2 →