Tightening Upper Bounds to the Expected Support for Uncertain Frequent Pattern Mining

Due to advances in technology, high volumes of valuable data can be collected and transmitted at high velocity in various scientific and engineering applications. Consequently, efficient data mining algorithms are in demand for analyzing these data. For instance, frequent pattern mining discovers implicit, previously unknown, and potentially useful knowledge about relationships among frequently co-occurring items, objects and/or events. While many frequent pattern mining algorithms handle precise data, there are situations in which data are uncertain. In recent years, tree-based algorithms for mining uncertain data have been developed. However, tree structures corresponding to these algorithms can be large. Other tree structures for handling uncertain data may achieve compactness at the expense of loose upper bounds on expected supports. In this paper, we propose (i) a compact tree structure for capturing uncertain data, (ii) a technique for using our tree structure to tighten upper bounds to expected support, and (iii) an algorithm for mining frequent patterns based on our tightened bounds. Experimental results show the benefits of our tightened upper bounds to expected supports in uncertain frequent pattern mining.