費雪線性判別

在模式识别中，费雪线性判别（Fisher's linear discriminant）是一种线性判别方法，其意图是在分类类别为c类时，将d维空间（样品点是d维向量）中的数据点投影到c-1维空间上去，使得不同类的样本点在这个空间上的投影尽量分离，同类的尽量紧凑。

两类情况

在二类判别时，费雪线性判别将d维空间中的数据点投影到一条直线上去，使得不同类的样本点在这条直线上的投影尽量分离，同类的样本点在这条直线上尽量紧凑。假设有两类样本集${𝒟}_1$的类别为ω₁，样本数为n₁，${𝒟}_2$的类别为ω₂，样本数为n₂。定义样本均值m_i和类内散布S_i。

${𝐦}_i=\frac{1}{n_i}\sum _{x\in {𝒟}_i}𝐱,i=1,2$

${𝐒}_i=\sum _{x\in {𝒟}_i}(𝐱-{𝐦}_i){(𝐱-{𝐦}_i)}^t,i=1,2$

投影直线的方向向量为w，样本投影在直线上的值为y。则可得两类样本投影后的均值和类内散布为${\tilde{m}}_i$和${\tilde{s}}_i^2$，i=1,2。

$y={𝐰}^t𝐱{\tilde{m}}_i={𝐰}^t{𝐦}_i,i=1,2$

$\begin{array}{cc}{\tilde{s}}_i^2& =\sum _{y\in {𝒴}_i}{(y-{\tilde{m}}_i)}^2\\ & =\sum _{x\in {𝒟}_i}{({𝐰}^t𝐱-{𝐰}^t{𝐦}_i)}^2\\ & =\sum _{x\in {𝒟}_i}{𝐰}^t(𝐱-{𝐦}_i){(𝐱-{𝐦}_i)}^t𝐰\\ & ={𝐰}^t{𝐒}_i𝐰\end{array}$

要使不同类的样本点的投影尽量分离，同类尽量紧凑，可以使两类的投影的均值的差异尽量大，其方差的和尽量小，也就是要求$\frac{{|{\tilde{m}}_1-{\tilde{m}}_2|}^2}{{\tilde{s}}_1^2+{\tilde{s}}_2^2}$最大化。

$\begin{array}{cc}𝑱(𝐰)& =\frac{{|{\tilde{m}}_1-{\tilde{m}}_2|}^2}{{\tilde{s}}_1^2+{\tilde{s}}_2^2}\\ & =\frac{{({𝐰}^t{𝐦}_1-{𝐰}^t{𝐦}_2)}^2}{{𝐰}^t{𝐒}_1𝐰+{𝐰}^t{𝐒}_2𝐰}\\ & =\frac{{𝐰}^t({𝐦}_1-{𝐦}_2){({𝐦}_1-{𝐦}_2)}^t𝐰}{{𝐰}^t({𝐒}_1+{𝐒}_2)𝐰}\\ & =\frac{{𝐰}^t{𝐒}_{𝐁}𝐰}{{𝐰}^t{𝐒}_{𝐖}𝐰}\\ \end{array}$

${𝐒}_{𝐁}=({𝐦}_1-{𝐦}_2){({𝐦}_1-{𝐦}_2)}^t,{𝐒}_{𝐖}=({𝐒}_1+{𝐒}_2)$

可以证明当w满足${𝐒}_{𝐁}𝐰=\lambda {𝐒}_{𝐖}𝐰$，即w的方向与${{𝐒}_{𝐖}}^{-1}({𝐦}_1-{𝐦}_2)$相同时，J(w)取得最大值。剩下的问题就是如何求解阈值w₀，也就是在这个一维空间中把两类分开的那个点的位置。当J(w)超过w₀就判决为某一类别ω，否则就判决为另一类别。然而目前并没有一个通用的选取方法。

在两个类别的分布是多元正态分布，且协方差矩阵相同时，根据贝叶斯决策理论，$𝐰={\mathrm{\Sigma }}^{-1}({𝐮}_1-{𝐮}_2)$，并且w₀是一个与w和先验概率有关的常数。我们可以用样本均值与样本协方差去估计u_i和Σ。更一般地说，如果我们对投影后的数据进行平滑，或用一维高斯函数进行拟合，ω₀就位于使两类的后验概率相同的位置上。

多类情况

费雪线性判别在面对二类判别时，将两类样本向一条直线投影，也就是将数据从d维空间向1维空间投影。这样在面对c个类的判别时，所要做就是将数据从d维空间向c-1维空间投影。这就需要推广投影方程、类间散布矩阵S_B和类内散布矩阵S_W。从d维空间向c-1维空间的投影是通过c-1投影方程进行的：

$y_i={𝐰}_i^t𝐱,𝐱\in {𝒟}_{i}i=1,\dots ,c-1$

这里的${𝒟}_i$为第i类的样本集。设$𝐲=[y_1,y_2,\dots ,y_{c-1}{]}^t𝐖=[w_1,w_2,\dots ,w_{c-1}]$，c-1个方程可以更简练地表达：

$𝐲={𝐖}^t𝐱,𝐲\in {𝒴}_{i}i=1,\dots ,c-1$

这里的${𝒴}_i$为第i类的样本的投影向量集。类间散布矩阵S_B和类内散布矩阵S_W可以由总体散布矩阵S_T和总体均值向量m推导得到： $𝐦=\frac{1}{n}\sum _{𝐱}𝐱=\frac{1}{n}\sum _{i=1}^c{n}_i{𝐦}_i{𝐒}_T=\sum _{𝐱}(𝐱-𝐦)(𝐱-𝐦{)}^t$

$\begin{array}{cc}{𝐒}_T& =\sum _{i=1}^c\sum _{𝐱\in {𝒟}_i}(𝐱-{𝐦}_i+{𝐦}_i-𝐦)(𝐱-{𝐦}_i+{𝐦}_i-𝐦{)}^t\\ & =\sum _{i=1}^c\sum _{𝐱\in {𝒟}_i}(𝐱-{𝐦}_i)(𝐱-{𝐦}_i{)}^t+\sum _{i=1}^c\sum _{𝐱\in {𝒟}_i}({𝐦}_i-𝐦)({𝐦}_i-𝐦{)}^T\\ \end{array}$

由此定义类间散布矩阵S_B和类内散布矩阵S_W：

${𝐒}_W=\sum _{i=1}^c\sum _{𝐱\in {𝒟}_i}(𝐱-{𝐦}_i)(𝐱-{𝐦}_i{)}^t{𝐒}_{𝐁}=\sum _{i=1}^c\sum _{𝐱\in {𝒟}_i}({𝐦}_i-𝐦)({𝐦}_i-𝐦{)}^T$

${𝐒}_T={𝐒}_W+{𝐒}_{𝐁}$

那么样本数据的投影向量的类间散布矩阵${\widetilde{𝐒}}_{𝐁}$和类内散布矩阵${\widetilde{𝐒}}_{𝐖}$：即为：

${\widetilde{𝐒}}_{𝐁}=\sum _{i=1}^c\sum _{𝐲\in {𝒴}_i}({\widetilde{𝐦}}_i-\widetilde{𝐦})({\widetilde{𝐦}}_i-\widetilde{𝐦}{)}^T={𝐖}^t{𝐒}_{𝐁}𝐖$

${\widetilde{𝐒}}_{𝐖}=\sum _{i=1}^c\sum _{𝐲\in {𝒴}_i}(𝐲-{\widetilde{𝐦}}_i)(𝐲-{\widetilde{𝐦}}_i{)}^t={𝐖}^t{𝐒}_{𝐖}𝐖$

与两类情况类似，要找到某一W使得类内散布尽量小，类间散布尽量大。但这里的类内散布和类间散布不再是一个值，而是一个矩阵。矩阵的行列式是矩阵的特征值的乘积，也就是数据在各个主要方向的方差的积，相当于类别散布超椭球体的体积的平方。故使用行列式来度量散布，这样判别函数即为$𝑱(𝐰)=\frac{|{\widetilde{𝐒}}_{𝐁}|}{|{\widetilde{𝐒}}_{𝐖}|}=\frac{|{𝐖}^t{𝐒}_{𝐁}𝐖|}{|{𝐖}^t{𝐒}_{𝐖}𝐖|}$

可以证明，当W的列向量w_i是${𝐒}_{𝐁}{𝐰}_i={\mathit{\lambda }}_i{𝐒}_{𝐖}{𝐰}_i$的广义特征向量时，可以使得J(w)最大。因为S_B中c个秩为1或0的矩阵相加，而且其中只有c-1个矩阵是相互独立的。所以S_B的秩最多为c-1。所以最多只有c-1个特征向量是非零的。

应用

人脸识别

在人脸识别中，每一个人脸图像具有大量的像素点。LDA主要用来将特征减少到一个可以处理的数目在进行分类。每一个新的维度都是原先像素值的线性组合，这就构成了一个模板。这样获得的线性组合被称为Fisher faces,而通过主成分分析获得的则称为特征脸。

参考文献

• Template:Cite book

• Template:Cite journal