本以为以后再也用不到到矩阵论的知识了，没想到还是没逃过去，大四学的矩阵论现在基本上忘光了，于是又要重新拿起课本和笔记了，我感觉这次写完过段时间又会忘掉，这记性….,在学习Svd的过程中，真的是每个概念都要重新去看，比较麻烦，不说了，摸鱼去了……
奇异值分解（Singular Value Decompositionm,简称SVD）是在机器学习领域应用较为广泛的算法之一，也是学习机器学习算法绕不开的基石之一。SVD算法主要用在降维算法中的特征分解、推荐系统、自然语言处理计算机视觉等领域。奇异值分解（SVD）通俗一点讲就是将一个线性变换分解为两个线性变换，一个线性变换代表旋转，一个线性变换代表拉伸。
| $$A = U\Sigma V^T \tag{1-1}$$ |
注：SVD是将一个矩阵分解成两个正交矩阵和一个对角矩阵，我们知道正交矩阵对应的变换是旋转变换，对角矩阵对应的变换是伸缩变换。
1、SVD算法实现
1.1 SVD原理简单回顾
有一个\(m \times n\)的实数矩阵A，我们可以将它分解成如下的形式 \( A = U\Sigma V^T \tag{1-1} \)
其中U和V均为单位正交阵，即有UU^T=I和VV^T=I，U称为左奇异矩阵，V称为右奇异矩阵，\( \Sigma\)仅在主对角线上有值，我们称它为奇异值，其它元素均为0。上面矩阵的维度分别为 $$U \in \mathbf{R}^{m\times m},\ \Sigma \in \mathbf{R}^{m\times n},\ V \in \mathbf{R}^{n\times n}$$。
正常求上面的 \( U,V,\Sigma \) 不便于求，我们可以利用如下性质
\(AA^T=U\Sigma V^TV\Sigma^TU^T=U\Sigma \Sigma^TU^T \tag{1-2}A^TA=V\Sigma^TU^TU\Sigma V^T=V\Sigma^T\Sigma V^T \tag{1-3}\)1.2 SVD算法#
据1.1小节，对式（1-3）和式（1-4）做特征值分解，即可得到奇异值分解的结果。但是样分开求存在一定的问题，由于做特征值分解的时候，特征向量的正负号并不影响结果，比如，我们利用式（1-3）和（1-4）做特征值分解 \( AA^T\mathbf{u}_i = \sigma_i \mathbf{u}_i\quad \text{or} \quad AA^T(-\mathbf{u}_i) = \sigma_i (-\mathbf{u}_i)\\ A^TA\mathbf{v}_i = \sigma_i \mathbf{v}_i\quad \text{or} \quad A^TA(-\mathbf{v}_i) = \sigma_i (-\mathbf{v}_i)\)
如果在计算过程取，取上面的\(\mathbf{u}_i\)组成左奇异矩阵U，取 \( -\mathbf{v}_i \) 组成右奇异矩阵V，此时\(A\ne U\Sigma V^T \) 。因此求\(\mathbf{v}_i\)时，要根据\(\mathbf{u}_i\)来求，这样才能保证\(A= U\Sigma V^T\)。因此，我们可以得出如下1.1计算SVD的算法。它主要是先做特性值分解，再根据特征值分解得到的左奇异矩阵U间接地求出部分的右奇异矩阵\(V’\in \mathbf{R}^{m\times n}\)。
算法1.1：SVD输入：样本数据
输出：左奇异矩阵，奇异值矩阵，右奇异矩阵
- 计算特征值： 特征值分解AA^T，其中\(A \in \mathbf{R}^{m\times n}\) 为原始样本数据\(AA^T=U\Sigma \Sigma^TU^T\)得到左奇异矩阵\(U \in \mathbf{R}^{m \times m}\) 和奇异值矩阵\(\Sigma’ \in \mathbf{R}^{m \times m}\)
- 间接求部分右奇异矩阵： 求\(V’ \in \mathbf{R}^{m \times n}\)利用\(A=U\Sigma’V’\)可得\(V’ = (U\Sigma’)^{-1}A = (\Sigma’)^{-1}U^TA \tag{1-4}\)
- 返回\(U,\ \Sigma’,\ V’\)，分别为左奇异矩阵，奇异值矩阵，右奇异矩阵。
注：这里得到的\(\Sigma’\)和V’与式（1-2）所得到的\(\Sigma,\ V\)有区别，它们的维度不一样。\(\Sigma’\)是只取了前m个奇异值形成的对角方阵，即\(\Sigma’ \in \mathbf{R}^{m \times m}；V’\)不是一个方阵，它只取了\(V \in \mathbf{R}^{m \times n}\)的前m行（假设m < n），即有\(V’ = V(:m,\cdot)\)。这样一来，我们同样有类似式（1-1）的数学关系成立，即\(A = U\Sigma’ (V’)^T\tag{1-5}\)
我们可以利用此关系重建原始数据。
2、SVD的Python实现#
以下代码的运行环境为python3.6+jupyter5.4。
2.1 SVD实现过程#
读取数据#
这里面的数据集大家随便找一个数据就好，如果有需要我的数据集，可以下在面留言。
import numpy as np
import pandas as pd
from scipy.io import loadmat
# 读取数据，使用自己数据集的路径。
train_data_mat = loadmat("../data/train_data2.mat")
train_data = train_data_mat["Data"]
print(train_data.shape)
特征值分解#
# 数据必需先转为浮点型，否则在计算的过程中会溢出，导致结果不准确
train_dataFloat = train_data / 255.0
# 计算特征值和特征向量
eval_sigma1,evec_u = np.linalg.eigh(train_dataFloat.dot(train_dataFloat.T))
计算右奇异矩阵#
#降序排列后，逆序输出
eval1_sort_idx = np.argsort(eval_sigma1)[::-1]
# 将特征值对应的特征向量也对应排好序
eval_sigma1 = np.sort(eval_sigma1)[::-1]
evec_u = evec_u[:,eval1_sort_idx]
# 计算奇异值矩阵的逆
eval_sigma1 = np.sqrt(eval_sigma1)
eval_sigma1_inv = np.linalg.inv(np.diag(eval_sigma1))
# 计算右奇异矩阵
evec_part_v = eval_sigma1_inv.dot((evec_u.T).dot(train_dataFloat))
上面的计算出的evec_u, eval_sigma1, evec_part_v分别为左奇异矩阵，所有奇异值，右奇异矩阵。
2.2 SVD降维后重建数据#
取不同个数的奇异值，重建图片，计算出均方误差，如图2-1所示。从图中可以看出，随着奇异值的增加，均方误差（MSE）在减小，且奇异值和的比率正快速上升，在100维时，奇异值占总和的53%
注： 均方误差MSE有如下计算公式\(\text{MSE} = \frac{1}{n}\left((y_1-y_1′)^2+(y_2-y_2′)^2+\cdots+(y_n-y_n’)^2\right)\).我们平时听到的\(\text{RMSE}=\sqrt{\text{MSE}}\)。
SVD与特征值分解（EVD）非常类似，应该说EVD只是SVD的一种特殊怀况。我们可以通过它们在实际的应用中返过来理解特征值/奇异值的含义：特征值/奇异值代表着数据的信息量，它的值越大，信息越多。
奇异值分解定义#
有一个\(m \times n\)的实数矩阵A，我们想要把它分解成如下的形式\(A = U\Sigma V^T \tag{2-1}\)
其中U和V均为单位正交阵，即有UU^T=I和VV^T=I，U称为左奇异矩阵，V称为右奇异矩阵，\(\Sigma\)仅在主对角线上有值，我们称它为奇异值，其它元素均为0。上面矩阵的维度分别为\(U \in R^{m\times m},\ \Sigma \in R^{m\times n},\ V \in R^{n\times n}\)。
一般地\(\Sigma\)有如下形式
| \(\Sigma = \left[ \begin{matrix} \sigma_1 & 0 & 0 & 0 & 0\\ 0 & \sigma_2 & 0 & 0 & 0\\ 0 & 0 & \ddots & 0 & 0\\ 0 & 0 & 0 & \ddots & 0\\ \end{matrix} \right]_{m\times n}\) |
Σ，只有其主对角线有奇异值，其余均为0。
在图像压缩中的应用
准备工具
下面的代码运行环境为python3.6+jupyter5.4
SVD（Python）
这里暂时用numpy自带的svd函数做图像压缩
①读取图片
%matplotlib inline
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
import numpy as np
img_eg = mpimg.imread("../img/beauty.jpg")
print(img_eg.shape)
图片的大小是\(600\times 400 \times 3\)
②奇异值分解
img_temp = img_eg.reshape(600, 400 * 3)
U,Sigma,VT = np.linalg.svd(img_temp)
我们先将图片变成\(600\times 1200\)，再做奇异值分解。从svd函数中得到的奇异值sigma它是从大到小排列的。
③取前部分奇异值重构图片
# 取前60个奇异值
sval_nums = 60
img_restruct1 = (U[:,0:sval_nums]).dot(np.diag(Sigma[0:sval_nums])).dot(VT[0:sval_nums,:])
img_restruct1 = img_restruct1.reshape(600,400,3)
# 取前120个奇异值
sval_nums = 120
img_restruct2 = (U[:,0:sval_nums]).dot(np.diag(Sigma[0:sval_nums])).dot(VT[0:sval_nums,:])
img_restruct2 = img_restruct2.reshape(600,400,3)
将图片显示出来看一下，对比下效果
fig, ax = plt.subplots(1,3,figsize = (24,32))
ax[0].imshow(img_eg)
ax[0].set(title = "src")
ax[1].imshow(img_restruct1.astype(np.uint8))
ax[1].set(title = "nums of sigma = 60")
ax[2].imshow(img_restruct2.astype(np.uint8))
ax[2].set(title = "nums of sigma = 120")
降维——奇异值分解
奇异值分解，全称Singular Value Decomposition，简称SVD。它是一种矩阵因式分解。通过计算奇异值个数和奇异向量，生成一个可以代替原矩阵的近似矩阵，将数据集的奇异值表征按重要性排列，舍弃不重要的特征向量。可用来达到降维的目的，从而找出数据中的主成分。
奇异值分解的计算该方法类似主成分分析(PCA)，差别在于PCA利用协方差矩阵进行分解，而SVD直接在原始矩阵上进行分解。所以SVD不要求被分解的矩阵是方阵，可以操作PCA无法操作的数据集，这也是SVD有价值的特点之一。
SVD推荐系统
首先，我们知道，任何推荐系统的整体大框架都是两部分：对某个用户user而言：首先是从数百万种Item中粗略的选出千级别的Item（实现这种功能的方法叫做召回算法），然后从几百上千的Item中精细的预测算出用户对每个Item的具体评价分数，然后选出前十个评价分数最高的Item推荐给用户（实现该方法的过程称为排序算法）
基于召回的算法，我们常常使用的有两种：基于用户行为的以及基于内容的。基于用户行为的推荐算法我们也称为协同过滤算法，基于内容的推荐算法后期详细讨论。而协同过滤算法又分为两大类，一类是基于邻域的协同过滤算法，一类是基于LFM（隐因子模型），而我们今天重点讨论的SVD算法就是召回算法里的LFM算法。
我们在召回阶段的目的是由一个稀疏的评分矩阵推算出其中的空缺分数。（补充：评分矩阵是指每个用户对各个电影的评价分数，m行代表m个用户，n行代表n个电影）
我们的目的是得到用户对未评价电影的分数，而这种user-Item的评分矩阵中，用户对Item的分数是没有直接关系的，我们需要寻找一种隐空间，使得将用户和Item联系起来。比如我们无法得知user1对《利刃出鞘》这部电影的分数，但是我们可以通过用户的历史信息（即用户对别的电影的分数）得到用户对“悬疑”类电影的爱好程度，我们也可以得到某个电影的“悬疑类”的程度有多大，这样，我们就可以将这俩个关系联系到一起了，比如我们想用户A对《南方车站的故事》进行预测，我们无法直接得到他的分数，但是我们知道他对“悬疑”类的电影有多喜爱，而《南方车站的故事》的“悬疑”程度有多大，两个值相乘即可得到A对《南方车站的故事》的预测分数，这里我们只是使用到了一个维度：“悬疑”类，我们可以将矩阵A分解成m* k列的一共k个维度的矩阵，将电影分解成k * n列一共k个维度的矩阵，然后这两个矩阵相乘即可得到矩阵中空的A[i][j]的值。
说白了，我们这里使用到得SVD的思想只是说任何一个矩阵均可以分解成两个矩阵相乘的形式（SVD是三个，但也可以合并俩个得到两个矩阵），这俩个子矩阵分别代表了用户的偏好程度和电影的成分程度，将这两个矩阵相乘即可得到用户对电影的评分矩阵。
至此，我们使用SVD的思想将矩阵A分解成两个矩阵相乘的形式（B*C），但事情没有那么简单，我们的推荐系统的矩阵A是一个稀疏矩阵，基本上是不能分解的，无法直接SVD，但分解的思想我们依旧要使用，所以我们使用机器学习的方法，使用最小均方误差学习到每个矩阵的各个元素，具体来讲就是，矩阵B的i行乘矩阵C的j列得到A的ij元素，有真实值的A[i][j]元素作为标签，不断地使用RMSE减小A中所有的标签，然后得到矩阵B和C，然后使用B和C取预测A中的空白缺失值。
参考：
https://www.cnblogs.com/endlesscoding/p/10033527.html