算法思想

LDA是经典的有监督的降维方法。而我们的降维方法，一般都是将样本数据进行投射。LDA的思想就是将样本投射到一条直线上，使同类的样本点尽可能的接近，而异类的样本点尽可能的远离。如下图所示：

算法推导

假设我们的样本数据是D={(x1,y1),...,(xm,ym)}$D=\left\{(x_1,y_1),...,(x_m,y_m)\right\}$ 其中yi∈{0,1}$y_i\in \left\{0,1\right\}$

我们假设xi,μi,Σi$x_i,{\mu }_i,{\mathrm{\Sigma }}_i$分别为第i$i$类样本的集合，均值以及协方差矩阵。

我们将数据映射到w上，则两类样本的中心点在直线上的投影分别为wTμ0,wTμ1$w^T{\mu }_0,w^T{\mu }_1$

将所有的数据投射到w上，则两类样本的协方差分别为wTΣ0w,wTΣ1w$w^T{\mathrm{\Sigma }}_{0}w,w^T{\mathrm{\Sigma }}_{1}w$

根据LDA的思想：

同类的样本点尽可能的接近，而异类的样本点尽可能的远离

有：

式子wTΣ0w+wTΣ1w$w^T{\mathrm{\Sigma }}_{0}w+w^T{\mathrm{\Sigma }}_{1}w$要尽可能的小

式子||wTμ0−wTμ1||22$||w^T{\mu }_0-w^T{\mu }_1|{|}_2^2$要尽可能的大

因此我们的目标转化为最大化：

J=||wTμ0−wTμ1||22wTΣ0w+wTΣ1w=wT(μ0−μ1)(μ0−μ1)TwwT(Σ0+Σ1)w$J=\frac{||w^T{\mu }_0-w^T{\mu }_1|{|}_2^2}{w^T{\mathrm{\Sigma }}_{0}w+w^T{\mathrm{\Sigma }}_{1}w}=\frac{w^T({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^{T}w}{w^T({\mathrm{\Sigma }}_0+{\mathrm{\Sigma }}_1)w}$

我们可以定义类内散度矩阵：

Sw=Σ0+Σ1=∑x∈x0(x−μ0)(x−μ0)T+∑x∈x1(x−μ1)(x−μ1)T$S_w={\mathrm{\Sigma }}_0+{\mathrm{\Sigma }}_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$

类间散度矩阵：

Sb=(μ0−μ1)(μ0−μ1)T$S_b=({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^T$

所以优化目标变为：

J=||wTμ0−wTμ1||22wTΣ0w+wTΣ1w=wT(μ0−μ1)(μ0−μ1)TwwT(Σ0+Σ1)w=wTSbwwTSww$J=\frac{||w^T{\mu }_0-w^T{\mu }_1|{|}_2^2}{w^T{\mathrm{\Sigma }}_{0}w+w^T{\mathrm{\Sigma }}_{1}w}=\frac{w^T({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^{T}w}{w^T({\mathrm{\Sigma }}_0+{\mathrm{\Sigma }}_1)w}=\frac{w^T{S}_{b}w}{w^T{S}_{w}w}$

下面我们的目标就是如何确定w。

上面的式子与w的大小无关，因此问题可以转换为：

minw −wTSbw$mi{n}_w-w^T{S}_{b}w$

s.t.wTSww=1$s.t.w^T{S}_{w}w=1$

利用拉个朗日乘子法，有：

Sbw=λSww$S_{b}w=\lambda S_{w}w$

由于Sb=(μ0−μ1)(μ0−μ1)T$S_b=({\mu }_0-{\mu }_1)({\mu }_0-{\mu }_1{)}^T$，因此可以令：

Sb=λ(μ0−μ1)$S_b=\lambda ({\mu }_0-{\mu }_1)$

带如式子有：

w=S−1w(μ0−μ1)$w=S_w^{-1}({\mu }_0-{\mu }_1)$

对Sw$S_w$做奇异值分解：

Sw=UΣVT$S_w=U\mathrm{\Sigma }{V}^T$

所以有：

S−1w=VΣ−1UT$S_w^{-1}=V{\mathrm{\Sigma }}^{-1}{U}^T$

因此可以得到投影向量：

w=VΣ−1UT(μ0−μ1)$w=V{\mathrm{\Sigma }}^{-1}{U}^T({\mu }_0-{\mu }_1)$

多维场景

对于降维问题，如果降到多维的场景，可以如下处理：

SbW=λSwW$S_{b}W=\lambda S_{w}W$

有：

S−w1SbW=λW$S_w^{-}1S_{b}W=\lambda W$

因此只需要对S−w1Sb$S_w^{-}1S_b$做特征值分解，得到的最大的特征值对应的特征向量组成的矩阵就是多维的投影向量。

多分类场景

如果是多分类(假设为N$N$)问题，则只需要修改下式即可：

Sb=∑Ni=1mi(μ0−μi)(μ0−μi)T$S_b=\sum _{i=1}^N{m}_i({\mu }_0-{\mu }_i)({\mu }_0-{\mu }_i{)}^T$

其中mi$m_i$为第i$i$例样本的个数。

最后说一句

特征值分解或者奇异值分解无处不在啊。