Efficient computation of PCA with SVD in SQL

ABSTRACT

PCA is one of the most common dimensionality reduction techniques with broad applications in data mining, statistics and signal processing. In this work we study how to leverage a DBMS computing capabilities to solve PCA. We propose a solution that combines a summarization of the data set with the correlation or covariance matrix and then solve PCA with Singular Value Decomposition (SVD). Deriving the summary matrices allow analyzing large data sets since they can be computed in a single pass. Solving SVD without external libraries proves to be a challenge to compute in SQL. We introduce two solutions: one based in SQL queries and a second one based on User-Defined Functions. Experimental evaluation shows our method can solve larger problems in less time than external statistical packages.

REFERENCES

• 1: Christos Boutsidis , Michael W. Mahoney , Petros Drineas, Unsupervised feature selection for principal components analysis, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401903]
• 2: Kaushik Chakrabarti , Eamonn Keogh , Sharad Mehrotra , Michael Pazzani, Locally adaptive dimensionality reduction for indexing large time series databases, ACM Transactions on Database Systems (TODS), v.27 n.2, p.188-228, June 2002 [doi>10.1145/568518.568520]
• 3: Salim Chitroub , Amrane Houacine , Boualem Sansal, A new PCA-based method for data compression and enhancement of multi-frequency polarimetric SAR imagery, Intelligent Data Analysis, v.6 n.2, p.187-207, April 2002
• 4: Alexandre d'Aspremont , Francis Bach , Laurent El Ghaoui, Optimal Solutions for Sparse Principal Component Analysis, The Journal of Machine Learning Research, 9, p.1269-1294, 6/1/2008
• 5: Chris Ding , Xiaofeng He, K-means clustering via principal component analysis, Proceedings of the twenty-first international conference on Machine learning, p.29, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015408]
• 6: J. J. Gerbrands. On the relationships between svd, klt and pca. Pattern Recognition, 14(1--6):375--381, 1981.
• 7: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 8: T. Hastie, R. Tibshirani, and J. H. Friedman. The Elements of Statistical Learning. Springer, New York, 1st edition, 2001.
• 9: Mia Hubert , Sanne Engelen, Robust PCA and classification in biosciences, Bioinformatics, v.20 n.11, p.1728-1736, July 2004 [doi>10.1093/bioinformatics/bth158]
• 10: Neil Lawrence, Probabilistic Non-linear Principal Component Analysis with Gaussian Process Latent Variable Models, The Journal of Machine Learning Research, 6, p.1783-1816, 12/1/2005
• 11: Sofia Mosci , Lorenzo Rosasco , Alessandro Verri, Dimensionality reduction and generalization, Proceedings of the 24th international conference on Machine learning, p.657-664, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273579]
• 12: Vinay Nadimpally , Mohammed J. Zaki, A novel approach to determine normal variation in gene expression data, ACM SIGKDD Explorations Newsletter, v.5 n.2, December 2003 [doi>10.1145/980972.980975]
• 13: Carlos Ordonez, Horizontal aggregations for building tabular data sets, Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13, 2004, Paris, France [doi>10.1145/1008694.1008700]
• 14: Carlos Ordonez, Vertical and horizontal percentage aggregations, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007670]
• 15: Carlos Ordonez, Optimizing recursive queries in SQL, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066260]
• 16: Carlos Ordonez, Building statistical models and scoring with UDFs, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247599]
• 17: Carlos Ordonez , Javier García-García, Vector and matrix operations programmed with UDFs in a relational DBMS, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183687]
• 18: Huseyin Polat , Wenliang Du, SVD-based collaborative filtering with privacy, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066860]
• 19: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical Recipes 3rd Edition: The Art of Scientific Computing, Cambridge University Press, New York, NY, 2007
• 20: Waree Rinsurongkawong , Carlos Ordonez, Microarray data analysis with PCA in a DBMS, Proceeding of the 2nd international workshop on Data and text mining in bioinformatics, October 30-30, 2008, Napa Valley, California, USA [doi>10.1145/1458449.1458456]
• 21: Shaharuddin Salleh , Albert Y. Zomaya , Sakhinah A. Bakar, Computing for Numerical Methods Using Visual C++, 2007
• 22: Polyxeni Zacharouli , Michalis Titsias , Michalis Vazirgiannis, Web Page Rank Prediction with PCA and EM Clustering, Proceedings of the 6th International Workshop on Algorithms and Models for the Web-Graph, February 12-13, 2009, Barcelona, Spain [doi>10.1007/978-3-540-95995-3_9]
• 23: Xiao-Sheng Zhuang , Dao-Qing Dai, Improved discriminate analysis for high-dimensional data and its application to face recognition, Pattern Recognition, v.40 n.5, p.1570-1578, May, 2007 [doi>10.1016/j.patcog.2006.11.015]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Singular value decomposition

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Performance, Theory

Keywords:
DBMS, PCA, SQL, SVD