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
from numpy import *
from numpy import linalg as la def loadExData():
return array([[4, 4, 0, 2, 2],
[4, 0, 0, 3, 3],
[4, 0, 0, 1, 1],
[1, 1, 1, 2, 0],
[2, 2, 2, 0, 0],
[1, 1, 1, 0, 0],
[5, 5, 5, 0, 0]]) def loadExData2():
return array([[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5],
[0, 0, 0, 3, 0, 4, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 4, 0, 0, 1, 0, 4, 0],
[3, 3, 4, 0, 0, 0, 0, 2, 2, 0, 0],
[5, 4, 5, 0, 0, 0, 0, 5, 5, 0, 0],
[0, 0, 0, 0, 5, 0, 1, 0, 0, 5, 0],
[4, 3, 4, 0, 0, 0, 0, 5, 5, 0, 1],
[0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 4],
[0, 0, 0, 2, 0, 2, 5, 0, 0, 1, 2],
[0, 0, 0, 0, 5, 0, 0, 0, 0, 4, 0],
[1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0]]) def ecludSim(inA,inB):
return 1.0/(1.0 + la.norm(inA - inB)) def pearsSim(inA,inB):
if len(inA) < 3 : return 1.0
return 0.5+0.5*corrcoef(inA, inB, rowvar = 0)[0][1] def cosSim(inA,inB):
num = float(inA.T*inB)
denom = la.norm(inA)*la.norm(inB)
return 0.5+0.5*(num/denom) def standEst(dataMat,user,simMeas,item):
n=shape(dataMat)[1]
simTotal=0.0; ratSimTotal=0.0
for j in range(n):
userRating=dataMat[user,j]
if userRating==0:continue
overLap=nonzero(logical_and(dataMat[:,item].A>0,dataMat[:,j].A>0))[0]
if len(overLap)==0:similarity=0
else: similarity=simMeas(dataMat[overLap,item],dataMat[overLap,j])
#print（'the %d and%d similarity is: %f' %(item,j,similarity)）
simTotal+=similarity
ratSimTotal+=similarity*userRating
if simTotal==0: return 0
else: return ratSimTotal/simTotal
def svdEst(dataMat, user, simMeas, item):
n = shape(dataMat)[1]
simTotal = 0.0; ratSimTotal = 0.0
U,Sigma,VT = la.svd(dataMat)
Sig4 = mat(eye(4)*Sigma[:4]) #arrange Sig4 into a diagonal matrix
xformedItems = dot(dataMat.T , U[:,:4] )* Sig4.I #create transformed items
for j in range(n):
userRating = dataMat[user,j]
if userRating == 0 or j==item: continue
similarity = simMeas(xformedItems[item,:].T,\
xformedItems[j,:].T)
print ('the item%d and item%d similarity is: %f' % (item, j, similarity))
simTotal += similarity
ratSimTotal += similarity * userRating
if simTotal == 0: return 0
else: return ratSimTotal/simTotal def recommend(dataMat, user, N=3, simMeas=ecludSim, estMethod=standEst): unratedItems =nonzero(dataMat[user,:]==0)[0]
print("item that user don't eat before :")
print(unratedItems)
if len(unratedItems) == 0: return ('you rated everything')
itemScores = []
for item in unratedItems:
estimatedScore = estMethod(dataMat, user, simMeas, item)
itemScores.append((item, estimatedScore))
list_=sorted(itemScores, key=lambda jj: jj[1], reverse=True)[:N]
print("top %d item of list and score that recommend to user %d ：" %(N,user) )
return list_
def main():
myMat=loadExData2()#导入矩阵1
users=1
A=recommend(myMat,users,estMethod=svdEst)#用户0
print(A) if __name__ == '__main__':
main()