費雪線性判別

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

兩類情況

在二類判別時，費雪線性判別將d維空間中的數據點投影到一條直線上去，使得不同類的樣本點在這條直線上的投影儘量分離，同類的樣本點在這條直線上儘量緊湊。假設有兩類樣本集${\mathcal {D}}_{1}$的類別為ω₁，樣本數為n₁，${\mathcal {D}}_{2}$的類別為ω₂，樣本數為n₂。定義樣本均值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₀，也就是在這個一維空間中把兩類分開的那個點的位置。當J(w)超過w₀就判決為某一類別ω，否則就判決為另一類別。然而目前並沒有一個通用的選取方法。

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

多類情況

費雪線性判別在面對二類判別時，將兩類樣本向一條直線投影，也就是將數據從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. .