Constrained frequent pattern mining on univariate uncertain data

In this paper, we propose a new algorithm called CUP-Miner (Constrained Univariate Uncertain Data Pattern Miner) for mining frequent patterns from univariate uncertain data under user-specified constraints. The discovered frequent patterns are called constrained frequent U2 patterns (where “U2” represents “univariate uncertain”). In univariate uncertain data, each attribute in a transaction is associated with a quantitative interval and a probability density function. The CUP-Miner algorithm is implemented in two phases: In the first phase, a U2P-tree (Univariate Uncertain Pattern tree) is constructed by compressing the target database transactions into a compact tree structure. Then, in the second phase, the constrained frequent U2 pattern is enumerated by traversing the U2P-tree with different strategies that correspond to different types of constraints. The algorithm speeds up the mining process by exploiting five constraint properties: succinctness, anti-monotonicity, monotonicity, convertible anti-monotonicity, and convertible monotonicity. Our experimental results demonstrate that CUP-Miner outperforms the modified CAP algorithm, the modified FIC algorithm, the modified U2P-Miner algorithm, and the modified Apriori algorithm.

► CUP-Miner algorithm is proposed for constrained mining on univariate uncertain data. ► The CUP-Miner algorithm utilizes five well-known constraint properties. ► The CUP-Miner algorithm pushes constraint verification into the mining process. ► The CUP-Miner algorithm outperforms the compared methods in terms of runtime.