Unsupervised feature selection for principal components analysis

ABSTRACT

Principal Components Analysis (PCA) is the predominant linear dimensionality reduction technique, and has been widely applied on datasets in all scientific domains. We consider, both theoretically and empirically, the topic of unsupervised feature selection for PCA, by leveraging algorithms for the so-called Column Subset Selection Problem (CSSP). In words, the CSSP seeks the "best" subset of exactly k columns from an m x n data matrix A, and has been extensively studied in the Numerical Linear Algebra community. We present a novel two-stage algorithm for the CSSP. From a theoretical perspective, for small to moderate values of k, this algorithm significantly improves upon the best previously-existing results [24, 12] for the CSSP. From an empirical perspective, we evaluate this algorithm as an unsupervised feature selection strategy in three application domains of modern statistical data analysis: finance, document-term data, and genetics. We pay particular attention to how this algorithm may be used to select representative or landmark features from an object-feature matrix in an unsupervised manner. In all three application domains, we are able to identify k landmark features, i.e., columns of the data matrix, that capture nearly the same amount of information as does the subspace that is spanned by the top k "eigenfeatures."

REFERENCES

• 1: A. d'Aspremont, L. El Ghaoui, M. I. Jordan, and G. R. G.Lanckriet. A Direct Formulation for Sparse PCA Using Semidefinite Programming. SIAM Review, 49(3), July 2007
• 2: A. Ben-Hur and I. Guyon. Detecting stable clusters using principal component analysis. Methods Mol Biol, 224:159--182, 2003.
• 3: Michael W. Berry , Shakhina A. Pulatova , G. W. Stewart, Algorithm 844: Computing sparse reduced-rank approximations to sparse matrices, ACM Transactions on Mathematical Software (TOMS), v.31 n.2, p.252-269, June 2005 [doi>10.1145/1067967.1067972]
• 4: C. H. Bischof , G. Quintana-Ortí, Algorithm 782: codes for rank-revealing QR factorizations of dense matrices, ACM Transactions on Mathematical Software (TOMS), v.24 n.2, p.254-257, June 1998 [doi>10.1145/290200.287638]
• 5: Christian H. Bischof , G. Quintana-Ortí, Computing rank-revealing QR factorizations of dense matrices, ACM Transactions on Mathematical Software (TOMS), v.24 n.2, p.226-253, June 1998 [doi>10.1145/290200.287637]
• 6: C. Boutsidis, M.W. Mahoney, and P. Drineas. Manuscript in preparation, 2008
• 7: J. Cadima, J. O. Cerdeira, and M. Minhoto. Computational aspects of algorithms for variable selection in thecontext of principal components. Computational Statistics & Data Analysis, 47(2):225--236, 2004.
• 8: T. F. Chan. Rank revealing QR factorizations. Linear Algebra Appl, 88/89:67--82, 1987.
• 9: Tony F. Chan , Per Christian Hansen, Some applications of the rank revealing QR factorization, SIAM Journal on Scientific and Statistical Computing, v.13 n.3, p.727-741, May 1992 [doi>10.1137/0913043]
• 10: T. F. Chan and P.C. Hansen. Low-rank revealing QR factorizations. Linear Algebra Appl, 1:33--44, 1994.
• 11: Shivkumar Chandrasekaran , Ilse C. F. Ipsen, On Rank-Revealing Factorisations, SIAM Journal on Matrix Analysis and Applications, v.15 n.2, p.592-622, April 1994 [doi>10.1137/S0895479891223781]
• 12: Amit Deshpande , Luis Rademacher , Santosh Vempala , Grant Wang, Matrix approximation and projective clustering via volume sampling, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1117-1126, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109681]
• 13: Mark Devaney , Ashwin Ram, Efficient Feature Selection in Conceptual Clustering, Proceedings of the Fourteenth International Conference on Machine Learning, p.92-97, July 08-12, 1997
• 14: Petros Drineas , Michael W. Mahoney , S. Muthukrishnan, Subspace sampling and relative-error matrix approximation: column-row-based methods, Proceedings of the 14th conference on Annual European Symposium, p.304-314, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_29]
• 15: P. Drineas, M. W. Mahoney, and S. Muthukrishnan. Relative-error CUR matrix decompositions. http://arxiv.org/abs/0708.3696, 2007.
• 16: Jennifer G. Dy , Carla E. Brodley, Feature Selection for Unsupervised Learning, The Journal of Machine Learning Research, 5, p.845-889, 12/1/2004
• 17: R.D. Fierro, P.C. Hansen, and P. Hansen. UTV tools: Matlab templates for rank-revealing UTV decompositions. Numerical Algorithms, 20(2-3):165--194, 1999.
• 18: L. V. Foster. Rank and null space calculations using matrix decomposition without column interchanges. Linear Algebra Appl, 74:47--71, 1986.
• 19: L.V. Foster and Xinrong Liu. Comparison of rank revealing algorithms applied to matrices with welldefined numerical ranks. manuscript, 2006.
• 20: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
• 21: Evgeniy Gabrilovich , Shaul Markovitch, Text categorization with many redundant features: using aggressive feature selection to make SVMs competitive with C4.5, Proceedings of the twenty-first international conference on Machine learning, p.41, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015388]
• 22: G. H. Golub. Numerical methods for solving linear least squares problems. Numer Math, 7:206--216, 1965.
• 23: G.H. Golub and C.F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, 1989.
• 24: Ming Gu , Stanley C. Eisenstat, Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM Journal on Scientific Computing, v.17 n.4, p.848-869, July 1996 [doi>10.1137/0917055]
• 25: Y. P. Hong and C. T. Pan. Rank-revealing QR factorizations and the singular value decomposition. Math Comp, 58:213--232, 1992.
• 26: W. J. Krzanowski. Selection of variables to preserve multivariate data structure,using principal components. Applied Statistics,36(1):22--33, 1987.
• 27: F.G. Kuruvilla and P.J. Park and S.L. Schreiber. Vector algebra in the analysis of genome-wide expression data. Genome Biology, 3, 2002.
• 28: K. Z. Mao. Identifying critical variables of principal components forunsupervised feature selection. IEEE Transactions on Systems,Man, and Cybernetics, Part B, 35(2):339--344, 2005.
• 29: Michael W. Mahoney , Mauro Maggioni , Petros Drineas, Tensor-CUR decompositions for tensor-based data, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150440]
• 30: P. Menozzi, A. Piazza, and L. Cavalli-Sforza. Synthetic maps of human gene frequencies in Europeans . Science, 201(4358):786--792, 1978.
• 31: Pabitra Mitra , C. A. Murthy , Sankar K. Pal, Unsupervised Feature Selection Using Feature Similarity, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.3, p.301-312, March 2002 [doi>10.1109/34.990133]
• 32: Open Directory Project. http://www.dmoz.org/
• 33: C. T. Pan. On the existence and computation of rank-revealing LUfactorizations. Linear Algebra Appl, 316:199--222, 2000.
• 34: C. T. Pan and P. T. P. Tang. Bounds on singular values revealed by QR factorizations. BIT Numerical Mathematics, 39:740--756, 1999.
• 35: P. Paschou, E. Ziv, E.G. Burchard, S. Choudhry, W.R. Cintron, M.WMahoney, and P. Drineas. PCA-Correlated SNPs for Structure Identification in Worldwide Human Populations, PLoS Genetics,9(3), 2007.
• 36: P. Paschou, M.W. Mahoney, A. Javed, J.R. Kidd, A.J. Pakstis, S.Gu, K.K. Kidd, and P. Drineas. Intra- and Inter-population genotype reconstruction from tagging SNPs, Genome Research, 17: 96--107, 2007.
• 37: N.A. Rosenberg, L.M. Li, R. Ward, and J.K. Pritchard. Informativeness of genetic markers for inference of ancestry. Am J Hum Genet, 73(6):1402--1422, 2003.
• 38: G.W. Stewart. Four algorithms for the efficientcomputation of truncated QR approximations to a sparse matrix. Num Math, 83:313--323, 1999.
• 39: Hervé Stoppiglia , Gérard Dreyfus , Rémi Dubois , Yacine Oussar, Ranking a random feature for variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• 40: J. Sun, Y. Xie, H. Zhang, and C. Faloutsos. Less is more: Compact matrix decomposition for large sparse graphs, SDM, 2007.
• 41: The International HapMap Consortium. A haplotype map of the human genome. Nature, 437:1299--1320, 2005.
• 42: 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
• 43: Zheng Zhao , Huan Liu, Spectral feature selection for supervised and unsupervised learning, Proceedings of the 24th international conference on Machine learning, p.1151-1157, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273641]
• 44: http://finance.yahoo.com/

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

Additional Classification:
  E. Data
  E.m MISCELLANEOUS

General Terms:
Algorithms, Experimentation, Theory

Keywords:
PCA, random sampling, subset selection