Apriori算法在数据挖掘中的应用

南京工业大学浦江学院 圣文顺 张林慧

导语：在信息化时代背景下，信息成为社会发展的重要推动力，数据则演变为人们社会行为规律分析与挖掘的基础载体。数据挖掘是指从海量数据中挖掘出更有价值的信息元素，并运用关联规则将事物紧密联系，分析预测人们的后续行为。本文围绕数据挖掘这一主题，研究Apriori算法在数据挖掘中的应用，从数据挖掘的基本概念、Apriori算法简介及该算法在数据挖掘中的应用三个方面进行论述，结合实例推演数据关联规则的产生及Apriori算法的具体应用过程。

当今社会已进入大数据时代，数据渗透在生活的每一个角落，数据之间存在有趣的关联。业界人士对数据挖掘的关注度大幅度上升，数据挖掘使业务更加智能，使信息更加可靠，种种现象表明数据也是生产力。清楚数据挖掘的基本概念是关联规则的首要任务，Apriori算法是寻找数据中频繁项集的有力武器，落实Apriori算法是对数据挖掘的应用夯实。由此，本文对数据关联规则作出了详细的介绍，给出了关于Apriori算法的应用实例。

1.数据挖掘的基本概念

通过大量数据的收集和存储，运用关联规则挖掘出数据各项之间的联系或关联，得到相关信息，从而得出数据也是生产力。因此，我们需要了解关于数据挖掘的几个基本概念。

（1）项、项集与事务

项（Item）是数据中的最小单位；某几个项的集合称为事务（T），每个事务有一个关键字属性，称为事务号（或交易号），由此区分数据库中的各个事务；所有项的集合为P，T为P的子集；事务的集合为事务集（D）。将这些基本概念如图所示：

图1 项、项集与事物关系图

（2）关联规则

用Venn图表示，如下：

图2 Venn图

（3）支持度（s）与置信度（c）

支持度s表示A与B的总和（A∪B）占D的百分比，即概率P（A∪B），表达式如下：

支持度定义的分子（事务数（））称为支持度计数。由于支持度更容易由分子导出，一般情况下，显示支持度计数而不是支持度。支持度反映的是实用性。

置信度c表示A与B的总和（A∪B）占包含A的事务的百分比，即条件概率P（A|B），表达式如下：

置信度反映的是有效性，确定性。当置信度为100%时，意味着规则完全有效确定，值得信赖。

当同时满足最小支持度阈值min_s和最小置信度阈值min_c时，就可以挖掘出强关联。支持度与置信度用百分比表示，区域范围在0%至100%之间。

（4）k-项集与k-频繁项集

包含k个项的项集称为k-项集。例如：集合{牛奶，蛋糕}是2-项集；集合{牛奶，蛋糕，布丁}是3-项集。包含项集的事务数是项集的出现频率，又称项集支持计数或计数。如果：项集的出现频率大于或者等于min_s乘以D中事物总数，则：项集满足最小支持度min_s。此时，项集称为频繁项集。频繁k-项集的集合记作：Lk。频繁项集的非空子集也必须是频繁的。

关联规则的挖掘涉及寻找频繁项集。

2.Apriori算法

关联规则的挖掘涉及寻找频繁项集。Apriori算法用于寻找频繁项集。

（1）Apriori算法简介

Apriori算法指的是一种逐层搜索的迭代方法。顾名思义，Apriori算法使用前一项集探索后一项集的方法。如：找出频繁1-项集（L1），用L1找出频繁2-项集L2，再用L2找出L3……Lk找出Lk+1，依次类推，直到不能找出频繁k-项集。每找一个Lk需要扫描一次数据库。

（2）Apriori性质

为提高逐层搜索频繁项集的效率，由此产生用于压缩搜索空间的重要性质。

根据定义，现定义一个项集I，如果I不满足最小支持度s，即P(I)＜s，显然，I不是频繁项集。将项A添加到I，根据支持度公式推导，A∪I不可能比I更频繁出现。即P（I∪A）＜P(I)＜s。此为反单调，即当一个集合不能通过测试，则包含此集合的任何集合都无法通过同一测试。

由此得出：任何非频繁的（k-1）项集都不可能是频繁k-项集的子集。用此性质压缩搜索空间，可以大大提高搜索频繁项集的效率。

（3）Apriori性质应用简介

运用此性质，用Lk寻找Lk+1：

1）寻找连接集

通过Lk与其自身做连接操作产生候选k-项集，记作Ck+1。li[j]表示li的第j项，例如l1[3]表示l1的第3项。执行连接Lk（JOIN）Lk。如果（l1[1]=l2[1]）∧（l1[2]=l2[2]）∧……∧（l1[k-1]=l2[k-1]）∧（l1[k]＜l2[k]）。其中l1[k]＜l2[k]是为了保证不产生重复。所以连接项集是{l1[1]，l1[2]，……，l1[k]，l2[k]}。

2）删除

Ck是Lk的超集（包含它的任何集合），Lk的成员可以是，也可以不是频繁的，但所有的频繁k-项集都包含在Ck中，确定Ck中每个候选的计数，从而确定Lk。为压缩Ck，提高搜索效率，使用Apriori性质：任何非频繁的（k-1）项集都不可能是频繁k-项集的子集。如果候选项集k-项集的子集不在Lk-1中，则候选项集不可能频繁，可以从Ck中删除。

重复寻找连接集与删除步骤操作，直到产生最后的频繁项集。不妨设最后产生的频繁项集为频繁k-项集。将频繁项集中的k拆分为A，B两个项集，计算其支持度与置信度，挖掘出其规则。

3.算法在数据挖掘中的应用

Apriori算法指的是一种逐层搜索的迭代方法。本实例采取“超市数据库”中的各项数据，具体展示介绍算法在数据挖掘实例当中的应用。

（1）算法迭代应用

我们以P1，P2，P3……形式代表不同的商品，以T表示每个记录。现有如下商品购买数据库D：

表1 商品购买数据库

从本数据库D中可以看出共有20笔交易，即20个事务（T）；共8件商品，即8个项。记P={P1，P2，P3，P4，P5，P6，P7，P8}。

1）第一轮算法迭代

使候选1-项集C1=P，则P中每一个成员（即P1，P2，P3，P4，P5，P6，P7，P8）成为C1的成员。计数每一项在数据库D中出现的次数，得到支持度计数。结果如下表：

表2 候选1-项集C1支持度计数

完成第一次与自身连接操作并得出支持度计数后进行查找删除。不妨设最小支持度计数为5（即最小支持度min_s=5/20=25%），从C1中查找并删除小于最小支持度计数的项集，得到频繁1-项集L1。结果如下表：

表3 频繁1-项集L1支持度计数

2）第二轮算法迭代

产生候选2-项集C2。使L1（JOIN）L1，将L1中的每个项进行组合，形成候选2-项集C2。计数二项集在数据库D中出现的次数，得到支持度计数。结果如下表：

表4 候选2-项集C2支持度计数

完成第二次连接操作并得出支持度计数后进行查找删除。不妨继续设最小支持度计数为5，从C2中查找并删除小于最小支持度计数的项集，得到频繁2-项集L2。结果如下表：

表5 频繁2-项集L2支持度计数

3）第三轮算法迭代

产生候选3-项集C3。使L2（JOIN）L2，将L2中的每个项进行组合，形成候选3-项集C3。根据Apriori性质：任何非频繁的（k-1）项集都不可能是频繁k-项集的子集。可直接删除某几个项集。如下表：

表6 候选3-项集C3删除操作表

计数三项集在数据库D中出现的次数，得到支持度计数。结果如下表：

表7 候选3-项集C3支持度计数

完成第三次连接操作并得出支持度计数后进行查找删除。不妨继续设最小支持度计数为5，从C3中查找并删除小于最小支持度计数的项集，得到频繁3-项集L3。结果如下表：

表8 频繁3-项集L3支持度计数

4）第四轮算法迭代

产生候选4-项集C4。使L3（JOIN）L3，将L3中的每个项进行组合，形成候选4-项集C4。计数四项集在数据库D中出现的次数，得到支持度计数。最终没有被删除的候选4-项集C4只有一个。如表9所示：

表9 频繁3-项集L3支持度计数

完成第四次连接操作并得出支持度计数后进行查找删除。继续设最小支持度计数为5，这一项仍被保留。

由算法得出的最后输出结果，频繁项集全集如表10所示：

表10 频繁项集全集

（2）形成关联规则

将频繁项集中的k拆分为A，B两个项集，满足条件：A∪B=k，排列出所有A，B，得出潜在规则，计算其置信度。以频繁项集频繁4-项集为例展示关联规则的产生，，其中A∪B={P1，P2，P5，P6}，A∩B=。表11所示为潜在规则表：

表11 潜在规则表

表12 规则表

由此规则表得到：“项集A的购买”推出“项集B的购买”。所有的频繁项集产生关联规则后，可以得出一些规则，如：

本研究为关联规则提供了强有效的算法，为数据挖掘提供了明确方式，也为今后对数据挖掘的研究提供了理论参考依据。

引文

①大数据.http://en.wikipedia.org/wiki/Big_data.

②Viktor Mayer-Sch.nberger,Kenneth Cukier.大数据时代:生活、工作与思维的大变革[M].杭州:浙江人民出版社,2013.

③Silberschatz.A..数据库系统概念(原书第6版)[M].北京:机械工业出版社,2012.

④韩嘉炜.Micheline Kamber.数据挖掘:概念与技术(原书第3版)[M].北京:机械工业出版社,2012.

⑤http://en.wikipedia.org/wiki/Meta-Object_Facility.