关联规则(AssociationRules),无监督学习方法,用于知识发现。
其可以用于给数据进行标注,但缺点是其结果难以进行评估。
关联规则的最经典的案例就是购物篮分析。同样也可用于电影推荐、约会网站或者药物间的相互副作用。
若X,Y均为项集,且X⊂I,Y⊂I,并且X∩Y= ∅ ,用蕴含式X =>Y表示一个关联规则。它表示某些项(X项集)在一个事务中的出现,可推导出另一些项(Y项集)在同一事务中也出现 。这里,“=>”称为“关联”操作,X称为关联规则的前提, Y称为关联规则的结果。
数据挖掘用到的基本数据集记为D,它是由事务构成的,一般多存储于事务数据库中。事物数据库表示为D={t1,t2,…,tm,…,tq}, 事务则表示为tk(k=1,2,…,n)。每一个事务可再细分,表示为tk={i1,i2,…,in,…,ip},im(m=1,2,…,p)称为项(item)。「所以事务是由若干个项组成的集合。」
每个事务可以用唯一的标识符事务编号TID来标识。设I={i1,i2,…,ip}是D中全体数据项组成的集合,I的任意子集X称为D中的项集(itemset)。若项集中项的个数为k,称为k项集(k-itemset)。「频繁项集是指出现次数较多的项集。」
支持度表示该数据项在事务中出现的频度。数据项集X的支持度support(X)是D中包含X的事务数量与D的总事务数量之比,如下公式所示:
关联规则X=>Y的支持度等于项集X∪Y的支持度,如下公式所示:
如果support(X)大于等于用户指定的最小支持度minsup,则称X为频繁项目集,否则称X为非频繁项目集。
置信度也称为可信度,规则 X=>Y 的置信度表示D中包含X的事务中有多大可能性也包含Y。表示的是这个规则确定性的强度,记作confidence(X=>Y)。通常,用户会根据自己的挖掘需要来指定最小置信度阈值,记为minconf。
如果数据项集X满足support(X) >= minsup,则X是频繁数据项集。若规则X=>Y同时满足confidence(X=>Y)>=minconf,则称该规则为强关联规则,否则称为弱关联规则。一般由用户给定最小置信度阈值和最小支持度阈值。发现关联规则的任务就是从数据库中发现那些置信度、支持度大于等于给定最小阈值的强关联规则。
Lift
Lift定义为:
如果一个规则的lift值等于1,这表示前提和结论对应的事件相互独立;如果lift值大于1,指示了两个事件之间的相互依赖程度,值越大,关联越强;如果lift值小于1,表明一个item的出现对其他item的出现存在消极影响(相斥),反之亦然(其中一个出现另一个一般不会出现)。lift的意义在于其即考虑了置信度也考虑了整个数据集中结论的支持度。
Conviction
Conviction,用来表示规则预测出错的概率,定义为:
在有了这些可计算的指标后,还需要给这些指标设定一个阈值,关联规则只有满足最小支持度阈值和最小置信度阈值,这条规则才能认为是有趣的。而且关联规则的生成可分以下两个步骤:
利用最小支持度阈值从数据库中找出所有的频繁项集;
利用最小置信度阈值从这些频繁项集中生成规则。
关联规则的生成规则的阶段是直接的,但寻找频繁项集却是非常耗时的,常用的高效的算法有Apriori,FP-growth等。
为了更好帮助大家理解置信度与支持度,请看下面这个例子:
假设最小支持度为50%,那么我们要这样生成频繁项集嘞?
L1与L1做连接得到候选2项集C2,并计算各项支持度,接下来就是剪枝步,由于C2的每个子集都是频繁项集,所以没有项集从C2中剔除。
对C2中的各项集的支持度与预先设定的最小支持度阈值进行比较,保留大于等于该阈值的项,「得2项频繁集L2」。
L2与L1连接得候选3项集C3,并计算每一项的支持度。接下来是剪枝步。L2余L1连接得所有项集为:{I1,I2,I3},{I1,I3,I5},{I2,I3,I5},{I1,I2,I5}。根据Apriori算法性质,频繁项集的所有非空子集必须是频繁项集,因为{I1,I2},{I1,I5}不在2项频繁项集中,所以应该剔除。最后三项候选集只剩下{I2,I3,I5}。
对C3中的各项集的支持度与预先设定的最小支持度阈值进行比较,保留大于等于该阈值的项,「得3项频繁集L3」。
由以上过程可知L1,L2,L3都是频繁项集,L3是最大频繁项集。
上面我们已经得到了频繁项集,接下来我们要基于频繁项集生成关联规则(假设最小置信度为50%)。
我们不妨基于最大频繁项集{I2,I3,I5}来生成规则:
Apriori 算法概述
Apriori 算法是一种机器学习算法,用于深入了解所涉及的不同项目之间的结构化关系。Apriori算法也是一个经典的挖掘规则算法,也是最常用的挖掘频繁项集的算法。该算法最突出的实际应用是根据用户购物车中已经存在的产品推荐产品。沃尔玛尤其在向其用户推荐产品时充分利用了该算法。
主要步骤如下
文字描述下算法流程就是:
根据上述流程我们也会发现,这个算法每一步产生候选集时循环产生的组合过多,我们可以通过挖掘关联规则的性质来做剪枝。
如图所示,AB是不频繁的,那么红色虚线圈出的所有超集也是不频繁的,因此可以剪掉。所以生成候选集的方法可以这样总结:
前面说完了如何生成频繁项集,接下来说说如何生成关联规则,现有频繁项集l,生成每个非空子集S,若S满足最小置信度:
如图所示,最小置信度mincnotallow=80%,对于频繁项集BCE,得到如下几个关联规则,其中大于80%的为BC->E和CE-<B两条规则。
作者用python编程语言完成了在线电子零售公司的跨国交易数据集的数据分析与可视化、根据关联规则原理设计实现了基于Apriori算法的关联规则挖掘程序并将程序封装、使用封装好的关联规则挖掘程序对数据集进行关联规则的挖掘,并对挖掘结果进行分析。
Apriori 算法实战亚马逊购物零售数据挖掘
数据集:亚马逊购物-杂货数据,共50万多万数据
变量列表如下
探索数据
看看前五条数据
数据汇总如下
数据总共有541909条,其中“Description”、“CustomerID”两个字段存在数据缺失情况。“Quantity”、“UnitPrice”字段最小值为负数,产品销售数量存在负数可能是存在退货情况,但是这种情况对产生关联规则存在反向作用(削弱关联强度),产品销售单价存在负数说明该字段存在异常数据。
数据中国家变量处重后如下:
建立模型并分析结果
从上面的输出可以看出,纸杯和纸盘是在法国一起买的。这是因为法国人有一种文化,即每周至少与朋友和家人聚会一次。此外,由于法国政府已禁止在该国使用塑料,人们不得不购买纸质替代品。
如果再深入分析一下英国的交易规则,就会发现英国人一起购买不同颜色的茶盘。这背后的一个原因可能是因为英国人通常非常喜欢喝茶,并且经常为不同的场合收集不同颜色的茶盘。
在分析葡萄牙交易的关联规则时,观察到 Tiffin 集 (Knick Knack Tins) 和彩色铅笔。这两种产品通常属于小学生。这两种产品是学校的孩子们分别用来携带午餐和创造性工作的必需品,因此在逻辑上将它们配对在一起是有意义的。
分析上述规则,发现男孩和女孩的餐具是搭配在一起的。这是有实际意义的,因为当父母为他/她的孩子购买餐具时,他/她会希望根据孩子的意愿对产品进行一些定制。
Apriori算法就为大家介绍到这里,欢迎各位同学了解
《呆瓜半小时入门python数据分析》课程。