分类问题也可以用降维来理解，比如一个D维的数据点x，我们可以采用下面的映射进行线性的降维，

 

y=θTx

 

在计算出y后，就可以选择一个阈值h,来进行分类。正如我们在前面的PCA模型中看到的，降维会有信息的损失，可能会在降维过程中，丢失使数据可分的特征，导致分类的效果不理想。

 

那采用什么样的降维方式，可以尽量的在低维空间中保存原来数据在高维空间中的可分性（区分类别的特征）。一个常用的模型 linear discriminant analysis(LDA)就是用来做这个工作的，下面就具体的看一下LDA模型。

原理

LDA的基本原理就是最大化类间方差（between-class variance）和类内方差（within-class variance）的比率（注意这个variance用来理解，下面用到的定义实际上是variance的一个变形），使得降维后数据有最好的可分性。如果偷用软件工程里面用的术语的话，就是“高内聚，低耦合”，类内的数据内聚，方差小，而类间数据松散，方差大。通常来说，这要比只考虑类间的距离越大要好，如下图所示：

左边图只是考虑最大化每个类期望的最大距离，我们看到有很多点投影后重合了，丧失了标签信息；而右边是LDA投影，重合的点的数目减少了很多，能更好的保存标签信息。

模型

下面我们就来形式化这个过程，首先如何定义between-class variance和within-class variance？在Fisher提出的方法中，没有使用统计中标准的variance的定义，而是使用了一个称为scatter的概念，与variance时等价的，使用这个概念可能是为了后面的推导简洁。设数据集为X=x1,x2,..,xN，则scatter的定义为：

 

s=∑n=1N(xn−m)T(xn−m)

 

其中，m=1N∑Nn=1xn。

类内方差很容易形式化，可以直接使用scatter来定义，然后把所有类别的scatter连加；那么类间的方差如何定义才能很好的让类之间的数据分的更开呢？当然应该有很多的数学关系很描述，在LDA中使用了下面这种方式，计算每个类别的期望，求期望之间的距离。先从简单的两类情况开始，然后拓展到多类的情况。

两类

设数据集合为X={

x1,x2,..,xN},类别为C1,C2,则这两类的数据期望为m1,m2，计算公式如：

 

mk=1Nk∑i∈Ckxi

 

mk表示投影后的数据点的期望，则between-class variance的形式化定义为：

 

m2−m1=θT(m2−m1)

 

其中，mk=θTmk。within-class variance用within-scatter这个定义来表示，scatter是variance的变种（不用除以数据的数目），第Ck类的scatter定义为：

 

S2k=∑i∈Ck(yi−mi)2

 

其中，yi=θTxi。这样就可以得到目标函数：

 

J(θ)=(m2−m1)2s21+s22

 

将上面的定义代入上式，可以得到式子:

 

maxargθJ(θ)=θTSBθθTSWθ

 

其中，SB,SW分别称为between-class scatter和within-class scatter，表示如下：

 

SB=(m2−m1)(m2−m1)T;SW=S1+S2

 

其中,Sk=∑i∈Ck(xi−mk)(xi−mk)T。下面要做的就是最优化目标函数(x−mk),对上面的式子求导数，让导数为0，则可以得到：

 

(θTSBθ)SWθ=(θTSWθ)SBθ

 

由于投影操作，我们只关心θ的方向，上面的式子，可以去掉(θTSBθ),(θTSWθ),根据SB的定义，SBθ的方向与(m2−m1)一致，我们可以得到：

 

θ∗∝S−1W(m2−m1)

 

这个式子称为Fisher’s linear discriminant[1936],尽管这个式子不是一个判别式，只是选择了投影方向,不过只要我们选择一个阈值，然后就可以根据这个阈值进行分类了。(ps:使用求解generalized eigenvalue problem的方法求解导数为零的等式，也可以得到这个判别式)

多类

在多类问题时，将D维的向量x投影到M<D维的y,投影矩阵方程为：

 

y=ΘTx

 

可以参照PCA文章中提到投影公式，这里Θ是一个投影矩阵，每一个列向量表示一个投影方向Θk。

设数据集合为X={

x1,x2,..,xN},类别为C1,C2,..,CK。在多类的时候，过程与上面一样，不过由于between-class scatter 和within-class scatter不再是标量，需要更改一下我们需要优化的目标函数。首先看一下在原空间x的定义，然后就可以类比到y空间。

withinin-class scatter 与二类时的定义一样，如下表示:

 

SW=∑k=1K∑i∈Ck(xi−mk)(xi−mk)T

 

mk定义与上面一致。

between-class scatter的定义，这里我们根据PRML里面论述的，首先定义一个ST，然后根据ST=SB+SW，然后分解得到SB。ST的定义类似Sk，不过不在一个类别，而是在所有的数据集上进行计算。

 

ST=∑n=1N(xn−m)(xn−m)Tm=1N∑n=1Nxn=1N∑k=1KNkmk

 

所以得到：

 

SB=======ST−SW∑n=1N(xn−m)(xn−m)T−∑k=1K∑i∈Ck(xi−mk)(xi−mk)T∑k=1K∑i∈Ck(xi−m)(xi−m)T−∑k=1K∑i∈Ck(xi−mk)(xi−mk)T∑k=1K∑i∈Ck{

(xi−m)(xi−m)T−