一种Apriori算法的高效实现方法及其应用_吴春旭.pdf

投稿网址：http：/辽宁石油化工大学学报JOURNAL OF LIAONING PETROCHEMICAL UNIVERSITY第43卷 第2期2023 年4月Vol.43 No.2Apr.2023一种 Apriori算法的高效实现方法及其应用吴春旭，贾银山，于红绯（辽宁石油化工大学 人工智能与软件学院，辽宁 抚顺 113001）摘要：针对 Apriori算法在扫描数据库和低维频繁项集时效率较低的问题，提出了一种基于 Apriori算法的高效实现方法 EI_Apriori算法。该方法基于向量的存储结构和预剪枝，降低了扫描数据库和低维频繁项集的次数，进而提高了 Apriori算法的效率。根据学生成绩分析的实际情况，在关联规则挖掘中增加了课程间先后关系的约束，在关联规则中增加了对成绩等级区间的约束，将调整后的 EI_Apriori算法在成绩关联分析中进行了应用。结果表明，EI_Apriori算法能精确地找到符合现实需求的关联规则，证明了 EI_Apriori算法的优越性。关键词：关联分析；教学改革；数据挖掘；Apriori算法；关联规则中图分类号：TP391 文献标志码：A doi：10.12422/j.issn.16726952.2023.02.013An Efficient Implementation Method of the Apriori Algorithm and its ApplicationWu Chunxu，Jia Yinshan，Yu Hongfei（School of Artificial Intelligence and Software，Liaoning Petrochemical University，Fushun Liaoning 113001，China）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 vectorbased storage structure and prepruning to reduce the number of scanning databases and lowdimensional 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.Keywords:Association analysis；Reform in education；Data mining；Apriori algorithm；Association rules随着信息化技术在高校成绩管理工作中的普及，学生成绩数据不断地产生、累积，如果能从学生成绩中发现有价值的信息，对促进教学改革具有重要意义。数据挖掘技术能高效地在海量的学生成绩数据中挖掘隐藏的、高价值的信息，这些信息反映学生成绩数据的内在规律或联系，能帮助教学管理人员和教师确定教学改革的方向。在学生成绩数据中进行数据挖掘的主要任务,是通过关联分析挖掘具有现实意义的关联规则。挖掘到的关联规则,可揭示课程、成绩间相互联系的内在规律。文献1提出了基于迭代思想的 Apriori 算法。Apriori算法因其在关联分析中具有适用性强、结构简单的优点，受到学者们的广泛关注。其主要思想是以迭代的方法逐步由低维频繁项集挖掘高维频繁项集，迭代过程中不断地通过剪枝操作减少非频繁项集的数量，大幅降低计算机的计算量2。但是，Apriori算法仍需要多次扫描数据库和低维频繁项集，并且在实际应用中还存在诸多不足。为此，提出了一种Apriori 算法的高效实现方法 EI_Apriori 算法，并且将其应用于高校学生成绩关联分析中。文章编号：16726952（2023）02007808收稿日期：20210710 修回日期：20211116基金项目：国家自然科学基金项目（1702247）。作者简介：吴春旭（1995），男，硕士研究生，从事机器学习、数据挖掘方面研究；Email：WuC。通信联系人：贾银山（1968），男，博士，教授，从事人工智能及其应用、大数据分析技术方面研究；Email：。第 2 期吴春旭等.一种 Apriori算法的高效实现方法及其应用1 Apriori算法 Apriori 算法的主要步骤是挖掘频繁项集和生成关联规则，其中挖掘频繁项集的计算量远远大于生成关联规则的计算量，对其进行研究具有较大的现实意义。因此，如何减少挖掘频繁项集的计算量是算法实现过程中的核心问题3。Apriori算法挖掘关联规则的形式化描述为4：事 务 Ti的 集 合 为 事 务 数 据 库d=T1,T2,TN，事务数据库 d 中记录的数目为N，I=i1,i2,ik是项i的集合，称为项集 I，Ti I。k_I项集是指有 k个不同项的集合。支持度 s大于最小支持度阈值smin的项的集合 I称为频繁项集。关联规则是形如X Y的表达式，X,Y I，X Y=，其中支持度 s为：s(X Y)=(X Y)N（1）式中，(X)=|Ti|X Ti,Ti d|。其置信度 c为：c(X Y)=s(X Y)s(X)（2）Apriori 算法巧妙地利用迭代和频繁项集向下封闭的性质，减少挖掘频繁项集过程中的计算量。其主要过程为：扫描 d，计算各项的支持度；再将支持度小于smin的项去除，剩余的项的集合即为频繁1_项集，记为 L1；将 L1与本身连接，生成项的集合C2，称为候选频繁 2_项集；对 C2进行剪枝操作，再根据smin去除不符合要求的项，剩余的项的集合 L2即为频繁 2_项集；重复此前的步骤，直到不能再挖掘到频繁项集为止。连接和剪枝操作是寻找频繁项集过程中的核心操作，其具体操作如下：（1）连接。此操作的目的是生成候选频繁项集Ck。Lk-1Lk-1表示 Lk-1与本身进行连接。设 ii和 il是 Lk-1中两个不同的项，Lk-1Lk-1即 ii和 il连接，ii和 il连接的结果是生成 Ck中 k 维的项，其中 ii和 il的前 k-2个元素必须是相同的。（2）剪枝。此操作的目的是减少非频繁项的数目。剪枝操作主要是利用低维频繁项集的超集都是频繁项集的性质5，对生成的项集进行剪枝，即由候选项集 Ck生成频繁项集 Lk时，删除所有 Ck中 k-1维子集不在 Lk-1中的项。2 Apriori算法的不足与改进 2.1 Apriori算法的不足虽然 Apriori 算法已经大大缩小了需要处理数据的计算量，但是由于受事务数据库中最小支持度阈值、最小置信度阈值、事务的数量、事务的平均宽度的影响，算法的运行时间仍然较长。算法运行时间的消耗主要表现在以下几个方面：（1）计算候选频繁项集 Ck中所有项的支持度，需要根据候选项集的项数多次扫描事务数据库，以确定每一项出现的次数。若事务数据库中事务的平均宽度为 n，遍历数据库的次数会达到 2n-1 次，将会给计算机造成巨大的 I/O设备开销。（2）Lk-1中的项两两连接生成候选项集 Ck时，会产生大量非频繁项，必须多次扫描低维频繁项集以做出判定。对于 Ck中的项 c，每做出一次删除或者保留的判定时，都至少需要扫描 Lk-1次。考虑最差的情况，每次做出判定都需要 k 次扫描。设 Ck中项的个数为|Ck|，并且i(1,|Ck|)，Lk-1中项的个数为|Lk-1|，则 Ck中子集的个数为 Ni。为判定 Ck中的全部项，Apriori 算法的运算次数为i=1|Ckj=1Ni|Lk-1，对于项 数 量 较 多 的 候 选 项 集，算 法 的 运 行 时 间 明 显增加。2.2 Apriori算法的改进上述问题主要有以下几种改进思路：（1）改进数据存储方式，以数组、矩阵和图的形式存储项集的算法611。这些算法将数据库中事务的分布和宽度信息通过新的存储结构映射到频繁项集中，虽然算法只读取一次数据库，但是对计算机内存要求较高。文献7以矩阵存储项集提高运行效率，达到了减少读取数据库次数的目的，但是数据库中事务的数目、事务平均宽度较大时矩阵的规模较大，在内存中存储和运算比较困难。文献8提出 MC_Apriori 算法，利用 Apriori 算法对矩阵进行压缩处理，不断地删除子集为非频繁项集和不符合最小支持度的行，减小了矩阵的规模，提高了算法的时空效率。（2）基于枚举策略的改进1213。该算法需要一次性读取数据库所有事务并生成每个事务的全部子集，算法虽不再多次扫描数据库和低维频繁项集，但算法的空间复杂度并不理想，并且单次遍历时间较长。文献12提出了一种基于组合的改进算法，通过组合的方法，在原集合中将不同的项进行组合，将所有事务的子集全部找出，不再重复扫描数据库，而是在全部子集的集合中计算所有事务子集的支持度。但是，对于事务数量、平均宽度较大的数据库，该算法的组合过程比较复杂，产生的子集数量较多，存储这些子集占用内存较大，计算每个子集支持度的遍历操作运行时间较长。79辽宁石油化工大学学报第 43 卷（3）对数据库进行精简的改进算法，主要基于采样、分块、分层的策略对原始数据进行清洗和分类1416。这类算法根据行业特点对大批量的冗余数据进行精简操作，利用分块、采样将原始数据划分成规模较小的部分，然后在这些较小的数据库中挖掘关联规则，并结合相应数据挖掘方法提高算法的效率。但是，算法的可扩展性不佳，每次应用都要人工分析数据结构，对算法做出相应的调整后，才能应用到相应实施例中。（4）基于并行策略的改进算法1722。这些算法大都在 Hadoop 平台中利用 MapReduce 并行技术提升查找频繁项集的效率，结合分组、分块、划分思想对数据集进行预处理，充分发挥各节点分布式计算的优势。但是，算法在计算支持度时扫描数据集、剪枝的操作效率较低，另外，此类算法大都采用分布式文件系统进行存储，访问时需要多次重启，降低了算法效率。本文提出了一种 Apriori 算法的高效实现方法EI_Apriori算法，该方法仅需遍历一遍事务数据库，并且不再扫描低维频繁项集，以此来弥补 Apriori算法的不足。2.3 Apriori算法的高效实现方法2.3.1主要思想 Apriori 算法高效实现方法的主要思想如图 1所示。该方法的主要思想是通过一次扫描，将事务数据库中的事务的数量信息以位向量的形式映射到频繁 1_项集中，利用向量的内积和“与”运算，快速、便捷地计算项的支持度和生成候选项集。以向量的内积计算代替多次扫描数据库来计算的