增量数据上的闭合定量高效用项集挖掘算法

doi:10.11772/j.issn.1001-9081.2022091333

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (7): 2049-2056.DOI: 10.11772/j.issn.1001-9081.2022091333

• 第39届CCF中国数据库学术会议(NDBC 2022) • 上一篇

增量数据上的闭合定量高效用项集挖掘算法

单芝慧, 韩萌(), 韩强

北方民族大学计算机科学与工程学院，银川 750021

收稿日期:2022-09-08 修回日期:2022-10-24 接受日期:2022-11-04 发布日期:2023-07-20 出版日期:2023-07-10
通讯作者: 韩萌
作者简介:单芝慧（1996—），女，河南周口人，硕士研究生，CCF会员，主要研究方向：模式挖掘；
韩萌（1982—），女，河南商丘人，教授，博士，CCF会员，主要研究方向：数据挖掘；
韩强（1973—），男，黑龙江阿城人，教授，博士，CCF会员，主要研究方向：工作流技术、可信软件。
基金资助:
国家自然科学基金资助项目(62062004);宁夏自然科学基金资助项目(2020AAC03216)

Closed high utility quantitative itemset mining algorithm on incremental data

Zhihui SHAN, Meng HAN(), Qiang HAN

School of Computer Science and Engineering，North Minzu University，Yinchuan Ningxia 750021，China

Received:2022-09-08 Revised:2022-10-24 Accepted:2022-11-04 Online:2023-07-20 Published:2023-07-10
Contact: Meng HAN
About author:SHAN Zhihui， born in 1996， M. S. candidate. Her research interests include pattern mining.
HAN Meng， born in 1982， Ph. D.， professor. Her research interests include data mining.
HAN Qiang， born in 1973， Ph. D.， professor. His research interests include workflow technology， trusted software.
Supported by:
National Natural Science Foundation of China(62062004);Natural Science Foundation of Ningxia(2020AAC03216)

摘要/Abstract

摘要：

高效用项集（HUI）挖掘能够提供数据集中高利润的项的组合信息，有利于在现实应用中制定有效的营销策略。然而，HUI仅提供项集及其总效用，不提供单个项的购买数量，而现实场景中项的数量能提供更精准的信息。因此，研究者提出定量高效用项集（HUQI）挖掘算法。针对当前的HUQI挖掘算法仅能处理静态数据且存在结果集冗余的问题，提出增量更新的定量效用列表结构来存储并更新数据集中项的效用信息，并基于该结构提出一种挖掘闭合定量高效用项集（CHUQI）的算法。将所提出的算法与FHUQI-Miner （Faster High Utility Quantitative Itemset Miner）算法在结果集数量、最小效用阈值、批次数目以及可扩展性上对比时间与内存消耗。实验结果表明，所提算法能够有效处理增量数据，挖掘出更有趣的项集。

关键词: 增量挖掘, 高效用项集, 定量高效用项集, 闭合高效用项集, 效用列表

Abstract:

High Utility Itemset （HUI） mining can provide information about the combination of highly profitable items in a dataset， which is useful for developing effective marketing strategies in real-world applications. However， HUIs only provide the itemsets and their total utility， not the purchased numbers of individual items， and the numbers of items in a real scenarios provide more precise accurate information. Therefore， High Utility Quantitative Itemset （HUQI） mining algorithms have been proposed by researchers. Focusing on the issue that the current HUQI mining algorithms can only process static data and have the problem of redundant resultsets， an incrementally updated quantitative utility list structure was proposed for storing and updating the utility information of items in the dataset， and based on this structure， an algorithm for mining Closed High Utility Quantitative Itemset （CHUQI） was proposed. The time and memory consumption of the proposed algorithm was compared with that of Faster High Utility Quantitative Itemset Miner （FHUQI-Miner） algorithm in terms of the number of result sets， minimum utility threshold， number of batches， and scalability. Experimental results show that the proposed algorithm can process incremental data effectively and mine more interesting itemsets.

Key words: incremental mining, High Utility Itemset (HUI), High Utility Quantitative Itemset (HUQI), Closed High Utility Itemset (CHUI), utility list

中图分类号:

TP301.6

单芝慧, 韩萌, 韩强. 增量数据上的闭合定量高效用项集挖掘算法[J]. 计算机应用, 2023, 43(7): 2049-2056.

Zhihui SHAN, Meng HAN, Qiang HAN. Closed high utility quantitative itemset mining algorithm on incremental data[J]. Journal of Computer Applications, 2023, 43(7): 2049-2056.

图/表 13

参考文献 27

1	AGRAWAL R， SRIKANT R. Fast algorithm for mining association rules in large databases ［C］// Proceedings of 20th International Conference on Very Large Data Bases. San Francisco： Morgan Kaufmann Publishers Inc.， 1994： 487-499.
2	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 2014 International Symposium On Methodologies for Intelligent Systems， LNCS 8502. Cham： Springer， 2014： 83-92.
3	FOURNIER-VIGER P， ZIDA S， LIN J C W， et al. EFIM-Closed： fast and memory efficient discovery of closed high-utility itemsets ［C］// Proceedings of the 2016 International Conference on Machine Learning and Data Mining in Pattern Recognition， LNCS 9729. Cham： Springer， 2016： 199-213.
4	FOURNIER-VIGER P. FHN： efficient mining of high-utility itemsets with negative unit profits ［C］// Proceedings of the 2014 International Conference on Advanced Data Mining and Applications， LNCS 8933. Cham： Springer， 2014： 16-29.
5	吴倩，王林平，罗相洲，等. 一种快速挖掘top-k高效用模式的算法［J］. 计算机应用研究， 2017， 34 （11）： 3303-3307. 10.3969/j.issn.1001-3695.2017.11.023
	WU Q， WANG L P， LUO X Z， et al. Algorithm for fast discovery of top-k high utility patterns［J］. Application Research of Computers， 2017， 34 （11）： 3303-3307. 10.3969/j.issn.1001-3695.2017.11.023
6	唐辉军，王乐，樊成立. 基于模式增长的高效用序列模式挖掘算法［J］. 自动化学报， 2021， 47 （4）： 943-954.
	TANG H J， WANG L， PAN C L. A new algorithm for mining high utility sequential patterns based on pattern-growth［J］. Acta Automatica Sinica， 2021， 47 （4）： 943-954.
7	YEN S J， LEE Y S. Mining high utility quantitative association rules ［C］// Proceedings of the 2007 International Conference on Data Warehousing and Knowledge Discovery， LNCS 4654. Berlin： Springer， 2007： 283-292.
8	LI C H， WU C W， TSENG V S. Efficient vertical mining of high utility quantitative itemsets ［C］// Proceedings of the 2014 IEEE International Conference on Granular Computing. Piscataway： IEEE， 2014： 155-160. 10.1109/grc.2014.6982826
9	LI C H， WU C W， HUANG J T， et al. An efficient algorithm for mining high utility quantitative itemsets ［C］// Proceedings of the 2019 International Conference on Data Mining Workshops. Piscataway： IEEE， 2019： 1005-1012. 10.1109/icdmw.2019.00145
10	NOUIOUA M， FOURNIER-VIGER P， WU C W， et al. FHUQI-Miner： fast high utility quantitative itemset mining［J］. Applied Intelligence， 2021， 51 （10）： 6785-6809. 10.1007/s10489-021-02204-w
11	TUNG N T， NGUYEN L T T， NGUYEN T D D， et al. Efficient mining of cross-level high-utility itemsets in taxonomy quantitative databases［J］. Information Sciences， 2022， 587： 41-62. 10.1016/j.ins.2021.12.017
12	CHEN L L， GAN W S， LIN Q， et al. OHUQI： mining on-shelf high-utility quantitative itemsets［J］. The Journal of Supercomputing， 2022， 78 （6）： 8321-8345. 10.1007/s11227-021-04218-0
13	单芝慧，韩萌，韩强. 动态数据上的高效用模式挖掘综述［J］. 计算机应用， 2022， 42 （1）： 94-108. 10.11772/j.issn.1001-9081.2021071290
	SHAN Z H， HAN M， HAN Q. Survey of high utility pattern mining on dynamic data［J］. Journal of Computer Application， 2022， 42 （1）： 94-108. 10.11772/j.issn.1001-9081.2021071290
14	YUN U， NAM H， LEE G， et al. Efficient approach for incremental high utility pattern mining with indexed list structure［J］. Future Generation Computer Systems， 2019， 95： 221-239. 10.1016/j.future.2018.12.029
15	TSAI P S M. Mining high utility itemsets in data streams based on the weighted sliding window model［J］. International Journal of Data Mining and Knowledge Management Process， 2014， 4 （2）： 13-28. 10.5121/ijdkp.2014.4202
16	DAM T L， RAMAMPIARO H， NØRVÅG K， et al. Towards efficiently mining closed high utility itemsets from incremental databases［J］. Knowledge-Based Systems， 2019， 165： 13-29. 10.1016/j.knosys.2018.11.019
17	NOUIOUA M， FOURNIER-VIGER P， QU J F， et al. CHUQI-Miner： mining correlated quantitative high utility itemsets ［C］// Proceedings of the 2021 International Conference on Data Mining Workshops. Piscataway： IEEE， 2021： 599-606. 10.1109/icdmw53433.2021.00079
18	TSENG V S， WU C W， FOURNIER-VIGER P， 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. 10.1109/tkde.2014.2345377
19	DAM T L， LI K L， FOURNIER-VIGER P， et al. CLS-Miner： efficient and effective closed high-utility itemset mining［J］. Frontiers of Computer Science， 2019， 13 （2）： 357-381. 10.1007/s11704-016-6245-4
20	NGUYEN L T T， VU V V， LAM M T H， et al. An efficient method for mining high utility closed itemsets［J］. Information Sciences， 2019， 495： 78-99. 10.1016/j.ins.2019.05.006
21	程浩东，韩萌，张妮，等. 基于滑动窗口模型的数据流闭合高效用项集挖掘［J］. 计算机研究与发展， 2021， 58 （11）： 2500-2514. 10.7544/issn1000-1239.2021.20200554
	CHENG H D， HAN M， ZHANG N， et al. Closed high utility itemsets mining over data stream based on sliding window model［J］. Journal of Computer Research and Development， 2021， 58 （11）： 2500-2514. 10.7544/issn1000-1239.2021.20200554
22	HONG T P， LEE C H， WANG S L. An incremental mining algorithm for high average-utility itemsets ［C］// Proceedings of the 10th International Symposium on Pervasive Systems， Algorithms， and Networks. Piscataway： IEEE， 2009： 421-425. 10.1109/i-span.2009.24
23	AHMED C F， TANBEER S K， JEONG B S， et al. Mining high utility patterns in incremental databases ［C］// Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication. New York： ACM， 2009： 656-663. 10.1145/1516241.1516357
24	SONG W， LIU Y， LI J H. Mining high utility itemsets by dynamically pruning the tree structure［J］. Applied Intelligence， 2014， 40 （1）： 29-43. 10.1007/s10489-013-0443-7
25	LIN J C W， GAN W S， HONG T P， et al. Incrementally updating high-utility itemsets with transaction insertion ［C］// Proceedings of the 2014 International Conference on Advanced Data Mining and Applications， LNCS 8933. Cham： Springer， 2014： 44-56.
26	NGUYEN L T T， VU D B， NGUYEN T D D， et al. Mining maximal high utility itemsets on dynamic profit databases［J］. Cybernetics and Systems， 2020， 51 （2）： 140-160. 10.1080/01969722.2019.1705549
27	FOURNIER-VIGER P， GOMARIZ A， GUENICHE T， et al. SPMF： a Java open-source pattern mining library［J］. Journal of Machine Learning Research， 2014， 15： 3569-3573.

数据集	事务标识符	事务
D₁	T₁	（a， 2）（c， 7）（h， 4）
	T₂	（a， 3）（c， 8）
	T₃	（a， 2）（b， 1）（c， 7）（g， 7）（h， 4）
D₂	T₄	（b， 2）（c， 9）（g， 8）（h， 5）
D₃	T₅	（a， 2）（d， 5）（e， 1）（f， 1）
D₄	T₆	（a， 3）（b， 2）（c， 3）（d， 1）（e， 2）

数据集	事务标识符	事务
D₁	T₁	（a， 2）（c， 7）（h， 4）
	T₂	（a， 3）（c， 8）
	T₃	（a， 2）（b， 1）（c， 7）（g， 7）（h， 4）
D₂	T₄	（b， 2）（c， 9）（g， 8）（h， 5）
D₃	T₅	（a， 2）（d， 5）（e， 1）（f， 1）
D₄	T₆	（a， 3）（b， 2）（c， 3）（d， 1）（e， 2）

（a， 2）	TWU：1 976
TID	IutilD	RutilD	IutilN	RutilN
T₁			40	0
T₃			40	15

（a， 2）	TWU：1 976
TID	IutilD	RutilD	IutilN	RutilN
T₁			40	0
T₃			40	15

（a， 2）	TWU：2 397
TID	IutilD	RutilD	IutilN	RutilN
T₁	40	0
T₃	40	15
T₅			40	11

增量数据上的闭合定量高效用项集挖掘算法

Closed high utility quantitative itemset mining algorithm on incremental data

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 27

相关文章 4

编辑推荐

Metrics

名称	事务数	项数	事务平均长度	类型
Foodmart	4 141	1 559	4.42	稀疏
BMS	59 601	497	2.42	稀疏
Connect	67 557	129	43.00	密集
Pumsb	49 046	2 113	74.00	密集
T20I6D100k	99 922	893	19.90	密集

[1]	高智慧, 韩萌, 刘淑娟, 李昂, 穆栋梁. 基于智能优化算法的高效用项集挖掘方法综述[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1676-1686.
[2]	袁泉, 唐成亮, 徐雲鹏. 基于长度约束的蝙蝠高效用项集挖掘算法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1473-1480.
[3]	荀亚玲, 王林青, 蔡江辉, 杨海峰. 基于多尺度的时序数据部分周期模式增量挖掘[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 391-397.
[4]	孙蕊, 韩萌, 张春砚, 申明尧, 杜诗语. 含负项top-k高效用项集挖掘算法[J]. 计算机应用, 2021, 41(8): 2386-2395.

项	外部效用	项	外部效用
a	20	e	11
b	15	f	100
c	70	g	75
d	54	h	47

项	外部效用	项	外部效用
a	20	e	11
b	15	f	100
c	70	g	75
d	54	h	47