数据挖掘算法之-关联规则挖掘(Association Rule)（购物篮分析），associationrule
在各种数据挖掘算法中，关联规则挖掘算是比较重要的一种，尤其是受购物篮分析的影响，关联规则被应用到很多实际业务中，本文对关联规则挖掘做一个小的总结。 首先，和聚类算法一样，关联规则挖掘属于无监督学习方法，它描述的是在一个事物中物品间同时出现的规律的知识模式，现实生活中，比如超市购物时，顾客购买记录常常隐含着很多关联规则，比如购买圆珠笔的顾客中有65%也购买了笔记本，利用这些规则，商场人员可以很好的规划商品摆放问题； 为叙述方便，设R= { I1,I2 ......Im}
定义：设W中支持物品集A的事务中，有c
通俗解释：简单地说，可信度就是指在出现了物品集A
实例说明：上面所举的圆珠笔和笔记本的例子，该关联规则的可信度就回答了这样一个问题：如果一个顾客购买了圆珠笔，那么他也购买笔记本的可能性有多大呢？在上述例子中，购买圆珠笔的顾客中有65％的人购买了笔记本,
概率描述：物品集A对物品集B的置信度confidence（A==>B）=P（A|B）
2.支持度(support)
定义：设W
通俗解释：简单地说，A==>B的支持度就是指物品集A和物品集B同时出现的概率。
实例说明：某天共有1000 个顾客到商场购买物品，其中有150个顾客同时购买了圆珠笔和笔记本，那么上述的关联规则的支持度就是15％。
概率描述：物品集A对物品集B的支持度support（A==>B）=P（A n B）
3.期望置信度（Expected confidence）
定义：设W
通俗解释：期望可信度描述了在没有任何条件影响时，物品集B
实例说明：如果某天共有1000
概率描述：物品集A对物品集B的期望置信度为support（B）=P（B）
4.提升度（lift）定义：提升度是可信度与期望可信度的比值
通俗解释：提升度反映了“物品集A的出现”对物品集B的出现概率发生了多大的变化。
实例说明：上述的关联规则的提升度=65%/25%=2.6
概率描述：物品集A对物品集B的期望置信度为lift（A==>B）=confidence（A==>B）/support(B)=p(B|A)/p(B)
总之，可信度是对关联规则的准确度的衡量，支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有事务中有多大的代表性，显然支持度越大，关联规则越重要。有些关联规则可信度虽然很高，但支持度却很低，说明该关联规则实用的机会很小，因此也不重要。
在关联规则挖掘中，满足一定最小置信度以及支持度的集合成为频繁集（frequent itemset），或者强关联。关联规则挖掘则是一个寻找频繁集的过程。
关联规则挖掘的相关算法
1.Apriori算法：使用候选项集找频繁项集
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。
该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。
可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。
2.基于划分的算法
Savasere等设计了一个基于划分的算法。这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。
3.FP-树频集算法
针对Apriori算法的固有缺陷，J. Han等提出了不产生候选挖掘频繁项集的方法：FP-树频集算法。采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有巨大的提高。
接分啦。。。找到一篇不错的文章
楼主看下，参考资料：blog.csdn.net/...6.aspx
2.关联规则挖掘过程、分类及其相关算法
2.1关联规则挖掘的过程
关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组(Frequent Itemsets)，第二阶段再由这些高频项目组中产生关联规则(Association Rules)。
关联规则挖掘的第一阶段必须从原始资料集合中，找出所有高频项目组(Large Itemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一水平。一项目组出现的频率称为支持度(Support)，以一个包含A与B两个项目的2-itemset为例，我们可以经由公式(1)求得包含{A,B}项目组的支持度，若支持度大于等于所设定的最小支持度(Minimum Support)门槛值时，则{A,B}称为高频项目组。一个满足最小支持度的k-itemset，则称为高频k-项目组(Frequent k-itemset)，一般表示为Large k或Frequent k。算法并从Large k的项目组中再产生Large k+1，直到无法再找到更长的高频项目组为止。
关联规则挖掘的第二阶段是要产生关联规则(Association Rules)。从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小信赖度(Minimum Confidence)的条件门槛下，若一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。例如：经由高频k-项目组{A,B}所产生的规则AB，其信赖度可经由公式(2)求得，若信赖度大于等于最小信赖度，则称AB为关联规则。
就沃尔马案例而言，使用关联规则挖掘技术，对交易资料库中的纪录进行资料挖掘，首先必须要设定最小支持度与最小信赖度两个门槛值，在此假设最小支持度min_support=5% 且最小信赖度min_confidence=70%。因此符合此该超市需求的关联规则将必须同时满足以上两个条件。若经过挖掘过程所找到的关联规则「尿布，啤酒」，满足下列条件，将可接受「尿布，啤酒」的关联规则。用公式可以描述Support(尿布，啤酒)>=5%且Confidence(尿布，啤酒)>=70%。其中，Support(尿布，啤酒)>=5%于此应用范例中的意义为:在所有的交易纪录资料中，至少有5%的交易呈现尿布与啤酒这两项商品被同时购买的交易行为。Confidence(尿布，啤酒)>=70%于此应用范例中的意义为:在所有包含尿布的交易纪录资料中，至少有70%的交易会同时购买啤酒。因此，今后若有某消费者出现购买尿布的行为，超市将可推荐该消费者同时购买啤酒。这个商品推荐的行为则是根据「尿布，啤酒」关联规则，因为就该超市过去的交易纪录而言，支持了“大部份购买尿布的交易，会同时购买啤酒”的消费行为。
从上面的介绍还可以看出，关联规则挖掘通常比较适用与记录中的指标取离散值的情况。如果原始数据库中的指标值是取连续的数据，则在关联规则挖掘之前应该进行适当的数据离散化（实际上就是将某个区间的值对应于某个值），数据的离散化是数据挖掘前的重要环节，离散化的过程是否合理将直接影响关联规则的挖掘结果......余下全文>>
baidu.google.yahu.sina.msdn.....