一种Apriori算法的高效实现方法及其应用

doi:10.12422/j.issn.1672-6952.2023.02.013

辽宁石油化工大学学报 ›› 2023, Vol. 43 ›› Issue (2): 78-85.DOI: 10.12422/j.issn.1672-6952.2023.02.013

一种Apriori算法的高效实现方法及其应用

吴春旭(), 贾银山(), 于红绯

辽宁石油化工大学人工智能与软件学院，辽宁抚顺 113001

收稿日期:2021-07-10 修回日期:2021-11-16 出版日期:2023-04-25 发布日期:2023-05-04
通讯作者: 贾银山
作者简介:吴春旭（1995⁃），男，硕士研究生，从事机器学习、数据挖掘方面研究；E⁃mail：WuChunxu1a@163.com。
基金资助:
国家自然科学基金项目(1702247)

An Efficient Implementation Method of the Apriori Algorithm and its Application

Chunxu Wu(), Yinshan Jia(), Hongfei Yu

School of Artificial Intelligence and Software，Liaoning Petrochemical University，Fushun Liaoning 113001，China

Received:2021-07-10 Revised:2021-11-16 Published:2023-04-25 Online:2023-05-04
Contact: Yinshan Jia

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP391

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

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.

图/表 10

图1 Apriori算法高效实现方法的主要思想

表1 事务数据库

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

表2 生成的频繁1_项集

项集	事务向量	内积
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

表3 生成的频繁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(删除)

图2 预剪枝示意图

表4 部分学生的成绩数据 (分)

编号	成绩
编号	高等数学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

表5 EI_Apriori算法生成的部分关联规则

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

表5 EI_Apriori算法生成的部分关联规则

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

图3 不同算法在不同尺度最小支持度下的运行时间

图4 不同算法处理不同事务数目数据库的算法运行时间

表6 四种算法的运行时间增长率随事务数目的变化

事务数目/项	运行时间的增长率
事务数目/项	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

参考文献 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]	于兆河，徐鹰博. “一带一路”背景下我国石油行业竞争战略与财务绩效关系研究[J]. 辽宁石油化工大学学报, 2019, 39(4): 93-100.
[2]	李阳. 基于灰色关联支持向量机的河道预测在S油田N区的应用[J]. 辽宁石油化工大学学报, 2018, 38(02): 40-46.
[3]	李占东，张丽双，李丽，梁顺，师昊，田秘，汪洋，张树鑫. 基于灰色关联支持向量机的河道预测方法[J]. 辽宁石油化工大学学报, 2017, 37(4): 34-38.
[4]	刘旸, 于辰云，张学军. 嵌入式数据库在数据挖掘系统中的应用[J]. 辽宁石油化工大学学报, 2010, 30(4): 63-65.
[5]	张春姝. 灰色关联理论与综合评分法在工程评标中的应用[J]. 辽宁石油化工大学学报, 2010, 30(4): 97-.
[6]	于辰云,刘旸,周金枝. 基于插件技术的数据挖掘平台设计与实现[J]. 辽宁石油化工大学学报, 2010, 30(2): 46-49.
[7]	王正阳,刘旸,张杰,于辰云,周金枝. 基于数据挖掘技术的CRM 在石油化工企业的应用[J]. 辽宁石油化工大学学报, 2009, 29(4): 78-80.
[8]	吕爱丽，魏海平，叶小涛. 基于数据挖掘的Multi-Agent动态取证系统研究[J]. 辽宁石油化工大学学报, 2008, 28(1): 62-65.
[9]	张　悦, 刘暘. 基于决策树数据挖掘的分析与应用[J]. 辽宁石油化工大学学报, 2007, 27(1): 78-80.

一种Apriori算法的高效实现方法及其应用

An Efficient Implementation Method of the Apriori Algorithm and its Application

HTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 22

相关文章 9

编辑推荐

Metrics