Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Regular Section -- Papers -- Image Recognition, Computer Vision |
RK-Means Clustering: K-Means with Reliability
1 The authors are with the Faculty of System Engineering, Wakayama University, Wakayama-shi, 640–8510 Japan. E-mail: wuhy{at}sys.wakayama-u.ac.jp, 2 Presently, with the Institute of Scientific and Industrial Research, Osaka University.
This paper presents an RK-means clustering algorithm which is developed for reliable data grouping by introducing a new reliability evaluation to the K-means clustering algorithm. The conventional K-means clustering algorithm has two shortfalls: 1) the clustering result will become unreliable if the assumed number of the clusters is incorrect; 2) during the update of a cluster center, all the data points belong to that cluster are used equally without considering how distant they are to the cluster center. In this paper, we introduce a new reliability evaluation to K-means clustering algorithm by considering the triangular relationship among each data point and its two nearest cluster centers. We applied the proposed algorithm to track objects in video sequence and confirmed its effectiveness and advantages.
Key Words: robust clustering, reliability evaluation, K-means clustering, data classification
Manuscript received May 2, 2006. Manuscript revised December 5, 2006.
Reference
[1] J.C. Dunn, "A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters," Journal of Cybernetics, vol.3, pp.32–57, 1973. [2] J.C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithm, Plenum Press, New York, 1981. [3] R.N. Dave and R. Krishnapuram, "Robust clustering methods: A unified review," IEEE Trans. Fuzzy Syst., vol.5, no.2, pp.270–293, May 1997. [4] R.N. Dave, "Characterization and detection of noise," Pattern Recognit. Lett., vol.12, no.11, pp.657–664, 1991. [5] R. Krishnapuram and J.M. Keller, "A possibilistic approach to clustering," IEEE Trans. Fuzzy Syst., vol.1, no.2, pp.98–110, 1993. [6] R. Krishnapuram and J.M. Keller, "The possibilistic c-means algorithm: Insights and recommendations," IEEE Trans. Fuzzy Syst., vol.4, no.3, pp.98–110, 1996. [7] A. Schneider, "Weighted possibilistic c-means clustering algorithms," Ninth IEEE International Conference on Fuzzy Systems, vol.1, pp.176–180, May 2000. [8] N.R. Pal, K. Pal, J.M. Keller, and J.C. Bezdek, "A new hybrid c-means clustering model," IEEE International Conference on Fuzzy Systems, vol.1, pp.179–184, July 2004. [9] N.R. Pal, K. Pal, J.M. Keller, and J.C. Bezdek, "A possibilistic fuzzy c-means clustering algorithm," IEEE Trans. Fuzzy Syst., vol.13, no.4, pp.517–530, Aug. 2005. [10] K.K. Chintalapudi and M. Kam, "A noise-resistant fuzzy C means algorithm for clustering," 1998 IEEE International Conference on Fuzzy Systems, vol.2, pp.1458–1463, May 1998. [11] J.-L. Chen and J.-H. Wang, "A new robust clustering algorithm-density-weighted fuzzy c-means," IEEE International Conference on Systems, Man, and Cybernetics, vol.3, pp.90–94, 1999. [12] J.M. Leski, "Generalized weighted conditional fuzzy clustering," IEEE Trans. Fuzzy Syst., vol.11, no.6, pp.709–715, 2003. [13] J.M. Jolion, P. Meer, and S. Bataouche, "Robust clustering with applications in computer vision," IEEE Trans. Pattern Anal. Mach. Intell., vol.13, no.8, pp.791–802, Aug. 1991. [14] M.A. Egan, "Locating clusters in noisy data: A genetic fuzzy c-means clustering algorithm," 1998 Conference of the North American Fuzzy Information Processing Society, pp.178–182, Aug. 1998. [15] J.-S. Zhan and Y.-W. Leung, "Robust clustering by pruning outliers," IEEE Trans. Syst. Man Cybern. B, Cybern, vol.33, no.6, pp.983–998, 2003. [16] J.J. DeGruijter and A.B. McBratney, "A modified fuzzy K-means for predictive classification," in Classification and Related Methods of Data Analysis, ed. H.H. Bock, pp.97–104, Elsevier Science, Amsterdam, 1988. [17] C. Hua, H. Wu, T. Wada, and Q. Chen, "K-means tracking with variable ellipse model," IPSJ Tans. CVIM, vol.46, no.Sig 15(CVIM12), pp.59–68, 2005. [18] T. Wada, T. Hamatsuka, and T. Kato, "K-means tracking: A robust target tracking against background involution," MIRU2004, vol.2, pp.7–12, 2004. [19] H.T. Nguyen and A. Semeulders, "Tracking aspects of the foreground against the background," ECCV, vol.2, pp.446–456, 2004. [20] B. Heisele, U. Kreßel, and W. Ritter, "Tracking non-rigid moving objects based on color cluster flow," CVPR, pp.253–257 1997. [21] J. Hartigan and M. Wong, "Algorithm AS136: A k-means clustering algorithm," Applied Statistics, vol.28, pp.100–108, 1979. [22] F. Gibou and R. Fedkiw, "A fast hybrid k-means level set algorithm for segmentation," 4th Annual Hawaii International Conference on Statistics and Mathematics, pp.281–291, 2005. [23] C. Baba, et al., "Multiresolution adaptive K-means algorithm for segmentation of brain MRI," ICSC 1995, pp.347–354, 1995. [24] P.K. Singh, "Unsupervised segmentation of medical images using DCT coefficients," VIP 2003, pp.75–81, 2003. [25] J.B. MacQueen, "Some methods for classification and analysis of multivariate observations," Proc. 5-th Berkeley Symposium on Mathematical Statistics and Probability, vol.1, pp.281–297, Berkeley, University of California Press, 1967. [26] R. Zass and A. Shashua, "A unifying approach to hard and probabilistic clustering," ICCV, vol.1, pp.294–301, 2005. [27] A.Y. Ng, M.I. Jordan, and Y. Weiss, "On spectral clustering: Analysis and an algorithm," NIPS, pp.849–856, 2002. [28] M. Pavan and M. Pelillo, "A new graph-theoretic approach to clustering and segmentation," CVPR, pp.145–152, 2003 [29] S.X. Yu and J. Shi, "Multiclass spectral clustering," ICCV, pp.313–319, 2003.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by HUA, C.
Articles by WADA, T.
Search for Related Content
Social Bookmarking
What's this?