Mining Expected Support-Based Frequent Itemsets by Sampling

Discovering Frequent itemsets over uncertain databases has become a hot topic in data mining community due to the wide application of uncertain data. Several algorithms are proposed to mine frequent itemsets over uncertain data. However, the existing mining algorithms generally suffer from extensive computation and prohibitively running time when the uncertain data is large or the frequent threshold is low. To address this issue, we propose a novel expected support-based frequent itemsets (E-FIs) mining method which discovers approximate E-FIs from a random sample of the original uncertain dataset. To obtain high quality approximation, we employ the solid theory of the Vapnik-Chervonenkis dimension. The mining result is thus a superset of the E-FIs with high probability guarantee. Finally, we conduct experiments on two public databases and evaluate our method in terms of accuracy, running time and scalability.

I. Introduction

In many recent emerging applications, the underlying databases usually contain imprecise or uncertain data, such as the ones related to RFID, GPS or wireless sensor network. Mining uncertain data has thus become a very important topic in data mining research field. Frequent itemsets mining is of great interest among all the tasks of uncertain data mining and has attracted much attention [1]. It is extended from the problem of frequent itemsets over exact database.