Text Categorization using Feature Projections

Text Categorization using Feature Projections Youngjoong Ko Department of Computer Science, Sogang University 1 Sinsu-dong, Mapo-gu Seoul, 121-742, Korea kyj@nlpzodiac.sogang.ac.kr, Jungyun Seo Department of Computer Science, Sogang University 1 Sinsu-dong, Mapo-gu Seoul, 121-742, Korea seojy@ccs.sogang.ac.kr Abstract This paper proposes a new approach for text categorization, based on a feature projection technique. In our approach, training data are represented as the projections of training documents on each feature. The voting for a classification is processed on the basis of individual feature projections. The final classification of test documents determined by a majority voting from theis individual classifications of each feature. Our empirical results show that the proposed approach, Text Categorization using Feature Projections (TCFP), outperforms k-NN, Rocchio, and Naïve Bayes. Most of all, TCFP is about one hundred times faster than k-NN. Since TCFP algorithm is very simple, its implementation and training process can be done very easily. For these reasons, TCFP can be a useful classifier in the areas, which need a fast and high-performance text categorization task. Introduction An issue of text categorization is to classify documents into a certain number of pre-defined categories. Text categorization is an active research area in information retrieval and machine learning. A wide range of supervised learning algorithms has been applied to this issue, using a training data set of categorized documents. The Naïve Bayes (McCalum et al., 1998; Ko et al., 2000), Nearest Neighbor (Yang et al., 2002), and Rocchio (Lewis et al., 1996) are well-known algorithms. Among these learning algorithms, we focus on the Nearest Neighbor algorithm. In particular, the k-Nearest Neighbor (k-NN) classifier in text categorization is one of the state-of-the-art methods including Support Vector Machine (SVM) and Boosting algorithms. Since the Nearest Neighbor algorithm is much simpler than the other algorithms, the k-NN classifier is intuitive and easy to understand, and it learns quickly. But the weak point of k-NN is too slow at running time. The main computation is the on-line scoring of all training documents, in order to find the k nearest neighbors of a test document. In order to reduce the scaling problem in on-line ranking, a number of techniques have been studied in the literature. Techniques such as instance pruning technique (Wilson et al., 2000) and projection (Akkus et al., 1996) are well known. The instance pruning technique is one of the most straightforward ways to speed classification in a nearest neighbor system. It reduces time necessary and storage requirements by removing instances from the training set. A large number of such reduction techniques have been proposed, including the Condensed Nearest Neighbor Rule (Hart, 1968), IB2 and IB3 (Aha et al., 1991), and the Typical Instance Based Learning (Zhang, 1992). These and other reduction techniques were surveyed in depth in (Wilson et al., 1999), along with several new reduction techniques called DROP1-DROP5. Of these, DROP4 had the best performance. Another trial to overcome this problem exists on feature projections. Akkus and Guvenir presented a new approach to classification based on feature projections (Akkus et al., …

Content truncated to 500 words