School of Computer Science and Technology, Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian, Liaoning, China 116024 and School of Innovation and Experiment, Dalian University of Technology, Liaoning, China 116024.

---

Abstract—Frequent itemset/pattern mining (FIM) over uncertain transaction dataset is a fundamental task in data mining. In this paper, we study the problem of FIM over uncertain datasets. There are two main approaches for FIM: the level-wise approach and the pattern-growth approach. The level-wise approach requires multiple scans of dataset and generates candidate itemsets. The pattern-growth approach requires a large amount of memory and computation time to process tree nodes because the current algorithms for uncertain datasets cannot create a tree as compact as the original FP-Tree. In this paper, we propose an array based tail node tree structure (namely AT-Tree) to maintain transaction itemsets, and a pattern-growth based algorithm named AT-Mine for FIM over uncertain dataset. AT-Tree is created by two scans of dataset and it is as compact as the original FP-Tree. AT-Mine mines frequent itemsets from AT-Tree without additional scan of dataset. We evaluate our algorithm using sparse and dense datasets; the experimental results show that our algorithm has achieved better performance than the state-of-the-art FIM algorithms on uncertain transaction datasets, especially for small minimum expected support number.

Index Terms—data mining, frequent itemset, frequent pattern, uncertain dataset

[PDF]

Cite: Le Wang, Lin Feng, and Mingfei Wu, " AT-Mine: An Efficient Algorithm of Frequent Itemset Mining on Uncertain Dataset," Journal of Computers vol. 8, no. 6, pp. 1417-1426, 2013.