摘要：本文详细分析了关联规则数据挖掘Apriori算法的思想和步骤，给出了算法的伪代码。现在Apriori算法已广泛应用于金融、医疗以及教育等领域，所以，作为教育工作者，有必要对其进行进一步的研究。
　　关键字：Apriori算法；数据挖掘；关联规则
　　中图分类号：TP 391
　　文献标识符：A
　　引 言
　　Apriori算法[1]是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。目前，Apriori算法广泛应用于各个领域，所以对其进行研究具有很重要的意义。
　　1.Apriori算法的思想
　　Apriori算法是由Agrawal和 Strikant提出的一种最有影响的关联规则挖掘算法。该算法的过程是针对给定的交易数据库DB，用户在初始阶段设定最小支持度Smin和最小置信度Cmin，然后找出频繁 1-项集的集合L1，使用逐层搜索的迭代方法，通过k-项集生成（k+1）-项集，而找每个 Lk都需要扫描一次数据库[1][2]。
　　2. Apriori算法的步骤
　　2.1生成频繁项集
　　在数据挖掘过程中为生成Lk，可通过连接和剪枝两步过程来完成[3] [4]。
　　1、连接：为找 Lk，通过 Lk - 1与自己连接产生候选 k-项集的集合。该候选项集的集合记作 Ck。设l1和 l2是 Lk - 1中的项集。记号Li[j]表示 li的第 j 项。为方便计，假定事务或项集中的项按字典次序排序。执行连接 Lk – 1 Lk - 1；其中，Lk - 1的元素是可连接的， 如果它们前（k-2）个项相同； 即， Lk - 1的元素 l1和 l2是可连接的，如果（l1 [1] = l2 [1]）∧（l1 [2] = l2 [2]）∧ ... ∧（l1 [k-2] = l2 [k-2]）∧（l1 [k-1] < l2 [k-1]）。条件（l1 [k-1] < l2 [k-1]）是简单地保证不产生重复。连接 l1和 l2产生的结果项集是 l1 [1] l1 [2]... l1 [k-1] l2 [k-1]。
　　2、剪枝：Ck是 Lk的超集；即，它的成员可以是，也可以不是频繁的，但所有的频繁 k-项集都包含在 Ck中。扫描数据库，确定 Ck中每个候选的计数，从而确定 Lk（即，根据定义，计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk）。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩 Ck，可以用以下办法使用 Apriori 性质：任何非频繁的（k-1）-项集都不是可能是频繁 k-项集的子集。因此，如果一个候选 k-项集的（k-1）-子集不在 Lk - 1中，则该候选也不可能是频繁的，从而可以由 Ck中删除[3][4]。
　　生成频繁项集的算法描述：
　　输入：事务数据库 D；最小支持度阈值。
　　输出：D 中的频繁项集F。
　　SetOfItemsets generateFrequentItemsets（Integer minimumSupport）
　　{
　　F[1]={frequent items}；
　　For （k=1，F[k]<>0；k++）
　　{
　　C[k+1]=generateCandidates（k，F[k]）；
　　For each transaction t in databases
　　{
　　For each candidate c in C[k+1]
　　{
　　If t contains c then c.count++
　　}
　　} //扫描数据库
　　For each candidate c in C[k+1]
　　{
　　If c.count>=minimum_support F[k+1]= F[k+1] U {c} //选择符合条件的候选项
　　}
　　}
　　While k>=1 do
　　{
　　F=F U F[k]；
　　k- -；
　　} //合并候选集
　　}
　　2.2产生强关联规则
　　一旦从数据库 D 中找出频繁项集，可从中产生强关联规则，强关联规则满足最小支持度和最小置信度。对于置信度，可以用下式，其中条件概率用项集支持度计数表示。
　　其中，support_count（A∪B）是包含项集 A∪B 的事务数，support_count（A）是包含項集 A 的事务数。根据该式，关联规则可以产生如下：
　　（1）对于每个频繁项集L，产生 L 的所有非空子集。
　　（2）对于L的每个非空子集 s，如果 ，则输出规则“s ? （l-s）” 。其中，min_conf 是最小置信度阈值。
　　由于规则由频繁项集产生，每个规则都自动满足最小支持度。
　　生成关联规则算法：
　　For each frequent itemset f， generate all the subset x and its
　　Complimentary set y=f-x
　　If support（f）/support（x）> Minimum_probability， then x=>y
　　Probability = Support（f）/Support（x） 　　3. Apriori算法应用实例
　　设事务数据库D如表1所示，最小支持数为2，最小可信度为60%求数据库D频繁项集和关联规则的过程如下。
　　表1 事务数据库示例
　　TID Item
　　T1 I1，I3
　　T2 I1，I2，I3，I5
　　T3 I2，I3，I4，I5
　　T4 I1，I2，I3
　　T5 I1，I4，I5
　　T6 I3，I5
　　数据库D的频繁1项集F={{I1：4}，{I2：3}，{I3：5}，{I4：2}，{I5：4}}；
　　候选2项集C2={{ I1，I2}：2，{ I1，I3}：2，{ I1，I4}：1，{ I1，I5}：2，{ I2，I3}：3，{ I2，I4}：1，{ I2，I5}：2，{ I3，I4}：1，{ I3，I5}：3，{ I4，I5}：2}；
　　由于最小支持数为2，则频繁2项集L2={{ I1，I2}，{ I1，I3}，{ I1，I5}，{ I2，I3}，{ I2，I5}，{ I3，I5} ，{ I4，I5}}；
　　候选3项集C3={{ I1，I2，I3}：2，{ I1，I2，I5}：1，{ I2，I3，I5}：2}；
　　频繁3项集L3={{ I1，I2，I3}，{ I2，I3，I5}}；
　　候选4项集C4={{ I1，I2，I3，I5}：1}，频繁4项集L4= ；
　　所以，该事务数据库D对应的频繁项集是L={{I1}，{I2}，{I3}，{I4}，{I5}，{ I1，I2}，{ I1，I3}，{ I1，I5}，{ I2，I3}，{ I2，I5}，{ I3，I5} ，{ I4，I5}，{ I1，I2，I3}，{ I2，I3，I5}} 。
　　关联规则及置信度如下：
　　I1=>I2 置信度为support_count（I1，I2）/ support_count（I1）=50%；
　　I1=>I3 置信度为support_count（I1，I3）/ support_count（I1）= 50%；
　　I1=>I5 置信度为support_count（I1，I5）/ support_count（I1）= 50%；
　　I2=>I3 置信度为support_count（I2，I3）/ support_count（I2）= 100%；
　　I2=>I5 置信度为support_count（I2，I5）/ support_count（I2）= 66.7%；
　　I3=>I5 置信度为support_count（I3，I5）/ support_count（I3）= 60%；
　　I4=>I5 置信度為support_count（I4，I5）/ support_count（I4）= 100%；
　　I1I2=>I3置信度为support_count（I1，I2，I3）/ support_count（I1，I2）= 100%；
　　I1=> I2I3置信度为support_count（I1，I2，I3）/ support_count（I1）= 50%；
　　I2=> I1I3置信度为support_count（I1，I2，I3）/ support_count（I2）= 66.7%；
　　……
　　则满足最小支持度和置信度的所有关联规则如下：
　　I2=>I3 ，I4=>I5， I1I2=>I3 ，I1I3=>I2 ，I2I5=>I3 置信度100%；
　　I2=>I5，I2=> I1I3，I2I3=>I1，I2I3=>I5，I3I5=>I2，I2=> I 3I5 置信度66.7%；
　　I3=>I5 置信度60%；
　　4.结束语
　　本文详细分析了关联规则数据挖掘Apriori算法的思想和步骤，给出了算法的伪代码，通过一个实例，演示了该算法的挖掘过程。现在Apriori算法已广泛应用于金融、医疗以及教育等领域，所以，作为教育工作者，有必要对其进行进一步的研究。