关联规则Apriori算法

1.前置知识

经典应用场景：购物车商品的关联规则。 

符号表示： 

I代表项集,项是可能出现的值，例如购物车中能有尿布、啤酒、奶粉等，I={尿布、啤酒、奶粉}，尿布是项 

K代表I中包含的项的数目，上面的k=3 

事务T，是项的子集,一个父亲进入超市买了啤酒和尿布，这里的事务是{尿布，啤酒} 

D代表事务库，相当于超市的系统账单 

支持度（存在数量）：support(尿布奶粉) = 包含尿布奶粉的事务条数/总的事务条数，换句话说，尿布奶粉同时购买的购物记录条数/超市总的购物记录条数 ,绝对支持是出现次数，相对支持是频率。一般都是说的P,频率。

可信度/置信度：confidence(A->B) = support(AB)/support(A),也就是单从包含A的购物记录中找出B存在的记录，得到一个存在比值。 

频繁项集：也就是项集出现的频率>minsup(最小支持度)。 

强关联规则 R ：关联项集频率>minsup and 关联项集置信度>minconf 

提升度LIFT：顾名思义：LIFT(A=>B)代表商品 A 的出现，对商品 B 的出现概率提升的”程度 。所以提升度公式是 AB置信度/B支持度 = P（A->B）/P(B) = P(AB)/(P(A)*P(B))。这个公式背后的意思就是      B在含A事务集中的占比/B在所有事务中的占比。 

提升度>1代表关联关系强，=1代表没有关系，<1代表 负 关联关系。 

性质**：频繁项集的子集仍为频繁项集，非频繁项集的超集仍为非频繁项集。 

很好理解，频繁项集出现多少次，子集就出现多少次，当然频繁。非频繁项集出现频率低，包含它的超集出现次数只能是最多等于它。 

2.Apriori-找关联规则的算法 

关联规则的寻找分为两步：1.寻找频繁项集 2.从频繁项集中寻找>=最小置信度的规则 

频繁项集用Lk表示，可能包括频繁项集的集合用Ck表示（C全名可能是Collection？）。k代表集合中项的个数。 

Apriori是从频繁1项集L1生成频繁2项集L2，再用频繁2项集L2生成频繁3项集L3的算法.又名Level-wise.

具体过程：首先项集itemsets里的每一条项集itemset里的项item必须按照排序,如果是名字，按拼音排序，排序后是为了方便比对，从Lk-1生成Lk,需要用 Lk-1和 Lk-1进行组合生成组合，组合的规则是循环拿出itemset1（记作l1） in Lk-1,itemset2（记作l2） in Lk-1,l1、l2前 k-2个数 必须相同，l1、l2最后一个数坐标是k-1必须不同。例如 l1 {橘子，苹果，牛奶}和l2{橘子，苹果，汽水}，我要生成4项集，就要比对橘子=橘子，苹果=苹果，最后一个数牛奶！=汽水，然后组合在一起是{橘子，苹果，牛奶，汽水}。但是这种两两比对的方式会生成很多组合集，再拿去在总的事务库中扫描每一条事务记录，看是不是频繁项集，这样的搜索次数非常高。由此，Apriori算法引入先验属性。 

先验属性剪枝就是，生成一个剪枝过的Ck，再到数据库里去搜索，剪枝过的Ck子集都是频繁子集，但是不能保证它本身就是频繁项集，生成Ck之前看到每一条itemset如果有k-1子项集不在Lk里的，删去，循环操作，生成Lk.因为上面所说的性质，也叫先验知识丢弃会剪枝，减少工作量的意思）。先从事务库D生成频繁项集L1,再从L1生成C2。这里就是因为不频繁项集的超集一定是不频繁项集，那我们就只能从L1中选取项集生成C2. 

// 伪代码input:D(事务集),min_sup
output:L（频繁项集itemsets）L1 = find_fre_1_itemset(D); //这里先生成C1,还是L1都是一样的
for（k=2;Lk-1不为空;k++){Ck = apriori_generation(L k-1) //先验属性生成Ckfor each t 属于 D{ //循环扫描事务库集Ct = find_subsets(Ck,t) //找到事务库事务中也存在的 候选频繁项集（Ck中的）for each c 属于 Ct{c.count++ //循环将频繁项集的数量属性加1}}Lk = {c属于Ck|c.count>=min_sup}
}
return L(所有频繁项集)// 找到候选K项集
apriori_generation(Lk-1)for each itemset l1 in L k-1{for each itemset l2 in L k-1{// 集合要排序对齐，后面还要剪枝if (l1[0]==l2[0]) and (l1[1]==l2[1]) and ... and(l1[k-1]<l2[k-1]){c = l1Xl2}if has_infrequent_subsets(c,Lk-1){delete c}else{add c into Ck}}}return Ck//先验属性剪枝
has_infrequent_subsets(c,Lk-1)for each k-1 subset s in c{if s 不属于 Lk-1{return True}}return False

实际举例

0.输入

D：

	事务
1	I1,I2,I3,I4,I7
2	I2,I3,I4,I5,I7
3	I1,I3,I4I7
4	I3,I4,I7
5	I2,I3,I4,I5,I6,I7

min_sup = 2

1.生成L1

候选1项集	sup_count
I1	2
I2	3
I3	5
I4	5
I5	2
I6	1
I7	5

min_sup筛选一下（写候选1的这个步骤也可以省去）

L1

I1	2
I2	3
I3	5
I4	5
I5	2
I7	5

2.生成候选2项集C2

L1XL1:

{I1，I2},{I1,I3},{I1,I4},{I1,I5},{I1,I7},

{I2,I3},{I2,I4},{I2,I5},{I2,I7}

{I3,I4},{I3,I5},{I3,I7}

{I4,I5},{I4,I7}

{I5,I7}

剪枝

注意候选2项集比较特殊，不用剪枝，因为k-1子集是频繁1项集，全部符合min_sup.后面的C3..Ck要剪枝。

3.生成L2

用c2循环事务库D，过滤不频繁项集

得

{I1,I3},{I1,I4},{I1,I7},

{I2,I3},{I2,I4},{I2,I5}，

{I3,I4},{I3,I5},{I3,I7}

{I4,I5},{I4,I7}

{15，17}

4.生成C3

L2XL2:

{I1,I3,I4}（这举个例子，是I1,I3和I1,I4组合，那主要看I3,I4是不是频繁项集来剪枝）,{I1,I3,I7},{I1,I4,I7}

{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}

{I3,I4,I5},{I3,I4,I7},{I3,I5,I7},

{I4,I5,I7}

剪枝，循环每一个2项集看在不在L2里，都在。

5.生成L3

用c3循环事务库D，过滤不频繁项集

得

{I1,I3,I4},{I1,I3,I7},{I1,I4,I7}

{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}

{I3,I4,I5},{I3,I4,I7},{I3,I5,I7},

{I4,I5,I7}

6.生成C4

L3XL3

{I1,I3,I4,I7}(记得顺序，{I1,I3,I4}和{I1,I4,I7}合不上，因为I1=I1,I3!=I4第二步不等于就结束了，为什么要前面全等于，最后一个不等于，如果能合得上有{I1,I3,I4,I7},那一定存在{I1,I3,I4}和{I1,I3,I7}是频繁项集，这个例子在上一步集合比较就已经出来这个结果了)

{I2,I3,I4,I5}

{I3,I4,I5,I7}

子集都在频繁项集，不剪枝。

7.生成L4

用C4循环事务库D，过滤不频繁项集

得

{I1,I3,I4,I7}

{I2,I3,I4,I5}

{I3,I4,I5,I7}

8.C5集合为空(第一个数没有相同得,l1!=I2,I1!=I3,I2!=I3)

9.L5集合为空，返回全部频繁项集

reference:

[1]Han Jiawei ,Kamber Micheline , Pei,Jian ."data mining "3rd ed 253 page