17 September 2007 The validity of pyramid K-means clustering
Author Affiliations +
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.
© (2007) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Dan E. Tamir, Dan E. Tamir, Chi-Yeon Park, Chi-Yeon Park, Wook-Sung Yoo, 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); doi: 10.1117/12.735436; https://doi.org/10.1117/12.735436

Back to Top