当前位置: 首页 > 推荐系统 > 正文

推荐系统的关联规则推荐

1 星2 星3 星4 星5 星 (1 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

说到推荐系统,就不能不说关联规则。基于关联规则的推荐,是入门级的推荐技术实现,也是目前应用最广泛的一种推荐形式。

就拿刚上线的“蚂蚁”来说吧,打开《引爆流行》的页面,稍微滚动两下鼠标,你就可以看到这个了——“喜欢此宝贝的会员还喜欢”。豆瓣上也有类似的形式,还看《引爆流行》,豆瓣的是——“喜欢引爆流行的人也喜欢”。是不是很像?但别被形式迷惑了,这两个用的是完全不同的技术实现。豆瓣的之前我说过了,他是 Item-Based 方法;蚂蚁的这个应该就是关联规则方法了。当然我是猜的,不过也不是乱猜。有兴趣的可以刷刷上面那两个《引爆流行》的页面,看一下两个推荐区域的内容会有什么不同。

关联规则起源于数据挖掘领域,人们用它来发现大量数据中项集之间(有趣/有用)的关联。它本身是数据挖掘领域中一个重要的研究课题,近些年来更是由于被业界广泛应用而倍受重视。Rakesh Agrawal 是关联规则领域的大牛,他于 1993 年发表的一篇 paper,《Mining Association Rules between Sets of Items in Large Databases》,是被引用最多的一篇大作。不过让 google fans 们失望的是,他目前就职于 microsoft 的搜索实验室!

关联规则的最典型例子就是购物篮分析。在一家超市里,有一个有趣的现象:尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话,而是发生在美国沃尔玛连锁店超市的真实案例,并一直为商家所津津乐道。原来,美国的妇女们经常会嘱咐她们的丈夫下班以后要为孩子买尿 布。而丈夫在买完尿布之后又要顺手买回自己爱喝的啤酒,因此啤酒和尿布在一起购买的机会还是很多的。这个故事听起来是不是很酷?没错,这就是技术的力量!

但是,和任何其他经典的故事一样——这事儿听起来带劲儿,做起来很难!真正做过关联规则挖掘的人,一定都有这样的体会:想从浩瀚的记录集里,挖掘一条带劲儿的关联规则出来,简直太难了。(什么,你问有多难?请参照朱广沪~~~)

对于挖掘得到的关联规则,都会制定一些指标来衡量它们的有效程度,最经典的包括,支持度和置信度。简单来讲,
支持度是指,商品A、商品B在全部销售订单中所占的比例。
置信度是指,购买商品A并且同时购买了商品B的订单,在所有包含商品A的订单中所占的比例。
当然,这里的商品和订单是个泛化的概念,具体指代是的什么,就得具体问题具体分析了。

Apriori Algorithm 是关联规则领域里最具影响力的基础算法。它是由 Rakesh Agrawal 在 1994 年提出的,详细的介绍在这里《Fast Algorithms for Mining Association Rules》。十几年过去了,不少学者围绕着 Apriori 进行了诸多改良。但与 1994 年相比,目前基于互联网的应用,数据量大了几十倍甚至是几百倍,因此,基于 Apriori 的算法逐渐暴露出其运算成本过高的问题。但不管怎样,对于大师及其做出的贡献,我们也只有高山仰止的份儿。

Apriori 是一种广度优先算法,通过多次扫描数据库来获取支持度大于最小支持度的频繁项集。它的理论基础是频繁项集的两个单调性原则:频繁项集的任一子集一定是频繁的;非频繁项集的任一超集一定是非频繁的。晦涩的理论我这里就不多写了,有兴趣的可以去看论文。我把里面的例子给翻译一下,图文并茂,简明易懂。

某数据库 DB 里有 4 条事务记录,取最小支持度(min support)为 0.5,则计算频繁项集的过程如下:
2d6d5c093c4a36f83ac76366
如上可以看出,在海量数据的情况下,Apriori 算法的运算过程有 2 个问题:
需要多次扫描数据库,时间成本很高;
运算过程中需要产生大量的候选集,空间成本也非常高。
针对 Apriori 算法所做的改进也基本上是围绕着解决这两个问题进行的,如在扫描DB前首先进行以便事务合并和压缩,数据分区或抽样等。

Weka 里有 Apriori 算法的 Java 实现,非常值得一看。
貌似 wikipedia 已经解封了,呵呵!
预报:关联规则(3),关于 FP-Growth 算法。

本文固定链接: http://www.chepoo.com/recommended-system-recommended-association-rules.html | IT技术精华网

推荐系统的关联规则推荐:等您坐沙发呢!

发表评论