Iterative uncertain frequent pattern mining with trees

Abstract

Many frequent-pattern mining algorithms were designed to handle precise data, such as the FP-tree structure and the FP-growth algorithm. In data mining research, attention has been turned to mining frequent patterns in uncertain data recently. A common way to represent the uncertainty of a data item in transactional databases is to associate it with an existential probability. In this thesis, we propose two solutions for uncertain frequent pattern mining. One solution is a novel uncertain-frequent-pattern discovery structure, the mUF-tree, for storing summarized and uncertain information about frequent patterns. With the mUF-tree, the UF-Evolve algorithm can utilize the shuffling and merging techniques to generate iterative versions of the tree. Its main purpose is to discover new uncertain frequent patterns from these iterative versions. The other solution is the mUF-trie structure and the UF-Prune algorithm. In the mUF-trie, the uncertain information about frequent patterns is summarized in the lexicographic order, which facilitates mining uncertain frequent patterns separately for each item. With the mUF-trie, the UF-Prune algorithm can continuously generate a sub-trie for each item, utilize the shuffling and merging techniques to generate iterative versions of the sub-trie, and prune away the processed items in the mUF-trie. As in the mUF-tree, the new structure can support the discovery of new uncertain frequent patterns relating to each item from iterative versions of its sub-trie. Our preliminary performance study shows that the UF-Evolve and UF-Prune algorithms are efficient and scalable for mining additional uncertain frequent patterns. We have also proposed an application and some extended work of the two solutions. The uncertain frequent pattern mining for rural systems can find out special patterns relating to productivity and sustainability to improve profitability or environmental gain for valuable crops, and the extensions are related to incremental uncertain frequent pattern mining with the mUF-tree and mUF-trie.