2.2Apriori算法

关联规则的挖掘分为两步：

①找出所有的频繁项集。其总体性能由第一步决定。在搜索频繁项集时，最简单的是Apriori算法。

②由频繁项集产生强关联规则。

1）、基本思想

①Apriori算法的名字基于一个事实：算法使用频繁项集性质的先验知识。

②Apriori算法使用一种称作逐层搜索的迭代方法，k-项集用于探索（k+1）-项集。

（1）基本知识：

③首先通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找出1-项集的集合。该集合记作L1。

④L1用于找频繁2-项集的集合L2，L2用于找L3。。。。。

⑤直到不能再找到频繁k-项集。

⑥最后再找Lk需要再一次数据库全扫描。

（2）综上，Apriori算法思想有两步：连接步和剪枝步。

（1、连接步：

①为了找出Lk ( 频繁k-项集 )，通过L（k-1）与自身连接，产生候选k-项集，记作Ck；

②其中L（k-1）的元素是可连接的。

（2、剪枝步：

①Ck是Lk的超集，即它的成员可以是也可以不是频繁的，但所有的频繁项集都包含在Ck中。

②扫描数据库，确定Ck中每个候选的计数，从而确定Lk（计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk）。

③Ck可能很大，这样涉及的计算量很大，为了压缩Ck，就要使用Apriori性质：任何非频繁的（k-1）-项集都不可能是频繁k-项集的子集（这个很重要，用于剪枝）。

④因此，如果一个候选k-项集的（k-1）-项集不在Lk中，则该候选项也不可能是频繁的，从而可以Ck中删除。

⑤这样子集测试可以使用所有频繁项集的散列树快速完成。

（3）优缺点：

①优点：算法思路简单，以递归为基础，生成频繁项集，易于实现 。       

②缺点：连接步骤需要大量的比较（在后面实例中会更加明白这一点）。

2）、算法步骤

①扫描全部数据，产生候选1-项集的集合C1。

②根据最小支持度，由C1产生频繁1-项集的集合L1。

③对k > 1，重复执行步骤 ④ ⑤ ⑥。

④由Lk执行连接和剪枝操作，产生候选（k+1）-项集的集合C（k+1）。

⑤根据最小支持度，由候选（k+1）-项集的集合C（k+1），产生频繁（k+1）-项集的集合L（k+1）。

⑥若L不为空集，则 k = k+1，跳往步骤 ④，否则到⑦

⑦根据最小置信度，由频繁项集产生强关联规则，结束。

3）、实例

商店的9笔交易，即 |D| = 9；设min_sup = 2

数据库事物列表事例

事物	商品ID的列表
T1	1,2,5
T2	2,4
T3	2,3
T4	1,2,4
T5	1,3
T6	2,3
T7	1,3
T8	1,2,3,5
T9	1,2,3

（1）第一次扫描

候选项集C1

项集	支持度计数
{1}	6
{2}	7
{3}	6
{4}	2
{5}	2

 

① 由候选项集  比较   候选支持计数  与   最小支持度计数   得到  频繁项集

②由于min_sup = 2，没有删除一项

频繁项集L1

项集	支持度计数
{1}	6
{2}	7
{3}	6
{4}	2
{5}	2

（2）第二次扫描

连接 L2 = L1∞L1（相互握手）产生候选2-项集 C2，因为没有剪枝，所以直接列出来了。

候选项集C2

项集	支持度
{1,2,}	4
{1,3}	4
{1,4}	1
{1,5}	2
{2,3}	4
{2,4}	2
{2,5}	2
{3,4}	0
{3,5}	1
{4,5}	0

进过和第一步一样的比较大于 min_sup = 2,得到的L2

频繁项集L2

项集	支持度计数
{1,2}	4
{1,3}	4
{1,5}	2
{2,3}	4
{2,4}	2
{2,5}	2

（3）第三次扫描

①连接步：C3 = L2 ∞ L2 ={{1,2,3}，{1,2,5}，{1,3,5,}，{2,3,4}，{2,3,5}，{2,4,5}}

②剪枝步：根据Apriori剪枝属性：频繁项集的所有非空子集也是频繁的。

例如：{1,3,5}的2-项的子集为{1,3}，{1,5}，{3,5}。但{3,5}不是L2的元素，即它是不频繁的，因此用C3中删去{1,3,5}。以此类推，进行检验。

候选项集C3

项集	支持度计数
{1,2,3}	2
{1,2,5}	2

与 min_sup = 比较，得L3

频繁项集L3

项集	支持度计数
{1,2,3}	2
{1,2,5}	2

（4）第四次扫描

①连接步：C4 = L3 ∞ L3 ={{1,2,3,5}} 

②剪枝步：由于C4的子集{2,3,5}不在L3中，所有该项删除

这样C4 =  Φ ，算法终值，找出了所有的频繁项集。

4）、程序实现（matlab）

（1）数据库

将上面的事物列表转化成为事务矩阵，对于每个事务中含有的物品标记为1，没有的标记为0

事务

	物品1	物2	物3	物4	物5
T1	1	1	0	0	1
T2	0	1	0	1	0
T3	0	1	1	0	0
T4	1	1	0	1	0
T5	1	0	1	0	0
T6	0	1	1	0	0
T7	1	0	1	0	0
T8	1	1	1	0	1
T9	1	1	1	0	0

（2）程序实现

（1、读数据代码

参数：

data：表数据，apriori（）函数：apriori算法，第一个参数数据，第二个参数最小支持度

（2、apriori（）函数代码

参数：

D：数据，min_sup：最小支持度，L：频繁项集和支持度，A：频繁项集，init（）函数：对数据集进行初始化。k：第k-频繁项集，A：第k-1次频繁项集，apriori_gen（）函数：产生候选项集Ck，C：候选项集，M：带支持度的候选项集，get_k_itemset（）函数：产生k-项频繁项集

（3、初始化init（）函数代码

参数：

n：列数，size（）函数：矩阵行、列大小函数，eye（）函数：返回n*n的矩阵，则A = n*n矩阵，sum（）：求和函数,上面的是列求和，则B矩阵就是实例中候选项集C1的支持度，A ( i , : )：取A矩阵的第 i 行的所有列，[A  B']：B先转置，然后和A拼接，此时L：含有项集和支持度计数。

（4、apriori_gen（）函数代码

参数：

zeros（）函数：生成m*n的零矩阵，该处是一列n行的零矩阵。A：为初始化中的A = n*n矩阵。

（5、get_k_itemset（）函数的代码

     

（6、isExit（）函数代码

（3）结果

频繁项集的0-1映射矩阵

前5列表示商品1,2,3,4,5，第六列表示支持度计数

该结果与实例中的频繁项集和支持度计数一样