Efficient Infrequent Pattern Mining Using Negative Itemset Tree

In this work, we focus on a simple and fundamental question: How to find infrequent patterns, i.e. patterns with small support value, in a transactional database. In various practical applications such as science, medical and accident data analysis, frequent patterns usually represent obvious and expected phenomena. Really interesting information might hide in obscure rarity. Existing rare pattern mining approaches are mainly adapted from frequent itemset mining algorithms, which either suffered from the expensive candidate generation step or need to traverse all frequent patterns first. In this paper, we propose an infrequent pattern mining algorithm using a top-down and depth-first traversing strategy to avoid the two obstacles above. A negative itemset tree is employed to accelerate the mining process with its dataset compressing and fast counting ability.