The validity of pyramid K-means clustering

Dan E. Tamir; Chi-Yeon Park; Wook-Sung Yoo

doi:10.1117/12.735436

17 September 2007 The validity of pyramid K-means clustering

Dan E. Tamir, Chi-Yeon Park, Wook-Sung Yoo

Proceedings Volume 6700, Mathematics of Data/Image Pattern Recognition, Compression, Coding, and Encryption X, with Applications; 67000D (2007) https://doi.org/10.1117/12.735436
Event: Optical Engineering + Applications, 2007, San Diego, California, United States

Abstract

K-means is a widely used objective optimization clustering method. It is generally implemented along with the minimum square error (MSE) minimization criteria. It has been shown empirically that the algorithm provides "good" MSE results. Nevertheless, K-means has several deficiencies; first, it is sensitive to the seeding method and may only converge to a local optimum. Second, the algorithms is known to be NP complete, hence, validating the quality of results may be intractable. Finally, the convergence rate of the algorithm is dependent on the seeding. Generally, low convergence rate is observed. This paper presents a multi-resolution K-means clustering method which applies the K-means algorithm to a sequence of monotonically increasing-resolution samples of the given data. The cluster-centers obtained from a low resolution stage are used as initial cluster-centers for the next stage which is a higher resolution stage. The idea behind this method is that a good estimation of the initial location of centers can be obtained through K-means clustering of a sample of the input data. This can reduce the convergence time of K-means. Alternatively the algorithm can be used to obtain better MSE in about the same time as the traditional K-means. The validity of pyramid K-means algorithm is tested using Monte Carlo simulations applied to synthetic data and to multi-spectral images and compared to traditional K-means. It is found that in the average case pyramid K-means improves the MSE by a factor of four to six. This may require only 1.35 more iterations than the traditional K-means. Alternatively, it can reduce the computation time by a factor of three to four with a slight improvement in the quality of clustering.

Citation Download Citation

Dan E. Tamir, Chi-Yeon Park, and Wook-Sung Yoo "The validity of pyramid K-means clustering", Proc. SPIE 6700, Mathematics of Data/Image Pattern Recognition, Compression, Coding, and Encryption X, with Applications, 67000D (17 September 2007); https://doi.org/10.1117/12.735436

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available