1. 線性判別分析（Linear Discriminant Analysis）（二類情況）
寫在最前面：LDA是一種經典的監督降維演算法
現在只考慮二值分類情況，也就是
或者
為了方便表示，我們先換符號重新定義問題，給定特徵為
維的
個樣例，
，其中有
個樣例屬於類別
，另外
個樣例屬於類別
。
現在我們覺得原始特徵數太多，想將d維特徵降到
只有一維
，而又要保證類別能夠“清晰”地反映在低維資料上，
也就是這一維就能決定每個樣例的類別
。
我們將這個最佳的向量稱為
（
維），那麼樣例
（
維）到
上的投影可以用下式來計算
這裡得到的
值不是0/1值，而是
投影到直線上的點到原點的距離。
當
是二維的，我們就是要找一條直線（方向為
）來做投影，然後尋找最能使樣本點分離的直線。如下圖：
從直觀上來看，右圖比較好，可以很好地將不同類別的樣本點分離。
接下來我們從定量的角度來找到這個最佳的
。
首先我們尋找每類樣例的均值（中心點），這裡
只有兩個
由於x到w投影后的樣本點均值為
由此可知，投影后的的均值也就是樣本中心點的投影。
什麼是最佳的直線
呢？我們首先發現，
能夠使投影后的兩類樣本中心點儘量分離的直線是好的直線
，定量表示就是：
越大越好。
但是隻考慮
行不行呢？不行，看下圖
樣本點均勻分佈在橢圓裡，投影到橫軸上時能夠獲得更大的中心點間距
，但是由於有重疊，
不能分離樣本點。投影到縱軸
上，雖然
較小，但是能夠分離樣本點。因此我們還需要考慮樣本點之間的方差，方差越大，樣本點越難以分離。
我們使用另外一個度量值，稱作
協方差矩陣：
從公式中可以看出，
協方差矩陣的幾何意義可以理解為是同類樣本點投影之後的密集程度，值越大，越分散，反之，越集中。
而我們想要的投影后的樣本點的期望：
不同類別的樣本點越分開越好，同類的越聚集越好，也就是均值差越大越好，協方差矩陣越小越好。
此時，我們可以使用
和
來度量，如下式：
接下來的事就比較明顯了，我們只需尋找使
最大的
即可。
先把雜湊值公式展開
我們定義上式中中間那部分
這個公式稱為散度矩陣（scatter matrices）
我們繼續定義：
稱為“類內散度矩陣”（
Within-class scatter matrix
）
那麼回到上面
的公式，使用
替換中間部分，得
然後，我們展開分子，繼續定義：
稱為“類間散度矩陣”（
Between-class scatter
），是兩個向量的外積，
這裡要注意，雖然是個矩陣，但秩為1！（後面要用到）
那麼
最終可以表示為
在求解之前，我們先觀察此式，注意到分子和分母都是關於
的二次項，
所以上式的解與 #FormatImgID_67# 的長度並無關係（這裡的長度我個人理解為具體數值大小），只與其方向有關。
在我們求導之前，需要對分母進行歸一化，因為不做歸一的話，
擴大任何倍，都成立，我們就無法確定
。因此我們打算令
那麼加入拉格朗日乘子後，求導
（其中用到了矩陣微積分，求導時可以簡單地把
當做
看待。）
如果
可逆，那麼將求導後的結果兩邊都乘以
，得
這個可喜的結果就是
就是矩陣
的特徵向量！
這個公式稱為Fisher Linear Discrimination
在這裡讓我們繼續挖掘一下，發現前面 #FormatImgID_82# 的公式：
那麼
（同維）：一行*一列=常數
代入最後的特徵值公式得：
由於對
擴大縮小任何倍不影響結果，因此可以約去兩邊的未知常數
和
，得到
至此，我們得到一個非常神奇的結果！
我們為了尋求最佳
只需要求出原始樣本的均值和方差
就可以求出最佳的方向
，
這就是Fisher於1936年提出的線性判別分析。
（在西瓜書上，對於
的求解由於涉及到了逆矩陣，作者說通常是對
進行奇異值分解，這裡不展開說明，作為一個小引，以後陸續會詳細研究。）
看上面二維樣本的投影結果圖：
2. 線性判別分析（多類情況）
前面是針對只有兩個類的情況，假設類別變成多個了，那麼要怎麼改變，才能保證投影后類別能夠分離呢？
我們之前討論的是如何將
維降到一維，現在類別多了，一維可能已經不能滿足要求。假設我們有
個類別，需要
維向量（或者叫做基向量）來做投影。
將這
維向量表示為
我們將樣本點在這
維向量投影后結果表示為
有以下公式成立
為了像上節一樣度量
，我們打算仍然從
類間散度矩陣
和
類內散度矩陣
來考慮。
當樣本是二維時，我們從幾何意義上考慮：
其中
和
與上節的意義一樣，
是類別1裡的樣本點相對於該類中心點
的雜湊程度，
變成類別1中心點相對於樣本中心點
的協方差矩陣，即類1相對於
的雜湊程度。
為：
的計算公式不變，仍然類似於類內部樣本點的協方差矩陣：
需要變，原來度量的是兩個均值點的雜湊情況，現在度量的是每類均值點相對於樣本中心的雜湊情況。類似於將
看作樣本點，
是均值的協方差矩陣，如果某類裡面的樣本點較多，那麼其權重稍大，權重用
表示，但由於
對倍數不敏感，因此使用
。
其中
是所有樣本的均值。
上面討論的都是在投影前的公式變化，但真正的
的分子分母都是在投影后計算的。下面我們看樣本點投影后的公式改變：
這兩個是第i類樣本點在某基向量上投影后的均值計算公式。
下面兩個是在某基向量上投影后的
和
其實就是將
換成了
。
綜合各個投影向量（
）上的
和
，更新這兩個引數，得到
是基向量矩陣，
是投影后的各個類內部的雜湊矩陣之和，
是投影后各個類中心相對於全樣本中心投影的雜湊矩陣之和。
回想我們上節的公式
，分子是兩類中心距，分母是每個類自己的散度矩陣。現在投影方向是多維了（好幾條直線），分子需要做一些改變，我們不是求兩兩樣本中心距之和（這個對描述類別間的分散程度沒有用），而是求每類中心相對於全樣本中心的散度矩陣之和。
然而，最後的
的形式是
由於我們得到的分子分母都是雜湊矩陣，要將矩陣變成實數，需要取行列式。又因為行列式的值實際上是矩陣特徵值的積，一個特徵值可以表示在該特徵向量上的發散程度。因此我們使用行列式來計算（此處我感覺有點牽強，道理不是那麼有說服力）。
整個問題又迴歸為求
的最大值了，我們固定分母為1，然後求導，得出最後結果（我翻查了很多講義和文章，沒有找到求導的過程）
與上節得出的結論一樣
最後還歸結到了求矩陣的特徵值上來了。首先求出
的特徵值，然後取前K個特徵向量組成W矩陣即可。
注意：
由於
中的
秩為1，因此
的秩至多為
（矩陣的秩小於等於各個相加矩陣的秩的和）。由於知道了前
個
後，最後一個
可以有前面的
來線性表示，
失去了一個自由度
，因此
的秩至多為
。那麼K最大為
，即特徵向量最多有
個。特徵值大的對應的特徵向量分割效能最好。
由於
不一定是對稱陣，因此得到的K個特徵向量不一定正交，這也是與PCA不同的地方。
