您的位置: 首页  >  文章  >  机器学习降维之线性判别模型(LDA)

机器学习降维之线性判别模型(LDA)

分类: 文章 • 2023-03-28 16:34:36

1.LDA简介

线性判别分析(Linear Discriminant Analysis, LDA) 是一种监督学习的降维方法，也就是说数据集的每个样本是有类别输出。和之前介绍的机器学习降维之主成分分析(PCA)方法不同，PCA是不考虑样本类别输出的无监督学习方法。LDA的原理简单来说就是将带上标签的数据（点），通过投影的方法，投影到维度更低的空间中，使得投影后的点会形成按类别区分。而我们的目标就是使得投影后的数据，类间方差最大，类内方差最小。

以下图为例，假设有两类数据，分别为红色和蓝色。现在我们希望，将这些数据投影到一维的直线上，让每一种类别数据的投影点尽可能的接近，而红色和蓝色数据中心之间的距离尽可能的大。
机器学习降维之线性判别模型(LDA)
从上图的两种投影方式能够看出，右图能够更好的满足我们的目标，即类间方差最大，类内方差最小。下面我们来看看LDA内部原理，如何达到我们所希望的目标。

2.瑞利商和广义瑞利商

介绍LDA原理之前，我们先了解一些数学知识，即瑞利商(Rayleigh quotient)与广义瑞利商(genralized Rayleigh quotient)。首先来看看瑞利商的函数R(A,x)
R(A,x)=xHAxxHx R(A,x) = \frac{x^HAx}{x^Hx}
其中x为非零向量，而A为n*n的Hermitan矩阵。Hermitan矩阵是指满足共轭转置矩阵和自己相等的矩阵，即AH=AA^H=A。如果矩阵A是实矩阵的话，如果满足AT=AA^T=A，那么就是Hermitan矩阵。

瑞利商R(A,x)有一个非常重要的性质，即它的最大值等于矩阵A的最大特征值，而最小值等于矩阵A的最小特征值，即满足

λmin≤xHAxxHx≤λmax \lambda_{min}\le \frac{x^HAx}{x^Hx}\le \lambda_{max}

以上就是瑞利商的内容，现在看看广义瑞利商内容，广义瑞利商函数R(A,B,x)
R(A,B,x)=xHAxxHBx R(A,B,x)= \frac{x^HAx}{x^HBx}
其中x为非零向量，而A,B为n*n的Hermitan矩阵，B是正定矩阵。那么R(A,B,x)的最大值和最小值是什么呢？

首先我们先将广义瑞利商转化为瑞利商的情况，令x=B−1/2x′​x=B^{-1/2}x'​。则其分母变为
xHBx=x′H(B−1/2)HBB−1/2x′=x′HB−1/2BB−1/2x′=x′Hx′ x^HBx = x^{'H}(B^{-1/2})^HBB^{-1/2}x' \\ = x^{'H}B^{-1/2}BB^{-1/2}x' \\ =x^{'H}x'
分子转化为
xHAx=x′HB−1/2AB−1/2x′ x^HAx= x^{'H}B^{-1/2}AB^{-1/2}x'
此时R(A,B,x)转变为R(A,B,x′)
R(A,B,x′)=x′HB−1/2AB−1/2x′x′Hx′ R(A,B,x')=\frac{x^{'H}B^{-1/2}AB^{-1/2}x'}{x^{'H}x'}
利用前面的瑞利商性质，我们可以知道，R(A,B,x)的最大值为矩阵B−1/2AB−1/2B^{-1/2}AB^{-1/2}的最大特征值，或者说矩阵B−1AB^{-1}A的最大特征值，最小值为B−1AB^{- 1}A的最小特征值。

3.二类LDA原理

假如我们数据集为D={(x1,y1),(x2,y2),...,(xm,ym)}D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m) \}，其中任意样本xix_i为n维向量，yi∈{0,1}y_i \in \{0,1 \}。我们定义Nj(j=0,1)N_j(j=0, 1)为第j类样本的个数，Xj(j=0,1)X_j(j=0,1)为第j类样本的结合，μj(j=0,1)\mu_j(j=0,1)为第j类样本的均值向量，∑j(j=0,1)\sum_j(j=0, 1)为第j类样本的协方差矩阵(严格来说是缺少分母部分的协方差矩阵)。其中
μj=1Nj∑x∈Xj x(j=0,1) \mu_j = \frac{1}{N_j}\sum_{x\in X_j}\ x(j=0,1)

∑j=∑x∈Xj(x−μj)(x−μj)T (j=0,1) \sum_j = \sum_{x\in X_j}(x-\mu_j)(x-\mu_j)^T\ (j=0,1)

由于是两类数据，因此我们只需要将数据投影到一条直线上即可。假设我们的投影直线向量为ww，则对于任意一个样本xix_i，它在直线w的投影为wTxiw^Tx_i。对于我们两个类别的中心点μ0,μ1\mu_0,\mu_1来说，在直线ww的投影为wTμ0,wTμ1w^T\mu_0,w^T\mu_1。

由于LDA需要让不同类别数据的中心之间距离尽可能的大，也就是要最大化∣∣wTμ0−wTμ1∣∣​||w^T\mu_0-w^T\mu_1||​。同时需要让同一类别数据的投影点尽可能的接近，也就是要最小化wT∑0w+wT∑1w​w^T\sum_0w+w^T\sum_1w​。因此，我们的优化目标变为
argmax⁡⎵wJ(w)=∣∣wTμ0−wTμ1∣∣22wT∑0w+wT∑1w=wT(μ0−μ1)(μ0−μ1)TwwT(∑0+∑1)w \underbrace{arg \max}_w J(w) = \frac{||w^T\mu_0-w^T\mu_1||_2^2}{w^T\sum_0w+w^T\sum_1w}=\frac{w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw}{w^T(\sum_0+\sum_1)w}
同时，定义类内散度矩阵SwS_w为
Sw=∑0+∑1=∑x∈X0(x−μ0)(x−μ0)T+∑x∈X1(x−μ1)(x−μ1)T S_w=\sum_0+\sum_1=\sum_{x\in X_0}(x-\mu_0)(x-\mu_0)^T + \sum_{x\in X_1}(x-\mu_1)(x-\mu_1)^T
定义类间散度矩阵SbS_b为
Sb=(μ0−μ1)(μ0−μ1)T S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T
这样我们的优化目标变为
argmax⁡⎵wJ(w)=wTSbwwTSww \underbrace{arg \max}_w J(w) = \frac{w^TS_bw}{w^TS_ww}
上述形式便是我们第二节介绍到的广义瑞利商，利用第二节介绍的广义瑞利商的性质，能够得到J(w)J(w)的最大值为Sw−1/2SbSw−1/2S_w^{-1/2}S_bS_w^{-1/2}的最大特征值，而对应的ww为Sw−1/2SbSw−1/2S_w^{-1/2}S_bS_w^{-1/2}的最大特征值所对应的特征向量。

Sw−1SbS_w^{-1}S_b的特征值和Sw−1/2SbSw−1/2S_w^{-1/2}S_bS_w ^{-1/2}的特征值相同，Sw−1SbS_w^{-1}S_b的特征向量w′w'和Sw−1/2SbSw−1/2S_w ^{-1/2}S_bS_w ^{-1/2}的特征向量满足w′=Sw−1/2ww'=S_w^{-1/2}w的关系。注意到对于二类的时候
Sbw′=(μ0−μ1)(μ0−μ1)Tw′=(μ0−μ1)(w′T(μ0−μ1))T S_bw' = (\mu_0-\mu_1)(\mu_0-\mu_1)^Tw'=(\mu_0-\mu_1)(w'^T(\mu_0-\mu_1))^T
即Sbw′S_bw'的方向恒为μ0−μ1\mu_0-\mu_1，因此令Sbw′=λ(μ0−μ1)S_bw'=\lambda(\mu_0-\mu_1)，将其带入(Sw−1Sb)w′=λw′(S_w^{-1}S_b)w' = \lambda w'
(Sw−1Sb)w′=Sw−1λ(μ0−μ1)=λw′ (S_w^{-1}S_b)w' = S_w^{-1}\lambda (\mu_0-\mu_1)= \lambda w'

w′=Sw−1(μ0−μ1) w'=S_w^{-1}(\mu_0-\mu_1)

也就是说，我们只要求出原始二类样本的均值和方差就可以确定最佳的投影方向w了。

4.多类LDA原理

假如我们数据集为D={(x1,y1),(x2,y2),...,(xm,ym)}D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m) \}，其中任意样本xix_i为n维向量，yi∈{C1,C2,...,Ck}y_i \in \{C_1,C_2,...,C_k \}。我们定义Nj(j=1,2,...,k)N_j(j=1,2,...,k)为第j类样本的个数，Xj(j=1,2,...,k)X_j(j=1,2,...,k)为第j类样本的结合，μj(j=1,2,...,k)\mu_j(j=1,2,...,k)为第j类样本的均值向量，∑j(j=1,2,...,k)​\sum_j(j=1,2,...,k)​为第j类样本的协方差矩阵。

由于是多维向低维投影，此时得到的低位空间就不是一条直线，而是一个超平面。假设投影后得到的低维空间维度为d，对应的基向量为(w1,w2,...,wd)​(w_1,w_2,...,w_d)​，基向量组成的矩阵为W，是一个n*d的矩阵。

此时我们的优化目标变为
WTSbWWTSwW \frac{W^TS_bW}{W^TS_wW}
其中Sb=∑j=1kNj(μj−μ)(μj−μ)TS_b=\sum_{j=1}^kN_j(\mu_j-\mu)(\mu_j-\mu)^T，μ\mu为所有样本的均值向量。Sw=∑j=1kSwj=∑j=1k∑x∈Xj(x−μj)(x−μj)TS_w=\sum_{j=1}^kS_{wj}=\sum_{j=1}^k\sum_{x\in X_j}(x-\mu_j)(x-\mu_j)^T。但是有一个问题，WTSbWW^TS_bW和WTSwW​W^TS_wW​都是矩阵，不是标量，无法作为一个标量函数来进行优化，怎么办呢。

常见的一个LDA多类优化目标函数定义如下所示，其中∏diagA​\prod_{diag}A​为A的主对角线元素的乘积，W为n*d的矩阵。
argmax⁡⎵wJ(w)=∏diagWTSbW∏diagWTSwW \underbrace{arg \max}_w J(w) = \frac{\prod_{diag}W^TS_bW}{\prod_{diag}W^TS_wW}
J(W)的优化过程可以转化为
J(W)=∏i=1dwiTSbwi∏i=1dwiTSwwi=∏i=1dwiTSbwiwiTSwwi J(W)=\frac{\prod_{i=1}^dw_i^TS_bw_i}{\prod_{i=1}^dw_i^TS_ww_i}= \prod_{i=1}^d\frac{w_i^TS_bw_i}{w_i^TS_ww_i}
上述便是我们前面所介绍的广义瑞利商，最大值便是矩阵Sw−1Sb​S_w^{-1}S_b​的最大特征值，最大的d个值的乘积就是矩阵Sw−1Sb​S_w^{-1}S_b​的最大的d个特征值的乘积，此时对应的矩阵W为这最大的d个特征值对应的特征向量张成的矩阵。

由于W是利用了样本的类别得到的投影矩阵，因此它的降维到的维度d最大值为k-1。为什么最大维数不是类别数k呢？因为Sb​S_b​中每个μj−μ​\mu_j-\mu​的秩为1，因此协方差矩阵相加后最大的秩为k(矩阵的秩小于等于各个相加矩阵的秩的和)，但是由于如果我们知道前k-1个μj​\mu_j​后，最后一个μk​\mu_k​可以由前k-1个μj​\mu_j​线性表示，因此Sb​S_b​的秩最大为k-1，即特征向量最多有k-1个。

5.LDA算法流程

输入：数据集D={(x1,y1),(x2,y2),...,(xm,ym)}​D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m) \}​，其中任意样本xi​x_i​为n维向量，yi∈{C1,C2,...,Ck}​y_i\in \{C_1,C_2,...,C_k \}​，降维到的维度d。

输出：降维后的样本集D′​D'​

算法过程：

  • 计算类内散度矩阵SwS_w。
  • 计算类内散度矩阵SbS_b。
  • 计算矩阵Sw−1Sb​S_w^{-1}S_b​。
  • 计算Sw−1SbS_w^{-1}S_b的最大的d个特征值和对应的d个特征向量w1,w2,...,wdw_1,w_2,...,w_d，得到投影矩阵W。
  • 对样本集中每一个样本特征xix_i，计算得到新样本zi=WTxiz_i=W^Tx_i。
  • 得到输出样本集D′={(z1,y1),(z2,y2),...,(zm,ym)}D'=\{(z_1,y_1),(z_2,y_2),...,(z_m,y_m) \}。

6.LDA vs PCA

LDA和PCA有很多相同点和不同点，我们来对比看看两者的区别。

相同点

  • 两者均可对数据进行降维。
  • 两者在降维时均使用了矩阵特征分解的思想。
  • 两者都假设数据符合高斯分布。

不同点

  • LDA是有监督的降维方法，而PCA是无监督的降维方法。
  • LDA降维最多降到类别数k-1的维数，而PCA无此限制。
  • LDA选择分类性能最好的投影方向，而PCA选择样本点投影具有最大方差的方向。

不同数据情况下，LDA和PCA降维方法各有优劣。例如某些数据情况下LDA比PCA方法更好
机器学习降维之线性判别模型(LDA)

某些数据情况下PCA比LDA方法降维更好
机器学习降维之线性判别模型(LDA)

7.LDA算法总结

LDA优点

  • 在降维过程中可以使用类别的先验知识经验，而PCA这种无监督学习则无法使用类别先验知识。

LDA缺点

  • LDA可能过度拟合数据。

  • LDA不适合对非高斯分布样本进行降维，PCA也有这个问题。

  • LDA降维最多降到类别数k-1的维数，如果我们降维的维数大于k-1，则不能使用LDA。

8.推广

更多内容请关注公众号谓之小一，若有疑问可在公众号后台提问，随时回答，欢迎关注，内容转载请注明出处。
机器学习降维之线性判别模型(LDA)

相关推荐