An Efficient Implementation Method of the Apriori Algorithm and its Application

doi:10.12422/j.issn.1672-6952.2023.02.013

Abstract

Abstract:

Aiming at the low efficiency of Apriori algorithm in scanning database and low dimensional frequent itemset, an efficient implementation method of Apriori algorithm was proposed, which is called EI_Apriori algorithm. This method utilizes the vector?based storage structure and pre?pruning to reduce the number of scanning databases and low?dimensional frequent itemsets and thus improves the efficiency of the Apriori algorithm. According to the actual situation of student achievement analysis, the constraints on the sequence relationship between courses are added in the association rule mining, and the constraints on the score level range are added in the association rules. The adjusted EI_Apriori algorithm was applied in score association analysis. The results show that the EI_Apriori algorithm can accurately find the association rules that meet the real needs, which proves the superiority of EI_Apriori algorithm.

Key words: Association analysis, Reform in education, Data mining, Apriori algorithm, Association rules

摘要：

针对Apriori算法在扫描数据库和低维频繁项集时效率较低的问题，提出了一种基于Apriori算法的高效实现方法EI_Apriori算法。该方法基于向量的存储结构和预剪枝，降低了扫描数据库和低维频繁项集的次数，进而提高了Apriori算法的效率。根据学生成绩分析的实际情况，在关联规则挖掘中增加了课程间先后关系的约束，在关联规则中增加了对成绩等级区间的约束，将调整后的EI_Apriori算法在成绩关联分析中进行了应用。结果表明，EI_Apriori算法能精确地找到符合现实需求的关联规则，证明了EI_Apriori算法的优越性。

关键词: 关联分析, 教学改革, 数据挖掘, Apriori算法, 关联规则

CLC Number:

TP391

Chunxu Wu, Yinshan Jia, Hongfei Yu. An Efficient Implementation Method of the Apriori Algorithm and its Application[J]. Journal of Liaoning Petrochemical University, 2023, 43(2): 78-85.

吴春旭, 贾银山, 于红绯. 一种Apriori算法的高效实现方法及其应用[J]. 辽宁石油化工大学学报, 2023, 43(2): 78-85.

Figures/Tables 10

TID	项集	TID	项集
T1	A,B,E	T6	B,C
T2	B,D	T7	A,C
T3	B,C	T8	A,B,C
T4	A,B	T9	A,B,C,E
T5	A,C

项集	事务向量	内积
A	1 0 0 1 1 0 1 1 1	6
B	1 1 1 1 0 1 0 1 1	7
C	0 0 1 0 1 1 1 1 1	6
D	0 1 0 0 0 0 0 0 0	1（删除）
E	1 0 0 0 0 0 0 0 1	2

项集	项的标志	事务向量	内积
A，B	1	1 0 0 1 0 0 0 1 1	4
A，C	1	0 0 0 0 1 0 1 1 1	4
A，E	1	1 0 0 0 0 0 0 0 1	4
B，C	1	0 0 1 0 0 1 0 1 1	4
B，E	1	1 0 0 0 0 0 0 0 1	2
C，E	0	0 0 0 0 0 0 0 0 1	1(删除)

编号	成绩
编号	高等数学1	高等数学2	概率论	线性代数
1	77	73	90	80
2	64	66	73	70
3	64	64	87	76
4	83	71	69	73
5	83	78	79	90

编号	关联规则	置信度
1	高等数学1：Ⅱ $\Rightarrow$ 概率论：Ⅰ	0.717 2
2	高等数学2：Ⅲ $\Rightarrow$ 概率论：Ⅲ	0.578 7
3	概率论：Ⅱ $\Rightarrow$ 线性代数：Ⅰ	0.731 1
4	高等数学1：Ⅴ $\Rightarrow$ 线性代数：Ⅴ	0.516 7
5	高等数学2：Ⅲ $\Rightarrow$ 线性代数：Ⅱ	0.534 7
6	概率论：Ⅴ $\Rightarrow$ 线性代数：Ⅴ	0.651 4
7	高等数学1：Ⅴ $\Rightarrow$ 高等数学2：Ⅴ	0.785 7
8	高等数学1：Ⅰ，高等数学2：Ⅱ $\Rightarrow$ 线性代数：Ⅰ	0.546 1
9	高等数学1：Ⅲ，高等数学2：Ⅳ $\Rightarrow$ 线性代数：Ⅲ	0.534 6
10	高等数学1：Ⅱ，高等数学2：Ⅳ $\Rightarrow$ 概率论：Ⅱ	0.715 2

编号	关联规则	置信度
1	高等数学1：Ⅱ $\Rightarrow$ 概率论：Ⅰ	0.717 2
2	高等数学2：Ⅲ $\Rightarrow$ 概率论：Ⅲ	0.578 7
3	概率论：Ⅱ $\Rightarrow$ 线性代数：Ⅰ	0.731 1
4	高等数学1：Ⅴ $\Rightarrow$ 线性代数：Ⅴ	0.516 7
5	高等数学2：Ⅲ $\Rightarrow$ 线性代数：Ⅱ	0.534 7
6	概率论：Ⅴ $\Rightarrow$ 线性代数：Ⅴ	0.651 4
7	高等数学1：Ⅴ $\Rightarrow$ 高等数学2：Ⅴ	0.785 7
8	高等数学1：Ⅰ，高等数学2：Ⅱ $\Rightarrow$ 线性代数：Ⅰ	0.546 1
9	高等数学1：Ⅲ，高等数学2：Ⅳ $\Rightarrow$ 线性代数：Ⅲ	0.534 6
10	高等数学1：Ⅱ，高等数学2：Ⅳ $\Rightarrow$ 概率论：Ⅱ	0.715 2

事务数目/项	运行时间的增长率
事务数目/项	Apriori算法	MC_Apriori算法	本文算法	文献[12]算法
1 000~2 000	0.514	0.527	0.501	0.583
2 001~3 000	0.510	0.524	0.467	0.566
3 001~4 000	0.517	0.476	0.374	0.552
4 001~5 000	0.547	0.445	0.372	0.543
5 001~6 000	0.579	0.435	0.322	0.531

References 22

1	Agrawal R，Imieliński T，Swami A N. Mining association rules between sets of items in large database［J］ ACM Sigmod Record，1993，22（2）：207⁃216.
2	崔妍，包志强.关联规则挖掘综述［J］.计算机应用研究，2016，33（2）：330⁃334.
3	李洁，朱洪亮，陈玉玲，等.基于哈希存储与事务加权的并行Apriori改进算法［J］.计算机工程，2020，46（11）：109⁃116.
4	张宗郁，张亚平，张静远，等.改进关联规则算法在高校教学管理中的应用［J］.计算机工程，2012，38（2）：75⁃77.
5	廖纪勇，吴晟，刘爱莲.基于布尔矩阵约简的Apriori算法改进研究［J］.计算机工程与科学，2019，41（12）：2231⁃2238.
6	高海洋，沈强，张轩溢，等.一种基于数据压缩的Apriori算法［J］.计算机工程与应用，2013，49（14）：117⁃120.
7	李亮.基于优化关联规则的车辆轨迹分析研究［D］.济南：山东大学，2020.
8	苗苗苗，王玉英.基于矩阵压缩的Apriori算法改进的研究［J］.计算机工程与应用，2013，49（1）：159⁃162.
9	王志华，刘绍廷，罗齐.基于邻接多重表的动态频繁项集挖掘算法［J］.计算机工程与设计，2019，40（11）：3090⁃3098.
10	林佳雄，黄战.基于数组向量的Apriori算法改进［J］.计算机应用与软件，2011，28（5）：268⁃271.
11	刘芳.基于图和双向搜索的频繁项集挖掘算法［J］.计算机工程，2012，38（1）：59⁃61.
12	石升，董金琳，王玮，等.Apriori算法的改进及其在睡眠辅助医疗中的应用［J］.小型微型计算机系统，2020，41（12）：2668⁃2671.
13	赵永尊，张谧，赵卫东，等.基于品类聚类的关联规则优化算法［J］.计算机应用与软件，2007，24（1）：140⁃142.
14	岳根霞.基于关联规则的医疗大数据挖掘算法［J］.微电子学与计算机，2019，36（4）：105⁃108.
15	周兴斌，骆四毛.牛顿插值与分块算法对自适应支持度的研究［J］.计算机工程与设计，2014，35（2）：520⁃524.
16	张永，迟忠先.一种高效的基于采样的关联规则挖掘算法［J］.计算机工程与应用，2007，43（2）：184⁃186.
17	刘惠惠，张祖平，龙哲.基于Spark的FP⁃Growth伴随车辆发现与应用［J］.计算机工程与应用，2018，54（8）：7⁃13.
18	瞿诗齐，刘少江，倪伟传，等.基于Hadoop平台的GPU集群加速Apriori算法［J］.计算机工程，2018，44（11）：14⁃18.
19	王青松，姜富山.Hadoop框架下的一种改进的Apriori算法［J］.辽宁大学学报（自然科学版），2019，46（3）：257⁃264.
20	曹菁菁，任欣欣，徐贤浩.基于并行Apriori的物流路径频繁模式研究［J］.计算机工程与应用，2019，55（11）：257⁃264.
21	丁勇，朱长水，武玉艳.一种基于Hadoop的关联规则挖掘算法［J］.计算机科学，2018，45（S2）：409⁃411.
22	刘莉萍，章新友，牛晓录，等.基于Spark的并行关联规则挖掘算法研究综述［J］.计算机工程与应用，2019，55（9）：1⁃9.

[1]	YU Chen－yun, LIU Yang*, ZHOU Jin－zhi. Design and Implementation of Data Mining Platform Based on Plug-in Technology [J]. Journal of Liaoning Petrochemical University, 2010, 30(2): 46-49.
[2]	WANG Zheng－yang, LIU Yang, ZHANG Jie, YU Chen－yun, ZHOU Jin－zhi. Application of CRM Based on Data Mining  Technology in Petrochemical Enterprise [J]. Journal of Liaoning Petrochemical University, 2009, 29(4): 78-80.
[3]	L Ai-li, WEI Hai-ping, YE Xiao-tao. Dynamic Computer Forensics System Based on Data Mining and Multi-Agent [J]. Journal of Liaoning Petrochemical University, 2008, 28(1): 62-65.
[4]	ZHANG Yue,LIU Yang . Analysis and Application of Data Mining Algorithm Based on Decision Tree [J]. Journal of Liaoning Petrochemical University, 2007, 27(1): 78-80.