NB-MAFIA_ 基于N-List 的最长频繁项集挖掘算法.pdf

北京大学学报(自然科学版) 第 52 卷 第 2 期 2016 年 3 月 Acta Scientiarum Naturalium Universitatis Pekinensis, Vol. 52, No. 2 (Mar. 2016) doi: 10.13209/j.0479-8023.2015.125 NB-MAFIA: 基于N-List 的最长频繁项集挖掘算法 1 1 2,3,† 沈戈晖 刘沛东 邓志鸿 1. 北京大学信息科学技术学院计算机科学技术系 , 北京 100871; 2. 北京大学信息科学技术学院智能科学系 , 北京 100871; 3. 北京大学机器感知与智能教育部重点实验室 , 北京 100871; † 通信作者 , E-mail: zhdeng@ 摘要 本文在深度优先搜索的框架上, 引入基于项集前缀树节点链表的项集表示方法 N-List, 提出一个高效 的最长频繁项集挖掘算法 NB-MAFIA 。N-List 的高压缩率和高效的求交集方法可以实现项集支持度的快速 计算 , 同时采用对搜索空间的剪枝策略和超集检测策略来提高算法效率。在多个真实和仿真数据集上, 通过 实验评估了 NB-MAFIA 和两个经典算法。实验结果表明 NB-MAFIA 在多数情况下优于其他算法, 尤其在真 实和稠密数据集上优势更为明显。 关键词 数据挖掘 ; 频繁项集挖掘 ; 最长项集 ; N-List; 算法 中图分类号 TP302 NB-MAFIA: An N-List Based Maximal Frequent Itemset Algorithm 1 1 2,3,† SHEN Gehui , LIU Peidong , DENG Zhihong 1. Department of Computer Science and Technology, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871; 2. Department of Machine Intelligence, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871; 3. Key Laboratory Machine Perception (MOE), Peking University, Beijing 100871; † Corresponding author: E-mail: zhdeng@ Abstract The authors propose an efficient algorithm, NB-MAFIA, for mining maximal frequent itemset using N- List, which uses node list of prefix tree to represent itemsets. By using N-List, itemsets’ su