设计本网站是用什么做的,官方小程序开发,做网站营业范围,巴中手机网站建设1.前置知识
经典应用场景#xff1a;购物车商品的关联规则。
符号表示#xff1a;
I代表项集,项是可能出现的值#xff0c;例如购物车中能有尿布、啤酒、奶粉等#xff0c;I{尿布、啤酒、奶粉}#xff0c;尿布是项
K代表I中包含的项的数目#xff0c;上面的k3
事…1.前置知识
经典应用场景购物车商品的关联规则。
符号表示
I代表项集,项是可能出现的值例如购物车中能有尿布、啤酒、奶粉等I{尿布、啤酒、奶粉}尿布是项
K代表I中包含的项的数目上面的k3
事务T是项的子集,一个父亲进入超市买了啤酒和尿布这里的事务是{尿布啤酒}
D代表事务库相当于超市的系统账单
支持度存在数量support(尿布奶粉) 包含尿布奶粉的事务条数/总的事务条数换句话说尿布奶粉同时购买的购物记录条数/超市总的购物记录条数 ,绝对支持是出现次数相对支持是频率。一般都是说的P,频率。
可信度/置信度confidence(A-B) support(AB)/support(A),也就是单从包含A的购物记录中找出B存在的记录得到一个存在比值。
频繁项集也就是项集出现的频率minsup(最小支持度)。
强关联规则 R 关联项集频率minsup and 关联项集置信度minconf
提升度LIFT顾名思义LIFT(AB)代表商品 A 的出现对商品 B 的出现概率提升的”程度 。所以提升度公式是 AB置信度/B支持度 PA-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频繁项集itemsetsL1 find_fre_1_itemset(D); //这里先生成C1,还是L1都是一样的
fork2;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.countmin_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
事务1I1,I2,I3,I4,I72I2,I3,I4,I5,I73I1,I3,I4I74I3,I4,I75I2,I3,I4,I5,I6,I7 min_sup 2
1.生成L1
候选1项集sup_countI12I23I35I45I52I61I75
min_sup筛选一下写候选1的这个步骤也可以省去
L1
I12 I2 3I35I45I52I75 2.生成候选2项集C2
L1XL1:
{I1I2},{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}
{1517}
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}合不上因为I1I1,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
