費雪線性判別

在模式識別中，**費雪線性判別**（Fisher's linear discriminant）是一種線性判別方法，其意圖是在分類類別為 c 類時，將 d 維空間（樣品點是 d 維向量）中的數據點投影到 c-1 維空間上去，使得不同類的樣本點在這個空間上的投影儘量分離，同類的儘量緊湊。

## 兩類情況

在二類判別時，費雪線性判別將 **d** 維空間中的數據點投影到一條直線上去，使得不同類的樣本點在這條直線上的投影儘量分離，同類的樣本點在這條直線上儘量緊湊。假設有兩類樣本集 ${\mathcal {D}}_{1}$ 的類別為 **ω**1，樣本數為 **n**1， ${\mathcal {D}}_{2}$ 的類別為 **ω**2，樣本數為 **n**2。定義樣本均值 **m**i 和類內散布 **S**i。

　
: $\mathbf {m} _{i}={\frac {1}{n_{i}}}\sum _{x\in {\mathcal {D}}_{i}}\mathbf {x} ,i=1,2$

　
: $\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$

投影直線的方向向量為 **w**，樣本投影在直線上的值為 _y_。則可得兩類樣本投影后的均值和類內散布為 ${\tilde {m}}_{i}$ 和 ${\tilde {s}}_{i}^{2}$ ，**i**=1,2。

　
: $y=\mathbf {w} ^{t}\mathbf {x} \quad {\tilde {m}}_{i}=\mathbf {w} ^{t}\mathbf {m} _{i},i=1,2$

　
: ${\begin{aligned}{\tilde {s}}_{i}^{2}&=\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{aligned}}$

要使不同類的樣本點的投影儘量分離，同類儘量緊湊，可以使兩類的投影的均值的差異儘量大，其方差的和儘量小，也就是要求 ${\frac {\left|{\tilde {m}}_{1}-{\tilde {m}}_{2}\right|^{2}}{{\tilde {s}}_{1}^{2}+{\tilde {s}}_{2}^{2}}}$ 最大化。

　
: ${\begin{aligned}{\boldsymbol {J}}(\mathbf {w} )&={\frac {\left|{\tilde {m}}_{1}-{\tilde {m}}_{2}\right|^{2}}{{\tilde {s}}_{1}^{2}+{\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{aligned}}$

　
: $\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)$

可以證明當 **w** 滿足 $\mathbf {S_{B}w} =\lambda \mathbf {S_{W}w} $ ，即 **w** 的方向與 $\mathbf {S_{W}} ^{-1}\left(\mathbf {m} _{1}-\mathbf {m} _{2}\right)$ 相同時，_**J**_(**w**) 取得最大值。剩下的問題就是如何求解閾值 **w**0，也就是在這個一維空間中把兩類分開的那個點的位置。當_**J**_(**w**) 超過 **w**0 就判決為某一類別 **ω**，否則就判決為另一類別。然而目前並沒有一個通用的選取方法。

在兩個類別的分布是多元常態分布，且協方差矩陣相同時，根據貝葉斯決策理論， $\mathbf {w} =\mathbf {\Sigma } ^{-1}\left(\mathbf {u} _{1}-\mathbf {u} _{2}\right)$ ，並且 **w**0 是一個與 **w** 和先驗概率有關的常數。我們可以用樣本均值與樣本協方差去估計 **u**i 和 **Σ**。更一般地說，如果我們對投影后的數據進行平滑，或用一維高斯函數進行擬合，**ω**0 就位於使兩類的後驗概率相同的位置上。

## 多類情況

費雪線性判別在面對二類判別時，將兩類樣本向一條直線投影，也就是將數據從 d 維空間向 1 維空間投影。這樣在面對 c 個類的判別時，所要做就是將數據從 d 維空間向 c-1 維空間投影。這就需要推廣投影方程、類間散布矩陣 **S**B 和類內散布矩陣 **S**W。從 d 維空間向 c-1 維空間的投影是通過 c-1 投影方程進行的：

$$
y_{i}=\mathbf {w} _{i}^{t}\mathbf {x} ,\mathbf {x} \in {\mathcal {D}}_{i}\quad i=1,\ldots ,c-1
$$

這裡的 ${\mathcal {D}}_{i}$ 為第 i 類的樣本集。設 $\mathbf {y} =[y_{1},y_{2},\ldots ,y_{c-1}]^{t}\quad \mathbf {W} =[w_{1},w_{2},\ldots ,w_{c-1}]$ ，c-1 個方程可以更簡練地表達：

$$
\mathbf {y} =\mathbf {W} ^{t}\mathbf {x} ,\mathbf {y} \in {\mathcal {Y}}_{i}\quad i=1,\ldots ,c-1
$$

這裡的 ${\mathcal {Y}}_{i}$ 為第 i 類的樣本的投影向量集。類間散布矩陣 **S**B 和類內散布矩陣 **S**W 可以由總體散布矩陣 **S**T 和總體均值向量 **m** 推導得到： $\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}$

$$
{\begin{aligned}\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{aligned}}
$$

由此定義類間散布矩陣 **S**B 和類內散布矩陣 **S**W：

$$
\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}
$$

$$
\mathbf {S} _{T}=\mathbf {S} _{W}+\mathbf {S_{B}}
$$

那麼樣本數據的投影向量的類間散布矩陣 ${\widetilde {\mathbf {S} }}_{\mathbf {B} }$ 和類內散布矩陣 ${\widetilde {\mathbf {S} }}_{\mathbf {W} }$ ：即為：

$$
{\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}
$$

$$
{\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}
$$

與兩類情況類似，要找到某一 **W** 使得類內散布儘量小，類間散布儘量大。但這裡的類內散布和類間散布不再是一個值，而是一個矩陣。矩陣的行列式是矩陣的特徵值的乘積，也就是數據在各個主要方向的方差的積，相當於類別散布超橢球體的體積的平方。故使用行列式來度量散布，這樣判別函數即為 ${\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} |}}$

可以證明，當 **W** 的列向量 **w**i 是 $\mathbf {S_{B}} \mathbf {w} _{i}=\mathbf {\lambda } _{i}\mathbf {S_{W}} \mathbf {w} _{i}$ 的廣義特徵向量時，可以使得_**J**_(**w**) 最大。因為 **S**B 中 c 個秩為 1 或 0 的矩陣相加，而且其中只有 c-1 個矩陣是相互獨立的。所以 **S**B 的秩最多為 c-1。所以最多只有 c-1 個特徵向量是非零的。

## 應用

### 人臉識別

在人臉識別中，每一個人臉圖像具有大量的像素點。LDA 主要用來將特徵減少到一個可以處理的數目在進行分類。每一個新的維度都是原先像素值的線性組合，這就構成了一個模板。這樣獲得的線性組合被稱為 Fisher faces, 而通過主成分分析獲得的則稱為特徵臉。

## 參考文獻

* Duda, R. O.; Hart, P. E.; Stork, D. H. Pattern Classification 第 2 版。機械工業出版社. 2004. ISBN 7-111-13687-X.
* Fisher, R. A. The Use of Multiple Measurements in Taxonomic Problems. Annals of Eugenics. 1936, **7** (2): 179–188. doi:10.1111/j.1469-1809.1936.tb02137.x. hdl:2440/15227.