費雪線性判別

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

兩類情況

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

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

${\displaystyle \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。則可得兩類樣本投影后的均值和類內散布為${\displaystyle {\tilde {m}}_{i}}$和${\displaystyle {\tilde {s}}_{i}^{2}}$，i=1,2。

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

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

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

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

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

在兩個類別的分布是多元正態分布，且協方差矩陣相同時，根據貝葉斯決策理論，${\displaystyle \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投影方程進行的：

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

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

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

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

${\displaystyle {\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：

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

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

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

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

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