An Efficient Approach for Mining Weighted Approximate Closed Frequent Patterns Considering Noise Constraints

摘要

Based on the frequent pattern mining, closed frequent pattern mining and weighted frequent pattern mining have been studied to reduce the search space and discover important patterns. In the previous definition of weighted closed patterns, supports of patterns are only considered to compute the closures of the patterns. It means that the closures of weighted frequent patterns cannot be perfectly checked. Moreover, the usefulness of weighted closed frequent patterns depends on the presence of frequent patterns that have supersets with the exactly same weighted support. However, from the errors such as noise, slight changes in items' supports or weights by them have significantly negative effects on the mining results, which may prevent us from obtaining exact and valid analysis results since the errors can break the original characteristics of items and patterns. In this paper, to solve the above problems, we propose a concept of robust weighted closed frequent pattern mining, and an approximate bound is defined on the basis of the concept, which can relax requirements for precise equality among patterns' weighted supports. Thereafter, we propose a weighted approximate closed frequent pattern mining algorithm which not only considers the two approaches but also suggests fault tolerant pattern mining in the noise constraints. To efficiently mine weighted approximate closed frequent patterns, we suggest pruning and subset checking methods which reduce search space. We also report extensive performance study to demonstrate the effectiveness, efficiency, memory usage, scalability, and quality of patterns in our algorithm.