Summarizing itemset patterns: a profile-based approach

ABSTRACT

Frequent-pattern mining has been studied extensively on scalable methods for mining various kinds of patterns including itemsets, sequences, and graphs. However, the bottleneck of frequent-pattern mining is not at the efficiency but at the interpretability, due to the huge number of patterns generated by the mining process.In this paper, we examine how to summarize a collection of itemset patterns using only K representatives, a small number of patterns that a user can handle easily. The K representatives should not only cover most of the frequent patterns but also approximate their supports. A generative model is built to extract and profile these representatives, under which the supports of the patterns can be easily recovered without consulting the original dataset. Based on the restoration error, we propose a quality measure function to determine the optimal value of parameter K. Polynomial time algorithms are developed together with several optimization heuristics for efficiency improvement. Empirical studies indicate that we can obtain compact summarization in real datasets.

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: L. Douglas Baker , Andrew Kachites McCallum, Distributional clustering of words for text classification, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.96-103, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290970]
• 5: 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
• 6: Toon Calders , Bart Goethals, Mining All Non-derivable Frequent Itemsets, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.74-85, August 19-23, 2002
• 7: L. Dehaspe, H. Toivonen, and R. King. Finding frequent substructures in chemical compounds. In Proc. of 1998 Int. Conf. on Knowledge Discovery and Data Mining (KDD'98), pages 30--36, 1998.
• 8: 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
• 9: Inderjit S. Dhillon , Subramanyam Mallela , Rahul Kumar, A divisive information theoretic feature clustering algorithm for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 10: Dimitrios Gunopulos , Heikki Mannila , Roni Khardon , Hannu Toivonen, Data mining, hypergraph transversals, and machine learning (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.209-216, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263684]
• 11: 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
• 12: W. Hoeffding. Probability inequalities for sums of bounded random variables. J. American Statistical Associations, 58:13--30, 1963.
• 13: L. Holder, D. Cook, and S. Djoko. Substructure discovery in the subdue system. In Proc. AAAI94 Workshop on Knowledge Discovery in Databases (KDD94), page 169--180, 1994.
• 14: Jun Huan , Wei Wang , Deepak Bandyopadhyay , Jack Snoeyink , Jan Prins , Alexander Tropsha, Mining protein family specific residue packing patterns from protein structure graphs, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.308-315, March 27-31, 2004, San Diego, California, USA [doi>10.1145/974614.974655]
• 15: Monica Hutchins , Herb Foster , Tarak Goradia , Thomas Ostrand, Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria, Proceedings of the 16th international conference on Software engineering, p.191-200, May 16-21, 1994, Sorrento, Italy
• 16: Ron Kohavi , Carla E. Brodley , Brian Frasca , Llew Mason , Zijian Zheng, KDD-Cup 2000 organizers' report: peeling the onion, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.86-93, Dec. 2000 [doi>10.1145/380995.381033]
• 17: T. Mielikainen and H. Mannila. The pattern ordering problem. In Prof. 7th European Conf. on Principles and Practice of Knowledge Discovery in Databases (PKDD'03), pages 327--338, 2003.
• 18: Edward R. Omiecinski, Alternative Interest Measures for Mining Associations in Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.1, p.57-69, January 2003 [doi>10.1109/TKDE.2003.1161582]
• 19: 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
• 20: Dmitry Pavlov , Heikki Mannila , Padhraic Smyth, Beyond Independence: Probabilistic Models for Query Approximation on Binary Transaction Data, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1409-1421, November 2003 [doi>10.1109/TKDE.2003.1245281]
• 21: Jian Pei , Guozhu Dong , Wei Zou , Jiawei Han, On Computing Condensed Frequent Pattern Bases, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.378, December 09-12, 2002
• 22: J. Pei, A. Tung, and J. Han. Fault-tolerant frequent pattern mining: Problems and challenges. In Proc. of 2001 ACM Int. Workshop Data Mining and Knowledge Discovery (DMKD'01), pages 7--12, 2001.
• 23: Michael Steinbach , Pang-Ning Tan , Vipin Kumar, Support envelopes: a technique for exploring the structure of association patterns, 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.1014086]
• 24: Pang-Ning Tan , Vipin Kumar , Jaideep Srivastava, Selecting the right interestingness measure for association patterns, 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.775053]
• 25: 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]
• 26: Xifeng Yan , Philip S. Yu , Jiawei Han, Graph indexing: a frequent structure-based approach, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007607]
• 27: Cheng Yang , Usama Fayyad , Paul S. Bradley, Efficient discovery of error-tolerant frequent itemsets in high dimensions, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.194-203, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502539]

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, probabilistic model, summarization