前言

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

談到LDA，就不得不談?wù)凱CA，PCA是一個(gè)和LDA非常相關(guān)的算法，從推導(dǎo)、求解、到算法最終的結(jié)果，都有著相當(dāng)?shù)南嗨啤?/p>

本次的內(nèi)容主要是以推導(dǎo)數(shù)學(xué)公式為主，都是從算法的物理意義出發(fā)，然后一步一步最終推導(dǎo)到最終的式子，LDA和PCA最終的表現(xiàn)都是解一個(gè)矩陣特征值的問題，但是理解了如何推導(dǎo)，才能更深刻的理解其中的含義。本次內(nèi)容要求讀者有一些基本的線性代數(shù)基礎(chǔ)，比如說特征值、特征向量的概念，空間投影，點(diǎn)乘等的一些基本知識(shí)等。除此之外的其他公式、我都盡量講得更簡單清楚。

LDA

LDA的全稱是Linear Discriminant Analysis（線性判別分析），是一種supervised learning。有些資料上也稱為是Fisher’s Linear Discriminant，因?yàn)樗籖onald Fisher發(fā)明自1936年，Discriminant這次詞我個(gè)人的理解是，一個(gè)模型，不需要去通過概率的方法來訓(xùn)練、預(yù)測數(shù)據(jù)，比如說各種貝葉斯方法，就需要獲取數(shù)據(jù)的先驗(yàn)、后驗(yàn)概率等等。LDA是在目前機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘領(lǐng)域經(jīng)典且熱門的一個(gè)算法，據(jù)我所知，百度的商務(wù)搜索部里面就用了不少這方面的算法。

LDA的原理是，將帶上標(biāo)簽的數(shù)據(jù)（點(diǎn)），通過投影的方法，投影到維度更低的空間中，使得投影后的點(diǎn)，會(huì)形成按類別區(qū)分，一簇一簇的情況，相同類別的點(diǎn)，將會(huì)在投影后的空間中更接近。要說明白LDA，首先得弄明白線性分類器(Linear Classifier)：因?yàn)長DA是一種線性分類器。對于K-分類的一個(gè)分類問題，會(huì)有K個(gè)線性函數(shù)：

上式實(shí)際上就是一種投影，是將一個(gè)高維的點(diǎn)投影到一條高維的直線上，LDA最求的目標(biāo)是，給出一個(gè)標(biāo)注了類別的數(shù)據(jù)集，投影到了一條直線之后，能夠使得點(diǎn)盡量的按類別區(qū)分開，當(dāng)k=2即二分類問題的時(shí)候，如下圖所示：

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

LDA分類的一個(gè)目標(biāo)是使得不同類別之間的距離越遠(yuǎn)越好，同一類別之中的距離越近越好，所以我們需要定義幾個(gè)關(guān)鍵的值。
類別i的原始中心點(diǎn)為：（Di表示屬于類別i的點(diǎn))

類別i投影后的中心點(diǎn)為：

衡量類別i投影后，類別點(diǎn)之間的分散程度（方差）為：

最終我們可以得到一個(gè)下面的公式，表示LDA投影到w后的損失函數(shù)：

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

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

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

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

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

和 PCA 區(qū)別

二者都有降維的作用。

1. 左邊是PCA，屬于無監(jiān)督方法，當(dāng)數(shù)據(jù)沒有標(biāo)簽時(shí)可以用它。
   右邊是 LDA，屬于監(jiān)督方法?？紤]了數(shù)據(jù)的分類信息，這樣數(shù)據(jù)在低維空間上就可以分類了，減少了很多的運(yùn)算量。

2. PCA 主要是從特征的協(xié)方差角度考慮，追求的是在降維之后能夠最大化保持?jǐn)?shù)據(jù)的內(nèi)在信息。
   它不考慮分類信息，因此，降低維度后，信息損失降到最低，但分類上可能會(huì)變得更加困難。
   LDA 追求的是降維后的數(shù)據(jù)點(diǎn)盡可能容易被區(qū)分。
   降維后的樣本數(shù)據(jù)在新的維度空間有最大的類間距離和最小的類內(nèi)方差，數(shù)據(jù)在低維空間有最佳的可分離性。

3. PCA 后的維度數(shù)目是和數(shù)據(jù)維度相關(guān)的，原始數(shù)據(jù)是 n 維，那么 PCA 后維度為 1、2～n 維。
   LDA 后的維度數(shù)目是和類別的個(gè)數(shù)相關(guān)的，原始數(shù)據(jù)是 n 維，一共有 C 個(gè)類別，那么 LDA 后維度為 1、2～C-1 維。

4. PCA 投影的坐標(biāo)系都是正交的。
   LDA 關(guān)注分類能力，不保證投影到的坐標(biāo)系是正交的。