基于N-list和DiffNodeset结构的频繁项集并行挖掘算法

作者：张阳; 王瑞; 吴贯锋^*; 刘弘毅

来源：计算机科学, 2023, 50(11): 55-61.

• 频繁项集
• 负载估计
• MapReduce
• 稀疏度估计
• 集合枚举树

频繁项集挖掘是数据挖掘中的一个基本问题，在许多数据挖掘应用中发挥着重要作用。针对并行频繁项集挖掘算法MrPrePost在大数据环境存在密集数据集下算法效率下降、计算节点负载量不均衡和冗余搜索等问题，提出了基于N-lists和DiffNodeset两种结构的并行频繁项集挖掘算法(Parallel Mining algorithm of Frequent Itemset based on N-list and DiffNodeset structure, PFIMND)。首先，根据N-list和DiffNodeset在存储不同数据集上的优势，设计了稀疏度估计函数(Sparsity Estimation, SE),根据数据集稀疏程度灵活选取其中之一压缩数据集，相比采用单一存储结构消耗的内存更少；其次，提出了计算量估计函数(Computation Estimation, CE)来估计频繁1项集F-list中每一项的负载量，并根据计算量进行均匀分组；最后采用集合枚举树作为搜索空间，为避免组合爆炸和冗余搜索问题，设计了超集剪枝策略和基于宽度优先搜索的剪枝策略，生成最终的挖掘结果。实验结果表明，相比同类算法HP-FIMBN,PFIMND算法在Susy数据集上挖掘频繁项集的效果提升了12.3%。

• 出版日期2023
• 单位西南交通大学; 数学学院