1. 算法简介
 
关联规则最初提出的动机是针对购物篮分析(Market Basket Analysis)问题提出的。1993年，Agrawal等人在首先提出关联规则概念，同时给出了相应的挖掘算法AIS，但是性能较差。1994年，他们建立了项目集格空间理论，并依据上述两个定理，提出了著名的Apriori算法，至今Apriori仍然作为关联规则挖掘的经典算法被广泛讨论，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。
 
假定你是AllElectronics的销售经理，当有顾客买了PC和数码相机时，你会向他推荐什么产品？你会考虑哪些问题？
 
这就是关联规则要回答的问题。
 
1.1 基本概念
 
关联规则的分类
 
1.按处理的变量 
 布林型：买啤酒=>买尿布 
 数值型：月收入5000元=>每月交通费800元
 
2.按资料的抽象层次 
 单层关联规则： IBM台式机=>Sony打印机，一个细节数据上的单层关联规则 
 多层关联规则：台式机=>Sony打印机，较高和细节层次之间的多层关联规则 
 
3.按涉及到的资料维数 
 单维关联规则：啤酒=>尿布，只涉及到用户的购买的物品 
 多维关联规则：性别=”女”=>职业=”秘书”，涉及到两个字段的信息
 
三个度 
 关联规则的计算主要计算三个度 
 支持度support 
 置信度confidence 
 提升度lift 
 以一组具体的数据来说明“三度”
 
举个例子吧说说三个度是咋回事？
 
假设有10000个消费者购买了商品，其中购买尿布的有1000个，购买啤酒的2000个，购买面包的500个，同时购买尿布与啤酒的800个，同时购买尿布与面包的600个。
 
支持度（support）:全部事务中，{X,Y}出现的可能性，即项集中{X,Y}同时出现的概率： 
 support(X=>Y)=P(X U Y) 
 该指标作为建立强关联规则的第一个门槛，衡量了所考察关联规则在量上的多少，其意义在于通过最小阈值(minsup)的设定，来剔除那些“出镜率”较低的无意义的规则，而相应地保留下出现较为频繁的项集所隐含的规则。即筛选出满足： 
 support(Z) >= minsup 
 的项集Z，被称为频繁项集(Frequent Itemset)。 
 当我们设定最小阈值为5%，由于{啤酒，尿布}的支持度为800/10000=8%，而{尿布，面包}的支持度为100/10000=1%，则{尿布，啤酒}满足了基本的数量要求，成为频繁项集，且规则啤酒=>尿布，尿布=>啤酒 
 同时被保留，而{尿布，面包}对应的两条规则都被排除。
 
置信度（confidence）:表示在关联规则的先决条件X发生的条件下，关联结果Y发生的概率，即含有X的项集条件下，同时含有Y的可能性：
 
                confidence(X=>Y) = P(Y/X)
 
这是生成强关联规则的第二个门槛，衡量所考察关联规则在“质”上的可靠性。相似的，需要对置信度设置最小阈值(mincon)来进一步筛选，从而最终生成满足需要的强关联规则。因此，继产生频繁项集后，需从中进而选取满足：
 
                confidence(X=>Y) >= mincon
 
的规则，至此完成所需关联规则的生成。 
 当设定mincon=70%，confidence(尿布=>啤酒)=800/1000=80%,confidence(啤酒=>尿布)=800/2000=40%，被剔除。至此，我们根据需要筛选出了一条强关联规则：尿布=>啤酒。
 
提升度（lift）:表示在含有X的条件下同时含有Y的可能性与无条件下含有Y的可能性之比。即在Y的自身出现的可能性P(Y)的基础上，X的出现对于Y的“出镜率” P(Y/X)的提升程度：
 
            lift(X=>Y) = P(Y/X)/P(Y) = confidence (X=>Y)/P(Y)
 
该指标与confidence同样用来衡量规则的可靠性，可以看作置信度的一种互补指标。 
 举例来说，我们考虑1000个消费者，发现有500人购买了茶叶，其中有450人同时购买了咖啡，另50人没有。由于confidence(茶叶=>咖啡)=450/500=90%，由此我们可能会认为喜欢喝茶的人往往喜欢喝咖啡。但当我们来看另外没有购买茶叶的500人，其中同样有450人购买了咖啡，同样是很高的置信度90%,由此，我们看到不爱喝茶的也爱喝咖啡。这样看来，其实是否购买咖啡，与有没有购买茶叶并没有关联，两者是相互独立的，其提升度90%/[(450+450)/1000]=1。 
 由此可见，lift正是弥补了confidence的这一缺陷，if lift=1,X与Y独立，X对Y出现的可能性没有提升作用，其值越大(lift>1),则表明X对Y的提升程度越大，也表明关联性越强。
 
1.2 算法原理
 
Apriori算法 
 是一种挖掘关联规则的算法，用于挖掘其内涵的、未知的却又实际存在的数据关系，其核心是基于两阶段频集思想的递推算法。
 
Apriori算法的两个阶段： 
 寻找频繁项集； 
 有频繁项集找关联规则。
 
 
 
 
 
 
 
FP-growth算法，FP-growth算法详解
 
 
数据挖掘—关联规则—ECLAT算法
 
2. 应用场景
 
购物篮分析、分类设计、货存安排、捆绑销售、亏本销售分析等等。 
 电子商务网站的交叉推荐销售： 
 淘宝购物时，发现买了该商品的人还买了啥啥。 
 看视频时，发现看了该视频的人还看了啥啥。 
 浏览网页时，浏览了该网页的也浏览了啥啥。 
 听音乐时，个性化音乐推荐。 
 超市里货架摆放设计： 
 沃尔玛通过大量的商品购物篮发现了啤酒与尿布。
 
这些一系列的东东都跟推荐算法有关，关联规则也是推荐算法之一。
 
3. 优缺点
 
Apriori算法缺点： 
 - 在每一步产生侯选项目集时循环产生的组合过多,没有排除 不应该参与组合的元素; 
 - 每次计算项集的支持度时,都对数据库中的全部记录进行了一遍扫描比较,需要很大的I/O 负载。

●
 关联规则( Association Rules )反映一个事物与
 其他事物之间的相互依存性和关联性。如果两个
 或者多个事物之间存在一定的关联关系,那么，
 其中一个事物就能够通过其他事物预测到。首先
 被Agrawal, Imielinski and Swami在1993年的
 SIGMOD会议_上提出.
 ●
 关联规则挖掘是数据挖掘中最活跃的研究方法之
 。典型的关联规则发现问题是对超市中的购物
 篮数据( Market Basket )进行分析。通过发现
 顾客放入购物篮中的不同商品之间的关系来分析
 顾客的购买习惯。
 
关联规则的支持度
 代表规则的重要性
 
支持度计算在所有的交易集中，既有A又有B的概率D 例 如在5条记录中，既有橙计又有可乐的记录有2条 。 则此条规则的支持度为 2/5=0.4，
 Support(A —>B)=P(AB)
 
对于关联规则R: X=Y，其中Xcl， Ycl，并且
 XnY=φ。
 规则R的的支持度(Support)是交易集中同时包含X
 和Y的交易数与所有交易数之比。
 $$\text{ support }(X\Rightarrow Y)=\frac{\mathrm{count}(X\cup Y)}{|D|}$$
 
关联规则的置信度
 置信度表示了这条规则有多大程度上值得可信。
 代表规则的可信度
 置信度表示了这条规则有多大程度上值得可信 。设条件 的项的集合为A 结果的集合为B 。 置信度计算在A中 ，同 时也含有B的概率(~P: 厅A ,.th’e,n’ Btn街冉。 即 Confidencel(A---->B)=P{BIA)即置信度就是条件概率
 
对于关联规则R: X→Y ,
 其中Xcl,Ycl，并且
 XnY=φ。
 规则R的置信度(Confidence)是指包含X和Y的交易
 数与包含X的交易数之比
 
$$\text{ confidence }(\mathrm{X}\to \mathrm{Y})=\frac{\text{ support }(\mathrm{X}\cup \mathrm{Y})}{\text{ support }(\mathrm{X})}$$
 $$\mathrm{Confidence}(x\to Y)=\frac{\text{ Support }(\mathrm{X}\cup \mathrm{Y})}{\text{ Support }(x)}=\frac{\frac{\mathrm{Count}(\mathrm{X}\cup \mathrm{Y})}{|D|}}{\frac{\mathrm{Count}(\mathrm{X})}{|D|}}=\frac{Count(\mathrm{X}\cup \mathrm{Y})}{Count(\mathrm{X})}$$
 
 
关联规则的最小支持度和最小置信度
 
  
关联规则的最小支持度也就是衡量频繁集的最小
 支持度(Minimum Support) ,记为minsup ,它
 用于衡量规则需要满足的最低重要性。
关联规则的最小置信度(Minimum Confidence)
 记为minconf ,它表示关联规则需要满足的最低
 可靠性。
 
 
强关联规则
 如果规则R:X------>Y满足$$\text{ support }(X\Rightarrow Y)\ge \underset{-}{\min }\text{sup }$$且
 $$\text{ confidence }(X\Rightarrow Y)\ge \underset{-}{\min }\text{conf }$$
 ,称关联规则X=>Y为强关联规则,否则称关联规则X= >Y为弱关联规则。
 在挖掘关联规则时,产生的关联规则要经过minsup和minconf的衡量筛选出来的强关联规则才能用干指旦商家的决策
 eg:
 
 
 
$$\begin{array}{l}\text{ support(A ->C)}=\frac{\text{ Court(AUC) }}{|D|}=\frac{1}{2}>=\text{ minsup}=\frac{1}{2}\\ \text{ Confidence }(A\to C)=\frac{\text{ Support }(A\cup C)}{\text{ Sp }u\text{ port }(A)}=66.6\%\text{ >=minconf}\\ =\frac{1}{2}\end{array}$$
 support(A)=Count(A)/|D|
 
即一条规则可表述为，如果一个颐客购买了橙汁，则有 50%(置信度)的可能购买可乐。而这样的情况 ( 即买了橙 汁会再买可乐) 会有4rQ%(支持度)的可能发生E