基于差集的高效用项集挖掘方法

doi:10.3969/j.issn.0372-2112.2018.08.002

电子学报 ›› 2018, Vol. 46 ›› Issue (8): 1804-1814.DOI: 10.3969/j.issn.0372-2112.2018.08.002

基于差集的高效用项集挖掘方法

黄坤¹, 吴玉佳², 李晶²

1. 中国舰船研究设计中心, 湖北武汉 430064;
2. 武汉大学计算机学院, 湖北武汉 430072

收稿日期:2016-11-26 修回日期:2017-06-30 出版日期:2018-08-25
- 作者简介:
- 黄坤男,1979年10月生于湖北孝感,中国舰船研究设计中心高级工程师,研究方向电子信息系统.E-mail:hkcfan@163.com;吴玉佳 男,1986年11月生于湖北广水.武汉大学计算机学院博士生.研究方向为数据挖掘与机器学习.E-mail:wuyujia@whu.edu.cn
- 基金资助:
- 国家自然科学基金 (No.61303046）

Mining High Utility Itemsets Using Diffsets

HUANG Kun¹, WU Yu-jia², LI Jing²

1. China Ship Development and Design Center, Wuhan, Hubei 430072, China;
2. School of Computer, Wuhan University, Wuhan, Hubei 430072, China

Received:2016-11-26 Revised:2017-06-30 Online:2018-08-25 Published:2018-08-25

摘要/Abstract

摘要： 高效用项集挖掘已成为关联规则中的一个热点研究问题.一些基于垂直结构的算法已用来挖掘高效用项集，此类算法的主要优点是将项集的事务和效用信息存储到效用列表中.在求一个项集的超集所在事务可以通过对它的子集进行一次交集运算得到.这种算法在稀疏数据集中非常的有效.但在稠密数据集中存在一个问题，即列表中存储的事务太多，在计算用于剪枝的效用上界时，需要耗费大量的存储空间，同时也影响运行速度.并且在现有的算法中，缺乏针对稠密数据集的高效用项集挖掘算法，往往需要设置很高的最小效用阈值，影响算法的运行效率.针对此问题，提出一个新的算法D-HUI （mining High Utility Itemsets using Diffsets）以及一个新的数据结构—项集列表，首次在高效用项集挖掘中引入差集的概念.利用事务的差集求项集的效用上界，减少计算量以及存储空间，从而提高算法的运行效率.实验结果表明，提出的算法在稠密数据集中，执行速度更快，内存消耗更少.

关键词: 关联规则, 高效用项集, 稠密数据集, 垂直结构, 差集

Abstract: High utility itemsets mining (HUIM) has become an emerging topic in association rules.Some algorithms based on vertical data structure have been used for mining high utility itemsets(HUIs),and the main advantage of the algorithms are to maintain transaction and utility information of itemsets in some utility lists(ULs).The transactions of superset of an itemsets can be calculated by its subset doing an intersection.These algorithms are very effective in sparse datasets.However,in the dense datasets,a problem is that:too many transactions maintained in ULs,not only required a lot of memory space,but also affected the runtime when computing the upper bound of utility in order to prune search space.Few of existing HUIM algorithm focused on dense datasets and it often need to set a high minimum threshold utility which affect the running efficiency of the algorithm.To solve this problem,propose a new algorithm D-HUI(mining High Utility Itemsets using Diffsets) and a new data structure,namely Itemset Lists (ILs).Introduce the concept of diffsets in the HUIM.Calculate upper bound of utility by using diffsets of transaction for pruning search space.The runtime and memory consumption are reduced,and the running efficiency of the algorithm is improved.Experimental results show that the proposed algorithm in the dense datasets outperforms state-of-the-art algorithms in terms of both running time and memory consumption.

Key words: association rules, high utility itemsets, dense datasets, vertical structure, diffsets

中图分类号:

TP311

黄坤, 吴玉佳, 李晶. 基于差集的高效用项集挖掘方法[J]. 电子学报, 2018, 46(8): 1804-1814.

HUANG Kun, WU Yu-jia, LI Jing. Mining High Utility Itemsets Using Diffsets[J]. Acta Electronica Sinica, 2018, 46(8): 1804-1814.

参考文献

[1] J Han,J Pei,Y Yin,Mining frequent patterns without candidate generation[A].Proc of the 2000 ACM SIGMOD International Conference on Management of Data[C].Dallas,TX:ACM,2000.1-12.
[2] M J Zaki.Scalable algorithms for association mining[J].IEEE Transactions on Knowledge and Data Engineering,2000,12(3):372-390.
[3] Ke-Chung Lin,I-En Liao,Tsui-Ping Chang,et al.A frequent itemset mining algorithm based on the Principle of Inclusion-Exclusion and transaction mapping[J].Information Sciences,2014,276(C):278-289.
[4] Yun Sing Koh,Sri Devi Ravana.Unsupervised rare pattern mining:A survey[J].ACM Transactions on Knowledge Discovery from Data,2016,10(4):45:1-29.
[5] 刘旭,毛国君,孙岳,等.数据流中频繁闭项集的近似挖掘算法[J].电子学报,2007,35(5):900-905. LIU Xu,MAO Guo-jun,SUN Yue,et al.An algorithm to approximately mine frecuent closed ltemsets from data streams[J].Acta Electronica Sinica,2007,35(5):900-905.(in Chinese)
[6] 周秀梅,黄名选.基于项权值变化的完全加权正负关联规则挖掘[J].电子学报,2015,43(8):1545-1554. ZHOU Xiu-mei,HUANG Ming-xuan.All-weighted positive and negative association ruies mining based on dynamic item weight[J].Acta Electronica Sinica,2015,43(8):1545-1554.(in Chinese)
[7] Y Liu,W Liao,A Choudhary.A two-phase algorithm for fast discovery of high utility itemsets[A].Proc of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining[C].Hanoi,Vietnam:Springer,2005.689-695.
[8] H Yao,H J Hamilton.Mining itemset utilities from transaction databases[J].Data and Knowledge Engineering,2006,59(3):603-626.
[9] Y C Li,J S Yeh,C C Chang.Isolated items discarding strategy for discovering high utility itemsets[J].Data and Knowledge Engineering,2008,64(1):198-217.
[10] C F Ahmed,S K Tanbeer,B S Jeong,et al.Efficient tree structures for high utility pattern mining in incremental databases[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(12):1708-1721.
[11] V S Tseng,C W Wu,B E Shie,et al.Up-growth:an efficient algorithm for high utility itemset mining[A].Proc of the 10th Conference Knowledge Discovery and Data Mining[C].Washington,DC:ACM,2010.253-262.
[12] V S Tseng,B E Shie,C W Wu,et al.Efficient algorithms for mining high utility itemsets from transactional databases[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(8):1772-1786.
[13] M C.Liu,J F Qu.Mining high utility itemsets without candidate generation[A].Proc of the 12th International Conference on Information and Knowledge Management[C].Maui,HI,USA:ACM,2012.55-64.
[14] Fournier-Viger P,C W Wu,Zida S,et al.FHM:Faster high-utility itemset mining using estimated utility co-occurrence pruning[A].Proc of the 21th International Symposium on Methodologies for Intelligent Systems[C].Roskilde,Denmark:Springer,2014.83-92.
[15] S Krishnamoorthy.Pruning strategies for mining high utility itemsets[J].Expert Systems with Applications,2015,42(5):2371-2381.
[16] C W Wu,P Fournier-Viger,P S Yu,et al.Efficient mining of a concise and lossless representation of high utility itemsets[A].Proc of the 11th IEEE International Conference on Data Mining[C].Vancouver,Canada:IEEE,2011.824-833.
[17] V S Tseng,C W Wu,Philippe Fournier-Viger et al.Efficient algorithms for mining the concise and lossless representation of high utility itemsets[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(3):726-739.
[18] J Sahoo,A K Das,A Goswami.An efficient fast algorithm for discovering closed+ high utility itemsets[J].Applied Intelligence,2016,45(1):44-74.
[19] C W Wu,Philippe Fournier-Viger,J Y Gu,et al.Mining closed+ high utility itemsets without candidate generation[A].The 2015 Conference on Technologies and Applications of Artificial Intelligence[C].Taiwan:TAAI,2015.1-8.
[20] Guo S M,Gao H.HUITWU:An efficient algorithm for high-utility itemset mining in transaction databases[J].Journal of Computer Science and Technology,2016,31(4):776-786.
[21] Tseng V S,Wu C W,Lin J H,et al.UP-Miner:A utility pattern mining toolbox[A].IEEE International Conference on Data Mining Workshop[C].Atlantic,USA:IEEE,2015.1656-1659.
[22] Fournier-Viger P,Lin C W,Gomariz A,et al.The SPMF open-source data mining library version 2[A].Machine Learning and Knowledge Discovery in Databases[C].Berlin,Germany:Springer International Publishing,2016.36-40.
[23] B Goethals,MJ Zaki.Frequent Itemset mining implementations repository[DB/OL].http://fimi.ua.ac.be/,2016-06-30.
[24] J Pisharath,Y Liu,J Parhi,et al.NU-MineBench Version 3.0.1[DB/OL].http://cucis.ece.northwestern.edu/projects/DMS/MineBench.html,2016-06-30.

基于差集的高效用项集挖掘方法

Mining High Utility Itemsets Using Diffsets

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘凯, 倪佳. 基于循环差集的最佳高斯整数序列构造[J]. 电子学报, 2021, 49(8): 1474-1479.
[2]	吴玉佳, 李晶, 宋成芳, 常军. 基于高效用神经网络的文本分类方法[J]. 电子学报, 2020, 48(2): 279-284.
[3]	杜栋栋, 任星彰, 陈坤, 叶蔚, 赵文, 张世琨. 一种基于One-Class SVM和GP安全事件关联规则生成方法研究[J]. 电子学报, 2018, 46(8): 1793-1803.
[4]	贾彦国, 沈秀敏, 张立超. 几类高能量效率的差集偶的研究[J]. 电子学报, 2018, 46(2): 304-307.
[5]	周秀梅, 黄名选. 基于项权值变化的完全加权正负关联规则挖掘[J]. 电子学报, 2015, 43(8): 1545-1554.
[6]	李文梅, 陈尔学, 李增元, 冯琦, 杨浩, 黎晓. 频谱分析技术在层析SAR森林垂直结构信息提取中的应用性能分析[J]. 电子学报, 2015, 43(4): 694-699.
[7]	郭晓波, 赵书良, 王长宾, 陈敏. 一种新的面向普通用户的多值属性关联规则可视化挖掘方法[J]. 电子学报, 2015, 43(2): 344-352.
[8]	耿生玲, 李永明, 刘震. 关联规则挖掘的软集包含度方法[J]. 电子学报, 2013, 41(4): 804-809.
[9]	李珺;潘启树;周浦城;洪炳镕. 未知环境下多机器人协作追捕算法[J]. 电子学报, 2011, 39(3): 567-574.
[10]	靳慧龙;许成谦. 基于分圆类的一类伪随机二进序列偶的构造方法研究[J]. 电子学报, 2010, 38(7): 1608-1611.
[11]	王扬志;许成谦. 可分差集偶与几乎最佳二元序列偶的研究[J]. 电子学报, 2009, 37(4): 692-695.
[12]	刘波, 潘久辉. 基于频繁模式图的多维关联规则挖掘算法研究[J]. 电子学报, 2007, 35(8): 1612-1616.
[13]	李美安;刘心松;王征. 一种基于松弛循环差集的高性能分布式互斥算法[J]. 电子学报, 2007, 35(1): 58-63.
[14]	罗永龙, 黄刘生, 荆巍巍, 姚亦飞, 陈国良. 一个保护私有信息的布尔关联规则挖掘算法[J]. 电子学报, 2005, 33(5): 900-903.
[15]	王云岚;李增智;屈科文. 基于候选项集个数上阶的增量式关联规则更新算法[J]. 电子学报, 2004, 32(5): 731-734.