第8章线性判别分析

主成分分析的目标是向量在低维空间中的投影能很好的近似代替原始向量，但这种投影对分类不一定合适。由于是无监督的学习，没有利用样本标签信息，不同类型样本的特征向量在这个空间中的投影可能很相近。本章要介绍的线性判别分析也是一种子空间投影技术，但是它的目的是用来做分类，让投影后的向量对于分类任务有很好的区分度。

8.1用投影进行分类

线性判别分析（Linear discriminant analysis，简称LDA）[1][2]的基本思想是通过线性投影来最小化同类样本间的差异，最大化不同类样本间的差异。具体做法是寻找一个向低维空间的投影矩阵W，样本的特征向量x经过投影之后得到新向量：

y Wx

=

同一类样本投影后的结果向量差异尽可能小，不同类的样本差异尽可能大。直观来看，就是经过这个投影之后同一类的样本尽量聚集在一起，不同类的样本尽可能离得远。下图8.1是这种投影的示意图：

图8.1最佳投影方向

上图中特征向量是二维的，我们向一维空间即直线投影，投影后这些点位于直线上。在上图中有两类样本，通过向右上方的直线投影，两类样本被有效的分开了。绿色的样本投影之后位于直线的下半部分，红色的样本投影之后位于直线的上半部分。由于是向一维空间投影，这相当于用一个向量w和特征向量x做内积，得到一个标量：

T

y=w x

8.2寻找投影矩阵

8.2.1一维的情况

问题的关键是如何找到最佳投影矩阵。下面先考虑最简单的情况，把向量映射到一维空间。假设有n 个样本，它们的特征向量为i x ，属于两个不同的类。属于类1C 的样本集为1D ，有1n 个样本；属于类2C 的样本集为2D ，有2n 个样本。有一个向量w ，所有向量对该向量做投影可以得到一个标量：

T y =w x

投影运算产生了n 个标量，分属于与1C 和2C 相对应的两个集合1Y 和2Y 。我们希望投影后两个类内部的各个样本差异最小化，类之间的差异最大化。类间差异可以用投影之后两类样本均值的差来衡量。投影之前每类样本的均值为：

x 1m i i D i n ∈=

∑x

投影后的均值为： T

T x 1m i i i D i n ∈==∑w x w m 它等价于样本均值在w 上的投影。投影后两类样本均值差的绝对值为：

()T 1212

-=-m m w m m 类内的差异大小可以用方差来衡量。定义类别i C 的类内散布为：

()2

2i i i y Y s y m

∈=-∑ 这是一个标量，和方差相差一个倍数，衡量了某一类的所有样本与该类中心的距离。()()

22121/n s s + 是全体样本的方差，2212s s + 称为总类内散布。我们要寻找的最佳投影需要使下面的目标函数最大化：

() ()2

122212m

m w L s s -=+ 即让类间的均值差最大化（分子），类内的差异最小化（分母）。为了把这个目标函数写成w 的函数，定义类内散布矩阵为：

()()

T

x S x m x m i i i i D ∈=

--∑总类内散布矩阵为：12S S S W =+

这样有：

()()()2

2T T x T

T x T w x w m w x m x m w w S w

i i i i D i i D i s

∈∈=-=--=∑∑ 因此各类的散布之和可以写成：

22T 12w S w

W s s += 各类样本的均值之差可以写成：

()()()()()22

T T T 12121212m m w m m w m m m m w -=-=--如果定义：

()()

T

1212S m m m m B =--则可以写成： ()2T 12m m w S w

B -=S B 称为总类间散布矩阵，S W 称为总类内散布矩阵。要优化的目标函数为：

()T T w S w w w S w

B W L =这个最优化问题的解不唯一，可以证明，如果w *

是最优解，将它乘上一个非零系数k 之后，w k *还是最优解。因此可以加上一个约束条件消掉冗余，同时简化问题：T w S w 1

W =这样上面的最优化问题转化为带等式约束的极大值问题：

T T max w S w

w S w 1

B W =下面用拉格朗日乘数法求解。构造拉格朗日乘子函数：

()()

T T ,w S w w S w 1B W L λλ=+-w 对w 求梯度并令梯度为0，可以得到：

S w S w 0

B W λ+=即：

S w S w

B W λ=如果S W 可逆，上式两边左乘1

S W -后可以得到：

1S S w w

W B λ-=即λ是矩阵1

S S W B -的特征值，w 为对应的特征向量。假设λ和w 是上面广义特征值问题的解，代入目标函数可以得到

()T T T T W B W W λλ==w S w w S w w S w w S w 这里的目标是要让该比值最大化，因此最大的特征值λ及其对应的特征向量是最优解。上面的做法只将样本向量投影到一维空间，并没有说明在这个空间中怎么分类。如果我们得到了投影后的值，一个方案是比较它离所有类的均值的距离，取最小的那个作为分类的结果： T arg min w x m

i i -这类似于kNN 算法，不同的是计算待分类样本和各类训练样本均值向量的距离。另外，也可以用其他分类器完成分类。

8.2.2推广到高维

接下来将上面的方法推广到多个类、向高维空间投影的情况。对于c 类分类问题，我们需要把特征向量投影到1c -维的空间中。类内散布矩阵定义为：

1

S S c W i i ==∑它仍然是每个类的类内散布矩阵之和，单个类的类内散布矩阵和之前的定义相同：

()()T

x S x m x m i i i i D ∈=

--∑其中m i 为每个类的均值向量。定义总体均值向量为：

11

11m x m n c i i i i i n n n ====∑∑定义总体散布矩阵为：

()()

T

1S x m x m n T i i i ==--∑则有：

()()

()()()()

()()

T 1x T T 1x 1x T 1S x m m m x m m m x m x m m m m m S m m m m i

i i

c T i i i i i D c c i i i i i D i D c

W i i i i n =∈=∈=∈==-+--+-=--+--=+--∑∑∑∑∑∑∑我们把上式右边的第二项定义为类间散布矩阵，总散布矩阵是类内散布矩阵和类间散布

矩阵之和：

()()

T

1S m m m m S S S c B i i i i T W B

n ==--=+∑相应的从d 维空间向1c -维空间投影变为矩阵和向量的乘积：

T y W x

=其中W 是()1d c ?-的矩阵。可以证明，最后的目标为求解下面的最优化问题：

()()

T T tr max tr B W W W S W

W S W 其中tr 为矩阵的迹。同样的这个问题存在冗余，加上约束条件消掉冗余，等价于优化下面的问题

()

T T max tr B W =W W S W W S W I

通过构造拉格朗日函数可以证明使该目标函数最大的W 的列w 必须满足：

S w S w

B W λ=最优解还是矩阵1

S S W B -的特征值和特征向量。实现时的关键步骤是计算矩阵S B ，S W 以及矩阵乘法1S S W B -，对矩阵1S S W B -进行特征值分解。矩阵1S S W B -可能有d 个特征值和特征向量，我们要将向量投影到1c -维，为此挑选出最大的1c -个特征值以及它们对应的特征向量，组成矩阵W 。

虽然最后都归结为求解矩阵的特征值问题，主成分分析和线性判别分析有本质的不同。前者是无监督的机器学习方法；而后者要计算类内和类间散度矩阵，使用了样本标签值，是有监督的机器学习方法。二者优化的目标也不同，前者是最小化重构误差，而后者是最大化类间差异同时最小化类内差异。从变换函数可以看出，线性判别分析也是一种判别模型。

计算投影矩阵的处理流程为：

1.计算各个类的均值向量与总均值向量。

2.计算类间散布矩阵S B ，类内散布矩阵S W 。

3.计算矩阵乘法1S S W B -。

4.对1S S W B -进行特征值分解，得到特征值和特征向量。

5.对特征值从大到小排序，截取部分特征值和特征向量构成投影矩阵。

得到投影矩阵W 之后，投影和重构算法与主成分分析相同，已经在第7.1.3和7.1.4节介绍。

8.3实验程序

下面通过实验程序介绍线性判别分析的使用。程序基于sklearn，使用iris数据集。这里将3类样本从4维空间投影到二维空间，根据样本类别显示成不同的颜色，方法与主成分分析相同。程序源代码如下

import matplotlib.pyplot as plt

from sklearn import datasets

from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

import matplotlib

%matplotlib inline

#载入iris数据集

iris=datasets.load_iris()

#特征向量为4维的

X=iris.data

#标签值用于将样本显示成不同的颜色

y=iris.target

target_names=iris.target_names

#创建LDA降维模型，并计算投影矩阵，对X执行降维操作，得到降维后的结果X_r lda=LinearDiscriminantAnalysis(n_components=2)

X_r=lda.fit(X,y).transform(X)

colors=['navy','turquoise','darkorange']

plt.figure()

#显示降维后的样本

for color,i,target_name in zip(colors,[0,1,2],target_names):

plt.scatter(X_r[y==i,0],X_r[y==i,1],alpha=.8,color=color,

label=target_name)

plt.legend(loc='best',shadow=False,scatterpoints=1)

plt.title('LDA of IRIS dataset')

plt.show()

程序运行结果如下图8.2所示。

图8.2LDA的对iris数据集的投影结果

8.4应用

线性判别分析被应用于模式识别中的各类问题，包括图像分类，人脸识别以及其他数据的分析。下面我们介绍在人脸识别中的应用。

子空间方法是人脸识别研究早期非常重要的一类方法，它将人脸图像作为一个向量投影到低维的子空间中然后进行分类。使用主成分分析的特征脸（Eigenfaces）和使用线性判别分析的Fisherfaces是这类方法的典型代表[3-5]。

使用主分量分析的人脸识别算法把人脸图像看作一个维向量，即将图像按行或者按列拼接起来。对人脸图像形成的向量进行主成分分解，得到投影矩阵，然后将训练样本向量投影到低维空间。在识别时，先对待识别图像进行主分量投影，然后在低维空间中计算待识别人脸图像与训练样本图像的距离，将其分到距离最近的那一类，即kNN算法。投影矩阵的每一行所代表的图像称为特征脸图像，如下图8.3所示：

图8.3特征脸图像

使用线性判别分析的人脸识别也是将人脸图像看做向量，然后对所有训练样本图像计算线性判别分析的投影矩阵，并将这些样本投影到子空间。接下来，在识别时将待识别图像也投影到LDA子空间，然后计算投影后的向量与训练样本投影向量的距离，将其分到距离最近的那个类中。我们只要将图像转换成向量，就可以直接使用前面的实验程序进行两个人的人脸识别，通过修改LDA投影空间的维数，很容易推广到多个人的识别。

在用线性判别分析进行人脸识别时，如果类内散布矩阵不可逆，这种方法将失效。有大量的文章研究此问题的解决方法，其中经典的做法是先对人脸图像进行主成分分析降维，然后再应用线性判别分析进行处理。

参考文献

[1]Ronald A.Fisher.The use of multiple measurements in taxonomic problems.Annals of Eugenics,7Part2:

179-188,1936.

[2]Geoffrey J.McLachlan.Discriminant Analysis and Statistical Pattern Recognition.Wiley,New York,

1992.

[3]Matthew Turk,Alex Pentland.Eigenfaces for recognition.Journal of Cognitive Neuroscience,1991.

[4]Peter N Belhumeur,J P Hespanha,David Kriegman.Eigenfaces vs.Fisherfaces:recognition using class

specific linear projection.IEEE Transactions on Pattern Analysis and Machine Intelligence,1997.

[5]Kamran Etemad,Rama Chellappa.Discriminant analysis for recognition of human face images.1997.