Python AI 教学|SVD（Singular Value Decomposition）算法及应用

1 SVD简介

1.1 特征值分解

如果一个向量v是方阵A的特征向量，则将其可以表示为Av=λv。λ被称为特征向量v对应的特征值。

特征值分解是将一个矩阵分解成下面的形式：

Q是这个矩阵A的特征向量组成的矩阵，Σ是一个对角矩阵，每一个对角线上的元素就是一个特征值。一个矩阵的一组特征向量是一组正交向量。

1.2奇异值分解

提取数据背后因素的方法称为奇异值分解（SVD），SVD使能够用小得多的数据集来表示原始数据集，这样做去除了噪声和冗余信息，我们可以把SVD看成是从噪声数据中抽取相关特征。

（1）奇异值分解定义

奇异值分解指将一个矩阵A(m*n)分解为如下形式：

（其中，U是左奇异矩阵，由左奇异向量组成；V是右奇异矩阵，由右奇异向量组成。）

下图是一个对角矩阵，其除了对角线上的元素外，其余均为0。形如：

该矩阵的对角元素便是奇异值（singular value），一般情况下奇异值是按从大到小排列的。为了节省存储空间，在奇异值分解算法中，只存储σ 值，而不是一个对角矩阵。

（2）奇异值特性

奇异值σ 的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了,则也可以用前r大的奇异值来近似描述矩阵：

（3）奇异值分解与特征值分解的关系

将矩阵A(m*n)和其转置相乘，将得到一个方阵，对这个方阵求特征值可以得到：

v就是矩阵A(m*n)的进行SVD的右奇异向量，同时还有：

σ就是矩阵A(m*n)的奇异值，u则是左奇异向量。

2 SVD算法实现

2.1分解过程

【1】算法实现：

【2】运行结果（python3）：

2.2重构过程

由上图可知Sigma的值中，前两个比后面两个大了很多，我们可以将最后两个值去掉，则原始数据集就可以用如下结果来近似：

【1】重构过程示意图：

（其中浅灰色区域是原始数据，深黑色区域是矩阵近似计算仅需要的数据）

【2】重构算法：

【3】运行结果：

（补充：确定要保留的奇异值的数目有很多启发式的策略，其中一个做法就是保留矩阵中90%的能量信息，先将所有的奇异值求其平方和计算出总能量信息，再按照从大到小的顺序将奇异值的平方和累加到大于等于总值的90%为止。举个例子，比如某矩阵分解后得到10个奇异值，这些奇异值的总平方和为500，500*90%=450，则需要累加的奇异值能量和至少为450。按顺序累加，前3个奇异值平方和为100，前5个奇异值的平方为400，前6个平方和为460，则经过计算，重构矩阵的时候，取前6个奇异值。）

函数说明（一）

【1】mat函数

将输入解释为矩阵

语法：numpy.mat(data, dtype=None)

等价于matrix(data, copy=False)

算法示例：

3 SVD应用

SVD在数据压缩（如PCA）、推荐算法、矩阵补全、潜在语义索引（LSI）等领域都有着广泛的应用，这里将详细介绍基于SVD的推荐引擎实现。推荐系统存在于我们生活的各个角落，比如淘宝会给我们推荐我们可能感兴趣的物品，网易云音乐有每日推荐的20首歌，大众点评也会给我们推荐餐厅等。相关的推荐算法有基于内容推荐、协同过滤、关联规则、混合推荐等等。

3.1 基于协同过滤的推荐引擎

协同过滤（collaborative filtering）指通过将用户和其他用户的数据进行对比实现推荐。比如要判断是否给某个用户推荐一部他还没有看过的电影，则可以先将这部电影与用户看过的电影进行比较，如果相似度很高则认为用户会喜欢这部电影，则进行推荐；反之则不推荐。

（1）相似度

假设有一个用户和电影的数据集，我们可以将用户和电影的对应关系看成一个矩阵，如下图所示，行代表用户，列表示电影，矩阵的元素中0表示用户没有看过，1-5表示用户对这部电影的喜爱程度，值越大代表用户越喜欢这部电影。

【1】欧氏距离

电影“一”和“三”的欧氏距离为：

电影“二”和“三”的欧氏距离为：

相似度= ，当距离为0时候，相似度为1，随着距离的增大，相似度减小。

算法实现：

【2】皮尔逊相关系数（Pearson correlation）

它度量的是两个向量之间的相似度。该方法相对于欧氏距离的一个优势在于，它对用户评级的量级并不敏感。皮尔逊相关系数的取值范围从-1到+ 1，通过0.5 + 0.5*corrcoef()这个函数把其取值范围归一化到0-1之间。

算法实现：

【3】余弦相似度（cosine similarity )

计算的是两个向量夹角的余弦值，两个向量之间的夹角为：

余弦相似度的取值范围也在-1到+1之间，因此借助0.5 + 0.5*()也将它归一化到0到1之间。

算法实现：

函数说明（二）

【1】 norm函数

用来计算向量或矩阵范数的函数，同svd一样属于numpy库中的linalg。

语法：numpy.linalg.norm(x,p)

【注释：①x表示向量或者矩阵；②p表示范数的种类：p=1计算1-范数；p=2计算2-范数，同norm(x)；p=inf计算无穷范数；p='fro'，计算Frobenius范数】

算法示例：

【2】 corrcoef函数

用来计算皮尔逊相关系数

语法：numpy.corrcoef(x, y=None, rowvar=True)

【注释：x为矩阵或者向量，y和x的shape一样】

算法示例：

（2）基于电影内容的相似度计算

【1】数据生成

【2】调取数据

【3】运行结果

（补充：除了上述基于物品（item-based)的相似度外，还可以基于用户（user-based）的相似度计算，使用哪一种相似度取决于用户或物品的数目。因为观看电影人数远远高于电影的数目，所以基于电影的推荐会比基于人的推荐花费更短的时间，但是这种基于item推荐的缺点在于对用户历史喜好数据的量及准确性依赖较强，对小众喜好的用户，推荐效果不佳；）

（3）基于电影内容的推荐引擎

目的是构建一个推荐引擎，寻找到用户没有观看过的电影，算法需要实现的事情包括：①寻找用户没有观看过的电影——矩阵中的0值②在上述没看过的电影中对每部电影预计一个用户可能给予的等级——基于相似度计算③对这些电影的评分从高到低进行排序，返回前N个item。

【1】估计评分

【2】推荐电影

【3】调取数据

【4】运行结果

结果表明用户3（从0开始数，数字2对应于第3个用户）对电影3的评分为2.3（因为用户3只有一部电影没有评级，因此算法只返回一个结果）。

使用另两种相似度计算实现对未观看电影的评级：

函数说明（三）

【1】range函数

是一个python自带的来创建包含算术级数的列表。它最常用于for循环。

语法：range(start, stop[, step])

【注释：①start，是列表起始值，省略时默认为0；②stop，是列表最大能够达到的值，列表最后一个元素小于等于stop值；③step是步长】

算法示例：

【2】append函数

用于在列表末尾添加新的对象

语法：list.append(obj)

【注释：obj表示添加到列表末尾的对象】

算法示例：

【3】logcal_and函数

逻辑与

语法：numpy.logical_and(x1, x2)

逻辑函数包括：

算法示例：

3.2 基于SVD的推荐引擎

现实生活中的数据集会比前文协同过滤用到的矩阵稀疏得多，因为观众不可能看过近乎全部的电影，所以需要通过SVD来减少特征空间并提高推荐的效果。详情可以查阅Netflix推荐算法大赛，里面用到了很多的比较复杂推荐算法，而且推荐准确率也很高。

【1】数据生成

同样保存在“svdRec.py”中

【2】SVD过程

运行结果：

截止第5个奇异值累加能量和高于总能量的90%，于是我们可以将一个11维的矩阵转换成一个5维的矩阵。

【3】推荐实现

这里还是用到了协同过滤里面的推荐算法，只是将相似度的计算模块替换成了基于SVD的相似度计算模块。

运行结果：

基于默认的余弦相似度进行推荐top-3：

基于皮尔逊相关系数进行推荐top-3：

函数说明（四）

【1】eye函数

生成对角矩阵

语法：numpy.eye(M, k)

【注释：①M方阵的规模，即行数、列数；②k默认为0，输出对角线全“1”，其余全“0”的方阵；k为正整数，右上方第k条对角线全“1”其余全“0”； k为负整数，左下方第k条对角线全“1”其余全“0”】

算法示例：

责编 | 罗 栾 申

指导 | 老薛

指导教授简介：

薛巍立，男，博士，东南大学经济管理学院教授，博士生导师，国家自然科学基金优秀青年基金项目获得者。博士毕业于中国香港中文大学系统工程与工程管理系，主要从事供应链物流管理、运营风险管理和医疗服务运作管理等。主要成果发表在Operations Research、Production and Operations Management、Transportation Science、European Journal of Operational Research、Operations Research Letters等期刊上。