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.
RomesburgH. C.Cluster Analysis for Researchers, 1990 (Krieger Publishing, Malabar, Florida).
2.
BilmesJ.VahdatA.HsuW.ImE. J.Empirical observations of probabilistic heuristics for the clustering problem. Technical Report TR-97-018, International Computer Science Institute, Berkeley, California, 1997.
3.
FritzkeB.The LBG-U method for vector quantization—an improvement over LBG inspired from neural networks. Neural Processing Letters 5, No. 1, 1997, pp. 35–45.
4.
KaufmanL.RousseeuwP. J.Finding Groups in Data: An Introduction to Cluster Analysis, 1990 (John Wiley, New York).
5.
PaoY.-H.Adaptive Pattern Recognition and Neural Networks, 1989 (Addison-Wesley, New York).
6.
TheilerJ.GislerG.A contiguity-enhanced K-means clustering algorithm for unsupervised multispectral image segmentation. Proc. SPIE, 1997, 3159, 108–118.
7.
GeeC. J.FabellaA. B.FernandesI. B.TuretskyI. B.GurC. R.GurE.New experimental results in atlas-based brain morphometry. In Proceedings of SPIE Medical Imaging 1999: Image Processing (Ed. HansonK. M.), Bellingham, Washington, 1999, pp. 604–611.
8.
HansenL. K.LarsenJ.Unsupervised learning and generalisation. In Proceedings of the IEEE International Conference on Neural Network, Washington DC, June 1996, pp. 25–30.
9.
McGovernA.An algorithm for automatically learning macro-actions. In NIPS1998 Workshop on Abstraction and Hierarchy in Reinforcement Learning, Denver, Colorado, 1998.
10.
CookG. D.RobinsonA. J.Utterance clustering for large vocabulary continuous speech recognition. In Proceedings of the European Conference on Speech Technology, Madrid, Spain, Vol. I, 1995, pp. 219–222.
11.
KosmalaA.RottlandJ.RigollG.Improved online handwriting recognition using context dependent hidden Markov models. In Proceedings of the International Conference on Document Analysis and Recognition, Ulm, Germany, 1997, pp. 641–644.
12.
JosienK.LiaoT. W.Simultaneous grouping of parts and machines with an integrated fuzzy clustering method. Fuzzy Sets and Systems, 2002, 126(1), 1–21.
13.
LozanoS.DobadoD.LarranetaJ.OnievaL.Modified fuzzy C-means algorithm for cellular manufacturing. Fuzzy Sets and Systems, 2002, 126(1), 23–32.
14.
MacQueenJ. B.Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1. Statistics, Berkeley, California, 1967, pp. 281–297 (University of California Press, Los Angeles, California).
15.
BottouL.BengioY.Convergence properties of the K-means algorithm. In Advances in Neural Information Processing Systems, Vol. 7, 1995 (MIT Press, Cambridge, Massachusetts).
16.
PenaJ. M.LazanoJ. A.LarranagaP.An empirical comparison of four initialisation methods for the K-means algorithm. Pattern Recognition Lett., 1999, 20, 1027–1040.
17.
Al-DaoudM. B.VenkateswarluN. B.RobertsS. A.Fast K-means clustering algorithms. Report 95.18, School of Computer Studies, University of Leeds, June 1995.
18.
AlsabtiK.RankaS.SinghV.An efficient K-means clustering algorithm. In Proceedings of the First Workshop on High-Performance Data Mining, Orlando, Florida, 1998; ftp://ftp.cise.ufl.edu/pub/faculty/ranka/Proceedings.
19.
PellegD.MooreA.Accelerating exact K-means algorithms with geometric reasoning. In Proceedings of the Conference on Knowledge Discovery in Databases1999 (KDD99), San Diego, California, 1999, pp. 277–281.
20.
CastroV. E.YangJ.A fast and robust general purpose clustering algorithm. In Fourth European Workshop on Principles of Knowledge Discovery in Databases and Data Mining 2000 (PKDD00), Lyon, France, 2000.
21.
KanungoT.MountD. M.NetanyahuN.PiatkoC.SilvermanR.WuA.The efficient K-means clustering algorithm: Analysis and implementation. IEEE Trans. Pattern Analysis and Mach. Intell., 2002, 24(7), 881–892.
22.
BermejoS.CabestanyJ.The effect of finite sample size on on-line K-means. Neurocomputing, 2002, 48, 511–539.
23.
Al-DaoudM. B.VenkateswarluN. B.RobertsS. A.New methods for the initialisation of clusters. Pattern Recognition Lett., 1996, 17, 451–455.
24.
EpterS.KrishnamoorthyM.ZakiM.Clusterability detection and initial seed selection in large data sets. Technical Report 99-6, Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York, 1999.
25.
BradleyS.FayyadU. M.Refining initial points for K-means clustering. In Proceedings of the Fifteenth International Conference on Machine Learning (ICML 1998) (Ed. ShavlikJ.), Madison, Wisconsin, 1998, pp. 91–99 (Morgan Kaufmann, San Francisco, California).
PellegD.MooreA.X-means: Extending K-means with efficient estimation of the number of clusters. In Proceedings of the Seventeenth International Conference on Machine Learning (ICML2000), Stanford, California, 2000.
BlakeC.KeoghE.MerzC. J.UCI Repository of machine learning databases. Department of Information and Computer Science, University of California Irvine, California, 1998.
