An Optimization Criterion for Generalized Discriminant Analysis on Undersampled Problems
|
Abstract—An optimization criterion is presented for discriminant analysis. The criterion extends the optimization criteria of the classical Linear Discriminant Analysis (LDA) through the use of the pseudoinverse when the scatter matrices are singular. It is applicable regardless of the relative sizes of the data dimension and sample size, overcoming a limitation of classical LDA. The optimization problem can be solved analytically by applying the Generalized Singular Value Decomposition (GSVD) technique. The pseudoinverse has been suggested and used for undersampled problems in the past, where the data dimension exceeds the number of data points. The criterion proposed in this paper provides a theoretical justification for this procedure. An approximation algorithm for the GSVD-based approach is also presented. It reduces the computational complexity by finding subclusters of each cluster and uses their centroids to capture the structure of each cluster. This reduced problem yields much smaller matrices to which the GSVD can be applied efficiently. Experiments on text data, with up to 7,000 dimensions, show that the approximation algorithm produces results that are close to those produced by the exact algorithm.
[1] 982 P. Baldi and G.W. Hatfield, DNA Microarrays and Gene Expression: From Experiments to Data Analysis and Modeling. Cambridge, 2002.
[2] M.W. Berry, S.T. Dumais, and G.W. O'Brien, Using Linear Algebra for Intelligent Information Retrieval SIAM Rev., vol. 37, pp. 573-595, 1995.
[3] P.N. Belhumeur, J. Hespanda, and D. Kriegeman, Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 7, pp. 711-720, July 1997.
[4] D.Q. Dai and P.C. Yuen, Regularized Discriminant Analysis and Its Application to Face Recognition Pattern Recognition, vol. 36, pp. 845-847, 2003.
[5] S. Deerwester, S.T. Dumais, G.W. Furnas, T.K. Landauer, and R. Harshman, Indexing by Latent Semantic Analysis J. Soc. Information Science, vol. 41, pp. 391-407, 1990.
[6] I.S. Dhillon and D.S. Modha, Concept Decompositions for Large Sparse Text Data Using Clustering Machine Learning, vol. 42, pp. 143-175, 2001.
[7] R.O. Duda, P.E. Hart, and D. Stork, Pattern Classification. Wiley, 2000.
[8] R.P.W. Duin, Small Sample Size Generalization Proc. Ninth Scandinavian Conf. Image Analysis, vol. 2, pp. 957-964, 1995.
[9] J.H. Friedman, Regularized Discriminant Analysis J. Am. Statistical Assoc., vol. 84, no. 405, pp. 165-175, 1989.
[10] K. Fukunaga, Introduction to Statistical Pattern Recognition, second ed. Academic Press, 1990.
[11] G.H. Golub and C.F. VanLoan, Matrix Computations. third ed. John Hopkins Univ. Press, 1996.
[12] J.C. Gower, Some Distance Properties of Latent Root and Vector Methods Used in Multivariate Analysis Biometrika, vol. 53, pp. 325-338, 1966.
[13] P. Howland, M. Jeon, and H. Park, Cluster Structure Preserving Dimension Reduction Based on the Generalized Singular Value Decomposition SIAM J. Matrix Analysis and Applications, vol. 25, no. 1, pp. 165-179, 2003.
[14] P. Howland and H. Park, Generalizing Discriminant Analysis Using the Generalized Singular Value Decomposition IEEE Trans. Pattern Analysis and Machine Intelligence, pending publication.
[15] P. Howland and H. Park, Equivalence of Several Two-Stage Methods for Linear Discriminant Analysis Proc. Fourth SIAM Int'l Conf. Data Mining, pending publication.
[16] A.K. Jain and R.C. Dubes, Algorithms for Clustering Data. Prentice Hall, 1988.
[17] G. Kowalski, Information Retrieval System: Theory and Implementation. Kluwer Academic Publishers, 1997.
[18] W.J. Krzanowski, P. Jonathan, W.V. McCarthy, and M.R. Thomas, Discriminant Analysis with Singular Covariance Matrices: Methods and Applications to Spectroscopic Data Applied Statistics, vol. 44, pp. 101-115, 1995.
[19] D.D. Lewis, Reuters-21578 Text Categorization Test Collection Distribution 1.0 http://www.research.att.comlewis, 1999.
[20] A. Mehay, C. Cai, and P.B. Harrington, Regularized Linear Discriminant Analysis of Wavelet Compressed Ion Mobility Spectra Applied Spectroscopy, vol. 15, no. 2, pp. 219-227, 2002.
[21] C.C. Paige and M.A. Saunders, Towards a Generalized Singular Value Decomposition SIAM J. Numerical Analysis, vol. 18, pp. 398-405, 1981.
[22] M.F. Porter, An Algorithm for Suffix Stripping Program Program, vol. 14, no. 3, pp. 130-137, 1980.
[23] S. Raudys and R.P.W. Duin, On Expected Classification Error of the Fisher Linear Classifier with Pseudo-Inverse Covariance Matrix Pattern Recognition Letters, vol. 19, nos. 5-6, pp. 385-392, 1998.
[24] G. Salton, Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer. Addison-Wesley, 1989.
[25] G. Salton and M.J. McGill, Introduction to Modern Information Retrieval. McGraw-Hill, 1983.
[26] M. Skurichina and R.P.W. Duin, Stabilizing Classifiers for very Small Sample Size Proc. Int'l Conf. Pattern Recognition, pp. 891-896, 1996.
[27] M. Skurichina and R.P.W. Duin, Regularization of Linear Classifiers by Adding Redundant Features Pattern Analysis and Applications, vol. 2, no. 1, pp. 44-52, 1999.
[28] D.L. Swets and J. Weng, Using Discriminant Eigenfeatures for Image Retrieval IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 16, no. 8, pp. 831-836, Aug. 1996.
[29] Q. Tian, M. Barbero, Z.H. Gu, and S.H. Lee, Image Classification by the Foley-Sammon Transform Optical Eng., vol. 25, no. 7, pp. 834-840, 1986.
[30] TREC Proc. Text Retrieval Conf., http:/trec.nist.gov, 1999.
[31] C.F. VanLoan, Generalizing the Singular Value Decomposition SIAM J. Numerical Analysis, vol. 13, no. 1, pp. 76-83, 1976.
[32] Y. Zhao and G. Karypis, Criterion Functions for Document: Experiments and Analysis Technical Report TR01-040. Dept. of Computer Science and Eng., Univ. of Minnesota, Minneapolis-St. Paul, 2001.
[33] X. S. Zhou and T.S. Huang, "Small Sample Learning during Multimedia Retrieval Using BiasMap," Proc. IEEE Conf. Computer Vision and Pattern Recognition, vol. 1, Dec. 2001, pp. 11-17.
Index Terms:
Classification, clustering, dimension reduction, generalized singular value decomposition, linear discriminant analysis, text mining.
Citation:
Jieping Ye, Ravi Janardan, Cheong Hee Park, Haesun Park, "An Optimization Criterion for Generalized Discriminant Analysis on Undersampled Problems," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 8, pp. 982-994, Aug. 2004, doi:10.1109/TPAMI.2004.37
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb