線性判別分析(Linear Discriminant Analysis, LDA）算法分析

一． LDA算法概述：

線性判別式分析(Linear Discriminant Analysis, LDA)，也叫做Fisher線性判別(Fisher Linear Discriminant ,FLD)，是模式識(shí)別的經(jīng)典算法，它是在1996年由Belhumeur引入模式識(shí)別和人工智能領(lǐng)域的。性鑒別分析的基本思想是將高維的模式樣本投影到最佳鑒別矢量空間，以達(dá)到抽取分類信息和壓縮特征空間維數(shù)的效果，投影后保證模式樣本在新的子空間有最大的類間距離和最小的類內(nèi)距離，即模式在該空間中有最佳的可分離性。因此，它是一種有效的特征抽取方法。使用這種方法能夠使投影后模式樣本的類間散布矩陣最大，并且同時(shí)類內(nèi)散布矩陣最小。就是說，它能夠保證投影后模式樣本在新的空間中有最小的類內(nèi)距離和最大的類間距離，即模式在該空間中有最佳的可分離性。

二． LDA假設(shè)以及符號(hào)說明：

假設(shè)對于一個(gè)空間有m個(gè)樣本分別為x1,x2,……xm 即 每個(gè)x是一個(gè)n行的矩陣，其中表示屬于i類的樣本個(gè)數(shù)，假設(shè)有一個(gè)有c個(gè)類，則。

三． 公式推導(dǎo)，算法形式化描述

根據(jù)符號(hào)說明可得類i的樣本均值為：

同理我們也可以得到總體樣本均值：

根據(jù)類間離散度矩陣和類內(nèi)離散度矩陣定義，可以得到如下式子：

當(dāng)然還有另一種類間類內(nèi)的離散度矩陣表達(dá)方式：

我們可以知道矩陣 的實(shí)際意義是一個(gè)協(xié)方差矩陣，這個(gè)矩陣所刻畫的是該類與樣本總體之間的關(guān)系，其中該矩陣對角線上的函數(shù)所代表的是該類相對樣本總體的方差（即分散度），而非對角線上的元素所代表是該類樣本總體均值的協(xié)方差（即該類和總體樣本的相關(guān)聯(lián)度或稱冗余度），所以根據(jù)公式（3）可知（3）式即把所有樣本中各個(gè)樣本根據(jù)自己所屬的類計(jì)算出樣本與總體的協(xié)方差矩陣的總和，這從宏觀上描述了所有類和總體之間的離散冗余程度。同理可以的得出（4）式中為分類內(nèi)各個(gè)樣本和所屬類之間的協(xié)方差矩陣之和，它所刻畫的是從總體來看類內(nèi)各個(gè)樣本與類之間（這里所刻畫的類特性是由是類內(nèi)各個(gè)樣本的平均值矩陣構(gòu)成）離散度，其實(shí)從中可以看出不管是類內(nèi)的樣本期望矩陣還是總體樣本期望矩陣，它們都只是充當(dāng)一個(gè)媒介作用，不管是類內(nèi)還是類間離散度矩陣都是從宏觀上刻畫出類與類之間的樣本的離散度和類內(nèi)樣本和樣本之間的離散度。

LDA做為一個(gè)分類的算法，我們當(dāng)然希望它所分的類之間耦合度低，類內(nèi)的聚合度高，即類內(nèi)離散度矩陣的中的數(shù)值要小，而類間離散度矩陣中的數(shù)值要大，這樣的分類的效果才好。

這里我們引入Fisher鑒別準(zhǔn)則表達(dá)式：

其中 為任一n維列矢量。Fisher線性鑒別分析就是選取使得達(dá)到最大值的矢量作為投影方向，其物理意義就是投影后的樣本具有最大的類間離散度和最小的類內(nèi)離散度。

我們把公式（4）和公式（3）代入公式（5）得到：

四． 算法的物理意義和思考

4.1 用一個(gè)例子闡述LDA算法在空間上的意義

下面我們利用LDA進(jìn)行一個(gè)分類的問題：假設(shè)一個(gè)產(chǎn)品有兩個(gè)參數(shù)來衡量它是否合格，

我們假設(shè)兩個(gè)參數(shù)分別為：

所以我們可以根據(jù)上圖表格把樣本分為兩類，一類是合格的，一類是不合格的，所以我們可以創(chuàng)建兩個(gè)數(shù)據(jù)集類：

cls1_data =

2.9500    6.6300

2.5300    7.7900

3.5700    5.6500

3.1600    5.4700

cls2_data =

2.5800    4.4600

2.1600    6.2200

3.2700    3.5200

其中cls1_data為合格樣本，cls2_data為不合格的樣本，我們根據(jù)公式（1），（2）可以算出合格的樣本的期望值，不合格類樣本的合格的值，以及總樣本期望：

E_cls1 =

3.0525    6.3850

E_cls2 =

2.6700    4.7333

E_all =

2.8886    5.6771

我們可以做出現(xiàn)在各個(gè)樣本點(diǎn)的位置：

圖一

其中藍(lán)色‘*’的點(diǎn)代表不合格的樣本，而紅色實(shí)點(diǎn)代表合格的樣本，天藍(lán)色的倒三角是代表總期望，藍(lán)色三角形代表不合格樣本的期望，紅色三角形代表合格樣本的期望。從x，y軸的坐標(biāo)方向上可以看出，合格和不合格樣本區(qū)分度不佳。

我們在可以根據(jù)表達(dá)式（3），（4）可以計(jì)算出類間離散度矩陣和類內(nèi)離散度矩陣：

Sb =

0.0358    0.1547

0.1547    0.6681

Sw =

0.5909   -1.3338

-1.3338    3.5596

我們可以根據(jù)公式（7），（8）算出 特征值以及對應(yīng)的特征向量：

L =

0.0000         0

0    2.8837

對角線上為特征值，第一個(gè)特征值太小被計(jì)算機(jī)約為0了

與他對應(yīng)的特征向量為

V =

-0.9742   -0.9230

0.2256   -0.3848

根據(jù)取最大特征值對應(yīng)的特征向量：（-0.9230,-0.3848)，該向量即為我們要求的子空間，我們可以把原來樣本投影到該向量后 所得到新的空間（2維投影到1維，應(yīng)該為一個(gè)數(shù)字）

new_cls1_data =

-5.2741

-5.3328

-5.4693

-5.0216

為合格樣本投影后的樣本值

new_cls2_data =

-4.0976

-4.3872

-4.3727

為不合格樣本投影后的樣本值，我們發(fā)現(xiàn)投影后，分類效果比較明顯，類和類之間聚合度很高，我們再次作圖以便更直觀看分類效果

圖二

藍(lán)色的線為特征值較小所對應(yīng)的特征向量，天藍(lán)色的為特征值較大的特征向量，其中藍(lán)色的圈點(diǎn)為不合格樣本在該特征向量投影下來的位置，二紅色的‘*’符號(hào)的合格樣本投影后的數(shù)據(jù)集，從中個(gè)可以看出分類效果比較好（當(dāng)然由于x，y軸單位的問題投影不那么直觀）。

我們再利用所得到的特征向量，來對其他樣本進(jìn)行判斷看看它所屬的類型，我們?nèi)颖军c(diǎn)

（2.81，5.46），

我們把它投影到特征向量后得到：result = -4.6947 所以它應(yīng)該屬于不合格樣本。

4.2 LDA算法與PCA算法

在傳統(tǒng)特征臉方法的基礎(chǔ)上，研究者注意到特征值打的特征向量（即特征臉）并一定是分類性能最好的方向，而且對K-L變換而言，外在因素帶來的圖像的差異和人臉本身帶來的差異是無法區(qū)分的，特征連在很大程度上反映了光照等的差異。研究表明，特征臉，特征臉方法隨著光線，角度和人臉尺寸等因素的引入，識(shí)別率急劇下降，因此特征臉方法用于人臉識(shí)別還存在理論的缺陷。線性判別式分析提取的特征向量集，強(qiáng)調(diào)的是不同人臉的差異而不是人臉表情、照明條件等條件的變化，從而有助于提高識(shí)別效果。