Apriori算法

Apriori算法：
在获取关联规则时最常用的算法，找出事务数据集中存在的最大频繁项集，再利用最小置信度阈值来筛选最大频繁项集中的强关联规则。
支持度与置信度：
1）项集A,B同时发生的的概率称为支持度
2）项集A发生，则项集B发生的概率称为该关联规则的置信度

思路：
先用支持度作为筛选条件找出事务数据集中的频繁项集，再用置信度作为筛选条件找出频繁项集中的强关联规则。

举个例子：有五种商品，ABCDE，商场得到的订单数据集为

1.ABE
2.BD
3.BC
4.ABD
5.AC
6.BC
7.AC
8.ABCE
9.ABC

设置最小支持度为0.2，最小置信度为0.7

k =1 筛选频繁1项集，计算每个1项集的支持度：

A:6/9
B:7/9
C:6/9
D:2/9
E:2/9

所有集的支持度都大于0.2所以没有要被剪枝的。

k=2 筛选频繁2项集,2项集由1项集连接生成候选集：

AB:4/9
AC:4/9
AD:1/9
AE:2/9
BC:4/9
BD:2/9
BE:2/9
CD:0/9
CE:1/9
DE:0/9

根据最小支持度筛选出频繁项集

AB
AC
AE
BC
BD
BE

k = 3 ，由频繁2项集连接生成候选集，这里需要注意
1.连接生成k项集的条件是，他们中有k-1项是相同的。
2.频繁集的所有子集都是频繁集

候选集：

ABC:2/9
ABE:2/9

为什么没有ABD呢，因为ABD的一个子集AD并不是k=2项频繁集，根据法则频繁集的所有子集都是频繁集，将ABD筛掉了。
根据最小支持度筛选出频繁项集

ABC
ABE

k=4
同理可得：因为ABCE有自己不是频繁集，所以ABCE并不是频繁集。

这时已经得到了所有的频繁项集，接下来从频繁项集中筛选强规则：
简单的可以理解，2项频繁集可以筛选出1对1的规则，3项频繁机可以筛选出2对1的规则。

如下：

A-->B       0.66   
B-->A       0.57
A-->C       0.66    
C-->A       0.66
A-->E       0.3
E-->A       1
B-->C       0.57
C-->B       0.66
B-->D       0.28
D-->B       1
B-->E       0.28
E-->B       1

A-->B的置信度表示A发生的情况下，B发生的概率。
计算方法: P（AB）/P(A)

三项频繁集可以筛选出2对1的规则：

AB-->C   0.5
AC-->B   0.5
BC-->A   0.5
AB-->E   0.5
AE-->B     1 
BE-->A     1 

AB-->C的置信度表示AB发生的情况下，ABC发生的概率：
计算方法p(ABC)/P(AB)

设定的最小频繁集为0.7，经过筛选得到强关系为：E-->A，D-->B，E-->B，AE-->B，BE-->A。强关系表示的含义为，如果用户购买了E产品，那么他有很大的可能会同时购买A产品。得到了不同商品之间的关联规则，就可以根据经验对规则进行解析。