LDN演算法

Ⅰ 降維演算法二：LDA（Linear Discriminant Analysis）

學習分類演算法，線性分類器最簡單的就是LDA，它可以看做是簡化版的SVM，如果想理解SVM這種分類器，那理解LDA就是很有必要的了。

談到LDA，就不得不談談PCA，PCA是一個和LDA非常相關的演算法，從推導、求解、到演算法最終的結果，都有著相當的相似。

本次的內容主要是以推導數學公式為主，都是從演算法的物理意義出發，然後一步一步最終推導到最終的式子，LDA和PCA最終的表現都是解一個矩陣特徵值的問題，但是理解了如何推導，才能更深刻的理解其中的含義。本次內容要求讀者有一些基本的線性代數基礎，比如說特徵值、特徵向量的概念，空間投影，點乘等的一些基本知識等。除此之外的其他公式、我都盡量講得更簡單清楚。

LDA的全稱是Linear Discriminant Analysis（線性判別分析），是一種 supervised learning 。有些資料上也稱為是Fisher』s Linear Discriminant，因為它被Ronald Fisher發明自1936年，Discriminant這次詞我個人的理解是，一個模型，不需要去通過概率的方法來訓練、預測數據，比如說各種貝葉斯方法，就需要獲取數據的先驗、後驗概率等等。LDA是在 目前機器學習、數據挖掘領域經典且熱門的一個演算法 ，據我所知，網路的商務搜索部裡面就用了不少這方面的演算法。

LDA的原理是，將帶上標簽的數據（點），通過投影的方法，投影到維度更低的空間中，使得投影後的點，會形成按類別區分，一簇一簇的情況，相同類別的點，將會在投影後的空間中更接近。要說明白LDA，首先得弄明白線性分類器( Linear Classifier )：因為LDA是一種線性分類器。對於K-分類的一個分類問題，會有K個線性函數：

上式實際上就是一種投影，是將一個高維的點投影到一條高維的直線上，LDA最求的目標是，給出一個標注了類別的數據集，投影到了一條直線之後，能夠使得點盡量的按類別區分開，當k=2即二分類問題的時候，如下圖所示：

紅色的方形的點為0類的原始點、藍色的方形點為1類的原始點，經過原點的那條線就是投影的直線，從圖上可以清楚的看到，紅色的點和藍色的點被原點明顯的分開了，這個數據只是隨便畫的，如果在高維的情況下，看起來會更好一點。下面我來推導一下二分類LDA問題的公式：
假設用來區分二分類的直線（投影函數)為：

LDA分類的一個目標是使得不同類別之間的距離越遠越好，同一類別之中的距離越近越好，所以我們需要定義幾個關鍵的值。
類別i的原始中心點為：（Di表示屬於類別i的點)

類別i投影後的中心點為：

衡量類別i投影後，類別點之間的分散程度（方差）為：

最終我們可以得到一個下面的公式，表示LDA投影到w後的損失函數：

分類的目標是， 使得類別內的點距離越近越好（集中），類別間的點越遠越好。 分母表示每一個類別內的方差之和，方差越大表示一個類別內的點越分散，分子為兩個類別各自的中心點的距離的平方，我們最大化J(w)就可以求出最優的w了。想要求出最優的w，可以使用拉格朗日乘子法，但是現在我們得到的J(w)裡面，w是不能被單獨提出來的，我們就得想辦法將w單獨提出來。
我們定義一個投影前的各類別分散程度的矩陣，這個矩陣看起來有一點麻煩，其實意思是，如果某一個分類的輸入點集Di裡面的點距離這個分類的中心店mi越近，則Si裡面元素的值就越小，如果分類的點都緊緊地圍繞著mi，則Si裡面的元素值越更接近0.

同樣的將J(w)分子化為：

我們希望 分母越小越好，分子越大越好 ：
分母小，則每個類內部數據點比較聚集；
分子大，則兩個類別的距離較遠。
所以需要找出一個 W 使 J(W) 的值最大。

這樣就可以用最喜歡的拉格朗日乘子法了，但是還有一個問題，如果分子、分母是都可以取任意值的，那就會使得有無窮解，我們將分母限制為長度為1（這是用拉格朗日乘子法一個很重要的技巧，在下面將說的PCA裡面也會用到，如果忘記了，請復習一下高數），並作為拉格朗日乘子法的限制條件，帶入得到：

這樣的式子就是一個求特徵值的問題了。
對於N(N>2)分類的問題，我就直接寫出下面的結論了：

二者都有降維的作用。