频道栏目
首页 > 网络 > 云计算 > 正文

关联规则算法简介和应用

2017-11-14 11:08:27      个评论    来源:qq_16093959的博客  
收藏   我要投稿

1. 算法简介

关联规则最初提出的动机是针对购物篮分析(Market Basket Analysis)问题提出的。1993年,Agrawal等人在首先提出关联规则概念,同时给出了相应的挖掘算法AIS,但是性能较差。1994年,他们建立了项目集格空间理论,并依据上述两个定理,提出了著名的Apriori算法,至今Apriori仍然作为关联规则挖掘的经典算法被广泛讨论,以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。

假定你是AllElectronics的销售经理,当有顾客买了PC和数码相机时,你会向他推荐什么产品?你会考虑哪些问题?

这就是关联规则要回答的问题。

1.1 基本概念

关联规则的分类

1.按处理的变量

布林型:买啤酒=>买尿布

数值型:月收入5000元=>每月交通费800元

2.按资料的抽象层次

单层关联规则: IBM台式机=>Sony打印机,一个细节数据上的单层关联规则

多层关联规则:台式机=>Sony打印机,较高和细节层次之间的多层关联规则

3.按涉及到的资料维数

单维关联规则:啤酒=>尿布,只涉及到用户的购买的物品

多维关联规则:性别=”女”=>职业=”秘书”,涉及到两个字段的信息

三个度

关联规则的计算主要计算三个度

支持度support

置信度confidence

提升度lift

以一组具体的数据来说明“三度”

举个例子吧说说三个度是咋回事?

假设有10000个消费者购买了商品,其中购买尿布的有1000个,购买啤酒的2000个,购买面包的500个,同时购买尿布与啤酒的800个,同时购买尿布与面包的600个。

支持度(support):全部事务中,{X,Y}出现的可能性,即项集中{X,Y}同时出现的概率:

support(X=>Y)=P(X U Y)

该指标作为建立强关联规则的第一个门槛,衡量了所考察关联规则在量上的多少,其意义在于通过最小阈值(minsup)的设定,来剔除那些“出镜率”较低的无意义的规则,而相应地保留下出现较为频繁的项集所隐含的规则。即筛选出满足:

support(Z) >= minsup

的项集Z,被称为频繁项集(Frequent Itemset)。

当我们设定最小阈值为5%,由于{啤酒,尿布}的支持度为800/10000=8%,而{尿布,面包}的支持度为100/10000=1%,则{尿布,啤酒}满足了基本的数量要求,成为频繁项集,且规则啤酒=>尿布,尿布=>啤酒

同时被保留,而{尿布,面包}对应的两条规则都被排除。

置信度(confidence):表示在关联规则的先决条件X发生的条件下,关联结果Y发生的概率,即含有X的项集条件下,同时含有Y的可能性:

confidence(X=>Y) = P(Y/X)

这是生成强关联规则的第二个门槛,衡量所考察关联规则在“质”上的可靠性。相似的,需要对置信度设置最小阈值(mincon)来进一步筛选,从而最终生成满足需要的强关联规则。因此,继产生频繁项集后,需从中进而选取满足:

confidence(X=>Y) >= mincon

的规则,至此完成所需关联规则的生成。

当设定mincon=70%,confidence(尿布=>啤酒)=800/1000=80%,confidence(啤酒=>尿布)=800/2000=40%,被剔除。至此,我们根据需要筛选出了一条强关联规则:尿布=>啤酒。

提升度(lift):表示在含有X的条件下同时含有Y的可能性与无条件下含有Y的可能性之比。即在Y的自身出现的可能性P(Y)的基础上,X的出现对于Y的“出镜率” P(Y/X)的提升程度:

lift(X=>Y) = P(Y/X)/P(Y) = confidence (X=>Y)/P(Y)

该指标与confidence同样用来衡量规则的可靠性,可以看作置信度的一种互补指标。

举例来说,我们考虑1000个消费者,发现有500人购买了茶叶,其中有450人同时购买了咖啡,另50人没有。由于confidence(茶叶=>咖啡)=450/500=90%,由此我们可能会认为喜欢喝茶的人往往喜欢喝咖啡。但当我们来看另外没有购买茶叶的500人,其中同样有450人购买了咖啡,同样是很高的置信度90%,由此,我们看到不爱喝茶的也爱喝咖啡。这样看来,其实是否购买咖啡,与有没有购买茶叶并没有关联,两者是相互独立的,其提升度90%/[(450+450)/1000]=1。

由此可见,lift正是弥补了confidence的这一缺陷,if lift=1,X与Y独立,X对Y出现的可能性没有提升作用,其值越大(lift>1),则表明X对Y的提升程度越大,也表明关联性越强。

1.2 算法原理

Apriori算法

是一种挖掘关联规则的算法,用于挖掘其内涵的、未知的却又实际存在的数据关系,其核心是基于两阶段频集思想的递推算法。

Apriori算法的两个阶段:

寻找频繁项集;

有频繁项集找关联规则。

这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述

2. 应用场景

购物篮分析、分类设计、货存安排、捆绑销售、亏本销售分析等等。

电子商务网站的交叉推荐销售:

淘宝购物时,发现买了该商品的人还买了啥啥。

看视频时,发现看了该视频的人还看了啥啥。

浏览网页时,浏览了该网页的也浏览了啥啥。

听音乐时,个性化音乐推荐。

超市里货架摆放设计:

沃尔玛通过大量的商品购物篮发现了啤酒与尿布。

这些一系列的东东都跟推荐算法有关,关联规则也是推荐算法之一。

3. 优缺点

Apriori算法缺点:

- 在每一步产生侯选项目集时循环产生的组合过多,没有排除 不应该参与组合的元素;

- 每次计算项集的支持度时,都对数据库中的全部记录进行了一遍扫描比较,需要很大的I/O 负载。

上一篇:Storm学习总结,离线计算是什么?
下一篇:安迪-比尔定律(Andy and Bill’s Law)介绍
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站