Abstract
In semi-supervised classification, labels smoothness and cluster assumption are the key point of many successful methods. In graph-based semi-supervised classification, graph representations of the data are quite important. Different graph representations can affect the classification results greatly. Considering the two assumptions and graph representations, we propose a novel method to build a better graph for semi-supervised classification. The graph in our method is called m-step Markov random walk graph (mMRW graph). The smoothness of this graph can be controlled by a parameter m. We believe that a relatively much smoother graph will benefit transductive learning. We also discuss some benefits brought by our smooth graphs. A cluster cohesion based parameter learning method can be efficiently applied to find a proper m. Experiments on artificial and real world dataset indicate that our method has a superior classification accuracy over several state-of-the-art methods.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chapelle, O., Weston, J., Schölkopf, B.: Cluster Kernels for Semi-Supervised Learning. In: Advances in Neural Information Processing Systems 15, pp. 585–592. MIT Press, Cambridge (2003)
Chapelle, O., Zien, A.: Semi-Supervised Classification by Low Density Separation. In: Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, pp. 57–64 (2005)
Henk, C.T.: Stochastic Models: An Algorithmic Approach. John Wiley & Sons, Chichester (1994)
Rudnick, J., Gaspari, G.: Elements of the Random Walk: An Introduction for Advanced Students and Researchers. Cambridge University Press, Cambridge (2004)
Seeger, M.: Learning with labeled and unlabeled data. Technical report, Edinburgh University (2000)
Shanbhag, D.N., Rao, C.R. (eds.): Handbook of Stochastic, vol. 19. Elsevier Science, Amsterdam (2001)
Szummer, M., Jaakkola, T.: Partially labeled classification with Markov random walks. Neural Information Processing. Systems (NIPS) 14 (2001)
Zhou, D., et al.: Learning with local and global consistency. In: Advances in Neural Information Processing System 16 (2004)
Zhu, X., Lafferty, J., Ghahramani, Z.: Semi-Supervised Learning Using Gaussian Fields and Harmonic Function. In: Proceedings of The Twentieth International Conference on Machine Learning (2003)
Zhu, X.: Semi-Supervised Learning with Graphs. Doctoral Thesis. CMU-LTI-05-192, Carnegie Mellon University (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhou, X., Li, C. (2006). Semi-supervised Classification Based on Smooth Graphs. In: Li Lee, M., Tan, KL., Wuwongse, V. (eds) Database Systems for Advanced Applications. DASFAA 2006. Lecture Notes in Computer Science, vol 3882. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11733836_53
Download citation
DOI: https://doi.org/10.1007/11733836_53
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33337-1
Online ISBN: 978-3-540-33338-8
eBook Packages: Computer ScienceComputer Science (R0)