一、前言

二、什么是LDA？

三、LDA原理

1.二分類問題

2.多分類問題

3.幾點說明

四、演算法實作

一、前言

之前我們已經介紹過PCA演算法，這是一種無監督的降維方法，可以將高維資料轉化為低維資料處理，然而，PCA總是能適用嗎？

考慮如下資料點：

由PCA的原理我們可知，這些資料點在經PCA處理后會被映射到x軸上，如下所示：

可以發現，投影后，紅色資料點和藍色資料點并不能很好地區分開，思考其背后的原因，在這個例子中，我們的資料點有了類別標簽，而PCA是一種無監督學習演算法，它會對所有類別的資料點一視同仁，所以在分類問題中，PCA總是顯得乏力，事實上，相比于X軸，將資料點投影到Y軸是一個更優選擇：

如上圖所示，將資料點投影到Y軸可以將兩個類別的資料點很好地區分開來，那么我們該如何找到這種投影方式呢，下面我們將介紹一種新的降維方法——LDA演算法，

二、什么是LDA？

線性判別分析（LDA），同PCA類似，也是一種降維演算法，不一樣的是，LDA是一種監督演算法，它需要用到類別資訊，LDA演算法的思路同PCA一致，即通過某種線性投影，將原本高維空間中的一些資料，映射到更低維度的空間中，但LDA演算法要求投影后的資料滿足：1.同類別的資料之間盡可能地接近，2.不同類別的資料之間盡可能地遠離，

三、LDA原理

1.二分類問題

從最簡單的二分類問題開始討論，根據LDA的投影目標，我們可以得到我們要優化的目標如下：

$J = \frac{\left \| u_1'-u_2' \right \|^2}{S_1'^2+S_2'^2}$

其中， $u_1',u_2'$ 代表投影后兩個類別的資料的中心點， $S_1',S_2'$ 代表投影后兩個類別的資料的標準差，同PCA一致，我們一般用方差來表示資料的離散散程度，觀察優化目標 $J$ ，分子衡量的是投影后兩個類別的資料中心點的距離，而分母衡量的是投影后兩個類別的資料各自的離散程度，同類別的資料越接近（LDA投影目標1），分母越小， $J$ 越大；不同類別的資料越遠離（LDA投影目標2），分子越大， $J$ 越大，目標合理，

方便起見，設 $X$ 為原始資料點， $u_1=\sum_{X\in Class1} \frac{X}{N},u_2=\sum_{X\in Class2} \frac{X}{N}$ 分別為原始資料的中心點， $w$ 為投影向量，則有:

$u_1'=\sum_{X\in Class1} \frac{w^TX}{N}=w^Tu_1$

$u_2'=\sum_{X\in Class2}\frac{w^TX}{N}=w^Tu_2$

$S_1'^2=\frac{1}{N}\sum \left \| w^TX-u_1' \right \|^2=\sum w^T\frac{1}{N}(X-u_1)(X-u_1)^Tw=w^TS_1w$

$S_2'^2=\frac{1}{N}\sum \left \| w^TX-u_2' \right \|^2=\sum w^T\frac{1}{N}(X-u_2)(X-u_2)^Tw=w^TS_2w$

優化目標即為：

$J(w) = \frac{\left \| u_1'-u_2' \right \|^2}{S_1'^2+S_2'^2}=\frac{\left \| w^T(u_1-u_2) \right \|^2}{w^T(S_1+S_2)w}=\frac{w^T(u_1-u_2)(u_1-u_2)^Tw}{w^T(S_1+S_2)w}$

不妨設 $S_B=(u_1-u_2)(u_1-u_2)^T,S_w=S_1+S_2$ ，則 $J(w)$ 可簡化為 $\frac{w^TS_Bw}{w^TS_ww}$ ，

對 $J(w)$ 求導，應有：

$\frac{d J(w)}{dw}=\frac{2S_Bw(w^TS_ww)-2S_ww(w^TS_Bw)}{\left \| w^TS_2w \right \|^2}=0$

化簡，得：

$S_Bw(w^TS_ww)-S_ww(w^TS_Bw)=0$

等式兩邊同除以 $w^TS_ww$ ，得：

$S_Bw-S_ww\frac{w^TS_Bw}{w^TS_ww}=S_Bw-S_wJw=0$

變形，得：

$S_w^{-1}S_Bw=Jw$

顯然，這又是一個矩陣分解問題， $J$ 是矩陣 $S_w^{-1}S_B$ 的特征值，同時也是我們優化的目標，而 $w$ 即為對應的特征值，也是投影向量，所以我們將矩陣分解得到的特征值從大到小排列，然后取最大的幾個特征值對應的特征向量作為我們的投影向量，

觀察式子 $S_Bw-S_wJw=0$ ，由于 $S_B=(u_1-u_2)(u_1-u_2)^T$ ，代入，得：

$(u_1-u_2)(u_1-u_2)^Tw=S_wJw$

由于 $(u_1-u_2)^Tw$ 代表的是投影后兩類資料中心點間的距離，我們可以用常數 $D$ 代替，于是有：

$w=\frac{D}{j}S_w^{-1}(u_1-u_2)$

對于投影向量 $w$ ，我們只需要求得它的方向，對于它的大小（縮放程度）并無要求，所以我們最終求得的投影向量 $w$ 即為 $S_w^{-1}(u_1-u_2)$ ，通過這種方法，我們并不需要對矩陣進行分解便能求得投影向量，大大減少了計算量，

2.多分類問題

對二分類問題進行推廣，考慮多分類問題，同樣，投影的目的仍是使得同類資料點盡可能近，不同類別的資料點盡可能遠，這里需要對優化目標 $J$ 做適當改變，如下：

$J=\frac{\sum N_i\left \| u_i'-u' \right \|^2}{\sum S_i'^2}$

其中， $u_i,S_i$ 和二分類問題一致，仍是第i類資料的中心點和標準差，而 $u$ 則代表所有資料的中心， $N_i$ 代表第i個類別的資料個數，仔細觀察，可以發現，目標 $J$ 的分母仍為各類別資料投影后的離散程度，而分子則是投影后各類別資料中心距所有資料中心點的距離的加權平方和，同樣是衡量不同類別資料點的分離程度，優化的目標同二分類問題一致，重點關注LDA投影目標，萬變不離其宗，

以二分類問題為例進行驗證，有：

$\begin{align} S_B&=N_1(u_1-u)(u_1-u)^T+N_2(u_2-u)(u_2-u)^T\\ &=N_1(u_1-u)(u_1-u)^T+N_2(u_2-u)(u_2-u)^T\\ &=N_1(u_1-\frac{N_1u_1+N_2u_2}{N})(u_1-\frac{N_1u_1+N_2u_2}{N})^T+N_2(u_2-\frac{N_1u_1+N_2u_2}{N})(u_2-\frac{N_1u_1+N_2u_2}{N})^T\\ &=N_1(\frac{N_2u_1-N_2u_2}{N})(\frac{N_2u_1-N_2u_2}{N})^T+N_2(\frac{N_1u_2-N_1u_1}{N})(\frac{N_1u_2-N_1u_1}{N})^T\\ &=\frac{N_1N_2^2}{N}(u_1-u_2)(u_1-u_2)^T+\frac{N_1^2N_2}{N}(u_1-u_2)(u_1-u_2)^T\\ &=\frac{N_1N_2}{N}(u_1-u_2)(u_1-u_2)^T \end{align}$

同樣，我們只需要知道投影的方向，所以對于常數項 $\frac{N_1N_2}{N}$ ，其只控制投影后資料點的縮放，并不影響最終結果，可以忽略，可以發現，用多分類問題的公式計算出來的結果同二分類的計算公式完全一致，

3.幾點說明

(1).維度必減少

PCA演算法降維可以理解為旋轉坐標軸，新的坐標下每條軸作為一個維度也即成分，對于差距不大的維度可以略去從而達到降維的目的，也就是說實際上PCA演算法可以將N維資料仍然變換為N維資料，然后可視情況刪減維度，但LDA演算法不盡然，使用LDA演算法時，新的坐標維度必會減少，

以二分類為例，觀察式子 $S_w^{-1}S_Bw=Jw$ ，由于 $S_B=(u_1-u_2)(u_1-u_2)^T$ ，可知 $S_B$ 為奇異矩陣（它的秩最多為C-1)，從而可以知道 $S_w^{-1}S_B$ 也必為奇異矩陣，所以它分解后必有一個特征值為0，我們只能得到C-1個投影向量，C為類別個數，