关联规则Apriori挖掘算法的优化研究

张 彤

西安财经学院长安校区

关联规则Apriori挖掘算法的优化研究

张 彤

西安财经学院长安校区

21世纪是海量数据的数字化时代，人们也开始习惯利用数据来分析、处理和解决问题，且数据挖掘算法日益被广泛应用。其中，数据挖掘的研究中，各个领域活动跨度最积极的就是关联规则Apriori挖掘算法。文章针对其两大瓶颈之一展开研究，即研究可能形成数量较多的候选项集。在探索优化方法的同时，根据频繁项集的性质，在原有算法基础上得到一个候选项目集数量最小化的Apriori优化算法，最后再进行实证的应用。

关联规则 频繁项集 Apriori算法 运算效率 优化

一、绪论

自上世纪80年代以来，大型数据库的普及和应用随着科学信息技术的飞速发展应运而生，各行业、各单位甚至各国都累积了以一定的形式存储的一定规模或海量的数据信息。面对数据分析的需求，“数据挖掘”应运而生，而主要的是关联规则挖掘算法。关联规则挖掘方法一开始的研究动机是由购物篮分析问题提出的，其最早是由Agrawal等人在1993年提出。次年，他们建立了项目集格空间理论，提出了著名的Apriori算法。随着应用的深入研究，该算法存在两个比较严重的问题：扫描事务数据库的次数频现、可能形成数量较多的候选项集。

针对Apriori算法会产生大量候选项集的问题，Park等人（1995）提出了一种依据散列技术产生频繁项集的算法。但其中产生候选项集所花费的时间和精力是无法度量的。所以才提出了一种基于划分的方法。与此同时，该算法会明显的使扫描事务数据库的次数变多，事物压缩的方法也就随之被提出。

综上所述，许多算法主要注重于挖掘质量的提高，忽略了挖掘效率，因此，文章主要针对挖掘效率的提高做进一步的研究。

因此，就频繁项集的“如果一个频繁项目集是数据集的项目集，那么这个数据集中的所有（k-1）项目子集也一定是频繁（k-1）-项目集”的性质，提出一种优化后的算法，取名称作：候选项目集数量最小化的Apriori优化算法。这种方法是在Apriori算法的根基上，进一步缩减候选项集中候选项的数量，研究出优化的算法，并在R语言中进行验证，进行比较优化前后两者的运行算法的时间，以此来进行对比，并总结出文章的主要结论。

二、关联规则Apriori算法的分析

（一）核心算法分析

Apriori算法主要有以下两个步骤：（1）通过数据库中每一项的累计结果，找出并罗列满足minsupport（最小支持度）的项，形成频繁1-项集，记作L1；（2）利用上一步形成的L1来形成频繁2-项集，记为L2，利用L2再找到L3，以此类推，直到找出所有符合搜索条件的频繁k-项集为止。

（二）算法的优缺点

Apriori作为频繁项集产生算法，在关联规则的数据挖掘中扮演着很重要的角色。但它也有利弊的两面。

对于核心思想是通过候选集生成和剪枝检测两个阶段来挖掘频繁项集的Apriori算法，在移动通信领域以及一些高等学校教育的管理和整治中，可以有效地辅助各个领域有针对性的进行交流和督查工作，并提出一些有建设性的意见。但随着经济、科技的飞速发展，它的应用随之深入，它的缺点也显而易见，主要包括：在产生频繁项集前会频繁的扫描数据库和在产生最终的频繁项集前可能形成数量较多的候选项集。因此，文章针对Apriori算法的第二个主要缺陷，进行优化研究和分析。

三、关联规则Apriori算法的优化设计

根据关联规则的基本性质，研究问题一般可以划分为两个层次：（1）发掘频繁项目集。实际上，有需求的用户在找到所有的频繁项集之前，都要通过一项检测，即：满足支持度不小于minsupport，这样才能更加准确的生成所需要的、可能有包含关系的项目子集。（2）关联规则的产生。在每个最大频繁项目集中通过置信度的指定检验，我们可以找到问题所真正必须的关联规则。一般情况下，我们都认定置信度不小于minconfidence的关联规则。

在上述两个层面的阐述中，第二层次较首层次来说相对比较简单、易懂，所以近几年来，研究的重中之重必然就落到了首层面的问题上。

（一）优化的Apriori算法

在传统的Apriori算法中，用规定的支持度让Ck-1进行比对，那些不小于minsupport的项集被保留，其余的项集被删除，由此生成Lk-1，并进一步结合Lk-1与Lk-1生成Ck。而提出的新的改进方法，即进一步减少候选项集的候选项的数量，其主要思想是：为了有效的减少参加结合的k-1的项目集的数量，即在Lk-1生成Ck之前，先对Lk-1的项目集进行比对和删减的处理，由此可以减少最终的Ck中结果候选项的数量。

（二）优化后的算法的设计

1.算法的描述。根据上述的一系列说明，优化后的算法可以展示如下：（1）在扫描数据库D产生Lk-1的过程期间，计算Lk-1中所有项出现的频数；（2）把Lk-1中出现频数小于（k-1）的项集完整剔除。

2.算法的优良性比对。在论述了Apriori算法、以及它优化后的算法之后，运用R语言进行算法程序的运行，并利用计算算法程序运行时间行优化前后两者时间上的比较，得到了如下表3-1所示的比较结果。

表3-1 优化前后Apriori算法程序运行时间对比表

下面先对表中的一些专业术语进行解释：

“用户”是消耗在算法程序（非操作系统部分）执行的时间，“系统”是最基层算法运行系统执行（例如磁盘读写等）部分的时间，“流逝”是算法运行经过的总时间（可以认为是前两者的总和）。一般优化时主要关注“用户”的时间。

从表3-1中可以看出，优化前后的Apriori算法的用户时间有明显的不同，优化前算法的用户时间比优化后算法的用户时间长，虽然两者的系统的时间没有差别，但是流逝的时间总体来说是有差别的。这样就正好证明了本篇文章所研究的主要问题——优化后的算法提升了关联规则Apriori挖掘算法的效率，在算法运行的时间上有了比较好的提升。

四、小结

文章从原有的Apriori算法的第二个缺点入手，对原有算法进行研究并致力于创新发现一种优化后的算法——候选项目集数量最小化的Apriori优化算法，这种优化后的算法的优点可以总结为下面三个方面：（1）在从项集Lk-1中产生频繁项集Ck时，先对Lk-1中的项的数目进行统计，根据频繁项集的性质对Lk-1进行删减，从而能减少参加组合频繁项集的项集数目；（2）对优化前后算法的运行时间有明显的区别：优化后的算法比优化前的算法所要花费的运行时间比较少，在一定程度上降低了挖掘的成本。（3）在大数据的环境中，该优化后的算法的运行效率较之前原有算法的高，优化后的算法具有明显的优势。

但优化后的算法也有一定的缺陷。在考虑了算法的候选项集的问题的同时，忽略了扫描数据库次数的问题，并且在进行优化的同时，算法编写的过程也有一定的难度，需要耗费大量的时间和精力来完成，且精度也有待进一步的提升。

［1］徐华.数据挖掘：方法与应用［N］.北京：清华大学出版社，2014：66-75.

［2］ Agrawal R，Imielinski T，Swami A.Mining association rules between sets of items in large databases.SIGMOD'93.

［3］ 胡慧荞，王周敬.一种基于关系矩阵的关联规则快速挖掘算法［J］.计算机应用，2005，25（7）：1577-1579.

张彤，女，汉族，陕西铜川人，硕士研究生研究方向：非线性动力学与统计学。