⼤⽩话解析Apriori算法python实现（含源代码详解）
⼤⽩话解析Apriori算法python实现（含源代码详解）
本⽂为博主原创⽂章，转载请注明出处，并附上原⽂链接。
原⽂链接：
前⾔：Apriori算法是关联规则挖掘算法，也是最经典的算法。(它的进阶算法有FpGrowth算法，通过构造⼀个树结构来压缩数据记录，使得挖掘频繁项集只需要扫描两次数据记录，且该算法不需要⽣成候选集合，具体算法实现及python实现，可以移步到我另⼀篇博客–>)
Apriori算法是为了发现事物之间的联系的算法，⽐如我们熟知的啤酒与尿布故事，某超市在对顾客购物习惯分析时，发现，男性顾客在购买婴⼉尿⽚时，常常会顺便搭配⼏瓶啤酒来犒劳⾃⼰，于是尝试推出了将啤酒和尿布摆在⼀起的促销⼿段，最后使得啤酒与尿布销量双双提升。
我们的Aprioir算法就是为了发现这样的关联⽽产⽣的，在⽂章中我会尽量⽤通俗的语⾔，讲解这个算法的思路，由于笔者⽔平有限，⽂章可能太过冗余，敬请谅解。
⼀、专业名词解释
假如现在有⼀组购物数据，共4条记录，每条记录都是⼀个顾客在超市购买商品产⽣的数据（我们只关⼼顾客买的种类，不关⼼它买了这类商品的数量，因为我们要到是商品种类之间的关联，不是数量的关联）。
现在假设有5种商品，A B C D E，为了程序实现，把它换成数字表⽰更好⼀点A–>1, B–>2, C–>3, D–>4, E–>5 。
下⾯是这4条数据，把种类ABCDE换成数字 1 2 3 4 5。
[A C D] --> 1 3 4
[B C E] --> 2 3 5
[A B C E] --> 1 2 3 5
[B E] --> 2 5
1、什么是关联规则
现在有⼀个⼈，超市⽼板⼩红，她拿到了这组数据，想出哪些商品是有关联的，关联是什么意思呢？
举个例⼦，⽐如，你想买个泡⾯，你⼀桶⾯不够吃，两桶吃不了，你是不是就想，要不我在顺便买个⾹肠？还不够！在加个蛋呢？实在不⾏，再加个鸡腿！
好了，现在你就明⽩了，泡⾯、⾹肠、鸡蛋、鸡腿，这4个商品可能就是关联的，如果超市把这⼏个放在⼀起，你在买泡⾯的时候，是不是⼀不⼩⼼就多消费了（万恶的资本家啊），你就会不由感受到，现在连泡⾯都吃不起了。
2、⽀持度
继续思考怎样出这些关联商品，⼩红现在有4条数据记录（实际的超市，每天产⽣的数据可能上千，我们这⾥就简化⼀点，⽅便理解），⼩红很聪明，她认为，如果某⼀种商品组合（这个组合，可以是1个，或者2个，甚⾄3个以上的不同种类商品的组合），在整条数据库中出现的次数太少，那我就认为他们没有关联， 这个道理很显然，⽐如，商品组合AB，假如A是⽩酒，B是头孢（不要问我为什么超市会卖药，反正它现在就得卖→_→），这两个⼀起吃可能会中毒，那么你在买酒的时候肯定不会刻意去买头孢吧（不要说是给⼥朋友买的￣へ￣，来⾃单⾝狗的怨念），换句话说，如果你买了A，⼤概率不会买B，甚⾄会刻意不去买B，那么AB同时出现在⼀条购物记录的次数必然不会太多，因此可以认为两者没有关联。
那⼩红⼜在想，这个商品组合出现的次数⼩于多少，我才认为它是⽆关联的呢？
这个次数可以随意规定，我们称为⽀持度。但你试想⼀下，如果这个数定的太⼩，连 酒 和 头孢 您都认为有关联，然后 你把这两个摆在⼀起卖，显然不合适，算法意义也不⼤。如果定的太⾼，很多商品本来有关联，结果你定的太⾼，这些商品组合出现次数都不能满⾜这个数，那么这些商品组合你也就不出来，算法也就失去了意义。所以这个值⼀定要取的合适才好。
这个取值就称为 最⼩⽀持度。
对应于我们⽂中的例⼦，
A在四条记录中出现了2次，它的最⼩⽀持度min_support(A)=2，这是以它出现的次数作为最⼩⽀持度。
还可以⽤A出现的概率来表⽰，就是 A出现的次数 ÷ 总记录次数
A出现的次数是2，我们总共有4条数据，最⼩⽀持度也可以表⽰为：
min_support(A)=2/4=0.5
在看⼀下BE的最⼩⽀持度：
BE同时出现的次数为3次，总记录数依旧是4条，
那 min_support(BE)=3 或 min_support(BE)=3/4
（在代码中⽤那种形式表⽰都可以，表⽰的意义是⼀样的）
3、置信度
⼩红⼜要开始想了（前⾯提到过她很聪明，⼿动狗头），只⽤次数⼤⼩来确定是否关联，是不是太草率了，假如你去买泡⾯，这个⽉钱快见底了（肯定啊，谁有钱会吃泡⾯），你打算买3或4包，到了地⽅，⾥⾯有很多⼝味的，⽐如⿇辣，原味，三鲜，酸菜，但你就喜欢⿇辣的，本来是想全买⿇辣⼝味的，可惜的是每种⼝味都只剩2包了，⽆奈之下，你买了2包⿇辣，还有1包酸菜的，⾛之前还拿了个蛋，，，这个时候你的这条购物信息是 {⿇辣， 酸菜， 蛋}，前⾯说了，我们不关⼼数量，只关⼼种类。
这个时候，虽然购物记录⾥⾯有 ⿇辣，和酸菜两种物品，但你要知道，你刚开始是想全买⿇辣的，是因为⿇辣的没了，才买了酸菜。虽然{⿇辣，酸菜}同时出现了，且在计算⽀持度时，还提供了次数，可能会误认为⿇辣和酸菜是 相关的，但其实你知道你是⽆奈才选的酸菜泡⾯，⿇辣和酸菜并不是相关的，甚⾄顾客在买⿇辣⼝味的时候，刻意不会去购买酸菜⼝味的泡⾯，它们是反相关的。
如果能计算出，顾客在买了⿇辣的情况下，同时买了酸菜的概率多好啊，如果这个概率⼤，就表明顾
客买了⿇辣的，还要买酸菜的情况不是偶然，顾客就是同时喜欢吃这两种⼝味，每次买泡⾯，总是同时买这两种⼝味，两种⼝味是关联的。如果概率⼩，就表明顾客只喜欢其中⼀种⼝味，买酸菜是因为⽆奈之举，超市没货了。
现在就清楚了，我们算⼀下这个概率，很明显是条件概率的计算，⽤AB表⽰这两种商品，则 AB同时出现的次数 ÷ A出现的次数，就是顾客在买A的前提下，⼜买了B的概率，这个概率⼜称为 置信度，这个式⼦的意思表⽰，对于顾客 <；买了A，同时⼜买了B的⾏为> 有多少⾃信，有多少把握，认为这个商品组合是有关联的。
和⽀持度类似，我们也得⾃⼰确定⼀个数，称为最⼩置信度，⼤于这个数就认为这个商品组合有关联。
下⾯对于⽂章给出的数据计算⼀下置信度：以BC为例
如：BC同时出现的次数为2，B单独出现的次数为3，
则置信度confidence（C–>B）=2/3，称为顾客 <；买了C的情况下，⼜买了B的这个⾏为> BC具有关联性质的把握为2/3，换句话说，就是顾客买了C后，有 2/3 的概率去买B。
再算⼀下 顾客买了B的情况下，⼜买了C的置信度是多少，
BC同时出现的次数依旧为2，C单独出现的次数为3
confidence（B–>C）=2/3，称为顾客 <；买了B的情况下，⼜买了C的这个⾏为> 的可信度2/3，换句话说，就是顾客买了C后，有 2/3的概率去买B。
（当然，我们使⽤的数据太少，有些数据计算出来是100%，这完全是巧合，如果数据⾜够⼤，这个概率就就不会这样夸张了）
要注意 ：只有当这个商品组合的⽀持度⼤于它的最⼩⽀持度并且置信度⼤于最⼩置信度，我们才认为这个商品组合是强关联的，我们称这个商品组合为频繁项集。（为了简化代码，我仅仅只⽤了⽀持度，如果某种商品组合的⽀持度 ⼤于 最⼩⽀持度，就认为是频繁项集。并没有⽤到最⼩置信度，，如果读者有能⼒，可以⾃⼰做出改进，只需要在求频繁项集的时候，在保持这种商品组合的⽀持度⼤于最⼩⽀持度的情况下，同时保证该商品组合的置信度 ⼤于 最⼩置信度 即可。）
(从公式可以看出，AB同时出现的次数其实就是AB的⽀持度，A单独出现的次数就是A的⽀持度，⽀持度可以⽤次数表⽰，也可以⽤频率表⽰，如⽤概率表⽰，则置信度confidence公式如下)
4、提升度
（也是⼀个度量某种商品组合是否为频繁项集的量（和⽀持度，置信度类似），⼤家可以了解⼀下，这个量我在代码中也没有体现，就是为了简化代码）
这时候⼩红还觉得不放⼼，她⼜思索了⼀下，发现这样⼀种情况：假如原来⼀个商品X，在总记录中出现的概率是80%（也就是⽀持度），但是XY两种商品同时出现的概率是50%，是不是在⼀定程度上，Y商品的出现反⽽降低了原来的商品X的销售额？
我们⾸先来看⼀个式⼦，
分析这个式⼦，对于P（AB），
1. 如果A，B两个相互独⽴，即A发⽣不会影响到B，那么P（AB）=P(A)P(B)，显然，最后这个式⼦结果为1
2. 如果A，B不独⽴，即A发⽣会影响到B的发⽣，但是要注意，我们不能确定这个影响是什么类型，
即A发⽣可能导致B发⽣的概率增
加，也有可能A发⽣会导致B发⽣的概率减⼩。
上⾯这个式⼦就是提升度计算公式，即提升度 Lift（A–>B）为：
例⼦，我们来看⼀下⽂章给出的数据，⽐如BC：
BC同时出现的次数为2，⽀持度support（B–>C）=2/4
C单独出现的次数为3，⽀持度support（C）=3/4
B单独出现的次数为3，⽀持度support（B）=3/4
由以上数据可计算出B–>C的置信度，
confidence（B–>C）= support(B–>C) ÷ support(B) = 2/3
则提升度：
Lift(B–>C)=confidence(B–>C) ÷ support( C) = 8/9
因为提升度⼩于1，所以可以确定，购买B时，会降低对C的购买，如果计算出来提升度⼤于1，说明购买B时，会促进C的购买。
⼆、算法思路
先来看两个定律：
Apriori定律1 ：如果某商品组合⼩于最⼩⽀持度，则就将它舍去，它的超集必然不是频繁项集。
Apriori定律2 ：如果⼀个集合是频繁项集，即这个商品组合⽀持度⼤于最⼩⽀持度，则它的所有⼦集都是频繁项集
俩个定律都很容易理解，举个例⼦，
-对于定律1，假如有AB这个商品组合，它的出现的次数⼩于2，那么你还会指望ABC同时出现的次数
⼤于2吗？
-对于定律2，假如ABC同时出现的次数⽐2⼤，那么不管是AB、AC、BC它门同时出现的次数⾄少不会⽐2⼩把。
如何实现算法？有两步
1、出所有频繁项集。
就是该商品组合的⽀持度 ⼤于 最⼩⽀持度
2、由频繁项集确定下⼀组候选集。（在下⾯的讲解中有具体说明）
（1）第⼀次扫描
⾸先，求第⼀次扫描数据库后的候选集。
从图中可以看出，第⼀次扫描后，可以求出单个商品的⽀持度（图中⽀持度⽤出现次数表⽰），这个表称为第⼀次候选集，即下图所⽰：
在第⼀次候选集基础上，求出第⼀次频繁项集，频繁项就是该商品的⽀持度 ⼤于 最⼩⽀持度，⽀持度选择时随意的，在这⾥取最⼩⽀持度
为 min_support=2
那么第⼀次频繁项集就是第⼀次候选集中，⽀持度⼤于或等于2的所有商品集合。即下表，（把 D 商品从表中去除了，因为它的⽀持度⼩于
源代码电影讲解2）
先求出第⼆次的候选集。即在第⼀次频繁项集的基础上，出第⼆次候选集，对商品进⾏组合，形成⼀个2元组，4种商品，不同组合有C 种，即 4x3=12 种，形
成的表称为第⼆次候选集表。如下图
在求第⼆次频繁项集
对于上表，求出这两种商品同时出现在总记录中的次数（即求⽀持度），然后去掉⽀持度⼩于2的商品组合，形成的表即为第⼆次频繁项
集。如下表
（3）第三次扫描
先求出第三次的候选集。
即在第⼆次频繁项集的基础上，出第三次候选集。
就是将原来的2元组，拓展为3元组，怎么拓展呢？
设K为第K次扫描，要求第K个候选集，出上⼀次扫描的频繁项集，然后观察⾥⾯的记录，对于⾥⾯的每个记录，前（K-2）个前缀相同的，归为⼀类，在同⼀类别中进⾏合并。
⽐如 这第三次扫描，要求出它的候选集，先出上次扫描形成的第⼆次频繁项集表，⾥⾯有4条记录，分别为，AC，BC，BE，CE，这些记录中，前（K-2）个前缀，就是前（3-2）个前缀，也就是第⼀个前缀相同的归为⼀类，接着在属于同⼀类的记录中，进⾏合并，⽐如BC，BE，它门的第⼀个前缀都是B，那么在这⼀类中，把它门合并起来就形成了BCE。还剩下AC、CE，它门第⼀个前缀不相同，也没有其他元素和它门相同，那么就不⽤去管了。如果你⾮要合并，把AC、CE合并为ACE，我们看⼀下ACE的⼦集，它的⼦集是{AC、CE、AE}，可以看出AC、CE确实是频繁项集，但是AE呢，你在求第⼆次的候选集时，因为AE的⽀持度⼩于2，你把它去除了，那么ACE也必然不是频繁项集。（Apriori定律1 ：如果某商品组合⼩于最⼩⽀持度，则就将它舍去，它的超集必然不是频繁项集。）
-----------在这⾥要说明⼀下减枝的概念
⽐如刚才新形成的BCE这个组合，它的⼦集是{BC、CE、BE}，显然BC和CE本来就是⼀个频繁项集，但是CE呢，我们必须对⽐上⼀次频繁项集中的元素，也就是第2次频繁项集的元素，如果CE不是第⼆次频繁项集的元素，那么就把新形成的 BC E 这个元素给 “减去”，也就是减枝，这⼀点我在代码中有体现，具体请看后⾯的代码。
（4）第四次扫描和前两次原理，⼀样，留给读者做练习。
最后值得⼀提的是，当最后⽣成的候选集表中，只有0个或1个的话，循环就结束了。
三、python 代码实现
运⾏环境： python3.6 PyCharm编译器
⾸先给出运⾏结果42

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。