SVD&PCA&LDA降维
目录
- SVD 奇异值分解 [无监督]
- PCA 主成份分析 [无监督]
- LDA 线性判别分析 [有监督]
- PCA与LDA的异同
1. SVD 奇异值分解(Singular Value Decomposition)
不仅可以用于降维算法中的特征分解,也可以用于推荐系统、自言语言处理等领域,是很多机器学习算法的基石。
1.1 特征值与特征向量
特征值和特征向量的定义如下: \[ Ax = \lambda x \]
其中A
是一个n x n
的矩阵,\(x\)是一个n维向量
,则我们\(\lambda\)是矩阵A
的一个特征值,而x
是矩阵A
的特征值\( \lambda \)所对应的特征向量。
根据特征值和特征向量,可以将矩阵A
特征分解。如果我们求出了矩阵A
的n
个特征值\( \lambda_1 \leq \lambda_2 \leq … \leq \lambda_n \)以及这n
个特征值所对应的特征向量\( \lbrace w_1, w_2, …, w_n \rbrace \),那么矩阵A
就可以用下式的特征分解表示:
\[
A = W \Sigma W^{-1}
\]
其中W
是这n
个特征向量所组成的n x n
维矩阵,而\( \Sigma \)为这n
个特征值为主对角线的n x n
维矩阵。
一般我们会把W
的这n
个特征向量标准化,即满足 \( || w_i ||_2=1 \), 或者说 \( w^T_i w_i=1 \),此时W
的n
个特征向量为标准正交基,满足\( W^T W=I \),即\( W^T=W^{−1}\), 也就是说W
为酉矩阵。
这样我们的特征分解表达式可以写成 \[ A=WΣW^T \]
注意到要进行特征分解,矩阵A必须为方阵。那么如果A不是方阵,即行和列不相同时,我们还可以对矩阵进行分解吗?答案是可以,这时就要使用到SVD了。
1.2 SVD的定义
SVD也是对矩阵进行分解,但是和特征分解不同,SVD并不要求要分解的矩阵为方阵。假设我们的矩阵\(A\)是一个m × n
的矩阵,那么我们定义矩阵\(A\)的SVD为:
\[
A=UΣV^T
\]
其中\(U\)是一个m × m
的矩阵,\(\Sigma\)是一个m × n
的矩阵,除了主对角线上的元素以外全为0,主对角线上的每个元素都称为奇异值,\(V\)是一个n × n
的矩阵。\(U\)和\(V\)都是酉矩阵,即满足\( U^TU=I,V^TV=I\)。下图可以很形象的看出上面SVD的定义:
如何求出SVD分解后的\( U, \Sigma, V \) 这三个矩阵呢?
如果将\(A^T\)和\(A\)做矩阵乘法,那么会得到n × n
的一个方阵\(A^TA\)。既然\(A^TA\)是方阵,那么就可以进行特征分解,得到的特征值和特征向量满足下式:
\[
(A^TA)v_i=\lambda_i v_i
\]
这样就可以得到矩阵\(A^TA\)的n
个特征值和对应的n
个特征向量\(v\)了。将\(A^TA\)的所有特征向量张成一个n × n
的矩阵\(V\),就是SVD公式里面的\(V\)矩阵了。一般将\(V\)中的每个特征向量叫做\(A\)的右奇异向量。
如果将\(A\)和\(A^T\)做矩阵乘法,那么会得到m × m
的一个方阵\(AA^T\)。既然\(AA^T\)是方阵,那么就可以进行特征分解,得到的特征值和特征向量满足下式:
\[
(AA^T)u_i=\lambda_iu_i
\]
这样就可以得到矩阵\(AA^T\)的m
个特征值和对应的m
个特征向量\(u\)了。将\(AA^T\)的所有特征向量张成一个m × m
的矩阵\(U\),就是SVD公式里面的\(U\)矩阵了。一般我们将\(U\)中的每个特征向量叫做\(A\)的左奇异向量。
\(U\)和\(V\)都求出来了,现在就剩下奇异值矩阵\( \Sigma \)没有求出了。由于\( \Sigma \)除了对角线上是奇异值其他位置都是0,那只需要求出每个奇异值\( \sigma \)就可以了。
注意到: \[ A=UΣV^T \Rightarrow AV=UΣV^TV \Rightarrow AV=UΣ \Rightarrow Av_i=\sigma_iu_i \Rightarrow \sigma_i= \frac{Av_i}{u_i} \]
这样可以求出每个奇异值,进而求出奇异值矩阵\( \Sigma \)。
上面还有一个问题没有讲,就是说\(A^TA\)的特征向量组成的就是我们SVD中的\(V\)矩阵,而\(AA^T\)的特征向量组成的就是我们SVD中的\(U\)矩阵,这有什么根据吗?这个其实很容易证明,我们以\(V\)矩阵的证明为例。 \[ A=UΣV^T \Rightarrow A^T=VΣ^TU^T \Rightarrow A^TA= VΣ^TU^TUΣV^T= VΣ^2V^T \]
上式证明使用了:\( U^TU=I,Σ^TΣ=Σ^2\),可以看出\( A^TA \)的特征向量组成的的确就是我们SVD中的\(V\)矩阵。类似的方法可以得到\(AA^T\)的特征向量组成的就是我们SVD中的\(U\)矩阵。
进一步还可以看出特征值矩阵等于奇异值矩阵的平方,也就是说特征值和奇异值满足如下关系: \[ \sigma_i=\sqrt{\lambda_i} \]
这样也就是说,可以不用\( \sigma_i= Av_i / u_i \)来计算奇异值,也可以通过求出\( A^TA \)的特征值取平方根来求奇异值。
1.3 SVD的性质
对于奇异值,它跟特征分解中的特征值类似,在奇异值矩阵中也是按照从大到小排列,而且奇异值的减少特别的快,在很多情况下,前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说,也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说: \[ A_{m×n}=U_{m×m} \Sigma_{m×n} V^T_{n×n} \sim U_{m×k} \Sigma_{k×k} V^T_{k×n} \]
其中 k 要比 n 小很多,也就是一个大的矩阵 A 可以用三个小的矩阵\( U_{m×k}, \Sigma_{k×k}, V^T_{k×n} \)来表示。如下图所示,现在我们的矩阵 A 只需要灰色的部分的三个小矩阵就可以近似描述了。
由于这个重要的性质,SVD可以用于PCA降维,来做数据压缩和去噪。也可以用于推荐算法,将用户和喜好对应的矩阵做特征分解,进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法,比如潜在语义索引(LSI)。
2. PCA 主成份分析
事先声明
当 X = 样本数量 * 每个样本的维度
时, 协方差矩阵为$ X^T X $;
当 X = 每个样本的维度 * 样本数量
时, 协方差矩阵为$ X X^T $;
2.1 PCA推导:基于小于投影距离(样本到超平面距离足够近)
假设 m 个 n 维数据\( (x^{(1)}, x^{(2)},…,x^{(m)}) \)都已经进行了中心化,即 \( \sum_{i=1}^m x^{(i)}=0 \)。经过投影变换后得到的新坐标系为\( \lbrace w_1,w_2,…,w_n \rbrace \),其中\(w\)是标准正交基,即\( || w ||^2 = 1, w^T_iw_j=0 \)。
如果将数据从 n 维降到 n’ 维,即丢弃新坐标系中的部分坐标,则新的坐标系为\( \lbrace w_1, w_2, …, w_{n′} \rbrace \),样本点\( x^{(i)} \)在 n’ 维坐标系中的投影为:\( z^{(i)} = ( z^{(i)}_1,z^{(i)}_2, …, z^{(i)}_{n′}) \)。其中,\( z^{(i)}_j = w^T_j x^{(i)} \)是\( x^{(i)} \)在低维坐标系里第 j 维的坐标。
如果用\( z^{(i)} \)来恢复原始数据\( x^{(i)} \),则得到的恢复数据 \( \bar{x}^{(i)} = \sum_{j=1}^{n′} z^{(i)}_j w_j = Wz^{(i)} \),其中,\(W\)为标准正交基组成的矩阵。
现在考虑整个样本集,希望所有的样本到这个超平面的距离足够近,即最小化下式: \[ \sum_{i=1}^m || \bar{x}^{(i)} − x^{(i)} ||^2_2 \]
将这个式子进行整理,可以得到: \[ \begin{equation} \begin{aligned} \sum_{i=1}^m || \bar{x}^{(i)} − x^{(i)} ||^2_2 & = \sum_{i=1}^m || Wz^{(i)} − x^{(i)} ||^2_2 \\ & = \sum_{i=1}^m (Wz^{(i)})^T (Wz^{(i)}) − 2 \sum_{i=1}^m (Wz^{(i)})^T x^{(i)} + \sum_{i=1}^m x^{(i)T}x^{(i)} \\ & = \sum_{i=1}^m z^{(i)T}z^{(i)} − 2 \sum_{i=1}^m z^{(i)T}W^T x^{(i)} + \sum_{i=1}^m x^{(i)T} x^{(i)} \\ & = \sum_{i=1}^m z^{(i)T}z^{(i)} − 2 \sum_{i=1}^m z^{(i)T}z^{(i)} + \sum_{i=1}^m x^{(i)T}x^{(i)} \\ & = − \sum_{i=1}^m z^{(i)T}z^{(i)} + \sum_{i=1}^m x^{(i)T}x^{(i)} \\ & = − tr( W^T ( \sum_{i=1}^m x^{(i)} x^{(i)T} ) W) + \sum_{i=1}^m x^{(i)T} x^{(i)} \\ & = − tr( W^T X X^T W) + \sum_{i=1}^m x^{(i)T} x^{(i)} \end{aligned} \end{equation} \]
- 第1个等式用到了\( \bar{x}^{(i)} = W z^{(i)} \)
- 第2个等式用到了平方和展开
- 第3个等式用到了矩阵转置公式\( (AB)^T= B^T A^T \) 和 \( W^T W =I \)
- 第4个等式用到了\( z^{(i)} = W^T x^{(i)} \)
- 第5个等式合并同类项
- 第6个等式用到了\( z^{(i)} = W^T x^{(i)} \)和矩阵的迹
- 第7个等式将代数和表达为矩阵形式
注意到\( \sum_{i=1}^m x^{(i)} x^{(i)T} \)是数据集的协方差矩阵,\(W\)的每一个向量\(w_j\)是标准正交基。而\( \sum_{i=1}^m x^{(i)T} x^{(i)} \) 是一个常量。最小化上式等价于: \[ \arg\min_W - tr( W^T X X^T W ) \quad \quad s.t. W^TW = I \]
这个最小化不难,直接观察也可以发现最小值对应的\(W\)由协方差矩阵\(XX^T\)最大的 n’ 个特征值对应的特征向量组成。当然用数学推导也很容易。利用拉格朗日函数可以得到 \[ J(W) = −tr( W^T X X^T W) + \lambda ( W^T W − I ) \]
对\( W \)求导有\( − X X^T W + \lambda W = 0 \),整理下即为: \[ XX^T W = \lambda W \]
这样可以更清楚的看出,\(W\)为\(X X^T \)的 n’ 个特征向量组成的矩阵,而\( \lambda \) 为 \( XX^T \) 的特征值。当我们将数据集从 n 维降到 n’ 维时,需要找到最大的 n’ 个特征值对应的特征向量。这 n’ 个特征向量组成的矩阵\( W\) 即为我们需要的矩阵。对于原始数据集,我们只需要用\( z^{(i)} = W^T x^{(i)} \),就可以把原始数据集降维到最小投影距离的 n’ 维数据集。
2.2 PCA的推导:基于最大投影方差
假设 m 个 n 维数据\( (x^{(1)}, x^{(2)}, …, x^{(m)} ) \)都已经进行了中心化,即\( \sum_{i=1}^m x^{(i)} = 0 \)。经过投影变换后得到的新坐标系为\( \lbrace w_1, w_2, …, w_n \rbrace \),其中\( w\) 是标准正交基,即\( || w ||^2 = 1, w^T_i w_j = 0\)。
如果将数据从 n 维降到 n’ 维,即丢弃新坐标系中的部分坐标,则新的坐标系为\( \lbrace w_1, w_2, …, w_{n′} \rbrace \),样本点\( x^{(i)} \) 在 n’ 维坐标系中的投影为:\( z^{(i)} = ( z^{(i)}_1, z^{(i)}_2, …, z^{(i)}_{n′}) \) 。其中,\( z^{(i)}_j = w^T_j x^{(i)} \)是 \( x^{(i)} \) 在低维坐标系里第 j 维的坐标。
对于任意一个样本\( x^{(i)} \),在新的坐标系中的投影为\( W^T x^{(i)} \),在新坐标系中的投影方差为\( W^T x^{(i)} x^{(i)T}W \),要使所有的样本的投影方差和最大,也就是最大化\( \sum_{i=1}^m W^T x^{(i)} x^{(i)T} W \),即: \[ \arg\max_W tr(W^T X X^T W) \quad \quad s.t. W^TW=I \]
观察上一节的基于最小投影距离的优化目标,可以发现完全一样,只是一个是加负号的最小化,一个是最大化。
利用拉格朗日函数可以得到 \[ J(W) = tr( W^T X X^T W) + \lambda (W^T W − I) \]
对\( W \) 求导有 \( XX^T W + \lambda W = 0 \),整理下即为: \[ XX^TW = (−\lambda)W \]
和上面一样可以看出,\(W\)为\(XX^T\)的 n’ 个特征向量组成的矩阵,而 \( −\lambda \) 为\( XX^T\) 的特征值。将数据集从 n 维降到 n’ 维时,需要找到最大的 n’ 个特征值对应的特征向量。这 n’ 个特征向量组成的矩阵\( W \)即为需要的矩阵。对于原始数据集,只需要用\( z^{(i)} = W^T x^{(i)} \),就可以把原始数据集降维到最小投影距离的 n’ 维数据集。
2.3 PCA算法流程
输入: n 维样本集 \( D = ( x^{(1)}, x^{(2)}, …, x^{(m)} ) \),要降维到的维数 n’。
输出: 降维后的样本集 \( D′ \)
- 对所有的样本进行中心化: \( x^{(i)} = x^{(i)} − \frac{1}{m} \sum_{j=1}^m x^{(j)} \)
- 计算样本的协方差矩阵\( XX^T \)
- 对矩阵\( XX^T \)进行特征值分解
- 取出最大的 n’ 个特征值对应的特征向量\( (w_1, w_2, …, w_{n′}) \),将所有的特征向量标准化后,组成特征向量矩阵\(W\)
- 对样本集中的每一个样本\( x^{(i)}\),转化为新的样本\( z^{(i)} = W^T x^{(i)} \)
- 得到输出样本集 \( D′=(z^{(1)}, z^{(2)}, …, z^{(m)} ) \)
有时候,我们不指定降维后的 n’ 的值,而是换种方式,指定一个降维到的主成分比重阈值 t 。这个阈值 t 在(0,1] 之间。假如我们的n个特征值为 \( \lambda_1 \geq \lambda_2 \geq … \geq \lambda_n \),则 n’ 可以通过下式得到: \[ \sum_{i=1}^{n′} \lambda_i / \sum_{i=1}^n \lambda_i \geq t \]
2.4 PCA实例
假设我们的数据集有 10 个二维数据需要用PCA降到1维特征,数据如下:
1 | (2.5, 2.4), (0.5, 0.7), (2.2, 2.9), (1.9, 2.2), (3.1, 3.0), |
首先对样本中心化,这里样本的均值为 (1.81, 1.91), 所有的样本减去这个均值后,即中心化后的数据集为
1 | (0.69, 0.49), (-1.31, -1.21), ( 0.39, 0.99), ( 0.09, 0.29), ( 1.29, 1.09), |
现在开始求样本的协方差矩阵,由于数据是二维的,则协方差矩阵为: \[ XX^T = \left( \begin{matrix} cov(x1,x1) & cov(x2,x1) \\ cov(x1,x2) & cov(x2,x2) \end{matrix} \right) \]
对于上述数据,求出协方差矩阵为: \[ XX^T = \left( \begin{matrix} 0.616555556 & 0.615444444 \\ 0.615444444 & 0.716555556 \end{matrix} \right) \]
求出特征值为 \((0.0490834, 1.28402771)\),对应的特征向量分别为:\( (-0.73517866, -0.6778734)^T, (0.6778734, -0.73517866)^T \), 由于最大的 k=1 个特征值为 1.28402771,对于的k=1个特征向量为 \( (0.6778734, -0.73517866)^T \)。 则 \( W=(0.6778734, -0.73517866)^T \)。
对所有的数据集进行投影\( z^{(i)} = W^T x^{(i)} \)[乘的是中心化后的x],得到PCA降维后的 10 个一维数据集为:
1
2 0.1074951 0.00155202 -0.46345624 -0.1521932 0.07311195
-0.24863317 0.35670133 0.04641726 0.01776463 0.26124033
下面是例子的Python代码
1 | import numpy as np |
2.5 PCA总结
作为一个非监督学习的降维方法,它只需要特征值分解,就可以对数据进行压缩,去噪。因此在实际场景应用很广泛。为了克服PCA的一些缺点,出现了很多PCA的变种,为解决非线性降维的KPCA、为解决内存限制的增量PCA方法Incremental PCA,以及解决稀疏数据降维的PCA方法Sparse PCA等。
PCA算法的主要优点有:
- 仅仅需要以方差衡量信息量,不受数据集以外的因素影响
- 各主成分之间正交,可消除原始数据成分间的相互影响的因素
- 计算方法简单,主要运算是特征值分解,易于实现
PCA算法的主要缺点有:
- 主成分各个特征维度的含义具有一定的模糊性,不如原始样本特征的解释性强
- 方差小的非主成分也可能含有对样本差异的重要信息,因降维丢弃可能对后续数据处理有影响
2.6 PCA实现方面
PCA降维需要找到样本协方差矩阵\( X^TX \)的最大的 d 个特征向量,然后用这最大的 d 个特征向量张成的矩阵来做低维投影降维。 可以看出,在这个过程中需要先求出协方差矩阵\( X^TX\),当样本数多样本特征数也多的时候,这个计算量是很大的。
注意到SVD也可以得到协方差矩阵\( X^TX \)最大的 d 个特征向量张成的矩阵,但是SVD有个好处,有一些SVD的实现算法可以不求先求出协方差矩阵\(X^TX\),也能求出右奇异矩阵\( V \)。 也就是说,PCA算法可以不用做特征分解,而是做SVD来完成。这个方法在样本量很大的时候很有效。 实际上,scikit-learn的PCA算法的背后真正的实现就是用的SVD,而不是暴力特征分解。
另一方面,注意到PCA仅仅使用了SVD的右奇异矩阵,没有使用左奇异矩阵,那么左奇异矩阵有什么用呢?
假设样本是 m×n 的矩阵 \(X\),如果通过SVD找到了矩阵\( XX^T \)最大的 d 个特征向量张成的 m×d 维矩阵\(U\),则如果进行如下处理: \[ X′_{d×n} = U^T_{d×m} X_{m×n} \]
可以得到一个 d×n 的矩阵\( X’ \),这个矩阵和原来的 m×n 维样本矩阵\( X \)相比,行数从 m 减到了 k ,可见对行数进行了压缩。 也就是说,左奇异矩阵可以用于行数的压缩;相对的,右奇异矩阵可以用于列数即特征维度的压缩,也就是PCA降维。
3. LDA 线性判别分析(Linear Discriminant Analysis | Fisher Linear Discriminant)
LDA是一种有监督的线性降维算法,与PCA保持数据信息不同,LDA是为了使得降维后的数据点尽可能地容易被区分。
LDA将训练集中的点映射到一条直线上,(1)使得相同类别中的点尽可能靠在一起,(2)属于不同类别的点尽可能离得比较远。 我们的目标就是找到一条直线,尽可能满足上面的要求。
来看一个例子:两类会这样被降维
设数据集\( D=\lbrace (x_i, y_i) \rbrace^m_{i=1} \),投影向量为\(w\),则点\(x_i\)经过投影后为\( y=w^Tx_i\),投影前的样本中心点为\( u \),投影后的中心点为\( \bar{u} = w^T u\)。
希望投影后不同类别的样本尽量离得较远:使用度量值 \[ || \hat{u}_0 - \hat{u}_1 ||^2_2 \]
同时希望投影后相同类别的样本之间尽量离得较近:使用度量值 \[ \sum_{y \in Y_i} (y - \hat{u}_i)^2 \]
这个值其实就是投影后样本的方差乘以此类样本集合中样本的数量。
所以总的优化目标函数为: \[ J(W) = \frac{|| \hat{u}_0 - \hat{u}_1 ||^2_2}{\sum_{y\in Y_i} ( y - \hat{u}_i )^2} = \frac{|| \hat{u}_0 - \hat{u}_1 ||^2_2}{\sum_0 ( y - \hat{u}_0 )^2 + \sum_1 (y - \hat{u}_1)^2} \]
目标\(J(W)\)当然是越大越好;
定义类内散度矩阵为: \( S_w = \sum_0 + \sum_1 = \sum_{X_0} (x-u_0)(x-u_0)^T + \sum_{X_1} (x-u_1)(x-u_1)^T \)
定义类间散度矩阵:\( S_b = (u_0 - u_1)(u_0 - u_1)^T \)
分子:\( || \hat{u}_0 - \hat{u}_1 ||^2_2 = w^T (u_0 - u_1)(u_0 - u_1)^T w = w^TS_bw \)
分母:\( \sum_0 (y-\hat{u}_0)^2 + \sum_1 (y-\hat{u}_1)^2 = w^T S_w w \)
所以\( J(w)= w^TS_bw / w^T S_w w \),因为向量\( w \)的长度成比例改变不影响\( J(W) \)的取值,所以我们令\( w^TS_ww=1 \),那么原优化目标就变为 \[ \min_{w} J(W) = - w^T S_b w, \quad \quad s.t. \quad w^TS_ww = 1 \]
这里直接使用拉格朗日乘子法就可以了,解得 \[ S_b w = \lambda w S_w \]
因为\( S_bw = (u_0-u_1)(u_0-u_1)^Tw = (u_0 - u_1) \lambda_t \), 所以\( (u_0 - u_1)\lambda_t = \lambda w S_w \),可以得到 \[ w = S_w^{-1} (u_0 - u_1) \]
LDA局限性:
- 当样本数量远小于样本的特征维数,样本与样本之间的距离变大使得距离度量失效,使LDA算法中的类内、类间离散度矩阵奇异,不能得到最优的投影方向,在人脸识别领域中表现得尤为突出
- LDA不适合对非高斯分布的样本进行降维
- LDA在样本分类信息依赖方差而不是均值时,效果不好
- LDA可能过度拟合数据
4. PCA与LDA的异同
出发思想不同。PCA主要是从特征的协方差角度,去找到比较好的投影方式,即选择样本点投影具有最大方差的方向(在信号处理中认为信号具有较大的方差,噪声有较小的方差,信噪比就是信号与噪声的方差比,越大越好);而LDA则更多的是考虑了分类标签信息,寻求投影后不同类别之间数据点距离更大化以及同一类别数据点距离最小化,即选择分类性能最好的方向。
学习模式不同。PCA属于无监督式学习,因此大多场景下只作为数据处理过程的一部分,需要与其他算法结合使用,例如将PCA与聚类、判别分析、回归分析等组合使用;LDA是一种监督式学习方法,本身除了可以降维外,还可以进行预测应用,因此既可以组合其他模型一起使用,也可以独立使用。
降维后可用维度数量不同。LDA降维后最多可生成 C-1 维子空间(分类标签数-1),因此LDA与原始维度 N 数量无关,只有数据标签分类数量有关;而PCA最多有n维度可用,即最大可以选择全部可用维度。
投影的坐标系不一定相同。PCA投影的坐标系都是正交的;LDA关注分类能力,不保证投影到的坐标系是正交的。
上图左侧是PCA的降维思想,它所作的只是将整组数据整体映射到最方便表示这组数据的坐标轴上,映射时没有利用任何数据内部的分类信息。因此,虽然PCA后的数据在表示上更加方便(降低了维数并能最大限度的保持原有信息),但在分类上也许会变得更加困难;上图右侧是LDA的降维思想,可以看到LDA充分利用了数据的分类信息,将两组数据映射到了另外一个坐标轴上,使得数据更易区分了(在低维上就可以区分,减少了运算量)。