Spectral feature selection for supervised and unsupervised learning

ABSTRACT

Feature selection aims to reduce dimensionality for building comprehensible learning models with good generalization performance. Feature selection algorithms are largely studied separately according to the type of learning: supervised or unsupervised. This work exploits intrinsic properties underlying supervised and unsupervised feature selection algorithms, and proposes a unified framework for feature selection based on spectral graph theory. The proposed framework is able to generate families of algorithms for both supervised and unsupervised feature selection. And we show that existing powerful algorithms such as ReliefF (supervised) and Laplacian Score (unsupervised) are special cases of the proposed framework. To the best of our knowledge, this work is the first attempt to unify supervised and unsupervised feature selection, and enable their joint study under a general framework. Experiments demonstrated the efficacy of the novel algorithms derived from the framework.

REFERENCES

• 1: Chapelle, O., Schölkopf, B., and Zien, A. (Eds.) (2006). Semi-supervised learning, chapter Graph-Based Methods. The MIT Press.
• 2: Chung, F. (1997). Spectral graph theory. AMS.
• 3: Jennifer G. Dy , Carla E. Brodley, Feature Selection for Unsupervised Learning, The Journal of Machine Learning Research, 5, p.845-889, 12/1/2004
• 4: Isabelle Guyon , André Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• 5: He, X., Cai, D., & Niyogi, P. (2005). Laplacian score for feature selection. In NIPS. MIT Press.
• 6: Risi Imre Kondor , John D. Lafferty, Diffusion Kernels on Graphs and Other Discrete Input Spaces, Proceedings of the Nineteenth International Conference on Machine Learning, p.315-322, July 08-12, 2002
• 7: Gert R. G. Lanckriet , Nello Cristianini , Peter Bartlett , Laurent El Ghaoui , Michael I. Jordan, Learning the Kernel Matrix with Semidefinite Programming, The Journal of Machine Learning Research, 5, p.27-72, 12/1/2004
• 8: Huan Liu , Lei Yu, Toward Integrating Feature Selection Algorithms for Classification and Clustering, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.491-502, April 2005 [doi>10.1109/TKDE.2005.66]
• 9: Ng, A., Jordan, M., & Weiss, Y. (2001). On spectral clustering: Analysis and an algorithm. NIPS.
• 10: R. B. Lehoucq, Implicitly Restarted Arnoldi Methods and Subspace Iteration, SIAM Journal on Matrix Analysis and Applications, v.23 n.2, p.551-562, 2001 [doi>10.1137/S0895479899358595]
• 11: Marko Robnik-Šikonja , Igor Kononenko, Theoretical and Empirical Analysis of ReliefF and RReliefF, Machine Learning, v.53 n.1-2, p.23-69, October-November 2003 [doi>10.1023/A:1025667309714]
• 12: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.731, June 17-19, 1997
• 13: Smola, A., & Kondor, I. (2003). Kernels and regularization on graphs. COLT.
• 14: Lior Wolf , Amnon Shashua, Feature Selection for Unsupervised and Supervised Inference: The Emergence of Sparsity in a Weight-Based Approach, The Journal of Machine Learning Research, 6, p.1855-1887, 12/1/2005
• 15: Zhang, T., & Ando, R. (2006). Analysis of spectral kernel design based semi-supervised learning. NIPS.
• 16: Zhao, Z., & Liu, H. (2007). Semi-supervised Feature Selection via Spectral Analysis. SDM.