SVD在餐馆菜肴推荐系统中的应用

SVD在餐馆菜肴推荐系统中的应用

摘要：餐馆可以分为很多类别，比如中式、美式、日式等等。但是这些类别不一定够用，有的人喜欢混合类别。对用户对菜肴的点评数据进行分析，可以提取出区分菜品的真正因素，利用这些因素我们可以估计人们对没去过的餐厅的看法。提取这些信息的方法就是SVD（Singular Value Decomposition）。本文首先介绍SVD的数学原理，然后简单介绍推荐系统的相关原理，最后通过python编程实现简单的基于协同过滤的菜肴推荐系统。

关键词：SVD；推荐系统；python；协同过滤；

1. SVD数学原理

SVD是矩阵最终也是最好的分解，任意矩阵可分解为A=U，分解结果为正交矩阵U，对角阵和正交矩阵。

1.1 SVD在子空间的解释

可以将矩阵A 看做是一种线性变换，将其行空间的一个向量v1变换为其列空间中的向量u1=Av1。奇异值分解就是在行空间寻找一组正交基，将其通过矩阵A线性变换生成列空间中的一组正交基，将其通过矩阵A线性变换生成列空间中的一组正交基。如图1。

图1 四个子空间

1.1.1 SVD求解

问题核心：寻找行空间中一组特殊的正交基。

AV=U,由于V是正交矩阵，其逆等于转置，所以有A=U。

为了得到这两个正交矩阵，先处理其中一个。在等式A=U两侧分别乘上:

上式其实是正定矩阵的正交分解，vi是矩阵的特征向量，是特征值，用同样的办法可以求U，它的列向量就是矩阵的特征向量。

1.2 SVD应用

1.2.1 推荐系统

简单版本的推荐系统能够计算事物或者人之间的相似度。更先进的方法是先利用SVD从数据中构建一个主题空间，然后再在该空间下计算器相似度。图14-1中给出的矩阵，它是由餐馆的菜和品菜师对这些菜的意见构成的。品菜师可以采用1到5之间的整数对菜品进行打分。如果没有吃过，打分为0。

图2 菜品打分矩阵

对以上矩阵进行SVD分解，我们可以得到2个奇异值，代表2种主题。右图阴影Ed, Peter和Tracy对“烤牛肉”和“手撕猪肉”进行了评级，同时这三人未对其他菜评级。烤牛肉和手撕猪肉都是美式烧烤餐馆才有的菜，其他日式餐馆才有。所以2个奇异值代表这2种主题。

我们可以把奇异值想象成一个新的空间。与图2矩阵的5*7的矩阵不同，奇异值矩阵是2维的。在A=U中，将用户（行空间）映射到2个主题菜品空间中去，U将菜肴（列空间）映射到2个主题菜品空间中去。

推荐系统中可能用噪声数据，比如某个人对某些菜进行故意低分或高分。但是推荐系统抽取数据是基于主题的，这样就会取得比原始数据更好的推荐结果。

2. python实现

2.1 SVD实现

Numpy中有一个linalg的线性代数工具，可以帮我实现SVD分解。

U,Sigma,VT =linalg.svd(M)

输入矩阵M 返回U,Sigma,VT。

矩阵分解后Sigma是对角阵，而且Sigma对角线上的元素依次减小，而且前面的元素远远大于后面的元素，所以我们可以用前面的元素进行近似计算，从而减少计算量。原始数据就可以用下面的式子近似：

如图3，浅灰色区域是原始数据，黑色区域是矩阵近似计算所需要的数据。

图3 矩阵分解示意图

确定保留前几个奇异值，有很多启发式的策略，其中一个是保留矩阵中90%的能量信息。为了计算总能量信息我们将所有的奇异值平方求和。于是可以将奇异值的平方和累加到90%为止。另一个就是根据我们对数据的理解，指定保留前几个奇异值，这种方法虽然粗暴，但是也很有效。

2.2 基于协同过滤的推荐系统实现

协同过滤是将用户和其他用户的数据进行对比来进行推荐。本文的方法是在Python3.5下实现。

2.2.1程序模块

1读取矩阵（有2个矩阵可以读入）

2相似度计算（欧式距离，皮尔逊系数，余弦相似度）

3计算用户评分（从矩阵中选择用户没有品尝过的菜品，计算这些菜品与原来品尝过菜品的相似度）

4推荐（向用户推荐评分最高的K个菜，试验中K=3）

2.2.2运行

主函数中我们向用户1推荐，相似度计算采用余弦相似度，返回菜品编号及菜品得分。

[参考文献]

[1] Peter Harrington.《机器学习实战》.2013

[2] G.Strang.《Introduction to Linear Algebra》,2003

 1 from numpy import *
 2 from numpy import linalg as la
 3 
 4 def loadExData():
 5     return array([[4, 4, 0, 2, 2],
 6            [4, 0, 0, 3, 3],
 7            [4, 0, 0, 1, 1],
 8            [1, 1, 1, 2, 0],
 9            [2, 2, 2, 0, 0],
10            [1, 1, 1, 0, 0],
11            [5, 5, 5, 0, 0]])
12     
13 def loadExData2():
14     return array([[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5],
15            [0, 0, 0, 3, 0, 4, 0, 0, 0, 0, 3],
16            [0, 0, 0, 0, 4, 0, 0, 1, 0, 4, 0],
17            [3, 3, 4, 0, 0, 0, 0, 2, 2, 0, 0],
18            [5, 4, 5, 0, 0, 0, 0, 5, 5, 0, 0],
19            [0, 0, 0, 0, 5, 0, 1, 0, 0, 5, 0],
20            [4, 3, 4, 0, 0, 0, 0, 5, 5, 0, 1],
21            [0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 4],
22            [0, 0, 0, 2, 0, 2, 5, 0, 0, 1, 2],
23            [0, 0, 0, 0, 5, 0, 0, 0, 0, 4, 0],
24            [1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0]])
25     
26 def ecludSim(inA,inB):
27     return 1.0/(1.0 + la.norm(inA - inB))
28 
29 def pearsSim(inA,inB):
30     if len(inA) < 3 : return 1.0
31     return 0.5+0.5*corrcoef(inA, inB, rowvar = 0)[0][1]
32 
33 def cosSim(inA,inB):
34     num = float(inA.T*inB)
35     denom = la.norm(inA)*la.norm(inB)
36     return 0.5+0.5*(num/denom)
37 
38 
39 def standEst(dataMat,user,simMeas,item):  
40     n=shape(dataMat)[1] 
41     simTotal=0.0; ratSimTotal=0.0  
42     for j in range(n):  
43         userRating=dataMat[user,j]  
44         if userRating==0:continue   
45         overLap=nonzero(logical_and(dataMat[:,item].A>0,dataMat[:,j].A>0))[0]  
46         if len(overLap)==0:similarity=0  
47         else: similarity=simMeas(dataMat[overLap,item],dataMat[overLap,j])  
48         #print（'the %d and%d similarity is: %f' %(item,j,similarity)）  
49         simTotal+=similarity  
50         ratSimTotal+=similarity*userRating  
51     if simTotal==0: return 0  
52     else: return ratSimTotal/simTotal     
53 def svdEst(dataMat, user, simMeas, item):
54     n = shape(dataMat)[1]
55     simTotal = 0.0; ratSimTotal = 0.0
56     U,Sigma,VT = la.svd(dataMat)
57     Sig4 = mat(eye(4)*Sigma[:4]) #arrange Sig4 into a diagonal matrix
58     xformedItems = dot(dataMat.T , U[:,:4] )* Sig4.I  #create transformed items
59     for j in range(n):
60         userRating = dataMat[user,j]
61         if userRating == 0 or j==item: continue
62         similarity = simMeas(xformedItems[item,:].T,
63                              xformedItems[j,:].T)
64         print ('the item%d and item%d similarity is: %f' % (item, j, similarity))
65         simTotal += similarity
66         ratSimTotal += similarity * userRating
67     if simTotal == 0: return 0
68     else: return ratSimTotal/simTotal
69 
70 def recommend(dataMat, user, N=3, simMeas=ecludSim, estMethod=standEst):
71 
72     unratedItems =nonzero(dataMat[user,:]==0)[0]
73     print("item that user don't eat before :")
74     print(unratedItems)
75     if len(unratedItems) == 0: return ('you rated everything')
76     itemScores = []
77     for item in unratedItems:
78         estimatedScore = estMethod(dataMat, user, simMeas, item)
79         itemScores.append((item, estimatedScore))
80     list_=sorted(itemScores, key=lambda jj: jj[1], reverse=True)[:N]
81     print("top %d item  of list and score that recommend to user %d ：" %(N,user)  )
82     return list_
83 def main():
84     myMat=loadExData2()#导入矩阵1
85     users=1
86     A=recommend(myMat,users,estMethod=svdEst)#用户0
87     print(A)
88 
89 if __name__ == '__main__':
90     main()