An Efficient Initialization of the K-Means Algorithm

• Activity Number: 295
• Type: Contributed
• Date/Time: Tuesday, July 31, 2012 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Igor Melnykov*+ and Volodymyr Melnykov
• Companies: Colorado State University Pueblo and North Dakota State University
• Keywords: cluster analysis ; K-means ; initialization ; Mahalanobis distance

Abstract

K-means is a popular method of clustering thanks to its simplicity and high computational speed. In its basic form, the algorithm minimizes the average squared Euclidean distance from points to their cluster centers. Thus, the quality of the solution suggested by the algorithm depends on the initial set of cluster centers as well as the shapes of clusters, since the use of Euclidian distances is beneficial in the case when the data form homogeneous spherical groups. One challenge in choosing the initial set of cluster centers is to have all clusters represented, which makes the convergence to the optimal solution more likely. Our proposed technique aims at achieving the proper cluster representation in the initial set of points. We also make the method more flexible by considering the Mahalanobis distance in the computations.