数据挖掘与关联规则

1、大数据时代算法-关联规则简介关联规则（Association Rules）反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。首先被Agrawal, Imielinski and Swami在1993年的SIGMOD会议上提出. 关联规则挖掘是数据挖掘中最活跃的研究方法之一。典型的关联规则发现问题是对超市中的购物篮数据（Market Basket）进行分析。通过发现顾客放入购物篮中的不同商品之间的关系来分析顾客的购买习惯。 “尿布与啤酒”的故事。美国的沃尔玛超市对一年多的原始交易数据进行了详细的分析，得到一个意

2、外发现：与尿布一起被购买最多的商品竟然是啤酒。借助于数据仓库和关联规则，商家发现了这个隐藏在背后的事实：美国的妇女们经常会嘱咐她们的丈夫下班以后要为孩子买尿布，而30%40%的丈夫在买完尿布之后又要顺便购买自己爱喝的啤酒。有了这个发现后，超市调整了货架的设置，把尿布和啤酒摆放在一起销售，从而大大增加了销售额。70%购买了牛奶的顾客将倾向于同时购买面包。某网上书店向用户推荐相关书籍。在买了一台PC之后下一步会购买？在保险业务方面，如果出现了不常见的索赔要求组合，则可能为欺诈，需要作进一步的调查；在医疗方面，可找出可能的治疗组合；在银行方面，对顾客进行分析，可以推荐感兴趣的服务等等。什么是规则？规

3、则形如如果那么(IfThen),前者为条件，后者为结果。例如一个顾客，如果买了可乐，那么他也会购买果汁。如何来度量一个规则是否够好？有两个量，置信度(Confidence)和支持度(Support)。假设有如下表的购买记录。 置信度置信度表示了这条规则有多大程度上值得可信。设条件的项的集合为A,结果的集合为B。置信度计算在A中，同时也含有B的概率(即：if A ,then B的概率)。即 Confidence(AB)=P(B|A)。例如计算“如果Orange则Coke”的置信度。由于在含有“橙汁”的4条交易中，仅有2条交易含有“可乐”。其置信度为0.5。支持度支持度计算在所有的交易集中，既有A

4、又有B的概率。例如在5条记录中，既有橙汁又有可乐的记录有2条。则此条规则的支持度为 2/5=0.4，即Support(AB)=P(AB)。现在这条规则可表述为，如果一个顾客购买了橙汁,则有50%(置信度)的可能购买可乐。而这样的情况（即买了橙汁会再买可乐）会有40%(支持度)的可能发生。 定义1 项目与项集设I=i1,i2,im是m个不同项目的集合，每个ik(k=1，2，m)称为一个项目(Item)。项目的集合 I 称为项目集合(Itemset)，简称为项集。其元素个数称为项集的长度，长度为k的项集称为k-项集(k-Itemset)。l定义2 交易l每笔交易T(Transaction)是项集I

5、上的一个子集，即TI，但通常TI。l对应每一个交易有一个唯一的标识交易号，记作TIDl交易的全体构成了交易数据库D，或称交易记录集D，简称交易集D。l交易集D中包含交易的个数记为|D|。 l定义3 项集的支持度l对于项集X，XI，设定count(XT)为交易集D中包含X的交易的数量l项集X的支持度support(X)就是项集X出现的概率，从而描述了X的重要性。 |D|T)count(Xsupport(X)定义4 项集的最小支持度与频繁集发现关联规则要求项集必须满足的最小支持阈值，称为项集的最小支持度(Minimum Support)，记为supmin。支持度大于或等于supmin的项集称为频繁

6、项集，简称频繁集，反之则称为非频繁集。通常k-项集如果满足supmin，称为k-频繁集，记作Lk。定义5 关联规则关联规则(Association Rule)可以表示为一个蕴含式： R：XY 其中：XI，YI，并且XY= 。例如：R：牛奶面包定义6 关联规则的支持度对于关联规则R：XY，其中XI，YI，并且XY=。规则R的的支持度(Support)是交易集中同时包含X和Y的交易数与所有交易数之比。 |D|Y)count(XY)support(X定义7 关联规则的置信度对于关联规则R：XY，其中XI,YI，并且XY=。规则R的置信度(Confidence)是指包含X和Y的交易数与包含X的交易数之

7、比 support(X)Y)support(XY)(X confidence一般来说，只有支持度和置信度均较高的关联规则才是用户感兴趣的、有用的关联规则。定义8 关联规则的最小支持度和最小置信度关联规则的最小支持度也就是衡量频繁集的最小支持度(Minimum Support)，记为supmin，它用于衡量规则需要满足的最低重要性。关联规则的最小置信度(Minimum Confidence)记为confmin，它表示关联规则需要满足的最低可靠性。定义9 强关联规则如果规则R:XY满足support(XY)supmin且confidence(XY)confmin，称关联规则XY为强关联规则，否则称

8、关联规则XY为弱关联规则。在挖掘关联规则时，产生的关联规则要经过supmin和confmin的衡量，筛选出来的强关联规则才能用于指导商家的决策。对于规则 AC：支持度 = support(A,C ) = 50%置信度 = support(A,C )/support(A) = 66.6%交易ID购买商品2000A,B,C1000A,C4000A,D5000B,E,F假设最小值支持度为假设最小值支持度为50%，最小置信度为，最小置信度为50%规则规则AC满足最小支持度和最小置信满足最小支持度和最小置信度，所以它是度，所以它是强关联规则强关联规则l关联规则挖掘是一个两步的过程：关联规则挖掘是一个两步

9、的过程：l找出所有找出所有频繁项集频繁项集l由频繁项集产生由频繁项集产生强关联规则强关联规则，这些规则必须大于，这些规则必须大于或者等于最小支持度和最小置信度或者等于最小支持度和最小置信度大于或者等于最小支持度大于或者等于最小支持度的项集的项集AprioriApriori算法算法Apriori算法是一种经典的生成布尔型关联规则的频繁项集挖掘算法。Apriori算法将发现关联规则的过程分为两个步骤：通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小置信度的规则。挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。 Aprior

10、iApriori算法的重要性质算法的重要性质性质1：频繁项集的子集必为频繁项集性质2：非频繁项集的超集一定是非频繁的假设项集假设项集A,CA,C是频繁项集，则是频繁项集，则AA和和CC也为频繁项集也为频繁项集假设项集假设项集DD不是频繁项集，则不是频繁项集，则A,DA,D和和C,DC,D也不是频繁项集也不是频繁项集AprioriApriori算法举例算法举例现有A、B、C、D、E五种商品的交易记录表，找出所有频繁项集，假设最小支持度=50%,最小置信度=50%AprioriApriori算法举例算法举例_ _产生频繁项集产生频繁项集K=1支持度50A50%50%B75%75%C75%75%E7

11、5%75%L1项集项集支持度支持度A,B25%25%A,C50%50%A,EA,E25%25%B,C50%50%B,E75%75%C,E50%50%C2 2K=2支持度50支持度50A,C50%50%B,C50%50%B,E75%75%C,E50%50%L2AprioriApriori算法举例算法举例_ _产生频繁项集产生频繁项集A,C50%50%B,C50%50%B,E75%75%C,E50%50%L2支持度50支持度50AprioriApriori算法举例算法举例_ _产生关联规则产生关联规则对于频繁项集B,C,E,它的非空子集有B、C、E、B,C、B,E、C,E。以下就是据此获得的关联规

12、则及其置信度。规则规则置信度置信度ConfidenceConfidenceBCE66.7%CBE66.7%EBC66.7%CEB1BEC66.7%BCE1置信度50%(最小置信度)，都是强关联规则AprioriApriori算法弊端算法弊端需要多次扫描数据表如果频繁集最多包含10个项，那么就需要扫描交易数据表10遍，这需要很大的I/O负载产生大量频繁集若有100个项目，可能产生候选项数目1210030100100100.1.27*10CCCFP-growthFP-growth算法算法Jiawei Han等人在2000年提出了一种基于FP-树的关联规则挖掘算法FP_growth，它采取“分而治之

13、”的策略，将提供频繁项目集的数据库压缩成一棵频繁模式树（FP-树）。仅两次扫描数据库。理论和实验表明该算法优于Apriori算法。FP-growthFP-growth算法算法其他关联规则挖掘算法其他关联规则挖掘算法约束性关联规则挖掘算法仅设置支持度和置信度阈值，缺乏用户控制，可能产生过多的规则，实际效果可能并不好。用户关心的是某些特定的关联规则，这需要把一些约束条件引入到挖掘算法中，从而筛选出符合约束条件的有用规则，提高算法的运行效率和用户满意度。增量式关联规则挖掘算法数据集不断增长，有新的数据加入后，重新挖掘很费时。增量式关联规则挖掘算法是当数据库变化后，在原挖掘结果的基础上生成新的关联规则

14、，删除过时的关联规则。多层关联规则挖掘关联规则的价值衡量关联规则的价值衡量客观上，使用“支持度和置信度”框架可能会产生一些不正确的规则。只凭支持度和置信度阈值未必总能找出符合实际的规则。例：歌曲A、歌曲C为小众歌曲，歌曲B为口水歌，共有10万个用户，有200个人听过歌曲A，这200个人里面有60个听过口水歌B，有40个人听过歌曲C。听过歌曲C的人数是300，听过口水歌B的人为50000。Confidence(AB) = 0.3，Confidence(AC) = 0.2但是10W人里面有5W听过歌曲B，有一半的用户都喜欢歌曲B，但听过歌曲A的人里面只有30%的人喜欢歌曲 B听过歌曲A的人不喜欢歌

15、曲B貌似A和B更相关矛盾的规则，如何评价？关联规则价值衡量关联规则价值衡量Lift(AB)=Confidence(AB)/Support(B)=()( ) ( )p ABp A p B引入提升度Lift，以度量此规则是否可用。它描述的是：相对于不用规则，使用规则可以提高多少。Lift(AB) =Confidence(AB)/Support(B)=0.3/0.5=0.6Lift(AC)=Confidence(AC)/Support(C)=0.2/(300/100000)=66.7歌曲A与B负相关，A与C正相关。Lift大于1，表示使用这条规则进行推荐能提升用户听歌曲C的概率。Lift小于1，则表

16、示使用这条规则来进行推荐，还不如不推荐，让顾客自行选择好了。Confidence(AB) = 0.3Confidence(AC) = 0.2Support(B)=0.5Support(C)=300/100000关联规则的价值衡量关联规则的价值衡量主观上，一个规则的有用与否最终取决于用户的感觉，只有用户才能决定规则的有效性、可行性。所以，应该将需求和关联规则挖掘方法紧密地结合起来。例如使用“约束性关联规则挖掘算法”，将约束条件与算法紧密结合，既能提高数据挖掘效率，又能明确数据挖掘的目标。参考文献：1高明 . 关联规则挖掘算法的研究及其应用D.山东师范大学. 20062李彦伟 . 基于关联规则的数据挖掘方法研究D.江南大学