Dimensionality Reduction——LDA線性判別分析原理篇

01-26

寫在前面：應基友的需求，同時對自己所學進行一個總結，寫一篇關於LDA的筆記，作為常見降維演算法小節的第一篇。

本篇為原理篇注重公式推導，實踐篇傳送門Dimensionality Reduction--LDA線性判別分析實現篇 - 知乎專欄

LDA簡介：

LDA的全稱是Linear Discriminant Analysis（線性判別分析），是一種supervised learning。因為是由Fisher在1936年提出的，所以也叫Fisher』s Linear Discriminant。

LDA通常作為數據預處理階段的降維技術，其目標是將數據投影到低維空間來避免維度災難（curse of dimensionality）引起的過擬合，同時還保留著良好的可分性。

LDA的引出：

經常經過特徵提取以後，我們需要進行降維。首先我們簡化一下問題便於闡述其原理:

假設在二維特徵空間中，有兩類樣本，那麼我們的目標就是對給定的數據集，將其投影到一條直線上，但是投影的方法有千千萬萬種，那麼我們改選擇什麼樣的投影呢？

首先我們的任務是為了分類服務的，那麼我們需要投影后的樣本儘可能的分開，最簡單的度量類別之間分開程度的方式就是類別均值投影之後的距離。

一種比較好的投影方式就是利用不同類別的數據的中心來代表這類樣本在空間中的位置，考慮1個2分類問題。兩類的均值向量為：

同時保證讓投影之後的中心距離儘可能的大，也就是：

其中

是來自類別 $i$ 的投影數據的均值， $w^T$ 是我們的投影向量。但是，通過增大w，這個表達式可以任意增大。為了解決這個問題，我們可以將w限制為單位長度，即 $sum_iw_i^2=1$ 。

使用拉格朗日乘數法來進行有限制條件的最大化問題的求解，我們可以發現 $w propto |widetilde{mu_2}-widetilde{mu_1}|$ 。這個方法還有一個問題，如下圖所示：

左圖為最大間隔度量的降維結果，這幅圖中的兩個類別在原始空維空間(x1; x2)中可以完美地被分開，但是當投影到連接它們的均值的直線上時，就有了一定程度的重疊。

因此，Fisher提出的思想：最大化一個函數，這個函數能夠讓類均值的投影分開得較大，同時讓每個類別內部的方差較小，從而最小化了類別的重疊（右圖中的結果）。

這也是LDA的中心思想即：最大化類間距離，最小化類內距離。

LDA演算法推導——2類：

接著上一段的引出，我們已經找到了一種不錯的投影方式，現在只需要讓其最小化類內的方差，我們假設投影結束後，樣本的坐標為 $y$ ，即 $y= extbf{w}^T extbf{x}$ ，那麼來自類別Ck的數據經過變換後的類內方差為：

我們可以把整個數據集的總的類內方差定義為 $widetilde{s}_2^1+widetilde{s}_2^2$ 。Fisher準則根據類間距離和類內方差的比值定義，即：

根據 $widetilde{mu_k}= extbf{w}^T mu_k$ ，以及 $y= extbf{w}^T extbf{x}$ ，對上式子進行改寫， $widetilde{mu_1} -widetilde{mu_2}$ 通過：

$widetilde{s}_2^1+widetilde{s}_2^2$ 通過下式：

J(W)可以被重寫為：

其中 $S_B$ 是類間（between-class）散度矩陣，形式為

$S_W$ 被稱為類內（within-class）散度矩陣，形式為：

$sum_{xin w_1} (x-mu_1)(x-mu_1)^T+sum_{xin w_2} (x-mu_2)(x-mu_2)^T$

對公式J(W)關於w求導，並另之為0，我們發現J(w)取得最大值的條件為：

實際上恰好就是倒數的分母。由於 $(w^TS_Bw)$ 和 $(w^TS_Ww)$ 在簡化的二分類問題中都是標量，因此我們可以把上式子看做：

（或者將分母限定在模為1，利用拉格朗日求解也可以得到上式，具體參考周志華《機器學習》）

將求導後的結果兩邊都乘以 $S_W^{-1}$ 可得：

從這裡就可以看出，是一個求特徵值和特徵向量的問題了。

具體的，對於我們在引出中提出的簡化問題，由於：

因此 $S_Bw$ 的方向始終為 $(mu_2-mu_1)$ ，故可以用 $lambda (mu_2-mu_1)$ 來表示，因此我們可以得到：

由於對w擴大縮小任何倍不影響結果，因此我們可得：

我們只需要求出原始樣本的均值和方差就可以求出最佳的方向w，這就是Fisher於1936年提出的線性判別分析。

LDA完全體——對於多類多維：

之前討論的是問題的簡化版，我們把問題定義在了2類，同時降維後維度為1的情況，但是當遇到類別為多類的時候，維度為1已經不能滿足要求了。現在我們把問題拓展為：

我們有C個類別，需要將特徵降維到K維。

那麼投影矩陣W自然就是 $W=[w_1|w_2...|w_k]$ ，之前的 $y_i= extbf{w}^T extbf{x}_i$ 也依然成立。

同樣的我們需要找到和之前一樣的一個優化目標J（w）來衡量，考慮之前的目標，通過投影后的類內散度矩陣和類間的散度矩陣來定義，我們發現對於多類的情況，類內散度矩陣依然存在。並且定義和之前一樣基本保持不變，即Sw為：

其中：

但是類間散度矩陣已經無法按照之前的定義來求，我們考慮下圖：

我們可以定義全局散度矩陣St，即 $sum_{i=1}^n(x_i-mu)(x_i-mu)^T$ 表示全局的散度，其中n表示數據集中所有的點 $mu$ 表示所有數據點的均值向量。

我們可以不是一般性的認為：全局散度矩陣=類內散度矩陣+類間散度矩陣

因此 $S_B = S_t-S_W$ ，有此可以得到：

從這個式子我們可以看出，其物理意義就是定義了每個類別到全局中心的距離，我們要讓類間分離的足夠開，就需要讓每個類別的樣本再投影后，距離全局中心足夠遠。

顯然，LDA可以有多種實現方法， $S_B,S_W,S_t$ 三者中任意兩個都可以構建出優化目標。和之前保持一致，我們選擇 $S_B,S_W$ ，我們定義出了投影后的 $widetilde{S_w}$ 和 $widetilde{S_B}$ ：

一種常見的的優化目標為：

上式可以通過如下廣義特徵值問題求解：

因此W的閉式解（closed-form）就是 $S_w^{-1}S_B$ 的K個最大的廣義特徵值的特徵向量組成的矩陣。將W看成一個投影矩陣，那麼實際上就是將原來的特徵空間投影到了K維空間中，可以縮小樣本點的維度，而且利用了類別信息，是一種經典的有監督降維方法。

注意：由於 $S_B$ 矩陣中的 $mu_i-mu$ 的秩為1，因此SB的秩最多為N，即類別數目（矩陣的秩小於等於各個相加矩陣的秩的和）。又由於 $mu_i$ 和N個 $mu$ 不是線性無關的， $mu_i$ 和前N-1個 $mu$ 可以表示出第N個 $mu$ ，或者說 $mu_i$ 可以通過 $mu$ 的線性組合表示出來，因此 $S_B$ 的秩最多為N-1，那麼K也最大為N-1，即特徵向量最多有N-1個。

參考資料：

PRML

《機器學習》

線性判別分析（Linear Discriminant Analysis）（一）