数据挖掘之关联规则挖掘（Apriori算法） - 好文

一、概述

本篇博文主要阐述数据挖掘相关的关联规则挖掘的算法（Apriori算法）。主要介绍关联规则的基本概念、Apriori算法原理和Apriori算法实例，文章末尾处附加Apriori算法源程序。

二、关联规则挖掘的基本概念

关联规则挖掘发现大量数据中项集之间有趣的关联关系。如果两项或者多项属性之间存在关联，那么其中一项的属性可以依靠其他属性值进行预测。

关联规则挖掘问题可以分为两个子问题：1、找出事物数据库中所有大于等于用户指定的最小支持度的数据项集；2、利用频繁项集生成所欲需要的关联规则，根据用户设置的最小置信度进行取舍，最后得到强关联规则。

2.1、项与项集

数据库中不可分割的最小单位信息称为项，用符号i表示。项的集合称为项集，用 I 表示。项集的个数为k称为k-项集。比如，集合{啤酒、尿布、奶粉}称为3-项集。

2.2、事物

事物数据库T={t1,t2,t3,....,tn}是由一系列具有唯一标识的事务组成的。每个事务ti（i=1,2,3,4,5....,n）包含的项集都是I的子集。

2.3、项集的频数（支持度计数）

包括项集的事务个数称之为项集的频数（支持度计数）

2.4、关联规则

关联规则x==>y 的蕴含式。其中x，y都是I的真子集，并且x∩y=∅。x称之为前提，y称之为结果。关联规则反应x中的项目出现时，y中项目也跟着出现的规律。

2.5、关联规则的支持度（support）

关联规则的支持度是交易集中同时包含x和y的交易数和所有交易数之比。它反应了x和y中所包含的项在事务集中同时出现的概率，support（x==》y）

support(x==>y) = support(x∪y)=p(xy)

2.6、关联规则的置信度（confidence）

关联规则的置信度是交易集包含x和y的交易数与所有交易数和包含x的交易数之比。ji为confidence（x==>y）=
support（x∪y）/support（x）=p（y|x）

通常情况下，用户需要制定最小支持度的阈值和最小置信度的阈值。关联规则必须要满足这两种阈值。如果关联规则既满足大于等于最小置信度，并且大于等于最小支持度则成只为强关联规则，反之不是。通常我们所说的都是强关联规则。

项集U在T中所占的支持度的百分比就是他的支持度。support（U）=||{t∈T|U∈t}/||T||.对于项目集I，在事务数据库T中所满足用户指定的最小支持度的项目集，称之为频繁项目集。

项目集空间理论-----频繁项集的子集仍然是频繁项集，非频繁项集的超集是非频繁项目集。

3、关联规则挖掘算法------Apriori算法原理

3.1、Apriori算法的基本思想

Apriori算法的基本思想是通过对数据库的多次扫描来计算项集的支持度，发现所有的频繁项集从而生成关联规则。Apriori算法对数据集进行多次扫描。第一次扫描得到频繁1-项集的集合L1，第K（k>1）次扫描首先利用第(k-1)次扫描的结果Lk-1来产生候选集k-项集的集合Ck，然后在扫描的过程中确定Ck的支持度。最后，在每次扫描结束时计算频繁k-项集的集合Lk，算法在候选集k-项集的集合Ck为空时结束。

3.2、Apriori算法产生频繁项集的过程

产生频繁项集的过程只要分为连接和减枝两步：

1、连接：为找到Lk（k>1）,通过Lk-1与自身做连接产生候选k-项集的集合Ck。设l1,l2是Lk-1中的项集。记li[j]表示li的第j个项。Apriori算法假定事务或项集中的项按字典次序排序;如果Lk-1的元素l1,l2的前k-2项相等，l1的k-1项小于l2的k-1项，则可以认为l1和l2可以做连接。连接结果（l1[1],l1[2],l1[3],l1[4],.......,l1[k-1],l2[k-1]）

2、减枝：由Apriori的性质可知，频繁项集k-项集的任何子集都是必须是频繁项集，由连接生成的集合Ck需要进行验证，去除不满足支持度的非频繁k-项集。

3.3、Apriori算法的主要步骤

* 扫描全部数据，产生候选1-项集的集合C1.
* 根据最小支持度，由候选1-项集的集合C1产生频繁1-项集的集合L1.
* 对k>1,重复执行步骤4,5,6
* 由Lk执行连接和减枝操作，产生候选k+1-项集的集合Ck+1
* 根据最小支持度，由候选（k+1）-项集的集合Ck+1，产生频繁（k+1）-项集的集合Lk+1
* 若L不等于∅，则k=k+1，步骤跳4，否则结束
* 根据最小置信度，由频繁项集产生强关联规则，结束
3.4、Apriori算法描述

输入：数据库D，最小支持度阈值min_sup。

输出：D中的频繁集L.

Begin

L1=1-频繁项集

for（k=2；Lk-1≠∅；k++）do begin

Ck=Apriori_gen(Lk-1);{调用函数Apriori——gen（Lk-1）通过频繁（k-1）-项集产生候选k-项集}

for所有数据集t∈D do begin {扫描D用于计数}

Ct=subset(ck,t);{用sbuset找出该事务中候选的所有子集}

for所有候选集c属于Ct，do

c.count++

end;

Lk={c∈Ck|c.count>=min_sup}

end

end

return L1∪L2∪......∪Lm{形成频繁项集的集合}

3、Apriori算法实例

热门工具换一换