线性判别分析 LDA (Linear Discriminant Analysis) 又称为 Fisher 线性判别,是一种监督学习的降维技术,也就是说它的数据集的每个样本都是有类别输出的,这点与 PCA(无监督学习)不同。LDA 在模式识别领域(比如人脸识别,舰艇识别等图形图像识别领域)中有非常广泛的应用,因此我们有必要了解下它的算法原理。

1. LDA 的思想

LDA 的思想是:最大化类间均值,最小化类内方差。意思就是将数据投影在低维度上,并且投影后同种类别数据的投影点尽可能的接近,不同类别数据的投影点的中心点尽可能的远。

我们先看看最简单的情况。假设我们有两类数据 分别为红色和蓝色,如下图所示,这些数据特征是二维的,我们希望将这些数据投影到一维的一条直线,让每一种类别数据的投影点尽可能的接近,而红色和蓝色数据中心之间的距离尽可能的大。

上图提供了两种投影方式,哪一种能更好的满足我们的标准呢?从直观上可以看出,右图要比左图的投影效果好,因为右图的黑色数据和蓝色数据各个较为集中,且类别之间的距离明显。左图则在边界处数据混杂。以上就是 LDA 的主要思想了,当然在实际应用中,我们的数据是多个类别的,我们的原始数据一般也是超过二维的,投影后的也一般不是直线,而是一个低维的超平面。

2. 瑞利商 与 广义瑞利商

首先来看瑞利商的定义。瑞利商是指这样的函数 R(A,x)R(A,x) :

R(A,x)=xHAxxHxR(A, x)=\frac{x^{H} A x}{x^{H} x}

其中, xx 是非零向量,而 AAn×nn \times nHermitan 矩阵。所谓 Hermitan 矩阵就是 共轭转置矩阵 和自己相等的矩阵,即 AH=AA^H=A ,例如, A=(12+i2i1)A=\left(\begin{array}{cc}{1} & {2+i} \\ {2-i} & {1}\end{array}\right) 的共轭转置等于其本身。当 AA 为实矩阵时,如果满足 AT=AA^T=A ,则 AA 为 Hermitan 矩阵。

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

λminxHAxxHxλmax\lambda_{\min } \leq \frac{x^{H} A x}{x^{H} x} \leq \lambda_{\max }

当向量 xx 是标准正交基,即满足 xHx=1x^{H} x=1 时,瑞利商退化为 R(A,x)=xHAxR(A, x)=x^{H} A x

下面看一下广义瑞利商。广义瑞利商是指这样的函数 R(A,B,x)R(A,B,x) :

R(A,B,x)=xHAxxHBxR(A,B, x)=\frac{x^{H} A x}{x^{H} B x}

其中 xx 为非零向量,而 A,BA,Bn×nn \times n 的 Hermitan 矩阵。 BB 为正定矩阵。它的最大值和最小值是什么呢?其实我们只要将其通过标准化就可以转化为瑞利商的格式。

x=B1/2xx=B^{-1 / 2} x^{\prime} ,则分母转化为:

xHBx=xH(B1/2)HBB1/2x=xHB1/2BB1/2x=xHxx^{H} Bx=x^{\prime H}\left(B^{-1 / 2}\right)^{H} B B^{-1 / 2} x^{\prime}=x^{\prime H} B^{-1 / 2} B B^{-1 / 2} x^{\prime}=x^{\prime H} x^{\prime}

而分子转化为:

xHAx=xHB1/2AB1/2xx^{H} A x=x^{\prime H} B^{-1 / 2} A B^{-1 / 2} x^{\prime}

此时我们的 R(A,B,x)R(A,B,x) 转化为 R(A,B,x)R(A,B,x') :

R(A,B,x)=xHB1/2AB1/2xxHxR\left(A, B, x^{\prime}\right)=\frac{x^{\prime H} B^{-1 / 2} A B^{-1 / 2} x^{\prime}}{x^{\prime H} x^{\prime}}

利用前面的瑞利商的性质,我们可以很快的知道, R(A,B,x)R(A,B,x') 的最大值为矩阵 B1/2AB1/2B^{-1 / 2} A B^{-1 / 2} 的最大特征值,或者说矩阵 B1AB^{−1}A 的最大特征值,而最小值为矩阵 B1AB^{−1}A 的最小特征值。

3. LDA 的原理及推导过程

假设样本共有 KK 类,每一个类的样本的个数分别为 N1,N2,...,NkN_1,N_2,...,N_k

x11,x12,...,x1N1x_1^1,x_1^2,...,x_1^{N_1} 对应第 1 类

x21,x22,...,x2N2x_2^1,x_2^2,...,x_2^{N_2} 对应第 2 类

xk1,xk2,...,xkNkx_k^1,x_k^2,...,x_k^{N_k} 对应第 KK 类,其中每个样本 xijx_i^j 均为 nn 维向量

x~ij\tilde{x}_{i}^{j}xijx_i^j 变化后的样本,则

x~ij=<x,u>u=xucosθu=(xTu)u\tilde{x}_{i}^{j}= <x, u>u=|x||u|cos \theta \cdot u =\left(x^{T} u\right)u

此处设 uu 为单位向量,即 uTu=1u^Tu=1 .

假设第 KK 类样本的数据集为 DkD_k ,变化后的样本的均值向量为: m~=x~Dkx~Nk\tilde{\mathrm{m}}=\frac{\sum_{\tilde{x}\in D_k}\tilde{x}}{N_k} ,那么,第 KK 类样本的方差定义为 SkNk\frac{S_k}{N_k} ,由于:

Sk=x~Dk(x~m~)T(x~m~)=xDk[(xTu)u(mTu)u]T[(xTu)u(mTu)u]=xDk[(xTu)uT(mTu)uT][(xTu)u(mTu)u]=xDk[(xTu)2uTu2(xTu)(mTu)uTu+(mTu)2uTu]=xDk[(xTu)22(xTu)(mTu)+(mTu)2]\begin{aligned} \mathrm{S}_{\mathrm{k}} &=\sum_{\tilde{x} \in D_{k}}(\tilde{x}-\tilde{\mathrm{m}})^{T}(\tilde{x}-\tilde{\mathrm{m}})\\ &=\sum_{x \in D_{k}} [\left(x^{T} u\right) u-\left(m^{T} u\right) u]^T [\left(x^{T} u\right) u -\left(m^{T} u\right) u] \\ &=\sum_{x \in D_{k}} [\left(x^{T} u\right) u^{T}-\left(m^{T} u\right) u^{T}] [\left(x^{T} u\right) u -\left(m^{T} u\right) u] \\ &=\sum_{x \in D_{k}} \left[ \left(x^{T} u\right)^{2} u^{T} u-2 \left(x^{T} u\right) \left(m^{T} u\right) u^{T} u + \left(m^{T} u\right)^{2} u^{T} u \right] \\ &=\sum_{x \in D_{k}} \left[\left(x^{T} u\right)^{2}-2\left(x^{T} u\right)\left(m^{T} u\right)+\left(m^{T} u\right)^{2}\right] \end{aligned}

(x^Tu,m^Tu 为实数,转置仍是本身)
因此,第 KK 类样本的方差可以改写为:

SkNk=xDk(xTu)2Nk2xDkxT(umTu)Nk+xDk(mTu)2Nk=xDkuTxxTuNk2xDkxTNkumTu+(mTu)2(注:xDk(mTu)2Nk=(mTu)2。因为mTux无关)=uTxDkxxTNku(mTu)2(注:xDkxTNk=mT=uTxDkxxTNkuuTmmTu=uT(xDkxxTNkmmT)u\begin{aligned} \frac{S_{k}}{N_{k}} &=\frac{\sum_{x \in D_{k}}\left(x^{T} u\right)^{2}}{N_{k}}-2 \frac{\sum_{x \in D_{k}} x^{T}\left(u m^{T} u\right)}{N_{k}}+\frac{\sum_{x\in D_{k}}\left(m^{T} u\right)^{2}}{N_{k}} \\ &=\frac{\sum_{x\in D_k} u^{T} x x^{T} u}{N_{k}}-2 \frac{\sum_{x\in D_k} x^{T}}{N_{k}} u m^{T} u+\left(m^{T} u\right)^{2}\quad (注:\frac{\sum_{x\in D_{k}}\left(m^{T} u\right)^{2}}{N_{k}}=(m^Tu)^2。因为 m^Tu 与 x 无关)\\ &=u^{T} \frac{\sum_{x\in D_k} x x^{T}}{N_{k}} u-\left(m^{T} u\right)^{2} \quad (注:\frac{\sum_{x \in D_k}x^T}{N_k}=m^T)\\ &=u^{T} \frac{\sum_{x\in D_k} x x^{T}}{N_{k}} u-u^{T} m m^{T} u \\ &=u^{T}\left(\frac{\sum_{x\in D_k} x x^{T}}{N_{k}}-m m^{T}\right) u \end{aligned}

所有类别的样本方差之和:

kSkNk=k=1KuT(xDkxxTNkmkmkT)u=uTk=1K(xDkxxTNkmkmkT)u=uTSwu\begin{aligned} \sum_{k}\frac{S_k}{N_k} &=\sum_{k=1}^{K}u^{T}\left(\frac{\sum_{x \in D_k} x x^{T}}{N_{k}}-m_k m_k^{T}\right) u \\ &=u^T\sum_{k=1}^{K}(\frac{\sum_{x \in D_k}xx^T}{N_k}-m_km_k^T)u\\ &=u^TS_wu \end{aligned}

其中, Sw=k=1K(xDkxxTNkmkmkT)S_w=\sum_{k=1}^{K}(\frac{\sum_{x \in D_k}xx^T}{N_k}-m_km_k^T)SwS_w 一般被称为类内散度矩阵

不同类别 i,ji,j 之间的中心距离:

Sij=(m~im~j)T(m~im~j)=[(uTmi)u(uTmj)u]T[(miTu)u(mjTu)u]=[(uTmi)uT(uTmj)uT][u(miTu)u(mjTu)]=uT(mimj)uTu(miTmjT)u=uT(mimj)(mimj)Tu\begin{aligned} S_{i j} &=\left(\tilde{m}_{i}-\tilde{m}_{j}\right)^{T}\left(\tilde{m}_{i}-\tilde{m}_{j}\right) \\ &=[(u^Tm_i)u-(u^Tm_j)u]^T[(m_i^Tu)u-(m_j^Tu)u] \\ &=[(u^Tm_i)u^T-(u^Tm_j)u^T][u(m_i^Tu)-u(m_j^Tu)] \\ &=u^T(m_i-m_j)u^Tu(m_i^T-m_j^T)u \\ &=u^{T}\left(m_{i}-m_{j}\right)\left(m_{i}-m_{j}\right)^{T} u \end{aligned}

所有类别之间的距离之和为:

i,jijsij=uTi,jij[(mimj)(mimj)T]u=uTSbu\begin{aligned} \sum_{i, j \atop i \neq j} s_{i j} &= u^T\sum_{i, j \atop i \neq j}[(m_i-m_j)(m_i-m_j)^T]u \\ &=u^TS_bu \end{aligned}

其中,Sb=i,jij[(mimj)(mimj)T]S_b=\sum_{i, j \atop i \neq j}[(m_i-m_j)(m_i-m_j)^T]SbS_b 一般被称为类间散度矩阵。

在已知条件下, Sw,SbS_w,S_b 均可求出。根据 LDA 算法的目标,即 类间距离尽可能大,类内方差尽可能小,我们需要求最大化 uTSbuu^TS_bu , 最小化 uTSwuu^TS_wu的解。

J(u)=uTSbuuTSwuJ(u)=\frac{u^{T} S_{b} u}{u^{T} S_{w} u} ,则目标函数为:

maxJ(u)\max J(u)

为了使所求最大,可假设 uTSwu=1u^TS_wu=1 ,则问题转化为:

maxuTSbus.t.uTSwu=1\begin{array}{l} {\max u^{T} S_{b} u} \\ s.t. \quad u^TS_wu=1 \end{array}

\begin{aligned} L(u, \lambda)&=u^{T} S_{b} u+\lambda\left(1-u^{T} S_{w} u\right) \\ \frac{\partial L}{\partial u} &= S_bu+S_b^Tu-\lambda S_wu-\lambda S_w^Tu \\ &=2(S_bu-\lambda S_wu)\quad \text{(因为 S_b,S_w 为对称矩阵)}\\ &=0 \Rightarrow S_{b} u=\lambda S_{w} u \end{aligned}

证明 SbS_b 为对称矩阵:

SbT=(i,jij[(mimj)(mimj)T])T=i,jij[(mimj)(mimj)T]T=i,jij[(mimj)(mimj)T]=Sb\begin{aligned} S_b^T &= (\sum_{i, j \atop i \neq j}[(m_i-m_j)(m_i-m_j)^T])^T\\ &=\sum_{i, j \atop i \neq j}[(m_i-m_j)(m_i-m_j)^T]^T \\ &=\sum_{i, j \atop i \neq j}[(m_i-m_j)(m_i-m_j)^T] \\ &=S_b \end{aligned}

所以, SbS_b 为对称矩阵,同理可证明 SwS_w 为对称矩阵。

Sw1Sbu=λu\begin{array}{l} S_{w}^{-1}{S_{b} u=\lambda u} \end{array}

计算矩阵 Sw1SbS_w^{-1}S_b 的最大的 dd 个特征值和对应的 dd 个特征向量 (w1,w2,...,wd)(w_1,w_2,...,w_d) ,可以得到投影矩阵 W=(w1,w2,...,wd)W=(w_1,w_2,...,w_d)

注意:

(1) 选取特征值时,如果一些特征值明显大于其他的特征值,则取这些取值较大的特征值,因为它们包含更多的数据分布的信息。相反,如果一些特征值接近于 0,我们将这些特征值舍去。

(2)由于 WW 是一个利用了样本类别得到的投影矩阵,因此它能够降维到的维度 dd 的最大值为 K1K-1 。为什么不是 KK 呢?因为 SbS_b 中每个 mimjm_i-m_j 的秩均为 11(因为 mim_i11 维向量)。

R(AB)min(R(A),R(B))R(AB)\leq \min(R(A), R(B)) 可知:R((mimj)(mimj)T)=1R((m_i-m_j)(m_i-m_j)^T)=1

\because

Sb=i,jij[(mimj)(mimj)T],R(A+B)R(A)+R(B)S_b=\sum_{i, j \atop i \neq j}[(m_i-m_j)(m_i-m_j)^T], \\ R(A+B)\leq R(A)+R(B)

R(Sb)K1R(Sw1Sb)K1\therefore R(S_b)\leq K-1 \Rightarrow R(S_w^{-1}S_b)\leq K-1

λ=0\therefore \lambda =0 对应的特征向量至少有 (K(K1))=1(K-(K-1))=1 个,也就是说 dd 最大为 K1K-1

3. LDA 算法流程

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

输出:降维后的数据集 DD'

1)计算类内散度矩阵 SwS_w

2)计算类间散度矩阵 SbS_b

3)计算矩阵 Sw1SbS_w^{-1}S_b

4)计算矩阵 Sw1SbS_w^{-1}S_b 的特征值与特征向量,按从小到大的顺序选取前 dd 个特征值和对应的 dd 个特征向量 (w1,w2,...,wd)(w_1,w_2,...,w_d) ,得到投影矩阵 WW

5)对样本集中的每一个样本特征 xix_i ,转化为新的样本 zi=WTxiz_i=W^Tx_i

6)得到输出样本集 D={(z1,y1),(z2,y2),...,(zm,ym)}D'=\{(z_1,y_1),(z_2,y_2),...,(z_m,y_m)\}

4. LDA 与 PCA 对比

LDA 与 PCA 都可用于降维,因此有很多相同的地方,也有很多不同的地方

相同点:

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

不同点:

  • LDA 是有监督的降维方法,而 PCA 是无监督降维方法
  • 当总共有 KK 个类别时,LDA 最多降到 K1K-1 维,而 PCA 没有这个限制
  • LDA 除了用于降维,还可以用于分类
  • LCA 选择分类性能最好的投影方向,而 PCA 选择样本点投影具有最大方差的方向。这点可以从下图形象的看出,在某些数据分布下 LDA 比 PCA 降维较优(如下图的左图)。当然,某些数据分布下 PCA 比 LDA 降维较优(如下图的右图)。

5. LDA 算法小结

LDA 算法既可以用来降维,也可以用来分来,但是目前来说,LDA 主要用于降维,在进行与图像识别相关的数据分析时,LDA 是一个有力的工具。下面总结一下 LDA 算法的优缺点。

LDA 算法的优点

  • 在降维过程中可以使用类别的先验知识经验,而像 PCA 这样的无监督学习无法使用先验知识;
  • LDA 在样本分类信息依赖均值而不是方差的时候,比 PCA 算法较优。

LDA 算法的缺点

  • LDA 与 PCA 均不适合对非高斯分布样本进行降维
  • LDA 降维算法最多降到类别数 K1K-1 的维度,当降维的维度大于 K1K-1 时,则不能使用 LDA。当然目前有一些改进的 LDA 算法可以绕过这个问题
  • LDA 在样本分类信息依赖方差而非均值的时候,降维效果不好
  • LDA 可能过度拟合数据
    其中是一个函数,我们将调用反向链接函数。有许多反向链接函数可供选择;可能最简单的是恒等函数。这是一个返回与其参数相同的值的函数。第 3 章“线性回归建模”中的所有模型都使用了单位函数,为简单起见,我们只是省略了它。身份功能本身可能不是很有用,但它允许我们以更统一的方式考虑几种不同的模型。