Generating semantic annotations for frequent patterns with context analysis

ABSTRACT

As a fundamental data mining task, frequent pattern mining has widespread applications in many different domains. Research in frequent pattern mining has so far mostly focused on developing efficient algorithms to discover various kinds of frequent patterns, but little attention has been paid to the important nextstep - interpreting the discovered frequent patterns. Although some recent work has studied the compression and summarization of frequent patterns, the proposed techniques can only annotate a frequent pattern with non-semantical information (e.g. support), which provides only limited help for a user to understand the patterns.In this paper, we propose the novel problem of generating semantic annotations for frequent patterns. The goal is to annotate a frequent pattern with in-depth, concise, and structured information that can better indicate the hidden meanings of the pattern. We propose a general approach to generate such anannotation for a frequent pattern by constructing its context model, selecting informative context indicators, and extracting representative transactions and semantically similar patterns. This general approach has potentially many applications such as generating a dictionary-like description for a pattern, finding synonym patterns, discovering semantic relations, and summarizing semantic classes of a set of frequent patterns. Experiments on different datasets show that our approach is effective in generating semantic pattern annotations.

REFERENCES

• 1: Foto Afrati , Aristides Gionis , Heikki Mannila, Approximating a collection of frequent sets, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014057]
• 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: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 4: 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
• 5: S. C. Deerwester, S. T. Dumais, T. K. Landauer,G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the American Society of Information Science, 41(6):391--407, 1990.
• 6: Mukund Deshpande , Michihiro Kuramochi , George Karypis, Frequent Sub-Structure-Based Approaches for Classifying Chemical Compounds, Proceedings of the Third IEEE International Conference on Data Mining, p.35, November 19-22, 2003
• 7: G. Grahne and J. Zhu. Efficiently using prefix-trees in mining frequent itemsets. In FIMI'03 Workshop on Frequent Itemset Mining Implementations., 2003.
• 8: Jiawei Han , Jian Pei , Yiwen Yin , Runying Mao, Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach, Data Mining and Knowledge Discovery, v.8 n.1, p.53-87, January 2004 [doi>10.1023/B:DAMI.0000005258.31418.83]
• 9: Jiawei Han , Jianyong Wang , Ying Lu , Petre Tzvetkov, Mining Top.K Frequent Closed Patterns without Minimum Support, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.211, December 09-12, 2002
• 10: P. Jaccard. Nouvelles recherches sur la distribution florale. Bull. Soc. Vaudoise Sci. Nat., 44:223C--270, 1908.
• 11: Paul B. Kantor , Ellen M. Voorhees, The TREC-5 Confusion Track: Comparing Retrieval Methods for Scanned Text, Information Retrieval, v.2 n.2-3, p.165-176, May 2000 [doi>10.1023/A:1009902609570]
• 12: Robert Krovetz, Viewing morphology as an inference process, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.191-202, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160718]
• 13: Dekang Lin , Patrick Pantel, Induction of semantic classes from natural language text, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.317-322, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502558]
• 14: X. Ling, J. Jiang, X. He, Q. Mei, C. Zhai, and B. Schatz. Automatically generating gene summaries from biomedical literature. In Proceedings of Pacific Symposium on Biocomputing, pages 40--51, 2006.
• 15: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceeding of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
• 16: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 17: G. Salton , A. Wong , C. S. Yang, A vector space model for automatic indexing, Communications of the ACM, v.18 n.11, p.613-620, Nov. 1975 [doi>10.1145/361219.361220]
• 18: T. Tao, C. Zhai, X. Lu, and H. Fang. A study of statistical methods for function prediction of protein motifs. Applied Bioinformatics, 3(2-3):115--124, 2004.
• 19: Ke Wang , Chu Xu , Bing Liu, Clustering transactions using large items, Proceedings of the eighth international conference on Information and knowledge management, p.483-490, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.320054]
• 20: Dong Xin , Jiawei Han , Xifeng Yan , Hong Cheng, Mining compressed frequent-pattern sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 21: Xifeng Yan , Hong Cheng , Jiawei Han , Dong Xin, Summarizing itemset patterns: a profile-based approach, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081907]
• 22: 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
• 23: X. Yan, J. Han, and R. Afshar. Clospan: Mining closed sequential patterns in large datasets. In Proceedings of SDM'03, pages 166--177, 2003.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
frequent pattern, pattern annotation, pattern context, pattern semantic analysis