×

Robust path-based spectral clustering. (English) Zbl 1122.68525

Summary: Spectral clustering and path-based clustering are two recently developed clustering approaches that have delivered impressive results in a number of challenging clustering tasks. However, they are not robust enough against noise and outliers in the data. In this paper, based on M-estimation from robust statistics, we develop a robust path-based spectral clustering method by defining a robust path-based similarity measure for spectral clustering under both unsupervised and semi-supervised settings. Our proposed method is significantly more robust than spectral clustering and path-based clustering. We have performed experiments based on both synthetic and real-world data, comparing our method with some other methods. In particular, color images from the Berkeley segmentation data set and benchmark are used in the image segmentation experiments. Experimental results show that our method consistently outperforms other methods due to its higher robustness.

MSC:

68T10 Pattern recognition, speech recognition
68T05 Learning and adaptive systems in artificial intelligence

Software:

BSDS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Duda, R. O.; Hart, P. E.; Stork, D. G., Pattern Classification, second ed. (2001), Wiley: Wiley New York, NY, USA
[2] Jain, A. K.; Dubes, R. C., Algorithms for Clustering Data (1988), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ, USA · Zbl 0665.62061
[3] A.Y. Ng, M.I. Jordan, Y. Weiss, On spectral clustering: analysis and an algorithm, in: T.G. Dietterich, S. Becker, Z. Ghahramani (Eds.), Advances in Neural Information Processing Systems, vol. 14, MIT Press, Cambridge, MA, USA, 2002, pp. 849-856.; A.Y. Ng, M.I. Jordan, Y. Weiss, On spectral clustering: analysis and an algorithm, in: T.G. Dietterich, S. Becker, Z. Ghahramani (Eds.), Advances in Neural Information Processing Systems, vol. 14, MIT Press, Cambridge, MA, USA, 2002, pp. 849-856.
[4] J. Shi, J. Malik, Normalized cuts and image segmentation, in: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Juan, Puerto Rico, 17-19 June 1997, pp. 731-737.; J. Shi, J. Malik, Normalized cuts and image segmentation, in: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Juan, Puerto Rico, 17-19 June 1997, pp. 731-737.
[5] Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 22, 8, 888-905 (2000)
[6] Y. Weiss, Segmentation using eigenvectors: a unifying view, in: Proceedings of the Seventh IEEE International Conference on Computer Vision, vol. 2, Kerkyra, Greece, 20-27 September 1999, pp. 975-982.; Y. Weiss, Segmentation using eigenvectors: a unifying view, in: Proceedings of the Seventh IEEE International Conference on Computer Vision, vol. 2, Kerkyra, Greece, 20-27 September 1999, pp. 975-982.
[7] Fischer, B.; Buhmann, J. M., Path-based clustering for grouping of smooth curves and texture segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 25, 4, 513-518 (2003)
[8] B. Fischer, V. Roth, J.M. Buhmann, Clustering with the connectivity kernel, in: S. Thrun, L. Saul, B. Schölkopf (Eds.), Advances in Neural Information Processing Systems, vol. 16, MIT Press, Cambridge, MA, USA, 2004.; B. Fischer, V. Roth, J.M. Buhmann, Clustering with the connectivity kernel, in: S. Thrun, L. Saul, B. Schölkopf (Eds.), Advances in Neural Information Processing Systems, vol. 16, MIT Press, Cambridge, MA, USA, 2004.
[9] B. Fischer, T. Zöller, J.M. Buhmann, Path based pairwise data clustering with application to texture segmentation, in: M.A.T. Figueiredo, J. Zerubia, A.K. Jain (Eds.), Proceedings of the Third International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, Sophia Antipolis, France, 3-5 September 2001, pp. 235-250.; B. Fischer, T. Zöller, J.M. Buhmann, Path based pairwise data clustering with application to texture segmentation, in: M.A.T. Figueiredo, J. Zerubia, A.K. Jain (Eds.), Proceedings of the Third International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, Sophia Antipolis, France, 3-5 September 2001, pp. 235-250.
[10] Huber, P. J., Robust regression: asymptotics, conjectures, and Monte Carlo, Ann. Stat., 1, 5, 799-821 (1973) · Zbl 0289.62033
[11] Comaniciu, D.; Meer, P., Mean shift: a robust approach toward feature space analysis, IEEE Trans. Pattern Anal. Mach. Intell., 24, 5, 603-619 (2002)
[12] Fischer, B.; Buhmann, J. M., Bagging for path-based clustering, IEEE Trans. Pattern Anal. Mach. Intell., 25, 11, 1411-1415 (2003)
[13] O. Chapelle, A. Zien, Semi-supervised classification by low density separation, in: Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, Barbados, 6-8 January 2005, pp. 57-64.; O. Chapelle, A. Zien, Semi-supervised classification by low density separation, in: Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, Barbados, 6-8 January 2005, pp. 57-64.
[14] L. Zelnik, P. Perona, Self-tuning spectral clustering, in: Advances in Neural Information Processing Systems, vol. 17, 2005.; L. Zelnik, P. Perona, Self-tuning spectral clustering, in: Advances in Neural Information Processing Systems, vol. 17, 2005.
[15] K. Wagstaff, C. Cardie, Clustering with instance-level constraints, in: Proceedings of the 17th International Conference on Machine Learning, Stanford, CA, USA, 29 June-2 July 2000, pp. 1103-1110.; K. Wagstaff, C. Cardie, Clustering with instance-level constraints, in: Proceedings of the 17th International Conference on Machine Learning, Stanford, CA, USA, 29 June-2 July 2000, pp. 1103-1110.
[16] K. Wagstaff, C. Cardie, S. Rogers, S. Schroedl, Constrained \(k\); K. Wagstaff, C. Cardie, S. Rogers, S. Schroedl, Constrained \(k\)
[17] D. Klein, S.D. Kamvar, C.D. Manning, From instance-level constraints to space-level constraints: making the most of prior knowledge in data clustering, in: Proceedings of the 19th International Conference on Machine Learning, Sydney, Australia, 8-12 July 2002, pp. 307-314.; D. Klein, S.D. Kamvar, C.D. Manning, From instance-level constraints to space-level constraints: making the most of prior knowledge in data clustering, in: Proceedings of the 19th International Conference on Machine Learning, Sydney, Australia, 8-12 July 2002, pp. 307-314.
[18] E.P. Xing, A.Y. Ng, M.I. Jordan, S. Russell, Distance metric learning, with application to clustering with side-information, in: S. Becker, S. Thrun, K. Obermayer (Eds.), Advances in Neural Information Processing Systems, vol. 15, MIT Press, Cambridge, MA, USA, 2003, pp. 505-512.; E.P. Xing, A.Y. Ng, M.I. Jordan, S. Russell, Distance metric learning, with application to clustering with side-information, in: S. Becker, S. Thrun, K. Obermayer (Eds.), Advances in Neural Information Processing Systems, vol. 15, MIT Press, Cambridge, MA, USA, 2003, pp. 505-512.
[19] A. Bar-Hillel, T. Hertz, N. Shental, D. Weinshall, Learning distance functions using equivalence relations, in: Proceedings of the 20th International Conference on Machine Learning, Washington, DC, USA, 21-24 August 2003, pp. 11-18.; A. Bar-Hillel, T. Hertz, N. Shental, D. Weinshall, Learning distance functions using equivalence relations, in: Proceedings of the 20th International Conference on Machine Learning, Washington, DC, USA, 21-24 August 2003, pp. 11-18. · Zbl 1222.68140
[20] H. Chang, D.Y. Yeung, Locally linear metric adaptation for semi-supervised clustering, in: Proceedings of the 21st International Conference on Machine Learning, Banff, Alberta, Canada, 4-8 July 2004, pp. 153-160.; H. Chang, D.Y. Yeung, Locally linear metric adaptation for semi-supervised clustering, in: Proceedings of the 21st International Conference on Machine Learning, Banff, Alberta, Canada, 4-8 July 2004, pp. 153-160.
[21] Z. Zhang. Learning metrics via discriminant kernels and multidimensional scaling: toward expected Euclidean representation, in: Proceedings of the 20th International Conference on Machine Learning, Washington, DC, USA, 21-24 August 2003, pp. 872-879.; Z. Zhang. Learning metrics via discriminant kernels and multidimensional scaling: toward expected Euclidean representation, in: Proceedings of the 20th International Conference on Machine Learning, Washington, DC, USA, 21-24 August 2003, pp. 872-879.
[22] Rand, W. M., Objective criteria for the evaluation of clustering methods, J. Am. Stat. Assoc., 66, 846-850 (1971)
[23] D.B. Graham, N.M. Allinson, Characterizing virtual eigensignatures for general purpose face recognition, in: H. Wechsler, P.J. Phillips, V. Bruce, F. Fogelman-Soulie, T.S. Huang (Eds.), Face Recognition: From Theory to Applications, NATO ASI Series F, Computer and Systems Sciences, vol. 163, 1998, pp. 446-456.; D.B. Graham, N.M. Allinson, Characterizing virtual eigensignatures for general purpose face recognition, in: H. Wechsler, P.J. Phillips, V. Bruce, F. Fogelman-Soulie, T.S. Huang (Eds.), Face Recognition: From Theory to Applications, NATO ASI Series F, Computer and Systems Sciences, vol. 163, 1998, pp. 446-456.
[24] D. Martin, C. Fowlkes, D. Tal, J. Malik, A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics, in: Proceedings of the Eighth IEEE International Conference on Computer Vision, vol. 2, Vancouver, BC, Canada, 7-14 July 2001, pp. 416-423.; D. Martin, C. Fowlkes, D. Tal, J. Malik, A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics, in: Proceedings of the Eighth IEEE International Conference on Computer Vision, vol. 2, Vancouver, BC, Canada, 7-14 July 2001, pp. 416-423.
[25] Y.Y. Boykov, M.P. Jolly, Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images, in: Proceedings of the Eighth IEEE International Conference on Computer Vision, vol. 1, Vancouver, BC, Canada, 7-14 July 2001, pp. 105-112.; Y.Y. Boykov, M.P. Jolly, Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images, in: Proceedings of the Eighth IEEE International Conference on Computer Vision, vol. 1, Vancouver, BC, Canada, 7-14 July 2001, pp. 105-112.
[26] Li, Y.; Sun, J.; Tang, C. K.; Shum, H. Y., Lazy snapping, ACM Trans. Graphics, 23, 3, 303-308 (2004)
[27] Yu, S. X.; Shi, J., Segmentation given partial grouping constraints, IEEE Trans. Pattern Anal. Mach. Intell., 26, 2, 173-183 (2004)
[28] Fowlkes, C.; Belongie, S.; Chung, F.; Malik, J., Spectral grouping using the Nyström method, IEEE Trans. Pattern Anal. Mach. Intell., 26, 2, 214-225 (2004)
[29] M. Ouimet, Y. Bengio, Greedy spectral embedding, in: Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, Barbados, 6-8 January 2005, pp. 253-260.; M. Ouimet, Y. Bengio, Greedy spectral embedding, in: Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, Barbados, 6-8 January 2005, pp. 253-260.
[30] C. Fowlkes, D. Martin, J. Malik, Learning affinity functions for image segmentation: combining patch-based and gradient-based approaches, in: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, Madison, WI, USA, 18-20 June 2003, pp. 54-61.; C. Fowlkes, D. Martin, J. Malik, Learning affinity functions for image segmentation: combining patch-based and gradient-based approaches, in: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, Madison, WI, USA, 18-20 June 2003, pp. 54-61.
[31] Schölkopf, B.; Smola, A. J., Learning with Kernels (2002), MIT Press: MIT Press Cambridge, MA, USA
[32] J. Ham, D.D. Lee, S. Mika, B. Schölkopf, A kernel view of the dimensionality reduction of manifolds, in: Proceedings of the 21st International Conference on Machine Learning, Banff, Alberta, Canada, 4-8 July 2004, pp. 369-376.; J. Ham, D.D. Lee, S. Mika, B. Schölkopf, A kernel view of the dimensionality reduction of manifolds, in: Proceedings of the 21st International Conference on Machine Learning, Banff, Alberta, Canada, 4-8 July 2004, pp. 369-376.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.