Probabilistic frequent itemset mining in uncertain databases

ABSTRACT

Probabilistic frequent itemset mining in uncertain transaction databases semantically and computationally differs from traditional techniques applied to standard "certain" transaction databases. The consideration of existential uncertainty of item(sets), indicating the probability that an item(set) occurs in a transaction, makes traditional techniques inapplicable. In this paper, we introduce new probabilistic formulations of frequent itemsets based on possible world semantics. In this probabilistic context, an itemset X is called frequent if the probability that X occurs in at least minSup transactions is above a given threshold τ. To the best of our knowledge, this is the first approach addressing this problem under possible worlds semantics. In consideration of the probabilistic formulations, we present a framework which is able to solve the Probabilistic Frequent Itemset Mining (PFIM) problem efficiently. An extensive experimental evaluation investigates the impact of our proposed techniques and shows that our approach is orders of magnitude faster than straight-forward approaches.

REFERENCES

• 1: Parag Agrawal , Omar Benjelloun , Anish Das Sarma , Chris Hayworth , Shubha Nabar , Tomoe Sugihara , Jennifer Widom, Trio: a system for data, uncertainty, and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 2: R. Agrawal and R. Srikant. Fast algorithms for mining association rules. In Proc. ACM SIGMOD Int. Conf. on Management of Data (SIGMOD'94), Minneapolis, MN, 1994.
• 3: Lyublena Antova , Thomas Jansen , Christoph Koch , Dan Olteanu, Fast and Simple Relational Processing of Uncertain Data, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.983-992, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497507]
• 4: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 5: Chun Kit Chui and Ben Kao. A decremental approach for mining frequent itemsets from uncertain data. In The 12th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), pages 64--75, 2008.
• 6: Chun Kit Chui, Ben Kao, and Edward Hung. Mining frequent itemsets from uncertain data. In 11th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2007, Nanjing, China, pages 47--58, 2007.
• 7: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.4, p.523-544, October 2007 [doi>10.1007/s00778-006-0004-3]
• 8: Karolien Geurts, Geert Wets, Tom Brijs, and Koen Vanhoof. Profiling high frequency accident locations using association rules. In Proceedings of the 82nd Annual Transportation Research Board, Washington DC. (USA), January 12-16, page 18pp, 2003.
• 9: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, ACM SIGMOD Record, v.29 n.2, p.1-12, June 2000
• 10: H.-P. Kriegel, P. Kunath, M. Pfeifle, and M. Renz. "Probabilistic Similarity Join on Uncertain Data". In Proc. 11th Int. Conf. on Database Systems for Advanced Applications, Singapore, pp. 295--309, 2006.
• 11: Carson Kai-Sang Leung , Christopher L. Carmichael , Boyu Hao, Efficient Mining of Frequent Patterns from Uncertain Data, Proceedings of the Seventh IEEE International Conference on Data Mining Workshops, p.489-494, October 28-31, 2007 [doi>10.1109/ICDMW.2007.38]
• 12: C. Re, N. Dalvi, and D. Suciu. "Efficient top-k query evaluation on probalistic databases". In Proc. 23rd Int. Conf. on Data Engineering, Istanbul, Turkey, 2007.
• 13: P. Sen and A. Deshpande. "Representing and querying correlated tuples in probabilistic databases". In Proc. 23rd Int. Conf. on Data Engineering, Istanbul, Turkey, 2007.
• 14: M.A. Soliman, I.F. Ilyas, and K. Chen-Chuan Chang. "Top-k Query Processing in Uncertain Databases". In Proc. 23rd Int. Conf. on Data Engineering, Istanbul, Turkey, pages 896--905, 2007.
• 15: Florian Verhein , Sanjay Chawla, Geometrically Inspired Itemset Mining, Proceedings of the Sixth International Conference on Data Mining, p.655-666, December 18-22, 2006 [doi>10.1109/ICDM.2006.75]
• 16: Yi Xia , Yirong Yang , Yun Chi, Mining association rules with non-uniform privacy concerns, 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.1008699]
• 17: Ke Yi , Feifei Li , George Kollios , Divesh Srivastava, Efficient Processing of Top-k Queries in Uncertain Databases, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1406-1408, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497571]
• 18: 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
          Subjects: Data mining

General Terms:
Algorithms, Theory

Keywords:
frequent itemset mining, probabilistic data, probabilistic frequent itemsets, uncertain databases