Towards Efficient Closed Infrequent Itemset Mining Using Bi-Directional Traversing

摘要

In this work, we investigate the opposite question of frequent itemset mining: what patterns occurred less than a given minimum support in a transactional database? This question, known as infrequent itemset mining, is important in fields such as medical science, security, finance and scientific research. Frequent patterns represent expected or obvious information while infrequent patterns are those unexpected behaviors and are more interesting in some applications. For example, health-care needs to identify sporadic but lethal crossover effects. Security agents have to uncover infrequent associative fraud indicators. Existing infrequent itemset mining approaches are time-consuming. Furthermore, extracting all infrequent patterns might suffer from the redundant problem. In this paper, we study the two factors that affect the performance of itemset mining tasks. The concept of closed itemset is applied for infrequent patterns to reduce the number of returned patterns. An efficient closed infrequent itemset mining approach is proposed which combines both bottom-up and top-down traversing strategies. Extensive experimental results show that a simple algorithm based on our framework, without using advanced data structure or pruning techniques, can still be significantly more efficient when compared with other approaches.