Efficient mining of association rules in text databases

ABSTRACT

In this paper, we propose two new algorithms for mining association rules between words in text databases. The characteristics of text databases are quite different from those of retail transaction databases, and existing mining algorithms cannot handle text databases efficiently because of the large number of itemsets (i.e., words) that need to be counted. Two well-known mining algorithms, Apriori algorithm and Direct Hashing and Pruning (DHP) algorithm, are evaluated in the context of mining text databases, and are compared with the new proposed algorithms named Multipass-Apriori (M-Apriori) and Multipass-DHP (M-DHP). It has been shown that the proposed algorithms have better performance for large text databases.

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: Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.255-264, May 11-15, 1997, Tucson, Arizona, United States
• 3: Ming-Syan Chen , Jiawei Han , Philip S. Yu, Data Mining: An Overview from a Database Perspective, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.866-883, December 1996 [doi>10.1109/69.553155 ]
• 4: Michael D. Gordon , Susan Dumais, Using latent semantic indexing for literature based discovery, Journal of the American Society for Information Science, v.49 n.8, p.674-685, June 1998 [doi>10.1002/(SICI)1097-4571(199806)49:8<674::AID-ASI2>3.0.CO;2-Q]
• 5: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, Using a Hash-Based Method with Transaction Trimming for Mining Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.9 n.5, p.813-825, September 1997 [doi>10.1109/69.634757 ]
• 6: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 7: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
• 8: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 9: E.M. Voorhee~ and D.K. Harmon (editors), The Fifth Text Retrieval Conference, National Institute of Standards and Technology, 1997.
• 10: Mohammed J Zaki , Srinivasan Parthasarathy , Mitsunori Ogihara , Wei Li, New Algorithms for Fast Discovery of Association Rules, University of Rochester, Rochester, NY, 1997

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases

General Terms:
Algorithms, Design, Documentation, Management, Measurement, Performance, Theory