特征值分解(EVD)和奇异值分解(SVD)简单总结。
矩阵分解的作用:
- 矩阵填充(通过矩阵分解来填充原有矩阵,例如协同过滤的ALS算法就是填充原有矩阵)
- 清理异常值与离群点
- 降维、压缩
- 个性化推荐
- 间接的特征组合(计算特征间相似度)
如果一个向量 v 是矩阵 A 的特征向量,将一定可以表示成下面的形式:
Av=λv
其中,λ 是特征向量 v 对应的特征值,一个矩阵的一组特征向量是一组正交向量。
对于矩阵 A,有一组特征向量 v,将这组向量进行正交化单位化,就能得到一组正交单位向量。特征值分解(Eigenvalue decomposition,EVD),就是将矩阵 A 分解为如下式:
A=QΣQ−1
其中,Q 是矩阵 A 的特征向量组成的矩阵,Σ 则是一个对角阵,对角线上的元素就是特征值。
解特征值的方式很简单,通过定义我们可以得到
∣A−λI∣=0
其中 I 为单位矩阵。
通过特征方程得到特征值,从而求出特征向量。
特征值分解示例
定义方阵 A 为
A=−1−41130002
下面对 A 进行特征值分解。
首先,由方阵 A 的特征方程,求出特征值:
∣A−λI∣=−1−λ−4113−λ0002−λ=(2−λ)−1−λ−413−λ=(2−λ)(λ−1)2=0
解得 λ=1,2,其中 1 为重根。
当 λ=2 时,求出 A−2I,过程如下
A−2I=−3−41110000→100010000
解得 x1=0,x2=0,取特征向量为 v1=001。
同理当 λ=1 时,特征向量为 v2=−1−21。
方阵 A 的特征分解为
A=QΣQT=001−1−21−1−21200010001001−1−21−1−21−1
SymPy 和 NumPy 均支持特征值分解,但 SymPy 是符号解,是精准值但更慢,适合研究。而 NumPy 为数值解,更快但有精度损失,适合生产。
SymPy 进行特征值分解:
from sympy import Matrix
A = Matrix([[-1, 1, 0], [-4, 3, 0], [1, 0, 2]])
print(A.eigenvals())
# {1: 2, 2: 1},特征值和其重根数量
print(A.eigenvects())
# [
# (1, 2, [ Matrix([[-1], [-2], [ 1]]) ]),
# (2, 1, [ Matrix([[0], [0], [1] ]) ]),
# ]
矩阵的 .eigenvects()
方法返回列表,每个列表是一个三元组,分别代表特征值、特征值的重根数和特征向量。
使用 NumPy 进行特征值分解:
import numpy as np
A = np.array([[-1, 1, 0], [-4, 3, 0], [1, 0, 2]])
vals, vecs = np.linalg.eig(A)
print(vals)
# [2. 1. 1.]
print(vecs)
# [[ 0. 0.40824829 0.40824829]
# [ 0. 0.81649658 0.81649658]
# [ 1. -0.40824829 -0.40824829]]
这里的特征向量和 SymPy 计算有所不同是因为 NumPy 进行了单位化。
特征值分解只能用于方阵,我们下面要介绍的 奇异值分解(Singular Value Decomposition,SVD)就是可以解决这个问题。
奇异值分解也有各种各样的用途:用 SVD 解 PCA、潜在语言索引也依赖于 SVD 算法。可以说,SVD 是矩阵分解、降维、压缩、特征学习的一个基础的工具,因而 SVD 在机器学习领域也相当的重要。
奇异值分解是一个能适用于任意矩阵的一种分解的方法,对于任意矩阵 A 总是存在一个奇异值分解:
A=UΣVT
若 A 是一个 m×n 的矩阵,那么得到的 U 是一个 m×m 方阵,U 里面的正交向量被称为左奇异向量。Σ 是一个 m×n 的矩阵,且 Σ 是对角矩阵,对角线上的元素称为奇异值。V 是 n×n 矩阵,且 U 和 V 都是酉矩阵。
那么我们如何计算左奇异向量、右奇异向量和奇异值呢?我们可以把奇异值和特征值联系起来。
首先,我们用矩阵 A 的转置乘 A,得到一个方阵,这样我们可以用方阵进行特征分解,得到特征值和特征向量满足下面的等式:
(ATA)vi=λivi
这里的 vi 就是右奇异向量,同理我们用下面的等式得到左奇异向量 ui:
(AAT)ui=λiui
当然以上结论只是我们的设想,下面进行证明,如果对证明细节不感兴趣可以忽略。
证明
⇒⇒AATATA=UΣVT=VΣTUT=VΣTUTUΣVT=VΣ2VT
提示:若 U 是实矩阵,且 UTU=I,那么 U 是实对称矩阵。
从上面的结论可以看出 ATA 的特征向量就是 SVD 中的 V 矩阵。同理 AAT 的特征矩阵为 U。
从证明中,我们得出求出奇异值的两种方法:
第一种方式是通过 Avi=σiui 得到 σi=AviuiT
第二种是通过 ATA=VΣ2VT 得出结论,特征值矩阵等于奇异值矩阵平方,也就是说特征值和奇异值满足如下关系
σi=λi
奇异值分解示例
矩阵 A 定义为
A=011110
首先计算 ATA 和 AAT:
ATA=[011110]011110=[2112]
AAT=011110[011110]=110121011
然后,求出 ATA 和 AAT 的特征值和特征向量:
- ATA 的特征值和特征向量
λ1=3,v1=[1/21/2]
λ2=1,v2=[−1/21/2]
- AAT 的特征值和特征向量
λ1=3,u1=1/62/61/6
λ2=1,u2=1/20−1/2
λ3=0,u3=1/3−1/31/3
其次,我们利用 Avi=σiui,i=1,2,求奇异值:
011110[1/21/2]=σ11/62/61/6⇒σ1=3
011110[1/2−1/2]=σ21/20−1/2⇒σ2=1
当然,最简单的方式是直接利用结论 σi=λi 得出奇异值。
最后,我们得到 A 的奇异值分解为
A=UΣVT=1/62/61/61/20−1/21/3−1/31/3300010[1/2−1/21/21/2]
此时 Σ 不为方阵,最后一行一定为 0,我们可以直接将其删去,因此也不需要计算最后一个特征值为 0 的特征向量。直接写为:
A=UΣVT=1/62/61/61/20−1/2[3001][1/2−1/21/21/2]
这里还是使用 SymPy 进行符号解和 NumPy 进行数值解两种方法。
SymPy 有求奇异值和奇异值分解的方法:
from sympy.matrices import Matrix
A = Matrix([[0, 1], [1, 1], [1, 0]])
print(A.singular_values())
# [sqrt(3), 1]
U, S, VH = A.singular_value_decomposition()
print(U)
# Matrix([[sqrt(2)/2, sqrt(6)/6],
# [0, sqrt(6)/3],
# [-sqrt(2)/2, sqrt(6)/6]])
print(S)
# Matrix([[1, 0],
# [0, sqrt(3)]])
print(VH)
# Matrix([[-sqrt(2)/2, sqrt(2)/2],
# [sqrt(2)/2, sqrt(2)/2]])
下面是 NumPy 进行奇异值分解的方法:
import numpy as np
A = np.array([[0, 1], [1, 1], [1, 0]])
U, S, VH = np.linalg.svd(A)
print(U)
# [[-4.08248290e-01 7.07106781e-01 5.77350269e-01]
# [-8.16496581e-01 2.64811510e-17 -5.77350269e-01]
# [-4.08248290e-01 -7.07106781e-01 5.77350269e-01]]
print(S)
# [1.73205081 1. ]
print(VH)
# [[-0.70710678 -0.70710678]
# [-0.70710678 0.70710678]]