PHUI-GA: GPU-based efficiency evolutionary algorithm for mining high utility itemsets

doi:10.23919/JSEE.2024.000020

Journal of Systems Engineering and Electronics ›› 2024, Vol. 35 ›› Issue (4): 965-975.doi: 10.23919/JSEE.2024.000020

• SYSTEMS ENGINEERING • Previous Articles

PHUI-GA: GPU-based efficiency evolutionary algorithm for mining high utility itemsets

Haipeng JIANG¹(), Guoqing WU²^,³(), Mengdan SUN²^,³(), Feng LI²(), Yunfei SUN⁴(), Wei FANG¹^,*()

¹ Jiangsu Provincial Engineering Laboratory of Pattern Recognition and Computational Intelligence, Department of Computer Science and Technology, Jiangnan University, Wuxi 214122, China
² China Ship Scientific Research Center, Wuxi 214082, China
³ Taihu Laboratory of Deepsea Technological Science, Wuxi 214082, China
⁴ Department of Mathematics, Nanjing University, Nanjing 210023, China

Received:2022-12-21 Online:2024-08-18 Published:2024-08-06
Contact: Wei FANG E-mail:6201924093@stu.jiangnan.edu.cn;www.lotems702@cssrc.com.cn;sunmengdan702@cssrc.com.cn;lifeng@cssrc.com.cn;201840049@smail.nju.edu.cn;fangwei@jiangnan.edu.cn
About author:
JIANG Haipeng was born in 1994. He received his bachelor degree from Jiangnan University, China, in 2020. He is a master student in School of Artificial Intelligence and Computer Science, Jiangnan University. His research interest is high utility itemsets mining based on evolutionary algorithms. E-mail: 6201924093@stu.jiangnan.edu.cn

WU Guoqing was born in 1984. He received his bachelor degree in automation from China University of Mining and Technology, China, in 2007, master’s degree in detection technology and automatic equipment from China University of Mining and Technology, China, in 2010. He then joined China Ship Scientific Research Center, where he has been a senior engineer since 2017. His main research interests include deep-sea equipment test and underwater optical testing technology. E-mail: www.lotems702@cssrc.com.cn

SUN Mengdan was born in 1995. She received her bachelor degree in mechanical engineering from Shandong University, and master degree in information technology from Monash University in 2021. After graduation, she joined China Ship Scientific Research Center. Her research interests are data analysis and big data processing. E-mail: sunmengdan702@cssrc.com.cn

LI Feng was born in 1979. He received his bachelor degree in computer Science from Henan University, China, in 2002, and Ph.D. degree from Jiangnan University, China, in 2008. He is now a senior expert in China Ship Scientific Research Center, China. His main research interests include experimental informatization and industrial software. E-mail: lifeng@cssrc.com.cn

SUN Yunfei was born in 2001. He is an under graduate in Department of Mathematics, Nanjing University. His research interest is data mining based on evolutionary algorithms. E-mail: 201840049@smail.nju.edu.cn

FANG Wei was born in 1980. He received his Ph.D. degree in Jiangnan University in 2008. He is now a professor of Jiangsu Provincial Engineering Laboratory of Pattern Recognition and Computational Intelligence, Jiangnan University. His research interests are evolutionary algorithm and its applications. E-mail: fangwei@jiangnan.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China(62073155;62002137;62106088;62206113), the High-End Foreign Expert Recruitment Plan (G2023144007L), and the Fundamental Research Funds for the Central Universities(JUSRP221028).

Abstract

Abstract:

Evolutionary algorithms (EAs) have been used in high utility itemset mining (HUIM) to address the problem of discovering high utility itemsets (HUIs) in the exponential search space. EAs have good running and mining performance, but they still require huge computational resource and may miss many HUIs. Due to the good combination of EA and graphics processing unit (GPU), we propose a parallel genetic algorithm (GA) based on the platform of GPU for mining HUIM (PHUI-GA). The evolution steps with improvements are performed in central processing unit (CPU) and the CPU intensive steps are sent to GPU to evaluate with multi-threaded processors. Experiments show that the mining performance of PHUI-GA outperforms the existing EAs. When mining 90% HUIs, the PHUI-GA is up to 188 times better than the existing EAs and up to 36 times better than the CPU parallel approach.

Key words: high utility itemset mining (HUIM), graphics processing unit (GPU) parallel, genetic algorithm (GA), mining performance

Haipeng JIANG, Guoqing WU, Mengdan SUN, Feng LI, Yunfei SUN, Wei FANG. PHUI-GA: GPU-based efficiency evolutionary algorithm for mining high utility itemsets[J]. Journal of Systems Engineering and Electronics, 2024, 35(4): 965-975.

Figures/Tables 11

Table 1

Table 2

Fig 1

Fig 2

Fig 3

Fig 4

Table 3

Fig 5

Fig 6

Fig 7

Table 4

References 36

1	SINGH K, KUMAR R, BISWAS B High average-utility itemsets mining: a survey. Applied Intelligence, 2022, 52 (4): 3901- 3938. doi: 10.1007/s10489-021-02611-z
2	JANGRA S, TOSHNIWAL D Efficient algorithms for victim item selection in privacy-preserving utility mining. Future Generation Computer Systems, 2022, 128, 219- 234. doi: 10.1016/j.future.2021.10.008
3	LIN C W, HONG T P, LU W H An effective tree structure for mining high utility itemsets. Expert Systems with Applications, 2011, 38 (6): 7419- 7424. doi: 10.1016/j.eswa.2010.12.082
4	KHEIROLLAHI H, CHAHARDOWLI M, SIMJOO M A new method of well clustering and association rule mining. Journal of Petroleum Science and Engineering, 2022, 214, 110479. doi: 10.1016/j.petrol.2022.110479
5	BICER M, INDICTOR D, YANG R, et al Efficient implementations for UWEP incremental frequent itemset mining algorithm. International Journal of Applied Logistics, 2021, 11 (1): 18- 37. doi: 10.4018/IJAL.2021010102
6	WU P, NIU X Z, FOURNIER-VIGER P, et al UBP-Miner: an efficient bit based high utility itemset mining algorithm. Knowledge-Based Systems, 2022, 248, 108865. doi: 10.1016/j.knosys.2022.108865
7	FOUAD M A, HUSSEIN W, RADY S, et al An efficient approach for mining reliable high utility patterns. IEEE Access, 2022, 10, 1419- 1431.
8	LEE D, NAM K, HAN I, et al From free to fee: monetizing digital content through expected utility-based recommender systems. Information & Management, 2022, 59 (6): 103681.
9	SETHI K K, RAMESH D, RATHORE A, et al. HUIM-SMP: high utility itemset mining based stock market analogy. Proc. of the 10th International Conference on Computing, Communication and Networking Technologies, 2019. DOI: 10.1109/ICCCNT45670.2019.8944752.
10	KRISHNA G J, RAVI V High utility itemset mining using binary differential evolution: an application to customer segmentation. Expert Systems with Applications, 2021, 181, 115122. doi: 10.1016/j.eswa.2021.115122
11	NOUIOUA M, FOURNIER-VIGER P, GAN W S, et al. TKQ: top-K quantitative high utility itemset mining. Proc. of the Advanced Data Mining and Applications, 2022: 16−28.
12	LE B, TRUONG T, DUONG H, et al H-FHAUI: hiding frequent high average utility itemsets. Information Sciences, 2022, 611, 408- 431. doi: 10.1016/j.ins.2022.07.027
13	HUYNH U, LE B, DINH D T, et al Multi-core parallel algorithms for hiding high-utility sequential patterns. Knowledge-Based Systems, 2022, 237, 107793. doi: 10.1016/j.knosys.2021.107793
14	LIN J C W, GAN W, FOURNIER-VIGER P, et al High utility-itemset mining and privacy-preserving utility mining. Perspectives in Science, 2016, 7, 74- 80. doi: 10.1016/j.pisc.2015.11.013
15	LIU Y W, WANG L, FENG L, et al. Mining high utility itemsets based on pattern growth without candidate generation. Mathematics, 2021, 9(1): 35.
16	AHMED C F, TANBEER S K, JEONG B S, et al. Efficient tree structures for high utility pattern mining in incremental databases. IEEE Trans. on Knowledge and Data Engineering, 2009, 21: 1708−1721.
17	DUONG Q H, FOURNIER-VIGER P, RAMAMPIARO H, et al Efficint high utility itemset mining using buffered utility-lists. Applied Intelligence, 2018, 48 (7): 1859- 1877. doi: 10.1007/s10489-017-1057-2
18	NAWAZ M S, FOURNIER-VIGER P, YUN U, et al Mining high utility itemsets with hill climbing and simulated annealing. ACM Transactions on Management Information System, 2021, 13 (1): 1- 22.
19	CHEN Y, AN A J Approximate parallel high utility itemset mining. Big Data Research, 2016, 6, 26- 42. doi: 10.1016/j.bdr.2016.07.001
20	SETHI K K, RAMESH D, EDLA D R P-FHM+: parallel high utility itemset mining algorithm for big data processing. Procedia Computer Science, 2018, 132, 918- 927. doi: 10.1016/j.procs.2018.05.107
21	LIU J Q, ZHAO R, YANG X C, et al. Efficient parallel algorithm for mining high utility patterns based on spark. Proc. of the IEEE Fourth International Conference on Data Science in Cyberspace, 2019: 367−372.
22	KANNIMUTHU S, PREMALATHA K Discovery of high utility itemsets using genetic algorithm with ranked mutation. Applied Artificial Intelligence, 2014, 28 (4): 337- 359. doi: 10.1080/08839514.2014.891839
23	LIN J C-W, YANG L, FOURNIER-VIGER P, et al Mining high-utility itemsets based on particle swarm optimization. Engineering Applications of Artificial Intelligence, 2016, 55, 320- 330. doi: 10.1016/j.engappai.2016.07.006
24	LIN J C W, YANG L, FOURNIER-VIGER P, et al A binary PSO approach to mine high-utility itemsets. Soft Computing, 2017, 21 (17): 5103- 5121. doi: 10.1007/s00500-016-2106-1
25	SONG W, HUANG C M. Discovering high utility itemsets based on the artificial bee colony algorithm. Proc. of the Advances in Knowledge Discovery and Data Mining, 2018: 3−14.
26	HERAGUEMI K E, KAMEL N, DRIAS H Association rule mining based on bat algorithm. Journal of Computational and Theoretical Nanoscience, 2015, 12 (7): 1195- 1200.
27	SONG W, NAN J K. Mining high utility itemsets using ant colony optimization. Proc. of the Advances in Natural Computation, Fuzzy Systems and Knowledge Discovery, 2020: 98−107.
28	SONG W, LI J Y, HUANG C W. Artificial fish swarm algorithm for mining high utility itemsets. Proc. of the Advances in Swarm Intelligence, 2021: 407−419.
29	SONG W, HUANG C M Mining high utility itemsets using bio-inspired algorithms: a diverse optimal value framework. IEEE Access, 2018, 6, 19568- 19582. doi: 10.1109/ACCESS.2018.2819162
30	ZHANG Q, FANG W, SUN J, et al Improved genetic algorithm for high-utility itemset mining. IEEE Access, 2019, 7, 176799- 176813. doi: 10.1109/ACCESS.2019.2958150
31	ZIDA S, FOURNIER-VIGER P, LIN J C W, et al. EFIM: a highly efficient algorithm for high-utility itemset mining. Proc. of the Advances in Artificial Intelligence and Soft Computing, 2015: 530−546.
32	SONG W, LI J Y. Discovering high utility itemsets using set-based particle swarm optimization. Proc. of the International Conference on Advanced Data Mining and Applications, 2022: 38−53.
33	DJENOURI Y, DJENOURI D, BELHADI A, et al Exploiting GPU and cluster parallelism in single scan frequent itemset mining. Information Sciences, 2019, 496, 363- 377. doi: 10.1016/j.ins.2018.07.020
34	DJENOURI Y, DJENOURI D, BELHADI A, et al Exploiting GPU parallelism in improving bees swarm optimization for mining big transactional databases. Information Sciences, 2019, 496, 326- 342. doi: 10.1016/j.ins.2018.06.060
35	DJENOURI Y, BENDJOUDI A, MEHI M, et al GPU-based bees swarm optimization for association rules mining. The Journal of Supercomputing, 2015, 71 (4): 1318- 1344. doi: 10.1007/s11227-014-1366-8
36	SAFARI M, HUISMAN M Formal verification of parallel prefix sum and stream compaction algorithms in CUDA. Theoretical Computer Science, 2022, 912, 81- 98. doi: 10.1016/j.tcs.2022.02.027

D	Transaction	TU
T₁	(a, 1) (b, 1)	5
T₂	(c, 2)	2
T₃	(b, 1), (e, 1), (f, 1)	9
T₄	(d, 3), (e, 1)	14
T₅	(a, 1), (b, 1), (c, 1), (d, 1), (e, 1), (f, 1)	17
T₆	(a, 4), (c, 1)	13

Dataset	Item	Transaction	Density/%
Chess	76	3196	49.33
Mushroom	119	8124	19.33
Connect	469	34018	7.22
Accidents_10%	130	67557	33.33

Dataset	Minimum utility	PHUI-GA/s	HUIM-IGA/s	Accelerate ratio/%	HUIF-PSO/s	Accelerate ratio/%	PHUI-Miner/s	Accelerate ratio/%
Chess	60 W	0.32	5.59	17.46	12.10	37.81	8.70	27.19
	59 W	0.38	10.40	27.36	18.90	49.73	9.68	25.47
	59 W	0.56	17.80	31.78	28.80	51.42	9.82	17.54
	57 W	0.79	27.56	34.88	57	72.15	10.50	13.29
	56 W	1.07	41.20	38.50	102	95.32	11.10	10.37
Mushroom	46 W	0.52	3.98	7.65	8.20	15.76	6.80	13.08
	45 W	0.70	4.2	6	10.70	15.28	7.10	10.14
	44 W	1.03	4.8	4.66	16.44	15.96	7.20	6.99
	43 W	1.53	7.7	5.03	21	13.72	7.35	4.80
	42 W	2.58	13.6	5.27	28	10.85	7.50	2.91
Accident_10%	250 W	1.47	30	20.41	31	21.08	20.95	14.25
	240 W	2.17	46	21.19	62	28.57	21.74	10.02
	230 W	3.10	72	23.22	214	69.03	23.50	7.58
	220 W	3.75	90	24	300	80	26.60	7.09
	210 W	5.0	149	29.8	477	95.4	27.50	5.50
Connect	1600 W	3.36	216	64.28	518	154.16	123.00	36.61
	1590 W	4.10	246	60	572	139.51	135.00	32.93
	1580 W	5.00	410	82	965	193	152.00	30.40
	1570 W	6.40	480	75	1148	179.37	162.00	25.31
	1560 W	8.31	632	76.05	1564	188.20	198.00	26.40

[1]	Hui CAO, Fuhai DUAN, Yu’nan DUAN. Reliability-based selective maintenance for redundant systems with dependent performance characteristics of components [J]. Journal of Systems Engineering and Electronics, 2023, 34(3): 804-814.
[2]	Jianwei SUN, Chao WANG, Qingzhan SHI, Wenbo REN, Zekun YAO, Naichang YUAN. Intelligent optimization methods of phase-modulation waveform [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 916-923.
[3]	Yongbin YU, Chenyu YANG, Quanxin DENG, Tashi NYIMA, Shouyi LIANG, Chen ZHOU. Memristive network-based genetic algorithm and its application to image edge detection [J]. Journal of Systems Engineering and Electronics, 2021, 32(5): 1062-1070.
[4]	Amir ZAHEDI, Bijan ABBASI ARAND. GA-based approach to phase compensation of large phased array antennas [J]. Journal of Systems Engineering and Electronics, 2018, 29(4): 723-730.
[5]	Jun Li, Hao Chen, Zhinong Zhong, Ning Jing, and Jiangjiang Wu. Method for electromagnetic detection satellites scheduling based on genetic algorithm with alterable penalty coefficient [J]. Journal of Systems Engineering and Electronics, 2014, 25(5): 822-832.
[6]	Guo Wei, Xudong Yu, and Xingwu Long. Novel approach for identifying Z-axis drift of RLG based on GA-SVR model [J]. Journal of Systems Engineering and Electronics, 2014, 25(1): 115-121.
[7]	Bin Suo, Yongsheng Cheng, Chao Zeng, and Jun Li. Computational intelligence approach for uncertainty quantification using evidence theory [J]. Journal of Systems Engineering and Electronics, 2013, 24(2): 250-260.
[8]	Hao Yuan, Dan Song, Qiangfeng Zhou, and Huaping Xu. Worst-case tolerance analysis on array antenna based on chaos-genetic algorithm [J]. Journal of Systems Engineering and Electronics, 2012, 23(6): 824-830.
[9]	Zhongzhao Zhang, Zhun Ye, and Weilin Jiang. Optimal antenna placement in distributed antenna systems [J]. Journal of Systems Engineering and Electronics, 2012, 23(4): 467-472.
[10]	Qunming Wang, Liguo Wang, and Danfeng Liu. Integration of spatial attractions between and within pixels for sub-pixel mapping [J]. Journal of Systems Engineering and Electronics, 2012, 23(2): 293-303.
[11]	Tianran Zhou, Huagang Xiong, and Zhen Zhang. Hierarchical resource allocation for integrated modular avionics systems [J]. Journal of Systems Engineering and Electronics, 2011, 22(5): 780-787.
[12]	Kezong Tang, Jingyu Yang, Haiyan Chen, and Shang Gao. Improved genetic algorithm for nonlinear programming problems [J]. Journal of Systems Engineering and Electronics, 2011, 22(3): 540-546.
[13]	Tao Haihong, Liao Guisheng & Yu Jiang. Space-borne antenna adaptive anti-jamming method based on gradient-genetic algorithm [J]. Journal of Systems Engineering and Electronics, 2007, 18(3): 469-475.

PHUI-GA: GPU-based efficiency evolutionary algorithm for mining high utility itemsets

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 11

References 36

Related Articles 13

Recommended Articles

Metrics

Comments

Item	Utility
a	3
b	2
c	1
d	4
e	2
f	5