Soft spectral clustering ensemble applied to image segmentation

Abstract

An unsupervised learning algorithm, named soft spectral clustering ensemble (SSCE), is proposed in this paper. Until now many proposed ensemble algorithms cannot be used on image data, even images of a mere 256 × 256 pixels are too expensive in computational cost and storage. The proposed method is suitable for performing image segmentation and can, to some degree, solve some open problems of spectral clustering (SC). In this paper, a random scaling parameter and Nyström approximation are applied to generate the individual spectral clusters for ensemble learning. We slightly modify the standard SC algorithm to aquire a soft partition and then map it via a centralized logcontrast transform to relax the constraint of probability data, the sum of which is one. All mapped data are concatenated to form the new features for each instance. Principal component analysis (PCA) is used to reduce the dimension of the new features. The final aggregated result can be achieved by clustering dimension-reduced data. Experimental results, on UCI data and different image types, show that the proposed algorithm is more efficient compared with some existing consensus functions.

Keywords

spectral clustering (SC) / Nyström approximation / centralized logcontrast transform / principal component analysis (PCA) / ensemble learning

References

[1] Duda R O, Hart P E, Stork D G. Pattern classification. New York: Wiley Interscience, 2001

[2] Dietterich T G. Machine-learning research: four current directions. AI Magazine, 1997, 18(4): 97–136

[3] Zhou Z H, Wu J, Tang W. Ensembling neural networks: many could be better than all. Artificial Intelligence, 2002, 137(1-2): 239–263

[4] Tang W, Zhou Z. Bagging-based selective clustering ensemble. Journal of Software, 2005, 34(12): 496–502

[5] Strehl A, Ghosh J. Cluster ensembles—a knowledge reuse framework for combining multiple partitions. Journal of Machine Learning Research, 2002, 3(12): 583–617

[6] Liu X, Wang Z, Chen W, Li X. Remote sensing images hierarchical clustering using Markov random field and generalized Gaussian mixture models. Journal of Remote Sensing, 2007, 11(6): 838–844

[7] Fan G, Xia X. A joint multicontext and multiscale approach to Bayesian image segmentation. IEEE Transactions on Geoscience and Remote Sensing, 2001, 39(12): 2680–2688

[8] Topchy A P, Law M H C, Jain A K, Fred A L. Analysis of consensus partition in cluster ensemble. In: Proceedings of the 4th IEEE International Conference on Data Mining. 2004, 225–232

[9] Munkres J. Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 1957, 5(1): 32–38

[10] MacQueen J B. Some methods for classification and analysis of multivariate observation. In: Proceeding of the 5th Berkeley Symp. on Mathematical Statistics and Probability. Berkeley: University of California Press, 1967, 281–297

[11] Ding C H Q, He X, Zha H, Gu M, Simon H D. A min-max cut algorithm for graph partitioning and data clustering. In: Proceedings of IEEE International Conference on Data Mining. 2001, 107–114

[12] Shi J, Malik J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888–905

[13] Ng A, Jordan M, Weiss Y. On spectral clustering: analysis and an algorithm. Advance of Neural Information Processing System. Cambridge: MIT Press, 2002, 849–856

[14] Wang S, Siskind J M. Image segmentation with ratio cut. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(6): 675–690

[15] Bach F R, Jordan M I. Blind one-microphone speech separation: a spectral learning approach. In: Proceedings of Advance of Neural Information Processing System (NIPS). Cambridge: MIT Press, 2005

[16] Odobez J M, Gatica-Perez D, Guillemot M. Video shot clustering using spectral methods. In: Proceedings of International Workshop on Content-based Multimedia Indexing. Rennes, 2003, 94–102

[17] Zhang X, Jiao L, Liu F, Bo L, Gong M. Spectral clustering ensemble applied to SAR image segmentation. IEEE Transactions on Geoscience and Remote Sensing, 2008, 46(7): 2126–2136

[18] Dhillon I S. Co-clustering documents and words using bipartite spectral graph parititioning. In: Proceedings of Knowledge Discovery and Data Mine. 2001, 269–274

[19] Topchy A, Jain A K, Punch W. Clustering ensembles: models of consensus and weak partitions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(12): 1866–1881

[20] Topchy A, Jain A K, Punch W. Combining multiple weak clusterings. In: Proceedings of IEEE International Conference on Data Mining. Melbourne, 2003, 331–338

[21] Fred A L N, Jain A K. Combining multiple clusterings using evidence accumulation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(6): 835–850

[22] Fred A L N. Data clustering using evidence accumulation. In: Proceeding of the 16th International Conference on Pattern Recognition. Quebec, 2002, 276–280

[23] Fred A L N. Finding consistent clusters in data partitions. In: Proceeding of the 3d International Workshop on Multiple Classifier System. Roli J K F, ed. LNCS 2364, 2001, 309–318

[24] Fern X Z, Brodley C E. Random projection for high dimensional data clustering: a cluster ensemble approach. In: Proceedings of the 20th International Conference on Machine Learning (ICML). Washington DC, 2003, 186–193

[25] Fischer B, Buhmann J M. Path-based clustering for grouping of smooth curves and texture segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(4): 513–518

[26] Minaei-Bidgoli B, Topchy A, Punch W F. Ensembles of partitions via data resampling. In: Proceedings of International Conference on Information Technology, ITCC. LasVegas, 2004, 188–192

[27] Fred A L N. Finding consistent clusters in data partitions. In: Proceedings of the 3d International Workshop on Multiple Classifier System. Roli J K F (ed.), LNCS 2364, 2001, 309–318

[28] Wang X, Yang C Y, Zhou J. Clustering aggregation by probability accumulation. Pattern Recognition, 2009, 42(5): 668–675

[29] Karypis G, Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 1995, 20(1): 359–392

[30] Karypis G, Aggarwal R, Kumar V, Shekhar S. Multilevel hypergraph partitioning: application in VLSI domain. In: Proceedings of ACM/IEEE Design Automation Conference, 1997, 526–529

[31] Fern X Z, Brodley C E. Solving cluster ensemble problems by bipartite graph partitioning. In: Proceedings of the 21st International Conference on Machine Learning (ICML). Canada, 2004

[32] Dempster A P, Laird N M, Rubin D B. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, Series A (General), 1977, 39(1): 1–38

[33] Punera K, Ghosh J. Soft cluster ensembles. In: Oliveira J V, Pedrycz W, eds. Advances in Fuzzy Clustering and its Applications. Wiley, 2007, 69–90

[34] Gao Y, Gu S, Xia L, . Fuzzy clustering ensemble based on mutual information. In: Proceedings of the 6th WSEAS International Conference on Simulation, Modelling and Optimization, Lisbon, Portugal, 2006, 476–481().

[35] Yu Z, Deng Z, Wong H, . Fuzzy cluster ensemble and its application on 3d head model classification. In: Proceedings of International Joint Conference on Neural Networks (IJCNN). 2008, 569–576

[36] Zhai S, Luo B, Guo Y. Fuzzy clustering ensemble based on dual boosting. In: Proceedings of 4th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). 2007

[37] Fowlkes C, Belongie S, Chung F, Malik J. Spectral grouping using the Nyström method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(2): 214–225

[38] Zhang X. Classification and Segmentation of SAR Images Based on Selective Feature Fusion and Ensemble Learning. Xi'an: Xidian University, 2006

[39] Barthelemy J P, Leclerc B. The median procedure for partitions. In: Cox I J, Hansen P, Julesz B, eds. Partitioning Data Sets. American Mathematical Society, Providence, 1995, 3–34

[40] Aitchison J. The statistical analysis of compositional data. Journal of the Royal Statistical Society, Series B. Methodological, 1982, 44(2): 139–177

[41] Billheimer D, Guttorp P, Fagan W F. Statistical analysis and interpretation of discrete compositional data. National Center for Statistics and the Environment (NRCSE) Technical Report NRCSE-TRS, 11, 1998

[42] Blake C L, Merz C J. UCI repository of machine learning databases.1998, available from: http://www.ics.uci.edu/mlearn/MLRepository

[43] Hansen L, Salamon P. Neural network ensembles. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, 12(10): 993–1001

[44] Melville P, Mooney R J. Constructing diverse classifier ensembles using artificial training examples. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence. 2003, 505–510

[45] Opitz D, Maclin R. Popular ensemble methods: an empirical study. Journal of Artificial Intelligence Research, 1999, 11(8): 169–198

Acknowledgement

The authors would thank the anonymous reviewers for their comments and suggestions which have improved the quality of this paper. This work was supported by the National High Technology Research and Development Program (863 Program) of China (Nos. 2008AA01Z125 and 2009AA12Z210), the National Basic Research Program (973 Program) of China (No. 2006CB705700).

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg