推荐算法之协同过滤实战

标签: 推荐算法 协同过滤 | 发表时间:2014-02-01 23:02 | 作者:liuzhiqiangruc
出处:http://www.iteye.com

协同过滤(Collective Filtering)可以说是推荐系统的标配算法。

在谈推荐必谈协同的今天,我们也来谈一谈基于KNN的协同过滤在实际的推荐应用中的一些心得体会。

 

我们首先从协同过滤的两个假设聊起。

 

两个假设:

  1. 用户一般会喜欢与自己喜欢物品相似的物品
  2. 用户一般会喜欢与自己相似的其他用户喜欢的物品

上述假设分别对应了协同过滤的两种实现方式:基于物品相似(item_cf)及基于用户相似(user_cf)。

 

因此,协同过滤在实现过程中,最本质的任务就是计算相似度的问题,包括计算item之间的相似度,或user之间的相似度。

要计算相似度,就需要一个用来计算相似度的表达。 

 

 

输入数据: 

而协同过滤的输入是一个用户对item的评分矩阵,如下图所示:

 

这种输入数据中,没有关于item或user的任何扩展描述。

因此item和user之间只能互为表达,用所有用户对某item的评分来描述一个item,以及用某个用户所有评分的item来描述该用户本身。分别对应途中的行向量和列向量。

 

这样,我们只需要搞定向量之间相似度的计算问题就OK了。

 

 

相似度计算:

以Item相似度为例,我们一般使用如下的公式完成相似度的计算:

 

其中:

Wij表示标号为i,j的两个item的相似度

U(i,j)表示同时对i,j有评分的用户的集合

Rui表示用户u对item i的评分

参数lambda为平滑(惩罚)参数

 

当然,相似度的计算有很多可选的方案, 例如直接计算两个向量夹角的cos值。只是通过实验发现,文中提到的方法在Lz的实际推荐应用中,效果要略好而已。

对于user相似度则只需要把输入矩阵转置看待即可。

 

评分预测过程:

仍以item_cf为例,在得到item相似度之后,可以通过一个矩阵乘法运算来为输入数据中的空白处计算一个预测值。

将输入矩阵看成一个n*m的矩阵,记为A,n为用户数,m为item数。而计算得到的相似度矩阵为一个m*m的矩阵,记为B。

则预测评分的过程就是A*B的过程,结果也是一个n*m的矩阵。

具体公式如下:

 

 

 其中bi为歌曲本身的流行程度,可通过其他方式计算得到。

 

 

相似度计算的复杂度:

item相似度计算的复杂度:输入矩阵A(n*m) 中的用户数为n,item数为m,则要计算出一个m*m的相似度矩阵的话共需要O=m*m*n*d,d为数据的稀疏度。

假设n=200w,m=5w,数据稀疏度为1%,则O=50万亿。好在该过程可以很方便地使用map-reducer的方式在hdfs上分布式实现。

再假设你通过1000个计算节点来完成,则每个计算节点上的复杂度O1=5000亿。

user相似度计算的复杂度:O=n*n*m*d,假设计算资源仍为1000,则每个计算节点的复杂度为O1=2000万亿。

 

相似度计算的两种实现方式:

 

 一般来讲,item的量都是比较小的,而且固定,而用户的量会比较大,而且每天都可能会不一样。

因此,在计算过程中的实用策略也不同,大体上有如下两种:

 

1. 倒排式计算:

这种方式尤其适用于用户量较大,而item量较小,且每个用户已评分的item数较少的情况。

具体做法就是:

在MR的map阶段将每个用户的评分item组合成pair <left,right,leftscore,rightscore> 输出,left作为分发键,left+right作为排序键。

在reduce阶段,将map中过来的数据扫一遍即可求得所有item的相似度。

 

详细Hadoop过程如下所示:

 

 

 

该方式的好处在于没有关联的item之间不会产生相似度的计算开销,所谓没有关联指没有任何一个用户对某两个item都有评分。

不好的地方在于,如果某些用户评分数据较多,则产生的pair对会十分巨大,在map和reducer之间会有极大的IO开销。

 

2. 矩阵分块计算:

这种计算方式适用于用户量远大于item量的情况下,用户相似度的计算过程。 

具体做法:将评分矩阵M切分成多个小块,每个小块与原矩阵的转置矩阵做类似矩阵乘法的运算(按照文中提到的相似度计算公式,而非向量点击),

最后将计算得到的结果合并即可。

 

详细Hadoop过程如下所示:

 

 

 

该方式的好处是避免map与reducer之间的大量缓存,而且这种方式压根不需要reducer。

不好的地方在于transpose(M)需要在任务开始计算前缓存在每个hadoop计算节点,在矩阵M较大的时候会影响任务的启动效率。

 

总之,两种方式各有优劣,在精确计算user之间或item之间的相似度时需要根据实际的数据特点选择合适的计算方式。

 

然而,随着业务的增长,评分矩阵会越来越大,同时也会越来越稠密。

这是无论采用哪一种方式,都无法完成相似度计算的工作了,这时精确地计算user之间或item之间的相似度已经变得可望而不可即。

而且,考虑实际的推荐场景,在数据足够多的情况下,相似度的精确计算也就没有必要了。

 

基于SimHash的相似度计算:

 

当数据量太大时,往往只需要求得一个与最优解相近的近似解即可,相似度的计算也是如此。

基于SimHash计算用户之间或item之间的相似度是推荐中较为常用的技巧。

 

该方法之所以能够work,主要基于如下两点:1.hash的随机性,2.数据足够多。

这两点决定了通过simhash计算得到的相似度是否靠谱。

而关于SimHash的具体原理,本文不做详述,不熟悉的同学可参阅链接 simhash算法原理或其他相关资料。

 

这里主要介绍下自己在实际工作中的做法:

首先Hash函数的选择:

本人在实际工作中尝试了两种Hash函数:

1. DJBX33A,将字符串映射成一个64位的无符号整数。具体实现参考: DJBX33A哈希函数实现

 

2. MD5, 将字符串映射成一个128为的二进制流。本人在实际工作中使用char[16]来表示。

 

汉明距离与相似度:

在计算得到每个对象的hashsign之后,可进一步得到两个hashsign的汉明距离。假设最终的sign为n维,则汉明距离最大为n,最小为0.

分别对应相似度为-1,1。当汉明距离为n/2时,两个hashsign对应的对象之间的相似度为0,也可以理解为他们的家教为 PI/2。

 

汉明距离的计算:

1. 如果hashcode在64位以内,最终计算的hashsign可以使用计算机内置的类型来表示,如unsigned long。

    然后对两个对象的hashsig按位异或,然后计算结果中有多少位为1,即为汉明距离值。

 

2. 如果hashcode大于64位,例如MD5,则需要一个复合结构来表示。我们可以使用char[16]来表示128bit。

    然后再计算汉明距离时分别使用两个unsigned long 来表示高位的64bit和低位的64bit。

 

实践证明,通过simhash计算的到的相似度,与真实的相似度之间几乎等同。

而且,在实际应用中,通过simhash的推荐结果,鲁棒性也更强。

 

目前为止,SimHash的计算中,MD5是效果最好的hash函数。

 

 



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [推荐算法 协同过滤] 推荐:

基于综合兴趣度的协同过滤推荐算法

- - IT技术博客大学习
标签:   兴趣   协同过滤   推荐. 电子商务推荐系统最大的优点在于它能收集用户的兴趣资料和个人信息,根据用户兴趣偏好主动为用户做出个性化推荐. 推荐技术指的是如何找出用户感兴趣的商品并列出推荐清单,在用户信息获取差别不大的情况下,推荐技术成为决定一个推荐系统性能的关键,其中推荐算法是推荐技术的核心[1].

推荐算法之协同过滤实战

- - 互联网 - ITeye博客
协同过滤(Collective Filtering)可以说是推荐系统的标配算法. 在谈推荐必谈协同的今天,我们也来谈一谈基于KNN的协同过滤在实际的推荐应用中的一些心得体会. 我们首先从协同过滤的两个假设聊起. 用户一般会喜欢与自己喜欢物品相似的物品. 用户一般会喜欢与自己相似的其他用户喜欢的物品.

推荐算法之基于用户的协同过滤算法

- - CSDN博客综合推荐文章
协同过滤是推荐算法中最基本的算法,主要分为基于用户的协同过滤算法和基于物品的协同过滤算法. 这篇文章主要介绍基于用户的协同过滤算法,简单来说,要给用户u作推荐,那么只要找出那些和u之前的行为类似的用户,即和u比较像的用户,把他们的行为推荐给用户u即可. 所以基于用户的系统过滤算法包括两个步骤:1)找到和目标用户兴趣相似的用户集合  2)找到这个集合中的用户喜欢的,且目标用户没有听说过的物品推荐给目标用户.

协同过滤推荐算法的原理及实现

- - 蓝鲸的网站分析笔记
协同过滤推荐算法是诞生最早,并且较为著名的推荐算法. 算法通过对用户历史行为数据的挖掘发现用户的偏好,基于不同的偏好对用户进行群组划分并推荐品味相似的商品. 协同过滤推荐算法分为两类,分别是基于用户的协同过滤算法(user-based collaboratIve filtering),和基于物品的协同过滤算法(item-based collaborative filtering).

[推荐算法]ItemCF,基于物品的协同过滤算法 - 在路上的学习者 - CSDN博客

- -
ItemCF:ItemCollaborationFilter,基于物品的协同过滤. 算法核心思想:给用户推荐那些和他们之前喜欢的物品相似的物品. 比如,用户A之前买过《数据挖掘导论》,该算法会根据此行为给你推荐《机器学习》,但是ItemCF算法并不利用物品的内容属性计算物品之间的相似度,它主要通过分析用户的行为记录计算物品之间的相似度.

协同过滤算法

- - CSDN博客推荐文章
今天要讲的主要内容是 协同过滤,即Collaborative Filtering,简称 CF.    关于协同过滤的一个最经典的例子就是看电影,有时候不知道哪一部电影是我们喜欢的或者评分比较高的,那.    么通常的做法就是问问周围的朋友,看看最近有什么好的电影推荐. 在问的时候,都习惯于问跟自己口味差不.

协同过滤 Collaborative Filtering

- - IT技术博客大学习
   协同过滤算法是推荐系统中最古老,也是最简单高效的推荐算法. 简单说协同过滤就是根据以往的用户产生的数据分析,对用户的新行为进行匹配分析来给用户推荐用户最有可能感兴趣的内容.    协同过滤算法是为了解决 长尾现象,也就是说推荐系统是为了解决长尾现象而诞生的. 因为在之前在有限的空间(如:书店的书架、服装店的衣架、商店的货架、网页的展示区域)只能摆有限的物品进行展示,造成大量的非热门物品很难进入人们的视野,也就无法产生任何价值.

协同过滤和推荐引擎

- - 刘思喆@贝吉塔行星
推荐系统在个性化领域有着广泛的应用,从技术上讲涉及概率、抽样、最优化、机器学习、数据挖掘、搜索引擎、自然语言处理等多个领域. 东西太多,我也不准备写连载,今天仅从基本算法这个很小的切入点来聊聊推荐引擎的原理. 推荐引擎(系统)从不同的角度看有不同的划分,比如:. 按照数据的分类:协同过滤、内容过滤、社会化过滤.

Spark MLlib中的协同过滤

- - JavaChen Blog
本文主要通过Spark官方的例子理解ALS协同过滤算法的原理和编码过程,然后通过对电影进行推荐来熟悉一个完整的推荐过程. 协同过滤常被应用于推荐系统,旨在补充用户-商品关联矩阵中所缺失的部分. MLlib当前支持基于模型的协同过滤,其中用户和商品通过一小组隐语义因子进行表达,并且这些因子也用于预测缺失的元素.