Associative text categorization exploiting negated words

ABSTRACT

Associative classification has been recently applied to text document categorization. However, differently from classification of structured data, the quality of the generated classifier is rather low. This effect is mainly due to the poor precision of generated rules.To increase the precision of associative classifiers we propose the use of classification rules including negated words, i.e. words that the considered document should not contain. Rules are in the form "If a document includes words A and B, but not word Z, then it belongs to class C1". Mining classification rules with negated words becomes quickly intractable when decreasing the support threshold. We tackle this problem by means of an opportunistic approach, where negated words are only generated to specialize rules that may wrongly classify training documents. Hence precision is increased, without losing recall.Experiments on the Reuters corpus show that our classifier based on negated words achieves good precision and recall results, while yielding an easily interpretable model typical of associative classifiers.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Maria-Luiza Antonie , Osmar R. Zaïane, Text Document Categorization by Term Association, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.19, December 09-12, 2002
• 3: Maria-Luiza Antonie , Osmar R. Zaïane, An associative classifier based on positive and negative rules, Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13, 2004, Paris, France [doi>10.1145/1008694.1008705]
• 4: Elena Baralis , Paolo Garza, A Lazy Approach to Pruning Classification Rules, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.35, December 09-12, 2002
• 5: Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States
• 6: William W. Cohen , Yoram Singer, Context-sensitive learning methods for text categorization, ACM Transactions on Information Systems (TOIS), v.17 n.2, p.141-173, April 1999 [doi>10.1145/306686.306688]
• 7: B. Goethals and M. J. Zaki. FIMI'03: Workshop on frequent itemset mining implementations. In FIMI'03, 2003.
• 8: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 9: S. Hettich and S. D. Bay. The reuters-21578 text collection. The UCI KDD Archive.
• 10: Thorsten Joachims, Text Categorization with Suport Vector Machines: Learning with Many Relevant Features, Proceedings of the 10th European Conference on Machine Learning, p.137-142, April 21-23, 1998
• 11: David D. Lewis, Naive (Bayes) at Forty: The Independence Assumption in Information Retrieval, Proceedings of the 10th European Conference on Machine Learning, p.4-15, April 21-23, 1998
• 12: Wenmin Li , Jiawei Han , Jian Pei, CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules, Proceedings of the 2001 IEEE International Conference on Data Mining, p.369-376, November 29-December 02, 2001
• 13: B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. In KDD'98, NY, 1998.
• 14: Bing Liu , Yiming Ma , Ching Kian Wong, Improving an Association Rule Based Classifier, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.504-509, September 13-16, 2000
• 15: Rosa Meo, Theory of dependence values, ACM Transactions on Database Systems (TODS), v.25 n.3, p.380-406, Sept. 2000 [doi>10.1145/363951.363956]
• 16: J. Quinlan. C4.5: program for classification learning. Morgan Kaufmann, 1992.
• 17: J. Rocchio. Relevance feedback in information retrieval. Prentice-Hall, 1971.
• 18: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, Mining for Strong Negative Associations in a Large Database of Customer Transactions, Proceedings of the Fourteenth International Conference on Data Engineering, p.494-502, February 23-27, 1998
• 19: 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]
• 20: Ke Wang , Senqiang Zhou , Yu He, Growing decision trees on support-less association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.265-269, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347147]
• 21: Yiming Yang, Expert network: effective and efficient learning from human decisions in text categorization and retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.13-22, July 03-06, 1994, Dublin, Ireland

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Keywords:
association rules, text classification