推荐系统系列之关联规则

一、背后的故事

沃尔玛为了能够准确了解顾客在其门店的购买习惯,对其顾客的购物行为进行购物篮分析,想知道顾客经常一起购买的商品有哪些。它集中了其各门店的详细 原始交易数据,利用数据挖掘方法对这些数据进行分析和挖掘,并且有了一个意外的发现:跟尿布一起购买最多的商品竟是啤酒!经过大量实际调查和分析,揭示了 一个隐藏在”尿布与啤酒”背后的美国人的一种行为模式:在美国,一些年轻的父亲下班后经常要到超市去买婴儿尿布,而他们中有30%~40%的人同时也为自 己买一些啤酒。产生这一现象的原因是:美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布,而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。

二、关联规则算法简介

关联规则,也叫购物篮分析,是为了研究购物篮中商品之间的关系,可产生A->B这样的蕴涵式(或者说是规则),其中A和B分别称为关联规则的 先导和后继。衡量该规则的强弱,有支持度、置信度和提升度这三种指标,详见相关概念说明。上诉故事中的规则就是尿布->啤酒。

在商业销售应用上,可进行交叉销售(cross sell),正如故事中所诉,在发现了啤酒与尿布的内在联系后,沃尔玛将尿布和啤酒摆在一起出售,结果使尿布和啤酒的销量双双增加了。关联规则亦可应用于 医疗,找出可能的治疗组合;在银行业方面,可对顾客进行分析,可以推荐感兴趣的服务等。

三、相关概念说明

这一部分我们将通过一个具体的数据来对算法中涉及的基本概念进行说明。

假设我们有这样一张交易清单,其中A、B、C为商品代号。

交易号商品清单

0001A B C

0002A B

0003C

0004B C

0005A C

现将其转换为如下形式的交易二维表,1表示有,0表示无。

交易号ABC

0001111

0002110

0003001

0004011

0005101

项集(Item):同时出现的项的集合,k项集即包含k个元素的项集;在本例中,{A}是1项集,{A C}是2项集;

支持度(Support):定 义为 supp(X) = occur(X) / count(D) = P(X),其中D是交易数据库,即事件X出现的概率;在本例中,supp(A)=3/5

置信度(Confidence): 定义为 conf(X->Y) = supp(X ∪ Y) / supp(X) = P(Y|X),即在事件X出现的情况下事件Y出现的概率;在本例中,conf(A->B)=2/3

提升度(Lift):lift(X->Y) = lift(Y->X) = conf(X->Y)/supp(Y) = conf(Y->X)/supp(X) = P(XY)/(P(X)P(Y)),即在事件X出现的情况下事情Y出现的概率,相较于整体情况下事件Y出现的概率,提升了多少倍,可通俗理解为提升度反映 了“物品X的出现”对物品Y的出现概率发生了多大的变化;在本例中,lift(A->B)=(2/3)/(3/5)=10/9

候选集(Candidate itemset):通过向下合并得出的项集,定义为C[k];在本例中,1项集{A} 、{B},向下合并,产生项集{A B},此时称为候选集;

频繁集(Frequent itemset):支持度大于等于特定的最小支持度(Minimum Support/minsup,自定义)的项集,表示为L[k];在本例中,设最小支持度阈值为0.3,候选集{A B}的支持度为0.4,大于阈值0.3,所以候选集{A B}是频繁集;

NOTE : 置信度是对关联规则的准确度的衡量,支持度是对关联规则重要性的衡量。支持度说明了这条规则在所有交易中有多大的代表性,显然支持度越大,关联规则越重 要。有些关联规则置信度虽然很高,但支持度却很低,说明该关联规则实用的机会很小,因此也不重要。若提升度lift(X->Y)=1,根据公式,可 得P(XY)=(P(X)P(Y)),也可以根据conf(X->Y)=supp(Y),即P(Y|X)=P(Y),换句话说X是否出现,对Y出现 的概率没有影响,即说明X与Y相互独立;若lift(X->Y)>1,说明X的出现提高了Y的出现概率,有促进作用,该规则有效,若 lift(X->Y)<1,则该规则无效。

四、Apriori算法

关联规则中常用的算法是Apriori算法,主要分为两步:

a)根据给定的最小支持度阈值,找出所有满足条件的项集,即频繁项集;

b)根据给定的最小置信度阈值,在所有频繁集中找出符合条件的关联规则,即强规则;

该算法的关键在于第一步。从效率考虑,Apriori算法基于“频繁项集的非空子集也是频繁项集”这一重要性质,从频繁K-1项集中去生成频繁k项集的候 选集。怎么理解这句话呢?首先,若k项集是频繁的,根据频繁项集的定义,该k项集的支持度,也就是出现的概率大于一定的阈值,它的子集出现的概率肯定会大 于等于它出现的概率,也就一定会大于我们指定的阈值;我们也可以换个角度理解这个性质,如果某个k-1项集不是频繁的,那再加上一项组成k项集,则该k项 集出现的概率肯定会小于等于之前的k-1项集,所以我们可以说“如果某项集的非空子集不是频繁项集,那么它也一定不是频繁项集”,这两个性质互为逆否命 题,是等价的。根据这个逆否命题,我们知道如果k-1项集不是频繁的,那基于这个非频繁的k-1项集生成的k项集也一定不是频繁的,所以我们要基于频繁的 k-1项集去生成k项集作为频繁k项集的候选集,然后再进一步判断该候选集是否是频繁的。

现在我们进一步将a)步展开,详细步骤如下:

a1)扫描交易数据库D,生产候选1项集,计算各个1项集的支持度,基于最小支持度阈值,得到频繁1项集的集合;

a2)从k=2开始循环,由频繁k-1项集生成频繁k项集:

a2.1)连接步:由2个只有一项不同的频繁k-1项集连接后预先生成候选k项集;

a2.2)剪枝步:舍弃掉子集不是频繁项集的候选集,即该候选集的某个子集不在频繁k-1项集中;

a2.3)扫描交易数据库D,计算候选k项集的支持度,基于最小支持度阈值,得到频繁k项集;

a3)若当前的频繁k项集只有一个,则循环结束,否则回到a2)步;

五、Apriori算法的缺点

Apriori算法采用了逐层搜索的迭代的方法,算法简单明了,没有复杂的理论推导,也易于实现。但其有一些难以克服的缺点:

对数据库的扫描次数过多;

Apriori算法会产生大量的中间项集;

采用唯一支持度;

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,839评论 6 482
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,543评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 153,116评论 0 344
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,371评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,384评论 5 374
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,111评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,416评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,053评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,558评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2 325
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1 334
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,756评论 4 324
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,324评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2 355
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2 345

推荐阅读更多精彩内容