奇异值分解(singular value decomposition)
特征值分解与PCA
一个矩阵的特征值分解可以将矩阵分解为更加规则和简单的子矩阵
但是不是所有矩阵都可以轻易地如此分解,当且仅当A有满秩的线性无关的特征向量,才可以做这样的分解。
不过,有一种特殊的矩阵——实对称矩阵,一定存在与维数相同个不等的特征值,也即存在与维数相同个线性无关且正交的特征向量。
PCA也就是利用了这一结论,因为PCA希望提取出主成分(新的正交基),在主成分上投影后原矩阵列向量的方差最大(保存信息最多),这恰好和A的协方差矩阵联系了起来,经过推导发现协方差矩阵经过特征值分解后得到的特征向量就是我们需要的使方差最大化的一组正交基。
PCA方法提出出主成分后,矩阵的两两比较,可以用它们的主成分来比较,这样可以加速某种识别或比对,如人脸检测和人脸识别;另外一种应用场景就是降维可视化,因为高维空间要将数据做成直观的可视化图形并不容易,降维(特别是2维)后就很容易在平面上展示,而且特征信息并不会丢失,如点之间的聚合和分散程度。
奇异值分解 简介
特征值分解是一个提取矩阵特征很不错的方法,但是它只是对方阵而言的,在现实的世界中,我们看到的大部分矩阵都不是方阵,比如说有N个学生,每个学生有M科成绩,这样形成的一个
奇异值分解可以用来干这个事情,奇异值分解是一个能适用于任意的矩阵的一种分解的方法:
奇异值分解是一个有着很明显的物理意义的一种方法,它可以将一个比较复杂的矩阵用更小更简单的几个子矩阵的相乘来表示,这些小矩阵描述的是矩阵的重要的特性。
所以说,奇异值分解和特征值分解的目标都是一样的——将矩阵分解为更加规则和简单的子矩阵,而且这些子矩阵描述了原矩阵的核心信息。
下图可以很形象的看出上面SVD的定义:
奇异值分解计算步骤
其中U是m×m阶酉矩阵,其向量称为左奇异向量;Σ是m×n阶非负实数对角矩阵,对角线上的值称为奇异值;而
一般计算步骤:
假设原数据为X,一行代表一个样本,列代表特征。
1)计算X’X,XX’;
2)对XX’进行特征值分解,得到的特征向量组成U,
3)对X’X进行特征值分解,得到的特征向量组成V,
4)通过求出
不过在应用中我们无需这样手动计算,调用np.linalg.svd(X)
即可得到一个元组(U,Sigma,V)
SVD用于PCA
要用PCA降维,需要找到样本协方差矩阵
注意到我们的SVD也可以得到协方差矩阵
另一方面,注意到PCA仅仅使用了我们SVD的右奇异矩阵,没有使用左奇异矩阵,那么左奇异矩阵有什么用呢?
假设我们的样本是
可以得到一个
——参考文献:奇异值分解(SVD)原理与在降维中的应用 - 刘建平Pinard
简记:左乘
SVD与矩阵压缩
对于奇异值,它跟我们特征分解中的特征值类似,在奇异值矩阵中也是按照从大到小排列,而且奇异值的减少特别的快,在很多情况下,前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说,我们也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说:
其中k要比n小很多,也就是一个大的矩阵A可以用三个小的矩阵
由于这个重要的性质,SVD可以用于PCA降维,来做数据压缩和去噪。也可以用于推荐算法,将用户和喜好对应的矩阵做特征分解,进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法,比如潜在语义索引(LSI)。