奇异值分解在协同过滤推荐算法中的应用
目录
推荐算法介绍
协同过滤算法
电影推荐系统
基于用户（项目）的协同过滤算法
基于模型的协同过滤算法
对缺失的地方进行填充---传统SVD
Funk-SVD
推荐算法介绍
所谓推荐算法，即根据用户的历史信息，去寻找每个用户可能关心的项目。例如淘宝根据用户的历史购买记录，用推荐算法去寻找每个用户关心的产品。抖音根据用户的浏览记录，用推荐算法去寻找每个用户关心的视频等等。
在推荐算法中比较常用的是协同过滤算法。本文主要详细介绍协同过滤是算法。
协同过滤算法
协同过滤算法，一般分为三大类：
1、基于用户的协同过滤算法。
2、基于项目的协同过滤算法。
3、基于模型的协同过滤算法。
在下文中用一个简单的例子，对每类进行具体介绍和算法实现。
电影推荐系统
已知某电影平台的用户观看电影后给出的电影评分数据如下所示：
| __ | 电影1 | 电影2 | 电影3 |
|---|---|---|---|
| 用户1 | 1 | 0 | 7 |
| 用户2 | 9 | 6 | 4 |
| 用户3 | 5 | 7 | 0 |
| 用户4 | 0 | 7 | 1 |
为清晰的讲清楚算法的来龙去脉和流程，数据集不采用繁琐的真实数据进而省去数据预处理，把数据集简化为4x3矩阵。
上表的行名是用户名称，列名是电影名称，表里面的数字为用户对电影的评级，评级为1到10级，评级也大说明用户越喜爱这个电影，0代表用户尚未观看电影。
现在的问题就是把用户未观看的电影，且用户可能关心的电影推荐给用户。怎么去衡量用户对未观看电影的评价，就是本推荐算法解决的问题。
对于以上问题。可以分别从两个角度解决问题，第一是用户的角度，既以用户协同过滤寻求推荐算法，第二是项目的角度，既以项目协同过滤寻求推荐算法。
基于用户（项目）的协同过滤算法。
基于用户的协同过滤算法为：以用户为样本点，寻求用户的相似性，根据用户的相似性推荐对应的电影给对应的用户。
基于项目的协同过滤算法为：以项目为样本点，寻求项目的相似性，根据项目的相似性推荐对应的电影给对应的用户。
在刻画两个样本点相似性的方法时，一般有以下三种:
欧氏距离相似度= 1/(1+两个样本的欧式距离)；
余弦相似度=0.5 + 0.5( float(inA.TinB) / la.norm(inA)*la.norm(inB))；
皮尔逊相关系数相似度= 0.5 + 0.5 * corrcoef(inA, inB, rowvar = 0)[0][1]
需要注意的是，在计算相似性时，不论从哪个角度，都不要计算没有打分的哪一项。
对于采用哪一种协同过滤的算法，依据是计算相似度时的计算量，本例中，若使用用户协同过滤算法，那么有四个样本点，若使用项目协同算法，有三个样本点，所以使用项目协同算法，明显计算相似度时计算量会优于用户协同算法。
所以这里使用项目协同算法。(在实际情况中，用户必然多余电影的数量。也会使用项目协同算法)
算法流程
（1）计算各个项目之间的相似度，本例中计算D(电影1，电影2)，D（电影1，电影3），D（电影2，电影3）。
（2）计算没有评级位置（数据集中为0的点）的评级。
具体代码如下：
import numpy as np
def loadExData():
# 利用SVD提高推荐效果
"""
行：用户
列：电影
值：用户对电影的评级，0表示未评分
"""
return np.mat([[1, 0, 7],
[9, 6, 4],
[5, 7, 0],
[0, 7, 1]])
def ecludSim(inA, inB):
return 1.0 / (1.0 + la.norm(inA - inB)) # 范数的计算方法linalg.norm()，这里的1/(1+距离)表示将相似度的范围放在0与1之间
def pearsSim(inA, inB):
if len(inA) < 3: return 1.0
return 0.5 + 0.5 * corrcoef(inA, inB, rowvar=0)[0][
1] # 皮尔逊相关系数的计算方法corrcoef()，参数rowvar=0表示对列求相似度，这里的0.5+0.5*corrcoef()是为了将范围归一化放到0和1之间
def cosSim(inA, inB):
num = np.dot(inA.T , inB)
denom = np.linalg.norm(inA) * np.linalg.norm(inB)
return 0.5 + 0.5 * (num / denom) # 将相似度归一到0与1之间
# 基于物品相似度的推荐引擎
def standEst(dataMat, user, simMeas, item):
"""standEst(计算某用户未评分电影中，以对该电影和其他物品评分的电影的物品相似度，然后进行综合评分)
Args:
dataMat 训练数据集
user 用户编号
simMeas 相似度计算方法
item 未评分的物品编号
Returns:
ratSimTotal/simTotal 评分（0～10之间的值）
"""
# 得到数据集中的物品数目
n = np.shape(dataMat)[1]
# 初始化两个评分值
simTotal = 0.0
ratSimTotal = 0.0
# 遍历行中的每个物品（对用户评过分的物品进行遍历，并将它与其他物品进行比较）
for j in range(n):
userRating = dataMat[user, j]
# 如果某个物品的评分值为0，则跳过这个物品
if userRating == 0:
continue
# 寻找两个用户都评级的物品
# 变量 overLap 给出的是两个物品当中已经被评分的那个元素的索引ID
# logical_and 计算x1和x2元素的真值。
overLap = np.nonzero(np.logical_and(dataMat[:, item].A > 0, dataMat[:, j].A > 0))[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'(iten,j,similarity)
# 相似度会不断累加，每次计算时还考虑相似度和当前用户评分的乘积
# similarity 用户相似度， userRating 用户评分
simTotal += similarity
ratSimTotal += similarity * userRating
if simTotal == 0:
return 0
# 通过除以所有的评分总和，对上述相似度评分的乘积进行归一化，使得最后评分在0~5之间，这些评分用来对预测值进行排序
else:
return ratSimTotal/simTotal
# recommend()函数，就是推荐引擎，它默认调用standEst()函数，产生了最高的N个推荐结果。
# 如果不指定N的大小，则默认值为3。该函数另外的参数还包括相似度计算方法和估计方法
def recommend(dataMat, simMeas=cosSim, estMethod=standEst):
retMat=dataMat.copy()
n=np.shape(dataMat)[0]
for user in range(0,n):
# 寻找未评级的物品
# 对给定的用户建立一个未评分的物品列表
unratedItems = np.nonzero(dataMat[user, :].A == 0)[1]
# 如果不存在未评分物品，那么就退出函数
if len(unratedItems) == 0:
continue
# 在未评分物品上进行循环
for item in unratedItems:
estimatedScore = estMethod(dataMat, user, simMeas, item)
retMat[user,item]=estimatedScore
# 按照估计得分，对该列表进行排序并返回。列表逆排序，第一个值就是最大值
return retMat
test_data=loadExData()
score_data=recommend(test_data)
print(score_data)
[[1 3 7]
[9 6 4]
[5 7 6]
[4 7 1]]
以上就是基于用户的协同过滤算法。这个算法简单实用，效果还可以，但为了更好的提高效果，经常使用下面基于模型的协同过滤算法。
基于模型的协同过滤算法
注：之所以整理这篇文章，就是因为这个地方，网上相关文章介绍的非常乱，很多概念含糊不清。下面就进行详细介绍。
基于模型的协同过滤算法，多种多样，这里主要介绍应用SVD的基于模型的协同过滤。
还是上面的例子。对于用户-电影评分矩阵
因为矩阵中为0的地方是未评分的地方，可以看出A矩阵是稀疏矩阵，所以A矩阵此时并不能进行SVD分解。针对评分矩阵A稀疏的问题，有两种解决方式，
其一、对缺失的地方进行填充，传统SVD。
其二、是Funk-SVD算法。
对缺失的地方进行填充---传统SVD
对于这方法，用什么值去填充又是一个问题，一般都用矩阵中元素的均值进行填充，其理由是对于用户未观看的电影用既不高也不低的均值进行评分。这种方式还是存在两个问题：
一、若矩阵A太稀疏，则这种方式误差很大，A相对稠密时才可以减小误差。
二、现实问题中，用户和电影数量庞大，这一做法的计算量很大。
对于本例A填充完成后为：
此时，使用SVD进行去燥降维，（去燥是提高效果准确性，若去燥维则，使用填充数据产生的噪音会影响准确性，降维是因为实际问题数据维数庞大）。其SVD分解为：
A=np.array([[1, 4, 7],
[9, 6, 4],
[5, 7, 4],
[4, 7, 1]])
U,S,VT =np.linalg.svd(A)
Sigma=np.diag(S)
print(A)
print('U=',U)
print('Sigma=',Sigma)
print('VT=',VT)
[[1 4 7]
[9 6 4]
[5 7 4]
[4 7 1]]
U= [[-0.35949466 0.89113483 0.02362996 0.27583316]
[-0.63196087 -0.33730085 0.66569561 0.2090525 ]
[-0.53609543 0.04067918 -0.23392266 -0.81007844]
[-0.42894141 -0.30075249 -0.70821689 0.47327163]]
Sigma= [[17.62761582 0. 0. ]
[ 0. 5.70380415 0. ]
[ 0. 0. 3.42546037]]
VT= [[-0.59244457 -0.67989919 -0.43214178]
[-0.55124384 -0.04905129 0.83290108]
[ 0.58748588 -0.73166321 0.34573007]]
去燥降维的方法为在矩阵的SVD分解中取前k大的奇异值对应的U，Sigma,VT 矩阵，分别设为.
k的确定方法为，根据给定的去燥比率，若去燥比率设置为不高于5%，则：
S_square=np.square(S)
Sum=0
k=0
for i in range(3):
Sum=Sum+S_square[i]
rate=1-Sum/sum(S_square)
print(rate)
k=i
if(rate<0.05):
break
print(k)
0.12469622694282334
0.033052897858724783
1
所以当只保留前两个最大的奇异值时，去燥比率就位3.3%，小于5%。
由上面得到，在给定去燥条件的前提下，我们确定了k的值，从而确定了评分矩阵A的降维去燥后的低秩最佳逼近矩阵为：
所以：
A_1 =Sigma[0,0]*np.dot(U[:,0].reshape(-1,1),np.mat(VT[0,:]))+Sigma[1,1]*np.dot(U[:,1].reshape(-1,1),np.mat(VT[1,:]))
print(A_1)
print(A)
[[0.95244684 4.05922338 6.9720154 ]
[7.66034775 7.66842183 3.21162691]
[5.47074821 6.41372353 4.27703102]
[5.42522248 5.22500781 1.83873038]]
[[1 4 7]
[9 6 4]
[5 7 4]
[4 7 1]]
可以看出，去燥后的矩阵和原始矩阵非常相似。也正因如此，用均值去填充的评分变化也不是很大，但是已经发生了变化，这种变化，可以理解为，是由真实评分构成的矩阵的特征改变的（这也是为什么使用SVD的原因），所以如果起始的评分矩阵太过稀疏，真实评分产生的影响就会很小，从而结果的准确性很低。
上面我们得到了去燥后的近似矩阵，然后怎么用这个矩阵呢，在用这个近似矩阵之前，就要先讨论下评分矩阵在SVD分解后，得到的U，Sigma，VT分别有什么物理意义。
由SVD的理论知识得到，对于U矩阵的列向量，是矩阵的特征向量，对于矩阵VT的行向量是矩阵
的特征向量。所以要搞清楚U和VT矩阵的物理意义，必须要从
和
两个矩阵触发。为了讨论一般情况，下面先设A为mxn阶评分矩阵。每一行对应一个用户，每一列对应一部电影。
对于任意n维向量x,Ax是一个m维向量，其第一个元素，可以看作是第一个用户对其所有电影评分的一个加权和，第二个元素为第二个用户对其所有电影的评分的一个加权和。当x固定为衡量每个电影本身某一维度的质量（如音乐的质量）的权重时，x对于用户无关，只取决于电影的音乐本身，那么Ax的第一个元素为用户一对音乐本身的偏好度，Ax的第二个元素为用户二对因为本身的偏好度。这个音乐偏好度和电影无关，只取决于用户本身。
设y=Ax,则从上面的分析，x固定为衡量每个电影本身音乐的质量的权重时，y时衡量用户本身的音乐偏好度。此时在分析,
的行代表电影，列代表用户。
是一个n维向量，其第一个元素是电影一的所有用户评分的一个加权和，其第二个元素是电影二的所有用户评分的一个加权和，因为权重y是各个用户对音乐本身的偏好，所以，
表示的向量维电影音乐的质量。所以此时
，
的存在是因为权重没有归一化处理。
所以有
所以，对于的每个特征向量都可以理解为电影本身某一维度上的质量分，衡量电影本身不同维度上的特征，和用户没有关系，这里用音乐维度只是方便理解，实际情况中，这些维度并没有真正的解释意义。
所以，根据上面的分析，U的列向量是衡量电影本身某一维度的质量和特征，和用户无关，且越排在前面的向量越能表示电影本身的特征，同理VT的行向量是衡量用户本身某一维度的质量和特征，和电影无关，且越排在前面的向量越能表示用户本身的特征。所以去前k个时，舍掉的都是一些噪音特征。
以上就是这个近似矩阵SVD分解的物理意义，有了这个意义，下面分析怎么使用这个近似矩阵的SVD分解。
对于一个新的用户，其用户评分向量维p=[1,4,0],其中0为未评分，则根绝SVD分解的意义，计算向量(实际上计算的是
中(去噪低维空间里)与p对应的向量。),其就是新用户p在去噪低维空间中对应的向量。
然后再用相似度，在中寻找与p最像的向量
,找到
后，在反推出
对应的用户，这样就找到了，去过噪音之后的相似用户，从而用相似用户的评分去填充新用户未评分的电影评分。
上面过程的代码实现如下：
p=[1,4,0]
U_k=U[:,0:2]
Sigma_k=Sigma[0:2,0:2]
VT_k=VT[0:2,:]
p_new=np.dot(np.dot(p,VT_k.T),np.mat(Sigma_k).I)
p_new=np.array(p_new)[0]
#这里用余弦相似度
print(cosSim(p_new,U_k[0,:]))
print(cosSim(p_new,U_k[1,:]))
print(cosSim(p_new,U_k[2,:]))
print(cosSim(p_new,U_k[3,:]))
0.38816907259497146
0.9964791723066383
0.88728868904969
0.9999984582439839
所以在低维空间中，U的第一个行向量和p最接近，所以用户1和新用户最像，所以用用户1的评分去填充新用户未评分的评分，得到p=[1,4,7]
同理如果给的不是新用户评分的向量，而是新电影的评分向量，也可以用相同的方法填充未评分的位置。
从上面的分析不难看出，这种传统的基于SVD的算法，要求待分解的评分矩阵是稠密的，若果是稀疏的，结果准确率会下降，但实际情况评分矩阵就是稀疏的，所以，需要下面的方法继续优化。
Funk-SVD
因为基于传统的SVD的协同过滤存在很大的问题，所以引入Funk-SVD算法，下面对其详细介绍。
由上面传统的SVD分析，得到评分矩阵的近似分解为：
因为是k阶对角矩阵，所以有
,此时
也是对角矩阵。所以A的近似分解可化简为：
其中，P是mxk阶矩阵，仅与电影本身相关，Q是kxn阶矩阵，仅与用户本身相关。
设,则：
所以PQ矩阵第i低行，第j列的元素
所以，问题就转化为一个优化问题，A的每个元素和矩阵PQ的每个元素之差最小化，既
考虑过拟合问题，我们引入正则项。最后优化问题化简如下：
求解这个优化问题使用梯度下降的方法。
梯度下降
梯度下降算法的介绍在这里不展开了，这里直接求梯度：
所以梯度下降的迭代公式是：
其中为学习效率，
代码实现为：
"""
@输入参数：
R：M*N 的评分矩阵
K：隐特征向量维度
max_iter: 最大迭代次数
alpha：步长
lamda：正则化系数
@输出：
分解之后的 P，Q
P：初始化用户特征矩阵 M*K
Q：初始化物品特征矩阵 N*K，Q 的转置是 K*N
"""
# 给定超参数
K = 5
max_iter = 5000000
alpha = 0.0002
lamda = 1
# 核心算法
def LMF_grad_desc(R, K=2, max_iter=1000, alpha=0.0001, lamda=0.002):
# 定义基本维度参数
M = len(R)
N = len(R[0])
# P、Q 的初始值随机生成
P = np.random.rand(M, K)
Q = np.random.rand(N, K)
Q = Q.T
# 开始迭代
for steps in range(max_iter):
# 对所有的用户 u，物品 i 做遍历，然后对对应的特征向量 Pu、Qi 做梯度下降
for u in range(M):
for i in range(N):
# 对于每一个大于 0 的评分，求出预测评分误差 e_ui
if R[u][i] > 0:
e_ui = np.dot(P[u,:], Q[:,i]) - R[u][i]
# 代入公式，按照梯度下降算法更新当前的 Pu、Qi
for k in range(K):
P[u][k] = P[u][k] - alpha * (2 * e_ui * Q[k][i] + 2 * lamda * P[u][k])
Q[k][i] = Q[k][i] - alpha * (2 * e_ui * P[u][k] + 2 * lamda * Q[k][i])
# u,i 遍历完成，所有的特征向量更新完成，可以得到 P、Q，可以计算预测评分矩阵
predR = np.dot(P, Q)
# 计算当前损失函数（所有的预测误差平方后求和）
cost = 0
for u in range(M):
for i in range(N):
# 对于每一个大于 0 的评分，求出预测评分误差后，将所有的预测误差平方后求和
if R[u][i] > 0:
cost += (np.dot(P[u,:], Q[:,i]) - R[u][i]) ** 2
# 加上正则化项
for k in range(K):
cost += lamda * (P[u][k] ** 2 + Q[k][i] ** 2)
if cost < 0.0001:
# 当前损失函数小于给定的值，退出迭代
break
return P, Q.T, cost
P, Q , cost=LMF_grad_desc(A,K,max_iter,alpha,lamda)
print(A)
print(np.dot(P,Q.T))
print(cost)
[[1 4 7]
[9 6 4]
[5 7 4]
[4 7 1]]
[[1.00366321 3.9974722 6.98747162]
[8.98683502 6.00055608 3.99691414]
[4.99780352 6.99263191 3.99742585]
[3.99994045 6.98860325 1.00426985]]
0.7409324229378083
以上就是梯度下降法的推导和实现。
