资源描述：
《关联规则算法Apriori的学习与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、关联规则算法Apriori的学习与实现 (2011-07-1811:28:52) 首先我们来看，什么是规则？规则形如”如果…那么…(If…Then…)”,前者为条件，后者为结果。关联规则挖掘用于寻找给定数据集中项之间的有趣的关联或相关关系。关联规则揭示了数据项间的未知的依赖关系，根据所挖掘的关联关系，可以从一个数据对象的信息来推断另一个数据对象的信息。例如购物篮分析。牛奶⇒ 面包[支持度：3%，置信度：40%]支持度3%意味3%顾客同时购买牛奶和面包。置信度40%意味购买牛奶的顾客40%也购买面包。规则的支持度和置信度
2、是两个规则兴趣度度量，它们分别反映发现规则的有用性和确定性。关联规则是有趣的，如果它满足最小支持度阈值和最小置信度阈值。这些阈值可以由用户或领域专家设定。我们先来认识几个相关的定义：定义1：支持度（support）支持度s是事务数据库D中包含AUB的事务百分比，它是概率P（AUB），即support（AB）=P（AUB），它描述了A和B这两个物品集的并集在所有的事务中出现的概率。定义2：置信度（confidence）可信度为事务数据库D中包含A的事务中同时也包含B的百分比，它是概率P（B
3、A），即confidence（
4、AB）=P（B
5、A）。定义3：频繁项目集支持度不小于用户给定的最小支持度阈值（minsup）的项集称为频繁项目集（简称频集），或者大项目集。所有的频繁1-项集记为L1。假设有如下表的购买记录。顾客项目1orangejuice,coke2milk,orangejuice,windowcleaner3orangejuice,detergent4orangejuice,detergent,coke5windowcleaner将上表整理一下，得到如下的一个2维表 OrangeWinClMilkCokeDetergentOran
6、ge41122WinCl12100Milk11100Coke20021Detergent10002上表中横栏和纵栏的数字表示同时购买这两种商品的交易条数。如购买有Orange的交易数为4，而同时购买Orange和Coke的交易数为2。置信度表示了这条规则有多大程度上值得可信。设条件的项的集合为A,结果的集合为B。置信度计算在A中，同时也含有B的概率。即Confidence(A==>B)=P(B
7、A)。例如计算"如果17Orange则Coke"的置信度。由于在含有Orange的4条交易中，仅有2条交易含有Coke.其置信
8、度为0.5。支持度计算在所有的交易集中，既有A又有B的概率。例如在5条记录中，既有Orange又有Coke的记录有2条。则此条规则的支持度为2/5=0.4。现在这条规则可表述为，如果一个顾客购买了Orange,则有50%的可能购买Coke。而这样的情况（即买了Orange会再买Coke）会有40%的可能发生。再来考虑下述情况。项支持度A0.45B0.42C0.4AandB0.25AandC0.2BandC0.15A,B，andC0.05可得到下述规则规则置信度IfBandCthenA0.05/0.15*100%=33.
9、33%IfAandCthenB0.05/0.20*100%=25%IfAandBthenC0.05/0.25*100%=20%上述的三条规则，哪一条规则有用呢？对于规则" IfBandCthenA"，同时购买B和C的人中，有33.33%会购买A。而单项A的支持度有0.45，也就是说在所有交易中，会有45%的人购买A.看来使用这条规则来进行推荐，还不如不推荐，随机对顾客进荐好了。为此引入另外一个量，即提升度(Lift)，以度量此规则是否可用。描述的是相对于不用规则，使用规则可以提高多少。有用的规则的提升度大于1。计算方式
10、为Lift(A==>B)=Confidence(A==>B)/Support(B)=Support(A==>B)/(Support(A)*Support(B))。在上例中，Lift(IfBandCTheA)=0.05/(0.15*0.45)=0.74。而Lift(IfAthenB)=0.25/(0.45*0.42)=1.32。也就是说对买了A的人进行推荐B,购买概率是随机推荐B的1.32倍。如何产生规则呢。可以分两步走。首先找出频繁集(frequentitemset)。所谓频繁集指满足最小支持度或置信度的集合。其次从频
11、繁集中找出强规则(strongrules)。强规则指既满足最小支持度又满足最小置信度的规则。我们来看如何产生频繁集。这其中有一个定理。即频繁集的子集也一定是频繁集。比如，如果{A,B,C}是一个3项的频繁集，则其子集{A,B},{B,C},{A,C}也一定是2项的频繁集。为方便，可以把含有k项的集合称之为k-itemsets.17
