基于索引效用的Top-k高效用项集挖掘方法

doi:10.12068/j.issn.1005-3026.2016.01.006

东北大学学报:自然科学版 ›› 2016, Vol. 37 ›› Issue (1): 24-28.DOI: 10.12068/j.issn.1005-3026.2016.01.006

基于索引效用的Top-k高效用项集挖掘方法

林树宽，王晓丛，乔建忠，王蕊

(东北大学信息科学与工程学院，辽宁沈阳110819)

收稿日期:2014-10-31 修回日期:2014-10-31 出版日期:2016-01-15 发布日期:2016-01-08
通讯作者: 林树宽
作者简介:林树宽(1966-)，女，吉林长春人，东北大学教授; 乔建忠(1964-)，男，辽宁兴城人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(61272177).

A Top-k High Utility Itemset Mining Method Based on the Index Utility

LIN Shu-kuan， WANG Xiao-cong， QIAO Jian-zhong， WANG Rui

School of Information Science & Engineering， Northeastern University， Shenyang 110819， China.

Received:2014-10-31 Revised:2014-10-31 Online:2016-01-15 Published:2016-01-08
Contact: LIN Shu-kuan
About author:-
Supported by:
-

摘要/Abstract

摘要： 已有的Top-k高效用项集挖掘为了保持向下封闭性，利用项集的事务效用代替其真实效用，使得项集效用被估计得过大，导致剪枝效果不好，挖掘效率较低.针对这一问题，提出了索引效用的概念，在此基础上建立两级索引，并进行索引剪枝，增强了挖掘中剪枝的效果，提高了Top-k高效用项集挖掘的效率；此外，通过建立效用矩阵，支持对项集效用的快速计算，进一步提高了挖掘效率.不同类型数据集上的实验验证了所提出的Top-k高效用项集挖掘方法的有效性和高效性.

关键词: 项集效用, 索引效用, Top-k高效用项集, 尾超项集, 效用矩阵

Abstract: The existing methods of Top-k high utility itemset mining substitute the transaction utilities of itemsets for their real utilities in order to keep the downward closure property. This makes the utilities of itemsets be estimated too large， resulting in bad pruning effect and low mining efficiency. To solve this problem， the concept of the index utility was proposed. On this basis， the two-level index was built and pruned， by which the pruning effect was strengthened and the efficiency of Top-k high utility itemset mining was enhanced. Moreover， the fast calculation of itemset utilities was supported by building the utility matrix. Therefore， the mining efficiency was further enhanced. The experiments on different types of datasets validate the effectiveness and the efficiency of the proposed method.

Key words: itemset utility, the index utility, Top-k high utility itemset, ending super itemset, utility matrix

中图分类号:

TP391

林树宽，王晓丛，乔建忠，王蕊. 基于索引效用的Top-k高效用项集挖掘方法[J]. 东北大学学报:自然科学版, 2016, 37(1): 24-28.

LIN Shu-kuan， WANG Xiao-cong， QIAO Jian-zhong， WANG Rui. A Top-k High Utility Itemset Mining Method Based on the Index Utility[J]. Journal of Northeastern University Natural Science, 2016, 37(1): 24-28.

参考文献

[1]Han J，Kamber M，Pei J.Data mining:concept and technique ［M］.3rd ed.Beijing:China Machine Press，2012.
[2]Brin S，Motwani R，Ullman J D，et al.Dynamic itemset counting and implication rules for market basket data［C］// Proceedings of ACM SIGMOD Conference on Management of Data.Tucson，1997:255-264.
[3]毛国君，宗东军.基于多维数据流挖掘技术的入侵检测模型与算法［J］.计算机研究与发展，2009，46(4):602-609.(Mao Guo-jun，Zong Dong-jun.An intrusion detection model based on mining multi-dimension data stream［J］.Journal of Computer Research and Development，2009，46(4):602-609.)
[4]杨欢，张玉清，胡予濮，等.基于权限频繁模式挖掘算法的Android 恶意应用检测方法［J］.通信学报，2013，34(Z1):106-115.(Yang Huan，Zhang Yu-qing，Hu Yu-pu，et al.Android malware detection method based on permission sequential pattern mining algorithm［J］.Journal on Communications，2013，34(Z1):106-115.)
[5]Agrawal R，Srikant R.Fast algorithms for mining association rules［C］// Proceedings of the 20th VLDB Conference.Santiago de Chile，1994:487-499.
[6]Agrawal R，Imielinski T，Swami A.Mining association rules between sets of items in large databases［C］// Proceedings of the ACM SIGMOD Conference on Management of Data.New York:ACM Press，1993:207-216.
[7]Pei J，Han J，Lu H，et al.H-Mine:hyper-structure mining of frequent patterns in large databases［C］// IEEE International Conference on Data Mining.Piscataway，2001:441-448.
[8]Han J，Pei J.Mining frequent patterns without candidate generation:a frequent-pattern tree approach ［J］.Data Mining and Knowledge Discovery，2004，8(1):53-87.
[9]Yao H，Hamilton H J，Geng L.A unified framework for utility-based measures for mining itemsets［C］// Proceedings of ACM SIGKDD 2nd Workshop on Utility-Based Data Mining.Philadelphia，2006:28-37.
[10]Tseng V，Wu C W，Shie B E，et al.UP-growth:an efficient algorithm for high utility itemset mining［C］// Proceedings of KDD’10.Washington DC，2010:253-263.
[11]Song W，Liu Y，Li J H.Vertical mining for high utility itemsets［C］// Proceedings of IEEE International Conference on Granular Computing.Hangzhou，2012:429-434.
[12]Liu J，Wang K，Fung B.Direct discovery of high utility itemsets without candidate generation［C］// Proceedings of ICDM’12.Brussels，2012:984-989.
[13]Lin C W，Hong T P，Lan G C，et al.Incrementally mining high utility patterns based on pre-large concept［J］.Applied Intelligence，2014，40(2):343–357.
[14]Wu C W，Shie B E.Mining top-k high utility itemsets［C］// Proceedings of KDD’12.Beijing，2012:78-86.

[1]	庞彦伟，苏畅，龙涛. 自适应构造与聚合多尺度代价体的双目立体匹配[J]. 东北大学学报（自然科学版）, 2023, 44(4): 457-468.
[2]	丁其川，王力，刘成. 融合长距离信道注意力与病理特征的肺结节分类[J]. 东北大学学报（自然科学版）, 2023, 44(4): 476-485.
[3]	李海燕，熊立昌，郭磊，李海江. 基于U-net边缘生成和超图卷积的两阶段修复算法[J]. 东北大学学报（自然科学版）, 2023, 44(3): 331-339.
[4]	杨丹，刘国如，任梦成，裴宏杨. 多尺度卷积核U-Net模型的视网膜血管分割方法[J]. 东北大学学报（自然科学版）, 2021, 42(1): 7-14.
[5]	韩东红，张宏亮，朱帅伟，齐孝龙. 面向新浪微博的情感社区检测算法[J]. 东北大学学报（自然科学版）, 2021, 42(1): 21-31.
[6]	原培新，陈鼎夫. 双能X射线高动态范围安检图像压缩算法[J]. 东北大学学报（自然科学版）, 2021, 42(1): 96-101.
[7]	魏颖, 徐楚翘, 刁兆富, 李伯群. 基于生成对抗网络的多目标行人跟踪算法[J]. 东北大学学报（自然科学版）, 2020, 41(12): 1673-1680.
[8]	李稷，徐安军. 炼钢车间多天车动态调度仿真方案[J]. 东北大学学报:自然科学版, 2020, 41(12): 1699-1707.
[9]	李占山，吕艾娜. 基于新冗余度的特征选择方法[J]. 东北大学学报:自然科学版, 2020, 41(11): 1550-1556.
[10]	王鑫，王翠荣，王聪，苑迎. 双通道多感知卷积神经网络图像超分辨率重建[J]. 东北大学学报:自然科学版, 2020, 41(11): 1564-1570.
[11]	张春雷，戴丽，刘宇，李鹤. 基于三点法和ICP算法的手术导航系统患者配准[J]. 东北大学学报:自然科学版, 2020, 41(11): 1584-1590.
[12]	陈剑，何涛，闻英友，马林涛. 基于BERT模型的司法文书实体识别方法[J]. 东北大学学报:自然科学版, 2020, 41(10): 1382-1387.
[13]	张田，田勇，王子，王昭东. 基于清晰度评价的自适应阈值图像分割法[J]. 东北大学学报:自然科学版, 2020, 41(9): 1231-1238.
[14]	张丽杰，刘建昌，谭树彬. 复杂建筑火灾中的人员疏散路径多目标规划[J]. 东北大学学报:自然科学版, 2020, 41(6): 761-766.
[15]	赵海，周冰玲，朱宏博，窦圣昶. 基于连续最大流的三维肺实质快速分割算法[J]. 东北大学学报:自然科学版, 2020, 41(4): 470-474.

基于索引效用的Top-k高效用项集挖掘方法

A Top-k High Utility Itemset Mining Method Based on the Index Utility

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价