Scalable Term Selection for Text Categorization

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 774–782, Prague, June 2007. c⃝2007 Association for Computational Linguistics Scalable Term Selection for Text Categorization Jingyang Li National Lab of Intelligent Tech. & Sys. Department of Computer Sci. & Tech. Tsinghua University, Beijing, China lijingyang@gmail.com Maosong Sun National Lab of Intelligent Tech. & Sys. Department of Computer Sci. & Tech. Tsinghua University, Beijing, China sms@tsinghua.edu.cn Abstract In text categorization, term selection is an important step for the sake of both cate- gorization accuracy and computational ef- ficiency. Different dimensionalities are ex- pected under different practical resource re- strictions of time or space. Traditionally in text categorization, the same scoring or ranking criterion is adopted for all target dimensionalities, which considers both the discriminability and the coverage of a term, such as χ2 or IG. In this paper, the poor ac- curacy at a low dimensionality is imputed to the small average vector length of the docu- ments. Scalable term selection is proposed to optimize the term set at a given dimen- sionality according to an expected average vector length. Discriminability and cover- age are separately measured; by adjusting the ratio of their weights in a combined cri- terion, the expected average vector length can be reached, which means a good com- promise between the specificity and the ex- haustivity of the term subset. Experiments show that the accuracy is considerably im- proved at lower dimensionalities, and larger term subsets have the possibility to lower the average vector length for a lower com- putational cost. The interesting observations might inspire further investigations. 1 Introduction Text categorization is a classical text information processing task which has been studied adequately (Sebastiani, 2002). A typical text categorization pro- cess usually involves these phases: document in- dexing, dimensionality reduction, classifier learn- ing, classification and evaluation. The vector space model is frequently used for text representation (document indexing); dimensions of the learning space are called terms, or features in a general ma- chine learning context. Term selection is often nec- essary because: • Many irrelevant terms have detrimental effect on categorization accuracy due to overfitting (Sebastiani, 2002). • Some text categorization tasks have many rel- evant but redundant features, which also hurt the categorization accuracy (Gabrilovich and Markovitch, 2004). • Considerations on computational cost: (i) Many sophisticated learning machines are very slow at high dimensionalities, such as LLSF (Yang and Chute, 1994) and SVMs. (ii) In Asian languages, the term set is often very large and redundant, which causes the learning and the predicting to be really slow. (iii) In some practical cases the computational resources (time or space) are restricted, such as hand-held devices, real-time applications and frequently retrained systems. (iv) Some deeper analysis or feature reconstruction techniques rely on matrix factorization (e.g. LSA based on SVD), which might be computationally in- tractable while the dimensionality is large. Sometimes an aggressive term selection might be needed particularly for (iii) and (iv). But it is no- table …

Content truncated to 500 words