機器學習算法系列(十)-線性判別分析算法(一)(Linear Discriminant Analysis Algorithm)

2022-01-09 AI導圖

收錄於話題 #機器學習算法系列 19個

閱讀本文需要的背景知識點：拉格朗日乘數法、一丟丟編程知識

前面學習了一種用回歸的方式來做分類的算法——對數機率回歸算法，下面再來學習另一種分類算法——線性判別分析算法1（Linear Discriminant Analysis Algorithm/LDA），該算法由羅納德·艾爾默·費希爾在1936年提出，所以也被稱為費希爾的線性鑑別方法（Fisher's linear discriminant）

先來看下圖，假設有二分類的數據集，「+」表示正例，「-」表示反例。線性判別分析算法就是要設法找到一條直線，使得同一個類別的點在該直線上的投影儘可能的接近，同時不同分類的點在直線上的投影儘可能的遠。該算法的主要思想總結來說就是要「類內小、類間大」，非常類似於在軟體設計時說的「低耦合、高內聚」。

來源：《機器學習》-周志華

當有新的樣本點需要分類時，計算該點在直線上的投影，根據投影的位置來判斷新樣本點的分類。那麼如何用數學公式來表示上述說法呢？

假設有樣本數為N的數據集，X_i表示第i個樣本點的特徵向量，y_i表示第i個樣本點的標籤值，w表示直線的權重係數。

樣本點到直線的投影向量

（3）由上圖可以看到，我們只需要關係該直線的斜率即可，也就是w的方向。不妨令w為單位向量，即|w| = 1，帶入後整理可得（4）可以看到（3）式中的第一項即為單位向量，後兩項乘積為實數。投影的方向必然與w的方向相同，所以不妨將第一項用w向量代替

均值向量與協方差矩陣

（1）樣本為二分類，N_1表示第一類樣本數量，N_2表示第二類樣本數量

我們知道樣本點的協方差可以用于衡量兩個變量的總體誤差，那麼可以使用協方差的大小來表示類內。而樣本點的均值點可以用來表示相對位置，那麼可以使用均值點來表示類間。我們的目標是讓投影的「類內小、類間大」，那麼可以寫出對應的代價函數如下：

分子為均值向量大小之差的平方，該值越大代表類間越大。分母為兩類樣本點的協方差之和，該值越小代表類內越小，我們的目標就是求使得該代價函數最大時的w：

（2）可以將公共的w的轉置與w提出來，觀察後可以寫成兩類樣本點的均值向量之差（3）中間兩項為實數可以提到前面，w為單位向量，與自己相乘為1

（3）可以將公共的w的轉置與w提出來，中間改寫成樣本點向量與樣本點均值向量之差
（5）將兩個實數相乘寫成向量的乘法並將公共的w的轉置與w提出來（6）觀察中括號中的部分，可以寫成樣本點的協方差矩陣的形式

（2）將實數部分提到前面，後面w為單位向量，與自己相乘為1

（3）使用S_b、S_w來代替中間部分，得到新的代價函數
（4）其中S_b 被稱為"類間散度矩陣"（between-class scatter matrix）（5）其中S_w 被稱為"類內散度矩陣"（within-class scatter matrix）

代價函數最優化

（1）代價函數的新形式，為S_b與S_w的"廣義瑞利商3（generalized Rayleigh quotient）"

（2）可以看到代價函數分子分母都是w的二次項，所以代價函數與w的長度無關，即縮放w不影響代價函數，不妨令分母為1。可以將問題轉化為當分母為1時，求分子前面加一個負號的最小值。

（3）可以運用拉格朗日乘數法4，引入一個新的變量λ，可以將（2）式改寫成新的形式

（4）對（3）式求偏導並令其等於零向量

（5）觀察後發現S_b*w的方向恆為兩類樣本點的均值向量之差的方向，不妨令其為λ倍的兩類樣本點的均值向量之差

（6）這樣就可以求出了w的方向

線性判別分析的核心思想在前面也介紹過——「類內小、類間大」，按照最後求得的公式直接計算即可。

（1）分別計算每一類的均值向量

（2）分別計算每一類的協方差矩陣

（3）計算每類協方差矩陣之和的逆矩陣，可以使用SVD矩陣分解來簡化求逆的複雜度

（4）帶入公式求出權重係數w

求新樣本的分類時，只需判斷新樣本點離哪一個分類的均值向量更近，則新樣本就是哪個分類，如下所示：

1def lda(X, y):
2    """
3    線性判別分析（LDA）
4    args:
5        X - 訓練數據集
6        y - 目標標籤值
7    return:
8        W - 權重係數
9    """
10    # 標籤值
11    y_classes = np.unique(y)
12    # 第一類
13    c1 = X[y==y_classes[0]][:]
14    # 第二類
15    c2 = X[y==y_classes[1]][:]
16    # 第一類均值向量
17    mu1 = np.mean(c1, axis=0)
18    # 第二類均值向量
19    mu2 = np.mean(c2, axis=0)
20    sigma1 = c1 - mu1
21    # 第一類協方差矩陣
22    sigma1 = sigma1.T.dot(sigma1) / c1.shape[0]
23    sigma2 = c2 - mu2
24    # 第二類協方差矩陣
25    sigma2 = sigma2.T.dot(sigma2) / c2.shape[0]
26    # 求權重係數
27    return np.linalg.pinv(sigma1 + sigma2).dot(mu1 - mu2), mu1, mu2
28
29def discriminant(X, w, mu1, mu2):
30    """
31    判別新樣本點
32    args:
33        X - 訓練數據集
34        w - 權重係數
35        mu1 - 第一類均值向量
36        mu2 - 第二類均值向量
37    return:
38        分類結果
39    """
40    a = np.abs(X.dot(w) - mu1.dot(w))
41    b = np.abs(X.dot(w) - mu2.dot(w))
42    return np.argmin(np.array([a, b]), axis=0)

scikit-learn5 實現線性判別分析：

1from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
2
3# 初始化線性判別分析器
4lda = LinearDiscriminantAnalysis()
5# 擬合線性模型
6lda.fit(X, y)
7# 權重係數
8W = lda.coef_
9# 截距
10b = lda.intercept_

如果你使用sklearn提供的線性判別分析的方法，會發現求解出來的結果與上面自己實現的結果不同，這是因為sklearn使用的是另一種方法，並有沒使用廣義瑞利商的形式，而是從概率分布的角度來做分類，後面一節再來介紹該方法。

下圖展示了存在二種分類時的演示數據，其中紅色表示標籤值為0的樣本、藍色表示標籤值為1的樣本：

下圖為擬合數據的結果，其中淺紅色表示擬合後根據權重係數計算出預測值為0的部分，淺藍色表示擬合後根據權重係數計算出預測值為1的部分：

https://en.wikipedia.org/wiki/Linear_discriminant_analysis

https://en.wikipedia.org/wiki/Indicator_function

https://en.wikipedia.org/wiki/Rayleigh_quotient

https://en.wikipedia.org/wiki/Lagrange_multiplier

https://scikit-learn.org/stable/modules/generated/sklearn.discriminant_analysis.LinearDiscriminantAnalysis.html

註：本文力求準確並通俗易懂，但由於筆者也是初學者，水平有限，如文中存在錯誤或遺漏之處，懇請讀者通過留言的方式批評指正

相關焦點

  • 人工智慧之機器學習算法體系匯總
    Github開源機器學習系列文章及算法源碼1. 人工智慧之機器學習體系匯總【直接上乾貨】此處梳理出面向人工智慧的機器學習方法體系，主要體現機器學習方法和邏輯關係，理清機器學習脈絡，後續文章會針對機器學習系列講解算法原理和實戰。
  • Sklearn包含的常用算法
    >線性判別分析（LDA）>>> from sklearn.discriminant_analysis import LinearDiscriminantAnalysis>>> lda = LinearDiscriminantAnalysis(solver="svd", store_covariance=True
  • 多元回歸分析(multiple linear regression)和判別分析(discriminant analysis)
    研究多個因素間關係及具有這些因素的個體之間的一系列統計分析方法稱為多元（因素）分析。主要包括：多元線性回歸，判別分析，聚類分析，主成分分析，因子分析，典型相關，logistic 回歸，Cox 回歸。本期和下一期公眾號文章將挑選幾個常用的多元統計方法為進行介紹。
  • 詳解線性判別分析(Linear Discriminant Analysis)
    對應一個類標籤的公式          至此，我們只需要求出原始樣本的均值和方差就可以求出最佳的方向w，這就是Fisher於1936年提出的線性判別分析。線性判別分析（多類情況）     前面是針對只有兩個類的情況，假設類別變成多個了，那麼要怎麼改變，才能保證投影后類別能夠分離呢？
  • 線性判別分析LDA(Linear Discriminant Analysis)
    線性判別分析（二類情況）回顧我們之前的logistic回歸方法，給定m個n維特徵的訓練樣例（i從1到m），每個x(i)對應一個類標籤。我們就是要學習出參數，使得（g是sigmoid函數）。現在只考慮二值分類情況，也就是y=1或者y=0。為了方便表示，我們先換符號重新定義問題，給定特徵為d維的N個樣例，，其中有個樣例屬於類別，另外個樣例屬於類別。
  • 線性判別分析(LDA)及其在R中實現
    線性判別分析（Linear Discriminant Analysis，LDA）是一種用於數據降維以及分類預測的機器學習方法，由RA Fisher（1936）提出，也稱為Fisher判別式。最初的LDA只能處理兩種分類問題，Rao（1948）拓展了「多類別線性判別分析」或稱「多元判別分析」，將LDA推廣至適用於多分類的情形。
  • 用MATLAB實現簡單的機器學習
    從昨天變清晰的那張圖片開始，一個肥腸簡單的機器學習入門實驗（鬼知道我為什麼敲了一晚上）。
  • 貝葉斯機器學習路線圖
    因子分析(factor analysis)因子分析中, 每個數據點被更低維度的線性函數近似表達. 我們的想法是, 潛在空間(latent space)中每個維度對應一個有意義的因子, 或者數據中變化的維度.隱馬爾科夫模型(hidden Markov models)隱馬爾科夫模型適用於時間序列數據, 其中有一個潛在的離散狀態隨著時間的推移而演變.
  • 機器學習算法一覽(附python和R代碼)
    這篇文章有可能是我寫的所有文章裡最有價值的一篇。寫這篇文章的目的，就是希望它可以讓有志於從事數據科學和機器學習的諸位在學習算法的路上少走些路。我會在文章中舉例一些機器學習的問題，你們也可以在思考解決這些問題的過程中得到啟發。我也會寫下對於各種機器學習算法的一些個人理解，並且提供R和Python的執行代碼。
  • 【R分享|實戰】LDA 線性判別分析
    」   --科白君之前我們分享了不少降維相關的分析方法，例如PCoA，NMDS，PCA分析，它們都是無監督學習。無監督學習指我們事先沒有任何訓練樣本，直接對數據進行建模。無監督學習的主要算法是聚類，聚類目的在於把相似的東西聚在一起，主要通過計算樣本間和群體間距離得到。
  • 10 種機器學習算法的要點
    利用這一系列變量，我們生成一個將輸入值映射到期望輸出值的函數。這個訓練過程會一直持續，直到模型在訓練數據上獲得期望的精確度。監督式學習的例子有：回歸、決策樹、隨機森林、K – 近鄰算法、邏輯回歸等。工作機制：在這個算法中，沒有任何目標變量或結果變量要預測或估計。這個算法用在不同的組內聚類分析。這種分析方式被廣泛地用來細分客戶，根據幹預的方式分為不同的用戶組。
  • 數學推導+純Python實現機器學習算法30:系列總結與感悟
    從第一篇線性回歸的文章開始到現在，已經接近有兩年的時間了。當然，也不是純寫這30篇文章用了這麼長時間，在第14篇Ridge回歸之後中間斷更了10個多月，好在今年抽出時間把全部補齊了。一點總結     整個系列對常用的、主流的機器學習模型與算法進行了梳理，主題只有兩個，一個是數學推導，一個手寫實現。
  • 小白入坑(Majorize-Minimize)MM算法?看這些就夠了!
    期望最大化(EM)算法可以被視為MM算法的特殊情況，在機器學習中經常用到。MM算法與EM算法有聯繫但是又有區別，在EM算法中通常涉及條件期望，而在MM算法中，凸性和不等式是主要焦點。摘自https://blog.csdn.net/ComputingCenter/article/details/80971273https://blog.csdn.net/ComputingCenter/article/details/80971273MM算法用一系列簡單的優化問題代替一個困難的優化問題。
  • 線性模型 || 線性回歸(Linear Regression)算法
    目錄：一、線性模型概念二、LR算法直觀原理三、Python代碼實現算法(notice：1)公式中，字母粗體以示向量2)本文中LR指代Linear Regression，而非Logistic Regression)一、線性模型概念
  • 新手必看的十種機器學習算法
    最常見的機器學習就是學習 Y=f(X) 的映射，針對新的 X 預測 Y。這叫做預測建模或預測分析。我們的目標就是讓預測更加精確。針對希望對機器學習有個基本了解的新人來說，下面將介紹數據科學家們最常使用的 10 種機器學習算法。1.
  • 線性判別分析LDA
    線性判別分析是一種線性降維的方法，和之前ARGO提及的PCA（見文章主成分分析（PCA）入門）目的一樣，都是為了降低海量特徵以實現降維，但兩者又有顯著的不同。全文分成如下四個部分：PCA 回顧線性判別分析（LDA）多類別的線性判別分析使用LDA的限制一  PCA回顧介紹LDA之前，簡單的回顧一下之前講到的PCA。
  • LDA線性判別分析
    問題線性判別分析（二分類情況）PCA和LDALDA降維實例小結　　參考資料問題之前我們討論的 PCA降維，對樣本數據來言，可以是沒有類別標籤 y 的。如果我們做回歸時，如果特徵太多，那麼會產生不相關特徵引入、過度擬合等問題。我們可以使用PCA 來降維，但 PCA 沒有將類別標籤考慮進去，屬於無監督的。
  • 機器學習必學10大算法
    選自Medium作者：garvitanand2機器之心編譯參與：Geek AI、路本文介紹了 10 大常用機器學習算法，包括線性回歸、Logistic 回歸、線性判別分析、樸素貝葉斯、KNN、隨機森林等。1. 線性回歸在統計學和機器學習領域，線性回歸可能是最廣為人知也最易理解的算法之一。
  • 機器學習算法優缺點綜述
    當用於分析因變量和一個 多個自變量之間的關係時，該算法能提供很多建模和分析多個變量的技巧。具體一點說，回歸分析可以幫助我們理解當任意一個自變量變化，另一個自變量不變時，因變量變化的典型值。最常見的是，回歸分析能在給定自變量的條件下估計出因變量的條件期望。回歸算法是統計學中的主要算法，它已被納入統計機器學習。
  • 機器學習算法一覽
    愧疚的是，工作雜事多，加之懶癌嚴重，導致這個系列一直沒有更新，向關注該系列的同學們道個歉。尷尬的是，按理說，機器學習介紹與算法一覽應該放在最前面寫，詳細的應用建議應該在講完機器學習常用算法之後寫，突然莫名奇妙在中間插播這麼一篇，好像有點打亂主線。 老話說『亡羊補牢，為時未晚』，前面開頭忘講的東西，咱在這塊兒補上。我們先帶著大家過一遍傳統機器學習算法，基本思想和用途。