SVD应用--电影推荐系统+图像压缩

推荐系统

协同过滤推荐

相似度计算

图像压缩

一.推荐系统

推荐系统如电影推荐系统的作用其实就是先对用户未评分的电影做预测评分，使数据完整，然后降序排序评分，为用户推荐评分前几名的物品。

如下图所示用户电影评价数据，其中用户2、用户3、用户5是某网站新注册用户，对新用户预测电影评价并做出推荐。

例如数据[3,1,3,'空白',3,6,100]，类似于机器学习中处理缺失数据，方法之一是用平均值、中值、分位数、众数、随机值等替代。.
推荐系统推荐的过程其实也可以理解为在填补缺失值，而为每一个用户做出精准的个性化推荐，就不能简单的将缺失值替换为平均值(非个性化推荐)，而是要计算加权平均值(个性化推荐)。
假如我们选择替换缺失值为算数平均值，即'空白'=(3+1+3+3+6+100)/6=19.3 但这样的替换前提是认为数据的所有可能值发生的概率都是一样的，一视同仁的结果并不准确，从数据分布来看，取'3'比取'100'的机会大得多，所以我们计算平均值时也要考虑数据发生的概率，即应该计算其期望或者称为加权平均更准确而不是算数平均。加权平均值是一个更准确的分数度量，能体现相对重要性。加权平均值往往用于投资组合，等级评分和其他统计数据。这样填充缺失值的过程其实也可以看作聚类或者回归的过程。

加权平均值中的权：1、数据出现的个数，2、数据所占的百分比。在推荐系统中，‘权’：w可以视为相似度(电影之间相似度或者用户之间相似度)，x则为用户对电影的评分。

如预测用户2对第一部电影的评分，分别计算film1与film2、3、4的相似度：p12,p13,p14，视为权重。设用户2对film2、3、4的评分分别为，f2,f3,f4，
则用户2对第一部电影的评分为f1=(p12*f2+p13*f3+p14*f4)/sum(p12,p13,p14)

上面的预测步骤中计算的相似度是第一电影与其他所有电影作比较，每一次比较需要比较全部属性，然而实际项目中，并不需要这么多，只需要寻找电影中的一些典型的有代表的属性作比较也能得到准确的结果，这样也能减少计算量。

那么如何寻找呢？
这里就可以使用SVD对用户电影评价数据做奇异值分解，寻找电影中有代表字段属性，其实也可以寻找用户中有代表字段属性，总之，SVD可以寻找到各个维度方向上的的代表量。设矩阵A为用户的电影评价数据矩阵，其中行为用户，列为电影。对矩阵A做奇异值分解，如下所示

其中U可视为用户的特征向量矩阵，V可视为电影的特征向量矩阵。注意：列向量为特征向量。对角矩阵S中的对角线值即奇异值(降序排序)的大小可以视为对特征用户和特征电影的权重影响。注意对角矩阵S对角线的奇异值需降序排序，特征向量根据对应的奇异值排序。

在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说，我们也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵，依然能很好得表达原始样本信息。

在本例中，如下图所示，假设我们发现前3个奇异值之和就占了全部的奇异值之和的90%以上的比例，据此，我们可以选取前3维V特征矩阵或者U特征矩阵从而实现降维处理(注意：列向量为特征向量)，如图中黄色虚线所示

更多关于奇异值分解的讲解，见文章

协同过滤推荐算法评分机制

回到推荐系统，在训练协同过滤算法前，为了能够计算相似度，首先需要将数据集中的缺失评分项填充为0，如下图所示。

评分机制：

评分>0：用户对该电影的喜欢程度
评分<0：用户对该电影的厌恶程度
评分=0：用户未看过该电影

奇异值分解

然后我们对数据集做奇异值分解，如下图所示

然后比较电影之间的相似度，我们选取电影的特征矩阵 $V^{T}$ 前k行属性(注意：列向量为特征向量)

这样计算相似度时，电影1只需要比较电影2、电影3和电影4各自的部分属性就可以了，

相似度计算

如何衡量物品之间相似程度？本文选用皮尔逊相关系数来计算相似度，公式如下，

式中，Cov(x,y)表示变量x与y的协方差， $\sigma_{x},\sigma_{y}$ 分别表示变量x与y的的标准差。更多关于相似度的内容见文章。

预测评分过程如下：

此外，我们不仅可以通过比较相似电影特点来为用户做出推荐，也可以比较相似用户的喜好来为用户做出推荐，过程与上面相似。

协同过滤推荐算法缺陷

协同过滤推荐算法关键是评分矩阵，当用户对物品评分较少或者说几乎不评分导致评分矩阵过于稀疏时，如下图所示，推荐结果的准确性将大打折扣。此外，在某些行业中金融产品、房产、手机、汽车等等，很难获取到大量用户的评分数据(用户不大可能会对已经购买到的(过时的产品)再进行一个评价或反馈了)，此时协同过滤推荐算法将不再使用了(巧妇难为无米之炊)。
评分矩阵相当"稠密"时，实际需要计算数据可能是数以亿计的，这就导致算法的时间复杂度不太乐观。对于一些需要实时推荐的平台而言，推荐效果会很糟糕。

代码

代码见Github

图像压缩

什么压缩？如何使用SVD奇异值分解对图像压缩？

如下图，我们将我们也可以用最大的前k个的奇异值和对应的左右奇异向量来近似描述矩阵，图片依然能很好得表达原始样本信息，同时占用内存也减小，这个过程即可视为图像压缩。此时SVD的降维体现在“近似”上，保留前k个奇异值及其对应的奇异矢量，算出的就是在秩为k的所有矩阵中达到逼近原有矩阵，如下所示

前面的SVD用于推荐系统不太直观，而图像压缩这可以很直观得看出SVD对图像奇异值分解的作用。如下图动图所示，展示了选取的奇异值占了全部的奇异值之和的0~100%时相应的图像变化

注意图像转换为矩阵是三维矩阵，即每个像素点都有3个值表示，所以就是3通道图。因此对图像矩阵数据做奇异值分解需要对3个通道分别做奇异值分解。伪代码如下

注意:图片有3通道，即m*n*3矩阵，需分别对每个通道做奇异值分解。
import numpy as np
from PIL import Image
#读取照片
img = Image.open(path)
#照片转为矩阵
img = np.array(img)
imgData = np.zroes_like(img)#照片有3个通道，imgData用来存储3个通道的奇异值分解
#奇异值分解
for i in range(3):#选取90%的奇异值占比索引，kU, S, V = np.linalg.svd(imgData[:,:,i])  # V已转置cumsum = np.cumsum(S)sum_list = cumsum / sum(S)k = np.where(sum_list>=0.9)[0][0]img[:,:,i] = U[:,:k]@np.diag(S[:k])@V[:k,:]
return img