Share Email Print

Proceedings Paper

The validity of pyramid K-means clustering
Author(s): Dan E. Tamir; Chi-Yeon Park; Wook-Sung Yoo
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper 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.

Paper Details

Date Published: 17 September 2007
PDF: 12 pages
Proc. SPIE 6700, Mathematics of Data/Image Pattern Recognition, Compression, Coding, and Encryption X, with Applications, 67000D (17 September 2007); doi: 10.1117/12.735436
Show Author Affiliations
Dan E. Tamir, Texas State Univ., San Marcos (United States)
Chi-Yeon Park, Kwandong Univ. (South Korea)
Wook-Sung Yoo, Gannon Univ. (United States)

Published in SPIE Proceedings Vol. 6700:
Mathematics of Data/Image Pattern Recognition, Compression, Coding, and Encryption X, with Applications
Gerhard X. Ritter; Mark S. Schmalz; Junior Barrera; Jaakko T. Astola, Editor(s)

© SPIE. Terms of Use
Back to Top