特征选择(亦即降维)是数据预处理中非常重要的一个步骤。对于分类来说，特征选择可以从众多的特征中选择对分类最重要的那些特征，去除原数据中的噪音。主成分分析(PCA)与线性判别式分析(LDA)是两种最常用的特征选择算法。关于PCA的介绍，可以见我的 另一篇博文 。这里主要介绍线性判别式分析(LDA)，主要基于Fisher Discriminant Analysis with Kernals[1]和Fisher Linear Discriminant Analysis[2]两篇文献。
LDA与PCA的一大不同点在于，LDA是有监督的算法，而PCA是无监督的，因为PCA算法没有考虑数据的标签(类别)，只是把原数据映射到一些方差比较大的方向(基)上去而已。而LDA算法则考虑了数据的标签。文献[2]中举了一个非常形象的例子，说明了在有些情况下，PCA算法的性能很差，如下图：
我们用不同的颜色标注C1,C2两个不同类别的数据。根据PCA算法，数据应该映射到方差最大的那个方向，亦即Y轴方向，但是如果映射到Y轴方向，C1,C2两个不同类别的数据将完全混合在一起，很难区分开，所以使用PCA算法进行降维后再进行分类的效果会非常差。但是使用LDA算法，数据会映射到X轴方向。
LDA算法会考虑到数据的类别属性，给定两个类别C1、C2，我们希望找到一个向量ω,当数据映射到ω的方向上时，来自两个类的数据尽可能的分开，同一个类内的数据尽可能的紧凑。数据的映射公式为：z=ω T x, 其中z是数据x到ω上的投影，因而也是一个d维到1维的维度归约。
令
m
1
和m
1
分别表示C1类数据投影之前个投影之后的均值，易知m
1
=ω
T
m
1,
同理m
2
=ω
T
m
2
令s 1 2 和s 2 2 分别表示C1和C2类数据在投影之后的散布(scatter)，亦即s 1 2 = ∑ (ω T x t -m1) 2 r t ，s 2 2 =∑(ω T x t -m2) 2 （1-r t ）其中如果x t ∈C1,则r t =1，否则r t =0。
我们希望|m 1 -m 2 |尽可能的大，而s 1 2 +s 2 2 尽可能的小， Fisher线性判别式 就是最大化下面式子的ω：
J(ω)=(m 1 -m 2 ) 2 /(s 1 2 +s 2 2 ) 式子-1
改写式子-1中的分子： (m 1 -m 2 ) 2 = (ω T m 1 -ω T m 2 ) 2 =ω T ( m 1 - m 2 )( m 1 - m 2 ) T ω=ω T S B ω
其中 S B =( m 1 - m 2 )( m 1 - m 2 ) T 式子-2
是 类间散布矩阵 (between class scatter matrix)。
改写式子-1中的分母：
∑(ω T x t -m1) 2 r t =∑ω T (x t - m 1 )(x t - m 1 ) T ωr t =ω T S 1 ω, 其中 S 1 =∑r t (x t - m 1 )(x t - m 1 ) T 是C1的 类内散布矩阵 (within class scatter matrix)。
令 S W = S 1 + S 2 ，是 类内散布的总和 ，则s 1 2 +s 2 2 =ω T S W ω。
所以式子-1可以改写为：
J(ω)=(ω T S B ω)/(ω T S W ω) 式子-3
我们只需要使式子-3对于ω求导，然后使导数等于0，便可以求出ω的值：ω=c S W -1 ( m 1 - m 2 ),其中c是一个参数，我们只对ω的方向感兴趣，所以c可以取值为1.
另外，最后求得的 J(ω)的值等于λ
k
，λ
k
是
S
W
-1
S
B
的最大的特征值，而ω则是
S
W
-1
S
B
的最大特征值所对应的特征向量。
最后有一些关于LDA算法的讨论，出自文献[1]：
1. Fisher LDA对数据的分布做了一些很强的假设，比如每个类的数据都是高斯分布，各个类的协方差相等。虽然这些强假设很可能在实际数据中并不满足，但是Fisher LDA已经被证明是非常有效地降维算法，其中的原因是线性模型对于噪音的鲁棒性比较好，不容易过拟合，缺点是模型简单，表达能力不强，为了增强Fisher LDA算法的表达能力，可以引入核函数，参见我的另外一篇博客 机器学习-核Fisher LDA算法 。
2. 准确的估计数据的散布矩阵是非常重要的，很可能会有较大的偏置。用式子-2进行估计在样本数据比较少(相对于维数来说)时会产生较大的变异性。
参考文献：
[1] Fisher Discriminant Analysis with Kernals . Sebastian Mika, Gunnar Ratsch, Jason Weston, Bernhadr Scholkopf, Klaus-Robert Muller.
[2] Fisher Linear Discriminant Analysis . Max Welling.
[3] 机器学习导论。 Ethem Alpaydin
