摘要：奇异值分解（singular value decomposition）是线性代数中一种重要的矩阵分解，在生物信息学、信号处理、金融学、统计学等领域有重要应用，SVD都是提取信息的强度工具。在机器学习领域，很多应用与奇异值都有关系，比如推荐系统、数据压缩（以图像压缩为代表）、搜索引擎语义层次检索的LSI等等。（本文原创，转载必须注明出处.）

奇异值分解原理

什么是奇异值分解(SVD）

奇异值分解

假设M是一个m×n阶矩阵，其中的元素全部属于域K，也就是实数域或复数域。如此则存在一个分解使得

$M_{m×n}=U_{m×m} \Sigma_{m×n} V^T_{n×n}$

其中U是m×m阶酉矩阵；Σ是m×n阶非负实数对角矩阵；而$V^T$，即V的共轭转置，是n×n阶酉矩阵。这样的分解就称作M的奇异值分解。Σ对角线上的元素$Σ_i$,i即为M的奇异值。常见的做法是将奇异值由大而小排列。如此Σ便能由M唯一确定了。（虽然U和V仍然不能确定。）

V的列组成一套对$M$的正交”输入”或”分析”的基向量。这些向量是$M^*M$的特征向量。
U的列组成一套对$M$的正交”输出”的基向量。这些向量是$MM^*$的特征向量。
Σ对角线上的元素是奇异值，可视为是在输入与输出间进行的标量的”膨胀控制”。这些是$ MM^* $及 $ M^* M $的特征值的非负平方根，并与U和V的行向量相对应。

矩阵知识

正交与正定矩阵

正交矩阵：若一个方阵其行与列皆为正交的单位向量，则该矩阵为正交矩阵，且该矩阵的转置和其逆相等。两个向量正交的意思是两个向量的内积为 0。 >> 正交矩阵知识扩展
正定矩阵：如果对于所有的非零实系数向量 $z$，都有 $z^T A z > 0$，则称矩阵 $A$ 是正定的。正定矩阵的行列式必然大于 0，所有特征值也必然 > 0。相对应的，半正定矩阵的行列式必然 ≥ 0。>> 正定矩阵知识扩展

转置与共轭转置

矩阵的转置（transpose）是最简单的一种矩阵变换。简单来说，若 $m\times n$ 的矩阵 $\mathbf M$ 的转置记为 $\mathbf M^{\mathsf T}$；则 $\mathbf M^{\mathsf T}$ 是一个 $n\times m$ 的矩阵，并且 $\mathbf M_{i,j} = \mathbf M^{\mathsf T}_{j,i}$ 。因此，矩阵的转置相当于将矩阵按照主对角线翻转；同时，我们不难得出 $\mathbf M = \bigl(\mathbf M^{\mathsf T}\bigr)^{\mathsf T}$ 。

矩阵的共轭转置（conjugate transpose）可能是倒数第二简单的矩阵变换。共轭转置只需要在转置的基础上，再叠加复数的共轭即可。因此，若以 $\mathbf M^{\mathsf H}$ 记矩阵 $\mathbf M$ 的共轭转置，则有 $\mathbf M_{i,j} = \overline{\bigl(\mathbf M^{\mathsf H}\bigr)_{j,i}}$ 。

酉矩阵

酉矩阵（unitary matrix）是一种特殊的方阵，它满足 $\mathbf U\mathbf U^{\mathsf H} = \mathbf U^{\mathsf H}\mathbf U = I_n.$ 酉矩阵实际上是推广的正交矩阵（orthogonal matrix）；当酉矩阵中的元素均为实数时，酉矩阵实际就是正交矩阵。另一方面，由于 $\mathbf M\mathbf M^{-1} = \mathbf M^{-1}\mathbf M = I_n$ ，所以酉矩阵 $\mathbf U$ 满足 $\mathbf U^{-1} = \mathbf U^{\mathsf H}$；事实上，这是一个矩阵是酉矩阵的充分必要条件。

正规矩阵

同酉矩阵一样，正规矩阵（normal matrix）也是一种特殊的方阵，它要求在矩阵乘法的意义下与它的共轭转置矩阵满足交换律。这也就是说，若矩阵 $\mathbf M$ 满足如下条件，则称其为正规矩阵： $\mathbf M\mathbf M^{\mathsf H} = \mathbf M^{\mathsf H}\mathbf M.$ 。显而易见，复系数的酉矩阵和实系数的正交矩阵都是正规矩阵。显而易见，正规矩阵并不只有酉矩阵或正交矩阵。例如说，矩阵 $\mathbf M = \begin{pmatrix}1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1\end{pmatrix}$ 即是一个正规矩阵，但它显然不是酉矩阵或正交矩阵；因为 $\mathbf M\mathbf M^{\mathsf H} = \begin{pmatrix}2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2\end{pmatrix} = \mathbf M^{\mathsf H}\mathbf M.$

谱定理和谱分解

矩阵的对角化是线性代数中的一个重要命题。谱定理（spectral theorem）给出了方阵对角化的一个结论：若矩阵 $\mathbf M$ 是一个正规矩阵，则存在酉矩阵 $\mathbf U$，以及对角矩阵 $\mathbf \Lambda$，使得 $\mathbf M = \mathbf U\mathbf \Lambda\mathbf U^{\mathsf H}.$
这也就是说，正规矩阵，可经由酉变换，分解为对角矩阵；这种矩阵分解的方式，称为谱分解（spectral decomposition）。

SVD 的计算方法

SVD 与特征值

现在，假设矩阵 $\mathbf M_{m\times n}$ 的 SVD 分解是 $\mathbf M = \mathbf U\mathbf\Sigma\mathbf V^{\mathsf H};$ 那么，我们有

$\begin{aligned} \mathbf M\mathbf M^{\mathsf H} &{}= \mathbf U\mathbf\Sigma\mathbf V^{\mathsf H}\mathbf V\mathbf\Sigma^{\mathsf H}\mathbf U^{\mathsf H} = \mathbf U(\mathbf\Sigma\mathbf\Sigma^{\mathsf H})\mathbf U^{\mathsf H}\\ \mathbf M^{\mathsf H}\mathbf M &{}= \mathbf V\mathbf\Sigma^{\mathsf H}\mathbf U^{\mathsf H}\mathbf U\mathbf\Sigma\mathbf V^{\mathsf H} = \mathbf V(\mathbf\Sigma^{\mathsf H}\mathbf\Sigma)\mathbf V^{\mathsf H}\\ \end{aligned}$

这也就是说，$\mathbf U$ 的列向量（左奇异向量），是 $\mathbf M\mathbf M^{\mathsf H}$ 的特征向量；同时，$\mathbf V$ 的列向量（右奇异向量），是 $\mathbf M^{\mathsf H}\mathbf M$ 的特征向量；另一方面，$\mathbf M$ 的奇异值（$\mathbf\Sigma$ 的非零对角元素）则是 $\mathbf M\mathbf M^{\mathsf H}$ 或者 $\mathbf M^{\mathsf H}\mathbf M$ 的非零特征值的平方根。

如何计算 SVD

有了这些知识，我们就能手工计算出任意矩阵的 SVD 分解了；具体来说，算法如下

计算 $\mathbf M\mathbf M^{\mathsf H}$ 和 $\mathbf M^{\mathsf H}\mathbf M$；
分别计算 $\mathbf M\mathbf M^{\mathsf H}$ 和 $\mathbf M^{\mathsf H}\mathbf M$ 的特征向量及其特征值；
$\mathbf M\mathbf M^{\mathsf H}$ 的特征向量组成 $\mathbf U$；而 $\mathbf M^{\mathsf H}\mathbf M$ 的特征向量组成 $\mathbf V$；
对 $\mathbf M\mathbf M^{\mathsf H}$ 和 $\mathbf M^{\mathsf H}\mathbf M$ 的非零特征值求平方根，对应上述特征向量的位置，填入 $\mathbf\Sigma$ 的对角元。

实际计算看看

现在，我们来试着计算 $\mathbf M = \begin{bmatrix}2 & 4 \\ 1 & 3 \\ 0 & 0 \\ 0 & 0\end{bmatrix}$ 的奇异值分解。计算奇异值分解，需要计算 $\mathbf M$ 与其共轭转置的左右积；这里主要以 $\mathbf M\mathbf M^{\mathsf H}$ 为例。
首先，我们需要计算 $\mathbf M\mathbf M^{\mathsf H}$，

$\mathbf W = \mathbf M\mathbf M^{\mathsf H} = \begin{bmatrix}2 & 4 \\ 1 & 3 \\ 0 & 0 \\ 0 & 0\end{bmatrix}\begin{bmatrix}2 & 1 & 0 & 0 \\ 4 & 3 & 0 & 0\end{bmatrix} = \begin{bmatrix}20 & 14 & 0 & 0 \\ 14 & 10 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0\end{bmatrix}.$

现在，我们要求 $\mathbf W$ 的特征值与特征向量。根据定义 $\mathbf W\vec x = \lambda \vec x$；因此 $(\mathbf W - \lambda\mathbf I)\vec x = \vec 0$。这也就是说

$\begin{bmatrix} 20 - \lambda & 14 & 0 & 0 \\ 14 & 10 - \lambda & 0 & 0 \\ 0 & 0 & -\lambda & 0 \\ 0 & 0 & 0 & -\lambda \end{bmatrix}\vec x = \vec 0.$

根据线性方程组的理论，若要该关于 $\vec x$ 的方程有非零解，则要求系数矩阵的行列式为 0；也就是

$\begin{vmatrix} 20 - \lambda & 14 & 0 & 0 \\ 14 & 10 - \lambda & 0 & 0 \\ 0 & 0 & -\lambda & 0 \\ 0 & 0 & 0 & -\lambda \end{vmatrix} = \begin{vmatrix} 20 - \lambda & 14 \\ 14 & 10 - \lambda \\ \end{vmatrix}\begin{vmatrix} -\lambda & 0 \\ 0 & -\lambda \\ \end{vmatrix} = 0,$

这也就是 $\bigl((20 - \lambda)(10 - \lambda) - 196\bigr)\lambda^2 = 0$；解得 $\lambda_{1} = \lambda_{2} = 0$ , $\lambda_{3} = 15 + \sqrt{221} \approx 29.866$ , $\lambda_{4} = 15 - \sqrt{221} \approx 0.134$ 。将特征值代入原方程，可解得对应的特征向量；这些特征向量即作为列向量，形成矩阵

$\mathbf U = \begin{bmatrix}-0.82 & -0.58 & 0 & 0 \\ -0.58 & 0.82 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}.$

同理可解得（注意，$\mathbf M\mathbf M^{\mathsf T}$ 和 $\mathbf M^{\mathsf T}\mathbf M$ 的特征值相同）

$\mathbf V = \begin{bmatrix}-0.40 & -0.91 \\ -0.91 & 0.40\end{bmatrix}.$

以及 $\mathbf\Sigma$ 上的对角线元素由 $\mathbf W$ 的特征值的算术平方根组成；因此有

$\mathbf\Sigma = \begin{bmatrix}5.46 & 0 \\ 0 & 0.37 \\ 0 & 0 \\ 0 & 0\end{bmatrix}.$

因此我们得到矩阵 $\mathbf M$ 的 SVD 分解（数值上做了近似）：

$\begin{bmatrix}2 & 4 \\ 1 & 3 \\ 0 & 0 \\ 0 & 0\end{bmatrix} \approx \begin{bmatrix}-0.82 & -0.58 & 0 & 0 \\ -0.58 & 0.82 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}\begin{bmatrix}5.46 & 0 \\ 0 & 0.37 \\ 0 & 0 \\ 0 & 0\end{bmatrix}\begin{bmatrix}-0.40 & -0.91 \\ -0.91 & 0.40\end{bmatrix}$

几何上的直观解释

我们先来看一个例子。假设 $\mathbf M$ 是一个 $m\times n$ 的矩阵，而 $\mathbf x$ 是线性空间 $\mathbb K^n$ 中的向量，则$\mathbf y = \mathbf M\cdot\mathbf x$ 是线性空间 $\mathbb K^m$ 中的向量。这样一来，矩阵 $\mathbb A$ 就对应了一个从 $\mathbb K^n$ 到 $\mathbb K^m$ 的变换 $T: \mathbb K^n \to \mathbb K^m$，具体来说既是 $\mathbf x\mapsto \mathbf M\cdot\mathbf x$。这也就是说，在线性代数中，任意矩阵都能看做是一种变换。这样一来，我们就统一了矩阵和变换。

SVD 场景

隐性语义检索

信息检索-隐性语义检索（Lstent Semantic Indexing, LSI）或隐形语义分析（Latent Semantic Analysis, LSA）
隐性语义索引：矩阵 = 文档 + 词语
最早的 SVD 应用之一，我们称利用 SVD 的方法为隐性语义索引（LSI）或隐性语义分析（LSA）。

推荐系统

利用 SVD 从数据中构建一个主题空间。
再在该空间下计算其相似度。(从高维-低维空间的转化，在低维空间来计算相似度，SVD 提升了推荐系统的效率。)

图像压缩

例如：32*32=1024 => 32*2+2*1+32*2=130(2*1表示去掉了除对角线的0), 几乎获得了10倍的压缩比。

SVD 工作原理

矩阵分解

矩阵分解是将数据矩阵分解为多个独立部分的过程。
矩阵分解可以将原始矩阵表示成新的易于处理的形式，这种新形式是两个或多个矩阵的乘积。（类似代数中的因数分解）
举例：如何将12分解成两个数的乘积？（1，12）、（2，6）、（3，4）都是合理的答案。

SVD 是矩阵分解的一种类型，也是矩阵分解最常见的技术

SVD 将原始的数据集矩阵 Data 分解成三个矩阵 U、∑、V
举例：如果原始矩阵 $Data_{m*n} $ 是m行n列，
- $U_{m * k}$ 表示m行k列
- $∑_{k * k}$ 表示k行k列
- $V_{k * n}$ 表示k行n列。

$Data_{m×n} = U_{m×k} * ∑_{k×k} * V_{k×n}$

具体的案例：

$\begin{vmatrix} 0 & -1.6 & 0.6 \\ 0 & 1.2 & 0.8 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{vmatrix} = \begin{vmatrix} 0.8 & 0.6 & 0 & 0 \\ -0.6 & 0.8 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{vmatrix} * \begin{vmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ \end{vmatrix} * \begin{vmatrix} 0 & 0 & 1 \\ -1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{vmatrix}$

上述分解中会构建出一个矩阵∑，该矩阵只有对角元素，其他元素均为0(近似于0)。另一个惯例就是，∑的对角元素是从大到小排列的。这些对角元素称为奇异值。
奇异值与特征值(PCA 数据中重要特征)是有关系的。这里的奇异值就是矩阵 $Data * Data^T$ 特征值的平方根。
普遍的事实：在某个奇异值的数目(r 个=>奇异值的平方和累加到总值的90%以上)之后，其他的奇异值都置为0(近似于0)。这意味着数据集中仅有 r 个重要特征，而其余特征则都是噪声或冗余特征。

SVD 算法特点

优点：简化数据，去除噪声，优化算法的结果
缺点：数据的转换可能难以理解
使用的数据类型：数值型数据

'''recommend函数推荐引擎，默认调用standEst函数，产生最高的N个推荐结果
Args:
    dataMat         训练数据集
    user            用户编号
    simMeas         相似度计算方法
    estMethod       使用的推荐算法
Returns:  返回最终 N 个推荐结果
'''
def recommend(dataMat, user, N=3, simMeas=cosSim, estMethod=standEst):
    # 寻找未评级的物品,对给定的用户建立一个未评分的物品列表
    unratedItems = nonzero(dataMat[user, :].A == 0)[1] # .A: 矩阵转数组
    # 如果不存在未评分物品，那么就退出函数
    if len(unratedItems) == 0:
        return 'you rated everything'
    # 物品的编号和评分值
    itemScores = []
    # 在未评分物品上进行循环
    for item in unratedItems:
        # 获取 item 该物品的评分
        estimatedScore = estMethod(dataMat, user, simMeas, item)
        itemScores.append((item, estimatedScore))
    # 按照评分得分 进行逆排序，获取前N个未评级物品进行推荐
    return sorted(itemScores, key=lambda jj: jj[1], reverse=True)[: N]

测试和项目调用

测试代码

# 计算相似度的方法
myMat = mat(loadExData3())
# 计算相似度的第一种方式
# print(recommend(myMat, 1, estMethod=svdEst))
# 计算相似度的第二种方式
# print(recommend(myMat, 1, estMethod=svdEst, simMeas=pearsSim))

# 默认推荐（菜馆菜肴推荐示例）
print(recommend(myMat, 2))

运行结果

菜馆菜肴推荐结果： [(3, 4.0), (5, 4.0), (6, 4.0)]

***Repl Closed***

分析结果，我们不难发现，分别对3烤牛肉，5鲁宾三明治、6印度烤鸡给我4星好评，推荐给我们的用户。

要点补充

基于内容(content-based)的推荐

通过各种标签来标记菜肴
将这些属性作为相似度计算所需要的数据
这就是：基于内容的推荐。

构建推荐引擎面临的挑战

问题

1）在大规模的数据集上，SVD分解会降低程序的速度
2）存在其他很多规模扩展性的挑战性问题，比如矩阵的表示方法和计算相似度得分消耗资源。
3）如何在缺乏数据时给出好的推荐-称为冷启动【简单说：用户不会喜欢一个无效的物品，而用户不喜欢的物品又无效】

建议

1）在大型系统中，SVD分解(可以在程序调入时运行一次)每天运行一次或者其频率更低，并且还要离线运行。
2）在实际中，另一个普遍的做法就是离线计算并保存相似度得分。(物品相似度可能被用户重复的调用)
3）冷启动问题，解决方案就是将推荐看成是搜索问题，通过各种标签／属性特征进行基于内容的推荐。

项目案例: 基于SVD的图像压缩

收集并准备数据

将文本数据转化为矩阵

'''图像压缩函数'''
def imgLoadData(filename):
    myl = []
    for line in open(filename).readlines():
        newRow = []
        for i in range(32):
            newRow.append(int(line[i]))
        myl.append(newRow)
    # 矩阵调入后，就可以在屏幕上输出该矩阵
    myMat = mat(myl)
    return myMat

分析数据: 分析Sigma的长度个数

通常保留矩阵 80% ～ 90% 的能量，就可以得到重要的特征并去除噪声。

'''分析 Sigma 的长度取值
根据自己的业务情况，就行处理，设置对应的 Singma 次数
通常保留矩阵 80% ～ 90% 的能量，就可以得到重要的特征并取出噪声。
'''
def analyse_data(Sigma, loopNum=20):
    # 总方差的集合（总能量值）
    Sig2 = Sigma**2
    SigmaSum = sum(Sig2)
    for i in range(loopNum):
        SigmaI = sum(Sig2[:i+1])
        print('主成分：%s, 方差占比：%s%%' % (format(i+1, '2.0f'), format(SigmaI/SigmaSum*100, '.2f')))

使用算法: 对比使用 SVD 前后的数据差异对比，对于存储大家可以试着写写

例如：32*32=1024 => 32*2+2*1+32*2=130(2*1表示去掉了除对角线的0), 几乎获得了10倍的压缩比。

'''打印矩阵
由于矩阵保护了浮点数，因此定义浅色和深色，遍历所有矩阵元素，当元素大于阀值时打印1，否则打印0
'''
def printMat(inMat, thresh=0.8):
    for i in range(32):
        for k in range(32):
            if float(inMat[i, k]) > thresh:
                print(1)
            else:
                print(0)
        print('')


'''实现图像压缩，允许基于任意给定的奇异值数目来重构图像
Args:
    numSV       Sigma长度
    thresh      判断的阈值
'''
def imgCompress(numSV=3, thresh=0.8):
    # 构建一个列表
    myMat = imgLoadData('./0_5.txt')

    print("****original matrix****")
    # 对原始图像进行SVD分解并重构图像e
    printMat(myMat, thresh)

    # 通过Sigma 重新构成SigRecom来实现
    # Sigma是一个对角矩阵，因此需要建立一个全0矩阵，然后将前面的那些奇异值填充到对角线上。
    U, Sigma, VT = la.svd(myMat)
    # SigRecon = mat(zeros((numSV, numSV)))
    # for k in range(numSV):
    #     SigRecon[k, k] = Sigma[k]

    # 分析插入的 Sigma 长度
    # analyse_data(Sigma, 20)

    SigRecon = mat(eye(numSV) * Sigma[: numSV])
    reconMat = U[:, :numSV] * SigRecon * VT[:numSV, :]
    print("****reconstructed matrix using %d singular values *****" % numSV)
    printMat(reconMat, thresh)

参考文献

完整代码下载

源码请进【机器学习和自然语言QQ群：436303759】文件下载：

作者声明

本文版权归作者所有，旨在技术交流使用。未经作者同意禁止转载，转载后需在文章页面明显位置给出原文连接，否则相关责任自行承担。

专注人工智能领域研究

一步步教你轻松学奇异值分解SVD降维算法

奇异值分解原理

什么是奇异值分解(SVD）

矩阵知识

SVD 的计算方法

SVD 与特征值

如何计算 SVD

实际计算看看

几何上的直观解释

SVD 场景

SVD 工作原理

矩阵分解

SVD 是矩阵分解的一种类型，也是矩阵分解最常见的技术

SVD 算法特点

推荐系统

推荐系统场景

推荐系统要点

相似度计算

推荐系统的评价

推荐系统原理

项目实战: 餐馆菜肴推荐系统

收集并准备数据

排序获取最后的推荐结果

测试和项目调用

要点补充

项目案例: 基于SVD的图像压缩

收集并准备数据

分析数据: 分析Sigma的长度个数

使用算法: 对比使用 SVD 前后的数据差异对比，对于存储大家可以试着写写

参考文献

完整代码下载

作者声明

奇异值分解原理

什么是奇异值分解(SVD）

矩阵知识

SVD 的计算方法

SVD 与特征值

如何计算 SVD

实际计算看看

几何上的直观解释

SVD 场景

SVD 工作原理

矩阵分解

SVD 是矩阵分解的一种类型，也是矩阵分解最常见的技术

SVD 算法特点

推荐系统

推荐系统场景

推荐系统要点

相似度计算

推荐系统的评价

推荐系统原理

项目实战: 餐馆菜肴推荐系统

收集并准备数据

训练算法: 通过调用 recommend() 函数进行推荐

排序获取最后的推荐结果

测试和项目调用

要点补充

项目案例: 基于SVD的图像压缩

收集并准备数据

分析数据: 分析Sigma的长度个数

使用算法: 对比使用 SVD 前后的数据差异对比，对于存储大家可以试着写写

参考文献

完整代码下载

作者声明