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

doi:10.12068/j.issn.1005-3026.2016.01.006

Abstract

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

CLC Number:

TP391

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.

References

[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]	PANG Yan-wei， SU Chang， LONG Tao. Adaptive Multi-scale Cost Volume Construction and Aggregation for Stereo Matching [J]. Journal of Northeastern University(Natural Science), 2023, 44(4): 457-468.
[2]	DING Qi-chuan， WANG Li， LIU Cheng. Classification of Pulmonary Nodule by Combining Long-Distance Channel Attention and Pathological Feature [J]. Journal of Northeastern University(Natural Science), 2023, 44(4): 476-485.
[3]	LI Hai-yan， XIONG Li-chang， GUO Lei， LI Hai-jiang. Two-Stage Inpainting Algorithm Based on U-net Edge Generation and Hypergraphs Convolution [J]. Journal of Northeastern University(Natural Science), 2023, 44(3): 331-339.
[4]	YANG Dan， LIU Guo-ru， REN Meng-cheng， PEI Hong-yang. Retinal Blood Vessel Segmentation Method Based on Multi-scale Convolution Kernel U-Net Model [J]. Journal of Northeastern University(Natural Science), 2021, 42(1): 7-14.
[5]	HAN Dong-hong， ZHANG Hong-liang， ZHU Shuai-wei， QI Xiao-long. Sentiment Community Detection Algorithm for Sina Weibo [J]. Journal of Northeastern University(Natural Science), 2021, 42(1): 21-31.
[6]	YUAN Pei-xin， CHEN Ding-fu. Compression Algorithm of Dual X-ray Security Inspection Images with High Dynamic Range [J]. Journal of Northeastern University(Natural Science), 2021, 42(1): 96-101.
[7]	WEI Ying, XU Chu-qiao, DIAO Zhao-fu, LI Bo-qun. A Multi-target Pedestrian Tracking Algorithm Based on Generated Adversarial Network [J]. Journal of Northeastern University(Natural Science), 2020, 41(12): 1673-1680.
[8]	LI Ji， XU An-jun. Simulation-based Solution for Multi-crane Dynamic Scheduling in Steelmaking Shop [J]. Journal of Northeastern University Natural Science, 2020, 41(12): 1699-1707.
[9]	LI Zhan-shan， LYU Ai-na. A Feature Selection Method Based on New Redundancy Measurement [J]. Journal of Northeastern University Natural Science, 2020, 41(11): 1550-1556.
[10]	WANG Xin， WANG Cui-rong， WANG Cong， YUAN Ying. Dual-channel Multi-perception Convolutional Network for Image Super-Resolution [J]. Journal of Northeastern University Natural Science, 2020, 41(11): 1564-1570.
[11]	ZHANG Chun-lei， DAI Li， LIU Yu， LI He. Patient Registration for Surgical Navigation System Based on Three-Point Method and ICP Algorithm [J]. Journal of Northeastern University Natural Science, 2020, 41(11): 1584-1590.
[12]	CHEN Jian， HE Tao， WEN Ying-you， MA Lin-tao. Entity Recognition Method for Judicial Documents Based on BERT Model [J]. Journal of Northeastern University Natural Science, 2020, 41(10): 1382-1387.
[13]	ZHANG Tian， TIAN Yong， WANG Zi， WANG Zhao-dong. Adaptive Threshold Image Segmentation Based on Definition Evaluation [J]. Journal of Northeastern University Natural Science, 2020, 41(9): 1231-1238.
[14]	ZHANG Li-jie， LIU Jian-chang， TAN Shu-bin. Multi-objective Planning of Personnel Evacuation Route in Complex Building Fire [J]. Journal of Northeastern University Natural Science, 2020, 41(6): 761-766.
[15]	ZHAO Hai， ZHOU Bing-ling， ZHU Hong-bo， DOU Sheng-chang. Fast Segmentation Algorithm of 3D Lung Parenchyma Based on Continuous Max-Flow [J]. Journal of Northeastern University Natural Science, 2020, 41(4): 470-474.