機(jī)器學(xué)習(xí)算法原理筆記（三）—— LDA線性判別分析

一、簡(jiǎn)述

線性判別分析(Linear discriminant Analysis，LDA)是一種監(jiān)督學(xué)習(xí)的降維技術(shù)，與PCA不同的是，PCA是尋找數(shù)據(jù)集中方差最大的方向作為主成分分量的軸，而LDA是最優(yōu)化分類的特征子空間。

LDA的思想可以用一句話概括，就是“投影后類內(nèi)方差最小，類間方差最大”。也就是說(shuō)，要將數(shù)據(jù)在低維度上進(jìn)行投影，投影后希望每一種類別數(shù)據(jù)的投影點(diǎn)盡可能的接近，而不同類別的數(shù)據(jù)的類別中心之間的距離盡可能的大：

與PCA之間的對(duì)比：

可以看出，如果是PCA的話，為了方差最大化，會(huì)選擇投影到左邊，而LDA則會(huì)選擇投影到下面。


二、二類LDA

假設(shè)我們的數(shù)據(jù)集 D=\{(x_1,y_1), (x_2,y_2), ...,((x_m,y_m))\} ，其中任意樣本xi為n維向量，yi∈{0,1}。我們定義N_{j}(j=0,1)為第j類樣本的個(gè)數(shù)，X_{j}(j=0,1)為第j類樣本的集合，而μ_{j}(j=0,1)為第j類樣本的均值向量，定義Σ_{j}(j=0,1)為第j類樣本的協(xié)方差矩陣（嚴(yán)格說(shuō)是缺少分母部分的協(xié)方差矩陣）。

μj的表達(dá)式為：

\mu_j = \frac{1}{N_j}\sum\limits_{x \in X_j}x\;\;(j=0,1)

Σj的表達(dá)式為：

\Sigma_j = \sum\limits_{x \in X_j}(x-\mu_j)(x-\mu_j)^T\;\;(j=0,1)

由于是兩類數(shù)據(jù)，因此我們只需要將數(shù)據(jù)投影到一條直線上即可。假設(shè)我們的投影直線是向量w，則對(duì)任意一個(gè)樣本本xi，它在直線w的投影為 w^Tx_i，我們希望同一種類別數(shù)據(jù)的投影點(diǎn)盡可能的接近，也就是要同類樣本投影點(diǎn)的協(xié)方差w^T\Sigma_0w和w^T\Sigma_1w盡可能的小，即最小化下面的式子：

w^T\Sigma_0w+w^T\Sigma_1w

另一方面，我們希望讓不同類別的數(shù)據(jù)盡可能地遠(yuǎn)離，考慮類的中心（也就是均值） \mu_0,\mu_1，只要使得 ||w^T\mu_0-w^T\mu_1||_2^2盡可能大即可。

綜合上面的考量，我們可以得出下面的優(yōu)化目標(biāo)：

\underbrace{arg\;max}_w\;\;J(w) = \frac{||w^T\mu_0-w^T\mu_1||_2^2}{w^T\Sigma_0w+w^T\Sigma_1w} = \frac{w^T(\mu_0-\mu_1)(\mu_0-\mu_1)^Tw}{w^T(\Sigma_0+\Sigma_1)w}

為了表示方便，我們做如下定義：

S_w = \Sigma_0 + \Sigma_1 = \sum\limits_{x \in X_0}(x-\mu_0)(x-\mu_0)^T + \sum\limits_{x \in X_1}(x-\mu_1)(x-\mu_1)^T

S_b = (\mu_0-\mu_1)(\mu_0-\mu_1)^T

優(yōu)化目標(biāo)重寫為：

\underbrace{arg\;max}_w\;\;J(w) = \frac{w^TS_bw}{w^TS_ww}

利用凸優(yōu)化的知識(shí)，我們使用和SVM中同樣的技巧，約束{w^TS_ww}=1（和SVM中一樣，上下式子一同縮放不影響最后求\underbrace{arg\;max}_w\;\;J(w)的結(jié)果），這樣使用拉格朗日乘子法就可以得到：

J(w)=w^TS_bw-\lambda(w^TS_ww-1)

\frac{dJ}{dw}=2S_bw-2\lambda S_ww=0

S_bw=\lambda S_ww

如果S_w可逆，就又變回了求特征向量的套路：

S_w^{-1}S_bw=\lambda w

當(dāng)然，在實(shí)際問(wèn)題中，S_w 常出現(xiàn)不可逆的問(wèn)題，不過(guò)一般情況下可以通過(guò)其他方法解決：

  • 令S_w=S_w+\gamma I，其中\gamma是一個(gè)特別小的數(shù)，這樣S_w一定可逆

  • 先使用PCA對(duì)數(shù)據(jù)進(jìn)行降維，使得在降維后的數(shù)據(jù)上S_w可逆，再使用LDA

再往前一步：

我們考慮到兩類的這種情況下，其實(shí)s_b w 和 (\mu_1 - \mu_2) 是平行的，所以：

S_b w= (\mu_1 - \mu_2) (\mu_1 - \mu_2)^T w = (\mu_1 - \mu_2) * k

那么就算在式子兩邊左乘S_w^{-1}也是成立的，那么原先的式子就可以轉(zhuǎn)化為：

S_w^{-1} S_b w = S_w^{-1} (\mu_1 - \mu_2) * k = w * \lambda

兩邊同除以 k 對(duì)式子沒(méi)有影響，所以，就可以得到得到特征向量：

w = S_w^{-1}{(\mu_1 - \mu_2)}

也就是說(shuō)我們只要求出原始二類樣本的均值和方差就可以確定最佳的投影方向w了


三、廣義瑞利商求解二類LDA

瑞利商 R(A,x) 的定義：

R(A,x) = \frac{x^HAx}{x^Hx}

其中，x為非零向量，而A為n×n的Hermitan矩陣(Hermitan矩陣就是滿足共軛轉(zhuǎn)置矩陣和自己相等的矩陣，即A^H=A，如果矩陣A是實(shí)矩陣，則滿足A^T = A的矩陣即為Hermitan矩陣)

瑞利商R(A,x)有一個(gè)非常重要的性質(zhì)，即它的最大值等于矩陣A最大的特征值，而最小值等于矩陣A的最小的特征值，也就是滿足(證明可以參考范數(shù)不等式):

\lambda_{min} \leq \frac{x^HAx}{x^Hx} \leq \lambda_{max}

廣義瑞利商R(A,B,x)的定義:

R(A,x) = \frac{x^HAx}{x^HBx}

其中，x為非零向量，而A,B為n×n的Hermitan矩陣，B為正定矩陣

廣義瑞利商是不是很眼熟，我們完全可以套用廣義瑞利商來(lái)求解之前的最大值問(wèn)題，但先要得到廣義瑞利商的最大最小值。

通過(guò)將廣義瑞利商通過(guò)標(biāo)準(zhǔn)化就可以轉(zhuǎn)化為瑞利商的形式，從而得到廣義廣義瑞利商的最大最小值：

令 x=B^{-1/2}x'，則：

分母：x^HBx = x'^H(B^{-1/2})^HBB^{-1/2}x' = x'^HB^{-1/2}BB^{-1/2}x' = x'^Hx'

分子：x^HAx = x'^HB^{-1/2}AB^{-1/2}x'

最后我們就可以得到：

R(A,B,x') = \frac{x'^HB^{-1/2}AB^{-1/2}x'}{x'^Hx'}

R(A,B,x)的最大值為矩陣B^{-1/2}AB^{-1/2}的最大特征值，或者說(shuō)矩陣B^{-1}A的最大特征值，而最小值為矩陣B^{-1}A的最小特征值。


四、多類LDA

假設(shè)我們的數(shù)據(jù)集D=\{(x_1,y_1), (x_2,y_2), ...,((x_m,y_m))\},其中任意樣本x_i為n維向量，y_i∈{C1,C2,...,Ck}。我們定義N_j(j=1,2...k)為第j類樣本的個(gè)數(shù)，X_j(j=1,2...k)為第j類樣本的集合，而μ_j(j=1,2...k)為第j類樣本的均值向量，定義Σ_j(j=1,2...k)為第j類樣本的協(xié)方差矩陣。

假設(shè)我們投影到的低維空間的維度為d，對(duì)應(yīng)的基向量為(w_1,w_2,...w_d)，基向量組成的矩陣為W，它是一個(gè)n×d的矩陣，按我們?cè)诙惱锏慕?jīng)驗(yàn)，此時(shí)我們的優(yōu)化目標(biāo)應(yīng)該可以寫成為:

\frac{W^TS_bW}{W^TS_wW}

S_w 不難寫出，畢竟二類里是兩個(gè)，那多類里就是多弄幾個(gè)而已：
S_w = \sum\limits_{j=1}^{k}S_{wj} = \sum\limits_{j=1}^{k}\sum\limits_{x \in X_j}(x-\mu_j)(x-\mu_j)^T

S_b 應(yīng)該怎么考慮呢，直接按之前的套路復(fù)雜度太高了，有沒(méi)有什么可以代替的好辦法呢？

我們先考慮整體的散度矩陣，也就是：

S_t = \sum\limits_{x \in X_j}(x- \overline{x})(x- \overline{x})^T

其中，\overline{x}是整體的均值

那么S_b 可以用 S_t - S_w 來(lái)表示（下面的推導(dǎo)來(lái)自熊貓學(xué)寫字的博客，符號(hào)有一些差異）

其中：

代入原式：

也就是：
S_b = \sum\limits_{j=1}^{k}N_j(\mu_j-\mu)(\mu_j-\mu)^T

現(xiàn)在我們的優(yōu)化目標(biāo)完全求解出來(lái)了，但是還有一個(gè)問(wèn)題就是現(xiàn)在 W^TS_bW 和 W^TS_wW 都是矩陣，不是標(biāo)量，無(wú)法作為一個(gè)標(biāo)量函數(shù)來(lái)優(yōu)化：

\underbrace{arg\;max}_W\;\;J(W) = \frac{W^TS_bW}{W^TS_wW}

一種解決方法是使用行列式的值來(lái)替換矩陣，解釋是說(shuō)實(shí)際上是矩陣特征值的積，一個(gè)特征值可以表示在該特征向量上的發(fā)散程度，因此我們可以使用行列式來(lái)計(jì)算。

也就是說(shuō)我們的優(yōu)化目標(biāo)變?yōu)椋?/p>

\underbrace{arg\;max}_W\;\;J(W) = \frac{|W^TS_bW|}{|W^TS_wW|}

這樣使用之前的拉格朗日乘子法就可以輕松解決，結(jié)果也和上面是一樣的。

不過(guò)需要注意的是由于S_b的秩最大為k?1，所以S_2^{-1}S_b的特征向量數(shù)目不會(huì)超過(guò)k?1，所以我們投影后的d<=(k?1)。(因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=S_b" alt="S_b" mathimg="1">中每個(gè)μ_j ? μ的秩為1，因此協(xié)方差矩陣相加后最大的秩為k(矩陣的秩小于等于各個(gè)相加矩陣的秩的和)，但是由于如果我們知道前k-1個(gè)μ_j后，最后一個(gè)μ_k可以由前k-1個(gè)μ_j線性表示，因此S_b的秩最大為k-1，即特征向量最多有k-1個(gè)。

另一種解決方法是取矩陣對(duì)角線之和，也就是特征值之和：

\underbrace{arg\;max}_W\;\;J(W) = \frac{\prod\limits_{diag}W^TS_bW}{\prod\limits_{diag}W^TS_wW}

優(yōu)化過(guò)程可以轉(zhuǎn)化為：

J(W) = \frac{\prod\limits_{i=1}^dw_i^TS_bw_i}{\prod\limits_{i=1}^dw_i^TS_ww_i} = \prod\limits_{i=1}^d\frac{w_i^TS_bw_i}{w_i^TS_ww_i}

那么根據(jù)廣義廣義瑞利商即可求得和上面一樣的結(jié)果。


五、LDA算法流程

輸入：數(shù)據(jù)集D=\{(x_1,y_1), (x_2,y_2), ...,((x_m,y_m))\}，其中任意樣本x_i為n維向y_i \in \{C_1,C_2,...,C_k\}，降維到的維度d:

  1. 計(jì)算S_w 、S_b 和 S_w^{-1}S_b

  2. 計(jì)算 S_w^{-1}S_b的最大的d個(gè)特征值和對(duì)應(yīng)的d個(gè)特征向量(w_1,w_2,...w_d),得到投影矩陣W

  3. 對(duì)樣本集中的每一個(gè)樣本特征x_i，轉(zhuǎn)化為新的樣本z_i=W^Tx_i

  4. 得到降維后的數(shù)據(jù)


六、LDA和PCA

LDA的優(yōu)缺點(diǎn)：


LDA和PCA的比較：


七、sklearn實(shí)現(xiàn)

class sklearn.discriminant_analysis.LinearDiscriminantAnalysis(solver='svd', shrinkage=None, priors=None, n_components=None, store_covariance=False, tol=0.0001)
Parameters:

  • solver: str類型，默認(rèn)值為‘svd’
    svd：使用奇異值分解求解，不用計(jì)算協(xié)方差矩陣，適用于特征數(shù)量很大的情形，無(wú)法使用參數(shù)收縮（shrinkage）
    lsqr：最小平方QR分解，可以結(jié)合shrinkage使用
    eigen：特征值分解，可以結(jié)合shrinkage使用

  • shrinkage: str or float類型，默認(rèn)值為None
    是否使用參數(shù)收縮
    None：不使用參數(shù)收縮
    auto：str，使用Ledoit-Wolf lemma
    浮點(diǎn)數(shù)：自定義收縮比例

  • components：int類型，需要保留的特征個(gè)數(shù)，小于等于n-1

Attributes:

  • covariances_：每個(gè)類的協(xié)方差矩陣， shape = [n_features, n_features]

  • means_：類均值，shape = [n_classes, n_features]

  • priors_：歸一化的先驗(yàn)概率

  • rotations_：LDA分析得到的主軸，shape [n_features, n_component]

  • scalings_：數(shù)組列表，每個(gè)高斯分布的方差σ

import numpy as np
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis

X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
y = np.array([1, 1, 1, 2, 2, 2])

clf = LinearDiscriminantAnalysis()
clf.fit(X, y)

LinearDiscriminantAnalysis(n_components=None, priors=None, shrinkage=None,
              solver='svd', store_covariance=False, tol=0.0001)

print(clf.predict([[-0.8, -1]]))

>> [1]


參考：

  1. 線性判別分析LDA詳解
  2. 線性判別分析LDA原理總結(jié)
  3. https://blog.csdn.net/liuweiyuxiang/article/details/78874106
  4. https://blog.csdn.net/u013719780/article/details/78298264
  5. https://www.cnblogs.com/solong1989/p/9593555.html
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • LDA的原理是，將帶上標(biāo)簽的數(shù)據(jù)（點(diǎn)），通過(guò)投影的方法，投影到維度更低的空間中，使得投影后的點(diǎn)，會(huì)形成按類別區(qū)分，...
    五秋木閱讀 3,148評(píng)論 0贊 2
  • 沒(méi)能深入的理解到溝通的作用，導(dǎo)致重復(fù)的造輪子，造的輪子還不能運(yùn)行，交流溝通至關(guān)重要。 在同一臺(tái) 電腦上啟多個(gè)服務(wù)，...
    zizl_zq閱讀 371評(píng)論 2贊 1
  • 我寫我的詩(shī)詞，你讀你的感受，可能感同身受，也可以無(wú)關(guān)你我——副標(biāo)題 詩(shī)人 應(yīng)該具有比常人更加細(xì)致的觀察能力或習(xí)慣，...
    望舍閱讀 304評(píng)論 3贊 10
  • 銀行家算法銀行家算法是一種最有代表性的避免[死鎖]的算法。在避免死鎖方法中允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，但系統(tǒng)在進(jìn)行資源...
    natewang閱讀 847評(píng)論 0贊 0
  • 人們總喜歡做飛蛾，撲火。當(dāng)然我也不例外。希望自己別太固執(zhí)
    Amoonlight閱讀 188評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容