机器学习-非监督分类算法之关联规则
一、什么是关联规则Association Rule
所谓数据挖掘就是以某种方式分析源数据，从中发现一些潜在的有用的信息，即数据挖掘又可以称作知识发现。而机器学习算法则是这种“某种方式”，关联规则作为十大经典机器学习算法之一，因此搞懂关联规则（虽然目前使用的不多）自然有着很重要的意义。顾名思义，关联规则就是发现数据背后存在的某种规则或者联系。关联规则挖掘的目的就是找出强关联规则，从而指导商家的决策。
经典例子是尿布和啤酒，除此之外，举个简单的例子：通过调研超市顾客购买的东西，可以发现30%的顾客会同时购买床单和枕套，而在购买床单的顾客中有80%的人购买了枕套，这就存在一种隐含的关系：床单→枕套，也就是说购买床单的顾客会有很大可能购买枕套，因此商场可以将床单和枕套放在同一个购物区，方便顾客购买。
一般，关联规则可以应用的场景有：
-
- 优化货架商品摆放或者优化邮寄商品的目录
- 交叉销售或者捆绑销售
- 搜索词推荐或者识别异
二、必备概念
- 项目：交易数据库中的一个字段，对超市的交易来说一般是指一次交易中的一个物品，如：牛奶
- 事务：某个客户在一次交易中，发生的所有项目的集合：如｛牛奶，面包，啤酒｝
- 项集：包含若干个项目的集合（一次事务中的），一般会大于0个
- 支持度：项集｛X，Y｝在总项集中出现的概率
- 频繁项集：某个项集的支持度大于设定阈值（人为设定或者根据数据分布和经验来设定），即称这个项集为频繁项集。
- 置信度：在先决条件X发生的条件下，由关联规则｛X->Y ｝推出Y的概率（见下面的例子）
- 提升度：表示含有X的条件下同时含有Y的概率，与无论含不含X含有Y的概率之比。
支持度和提升度示例：
假如有一条规则：牛肉—>鸡肉，那么同时购买牛肉和鸡肉的顾客比例是3/7，而购买牛肉的顾客当中也购买了鸡肉的顾客比例是3/4。这两个比例参数是很重要的衡量指标，它们在关联规则中称作支持度（support）和置信度（confidence）。
提升度示例：
1000名顾客，购买年货，A组有500人购买茶叶，有450人购买咖啡；B组有0人购买茶叶，有450人购买咖啡。
| 购买茶叶 | 购买咖啡 | |
| A组（500人） | 500 | 450 |
| B组（500人） | 0 | 450 |
茶叶->咖啡的支持度＝450/1000=45%
茶叶->咖啡的置信度＝450/500=90%
茶叶->咖啡的提升度＝90%／90%＝1
说明：
（1）由于lift(茶叶X->咖啡Y)＝1，所以说明X与Y相互独立，即是否有X对于Y的出现没有影响。虽然支持度和置信度都高，但它们之间没有必然的关联关系。
（2）满足最小支持度和最小置信度的关联关系叫做强关联关系
-
- 如果lift>1，叫做有效的强关联关系，
- 如果lift<=1，叫做无效的强关联关系
- 特别的如果lift（X->Y）＝1，则称X与Y相互独立
三、实现过程
从以上的分析可以得知，关联规则是从事务集合中挖掘出这样的关联规则｛X->Y｝：它的支持度和置信度要大于最小阈值（minSup，minConf），当然这个最小阈值是由用户指定的，可以根据数据分布和经验；同时他的提升度最好是大于1的（具体值根据实际情况设定，例如：3、5均可），即是有效强关联规则。
使用关联规则的过程主要包含以下三个步骤：
（1）数据筛选，首先对数据进行清洗，清洗掉那些公共的项目，比如：热门词，通用词（此步依据具体项目而定）
（2）根据支持度（support），从事务集合中找出频繁项集（使用算法：Apriori算法，FP-Growth算法）
（3）根据置信度（confidence），从频繁项集中找出强关联规则（置信度阈值需要根据实验或者经验而定）
（4）根据提升度（lift），从强关联规则中筛选出有效的强关联规则（提升度的设定需要经过多次试验确定）
关联规则中，比较关键的两个点是：（1）三种阈值的设定（三个阈值点需要经过对此实验或者经验才能找到合适的阈值）（2）如何找出频繁项集。
下节主要讨论如何解决寻找频繁项集的问题，目前主要有两种算法：（1）Apriori算法（2）FP-Growth算法，下面分别介绍一下这两种算法。
四、生成频繁项集－Apriori算法［1］
（1）算法原理
它主要利用了向下封闭属性：如果一个项集是频繁项目集，那么它的非空子集必定是频繁项目集。它先生成1-频繁项目集，再利用1-频繁项目集生成2-频繁项目集。。。然后根据2-频繁项目集生成3-频繁项目集。。。依次类推，直至生成所有的频繁项目集，然后从频繁项目集中找出符合条件的关联规则。
（2）生成频繁项集过程
它的原理是根据k-频繁项目集生成（k+1）-频繁项目集。因此首先要做的是找出1-频繁项目集，这个很容易得到，只要循环扫描一次事务集合统计出项目集合中每个元素的支持度，然后根据设定的支持度阈值进行筛选，即可得到1-频繁项目集。下面证明一下为何可以通过k-频繁项目集生成（k+1）-频繁项目集：（下面证明如何从K-频繁项集生成k+1频繁项集）
假设某个项目集S={s1，s2...，sn}是频繁项目集，那么它的（n-1）非空子集{s1，s2，...sn-1}，{s1，s2，...sn-2，sn}...{s2，s3，...sn}必定都是频繁项目集，通过观察，任何一个含有n个元素的集合A={a1，a2，...an}，它的（n-1）非空子集必行包含两项{a1，a2，...an-2，an-1}和 {a1，a2，...an-2，an}，对比这两个子集可以发现，它们的前（n-2）项是相同的，它们的并集就是集合A。对于2-频繁项目集，它的所有1非空子集也必定是频繁项目集，那么根据上面的性质，对于2-频繁项目集中的任一个，在1-频繁项目集中必定存在2个集合的并集与它相同。因此在所有的1-频繁项目集中找出只有最后一项不同的集合，将其合并，即可得到所有的包含2个元素的项目集，得到的这些包含2个元素的项目集不一定都是频繁项目集，所以需要进行剪枝。剪枝的办法是看它的所有1非空子集是否在1-频繁项目集中，如果存在1非空子集不在1-频繁项目集中，则将该2项目集剔除。经过该步骤之后，剩下的则全是频繁项目集，即2-频繁项目集。依次类推，可以生成3-频繁项目集。。直至生成所有的频繁项目集。
（3）生成强关联规则
得到频繁项目集之后，则需要从频繁项目集中找出符合条件的关联规则。最简单的办法是：遍历所有的频繁项目集，然后从每个项目集中依次取1、2、...k个元素作为后件，该项目集中的其他元素作为前件，计算该规则的置信度进行筛选即可。这样的穷举效率显然很低。假如对于一个频繁项目集f，可以生成下面这样的关联规则：（f-β）—>β，那么这条规则的置信度=f.count/(f-β).count
（下面证明如何生成强关联规则，即先生成小后件的，再根据小后件依次生成大后件，因为假设该规则是强关联规则，则（f-βsub）—>βsub也是强关联规则）
根据这个置信度计算公式可知，对于一个频繁项目集f.count是不变的，而假设该规则是强关联规则，则（f-βsub）—>βsub也是强关联规则，其中βsub是β的子集，因为(f-βsub).count肯定小于(f-β).count。即给定一个频繁项目集f，如果一条强关联规则的后件为β，那么以β的非空子集为后件的关联规则都是强关联规则。所以可以先生成所有的1-后件（后件只有一项）强关联规则，然后再生成2-后件强关联规则，依次类推，直至生成所有的强关联规则。
五、如何生成频繁项集－FP-Growth算法［4］
Apriori算法是关联规则的基本算法，很多用于发现关联规则的算法都是基于Apriori算法，但Apriori算法需要多次访问数据库，具有严重的性能问题。FP-Growth算法只需要两次扫描数据库，相比于Apriori减少了I/O操作，克服了Apriori算法需要多次扫描数据库的问题。本文采用如下的样例数据
| 1 2 3 4 5 6 7 8 9 | A;B;E; B;D; B;C; A;B;D A;C; B;C; A;C; A;B;C;E; A;B;C; |
（1）FP-Growth生成FP-Tree
FP-Growth算法将数据库中的频繁项集压缩到一颗频繁模式树中，同时保持了频繁项集之间的关联关系。通过对该频繁模式树挖掘，得到频繁项集。其过程如下：
图5.1 FT－Tree
图5.2 生成fp-tree的步骤
（2）从FP-Tree挖掘频繁项集
从FP-Tree重可以挖掘出频繁项集，其过程如下：
图5.3 频繁项集挖掘过程
从频繁1项集链表中按照逆序开始，链表可以追溯到每个具有相同项的节点。
（3）找出强关联规则
同第四节
（4）找出有效的强关联规则
同第四节
至此，FP－Growth算法生成频繁项集已经结束。
以上内容的参考文献是https://www.cnblogs.com/hdu-cpd/p/5987904.html，感谢博主
七、误导我们的强关联规则-关联规则评价准则
前面我们讨论的关联规则都是用支持度和自信度来评价的，如果一个规则的自信度高，我们就说它是一条强规则，但是自信度和支持度有时候并不能度量规则的实际意义和业务关注的兴趣点。
一个误导我们的强规则
看这样一个例子，我们分析一个购物篮数据中购买游戏光碟和购买影片光碟之间的关联关系。交易数据集共有10,000条记录，其中购买6000条包含游戏光碟，7500条包含影片光碟，4000条既包含游戏光碟又包含影片光碟。数据集如下表所示：
| 买游戏 | 不买游戏 | 行总计 | |
| 买影片 | 4000 | 3500 | 7500 |
| 不买影片 | 2000 | 500 | 2500 |
| 列总计 | 6000 | 4000 | 10000 |
假设我们设置得最小支持度为30%，最小自信度为60%。从上面的表中，可以得到：support(买游戏光碟—>买影片光碟)=4000/10000=40%，confidence(买游戏光碟—>买影片光碟)=4000/7500*100%=66%（写错了，应该是4000/6000）。这条规则的支持度和自信度都满足要求，因此我们很兴奋，我们找到了一条强规则，于是我们建议超市把影片光碟和游戏光碟放在一起，可以提高销量。
可是我们想想，一个喜欢的玩游戏的人会有时间看影片么，这个规则是不是有问题，事实上这条规则误导了我们。在整个数据集中买影片光碟的概率p(买影片)=7500/10000=75%，而买游戏的人也买影片的概率只有66%，66%<75%恰恰说明了买游戏光碟抑制了影片光碟的购买，也就是说买了游戏光碟的人更倾向于不买影片光碟，这才是符合现实的。
从上面的例子我们看到，支持度和自信度并不能过成功滤掉那些我们不感兴趣的规则，因此我们需要一些新的评价标准，下面介绍六中评价标准：相关性系数，卡方指数，全自信度、最大自信度、Kulc、cosine距离。
相关性系数lift
从上面游戏和影片的例子中，我们可以看到游戏和影片不是正相关的，因此用相关性度量关联规则可以过滤这样的规则，对于规则A—>B或者B—>A，lift(A,B)=P(A交B)/(P(A)*P(B))，如果lift(A,B)>1表示A、B呈正相关，lift(A,B)<1表示A、B呈负相关，lift(A,B)=1表示A、B不相关（独立）。实际运用中，正相关和负相关都是我们需要关注的，而独立往往是我们不需要的，两个商品都没有相互影响也就是不是强规则，lift(A,B)等于1的情形也很少，一般只要接近于1我们就认为是独立了。
注意相关系数只能确定相关性，相关不是因果，所以A—>B或者B—>A两个规则的相关系数是一样的，另外lift(A,B)=P(A交B)/(P(A)*P(B))=P(A)*P(B|A)/(P(A)*P(B))=P(B|A)/P(B)=confidence(A—>B)/support(B)=confidence(B—>A)/support(A)。
卡方系数
卡方分布是数理统计中的一个重要分布，利用卡方系数我们可以确定两个变量是否相关。卡方系数的定义:
公式中的observed表示数据的实际值,expected表示期望值,不理解没关系,我们看一个例子就明白了。
| 买游戏 | 不买游戏 | 行总计 | |
| 买影片 | 4000(4500) | 3500(3000) | 7500 |
| 不买影片 | 2000(1500) | 500(1000) | 2500 |
| 列总计 | 6000 | 4000 | 10000 |
上面表格的括号中表示的是期望值，(买影片，买游戏)的期望值E=6000*(7500/10000)=4500，总体记录中有75%的人买影片，而买游戏的有6000人，于是我们期望这6000人中有75%(即4500)的人买影片。其他三个值可以类似计算得到。现在我们计算一下，买游戏与买影片的卡方系数：
卡方系数X=(4000-4500)^2/4500+(3500-3000)^2/3000+(2000-1500)^2/1500+(500-1000)^2/1000=555.6。
卡方系数需要查表才能确定值的意义，基于置信水平和自由度(r-1)*(c-1)=(行数-1)*(列数-1)=1，查表得到自信度为(1-0.001)的值为6.63，555.6大于6.63，因此拒绝A、B独立的假设，即认为A、B是相关的，而expected(买影片，买游戏)=4500>4000,因此认为A、B呈负相关。这里需要一定的概率统计知识。如果觉得不好理解，可以用其他的评价标准。
全自信度
全自信度all_confidence的定义如下：all_confidence(A,B)=P(A交B)/max{P(A),P(B)}
=min{P(B|A),P(A|B)}
=min{confidence(A—>B),confidence(B—>A)}
对于前面的例子，all_confidence(买游戏，买影片)=min{confidence(买游戏—>买影片),confidence(买影片—>买游戏)}=min{66%,53.3%}=53.3%。可以看出全自信度不失为一个好的衡量标准。
最大自信度
最大自信度则与全自信度相反，求的不是最小的支持度而是最大的支持度，max_confidence(A,B)=max{confidence(A—>B),confidence(B—>A)}，不过感觉最大自信度不太实用。
Kulc
Kulc系数就是对两个自信度做一个平均处理：kulc(A,B)=(confidence(A—>B)+confidence(B—>A))/2。，kulc系数是一个很好的度量标准，稍后的对比我们会看到。
cosine(A,B)
cosine(A,B)=P(A交B)/sqrt(P(A)*P(B))=sqrt(P(A|B)*P(B|A))=sqrt(confidence(A—>B)*confidence(B—>A))
七个评价准则的比较
这里有这么多的评价标准，究竟哪些好，哪些能够准确反应事实，我们来看一组对比。
| milk | milk | 行总计 | |
| coffee | MC | MC | C |
| coffee | MC | MC | C |
| 列总计 | M | M | total |
上表中，M表示购买了牛奶、C表示购买了咖啡,M表示不购买牛奶，C表示不购买咖啡，下面来看6个不同的数据集，各个度量标准的值
| 数据 | MC | MC | MC | MC | total | C->M自信度 | M->C自信度 | 卡方 | lift | all_conf | max_conf | Kulc | cosine |
| D1 | 10000 | 1000 | 1000 | 100000 | 112000 | 0.91 | 0.91 | 90557 | 9.26 | 0.91 | 0.91 | 0.91 | 0.91 |
| D2 | 10000 | 1000 | 1000 | 100 | 12100 | 0.91 | 0.91 | 0 | 1.00 | 0.91 | 0.91 | 0.91 | 0.91 |
| D3 | 100 | 1000 | 1000 | 100000 | 102100 | 0.09 | 0.09 | 670 | 8.44 | 0.09 | 0.09 | 0.09 | 0.09 |
| D4 | 1000 | 1000 | 1000 | 100000 | 103000 | 0.50 | 0.50 | 24740 | 25.75 | 0.50 | 0.50 | 0.50 | 0.50 |
| D5 | 1000 | 100 | 10000 | 100000 | 111100 | 0.91 | 0.09 | 8173 | 9.18 | 0.09 | 0.91 | 0.50 | 0.29 |
| D6 | 1000 | 10 | 100000 | 100000 | 201010 | 0.99 | 0.01 | 965 | 1.97 | 0.01 | 0.99 | 0.50 | 0.10 |
我们先来看前面四个数据集D1-D4，从后面四列可以看出，D1,D2中milk与coffee是正相关的，而D3是负相关，D4中是不相关的，大家可能觉得，D2的lift约等于1应该是不相关的，事实上对比D1你会发现，lift受MC的影响很大，而实际上我们买牛奶和咖啡的相关性不应该取决于不买牛奶和咖啡的交易记录，这正是lift和卡方的劣势，容易受到数据记录大小的影响。而全自信度、最大自信度、Kulc、cosine与MC无关，它们不受数据记录大小影响。卡方和lift还把D3判别为正相关，而实际上他们应该是负相关，M=100+1000=1100，如果这1100中有超过550的购买coffee那么就认为是正相关，而我们看到MC=100<550，可以认为是负相关的。
上面我们分析了全自信度、最大自信度、Kulc、cosine与空值无关，但这几个中哪一个更好呢？我们看后面四个数据集D4-D6,all_conf与cosine得出相同的结果，即D4中milk与coffee是独立的，D5、D6是负相关的，D5中support（C-->M）=0.91而support（M-->C）=0.09，这样的关系，简单的认为是负相关或者正相关都不妥，Kulc做平均处理倒很好，平滑后认为它们是无关的，我们再引入一个不平衡因子IR(imbalance ratio):
IR(A,B)=|sup(a)-sup(B)|/(sup(A)-sup(B)-sup(A交B))（注：应为(sup(A)+sup(B)-sup(A交B)）
D4总IR(C,M)=0，非常平衡，D5中IR(C,M)=0.89,不平衡，而D6中IR(C,M)=0.99极度不平衡，我们应该看到Kulc值虽然相同但是平衡度不一样，在实际中应该意识到不平衡的可能，根据业务作出判断，因此这里我们认为Kulc结合不平衡因子的是较好的评价方法。
另外weka中还使用 Conviction和Leverage。Conviction(A,B) = P(A)P(B)/P(AB)， Leverage(A,B) = P(A交B)-P(A)P(B)，Leverage是不受空值影响，而Conviction是受空值影响的。
总结
介绍了9个关联规则评价的准则，其中全自信度、最大自信度、Kulc、cosine，Leverage是不受空值影响的，这在处理大数据集是优势更加明显，因为大数据中想MC这样的空记录更多，根据分析我们推荐使用kulc准则和不平衡因子结合的方法。
参考文献
[1]：HanJiaWei. Data Mining: concept and techniques.
以上内容参考https://www.cnblogs.com/fengfenggirl/p/associate_measure.html，感谢博主
总结
以上是生活随笔为你收集整理的机器学习-非监督分类算法之关联规则的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 访问控制符
- 下一篇： 机器学习基本概念-阿里云大学