Maximal Frequent Itemset Mining Algorithm Based on Nodeset

doi:10.3969/j.issn.1000-3428.2016.12.035

Abstract

Abstract: The major performance bottlenecks of most maximal frequent itemset mining algorithms based on FP-Tree are caused by recursively traversing and constructing conditional FP-Trees and superset check.Therefore,this paper proposes a maximal frequent itemset mining algorithm based on Nodeset named MFIN.Instead of recursively traversing and constructing conditional FP-Trees,this algorithm adopts a novel data structure called Nodeset to encode the nodes of POC-Tree and uses a set-enumeration tree to represent search space.Besides,this paper proposes an early-stopping method to minimize the cost of intersection operation of Nodesets and adopts parent equivalence pruning technique and look-ahead pruning technique to reduce the search space.The efficiency of superset check method is promoted by improving the projection strategy based on MFI-Tree.Experimental results show that the performance of MFIN algorithm is superior to the classic FP-Max algorithm which is based on FP-Tree in running time and efficiency on mushroom,pumsb and webdocs datasets.

Key words: maximal frequent itemset, association rule, pruning technique, prefix tree, superset check

摘要： 递归遍历、条件FP-Tree构建与超集检测是多数基于FP-Tree最大频繁项集挖掘算法的主要性能瓶颈。为此,提出一种基于Nodeset的最大频繁项集挖掘算法——MFIN算法。该算法采用Nodeset数据结构对POC-Tree的节点编码,将集合枚举树作为搜索空间,避免递归遍历和条件FP-Tree构建的时间开销。设计提前停止方法提高求解Nodeset交集的效率,采用父等价剪枝技术和前瞻剪枝技术缩小搜索空间。对基于MFI-Tree的投影策略进行改进,提升超集检测的速度。实验结果表明,MFIN算法在mushroom,pumsb,webdocs数据集上的运行时间及执行效率等总体性能明显优于基于FP-Tree的FP-Max算法。

关键词: 最大频繁项集, 关联规则, 剪枝技术, 前缀树, 超集检测

CLC Number:

TP391

LIN Chen,GU Junzhong. Maximal Frequent Itemset Mining Algorithm Based on Nodeset[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2016.12.035.

林晨,顾君忠. 基于Nodeset的最大频繁项集挖掘算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2016.12.035.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2016.12.035

http://www.ecice06.com/EN/Y2016/V42/I12/204

References

参考文献［1］Agrawal R,Imieliński T,Swami A.Mining Association Rules Between Sets of Items in Large Databases［C］//Proceedings of International Conference on Management of Data.New York,USA:ACM Press,1993:215-222. (下转第216页) (上接第207页) ［2］眭俊明,姜远,周志华.基于频繁项集挖掘的贝叶斯分类方法［J］.计算机研究与发展,2007,44(8):1293-1300. ［3］Han Jiawei,Kamber M.数据挖掘概念与技术［M］.范明,孟小峰,译.北京:机械工业出版社,2004. ［4］李金凤,王怀彬.基于关联规则的网络故障告警相关性分析［J］.计算机工程,2012,38(5):44-46. ［5］Agrawal R,Srikant R.Fast Algorithms for Mining Association Rules in Large Databases［C］//Proceedings of the 20th International Conference on Very Large Data Base.San Francisco,USA:Morgan Kaufmann Publishers Inc.,1994:326-333. ［6］Han Jiawei,Pei Jian,Yin Yiwen,et al.Mining Frequent Patterns Without Candidate Generation:A Frequent-pattern Tree Approach［J］.Data Mining and Knowledge Discovery,2004,8(1):53-87. ［7］Deng Zhihong,Lv Shenglong.Fast Mining Frequent Itemsets Using Nodesets［J］.Expert Systems with Applications,2014,41(10):4505-4512. ［8］Aggarwal C C,Han Jiawei.Frequent Pattern Min-ing［M］.Zurich,Switzerland:Springer,2014:169-178. ［9］Bayardo R J.Efficiently Mining Long Patterns from Database［C］//Proceedings of International Conference on Management of Data.New York,USA:ACM Press,1998:321-336. ［10］Agarwal R C,Aggarwal C C,Prasad V V V.Depth First Generation of Long Patterns［C］//Proceedings of the 6th International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2000:564-576. ［11］Burdick D,Calimlim M,Gehrke J.MAFIA:A Maximal Frequent Itemset Algorithm for Transactional Data-bases［C］//Proceedings of the 17th International Con-ference on Data Engineering.Heidelberg,Germany:［s.n.］,2001:458-469. ［12］薛安荣,王富强,李明.基于Iceberg概念格的最大频繁项集挖掘［J］.计算机工程,2011,37(7):35-37. ［13］张志刚,黄刘生,金宗安,等.基于父子等价剪枝策略的最大频繁项集挖掘［J］.计算机工程,2013,39(4):219-221,225. ［14］Grahne G,Zhu Jianfei.High Performance Mining of Maximal Frequent Itemsets［C］//Proceedings of the 6th International Workshop on High Performance Data Mining.Bethesda,USA:IEEE Press,2003:635-646. ［15］Han Jiawei,Cheng Hong,Xin Dong,et al.Frequent Pattern Mining:Current Status and Future Direc-tions［J］.Data Mining and Knowledge Discovery,2007,15(1):55-86. 编辑索书志

[1]	LIU Zhiguo, CAI Wenzhu, LI Yunqi, PAN Chengsheng. Feature Extraction Method for Unknown Wireless Protocol Based on Sequence Statistical [J]. Computer Engineering, 2021, 47(11): 192-197.
[2]	WANG Yuqi, GAO Jianhua. A Web Application Statistical Testing Method Based on Association Rules [J]. Computer Engineering, 2020, 46(3): 206-213.
[3]	LI Jie, ZHU Hongliang, CHEN Yuling, XIN Yang. Improved Parallel Apriori Algorithm Based on Hash Storage and Transaction Weighting [J]. Computer Engineering, 2020, 46(11): 109-116.
[4]	XIANG Chengguan,XIONG Shihuan,WANG Dong,XIONG Weicheng. Social Friend Recommendation Algorithm Based on Association Rules and Similarity [J]. Computer Engineering, 2019, 45(4): 175-180.
[5]	WU Ruixue, PENG Changgen, LIU Botao, DING Hongfa, XIE Mingming. Multi-sensitive Attribute Anonymity Algorithm Based on Association Rule [J]. Computer Engineering, 2019, 45(11): 126-132.
[6]	XIE Bin,ZHANG Kun,CAI Ying,JIANG Tongtong,MA Mengyue. Research on Mining Algorithm for Association Co-occurrence Rule of Moving Targets [J]. Computer Engineering, 2018, 44(8): 61-67,73.
[7]	WANG Shuyan,LUO Dan,SUN Jiaze. Fault Location Method Based on Variable Slicing and Association Rule [J]. Computer Engineering, 2018, 44(7): 74-79,85.
[8]	NING Ke,SUN Tongjing,ZHAO Haoqiang. Naive Bayesian Classification Algorithm Based on Attribute Association [J]. Computer Engineering, 2018, 44(6): 18-23.
[9]	LI Hongcheng,WU Xiaoping. Network Intrusion Correlation Method with Differential Privacy Protection of Alerts Sequence [J]. Computer Engineering, 2018, 44(5): 128-132.
[10]	WU Qiong,ZENG Qingpeng. Mining of Positive and Negative Quantitative Association Rules Based on Multi-objective Firework Optimization Algorithm [J]. Computer Engineering, 2017, 43(6): 158-168.
[11]	HUANG Wenming,MO Yang. Chinese Spam Message Filtering Based on Text Weighted KNN Algorithm [J]. Computer Engineering, 2017, 43(3): 193-199.
[12]	CHENG Guang,WANG Xiaofeng. Incremental Updating Algorithm of Parallel Association Rule Based on MapReduce [J]. Computer Engineering, 2016, 42(2): 21-25,32.
[13]	WANG Yingbo,MA Jing,CHAI Jiajia,ZHAO Bin. Improved Association Rule Mining Algorithm Based on Hadoop Platform [J]. Computer Engineering, 2016, 42(10): 69-74,79.
[14]	DING Sanjun,XUE Yu,WANG Chaoxia,XU Lei. Fault Prediction of Virtual Environment Host Based on Fuzzy Data Mining [J]. Computer Engineering, 2015, 41(11): 202-206.
[15]	ZHANG Zhi-Gang, HUANG Liu-Sheng, JIN Zong-An, XIANG Chi-Ping. Maximal Frequent Itemset Mining Based on Parent-child Equivalency Pruning Strategy [J]. Computer Engineering, 2013, 39(4): 219-221,225.

Please choose a citation manager

Content to export