A class-feature-centroid classifier for text categorization

ABSTRACT

Automated text categorization is an important technique for many web applications, such as document indexing, document filtering, and cataloging web resources. Many different approaches have been proposed for the automated text categorization problem. Among them, centroid-based approaches have the advantages of short training time and testing time due to its computational efficiency. As a result, centroid-based classifiers have been widely used in many web applications. However, the accuracy of centroid-based classifiers is inferior to SVM, mainly because centroids found during construction are far from perfect locations.

We design a fast Class-Feature-Centroid (CFC) classifier for multi-class, single-label text categorization. In CFC, a centroid is built from two important class distributions: inter-class term index and inner-class term index. CFC proposes a novel combination of these indices and employs a denormalized cosine measure to calculate the similarity score between a text vector and a centroid. Experiments on the Reuters-21578 corpus and 20-newsgroup email collection show that CFC consistently outperforms the state-of-the-art SVM classifiers on both micro-F1 and macro-F1 scores. Particularly, CFC is more effective and robust than SVM when data is sparse.

REFERENCES

• 1: Mohammed Benkhalifa , Abdelhak Mouradi , Houssaine Bouyakhf, Integrating External Knowledge to Supplement Training Data in Semi-Supervised Learning for Text Categorization, Information Retrieval, v.4 n.2, p.91-113, July 2001 [doi>10.1023/A:1011458711300]
• 2: Andrei Z. Broder , Marcus Fontoura , Evgeniy Gabrilovich , Amruta Joshi , Vanja Josifovski , Tong Zhang, Robust classification of rare queries using web knowledge, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277783]
• 3: Z. Cataltepe and E. Aygun. An improvement of centroid-based classification algorithm for text classification. IEEE 23rd International Conference on Data Engineering Workshop, 1-2:952--956, 2007.
• 4: R. N. Chau, C. S. Yeh, and K. A. Smith. A neural network model for hierarchical multilingual text categorization. Advances in Neural Networks, LNCS, 3497:238--245, 2005.
• 5: Susan Dumais , Hao Chen, Hierarchical classification of Web content, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.256-263, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345593]
• 6: Paolo Frasconi , Giovanni Soda , Alessandro Vullo, Text categorization for multi-page documents: a hybrid naive Bayes HMM approach, Proceedings of the 1st ACM/IEEE-CS joint conference on Digital libraries, p.11-20, January 2001, Roanoke, Virginia, United States [doi>10.1145/379437.379440]
• 7: Sheng Gao , Wen Wu , Chin-Hui Lee , Tat-Seng Chua, A maximal figure-of-merit (MFoM)-learning approach to robust classifier design for text categorization, ACM Transactions on Information Systems (TOIS), v.24 n.2, p.190-218, April 2006 [doi>10.1145/1148020.1148022]
• 8: G. D. Guo, H. Wang, D. Bell, Y. X. Bi, and K. Greer. Using kNN model for automatic text categorization. Soft Computing, 10(5):423--430, 2006.
• 9: Bong Chih How , K. Narayanan, An Empirical Study of Feature Selection for Text Categorization based on Term Weightage, Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence, p.599-602, September 20-24, 2004 [doi>10.1109/WI.2004.24]
• 10: A. M. Kibriya, E. Frank, B. Pfahringer, and G. Holmes. Multinomial naive bayes for text categorization revisited. AI 2004: Advances in Artificial Intelligence, 3339:488--499, 2004.
• 11: Hyunsoo Kim , Peg Howland , Haesun Park, Dimension Reduction in Text Classification with Support Vector Machines, The Journal of Machine Learning Research, 6, p.37-53, 12/1/2005
• 12: Ralf Klinkenberg , Thorsten Joachims, Detecting Concept Drift with Support Vector Machines, Proceedings of the Seventeenth International Conference on Machine Learning, p.487-494, June 29-July 02, 2000
• 13: Changki Lee , Gary Geunbae Lee, Information gain and divergence-based feature selection for machine learning-based text categorization, Information Processing and Management: an International Journal, v.42 n.1, p.155-165, January 2006 [doi>10.1016/j.ipm.2004.08.006]
• 14: Verayuth Lertnattee , Thanaruk Theeramunkong, Combining Homogeneous Classifiers for Centroid-based Text Classification, Proceedings of the Seventh International Symposium on Computers and Communications (ISCC'02), p.1034, July 01-04, 2002
• 15: Verayuth Lertnattee , Thanaruk Theeramunkong, Effect of term distributions on centroid-based text categorization, Information Sciences—Informatics and Computer Science: An International Journal, v.158 n.1, p.89-115, January 2004 [doi>10.1016/j.ins.2003.07.007]
• 16: V. Lertnattee and T. Theeramunkong. Class normalization in centroid-based text categorization. Information Sciences, 176(12):1712--1738, 2006.
• 17: D. Lewis and J. Catlett. Heterogeneous uncertainty sampling for supervised learning. In Proceedings of the Eleventh International Conference on Machine Learning, pages 148--156, 1994.
• 18: Yan Liu , Yiming Yang , Jaime Carbonell, Boosting to correct inductive bias in text classification, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584850]
• 19: Sven Martin , Jörg Liermann , Hermann Ney, Algorithms for bigram and trigram word clustering, Speech Communication, v.24 n.1, p.19-37, April 1, 1998 [doi>10.1016/S0167-6393(97)00062-9]
• 20: A. K. McCallum. Mallet: A machine learning for language toolkit. http://mallet.cs.umass.edu, 2002.
• 21: Elena Montanes , Irene Diaz , Jose Ranilla , Elias F. Combarro , Javier Fernandez, Scoring and Selecting Terms for Text Categorization, IEEE Intelligent Systems, v.20 n.3, p.40-47, May 2005 [doi>10.1109/MIS.2005.49]
• 22: Xiaochuan Ni , Gui-Rong Xue , Xiao Ling , Yong Yu , Qiang Yang, Exploring in the weblog space by detecting informative and affective articles, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242611]
• 23: Z. L. Pei, X. H. Shi, M. Marchese, and Y. C. Liang. An enhanced text categorization method based on improved text frequency approach and mutual information algorithm. Progress in Natural Science, 17(12):1494--1500, 2007.
• 24: Paul Resnick , Neophytos Iacovou , Mitesh Suchak , Peter Bergstrom , John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.175-186, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.192905]
• 25: S. Robertson. Understanding inverse document frequency: on theoretical arguments for IDF. Journal of Documentation, 60:503--520, 2004.
• 26: Robert E. Schapire , Yoram Singer , Amit Singhal, Boosting and Rocchio applied to text filtering, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.215-223, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290996]
• 27: K. M. Schneider. Weighted average pointwise mutual information for feature selection in text categorization. Knowledge Discovery in Databases: PKDD 2005, 3721:252--263, 2005.
• 28: Fabrizio Sebastiani, Machine learning in automated text categorization, ACM Computing Surveys (CSUR), v.34 n.1, p.1-47, March 2002 [doi>10.1145/505282.505283]
• 29: S. Shankar and G. Karypis. Weight Adjustment Schemes for a Centroid Based Classifier. Army High Performance Computing Research Center, 2000.
• 30: P. Soucy and G. W. Mineau. Feature selection strategies for text categorization. Advances in Artificial Intelligence, Proceedings, 2671:505--509, 2003.
• 31: Ardi Santoso, A Comparative Study of Centroid-Based, Neighborhood-Based and Statistical Approaches for Effective Document Categorization, Proceedings of the 16 th International Conference on Pattern Recognition (ICPR'02) Volume 4, p.40235, August 11-15, 2002
• 32: Songbo Tan, Large margin DragPushing strategy for centroid text categorization, Expert Systems with Applications: An International Journal, v.33 n.1, p.215-220, July, 2007 [doi>10.1016/j.eswa.2006.04.008]
• 33: Songbo Tan , Xueqi Cheng, Using hypothesis margin to boost centroid text classifier, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244096]
• 34: Songbo Tan, An improved centroid classifier for text categorization, Expert Systems with Applications: An International Journal, v.35 n.1-2, p.279-285, July, 2008 [doi>10.1016/j.eswa.2007.06.028]
• 35: Sholom M. Weiss , Chidanand Apte , Fred J. Damerau , David E. Johnson , Frank J. Oles , Thilo Goetz , Thomas Hampp, Maximizing Text-Mining Performance, IEEE Intelligent Systems, v.14 n.4, p.63-69, July 1999 [doi>10.1109/5254.784086]
• 36: Haoran Wu , Tong Heng Phang , Bing Liu , Xiaoli Li, A refinement approach to handling model misfit in text categorization, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775078]
• 37: Jinxi Xu , W. Bruce Croft, Corpus-based stemming using cooccurrence of word variants, ACM Transactions on Information Systems (TOIS), v.16 n.1, p.61-81, Jan. 1998 [doi>10.1145/267954.267957]
• 38: Gui-Rong Xue , Dikan Xing , Qiang Yang , Yong Yu, Deep classification in large-scale text hierarchies, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390440]
• 39: 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.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

General Terms:
Algorithms, Experimentation, Performance

Keywords:
centroid, denormalized cosine measure, inner-class, inter-class, text classification