查看“︁費雪線性判別”︁的源代码

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

== 两类情况 ==
在二类判别时，费雪线性判别将'''d'''维空间中的数据点投影到一条直线上去，使得不同类的样本点在这条直线上的投影尽量分离，同类的样本点在这条直线上尽量紧凑。假设有两类样本集<math>\mathcal{D}_1</math>的类别为'''ω'''<sub>1</sub>，样本数为'''n'''<sub>1</sub>，<math>\mathcal{D}_2</math>的类别为'''ω'''<sub>2</sub>，样本数为'''n'''<sub>2</sub>。定义样本均值'''m'''<sub>i</sub>和类内散布'''S'''<sub>i</sub>。

:<math>\mathbf{m}_i=\frac{1}{n_i} \sum_{x\in \mathcal{D}_i} \mathbf{x},i=1,2</math>
:<math>\mathbf{S}_i=\sum_{x\in \mathcal{D}_i} \left( \mathbf{x}-\mathbf{m}_i \right) \left(\mathbf{x}-\mathbf{m}_i \right)^t,i=1,2</math>

投影直线的方向向量为'''w'''，样本投影在直线上的值为''y''。则可得两类样本投影后的均值和类内散布为<math>\tilde{m}_i</math>和<math>\tilde{s}^2_i</math>，'''i'''=1,2。
:<math>y=\mathbf{w}^t\mathbf{x} \quad  \tilde{m}_i=\mathbf{w}^t\mathbf{m}_i,i=1,2</math>
:<math>\begin{align}
       \tilde{s}^2_i &=\sum_{y\in \mathcal{Y}_i} \left( y-\tilde{m}_i \right)^2\\
                     &=\sum_{x\in \mathcal{D}_i} \left( \mathbf{w}^t\mathbf{x}-\mathbf{w}^t\mathbf{m}_i \right)^2\\
                     &=\sum_{x\in \mathcal{D}_i} \mathbf{w}^t \left( \mathbf{x}-\mathbf{m}_i \right)\left( \mathbf{x}-\mathbf{m}_i \right)^t \mathbf{w}\\
                    &=\mathbf{w}^t \mathbf{S}_i \mathbf{w}
\end{align}</math>

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

:<math>\begin{align}
       \boldsymbol{J}(\mathbf{w}) &=\frac{\left| \tilde{m}_1-\tilde{m}_2 \right|^2 }{\tilde{s}^2_1+\tilde{s}^2_2} \\
                    &= \frac{ \left( \mathbf{w}^t\mathbf{m}_1-\mathbf{w}^t\mathbf{m}_2 \right)^2}{\mathbf{w}^t \mathbf{S}_1 \mathbf{w}+\mathbf{w}^t \mathbf{S}_2 \mathbf{w}} \\
                    &=\frac{\mathbf{w}^t \left( \mathbf{m}_1-\mathbf{m}_2 \right)\left( \mathbf{m}_1-\mathbf{m}_2 \right)^t \mathbf{w}} { \mathbf{w}^t \left( \mathbf{S}_1 + \mathbf{S}_2 \right) \mathbf{w} }\\
                    &=\frac{\mathbf{w}^t \mathbf{S_B} \mathbf{w}} {\mathbf{w}^t \mathbf{S_W} \mathbf{w}} \\
\end{align}</math>
:<math>
\mathbf{S_B}=\left( \mathbf{m}_1-\mathbf{m}_2 \right)\left( \mathbf{m}_1-\mathbf{m}_2 \right)^t, \mathbf{S_W}=\left( \mathbf{S}_1 + \mathbf{S}_2 \right)
</math>
可以证明当'''w'''满足<math>\mathbf{S_B w}=\lambda \mathbf{S_W w}</math>，即'''w'''的方向与<math>\mathbf{S_W}^{-1} \left(  \mathbf{m}_1-\mathbf{m}_2 \right)</math>相同时，'''''J'''''('''w''')取得最大值。剩下的问题就是如何求解阈值'''w'''<sub>0</sub>，也就是在这个一维空间中把两类分开的那个点的位置。当'''''J'''''('''w''')超过'''w'''<sub>0</sub>就判决为某一类别'''ω'''，否则就判决为另一类别。然而目前并没有一个通用的选取方法。

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

== 多类情况 ==

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

<center>
<math>y_i=\mathbf{w}^t_i \mathbf{x},\mathbf{x}\in \mathcal{D}_i \quad i=1,\ldots,c-1</math>

</center>

这里的<math>\mathcal{D}_i</math>为第i类的样本集。设<math>\mathbf{y}=[y_1,y_2,\ldots,y_{c-1}]^t \quad \mathbf{W}=[w_1,w_2,\ldots,w_{c-1}] </math>，c-1个方程可以更简练地表达：

<center>
<math>\mathbf{y}=\mathbf{W}^t \mathbf{x},\mathbf{y}\in \mathcal{Y}_i \quad i=1,\ldots,c-1</math>
</center>
这里的<math>\mathcal{Y}_i</math>为第i类的样本的投影向量集。类间散布矩阵'''S'''<sub>B</sub>和类内散布矩阵'''S'''<sub>W</sub>可以由总体散布矩阵'''S'''<sub>T</sub>和总体均值向量'''m'''推导得到：
<math>\mathbf{m}=\frac{1}{n} \sum_{\mathbf{x}} \mathbf{x}=\frac{1}{n} \sum_{i=1}^c n_i\mathbf{m}_i \qquad \mathbf{S}_T=\sum_{\mathbf{x}}(\mathbf{x}-\mathbf{m})(\mathbf{x}-\mathbf{m})^t</math>

<math>

\begin{align}

\mathbf{S}_T & = \sum_{i=1}^{c} \sum_{\mathbf{x} \in \mathcal{D}_i}(\mathbf{x}-\mathbf{m}_i+\mathbf{m}_i-\mathbf{m})(\mathbf{x}-\mathbf{m}_i+\mathbf{m}_i-\mathbf{m})^t \\

& = \sum_{i=1}^{c} \sum_{\mathbf{x} \in \mathcal{D}_i}(\mathbf{x}-\mathbf{m}_i)(\mathbf{x}-\mathbf{m}_i)^t+\sum_{i=1}^{c} \sum_{\mathbf{x} \in \mathcal{D}_i}(\mathbf{m}_i-\mathbf{m})(\mathbf{m}_i-\mathbf{m})^T \\

\end{align}</math>

由此定义类间散布矩阵'''S'''<sub>B</sub>和类内散布矩阵'''S'''<sub>W</sub>：

<math>

\mathbf{S}_W=\sum_{i=1}^{c} \sum_{\mathbf{x} \in \mathcal{D}_i}(\mathbf{x}-\mathbf{m}_i)(\mathbf{x}-\mathbf{m}_i)^t \quad \mathbf{S_B}=\sum_{i=1}^{c} \sum_{\mathbf{x} \in \mathcal{D}_i}(\mathbf{m}_i-\mathbf{m})(\mathbf{m}_i-\mathbf{m})^T 

</math>

<math>\mathbf{S}_T=\mathbf{S}_W+\mathbf{S_B}</math>

那么样本数据的投影向量的类间散布矩阵<math>\widetilde{\mathbf{S}}_\mathbf{B}</math>和类内散布矩阵<math>\widetilde{\mathbf{S}}_\mathbf{W}</math>：即为：

<math>\widetilde{\mathbf{S}}_\mathbf{B}=\sum_{i=1}^{c} \sum_{\mathbf{y} \in \mathcal{Y}_i}(\widetilde{\mathbf{m}}_i-\widetilde{\mathbf{m}})(\widetilde{\mathbf{m}}_i-\widetilde{\mathbf{m}})^T=\mathbf{W}^t \mathbf{S_B} \mathbf{W}</math>

<math>\widetilde{\mathbf{S}}_\mathbf{W}=\sum_{i=1}^{c} \sum_{\mathbf{y} \in \mathcal{Y}_i}(\mathbf{y}-\widetilde{\mathbf{m}}_i)(\mathbf{y}-\widetilde{\mathbf{m}}_i)^t=\mathbf{W}^t \mathbf{S_W} \mathbf{W}</math>

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

可以证明，当'''W'''的列向量'''w'''<sub>i</sub>是<math>\mathbf{S_B}\mathbf{w}_i=\mathbf{\lambda}_i \mathbf{S_W}\mathbf{w}_i</math>的广义[[特征向量]]时，可以使得'''''J'''''('''w''')最大。因为'''S'''<sub>B</sub>中c个秩为1或0的矩阵相加，而且其中只有c-1个矩阵是相互独立的。所以'''S'''<sub>B</sub>的秩最多为c-1。所以最多只有c-1个特征向量是非零的。

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

== 参考文献 ==

* {{cite book
 |title=Pattern Classification
 |edition=第2版
 |first1=R. O. |last1=Duda
 |first2=P. E. |last2=Hart
 |first3=D. H. |last3=Stork
 |publisher=机械工业出版社
 |year=2004
 |isbn=7-111-13687-X
}}

* {{cite journal
 |last=Fisher |first=R. A. |authorlink=Ronald Fisher
 |title=The Use of Multiple Measurements in Taxonomic Problems
 |journal=[[Annals of Eugenics]]
 |volume=7
 |pages=179–188
 |year=1936
 |id={{hdl|2440/15227}}|doi=10.1111/j.1469-1809.1936.tb02137.x
 |issue=2
}}
[[分类:统计学]]