基于数据集稀疏度的频繁项集挖掘算法性能分析

doi:10.11772/j.issn.1001-9081.2017092389

计算机应用 ›› 2018, Vol. 38 ›› Issue (4): 995-1000.DOI: 10.11772/j.issn.1001-9081.2017092389

基于数据集稀疏度的频繁项集挖掘算法性能分析

肖文, 胡娟

河海大学文天学院电气信息工程系, 安徽马鞍山 243031

收稿日期:2017-10-13 修回日期:2017-11-06 出版日期:2018-04-10 发布日期:2018-04-09
通讯作者: 肖文
作者简介:肖文(1984-),男,安徽黄山人,讲师,硕士研究生,主要研究方向:分布式计算、数据挖掘;胡娟(1985-),女,江苏海门人,讲师,硕士研究生,主要研究方向:软件工程、数据库系统。
基金资助:
安徽省高校自然科学研究项目（KJ2016A623）。

Performance analysis of frequent itemset mining algorithms based on sparseness of dataset

XIAO Wen, HU Juan

Department of Electrical and Information Engineering, Hohai University Wentian College, Maanshan Anhui 243031, China

Received:2017-10-13 Revised:2017-11-06 Online:2018-04-10 Published:2018-04-09
Supported by:
This work is partially supported by the Natural Science Foundation of the Colleges and Universities in Anhui Province (KJ2016A623).

摘要/Abstract

摘要： 频繁项集挖掘（FIM）是最基础的数据挖掘任务之一，被挖掘数据集的特征对FIM算法的性能有着显著影响。数据集稀疏度是体现数据集本质特征的属性之一，不同类型的FIM算法对数据集稀疏度的可扩展性有着很大的不同。针对如何量化度量数据集稀疏度及稀疏度对不同类型FIM算法性能影响等问题，首先回顾并讨论了已有的度量方法，然后提出两种新的量化度量数据集稀疏度的方法（基于事务差异度的度量方法和基于FP-Tree的度量方法）。这两种度量方法均考虑了FIM任务背景下最小支持度对数据集稀疏度的影响，反映的是事务频繁项集之间的差异度。最后通过实验验证了不同类型FIM算法对数据集稀疏度的可扩展性。实验结果表明，数据集稀疏度与最小支持度成反比，基于垂直格式的FIM算法在三类典型FIM算法中具有最佳的稀疏度可扩展性。

关键词: 数据挖掘, 频繁项集挖掘, 稀疏度, 可扩展性

Abstract: Frequent Itemset Mining (FIM) is one of the most important data mining tasks. The characteristics of the mined datasets have a significant effect on the performance of FIM algorithms. Sparseness of datasets is one of the attributes that characterize the essential characteristics of datasets. Different types of FIM algorithms are very different in the scalability of dataset sparseness. Aiming at the measurement of sparseness of datasets and influence of sparsity on the performance of different types of FIM algorithms, the existing measurement methods were reviewed and discussed, then two methods were proposed to quantify the sparseness of the datasets:the measurement based on transaction difference and the measurement based on FP-Tree method, both of which considered the influence of the minimum support degree on the sparseness of the datasets in the background of the FIM task, and reflected the difference between the frequent itemsets of the transaction. The scalability of different types of FIM algorithms for sparseness of datasets was studied experimentally. The experimental results show that the sparseness of datasets is inversely proportional to the minimum support, and the FIM algorithm based on vertical format has the best scalability in three kinds of typical FIM algorithms.

Key words: data mining, Frequent Itemset Mining (FIM), sparseness, scalability

中图分类号:

TP311.5

肖文, 胡娟. 基于数据集稀疏度的频繁项集挖掘算法性能分析[J]. 计算机应用, 2018, 38(4): 995-1000.

XIAO Wen, HU Juan. Performance analysis of frequent itemset mining algorithms based on sparseness of dataset[J]. Journal of Computer Applications, 2018, 38(4): 995-1000.

参考文献

[1] AGRAWAL R, IMIELINSKI T, SWAMI A N. Mining association rules between sets of items in large databases[C]//Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. New York:ACM,1993:207-216.
[2] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases[EB/OL].[2017-05-10]. http://www.cs.uu.nl/docs/vakken/adm/agrawalfast.pdf.
[3] PARK J S, CHEN M S, YU P S. Using a hash-based method with transaction trimming for mining association rules[J]. IEEE Transactions on Knowledge & Data Engineering, 1997, 9(5):813-825.
[4] OZEL S A, GUVENIR H A. An algorithm for mining association rules using perfect hashing and database pruning[C]//Proceedings of the 10th Turkish Symposium on Artificial Intelligence and Neural Networks. Berlin:Springer, 2001:257-264.
[5] BRIN S, MOTWANI R, ULLMAN J D, et al. Dynamic itemset counting and implication rules for market basket data[J]. ACM Sigmod Record, 2001, 26(2):255-264.
[6] HAN J, PEI J, YIN Y, et al. Mining frequent patterns without candidate generation:a frequent-pattern tree approach[J]. Data Mining & Knowledge Discovery, 2015, 8(1):53-87.
[7] PYUN G, YUN U, RYU K H. Efficient frequent pattern mining based on linear prefix tree[J]. Knowledge-Based Systems, 2014, 55:125-139.
[8] TSAY Y J, HSU T J, YU J R. FIUT:a new method for mining frequent itemsets[J]. Information Sciences, 2009, 179(11):1724-1737.
[9] LIN K C, LIAO I E, CHEN Z S. An improved frequent pattern growth method for mining association rules[J]. Expert Systems with Applications, 2011, 38(5):5154-5161.
[10] TSENG F C. An adaptive approach to mining frequent itemsets efficiently[J]. Expert Systems with Applications, 2012, 39(18):13166-13172.
[11] BURDICK D, CALIMLIM M, FLANNICK J, et al. MAFIA:a maximal frequent itemset algorithm[J]. IEEE Transactions on Knowledge & Data Engineering, 2005, 17(11):1490-1504.
[12] GOETHALS B, ZAKI M J. Advances in frequent itemset mining implementations:report on FIMI'03[J]. ACM Sigkdd Explorations Newsletter, 2003, 6(1):109-117.
[13] BAYARDO R J J, AGRAWAL R, GUNOPULOS D. Constraint-based rule mining in large, dense databases[J]. Data Mining & Knowledge Discovery, 2000, 4(2/3):217-240.
[14] GOUDA K, ZAKI M J. Efficiently mining maximal frequent itemsets[C]//ICDM 2001:Proceedings of the 2001 IEEE International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2001:163-170.
[15] PALMERINI P, ORLANDO S, PEREGO R. Statistical properties of transactional databases[C]//SAC 2004:Proceedings of the 2004 ACM Symposium on Applied Computing. New York:ACM, 515-519.
[16] STEINBACH M, TAN P N, KUMAR V. Support envelopes:a technique for exploring the structure of association patterns[C]//Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2004:296-305.
[17] YAN H, CHEN K, LIU L, et al. SCALE:a scalable framework for efficiently clustering transactional data[J]. Data Mining & Knowledge Discovery, 2010, 20(1):1-27.
[18] 闫珍, 皮德常, 吴文昊. 高维稀疏数据频繁项集挖掘算法的研究[J]. 计算机科学, 2011, 38(6):183-186.(YAN Z, PI D C, WU W H. Research on frequent itemsets mining algorithm for high-dimensional sparse data[J]. Computer Science, 2011, 38(6):183-186.)
[19] GRAHNE G, ZHU J F. Efficiently using prefix-trees in mining frequent itemsets[EB/OL].[2017-05-10]. http://ceur-ws.org/Vol-90/grahne.pdf.
[20] SALLEB-AOUISSI A, VRAIN C. A Contribution to the Use of Decision Diagrams for Loading and Mining Transaction Databases[M]. Amsterdam:IOS Press, 2007:220-242.
[21] SHEPARD T H. Looking for a structural characterization of the sparseness measure of(frequent closed) itemset contexts[J]. Information Sciences, 2013, 222(3):343-361.
[22] 严蔚敏, 吴伟民. 数据结构(C语言版)[M]. 北京:清华大学出版社, 2007:96-96.(YAN W M, WU W M. Data Structure(C Language Edition)[M]. Beijing:Tsinghua University Press, 2007:96-96.)
[23] YAHIA S B, HAMROUNI T, NGUIFO E M. Frequent closed itemset based algorithms[J]. ACM SIGKDD Explorations Newsletter, 2006, 8(1):93-104.
[24] PASQUIER N, BASTIDE Y, TAOUIL R, et al. Discovering frequent closed itemsets for association rules[C]//ICDT 1999:Proceedings of the 7th International Conference on Database Theory, LNCS 1540. Berlin:Springer, 1999:398-416.
[25] 韩家炜, 范明.数据挖掘:概念与技术[M]. 北京:机械工业出版社, 2012:27-46.(HAN J W, FAN M. Data Mining:Concepts and Techniques[M]. Beijing:China Machine Press, 2012:27-46.)
[26] IEEE computer society. Frequent itemset mining dataset repository[DB/OL].[2017-11-01].http://fimi.ua.ac.be/data/.

基于数据集稀疏度的频繁项集挖掘算法性能分析

Performance analysis of frequent itemset mining algorithms based on sparseness of dataset

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘世泽, 秦艳君, 王晨星, 苏琳, 柯其学, 罗海勇, 孙艺, 王宝会. 基于深度残差长短记忆网络交通流量预测算法[J]. 计算机应用, 2021, 41(6): 1566-1572.
[2]	李旭娟, 皮建勇, 黄飞翔, 贾海朋. 基于自生成深度神经网络的4D航迹预测[J]. 计算机应用, 2021, 41(5): 1492-1499.
[3]	张鲁飞, 孙茹君, 秦芳. 面向图计算的运行时系统的消息聚合技术[J]. 计算机应用, 2021, 41(4): 984-989.
[4]	陈凯, 于彦伟, 赵金东, 宋鹏. 基于城市交通监控大数据的工作位置推理方法[J]. 计算机应用, 2021, 41(1): 177-184.
[5]	龙洋洋, 陈玉玲, 辛阳, 豆慧. 基于联盟区块链的安全能源交易方案[J]. 计算机应用, 2020, 40(6): 1668-1673.
[6]	徐周波, 杨健, 刘华东, 黄文文. 基于XGBoost与拓扑结构信息的蛋白质复合物识别算法[J]. 计算机应用, 2020, 40(5): 1510-1514.
[7]	杜旭升, 于炯, 叶乐乐, 陈嘉颖. 基于图上随机游走的离群点检测算法[J]. 计算机应用, 2020, 40(5): 1322-1328.
[8]	陈曦, 梅广, 张金金, 许维胜. 融合知识图谱和协同过滤的学生成绩预测方法[J]. 计算机应用, 2020, 40(2): 595-601.
[9]	马董, 陈红梅, 王丽珍, 肖清. 空间亚频繁co-location模式的主导特征挖掘[J]. 计算机应用, 2020, 40(2): 465-472.
[10]	李莎莎, 梁冬阳, 余杰, 纪斌, 马俊, 谭郁松, 吴庆波. 基于师门关系的研究团队挖掘算法[J]. 计算机应用, 2020, 40(11): 3198-3202.
[11]	孙鹤立, 张优优, 杨洲, 何亮, 贾晓琳. 基于时间线段树的城市可达区域搜索[J]. 计算机应用, 2020, 40(10): 2936-2941.
[12]	李博, 张晓, 颜靖艺, 李可威, 李恒, 凌玉龙, 张勇. 基于值差度量和聚类优化的K最近邻算法在银行客户行为预测中的应用[J]. 计算机应用, 2019, 39(9): 2784-2788.
[13]	纪丽娜, 陈凯, 于彦伟, 宋鹏, 王淑莹, 王成锐. 基于城市交通大数据的车辆类别挖掘及应用分析[J]. 计算机应用, 2019, 39(5): 1343-1350.
[14]	史志才, 王益涵, 张晓梅, 陈珊珊, 陈计伟. 可扩展及可证安全的射频识别认证协议[J]. 计算机应用, 2019, 39(3): 774-778.
[15]	陈婉杰, 盛益强. 基于网络表示学习的非单一维度的社区发现算法[J]. 计算机应用, 2019, 39(12): 3467-3475.