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等期刊上。
