Frequent pattern-growth approach for document organization

ABSTRACT

In this paper, we propose a document clustering mechanism that depends on the appearance of frequent senses in the documents rather than on the co-occurrence of frequent keywords. Instead of representing each document as a collection of keywords, we use a document-graph which reflects a conceptual hierarchy of keywords related to that document. We incorporate a graph mining approach with one of the well-known association rule mining procedures, FP-growth, to discover the frequent subgraphs among the document-graphs. The similarity of the documents is measured in terms of the number of frequent subgraphs appearing in the corresponding document-graphs. We believe that our novel approach allows us to cluster the documents based more on their senses rather than the actual keywords.

REFERENCES

• 1: 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
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: 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
• 4: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 5: 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
• 6: Michihiro Kuramochi , George Karypis, An Efficient Algorithm for Discovering Frequent Subgraphs, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1038-1051, September 2004 [doi>10.1109/TKDE.2004.33]
• 7: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 8: Moti Cohen , Ehud Gudes, Diagonally Subgraphs Pattern Mining, 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.1008702]
• 9: Nikhil S. Ketkar , Lawrence B. Holder , Diane J. Cook, Subdue: compression-based frequent pattern discovery in graph data, Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations, p.71-76, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1133905.1133915]
• 10: http://www.wordnet.princeton.edu
• 11: M. Shahriar Hossain , Rafal A. Angryk, GDClust: A Graph-Based Document Clustering Technique, Proceedings of the Seventh IEEE International Conference on Data Mining Workshops, p.417-422, October 28-31, 2007 [doi>10.1109/ICDMW.2007.48]
• 12: Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 13: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 14: Kaufman, L. and Rousseeuw, P. J., "Finding Groups in Data: an Introduction to Cluster Analysis", John Wiley & Sons, (1990).
• 15: http://people.csail.mit.edu/jrennie/20Newsgroups

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.0 General

General Terms:
Algorithms

Keywords:
FP-growth, WordNet, clustering, document-graph, frequent subgraph clustering, graph mining