基于效用表的快速高平均效用挖掘算法

doi:10.11772/j.issn.1001-9081.2016.11.3062

计算机应用 ›› 2016, Vol. 36 ›› Issue (11): 3062-3066.DOI: 10.11772/j.issn.1001-9081.2016.11.3062

基于效用表的快速高平均效用挖掘算法

王敬华, 罗相洲, 吴倩

华中师范大学计算机学院, 武汉 430079

收稿日期:2016-05-16 修回日期:2016-06-20 出版日期:2016-11-10 发布日期:2016-11-12
通讯作者: 罗相洲
作者简介:王敬华(1965-),男,湖北红安人,副教授,硕士,主要研究方向:数据挖掘、现代信息系统;罗相洲(1991-),男,湖北武汉人,硕士研究生,主要研究方向:数据库、数据挖掘;吴倩(1990-),女,湖北汉川人,硕士研究生,主要研究方向:数据挖掘、复杂网络。
基金资助:
国家自然科学基金资助项目（61370108）。

Fast high average-utility itemset mining algorithm based on utility-list structure

WANG Jinghua, LUO Xiangzhou, WU Qian

School of Computer, Central China Normal University, Wuhan Hubei 430079, China

Received:2016-05-16 Revised:2016-06-20 Online:2016-11-10 Published:2016-11-12
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61370108).

摘要/Abstract

摘要： 高效用项集挖掘在数据挖掘领域中受到了广泛的关注，但是高效用项集挖掘并没有考虑项集长度对效用值的影响，所以高平均效用项集挖掘被提出；而目前的一些高平均效用项集挖掘算法需要耗费大量的时间才能挖掘出有效的高平均效用项集。针对此问题，给出了一个高平均效用项集挖掘的改进算法——FHAUI。FHAUI算法将效用信息保存到效用列表中，通过效用列表的比较来挖掘出所有的高平均效用值，同时FHAUI算法还采用了一个二维矩阵来有效减少二项效用值的连接比较次数。最后将FHAUI算法在多个经典的数据集上测试。实验结果表明，FHAUI算法在效用列表的连接比较次数上有了极大的降低，同时其时间性能也有非常大提高。

关键词: 平均效用, 高效用, 模式挖掘, 数据挖掘, 频繁模式

Abstract: In the field of data mining, high utility itemset mining has been widely studied. However, high utility itemset mining does not consider the effect of the itemset length. To address this issue, high average-utility itemset mining has been proposed. At present, the proposed high average utility itemset mining algorithms take a lot of time to dig out the high average-utility itemset. To solve this problem, an improved high average itemset mining algorithm, named FHAUI (Fast High Average Utility Itemset), was proposed. FHAUI stored the utility information in the utility-list and mined all the high average-utility itemsets from the utility-list structure. At the same time, FHAUI adopted a two-dimensional matrix to effectively reduce the number of join-operations. Finally, the experimental results on several classical datasets show that FHAUI has greatly reduced the number of join-operations, and reduced its cost in time consumption.

Key words: average utility, high utility, pattern mining, data mining, frequent pattern

中图分类号:

TP311.13

王敬华, 罗相洲, 吴倩. 基于效用表的快速高平均效用挖掘算法[J]. 计算机应用, 2016, 36(11): 3062-3066.

WANG Jinghua, LUO Xiangzhou, WU Qian. Fast high average-utility itemset mining algorithm based on utility-list structure[J]. Journal of Computer Applications, 2016, 36(11): 3062-3066.

参考文献

[1] AGRAWAL R, IMIELINSKI T, SWAMI A. Mining association rules between sets of items in large databases[J]. ACM SIGMOD Record, 1993, 22(2):207-216.
[2] HAN J W, PEI J, YIN Y W. Mining frequent patterns without candidate generation[J].ACM SIGMOD Record, 2000, 29(2):1-12.
[3] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases[C]//Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco, CA:Morgan Kaufmann Publishers Inc., 1994:487-499.
[4] 李也白, 唐辉, 张淳,等. 基于改进的FP-tree的频繁模式挖掘算法[J]. 计算机应用, 2011, 31(1):101-103. (LI Y B, TANG H, ZHANG C, et. al. Frequent pattern mining algorithm based on improved FP-tree[J]. Journal of Computer Applications, 2011, 31(1):101-103.)
[5] LIU M, QU J. Mining high utility itemsets without candidate generation[C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management. New York:ACM, 2012:55-64.
[6] FOURNIER-VIGER P, WU C W, ZIDA S, et al. FHM:faster high-utility itemset mining using estimated utility co-occurrence pruning[C]//Proceedings of the 21st International Symposium Foundations of Intelligent Systems. Berlin:Springer, 2014:83-92.
[7] KRISHNAMOORTHY S. Pruning strategies for mining high utility itemsets[J]. Expert Systems with Applications, 2015, 42(5):2371-2381.
[8] YAO H, HAMILTON H J, BUTZ C J. A foundational approach to mining itemset utilities from databases[C]//Proceedings of the 2004 SIAM International Conference on Data Mining. Philadelphia, PA:SIAM, 2004, 4:215-221.
[9] LIU Y, LIAO W, CHOUDHARY A. A two-phase algorithm for fast discovery of high utility itemsets[C]//Proceedings of the 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Heidelberg:Springer-Verlag, 2005:689-695.
[10] TSENG V S, SHIE B E, WU C W, 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.
[11] TSENG V S, WU C W, SHIE B E, et al. UP-Growth:an efficient algorithm for high utility itemset mining[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2010:253-262.
[12] 祝孔涛, 李兴建, 王乐. 高效用项集挖掘算法[J]. 计算机工程与设计, 2013, 34(12):4220-4225.(ZHU K T, LI X J, WANG L. Improved algorithm for mining high utility itemsets[J]. Computer Engineering and Design, 2013, 34(12):4220-4225.)
[13] HONG T P, LEE C H, WANG S L. Effective utility mining with the measure of average utility[J]. Expert Systems with Applications, 2011, 38(7):8259-8265.
[14] LIN C W, HONG T P, LU W H. Efficiently mining high average utility itemsets with a tree structure[M]//Proceedings of the 2nd International Conference on Intelligent Information and Database Systems. Berlin:Springer-Verlag, 2010:131-139.
[15] LAN G C, HONG T P, TSENG V S. A projection-based approach for discovering high average-utility itemsets[J]. Journal of Information Science and Engineering, 2012, 28(1):193-209.
[16] LU T, VO B, NGUYEN H T, et al. A new method for mining high average utility itemsets[C]//Proceedings of the 13th IFIP TC8 International Conference on Computer Information Systems and Industrial Management. Berlin:Springer, 2014:33-42.
[17] LIN J C W, LI T, FOURNIER-VIGER P, et al. An efficient algorithm to mine high average-utility itemsets[J]. Advanced Engineering Informatics, 2016, 30(2):233-243.

基于效用表的快速高平均效用挖掘算法

Fast high average-utility itemset mining algorithm based on utility-list structure

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	康军, 黄山, 段宗涛, 李宜修. 时空轨迹序列模式挖掘方法综述[J]. 计算机应用, 2021, 41(8): 2379-2385.
[2]	孙蕊, 韩萌, 张春砚, 申明尧, 杜诗语. 含负项top-k高效用项集挖掘算法[J]. 计算机应用, 2021, 41(8): 2386-2395.
[3]	刘世泽, 秦艳君, 王晨星, 苏琳, 柯其学, 罗海勇, 孙艺, 王宝会. 基于深度残差长短记忆网络交通流量预测算法[J]. 计算机应用, 2021, 41(6): 1566-1572.
[4]	李旭娟, 皮建勇, 黄飞翔, 贾海朋. 基于自生成深度神经网络的4D航迹预测[J]. 计算机应用, 2021, 41(5): 1492-1499.
[5]	陈凯, 于彦伟, 赵金东, 宋鹏. 基于城市交通监控大数据的工作位置推理方法[J]. 计算机应用, 2021, 41(1): 177-184.
[6]	龙洋洋, 陈玉玲, 辛阳, 豆慧. 基于联盟区块链的安全能源交易方案[J]. 计算机应用, 2020, 40(6): 1668-1673.
[7]	杜旭升, 于炯, 叶乐乐, 陈嘉颖. 基于图上随机游走的离群点检测算法[J]. 计算机应用, 2020, 40(5): 1322-1328.
[8]	徐周波, 杨健, 刘华东, 黄文文. 基于XGBoost与拓扑结构信息的蛋白质复合物识别算法[J]. 计算机应用, 2020, 40(5): 1510-1514.
[9]	马董, 陈红梅, 王丽珍, 肖清. 空间亚频繁co-location模式的主导特征挖掘[J]. 计算机应用, 2020, 40(2): 465-472.
[10]	陈曦, 梅广, 张金金, 许维胜. 融合知识图谱和协同过滤的学生成绩预测方法[J]. 计算机应用, 2020, 40(2): 595-601.
[11]	李莎莎, 梁冬阳, 余杰, 纪斌, 马俊, 谭郁松, 吴庆波. 基于师门关系的研究团队挖掘算法[J]. 计算机应用, 2020, 40(11): 3198-3202.
[12]	孙鹤立, 张优优, 杨洲, 何亮, 贾晓琳. 基于时间线段树的城市可达区域搜索[J]. 计算机应用, 2020, 40(10): 2936-2941.
[13]	王淳颖, 张驯, 赵金雄, 袁晖, 李方军, 赵博, 朱小琴, 杨凡, 吕世超. 基于多源告警的攻击事件分析[J]. 计算机应用, 2020, 40(1): 123-128.
[14]	李博, 张晓, 颜靖艺, 李可威, 李恒, 凌玉龙, 张勇. 基于值差度量和聚类优化的K最近邻算法在银行客户行为预测中的应用[J]. 计算机应用, 2019, 39(9): 2784-2788.
[15]	纪丽娜, 陈凯, 于彦伟, 宋鹏, 王淑莹, 王成锐. 基于城市交通大数据的车辆类别挖掘及应用分析[J]. 计算机应用, 2019, 39(5): 1343-1350.