基于類內加權的線性判別分析改進算法?

呂琳 劉杰

（91388部隊91分隊 湛江 524022）

1 引言

在模式識別中，由被識別的對象產生一組基本特征，當待識別對象是波形或者數字圖像時，這些特征可以通過計算得到；當待識別對象是實物或者某種過程時，需要用儀表或者傳感器測量出來，這些產生的特征稱為原始特征。一般情況下，得到的原始特征的數量會非常大，即樣本處于高維空間，這樣不利于后續的分類識別計算，所以如何將特征從高維空間映射到低維空間是模式識別中的一個關鍵問題，這個映射的過程叫做特征提取。目前，較常用的特征提取方法有主成分分析（Principal Component Analysis，PCA）［1～2］方法和線性判別分析（Linear Discriminant Analysis ，LDA）［3～8］方法，這兩種算法都是基于統計的特征提取方法，通過對大量訓練樣本數據進行分析，提取相應的統計特征，已廣泛應用于模式識別、數據分析等領域。PCA方法能夠有效的去除噪聲和降低特征的維數，但是它提取的只是樣本的最佳描述特征，并不是最好的分類特征，而LDA算法是以樣本的可分性為目標的一種特征提取方法，所以在模式識別中，理論上LDA算法要優于PCA算法，但是傳統的LDA算法在求解映射子空間的時候，假設各類散布矩陣相同，散布矩陣進行平均計算，沒有考慮到類內和類間分布的關系，本文針對這個問題提出了類內加權的LDA算法，更好地提取待識別對象的分類特征。

2 LDA算法

LDA算法的原理就是尋找一個投影方向，所有樣本在這個方向的投影能夠實現類間離散度最大化和類內離散度最小化，即能夠使同類樣本盡量聚集，不同類樣本盡量分開，是一種以分類識別為目的的特征提取方法，和傳統的基于主成分分析（PCA）的特征提取方法相比，使用LDA提取后的特征具有更強的分類能力，有利于目標的分類識別，圖1給出了PCA和LDA分別在兩類問題上求解投影子空間的情況，從中可以看出，經過LDA投影后的子空間分類能力明顯好于經過PCA投影后的子空間。

因為LDA使用的是Fisher準則函數，所以LDA也稱為Fisher線性判別分析（FDA）［9～12］。Fisher準則函數為

W表示投影方向，Sb表示類間離散度矩陣，Sw表示類內離散度矩陣。Sb和Sw的定義分別如式（2）和式（3）。

C 表示樣本的類別數，Ni(i=1，2，…，C)表示第i類樣本的數目，表示所有樣本的均值向量，N表示樣本總數目，xj表示第 j個樣本向量，Xi表示第i類樣本，表示第i類的第k個樣本向量，表示第i類樣本的均值向量。

圖1 PCA和LDA對兩類問題投影子空間求解的比較

式（1）可以用拉格朗日乘子求解，令WTSwW=ξ≠0，構造拉格朗日函數：

λ表示拉格朗日乘子，式4對W求偏導得：

令其偏導數等于0得：

W′表示式（1）中 j(W)取得最大值時的W ，在Sw非奇異的情況下，式（6）兩邊同乘得：

所以就是求解Sw-1Sb的特征值問題，W′就是由最大的m(m≤n)個特征值對應的特征向量組成，n表示樣本維數。

3 F-LDA算法

傳統的LDA算法在求解投影子空間的時候認為所有訓練樣本對分類的貢獻都是一樣的，沒有考慮邊緣樣本的存在，實際上不同的訓練樣本在求解投影子空間的時候應該具有不同的作用。一部分樣本由于和其他類的差別比較大，和同類之間的差別比較小，能夠很好地被區分，而一部分樣本與其他類的差別比較小，和同類之間的差別比較大，難以被區分，這些難以區分的樣本稱為邊緣樣本，為了提高對邊緣樣本的區分能力，Rohit和Ravi提出了F-LDA（Fractional-Step Linear Discriminant Analysis）算法。

F-LDA算法就是在求解類間離散度矩陣Sb的時候加入權重，Sb重新定義成如下的形式：

μk和 μl分別為第k類和第l類樣本特征向量的均值，dkl=‖‖μk-μl表示第k類樣本平均值和第l類樣本平均值之間的歐氏距離，w(dkl)=(dkl)-2p(p=2，3，…)用于歐式加權，可以看出，權重的大小與兩類樣本間的距離成反比，這樣可以增強投影子空間對難以區分的邊緣類的區分能力。一般情況下 p取2或者3。

4 類內加權的LDA改進算法

對LDA的類內協方差矩陣進行加權改進，將式（3）的類內協方差矩陣Sw重新定義為S?w：

在LDA中，我們希望類間盡量離散，類內盡量聚合，在同一類樣本中，如果dki較小的話，說明樣本聚合力強，能夠較好的區分開，反之則表示為邊緣樣本，不能較好地區分，使用與dki成正比的w(dki)進行加權，就可以對那些已經能夠很好區分的樣本降低權重，對不能很好區分的樣本增加權重，提高其分類能力。當 p=0的時候，改進的LDA算法等同于傳統的LDA算法，在這里 p一般取小于1的值效果較好，本文中 p取0.2，不同 p值對分類能力的影響如圖3所示。。

5 實驗與結果

本文使用模擬數據進行實驗，測試集共包含六種類型的二維數據集。每一類數據都服從高斯分布，其協方差矩陣為0.04I（I表示單位矩陣），包含100個二維數據。每一類數據的中心點分別為［0.1，0］，［-0.1，0］，［-1，1］，［1，-1］，［-0.5，-0.5］，［0.5，0.5］，如圖2所示。

圖2 實驗模擬數據分布圖

使用不同的 p值在模擬數據測試集上測試內類加權LDA算法的分類正確率，結果如圖3所示。

圖3 內類加權LDA算法中P值對分類識別效果的影響

下面分別使用LDA、F-LDA和類內加權LDA求解投影子空間，然后在模擬測試集上進行測試，其中F-LDA中 p的值取2，使用投影子空間得到的分類結果分別如圖4、圖5、圖6所示。

圖4 使用傳統LDA算法的分類結果

圖5 使用F-LDA算法的分類結果（p=2）

圖6 使用類內加權LDA算法的分類結果（p=0.2）

從結果看，傳統的LDA算法能夠很好地對大部分樣本進行區分，但是對于不同類樣本之間的重疊部分，即對邊緣類的分類能力不理想，F-LDA算法在一定程度上克服了傳統LDA算法在邊緣類分類問題上的不足，本文提出的類內加權LDA算法則進一步提高了算法對邊緣類的分類能力。

6 結語

本文在詳細闡述了LDA算法，分析了傳統LDA算法在求解投影子空間的時候存在的不足，提出了類內加權LDA改進算法，通過在模擬數據上與傳統LDA算法、F-LDA算法的實驗對比，可以得出改進算法在一定程度上提高了對邊緣樣本的分類能力，同時，分類效果會受到權重系數的影響，在實際使用中，需要通過調整值來得到最好的分類投影子空間。