Label Propagation through Linear Neighborhoods
Authors:
Top Cited Papers
- 27 November 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 20 (1) , 55-67
Abstract
In many practical data mining applications such as text classification, unlabeled training examples are readily available, but labeled ones are fairly expensive to obtain. Therefore, semi supervised learning algorithms have aroused considerable interests from the data mining and machine learning fields. In recent years, graph-based semi supervised learning has been becoming one of the most active research areas in the semi supervised learning community. In this paper, a novel graph-based semi supervised learning approach is proposed based on a linear neighborhood model, which assumes that each data point can be linearly reconstructed from its neighborhood. Our algorithm, named linear neighborhood propagation (LNP), can propagate the labels from the labeled points to the whole data set using these linear neighborhoods with sufficient smoothness. A theoretical analysis of the properties of LNP is presented in this paper. Furthermore, we also derive an easy way to extend LNP to out-of-sample data. Promising experimental results are presented for synthetic data, digit, and text classification tasks.Keywords
This publication has 18 references indexed in Scilit:
- Semi-Supervised Learning2006
- Label propagation through linear neighborhoods2006
- Tikhonov regularization and semi-supervised learning on large graphs2004
- Nonlinear Dimensionality Reduction by Locally Linear EmbeddingScience, 2000
- A Global Geometric Framework for Nonlinear Dimensionality ReductionScience, 2000
- Text Classification from Labeled and Unlabeled Documents using EMMachine Learning, 2000
- Combining labeled and unlabeled data with co-training1998
- The Nature of Statistical Learning Theory1995
- The effect of unlabeled samples in reducing the small sample size problem and mitigating the Hughes phenomenonIEEE Transactions on Geoscience and Remote Sensing, 1994
- Induction of decision treesMachine Learning, 1986