关联规则大全

工作报告报告人：李雪园

报告内容1.关联规则简介2.关联规则算法基本模型及相关概念3.Apriori算法4.关联规则算法举例及java实现5.前21天内的工作总结6.未来7天工作计划经典案例回放：“尿布与啤酒”的故事：

美国的沃尔玛超市对一年多的原始交易数据进行了详细的分析，得到一个意外发现：与尿布一起被购买最多的商品竟然是啤酒。借助于数据仓库和关联规则，商家发现了这个隐藏在背后的事实：美国的妇女们经常会嘱咐她们的丈夫下班以后要为孩子买尿布，而30%～40%的丈夫在买完尿布之后又要顺便购买自己爱喝的啤酒。有了这个发现后，超市调整了货架的设置，把尿布和啤酒摆放在一起销售，从而大大增加了销售额。这个故事告诉了我们什么呢?一、关联规则简介

关联规则（AssociationRules）是反映数据库中一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。关联分析：1.所谓关联是指寻找已有数据库中值的依存程度和相关性

2.关联规则是寻找在同一个事件中出现的不同项的相关性。如：在一次购买活动中所买商品1和商品2的相关性。3.

若知道其关联关系那么就可以用于其他事物的预测，但是有时预测的结果并不是完全准确的。如：购买商品1和商品2相关性预测具有概率统计意义。4.我的理解是：可以说对不同的组合进行分析，推荐感兴趣的服务。关联规则种类：

1)基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。性别=“女”=>职业=“秘书”数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。性别=“女”=>avg（收入）=20002)基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的。IBM台式机=>Sony打印机在多层关联规则中，对数据的多层性已经进行了充分的考虑。台式机=>Sony打印机3)基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单维关联规则中，我们只涉及到数据的一个维。啤酒=>尿布在多维关联规则中，要处理的数据将会涉及多个维。性别=“女”=>职业=“秘书”二.关联规则算法基本模型及相关概念

基本模型：关联规则可简记为A==>B，A称为前提，B称为后续。形如"如果…那么…(If…Then…)",前者为条件，后者为结果。例如前面的例子：买了尿布的人也同时买了啤酒，尿布是前提，啤酒是结果。模型讨论：

由前提推结论，算出他们的相关性有多大，通常以概率表示，要计算包含某个特定项或几个项的事务在数据库中出现的概率只要在数据库中直接统计即可。然而如何来度量一个规则的好坏呢？相关概念：已知A、B代表两个事件1.置信度：当已有A发生时，B发生的概率是多少？也就是概率论中的条件概率。表示了这条规则有多大程度上值得可信。Confidence(AB)=P(B|A)2.支持度：某一特定关联（“尿布和啤酒”）在数据库中出现的概率称为支持度。表示在上述置信度的情况下，AB同时发生的可能性。Support(AB)=P(AB)举例：人物购买商品1AD2ABE3AC4DE5ABC如何计算置信度与支持度？在5条交易记录中，既有A又有B的记录有2条。则此条规则的支持度为2/5=0.4。在5条交易记录中，在含有A的交易有4条中，仅有2条交易记录含有B。其置信度为2/4=0.5。代表意义：如果一个人购买了商品A,则有50%(置信度)的可能购买商品B。而这样的情况（即购买商品A后会继续购买商品B）会有40%(支持度)的可能发生。其他概念：1.项目与项集设I={i1,i2,…,im}是m个不同项目的集合，每个ik(k=1，2，……，m)称为一个项目。项目的集合I称为项目集合，简称为项集。其元素个数称为项集的长度，长度为k的项集称为k-项集。2.交易每笔交易T(Transaction)是项集I上的一个子集，即TI，但通常TI。对应每一个交易有一个唯一的标识——交易号，记作TID交易的全体构成了交易数据库D，或称交易记录集D，简称交易集D。交易集D中包含交易的个数记为|D|。

3.项集的支持度对于项集X，设定count(XT)为交易集D中包含X的交易的数量

4.项集的最小支持度与频繁集

发现关联规则要求项集必须满足的最小支持阈值，称为项集的最小支

持度(MinimumSupport)，记为supmin。

支持度大于或等于supmin的项集称为频繁项集，简称频繁集，反之则

称为非频繁集。

通常k-项集如果满足supmin，称为k-频繁集，记作Lk。5.关联规则的支持度规则的支持度是数据集中同时包含其子集X和子集Y的记录数与所有记录数之比。6.关联规则的置信度

规则的置信度是指包含X和Y的数据子集数与包含X的记录数之比

7.关联规则的最小支持度和最小置信度关联规则的最小支持度也就是衡量频繁集的最小支持度，记为supmin，它用于衡量规则需要满足的最低重要性。关联规则的最小置信度记为confmin，它表示关联规则需要满足的最低可靠性。8.强关联规则如果规则满足support(X==>Y)≧supmin且confidence(X==>Y)≧confmin，称关联规则X==>Y为强关联规则，否则称关联规则X==>Y为弱关联规则。在挖掘关联规则时，产生的关联规则要经过supmin和confmin的衡量，筛选出来的强关联规则才能用于指导商家的决策。客观上，使用“支持度和置信度”框架可能会产生一些不正确的规则。只凭支持度和置信度阈值未必总能找出符合实际的规则。改善度：

是另外一个描述规则价值的数值。它描述的是：相对于不用规则，使用规则可以提高多少。

改善度是一个比值：（A==>B的置信度）/（B出现的概率）。

Lift(AB)=Confidence(AB)/Support(B)改善度越高，A的出现对B出现的可能性影响越大。三、Apriori算法算法基本思想：其核心是基于两阶段频集思想的递推算法1.找出所有频繁项集。2.由频繁项集产生强关联规则，这些规则必须大于或者等于最小支持度和最小置信度。算法性质：性质1：频繁项集的子集必为频繁项集性质2：非频繁项集的超集一定是非频繁的连接步和剪枝步Apriori算法采用连接步和剪枝步两种方式来找出所有的频繁项集1）连接步为找出Lk（所有的频繁k项集的集合），通过将Lk-1（所有的频繁k-1项集的集合）与自身连接产生候选k项集的集合。候选集合记作Ck。设l1和l2是Lk-1中的成员。记li[j]表示li中的第j项。假设Apriori算法对事务或项集中的项按字典次序排序，即对于（k-1）项集li，li[1]<li[2]<……….<li[k-1]。将Lk-1与自身连接，如果(l1[1]=l2[1])&&(l1[2]=l2[2])&&……..&&(l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那认为l1和l2是可连接。连接l1和l2产生的结果是{l1[1],l1[2],……,l1[k-1],l2[k-1]}。2）剪枝步CK是LK的超集，也就是说，CK的成员可能是也可能不是频繁的。通过扫描所有的事务（交易），确定CK中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。为了压缩Ck,可以利用Apriori性质：任一频繁项集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。

Apriori核心算法分析为了生成所有频集，使用了递推的方法。其核心思想简要描述如下：(1)L1={large1-itemsets};(2)for(k=2;Lk-1¹F;k++)dobegin(3)Ck=apriori-gen(Lk-1);//新的候选集(4)foralltransactionstÎDdobegin(5)Ct=subset(Ck,t);//事务t中包含的候选集(6)forallcandidatescÎCtdo(7)c.count++;//扫描并计数(8)end(9)Lk={cÎCk|c.count³minsup}//所有频繁子集(10)end(11)Answer=∪kLk;首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。算法举例及java实现：人物下载文档1ABE2BD3BC4ABC5AC6BC7AC8ABCE9ABC根据连接剪枝原理分析寻找频集过程：项集频数A6B7C7D1E2候选项集ABCDE候选项集ABACADAEBCBDBECDCEDE项集频数AB4AC5AD0AE2BC5BD1BE2CD0CE1DE0项集频数AB4AC5BC5项集支持频数ABC3项集频数ABC3候选项集ABCC1L1C2C2L2C3C3L3首先需要建立数据库，存放已知数据，因此首先建立集合写主函数入口，包括输出各个满足要求的频繁项集、频数，以及最后输出关联规则、置信度算法缺点：1.产生候选项目集时循环产生的组合过多，没有排除不应该参与组合的元素。2.每次计算项集的支持度时都对数据库中全部记录做了扫描，增加计算机I/O开销算法改进：1.在apriori算法的基础上，在扫描数据库产生候选项目集的同时直接生成对应的频繁项集。如频繁项集不符合apriori的性质，则直接删除，不需经过产生候选项目集再扫描数据库生成频繁项集，由候选项一次性产生频繁项集。2.在扫描数据库的过程中，有些可以直接判断出而不必再去扫描，如果能避免不必要的扫描则可以提高apriori算法的效率。比较其他算法候选项集ABCDE项集频数A6B7C7D1E2候选项集ABACADAEBCBDBECDCEDE项集频数AB4AC5AD0AE2BC5BD1BE2CD0CE1DE0项集频数AB4AC5BC5项集支持频数ABC3项集频数ABC3候选项集ABCC1L1C2C2L2C3C3L3返回其他关联规则挖掘算法

频繁树(FP-Tree)算法这个算法只进行两次数据库扫描，它不使用候选项目集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成关联规则。约束性关联规则挖掘算法仅设置支持度和置信度阈值，缺乏用户控制，可能产生过多的规则，实际效果可能并不好。用户关心的是某些特定的关联规则，这需要把一些约束条件引入到挖掘算法中，从而筛选出符合约束条件的有用规则，提高算法的运行效率和用户满意度。

增量式关联规则挖掘算法数据集不断增长，有新的数据加入后，重新挖掘很费时。增量式关联规则挖掘算法是当数据库变化后，在原挖掘