Abstract: In data mining, mining maximum frequent itemsets instead of mining frequent itemsets can greatly improve the operating efficiency of system. The running time consumption of existing maximum frequent itemset mining algorithms is still very large. In order to solve the problem, a new DiffNodeset Maxmal Frequent Itemset Mining (DNMFIM) algorithm was proposed. Firstly, a new data structure DiffNodeset was adopted to realize the fast calculation of intersection and support degree. Secondly, the connection method with linear time complexity was adopted to reduce the complexity of connecting two DiffNodesets and avoid multiple invalid calculations. Then, the set-enumeration tree was adopted as the search space, and a variety of optimal pruning strategies were used to reduce the search space. Finally, the superset detection technology used in the MAximal Frequent Itemset Algorithm (MAFIA) algorithm was adopted to improve the accuracy of algorithm effectively. The experimental results show that, DNMFIM algorithm outperforms MAFIA and N-list based MAFIA (NB-MAFIA) in terms of time efficiency. The proposed algorithm has a good performance when mining the maximal frequent itemsets in different types of datasets.

Key words: maximal frequent itemset mining, association rule, set-enumeration tree, optimized pruning, superset detection

摘要： 在数据挖掘中，通过挖掘最大频繁项集来代替挖掘频繁项集可以大大地提升系统的运行效率。针对现有的最大频繁项集挖掘算法的运行时间消耗仍然很大的问题，提出了一种基于DiffNodeset结构的最大频繁项集挖掘（DNMFIM）算法。首先，采用了一种新的数据结构DiffNodeset来实现求交集以及支持度的快速计算；其次，引入一种新的线性复杂度的连接方法来降低两个DiffNodeset在连接过程中的复杂度，避免了多次的无效计算；然后，将集合枚举树作为搜索空间，同时采用多种优化剪枝策略来缩小搜索空间；最后，再结合最大频繁项集挖掘算法（MAFIA）中所使用的超集检测技术来有效地提高算法的准确性。实验结果表明，DNMFIM算法在时间效率方面性能优于MAFIA与基于N-list的MAFIA（NB-MAFIA），该算法在不同类型数据集中进行最大频繁项集挖掘时均有良好的效果。

关键词: 最大频繁项集挖掘, 关联规则, 集合枚举树, 优化剪枝, 超集检测