在描述有关关联规则的一些细节之前，先来看一个有趣的故事： "尿布与啤酒"的故事。

在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是："跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在"尿布与啤酒"背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。

关联规则最初提出的动机是针对购物篮分析(Market Basket Analysis)问题提出的。假设分店经理想更多的了解顾客的购物习惯。特别是，想知道哪些商品顾客可能会在一次购物时同时购买？为回答该问题，可以对商店的顾客事物零售数量进行购物篮分析。该过程通过发现顾客放入“购物篮”中的不同商品之间的关联，分析顾客的购物习惯。这种关联的发现可以帮助零售商了解哪些商品频繁的被顾客同时购买，从而帮助他们开发更好的营销策略。

关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。

1993年，Agrawal等人在首先提出关联规则概念，同时给出了相应的挖掘算法AIS，但是性能较差。1994年，他们建立了项目集格空间理论，并依据上述两个定理，提出了著名的Apriori算法，至今Apriori仍然作为关联规则挖掘的经典算法被广泛讨论，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。

关联规则算法

挖掘步骤：

1.依据支持度找出所有频繁项集（频度）

2.依据置信度产生关联规则（强度）

三、基本概念

对于A->B

①支持度（Support）：P(A ∩ B)，既有A又有B的概率

②置信度(信赖度：Confidence)：

P(B|A)，在A发生的事件中同时发生B的概率 p(AB)/P(A)     例如购物篮分析：牛奶 ⇒ 面包

  置信度(信赖度：Confidence)： P(B|A)=p(AB)/P(A)    （利用置信度判断商品之间的关联）

例子：[支持度：25%，置信度：71.4%]

关联规则为：牛奶----->面包     支持度为：25%，信赖度为：0.25/0.35=0.714

支持度25%：意味着25%顾客同时购买牛奶和面包

置信度71.4%：意味着购买牛奶的顾客中国有71.4%也购买面包

③如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。

④同时满足最小支持度阈值和最小置信度阈值的规则称为强规则

注：如果买A商品的同时购买B商品的概率较高，将两商品放在一起就可以增加商品的销量。

 ①Apriori算法的缺点：

(1)由频繁k-1项集进行自连接生成的候选频繁k项集数量巨大。

(2)在验证候选频繁k项集的时候需要对整个数据库进行扫描，非常耗时。

  ②网上提到的频集算法的几种优化方法：

1. 基于划分的方法。

2. 基于hash的方法。

3. 基于采样的方法。

4. 减少交易的个数。

  改进算法：有些学着觉得算法仍有不足，提出了兴趣度（Interesting）或称增益（Improvement）的指标，即：

兴趣度=Confident(X---->Y)/P(Y)=P(XY)/(P(X)P(Y))

当兴趣值大于1的时候，规则就是较好的，兴趣值小于1时，规则没有太大意义，即新区读的值越大，实际意义就越好。