Frequent pattern mining with uncertain data

ABSTRACT

This paper studies the problem of frequent pattern mining with uncertain data. We will show how broad classes of algorithms can be extended to the uncertain data setting. In particular, we will study candidate generate-and-test algorithms, hyper-structure algorithms and pattern growth based algorithms. One of our insightful observations is that the experimental behavior of different classes of algorithms is very different in the uncertain case as compared to the deterministic case. In particular, the hyper-structure and the candidate generate-and-test algorithms perform much better than tree-based algorithms. This counter-intuitive behavior is an important observation from the perspective of algorithm design of the uncertain variation of the problem. We will test the approach on a number of real and synthetic data sets, and show the effectiveness of two of our approaches over competitive techniques.

REFERENCES

• 1: Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, A tree projection algorithm for generation of frequent item sets, Journal of Parallel and Distributed Computing, v.61 n.3, p.350-371, March 1, 2001 [doi>10.1006/jpdc.2000.1693]
• 2: Charu C. Aggarwal, Managing and Mining Uncertain Data, Springer Publishing Company, Incorporated, 2009
• 3: 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
• 4: 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
• 5: F. Bodon. A fast APRIORI implementation. URL: {http://fimi.cs.helsinki.fi/src/}.
• 6: Doug Burdick , Manuel Calimlim , Jason Flannick , Johannes Gehrke , Tomi Yiu, MAFIA: A Maximal Frequent Itemset Algorithm, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1490-1504, November 2005 [doi>10.1109/TKDE.2005.183]
• 7: C.-K. Chui, B. Kao, E. Hung. Mining Frequent Itemsets from Uncertain Data. PAKDD 2007.
• 8: C.-K. Chui, B. Kao. Decremental Approach for Mining Frequent Itemsets from Uncertain Data. PAKDD 2008.
• 9: 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
• 10: Sudipto Guha , Nick Koudas , Kyuseok Shim, Approximation and streaming algorithms for histogram construction problems, ACM Transactions on Database Systems (TODS), v.31 n.1, p.396-438, March 2006 [doi>10.1145/1132863.1132873]
• 11: C. K.-S. Leung, M. A. F. Mateo, D. A. Brajczuk. A Tree-Based Approach for Frequent Pattern Mining from UncertainData, PAKDD 2008.
• 12: Jian Pei , Jiawei Han , Hongjun Lu , Shojiro Nishio , Shiwei Tang , Dongqing Yang, H-Mine: Hyper-Structure Mining of Frequent Patterns in Large Databases, Proceedings of the 2001 IEEE International Conference on Data Mining, p.441-448, November 29-December 02, 2001
• 13: Y.G. Sucahyo, R.P. Gopalan. CT-PRO: A Bottom-up Non-Recursive Frequent Itemset Mining Algorithm Using Compressed FP-Tree DataStructure. URL: {http://fimi.cs.helsinki.fi/src/}.
• 14: Qin Zhang , Feifei Li , Ke Yi, Finding frequent items in probabilistic data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376698]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
uncertain data