Searching for closed itemset with formal concept analysis

The problem of mining frequent patterns plays an essential role in many important data mining tasks. However, it often generates a very large number of frequent itemsets. The set of frequent closed itemsets uniquely determines the exact frequency of all itemsets, yet it can be orders of magnitude smaller than the set of all frequent itemsets. An algorithm Closearcher based on formal concept analysis for closed itemset searching is proposed. This algorithm divides the whole search space of closed itemsets into several subspaces in accordance with criterions prescribed ahead, and introduces an efficient scheme to recognize the valid ones, in which the search for closed itemsets is bounded. An intermediate structure is employed to judge the validity of a subspace and search closed itemsets more efficiently. The algorithm is experimental evaluated and compared with the famous NextClosure algorithm proposed by Ganter for random generated data, as well as for real application data. The results show that our algorithm performs much better than the later.