基于协同过滤算法的推荐系统设计.doc
《基于协同过滤算法的推荐系统设计.doc》由会员分享，可在线阅读，更多相关《基于协同过滤算法的推荐系统设计.doc（11页珍藏版）》请在冰点文库上搜索。
基于协同过滤算法的推荐系统设计
一、绪论：
长尾理论。
二、协同过滤算法的定义：
（一）预定义：
要实现协同过滤算法，需要做以下的预定义：
1、邻域：
给定集合X，映射U：
X→P（P（X））（其中P（P（X））是X的幂集的幂集），U将X中的点x映射到X的子集族U（x）），称U（x）是X的邻域系以及U（x）中的元素（即X的子集）为点x的邻域，当且仅当U满足以下的邻域公理：
U1：
若集合A∈U（x），则x∈A。
U2：
若集合A，B∈U（x），则A∩B∈U（x）。
U3：
若集合A∈U（x），且A⊆B⊆X，则B∈U（x）。
U4：
若集合A∈U（x），则存在集合B∈U（x），使B⊆A，且∀y∈B，B∈U（y）。
2、皮尔逊相关系数：
皮尔逊相关系数是一种度量两个变量相似程度的一种方法，若变量X和变量Y线性相关，则其皮尔逊系数的z值域为[-1,1]。
系数值为1表示完全正相关；系数值为-1表示完全负相关。
3、曼哈顿距离：
4、欧几里得距离：
5、余弦相似度：
6、Jaccard相似度：
（二）基于用户的协同过滤算法：
在实际应用中，如果一个用户C需要得到个性化的推荐，那么根据这个用户过去喜欢过的物品，计算出与这个顾客有着相似偏好的用户，继而把这些相似的用户所喜欢的、且C没有喜好过的物品推荐给用户C，这就是基于用户的协同过滤算法的主要思路。
该方法主要包括两个步骤：
1、寻找和查询用户具有相似偏好的用户群体。
2、找到这些用户所喜欢的物品集合，选取其中用户最为感兴趣的子集推荐给查询用户。
在步骤1中，我们使用相似度来度量两个用户之间的相似度。
相似度的计算方法可以调用预定义中的皮尔逊相似度、余弦相似度、曼哈顿距离、欧几里得距离和jaccard相似度。
记用户A和用户B之间的相似度为sim
在得到用户的相似度之后，我们需要给查询用户返回根据其兴趣度的TopK结果，我们用如下公式衡量用户的兴趣度：
公式
其中S（u,K）代表相似用户集中的前K个用户，N（i）代表喜欢物品i的用户集合。
R代表用户u对物品i的感兴趣程度。
下图代表基于用户协同过滤算法的主要流程：
（三）基于物品的协同过滤算法：
在基于用户的协同过滤算法的基础上，又发展出了基于物品的协同过滤算法。
这主要是因为在一般的网站应用中，用户的数量往往远远大于物品的数量，这就造成了计算用户之间的相似度成为一件非常耗时的工作：
以余弦相似度为例。
设一个网站中的用户数为N，那么就需要维护一张N*N的矩阵，因而遍历矩阵计算相似度的时间复杂度为O（N*N），这在用户基数较大时其计算时间会明显增加。
基于物品的协同推荐算法的工作方式是先找到和用户历史上喜好过的物品相似的物品，然后返回这些物品中用户兴趣度最高的前K个物品。
基于物品的协同过滤算法也分为两步：
1、计算物品之间的相似度。
2、根据物品的相似度和用户的历史行为返回给用户的推荐列表。
在步骤1中，与基于用户的推荐算法相似，也使用皮尔逊相关系数、欧几里得距离等预定义中的相似度计算方法来计算物品之间的相似度。
记物品A和物品B之间的相似度为sim。
在得到物品间的相似度之后，通过以下公式计算对用户u来说，每个物品的感兴趣程度。
公式
这里N（u）代表某个用户的物品喜好集合，s（j，K）代表相似物品集合中相似度最高的前K个物品组成的子集。
三、SVD推荐算法：
1、矩阵分解和baseline预测
matrixfactorizationmodel
把我们的用户评分想象成一个表:
每一行代表一个用户,每一列代表一个物品,这其实就是一个矩形,只是我们拥有的这个矩形可能是非常稀疏的,也就是我们知道的评分占总量很少,,但现在我们知道它是一个矩形,一个矩形自然可以表示为另两个矩形的乘积:
这也就是matrixfactorizationmodel的原理了,我们需要做的就是通过已有数据来学习右边的两个矩形,更intuitive的你可以把总的矩形里的每个评分看成是该用户的特征向量与物品特征向量的内积:
（这里符号变得有些多,你理解了意思就成）
2.BaselinePredictors
BaselinePredictors就简单多了，我们设定μ是平均值，然后分别用bi和bu来代表具体用户和物品的“偏好”，也就是
这两个参数我们当然可以当成一个优化任务来计算，比如最小二乘：
也可以用比较快的方法来，因为实际上这就是经验似然：
1、SVD算法的原理
SVD（SingularValueDecomposition）的想法是根据已有的评分情况，分析出评分者对各个因子的喜好程度以及电影包含各个因子的程度，最后再反过来根据分析结果预测评分。
电影中的因子可以理解成这些东西：
电影的搞笑程度，电影的恐怖程度，等等。
根据这些因子，将N*M的评分矩阵（R[u][i]代表用户u对电影i的评分）分解成一个N行F列的用户因子矩阵P（P[u][k]表示用户u对因子k的喜好程度）和一个M行F列的物品因子矩阵Q（Q[i][k]表示第i个物品的因子k，具体见下述公式：
公式
下面是将评分矩阵R分解成用户因子矩阵P与物品因子矩阵Q的一个例子。
R的元素数值越大，表示用户越喜欢这部电影。
P的元素数值越大，表示用户越喜欢对应的因子。
Q的元素数值越大，表示物品对应的因子程度越高。
分解完后，就能利用P，Q来预测用户A对《等风来》的评分了。
按照这个例子来看，用户A应该会给《等风来》较低的分数。
因为他不喜欢幽默片。
表1
评分矩阵R
《阿甘正传》
《美丽人生》
《等风来》
用户A
5
3
？
用户B
2
4
5
表2
用户因子矩阵P
励志
幽默
用户A
1
0.1
用户B
0.2
1
表3
物品因子矩阵Q
励志
幽默
《阿甘正传》
5
0
《美丽人生》
3
3
《等风来》
0
5
实际上，我们给一部电影评分时，除了考虑电影是否合自己口味外，还会受到自己是否是一个严格的评分者和这部电影已有的评分状况影响。
例如：
一个严格评分者给的分大多数情况下都比一个宽松评分者的低。
你看到这部电影的评分大部分较高时，可能也倾向于给较高的分。
在SVD中，口味问题已经有因子来表示了，但是剩下两个还没有相关的式子表示。
因此有必要加上相关的部分，提高模型的精准度。
改进后的SVD的公式如下：
R=OverallMean+biasU+biasI+P*T（Q）
（1）
其中OverallMean表示所有电影的平均分，biasU表示用户评分偏离OverallMean的程度，biasI表示电影评分偏离OverallMean的程度，P，Q意思不变。
特别注意，这里除了OverallMean之后，其它几个都是矩阵。
分解完后，即
（1）式中的五个参数都有了正确的数值后，就可以用来预测分数了。
假设我们要预测用户u对电影i的评分：
bu表示第u个用户的偏离程度，bi表示第i部电影的偏离程度，pu表示第u个用户的因子爱好程度，qi表示第i部电影的因子程度。
2、参数学习：
为了得到用户因子P和物品因子Q，需要通过学习来得到矩阵的参数。
SVD使用随机梯度下降（stochasticgradientdescent）学习
（1）式中除了OverallMean之外的参数。
学习过程可以概括成这样：
先给各个参数一个初值，然后利用这些参数进行预测，并将预测结果与已知评分进行对比，最后根据对比结果修正各个参数。
更准确点的说法是调整参数的值，使得以下式子能取到最小值：
ALPHA表示所有训练样本。
被第一个圆括号括着的部分表示当前的预测结果与实际值的偏差。
被第二个圆括号括着的部分是为了防止过拟合（overfitting）。
四、基于MovieLens数据集的推荐系统设计
1、选取数据集：
为了实现协同过滤算法和SVD算法，需要选取一个合适的数据集来分析。
本文研究了以下数据集：
1、BookCrossing：
这个数据集是网上的Book-Crossing图书社区的278858个用户对271379本书进行的评分，包括显式和隐式的评分。
这些用户的年龄等人口统计学属性（demographicfeature）都以匿名的形式保存并供分析。
这个数据集是由Cai-NicolasZiegler使用爬虫程序在2004年从Book-Crossing图书社区上采集的。
2、JesterJoke：
JesterJoke是一个网上推荐和分享笑话的网站。
这个数据集有73496个用户对100个笑话作的410万次评分。
评分范围是-10~10的连续实数。
这些数据是由加州大学伯克利分校的KenGoldberg公布的。
3、Netflix：
这个数据集来自于电影租赁网址Netflix的数据库。
Netflix于2005年底公布此数据集并设立百万美元的奖金（netflixprize），征集能够使其推荐系统性能上升10％的推荐算法和架构。
这个数据集包含了480189个匿名用户对大约17770部电影作的大约lO亿次评分。
4、UsenetNewsgroups：
这个数据集包括20个新闻组的用户浏览数据。
最新的应用是在KDD2007上的论文。
新闻组的内容和讨论的话题包括计算机技术、摩托车、篮球、政治等。
用户们对这些话题进行评价和反馈。
5、MovieLens：
MovieLens数据集中，用户对自己看过的电影进行评分，分值为1～5。
MovieLens包括两个不同大小的库，适用于不同规模的算法．小规模的库是943个独立用户对1682部电影作的100000次评分的数据；大规模的库是6040个独立用户对3900部电影作的大约100万次评分。
在分析、比较各数据集的特性之后，发现MovieLens的数据集所涉及的主题—电影较为贴近我们的日常生活，因而具有较大的实用价值，且该数据库数据较为规范、不存在空值等需要进行数据清洗的情况，因而选择MovieLens作为分析实用的数据集。
在MovieLens中，有大、中、小三个不同大小的数据集，因为本项目是个人开发，所以选择规模最小的“MovieLens-100K”数据集，其中包含了943个独立用户对1682部电影作的100000次评分的数据。
2、数学建模：
在数据集“MovieLens-100k”中，需要用到三个数据文件，分别是“u.data”、“u.item”、“u.user”。
“user.data”中包含943个独立用户对1682部电影作的100000次评分的数据。
每个用户都至少对20部进行了打分。
我们将其分为用户编号、电影编号、打分分值、打分之间等4个属性，以下述的形式存入数组：
userid|itemid|rating|timestamp.
其中timestamp为用户评分的时间戳。
“u.item”保存了电影的信息，我们讲其分为电影编号、电影标题、上映时间、视频发行时间、IMDB链接、类别等属性，表示为下述的数组：
movieid|movietitle|releasedate|videoreleasedate|
IMDbURL|category|
“u.user”保存了评分人的信息，将其分类为用户编号、年龄、性别、职业、解压密码等属性，以下述数组的形式储存：
userid|age|gender|occupation|zipcode
将u.data按7：
1分为训练集和测试集，具体方法见下述伪代码：
defdataSplit（data,M,k,seed）
test=empty
train=empty
foruser,itemindata:
ifrandom（0,M）==k:
test.append（user,item）
else
train.append（user,item）
returntest,train
3、算法实现：
对于数据集“MovieLens-100k”调用载第二章所属的基于用户协同过滤算法、基于物品的协同过滤算法和SVD算法，其中相似度的计算方法调用预定义中的皮尔逊相关系数等6中方法。
下面给出个算法的伪代码：
（1）基于用户的协同过滤算法：
defUserSimilarity（train）:
item_user=dict（）
foru,itemsintrain.items:
foriinitem.keys（）
ifiinitem.keys（）:
item_user[i].add（u）
C=empty
N=empty
fori,usersinitem_users.items（）:
foruinusers:
N（u）+=1
forvinusers:
ifu==v:
continue
C[u][v]+=1
W=empty
foru.related_usersinC.items（）:
forv.cuvinrelated_users.items（）:
W[u][v]=cuv/math.sqrt（N（u）*N（v））
returnW
defRecommand（user,train,W）:
rank=emptydict
interacted_items=train[user]
forv,wuvinsorted（W[u].items,key=itemgetter
（1）,\reverse=true）
forirviintrain[v].item（）:
ifiininteracted_items[v].items（）:
continue
rank[i]+=wuv*rvi
returnrank
（2）基于物品的协同过滤算法：
defUserSimilarity（train）:
item_user=dict（）
foru,itemsintrain.items:
foriinitem.keys（）
ifiinitem.keys（）:
item_user[i].add（u）
C=empty
N=empty
fori,usersinitem_users.items（）:
foruinusers:
N（u）+=1
forvinusers:
ifu==v:
continue
C[u][v]+=1
W=empty
foru.related_usersinC.items（）:
forv.cuvinrelated_users.items（）:
W[u][v]=cuv/math.sqrt（N（u）*N（v））
returnW
defRecommand（user,train,W）:
rank=emptydict
interacted_items=train[user]
forv,wuvinsorted（W[u].items,key=itemgetter
（1）,\reverse=flase）
forirviintrain[v].item（）:
ifiininteracted_items[v].items（）:
continue
rank[i]+=wuv*rvi
returnrank
（3）SVD算法：
from__future__importdivision
importnumpyasnp
importscipyassp
fromnumpy.randomimportrandom
classSVD_C:
def__init__（self,X,k=20）:
'''
kisthelengthofvector
'''
self.X=np.array（X）
self.k=k
self.ave=np.mean（self.X[:
2]）
print"theinputdatasizeis",self.X.shape
self.bi={}
self.bu={}
self.qi={}
self.pu={}
self.movie_user={}
self.user_movie={}
foriinrange（self.X.shape[0]）:
uid=self.X[i][0]
mid=self.X[i][1]
rat=self.X[i][2]
self.movie_user.setdefault（mid,{}）
self.user_movie.setdefault（uid,{}）
self.movie_user[mid][uid]=rat
self.user_movie[uid][mid]=rat
self.bi.setdefault（mid,0）
self.bu.setdefault（uid,0）
self.qi.setdefault（mid,random（（self.k,1））/10*（np.sqrt（self.k）））
self.pu.setdefault（uid,random（（self.k,1））/10*（np.sqrt（self.k）））
defpred（self,uid,mid）:
self.bi.setdefault（mid,0）
self.bu.setdefault（uid,0）
self.qi.setdefault（mid,np.zeros（（self.k,1）））
self.pu.setdefault（uid,np.zeros（（self.k,1）））
if（self.qi[mid]==None）:
self.qi[mid]=np.zeros（（self.k,1））
if（self.pu[uid]==None）:
self.pu[uid]=np.zeros（（self.k,1））
ans=self.ave+self.bi[mid]+self.bu[uid]+np.sum（self.qi[mid]*self.pu[uid]）
ifans>5:
return5
elifans<1:
return1
returnans
deftrain（self,steps=20,gamma=0.04,Lambda=0.15）:
forstepinrange（steps）:
print'the',step,'-thstepisrunning'
rmse_sum=0.0
kk=np.random.permutation（self.X.shape[0]）
forjinrange（self.X.shape[0]）:
i=kk[j]
uid=self.X[i][0]
mid=self.X[i][1]
rat=self.X[i][2]
eui=rat-self.pred（uid,mid）
rmse_sum+=eui**2
self.bu[uid]+=gamma*（eui-Lambda*self.bu[uid]）
self.bi[mid]+=gamma*（eui-Lambda*self.bi[mid]）
temp=self.qi[mid]
self.qi[mid]+=gamma*（eui*self.pu[uid]-Lambda*self.qi[mid]）
self.pu[uid]+=gamma*（eui*temp-Lambda*self.pu[uid]）
gamma=gamma*0.93
print"thermseofthisstepontraindatais",np.sqrt（rmse_sum/self.X.shape[0]）
#self.test（test_data）
deftest（self,test_X）:
output=[]
sums=0
test_X=np.array（test_X）
#print"thetestdatasizeis",test_X.shape
foriinrange（test_X.shape[0]）:
pre=self.pred（test_X[i][0],test_X[i][1]）
output.append（pre）
#printpre,test_X[i][2]
sums+=（pre-test_X[i][2]）**2
rmse=np.sqrt（sums/test_X.shape[0]）
print"thermseontestdatais",rmse
returnoutput
4、评分标准：
对于系统返回的推荐结果，需要对推荐的结果做出评价。
一个完整的推荐系统一般存在3个参与方：
用户、物品提供者和提供推荐的网站，因此在测评一个推荐系统时，需要同时考虑三方的利益，一个好的推荐系统可以使三方收益。
好的推荐系统不仅可以准确预测用户的行为，而且可以拓展用户的视野，帮助用户发现可能的潜在兴趣。
同时，推荐系统还要帮助商家将被埋没在长尾中的物品推荐给可能感兴趣的用户。
本着这样的目的，本文使用了以下几种测评标准来衡量推荐结果的好坏：
1、预测准确度：
预测准确度度量一个推荐系统预测用户行为的能力。
这个指标是最重要的系统离线测评指标。
在训练集trainingset中建立用户行为和兴趣模型，预测用户在测试集上的行为，并将预测行为和测试行为的重合度作为预测的准确度。
对于MovieLens这种打分型的数据集，一般使用均方根误差（RMSE）来作为预测准确度的测评标准。
对于测试集中的一个用户u和物品i，令Rui是用户对物品的实际评分，而Rui是推荐算法给出的预测评分，则RMSE的定义为：
公式
下面给出计算RMSE的伪代码：
defRMSE（records）：
re
升级会员 