基于自權值線性判別分析算法的圖像處理研究

陸榮秀，蔡瑩杰，朱建勇，楊 輝

（華東交通大學電氣與自動化工程學院，江西 南昌330013）

在機器學習和模式識別領域中，降維是分析高維數據的一項重要方法。 在各類降維算法中，主成成分分析（principle component analysis，PCA）[1]和線性判別分析（linear discriminant analysis，LDA）[2]是運用最為廣泛的兩種降維算法。 其中，PCA 是一種無監督的算法，而LDA 則利用了樣本的標簽信息，是一種監督學習算法，LDA 的目標是學習一個映射矩陣使得類內散度最小化的同時最大化類間散度矩陣。 但是傳統的LDA 仍然存在以下缺點：第一，當數據維度遠遠超過訓練樣本時，類內散度矩陣將會變成奇異矩陣，這會導致小樣本問題[3-5]，所以傳統的LDA 不適用于超高維的數據樣本；第二，傳統的LDA 假設輸入的數據是符合高斯分布的，但是現實世界中的真實數據往往是呈多模態的非高斯分布[6-8]，傳統LDA 算法往往在處理非高斯分布的數據時不能夠很好地捕捉到隱含在數據內部的局部流形結構，導致降維效果不佳。

而對于非高斯分布的多模態數據，要從高維空間映射到低維空間中且不丟失原始數據的信息，最重要的是保證數據在從高維空間嵌入到低維空間的過程中能夠保留數據的局部流形結構。 為此，許多科研工作者做了很多算法研究，其中最具有代表性的算法就是局部保持映射（locality preserving projection，LPP）[9]，該算法是讓在原始空間中鄰近成對的樣本點在嵌入到低維子空間時樣本點之間盡可能相互靠近，考慮了樣本之間的相似性，從而使得非高斯分布的數據在映射到低維的子空間的過程中能夠保留隱含在數據內部的局部流形結構。但是LPP 是一種無監督的學習算法，沒有利用數據的標簽信息，在一定程度上限制了其降維的性能。

基于以上的分析，本文提出了一種改進的線性判別分析算法，該算法在傳統的LDA 的基礎上，通過分析傳統的LDA 算法不同形式的目標函數，利用樣本對之間在數據空間里的距離分布，提出了一種自權值線性判別分析算法。 算法的主要思想是通過將輸入數據在原始空間中的距離分布轉換成其對應樣本點之間的權值，對樣本點之間的相似性與差異性進行區分，以保留隱含在數據內部的局部流形結構，從而改變了傳統LDA 賦予樣本相同權值的形式，也就是說，在改進的自權值LDA 算法中，當兩個樣本在原始空間的距離相近時，則樣本對之間會被賦予較大的權值，這表明其在原始空間中的相似度越大，反之則賦予較小的權值，表明相似度越小。 從而使得數據從高維空間映射到低維子空間的過程中能夠考慮樣本點之間的差異性，抽取更多的數據局部結構信息， 發現數據內部中隱含的局部流形結構。 通過對傳統的LDA 和改進的自權值LDA 算法在人工合成數據和真實數據上的實驗對比分析， 結果表明改進的自權值LDA 算法相比于比于傳統的LDA 算法，改進的自權值LDA 能夠在一定程度上提高模型對非高斯分布的。

1 線性判別分析

線性判別分析算法是機器學習和模式識別領域廣泛應用的降維方法， 其有效利用了樣本的標簽信息，屬于有監督的學習算法。 本節將歸納總結傳統線性判別分析算法的模型以及其對應的常規求解方法。

1.1 傳統的LDA

給定一個數據矩陣X=[x1，x2，…，xl]∈Rd×l，LDA 的目的是學習一個線性轉換矩陣，通過轉換矩陣W∈Rd×m將d 維的數據xj映射到m 維子空間yj∈Rm（d＞m），使得樣本點在低維空間中同類樣本之間相互靠近，不同類之間的樣本點相互遠離。 數據映射關系表達式如下

式中：xj表示第j 個樣本， LDA 假設最優的轉換矩陣應該最小化類內散度的同時最大化類間散度。因此不失一般性，傳統的LDA 的目標函數如下所示

式中：類內散度矩陣Sw以及總的散度矩陣St定義為

在目標函數式（2）中，為了確保解的唯一性，通常會對LDA 施加正交限制，則式（2）中施加了正交限制的LDA 目標函數為

將式（5）寫成向量形式

對于比跡形式的LDA 目標函數，式（5）通常可以通過廣義特征值分解（generalized eigenvalue decomposition，GEVD）[10]進 行 求解，最優的轉換矩陣W 可以通過進行以下的特征值分解得到

則最優的轉換矩陣W 由St-1Sw中k 個最小的特征值所對于的特征向量組成，即W=[w1，w2，…，wk]。

2 改進的自權值LDA 算法

在模式識別領域中，越來越多的降維技術被運用于圖片處理領域[11-15]，例如人臉圖片，醫學影像圖片[16]等。 LDA 是目前應用最廣泛的圖片降維技術之一，但是傳統的LDA 只適合于處理高斯分布的數據，也就是說傳統的LDA 是賦予類內樣本點相同的權值，這使得LDA 讓相互遠離的成對的樣本點相互靠近，因此傳統的LDA 對處理高斯分布的數據具有很好的效果。

但是對于非高斯分布的數據，傳統的LDA 則難以發現隱含在數據內部的流形結構，從而導致降維效果不佳。 這主要是因為傳統的LDA 算法在數據點從高維空間嵌入到低維空間的過程中沒有考慮樣本間的相似性和差異性，最終使學習的映射矩陣不能完全辨識樣本之間的判別信息。 因此本文針對傳統的LDA 無法辨識樣本對之間的相似性與差異性的問題，通過將樣本對之間的距離分布轉換為樣本對之間的權值，以區分樣本對之間的差異性,基于以上的分析并結合式（6），本文改進的自權值LDA 的目標函數定義如下

2.1 目標函數的求解

在上一節中，本文通過在傳統的LDA 模型的基礎上，改進了其不能區分樣本點之間差異性的問題并定義了基于自權值的LDA 目標函數。 這一節，本文將介紹對改進的自權值LDA 模型的求解過程。

首先在求解式（9）時，先計算樣本之間的權值系數，同類樣本之間的權值系數為pijk，不同類的樣本的權值設置為0，所以當權值系數已知時，基于自權值LDA 算法的總的散度矩陣S~t和類內散度S~w定義為

根據式（11），式（9）可以進一步寫成其矩陣的形式

其中Tr（·）表示矩陣的跡，式（12）可以進一步化簡為

其中

式中：L=D-A 為拉普拉斯矩陣， 其中A 為對稱矩陣，D 為對角矩陣，D 的對角元素為對應A 的每列列和，A表達式如下：

其中πk表示第k 類樣本，權值系數pijk可由樣本點計算得到，則根據式（5），最終式（13）中的映射矩陣可以通過求解以下的廣義特征值問題得到

輸入：數據矩陣X∈Rd×n，標簽：y∈Rm降維的維數為m。

1） 計算樣本對之間的權值系數pijk；

3 實驗

3.1 實驗設置

為了有效的分析改進的自權值算法的降維性能，設置的實驗主要由三部分組成，第一部分主要是針對于人工數據，用隨機生成的符合高斯分布的數據和非高斯分布的數據，來可視化檢驗傳統的LDA 以及改進的自權值LDA 的降維效果。 第二部分主要為常見的UCI 數據集， 對比的算法分別是相關傳統的降維算法LDA 和LPP ；第三部分實驗主要為人臉圖片，對比的算法為傳統的LDA 算法。 實驗中我們隨機從每個類中選擇相同比例的樣本用作訓練集，其余的樣本用于測試集，訓練集的比例設置為0.5。 另外，采用PCA 預處理以保留所有數據的95% 信息以便刪除數據協方差矩陣的零空間。 實驗中， 使用k 最近鄰 （k-Nearest-Neighbor，kNN）（k=1）分類器對樣本進行預測分類。 每次實驗隨機分割數據集進行預測，分別進行20 次。 不同算法在不同維度的預測正確率如圖2 所示，在所有的降維維度中，預測的最好的平均正確率的維度及其標準偏差如表4 和表5 所示。

3.2 數據集描述

3.2.1 實驗二數據集介紹

實驗二選取了6 個數據集， 在表2 中給出， 分別是：Control，Segment，Dermatology，Letter，Mnist，USPS。Dermatology 為皮膚病學數據集，這個數據庫包含34 個屬性，其中33 個是線性值，一個是標稱值。Mnist 標準的手寫數字數據庫,它包含3 495 張手寫數字圖片共10 類，每張圖片的為784 個像素點。 USPS 是美國郵政USPS 的手寫數據集，它包含9 298 張手寫數字圖片共10 類，每張圖片的大小為16×16 個像素點。 關于不同數據集的具體描述如表1 所示。

表1 UCI 數據集描述Tab.1 UCI data set description

3.2.2 實驗三人臉數據集介紹

實驗三的人臉數據集在表4 中給出, 分別是AR， FERET， MSRA25， ORL，Umist，YaleFace。各個數據集的簡短介紹如下：

AR 數據集包含超過4 000 張彩色圖像，對應126 張人臉，圖像具有不同面部表情、照明條件和遮擋的正面視圖臉。 FERE 是一個標準的面部圖像數據庫，它共收集了14 126 張圖像，涉及1 199 個人。 它包含20類共574 張人臉圖片，每張圖片的像素點10 304 個像素點。MSRA25 包含12 個受試者的1 799 張臉部灰度圖片，每一類中有113～186 張不同姿勢的照片。每張圖片的像素點是16×16 像素。ORL 共包含40 個不同人的400 張圖像。 每張圖片的像素點是32×32 像素。 Umist 人臉數據庫由564 張20 人的圖像組成。 每個人都以從側面到正面的一系列姿勢。YaleFace 人臉數據庫包含165 張15 人的GIF 格式灰度圖像。每個受試者有11 個圖像。 關于不同數據集的具體描述如表2 所示。

表2 人臉數據集描述Tab.2 Face data set description

3.3 實驗結果與分析

為了體現提出的算法的有效性,本文分別用人工數據，常規的UCI 數據集以及人臉數據集分別對模型性能進行評估，在實驗中本文對比了3 種相關的降維算法，分別是LDA，LPP。其中LDA 是監督的降維算法，LPP 是無監督的降維算法。

在實驗結果中，人工數據實驗的結果如圖1 所示，圖1 中虛線代表的是LDA 求解的投影方向，實線代表的是改進的算法求解的投影方向。 圖1（a）中的數據為人工隨機生成的高斯分布數據，圖1（b）中的數據則是非高斯分布的人工數據。從圖中可以看出，對于高斯分布的數據，LDA 和改進的新算法所學習的映射方向基本一致，而對于處理非高斯分布的數據， LDA 學習的投影方向會出現許多樣本的重疊，這說明加入了自權值后得新算法相比于傳統的LDA 很好的保留了數據局部的幾何結構。

UCI 數據實驗結果如表3，圖2 所示，在圖2 中，軸表示降維的維度，x 軸為分類的正確率，分類器為k最近鄰（kNN）（k=1）分類器。OUR 代表的是改進的算法，LDA，LPP 為相關的對比算法。 實驗的數據集如表3所示，每種算法在不同的數據集中最好的分類正確率以及標準差如表2 所示，在不同的降維維度不同算法的正確率如圖2 所示。

圖1 改進的LDA 與傳統LDA 在高斯分布與非高斯分布的人工數據上學習投影效果Fig.1 The proposed LDA and the traditional LDA learning projection results on the artificial data of Gaussian distribution and non-Gaussian distribution

圖2 UCI 數據在不同對比算法中不同降維維度上的平均正確率Fig.2 Average accuracy of UCI data with different dimension reduction in different comparison algorithms

表3 UCI 數據集識別的平均正確率(均值±標準差)，最好的預測結果用黑體加粗Tab.3 The average accuracy of UCI dataset identification (mean ± standard deviation (reduction dimension), and the best prediction results in bold

人臉圖片數據實驗結果如表4 所示， OUR 代表的是改進的線性判別分析算法， LDA 代表的是傳統的線性判別分析算法。baseline 表示的是沒有經過降維處理所分類的正確率。實驗中所用的人臉數據集在表3中給出。 從以上的實驗結果中，本文可以得出以下結論：

表4 人臉數據集識別的平均正確率（均值±標準差（降維維度）），最好的預測結果用黑體加粗Tab.4 The average accuracy ofFace dataset identification （mean ± standard deviation （reduction dimension）），and the best prediction results in bold

1） 從圖1 中的人工數據實驗可以看出，對于高斯分布的數據， LDA 和新算法都能有較好的表現，而對于處理非高斯分布的數據，傳統的LDA 表現性能不佳，學習的映射方向經過樣本點的投影后出現了許多樣本點的重疊，而新算法則很好的保留了數據的局部幾何結構,體現了改進的自權值LDA 算法對非高斯數據的處理能力。

2） 從表4 中可以看出，改進的線性判別分析算法的預測最佳正確率均高于傳統的降維算法，這表明改進的算法在加入了自權值的特性后，能夠抽取樣本點之間更多的判別信息，提高了降維性能。

3） 從圖2 中可以看出，對于Mnist 數據集，改進的算法與LPP 的表現整體好于傳統的LDA 算法，這表明相比于傳統的LDA 算法， 改進的線性判別分析算法和LPP 都能夠通過區分樣本間的相似性與差異性提高降維性能，而對于Control, Mnist, USPS 數據集等，改進的算法和LDA 的表現則整體好于LPP，這是因為LPP 是無監督的學習算法，它沒有利用標簽信息，而改進的新算法則是附帶有權值的監督學習算法，充分的利用了樣本的標簽信息，因此整體的表現性能更好。

4） 從表4 中可以看出，在6 個人臉數據集中，改進的模型只有在YaleFace 的數據集上的分類正確率略低于傳統的LDA，在其他人臉數據集上，改進的模型的預測分類正確率均優于傳統LDA。這表明改進的新算法由于考慮了樣本之間的相似性與差異性，從而使得新模型能夠在樣本點從高維空間嵌入到低維空間的過程中考慮隱含在數據內部的流形結構，因此整體性能得到改善。

4 結論

本文針對傳統的線性判別分析（LDA）算法未考慮數據從高維空間嵌入到低維空間中的局部流形結構，在處理非高斯分布數據時不能取得較好效果的問題，提出了一種新的監督降維的算法，利用數據在原始空間的距離分布，將樣本間的距離分布大小轉換為樣本對之間的權值來用作區分樣本間的差異性，從而使得數據從高維空間映射到低維空間中能夠保留數據中的局部幾何結構， 使得新的模型相比傳統LDA 算法不僅適用高斯分布的數據，同樣也適用于非高斯分布的數據。 大量的實驗表明改進的新算法相比于傳統的線性判別分析算法能夠更好的抽取數據局部的流形結構，也充分驗證了新算法的有效性。