Abstract
Constrained spectral clustering (CSC) has recently shown great promise in improving clustering accuracy or catering for some specific grouping bias by encoding pairwise constraints into spectral clustering. Essentially, the existing CSC algorithms coarsely lie in two camps in terms of encoding pairwise constraints: (1) they modify the original similarity matrix to encode pairwise constraints; (2) they regularize the spectral embedding to encode pairwise constraints. Those methods have made significant progresses, but little of them takes the extensional sense of pairwise constraints into account, e.g., respective neighbors of two musk-link points lie in a same cluster with certain high probabilities, and respective neighbors of two cannot-link points lie in different clusters with certain high probabilities, etc. In this paper, we use absorbing Markov chains to formulate the extensional sense of instance-level constraints as such, under the assumption that the formulation aids in improving the accuracy of CSC. We describe a new CSC algorithm which could propagates the extensional sense over a partly-labeled affinity graph. Experiments over publicly available datasets verify the performance of our algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Jain, A., Murty, M., Flynn, P.: Data clustering: A review. ACM Computing Survey 31(3), 264–323 (1999)
Wagstaff, K., Cardie, C., Rogers, S., Schroedl, S.: Constrained k-means clustering with background knowledge. In: The 18th International Conference on Machine Learning, pp. 577–584. Morgan Kaufmann (2001)
Yu, S.X., Shi, J.B.: Grouping with bias. In: Advances in Neural Information Processing Systems. MIT Press (2001)
Shental, N., Bar-hillel, A., Hertz, T., Weinshall, D.: Computing gaussian mixture models with em using equivalence constraints. In: Advances in Neural Information Processing Systems 16. MIT Press (2003)
Kamvar, S.D., Klein, D., Manning, C.D.: Spectral learning. In: The International Joint Conferences on Artificial Intelligence, pp. 561–566 (2003)
Ji, X., Xu, W.: Document clustering with prior knowledge. In: The 29th Annual International Conference on Research and Development in Information Retrieval, pp. 405–412. ACM, New York (2006)
Lu, Z.: Constrained spectral clustering through affinity propagation. In: IEEE Conference on Computer Vision and Pattern Recognition. IEEE Computer Society (2008)
Li, Z., Liu, J., Tang, X.: Constrained clustering via spectral regularization. In: IEEE Conference on Computer Vision and Pattern Recognition, pp. 421–428. IEEE (2009)
Coleman, T., Saunderson, J., Wirth, A.: Spectral clustering with inconsistent advice. In: The 25th International Conference on Machine Learning, pp. 152–159. ACM (2008)
Wang, X., Davidson, I.: Flexible constrained spectral clustering. In: The 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 563–572 (2010)
Shi, J.B., Malik, J.: Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8), 888–905 (2000)
Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: Advances in Neural Information Processing Systems 14, pp. 849–856. MIT Press (2001)
Zelnik-manor, L., Perona, P.: Self-tuning spectral clustering. In: Advances in Neural Information Processing Systems 17, pp. 1601–1608. MIT Press (2004)
Ning, H., Xu, W., Chi, Y., Gong, Y., Huang, T.: Incremental spectral clustering with application to monitoring of evolving blog communities. In: The SIAM International Conference on Data Mining (2007)
Song, Y., Chen, W.-Y., Bai, H., Lin, C.-J., Chang, E.Y.: Parallel Spectral Clustering. In: Daelemans, W., Goethals, B., Morik, K. (eds.) ECML PKDD 2008, Part II. LNCS (LNAI), vol. 5212, pp. 374–389. Springer, Heidelberg (2008)
Alzate, C., Suykens, J.A.K.: Multiway spectral clustering with out-of-sample extensions through weighted kernel pca. IEEE Transactions Pattern Analysis and Machine Intelligence 32(2), 335–347 (2010)
Rangapuram, S.S., Hein, M.: Constrained 1-spectral clustering. Journal of Machine Learning Research, W & CP 20, 1143–1151 (2012)
Hu, G., Zhou, S., Guan, J., Hu, X.: Towards effective document clustering: A constrained k-means based approach. Information Processing and Management 44(4), 1397–1409 (2008)
Xing, E.P., Ng, A.Y., Jordan, M.I., Russell, S.J.: Distance metric learning with application to clustering with side-information. In: NIPS, pp. 505–512 (2002)
Fowlkes, C., Belongie, S., Chung, F.R.K., Malik, J.: Spectral grouping using the nyström method. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 214–225 (2004)
Macqueen, J.B.: Some methods of classification and analysis of multivariate observations. In: The Fifth Berkeley Symposium on Mathematical Statistics and Probability, pp. 281–297 (1967)
Norris, J.R.: Markov Chains. Cambridge University Press, Cambridge (1997)
Luxburg, U.V.: A tutorial on spectral clustering. Statistics and Computing 17(4), 395–416 (2007)
Roweis, S., Saul, L.: Nonlinear dimensionality reduction by locally linear embedding. Science 290(5500), 2323–2326 (2000)
Jebara, T., Wang, J., Chang, S.: Graph construction and b-matching for semi-supervised learning. In: ICML, p. 56 (2009)
Daitch, S.I., Kelner, J.A., Spielman, D.A.: Fitting a graph to vector data. In: The 26th Annual International Conference on Machine Learning, p. 26 (2009)
Rand, W.M.: Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association 66, 846–850 (1971)
Xu, Q., Desjardins, M., Wagstaff, K.: Constrained spectral clustering under a local proximity structure assumption. In: The International Conference of the Florida Artificial Intelligence Research Society. AAAI Press (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, J., Guan, J. (2012). Constrained Spectral Clustering Using Absorbing Markov Chains. In: Zhou, S., Zhang, S., Karypis, G. (eds) Advanced Data Mining and Applications. ADMA 2012. Lecture Notes in Computer Science(), vol 7713. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35527-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-35527-1_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35526-4
Online ISBN: 978-3-642-35527-1
eBook Packages: Computer ScienceComputer Science (R0)