推荐算法--基于物品的协同过滤及Spark实现
本帖最后由 喵十八 于 2018-9-22 11:07 编辑问题导读
1. 基于物品的协同过滤是什么？其核心思想是什么？
2. 使用Python如何实现基于物品的协同过滤？
3. 在大数据集群上，用Spark如何实现基于物品的协同过滤？
关注最新经典文章，欢迎关注公众号
http://www.aboutyun.com/data/attachment/forum/201406/15/084659qcxzzg8n59b6zejp.jpg
综述
本文基于项亮大神的《推荐系统实践》介绍基于物品的协同过滤，并用python和spark分别进行了实现。
基于物品的协同过滤（item-based collaborative filtering）算法是目前业界应用最多的算法。无论是亚马逊网，还是Netflix、 Hulu、 YouTube，其推荐算法的基础都是该算法。
基于物品的协同过滤算法（简称ItemCF）给用户推荐那些和他们之前喜欢的物品相似的物品。比如，该算法会因为你购买过《数据挖掘导论》而给你推荐《机器学习》。不过， ItemCF算法并不利用物品的内容属性计算物品之间的相似度，它主要通过分析用户的行为记录计算物品之间的相似度。该算法认为，物品A和物品C具有很大的相似度是因为喜欢物品A的用户大都也喜欢物品C。
如图所示：
算法基本步骤
基于物品的协同过滤算法主要分为两步：
一、计算物品之间的相似度；
二、根据物品的相似度和用户的历史行为给用户生成推荐列表；
计算相似度
主要使用如下公式进行计算：
其中，|N(i)|是喜欢物品i的用户数，|N(j)|是喜欢物品j的用户数，|N(i)&N(j)|是同时喜欢物品i和物品j的用户数。
从上面的定义看出，在协同过滤中两个物品产生相似度是因为它们共同被很多用户喜欢，两个物品相似度越高，说明这两个物品共同被很多人喜欢。
这里面蕴含着一个假设：就是假设每个用户的兴趣都局限在某几个方面，因此如果两个物品属于一个用户的兴趣列表，那么这两个物品可能就属于有限的几个领域，而如果两个物品属于很多用户的兴趣列表，那么它们就可能属于同一个领域，因而有很大的相似度。
下是一个根据上面的程序计算物品相似度的简单例子。图中最左边是输入的用户行为记录，每一行代表一个用户感兴趣的物品集合。然后，对于每个物品集合，我们将里面的物品两两加一，得到一个矩阵。最终将这些矩阵相加得到上面的C矩阵。其中C记录了同时喜欢物品i和物品j的用户数。最后，将C矩阵归一化可以得到物品之间的余弦相似度矩阵W。
生成推荐列表：
ItemCF通过如下公式计算用户u对一个物品j的兴趣：
这里N(u)是用户喜欢的物品的集合， S(j,K)是和物品j最相似的K个物品的集合， wji是物品j和i的相似度， rui是用户u对物品i的兴趣。（对于隐反馈数据集，如果用户u对物品i有过行为，即可令
rui=1。）该公式的含义是，和用户历史上感兴趣的物品越相似的物品，越有可能在用户的推荐列表中获得比较高的排名。
代码实现
根据《推荐系统实践》 给出了如下python 版本的相似度计算
def calc_movie_sim(self):
for user, movies in self.trainset.items():
for movie in movies:
if movie not in self.movie_popular:
self.movie_popular = 0
self.movie_popular += 1
print('count movies number and pipularity succ', file=sys.stderr)
self.movie_count = len(self.movie_popular)
print('total movie number = %d' % self.movie_count, file=sys.stderr)
itemsim_mat = self.movie_sim_mat
print('building co-rated users matrix', file=sys.stderr)
for user, movies in self.trainset.items():
for m1 in movies:
for m2 in movies:
if m1 == m2:
continue
itemsim_mat.setdefault(m1, {})
itemsim_mat.setdefault(m2, 0)
itemsim_mat += 1
print('build co-rated users matrix succ', file=sys.stderr)
print('calculating movie similarity matrix', file=sys.stderr)
simfactor_count = 0
PRINT_STEP = 2000000
for m1, related_movies in itemsim_mat.items():
for m2, count in related_movies.items():
itemsim_mat = count / math.sqrt(self.movie_popular * self.movie_popular)
simfactor_count += 1
if simfactor_count % PRINT_STEP == 0:
print('calcu movie similarity factor(%d)' % simfactor_count, file=sys.stderr)
print('calcu similiarity succ', file=sys.stderr)
整体效率还是比较低的。因为我们实际的业务，使用的spark进行ELT。为了存储方便，将数据存储为稀疏矩阵的形式，如下：
User movie1:ratting1 movie2:ratting2 .....
使用load_svmlight_file 导入，然后直接调用jaccard 距离计算。
def get_data(filename):
data = load_svmlight_file(filename)
return data, data
# 计算jaccard 相似度
def get_jaccard_similarity(X):
n = X.T.shape
similarity = np.zeros()
for i in range(n):
v1 = X.T.toarray()
for j in range(i + 1, n):
v2 = X.T.toarray()
sim = jaccard_similarity_score(v1, v2)
similarity = sim
similarity = sim
return similarity
例子解释
用户喜欢《C++ Primer中文版》和《编程之美》两本书。然后ItemCF会为这两本书分别找出和它们最相似的3本书，然后根据公式的定义计算用户对每本书的感兴趣程度。比如， ItemCF给用户推荐《算法导论》，是因为这本书和《C++Primer中文版》相似，相似度为0.4，而且这本书也和《编程之美》相似，相似度是0.5。考虑到用户对《C++ Primer中文版》的兴趣度是1.3，对《编程之美》的兴趣度是0.9，那么用户对《算法导论》的兴趣度就是1.3 × 0.4 + 0.9×0.5 = 0.97。
过程如图：
Spark实现
因为数据都在CDH集群上，且量比较大，download到本地资源浪费比较明显，基于BitSet写了一版Spark版本计算Jaccard距离的。
使用BitSet 比较节约资源。
代码如下：
/**
* 使用BitSet 计算jaccard 距离
*/
def computeItemJaccardSim(sc: SparkContext,
featurePath: String,
simOutPath: String): Unit ={
val rdd = sc.textFile(featurePath)
.map(_.split(" ", 2)(1))
.zipWithIndex()
.map(x => (x._2.toInt,x._1.split(" ", -1)))
.map(x=>{
for (i <- x._2) yield {
(i.split("\\:")(0), x._1)
}
}).flatMap(x=>x)
.map(x=>(x._1,BitSet(x._2.toString.toInt)))
.reduceByKey(_.union(_))
val re = rdd.cartesian(rdd).map {
case((key0,set0),(key1,set1))=>{
val key=key0+","+key1
val j = (set0 &(set1)).size
val q = set0.union(set1).size
val re = j.toDouble/q
key+","+re
}
}
re.saveAsTextFile(simOutPath)
println("compute jaccard sim success!")
}
总结
介绍了基于物品协同过滤的基本概念，并给出了相关实现代码。代码、数据集整理在如下github 欢迎star
基于物品的协同过滤及Spark实现， 很好 学习学习
页:
[1]