OCFS: optimal orthogonal centroid feature selection for text categorization

ABSTRACT

Text categorization is an important research area in many Information Retrieval (IR) applications. To save the storage space and computation time in text categorization, efficient and effective algorithms for reducing the data before analysis are highly desired. Traditional techniques for this purpose can generally be classified into feature extraction and feature selection. Because of efficiency, the latter is more suitable for text data such as web documents. However, many popular feature selection techniques such as Information Gain (IG) andχ²-test (CHI) are all greedy in nature and thus may not be optimal according to some criterion. Moreover, the performance of these greedy methods may be deteriorated when the reserved data dimension is extremely low. In this paper, we propose an efficient optimal feature selection algorithm by optimizing the objective function of Orthogonal Centroid (OC) subspace learning algorithm in a discrete solution space, called Orthogonal Centroid Feature Selection (OCFS). Experiments on 20 Newsgroups (20NG), Reuters Corpus Volume 1 (RCV1) and Open Directory Project (ODP) data show that OCFS is consistently better than IG and CHI with smaller computation time especially when the reduced dimension is extremely small.

REFERENCES

• 1: Nicholas J. Belkin , W. Bruce Croft, Retrieval techniques, Annual review of information science and technology, vol. 22, Elsevier Science Inc., New York, NY, 1987
• 2: Douglas Hardin , Ioannis Tsamardinos , Constantin F. Aliferis, A theoretical characterization of linear SVM-based feature selection, Proceedings of the twenty-first international conference on Machine learning, p.48, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015421]
• 3: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 4: Franca Debole , Fabrizio Sebastiani, Supervised term weighting for automated text categorization, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952688]
• 5: Greengrass, E. Information Retrieval: A Survey, 30 November 2000.
• 6: Howland, P. and Park, H. Generalizing discriminant analysis using the generalized singular value decomposition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26 (8). 995--1006.
• 7: James E. Gentle, J. Chambers, W. Eddy, W. Haerdle, S. Sheather and Tierney, L. Numerical Linear Algebra for Applications in Statistics. Springer-Verlag, Berlin, 1998.
• 8: Jolliffe, I.T. Principal Component Analysis. New York: Spriger Verlag, 1986.
• 9: Lang, K. and NewsWeeder, Learning to Filter Netnews. In Proceedings of the 12th International Conference on Machine Learning (ICML 95), (Morgan Kaufmann, 1995).
• 10: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 11: David D. Lewis, Feature selection and feature extraction for text categorization, Proceedings of the workshop on Speech and Natural Language, February 23-26, 1992, Harriman, New York [doi>10.3115/1075527.1075574]
• 12: Li, H., Jiang, T., and Zhang, K., Efficient and Robust Feature Extraction by Maximum Margin Criterion. In Proceedings of the Advances in Neural Information Processing Systems, (Vancouver, Canada, 2003), 97--104.
• 13: Huan Liu , Hiroshi Motoda, Feature Extraction, Construction and Selection: A Data Mining Perspective, Kluwer Academic Publishers, Norwell, MA, 1998
• 14: Jeon M., Park, H. and Rosen, J.B. Dimension Reduction Based on Centroids and Least Squares for Efficient Processing of Text Data, Minneapolis, MN, University of Minnesota.
• 15: Malhi, A. and Gao, R.X. PCA-Based Feature Selection Scheme for Machine Defect Classification. IEEE Transactions on Instrumentation and Measurement, 53. 1517--1525.
• 16: Aleix M. Martínez , Avinash C. Kak, PCA versus LDA, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.2, p.228-233, February 2001 [doi>10.1109/34.908974]
• 17: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 18: John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 19: Ran Gilad-Bachrach , Amir Navot , Naftali Tishby, Margin based feature selection - theory and algorithms, Proceedings of the twenty-first international conference on Machine learning, p.43, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015352]
• 20: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 21: Roweis, S.T. and Saul, L.K. Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 2000 Dec 22; 290(5500):2323-6.
• 22: Tenenbaum J.B., Silva, V.d. and Langford, J.C. A global geometric framework for nonlinear dimensionality reduction. Science, 290. 2319--2323.
• 23: Gang Wang , Frederick H. Lochovsky, Feature selection with conditional mutual information maximin in text categorization, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031241]
• 24: Jun Yan , Benyu Zhang , Shuicheng Yan , Qiang Yang , Hua Li , Zheng Chen , Wensi Xi , Weiguo Fan , Wei-Ying Ma , Qiansheng Cheng, IMMC: incremental maximum margin criterion, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014147]
• 25: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

General Terms:
Algorithms, Performance

Keywords:
feature extraction (FE), feature selection (FS)