数据挖掘结课论文--- 关联规则-Apriori算法研究及其应用

                         2017-06

摘要：通过介绍关联规则模型和关联规则中提供了求频繁项集的Apriori算法，并运用实例进行解释该算法的基本实现过程。

关键字：关联规则  Apriori  数据挖掘

引言

数据挖掘是从大量的数据中挖掘哪些令人感兴趣的、有用的、隐含的、先前未知的和可能有用的模式或知识[1]。关联规则是数据挖掘的典型方法，它是描述在数据库中数据项之间同时出现的规律的知识模式。关联规则的分析方法用于隐藏在大型数据集中令人感兴趣的联系，所发现的联系可以用关联规则或频繁项集的形式表示。关联规则挖掘问题首先是R. Agrawal等人于1993年提出的，而后又进一步提出了 著名的Apriori算法，该算法的主要思想是首先寻找给定数据集中的频繁项集，然后通过频繁项集生成强关联规则[2]。

Aprori算法介绍：

 它率先利用支持度对候选项集进行剪枝，系统地控制候选项集指数增长。其主要步骤分为两步，首先产生候选项集，其次是对候选项集进行剪枝产生频繁项集，由频繁1-项集L1 开始，反复迭代重复，直至找到含有最多项的频繁项集为止。

Apriori算法基本思想

 算法使迭代的方法，从1-项集开始，根据给定的支持度阈值minsup将频繁的1-项集剪枝，找到频繁1-项免L1。根据先验原理：若某个项集是频繁的，那么其所有的项集必然是频繁的。所以在产生候选2-项集，记做C2, 的时候就直接使用频繁1-项集L1来产生就可以了。产生候选2-项集之后再根据给定的minsup对候选2-项集C2进行前枝，产生频繁2-项免L2。依次类推，根据L2产生C3，将C3剪枝产生L3，......直接产生最多想的频繁项集LK为止[3]。 如前所述，Apriori算法挖掘规则的过程也可分为两步来实现：

 ①找到数据集中的所有频繁项集L。

 ②从频繁项集L中提取出强规则。

 其中①步是Apriori算法的关键所在，是决定此算法性能是否优良的评价关键，②步的实现相对比较简单。口前对于Apriori算法的改进方法也大多数足针对①步。①步的实现吋以再细分为两个操作。第一个操作是产生候选项集C,第二个操作是将已产生的候选项集C根据minsup进行剪枝，找到频繁项集L。

其中候选项免的产生也苻很多实现方法，常见的主要有：蛮力方法，Fk-1 X F1方法和Fk-1 * Fk-1方法等。

1、蛮力方法

 如果我们需要产生候选集k-项集，蛮力方法就会将所有的1-项集进行排列组合，列出所有可能的候选项集。如果有n个1-项集，则会产生个候选项集，然后再以推理3.7为依据减掉一部分不必要的候选项集。由此可见，虽然此方法候选项集的产生非常简单但操作起来比较复杂，剪枝时要考虑的候选数量太大。

2、Fk-1*F1 方法

此方法是利用Lk-1与L1组合来产生候选k-项集Ck-1.图1是此方法将频发2-项集与频繁1-项集组合差残生候选3-项集的过程。

 图1 通过合并Lk-1和L1得到候选k项集Ck

 但是由于此方法中的Lk是由Lk-1和L1组合产生的，因此不可避免产生重复候选项集。

 k-1*Fk-1方法

 此方法中候选k-项集是由合并一对频繁（k-1）-项集得到的，并且这一对频繁（k-1）项集要满足前k-2个项是相同的。即令A={a1,a2,...,ak-1}和B={b1,b2,...,bk-1},当他们满足以下条件时，合并A和B:

 i=bi(i=1,2,3,...k-2)并且ak-1不等于bk-1

和图2展示了如何利用此方法将一对频发2-项集组合产生候选3-项集的过程。

 图2 通过合并一对频繁（k-1）项集Lk-1得到候选k-项集Ck

由于此方法是合并一对频繁(k-1)-项集得到候选k-项集，所以需要在合并之前需要增加一步来确保此对频繁（k-l)-项集的前(k-2)项是相同的。

Apriori算法的频繁项集产生过程有两个特点：第一，它的过程是—个逐层迭代（level-wise)的过程，即从频繁1-项集到项数最多的频繁项集，每次产生新的频繁项集都需要遍历一遍事务集：第二，它使用生成-剪枝的规则来产生频繁项集。在每次迭代产生新的候选项集时都要使用上一次发现的频繁项集, 然后计算每一个候选项集的支持度计数，再与给定的支持度阈值进行比较，删除支持度小于支持度阈值的候选项集。

Apriori算法实例：

下图是某商场交易记录：

 （a）连接C3=L2L2={{I1,I2},{I1,I3,{I1,I5}},{I2,I3},{I2,I4},{I2,I5}}  

 {{I1,I2},{I1,I3,{I1,I5}},{I2,I3},{I2,I4},{I2,I5}}=

（b）使用Apriori性质剪枝，频繁项集的所有非空子集也必须是频繁的。

{I1,I2,I3}的第二项子集是{I1,I2}，{I2,I3}和{I2,I3}。{I1,I2,I3}的所有2项子集都是L2的元素。因此，{I1,I2,I3}保留在C3中

{I1,I2,I5}的2项子集是{I1,I2}，{I1,I5}和{I2,I5}。{I1,I2,I5}的所有2项子集都是L2的元素。因此，{I1,I2,I5}保留在C3中。

{I1,I3,I5}的2项子集是{I1,I3}，{I1,I5}和{I3,I5}。{I3,I5}不是L2的元素，因而不是频繁的。因此从C3中删除{I1,I3,I5}。

{I2,I3,I4}的2项子集是{I2,I3}，{I2,I4}和{I3,I4}。{I3,I4}不是L2的元素，因而不是频繁的，因此，从C3中删除{I2,I3,I4}。

{I2,I3,I5}的2项子集是{I2,I3}，{I2,I5}和{I3,I5}。{I3,I5}不是L2的元素，因而不是频繁的，因此，从C3中删除{I2,I3,I5}

{I2,I4,I5}的2项子集是{I2,I4}，{I2,I5}和{I4,I5}。{I4,I5}不是L2的元素，因而不是频繁的，因此，从C3中删除{I2,I4,I5}

剪枝后C3={{I1,I2,I3},{I1,I2,I5}}。

 总之，Apriori的目的是取出哪些之间的联系是紧密的，进而退出他们之间的关系，基于以上规则，我们可以很好地发现事物之间的联系。  

参考文献：

[1]  康敏旸，张 安．改进的Apriori 数据挖掘算法的应用［J］．火力与指挥控制，2009，34(

10) :111 － 114

[2]  陈则芝，李冬梅． 数据挖掘关联规则Apriori算法的优化［J］． 山西大同大学学报(自然科学版),2008，24(4)，35-37．  

[3]  黄彦.基于高校人力资源的数据挖掘技术研究:[硕士学位论文].天津：天津大学,2004