線性判別分析

線性判別分析（Linear discriminant analysis，縮寫：LDA）是對費舍爾的線性鑑別方法的歸納，這種方法使用統計學，模式識別和機器學習方法，試圖找到兩類物體或事件的特徵的一個線性組合，以能夠特徵化或區分它們。所得的組合可用來作為一個線性分類器，或者，更常見的是，為後續的分類做降維處理。

LDA與變異數分析（ANOVA）和迴歸分析緊密相關，這兩種分析方法也試圖透過一些特徵或測量值的線性組合來表示一個因變量。然而，變異數分析使用類別型的自變量和連續型的因變量，而判別分析則使用連續型自變量和類別型因變量（即類標籤）。邏輯斯諦迴歸和機率迴歸比變異數分析更類似於LDA，因為他們也是用連續型自變量來解釋類別型因變量。LDA的基本假設是自變量是常態分布的，當這一假設無法滿足時，在實際應用中更傾向於用上述的其他方法。

LDA也與主成分分析（PCA）和因素分析緊密相關，它們都在尋找最佳解釋數據的變量線性組合。LDA明確地嘗試在不同數據類之間建立模型，而PCA則不考慮類別上的不同（只是在保留大部分訊息的前提下降低維度數），因素分析則是根據相異處而非相同處來建立特徵組合。判別分析跟因素分析的差異還在於，它不是一個相互依存技術：即必須區分出自變量和因變量（也稱為準則變量）的不同。

當自變量每一次的觀察測量值都是連續量的時候，LDA能發揮作用。如果是處理類別型自變量，與LDA相對應的技術稱為判別反應分析。

## 二類LDA

考慮在已知類別 y 中每一個對象或事件的一組觀察量${ \vec x }$（也稱為特徵、屬性、變量或測量）；這一組樣本稱為訓練集。分類問題即為在給定觀察量 $\vec x$ 為 y 類的情況下找一個良好的預測器，使得任意具有相同分布的樣品（未必來自訓練集合）都能被正確地判斷。

LDA 的方法是，透過假設條件概率密度函數$p(\vec x|y=0)$ 和 $p(\vec x|y=1)$ 都是正態分布，分別具有均值和協方差$\left(\vec \mu_0, \Sigma_0\right)$ 和 $\left(\vec \mu_1, \Sigma_1\right)$。根據這一假設，貝葉斯最佳解決方案是如果預測點的可能性比率之對數值低於某一閾值 T，其就屬於第二類：

$$(\vec x- \vec \mu_0)^T \Sigma_0^{-1} ( \vec x- \vec \mu_0) + \ln|\Sigma_0| - (\vec x- \vec \mu_1)^T \Sigma_1^{-1} ( \vec x- \vec \mu_1) - \ln|\Sigma_1| \ > \ T$$

如果沒有任何進一步的假設，所得到的分類器稱為QDA（二次判別分析）。

相反地，LDA做出額外簡化的同方差性假設（即不同類之間的協方差相同，$\Sigma_0 = \Sigma_1 = \Sigma$），並且協方差是滿秩的。在這種情況下，可以消掉一些項：

$${\vec x}^T \Sigma_0^{-1} \vec x = {\vec x}^T \Sigma_1^{-1} \vec x$$

${\vec x}^T {\Sigma_i}^{-1} \vec{\mu_i} = {\vec{\mu_i}}^T{\Sigma_i}^{-1} \vec x$ 因為$\Sigma_i$是埃爾米特矩陣

如此一來，上面的判斷準則就變成了判斷點積的閾值是否大於某常數 c

$$\vec w \cdot \vec x > c$$

而

$$\vec w = \Sigma^{-1} (\vec \mu_1 - \vec \mu_0)$$

$$c = \frac{1}{2}(T-{\vec{\mu_0}}^T \Sigma_0^{-1} {\vec{\mu_0}}+{\vec{\mu_1}}^T \Sigma_1^{-1} {\vec{\mu_1}})$$

這意味著，一個輸入 $\vec x$ 屬於類 y 的標準就純粹成為一個已知觀察值的線性組合的函數。

從幾何學的角度來看這個結論通常會有些幫助：判斷一個輸入 $\vec x$ 是否為類 y 的標準就是一個將多維空間上的點 $\vec x$ 投影到向量 $\vec w$（我們僅僅考慮其方向）的函數。換句話說，如果相對應的 $\vec x$ 位於一個垂直於 $\vec w$ 的超平面的某一側，那麼觀察值就屬於y類。平面的位置由閾值c來決定。

## k類正則判別分析

正則判別分析法（CDA）尋找最優區分類別的坐標軸（k-1個正則坐標，k為類別的數量）。這些線性函數是不相關的，實際上，它們通過n維數據云定義了一個最優化的k-1個空間，能夠最優的區分k個類（通過其在空間的投影）。詳細請參見下面的「多類LDA」。

## 費舍爾的線性判別

費舍爾的線性判別和LDA的叫法往往是可以互換使用，儘管費舍爾最早的文章實際上描述了一個稍微不同的判別，他沒有作出一些類似LDA所作的假設，比如正態分布的各類或者相等的類協方差。

假設觀察的兩個類分別有均值$\vec \mu_0, \vec \mu_1$和協方差$\Sigma_0,\Sigma_1$。那麼特徵的線性組合$\vec w \cdot \vec x$將具有均值$\vec w \cdot \vec \mu_i$和協方差$\vec w^T \Sigma_i \vec w$ 其中$i=0,1$。費舍爾把區分這兩類分布的規則為類間方差與類內方差的比率：

$$S=\frac{\sigma_{\text{between}}^2}{\sigma_{\text{within}}^2}= \frac{(\vec w \cdot \vec \mu_1 - \vec w \cdot \vec \mu_0)^2}{\vec w^T \Sigma_1 \vec w + \vec w^T \Sigma_0 \vec w} = \frac{(\vec w \cdot (\vec \mu_1 - \vec \mu_0))^2}{\vec w^T (\Sigma_0+\Sigma_1) \vec w}$$

從某種意義上說，這一方法是測量類標籤的信噪比。它可以顯示，當滿足如下條件時，會產生最大的區分

$$\vec w \propto (\Sigma_0+\Sigma_1)^{-1}(\vec \mu_1 - \vec \mu_0)$$

當LDA的假設滿足時，上述方程式就是LDA。

一定要注意的矢量$\vec w$是判別超平面的法線。以二維空間為例，能區分兩類的最優線就是與$\vec w$。

一般來說，要判別數據點投影到$\vec w$；然後從一維分布中選取區分數據的最佳閾值。選取閾值沒有通用的規則。然而，如果兩類的投影點顯示出近似的分布，那麼選取兩個均值的投影$\vec w \cdot \vec \mu_0$和$\vec w \cdot \vec \mu_1$之間的超平面是比較合適的。在這種情況下，$\vec w \cdot \vec x > c$條件下的閾值參數c可以明確表達為：

$c = \vec w \cdot \frac12 (\vec \mu_0 + \vec \mu_1) = \frac{1}{2} \vec\mu_1^T \Sigma^{-1} \vec\mu_1 - \frac{1}{2} \vec\mu_0^T \Sigma^{-1} \vec\mu_0$.

大津算法與費舍爾的線性判別有些相關，它的建立是通過最優選取黑白間的閾值，來二元化灰度圖像中像素的直方圖，既能使黑白像素兩類間的方差最大化，又能使兩類內各自的方差最小化。

## 多類LDA

當出現超過兩類的情況時，可以使用由費舍爾判別派生出的分析方法，它延伸為尋找一個保留了所有類的變化性的子空間。這是由C.R.Rao總結出來的。假設，C個類中每一個類都有均值$\mu_i$和相同的協方差$\Sigma$。那麼，類間的變化可以通過類均值的協方差來定義

$$\Sigma_b = \frac{1}{C} \sum_{i=1}^C (\mu_i-\mu) (\mu_i-\mu)^T$$

這裡$\mu$是各類均值的均值。在$\vec w$的方向區分類有下式給出

$$S = \frac{\vec w^T \Sigma_b \vec w}{\vec w^T \Sigma \vec w}$$

這意味著如果$\vec w$是$\Sigma^{-1} \Sigma_b$的特徵向量，等同於用對應的特徵值進行分類。

如果$\Sigma^{-1} \Sigma_b$是可對角化矩陣，特徵之間的變化性就會被保留在C-1個最大特徵值對應的特徵向量構成子空間內（因為 $\Sigma_b$最大可能的秩是C−1）。與PCA相同，這些特徵向量的主要用途是縮減特徵數。較小的特徵值對應的特徵向量對訓練數據的選擇非常敏感，所以常常需要使用下段中描述的調整方法。

如果只是為了分類，而不需要降維，還有一些替代技術可用。例如，多個類本身就是分離的，可用費舍爾判別或者LDA對每個區進行分類。一個常見的例子是「一個對其餘」，指的是從一個類里出來的點，放入一組裡，其他的歸入另一組，這就可以用LDA。這將導致C類分類器，它的結果是組合在一起的。另一個常見的方法就是配對分類，給每一對類別創建一個分類器（總共有C(C−1)/2個分類器)，再將每個分類器的結果綜合得到最終結果。

## 增量LDA

要實現典型的LDA技術前提是所有的樣本都必須提前準備完畢。但有些情況下，沒有現成的完整數據集或者輸入觀察數據是流的形式。這樣，就要求LDA的特徵提取有能力隨著觀察新樣本的增加而更新LDA的特徵，而不是在整個數據集上運行演算法。例如，在移動機器人或實時臉部識別等實時應用中，提取的LDA特徵能隨著新觀察值實時更新是非常重要的。這種能夠通過簡單觀察新樣本來更新LDA特徵的技術就叫做增量LDA演算法，在過去二十年裡，它已經被廣泛的研究過。Catterjee和Roychowdhury提出了一種增量自組織LDA演算法來更新LDA特徵。另外，Demir和Ozmehmet提出利用誤差改正和赫布學習規則的線上本地學習演算法來更新LDA特徵。最後，Aliyari等人提供了快速增量LDA演算法。

## 實際使用

在實際中，類的均值和協方差都是未知的。然而，它們可以從訓練集合中估算出來。最大似然估計和最大後驗概率估計都可以用來替代上述方程裡面的相應值。雖然協方差的估值在某種意義上是最優的，即使對類的正態分布假設是正確的，也並不能表明用這些估值替換得到的判別是最優的。

另一個應用LDA和費舍爾判別的複雜情況是，每個樣品測量值的數量（即每個數據向量的維度）超過類中的樣品數量。在這種情況下，協方差估值不是滿秩，因此不能取逆。有幾種方法可以應對這種情況。一種是在上述公式中使用廣義逆陣替代通常的逆矩陣。不過，先把問題投影到$\Sigma_b$構成的子空間上可以得到更好的數字穩定性。另一個處理小樣本的策略是，用協方差矩陣的收縮估算，可以表達為以下數學式

$$\Sigma = (1-\lambda) \Sigma+\lambda I\,$$

這裡$I$的單位矩陣，$\lambda$是的收縮度或歸一參數。這產生了歸一判別分析或收縮判別分析的框架。

此外，在許多實際情形中線性判別是不合適的。LDA和費舍爾判別可以通過核函數擴展到非線性分類。原始的觀察值有效的映射到一個高維的非線性空間裡。在這個非線性空間裡的線性分類，就相當於在原始空間裡面的非線性分類。最常用的例子就是核函數費舍爾判別。

LDA可以推廣到多類判別分析，其中c變為一個具有N個可能狀態，而不是兩個狀態的類別變量。類似地，如果各類的條件概率密度 $p(\vec x\mid c=i)$都是正態分布有共同的協方差，那麼$P(c\mid\vec x)$的充分統計量就是協方差逆矩陣在N個均值構成的子平面上仿射的N個投影值。這些投影值可以通過解廣義特徵值問題來找到，分子是以均值為樣本構成的協方差矩陣，分母是共有協方差矩陣。詳情參見上述「多類LDA」。

## 應用領域

除了下面給出的實例，LDA應用於市場定位和產品管理。

### 破產預測

在基於財務比率和其他金融變量的破產預測中，LDA是第一個用來系統解釋公司進入破產或存活的統計學工具。儘管受到財務比率不遵守LDA正態分布假設的限制，Edward Altman的1968年模型仍然是實際應用的領先者。

### 臉部識別

在電腦化的臉部識別中，每一張臉由大量像素值表達。LDA在這裡的主要作用是把特徵的數量降到可管理的數量後再進行分類。每一個新的維度都是模板里像素值的線性組合。使用費舍爾線性判別得到的線性組合稱為費舍爾臉，而通過主成分分析（PCA）得到稱為特徵臉。

### 市場營銷

在市場營銷，判別分析曾經常用於通過市場調查或其他數據收集手段，找出那些能區分不同客戶或產品類型的多個因素。如今用的更多的是邏輯斯諦迴歸或其他方法。在市場營銷中使用判別分析的具體步驟如下描述：

- 制定問題並收集數據 --識別消費者評估產品的一些顯著屬性一 用定量市場研究技術（例如市場調查）從潛在消費者中收集關於他們對產品所有屬性的評分數據。數據收集階段通常是由專業的市場調查公司完成的。調查人員選擇一系列屬性，請參與者對他們給出1到5（或者1到7，1到10）的評分。通常選5到20個屬性。通常包括：易用度，重量，準確度，耐用性，色彩度，價格，或尺寸。根據研究的產品選擇不同的屬性。在調查中對所有的產品都問相同的問題。多個產品的數據編碼後，輸入統計分析程序，比如R，SPSS或SAS。（這一步與因子分析法一樣）。
- 估計的判別函數的係數並確定統計顯著水平和有效性—選擇適當的判別分析方法。直接的方法涉及估計判別函數，以便所有的預測器同時被評估。逐步的方法順序進入的預測器。當因變量只有兩類或狀態時，適用兩組的方法。因變量多於三個是，用多類判別方法。在SPSS或者SAS里的F統計包，用Wilks's Lambda檢驗顯著水平。最常用的有效性檢驗方法是，將樣本分為兩組：估計/分析樣本和驗證樣本。估計樣本用來構建判別函數，驗證樣本構建分類矩陣，其中包括正確分類和不正確分類的數量。正確分類案例的百分比稱為命中率。
- 將結果畫在二維圖裡，定義維度，並解釋結果。統計程序（或相關模塊）會將結果做出圖。圖中包括每個產品（通常為二維空間）。每個產品之間的距離表明他們不同的程度。研究者必須給每個維度註明標籤。整個過程需要主觀判斷，非常具有挑戰性。參見感知映射。

### 生物醫學研究

判別分析在醫學的主要應用是評估患者的嚴重程度和對疾病結果的預後判斷。比如，在回顧分析中，根據患者的病情分為幾組：輕微，中度和嚴重。通過對臨床和實驗室分析結果的研究，揭示被研究組中哪些變量是統計上不同的。使用這些變量建立判別函數，幫助將未來的患者客觀的劃分到輕微，中度和嚴重的類別里。

在生物學中，類似的原則被用以劃分和定義不同的生物對象。例如，用傅立葉變換紅外光譜定義沙門氏菌的噬菌體類別，檢測大腸桿菌的動物來源以研究它的毒力因子等。

### 地球科學

這種方法可用於區分蝕變帶。例如，當很多帶的不同數據都現成時，判別分析可以從數據中找到模式並有效的對它分類。

## 擴展閱讀

- Duda, R. O.; Hart, P. E.; Stork, D. H. (2000). Pattern Classification (2nd ed.). Wiley Interscience. ISBN 0-471-05669-3. MR //www.ams.org/mathscinet-getitem?mr=1802993 1802993.
- Hilbe, J. M. (2009). Logistic Regression Models. Chapman & Hall/CRC Press. ISBN 978-1-4200-7575-5.
- Mika, S.; et al. (1999). "Fisher Discriminant Analysis with Kernels" . IEEE Conference on Neural Networks for Signal Processing IX: 41–48. doi:10.1109/NNSP.1999.788121.
- Mark Burdon and Paul Harpur, 『Re-Conceptualising Privacy and Discrimination in an Age of Talent Analytics』 (2014) 37 University of New South Wales Law Journal, 2, 679–712.1
- Miranda Terry and Paul Harpur, 『The New Era of Segmenting Society on Ability Lines: Workplace Analytics and Disability Discrimination』 (Society for Disability Studies, Atlanta USA, 10–13 June 2015).
- H. Richard McFarland and Donald St. P. Richards, 「Exact Misclassification Probabilities for Plug-In Normal Quadratic Discriminant Functions. I. The Equal-Means Case」 Journal of Multivariate Analysis, 2001, vol. 77, issue 1, pages 21–53 link to article
- H. Richard McFarland and Donald St. P. Richards, 「Exact Misclassification Probabilities for Plug-In Normal Quadratic Discriminant Functions. II. The Heterogeneous Case」 Journal of Multivariate Analysis, 2002, vol. 82, issue 2, pages 299-330 link to article

## 外部連結

- ALGLIB contains open-source LDA implementation in C# / C++ / Pascal / VBA.
- Psychometrica.de open-source LDA implementation in Java
- LDA tutorial using MS Excel
- Biomedical statistics. Discriminant analysis
- www.powercam.cc/chli (中文的影片介紹包含Kernel Method, PCA, KPCA, LDA, GDA, and SVMs)