An Incremental K-means algorithm
Authors:
- 1 July 2004
- journal article
- research article
- Published by SAGE Publications in Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science
- Vol. 218 (7) , 783-795
Abstract
Data clustering is an important data exploration technique with many applications in engineering, including parts family formation in group technology and segmentation in image processing. One of the most popular data clustering methods is K-means clustering because of its simplicity and computational efficiency. The main problem with this clustering method is its tendency to coverge at a local minimum. In this paper, the cause of this problem is explained and an existing solution involving a cluster centre jumping operation is examined. The jumping technique alleviates the problem with local minima by enabling cluster centres to move in such a radical way as to reduce the overall cluster distortion. However, the method is very sensitive to errors in estimating distortion. A clustering scheme that is also based on distortion reduction through cluster centre movement but is not so sensitive to inaccuracies in distortion estimation is proposed in this paper. The scheme, which is an incremental version of the K-means algorithm, involves adding cluster centres one by one as clusters are being formed. The paper presents test results to demonstrate the efficacy of the proposed algorithm.Keywords
This publication has 17 references indexed in Scilit:
- The global k-means clustering algorithmPattern Recognition, 2003
- The effect of finite sample size on on-line K-meansNeurocomputing, 2002
- An efficient k-means clustering algorithm: analysis and implementationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2002
- Simultaneous grouping of parts and machines with an integrated fuzzy clustering methodFuzzy Sets and Systems, 2002
- Modified fuzzy C-means algorithm for cellular manufacturingFuzzy Sets and Systems, 2002
- The enhanced LBG algorithmNeural Networks, 2001
- Stochastic K-means algorithm for vector quantizationPattern Recognition Letters, 2001
- An empirical comparison of four initialization methods for the K-Means algorithmPattern Recognition Letters, 1999
- New methods for the initialisation of clustersPattern Recognition Letters, 1996
- Optimal adaptive k-means algorithm with dynamic adjustment of learning rateIEEE Transactions on Neural Networks, 1995