面向局部線性回歸分類器的判別分析方法

朱換榮，鄭智超，孫懷江

（南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 210094）

維數(shù)約簡(jiǎn)是幫助我們理解數(shù)據(jù)特征結(jié)構(gòu)的有效工具，被廣泛地應(yīng)用于人臉識(shí)別[1-3]、圖像檢索[4-5]、指紋認(rèn)證[6-7]、生物信息學(xué)[8-9]、數(shù)據(jù)挖掘[10-11]等。維數(shù)約簡(jiǎn)的目標(biāo)是減少冗余、不相關(guān)的信息和噪聲，同時(shí)保留數(shù)據(jù)的潛在結(jié)構(gòu)和本征信息。文獻(xiàn)[12]顯示，雖然隨著樣本維數(shù)的增加，分類器的性能會(huì)逐步上升，但是過高的維數(shù)卻會(huì)使分類器的性能急劇下降，甚至造成“維數(shù)災(zāi)難”問題。因此，維數(shù)約簡(jiǎn)對(duì)于分類具有重要的意義。在過去的幾十年中，針對(duì)維數(shù)約簡(jiǎn)問題出現(xiàn)了各種不同的解決方案和算法，其中主成分分析[13](principal component analysis，PCA)和線性判別分析[14](linear discriminant analysis，LDA)是最具代表性的兩個(gè)線性降維算法。PCA的思想是最大化投影空間中樣本之間的差異。LDA的目標(biāo)是找到一組投影軸，使得在投影空間中同類樣本盡可能靠近，而不同類樣本盡可能分開。LDA是一種監(jiān)督算法，充分利用了樣本的類別信息來發(fā)現(xiàn)數(shù)據(jù)的特征結(jié)構(gòu)，因此在維數(shù)約簡(jiǎn)方面通常比PCA更加有效，但是LDA不能很好地處理非線性分類問題。流形學(xué)習(xí)[15](manifold learning)是一種非線性的維數(shù)約簡(jiǎn)方法。流形算法的主要思想是學(xué)習(xí)高維空間中樣本的局部鄰域結(jié)構(gòu)，并尋找能夠保留這種流形結(jié)構(gòu)的子空間，使得樣本投影到子空間后有著較好的局部近鄰關(guān)系。其中局部保持投影[15](locality preserving projections，LPP)就是最常見的流形學(xué)習(xí)算法之一。LPP方法得到的投影矩陣，可以使樣本在投影之后保留鄰域結(jié)構(gòu)。

近年來，基于表示的分類方法引起了人們的廣泛關(guān)注，稀疏表示分類器[16](sparse representation based classification，SRC)是最具代表性的基于表示的分類方法之一。SRC中測(cè)試樣本用訓(xùn)練樣本的稀疏線性組合來表示，然后計(jì)算測(cè)試樣本與每類樣本之間的重構(gòu)誤差，最終將測(cè)試樣本分類到重構(gòu)誤差最小的類別。SRC表現(xiàn)出了良好的分類性能，但是由于SRC計(jì)算稀疏表示系數(shù)需要求解范數(shù)，所以花費(fèi)的時(shí)間較多。而線性回歸分類器[17](linear regression classification，LRC)則很好地避免了這一問題。LRC假設(shè)同一類的樣本處于相同的線性子空間中。因此LRC分別計(jì)算測(cè)試樣本在不同類的子空間中的投影，然后通過計(jì)算最小重構(gòu)誤差來判別測(cè)試樣本的類別。LRC利用最小二乘法估算回歸系數(shù)，所以LRC是一個(gè)簡(jiǎn)單而有效的分類方法。然而，在許多現(xiàn)實(shí)應(yīng)用中，樣本通常表現(xiàn)出局部線性，而不是全局線性。于是Brown等[18]提出了局部線性回歸分類器(locality-regularized linear regression classification，LLRC)，將流形學(xué)習(xí)系統(tǒng)嵌入到LRC中，使用流形學(xué)習(xí)來擴(kuò)展傳統(tǒng)的LRC，從而提高分類精度。

為了防止過高的維數(shù)影響LLRC的分類性能并且保留數(shù)據(jù)的潛在結(jié)構(gòu)，所以在使用原始數(shù)據(jù)時(shí)先進(jìn)行降維處理。大多數(shù)的降維方法獨(dú)立于分類器的決策準(zhǔn)則，因此分類器往往不能有效地利用學(xué)習(xí)到的特征子空間。為了更好地將維數(shù)約簡(jiǎn)與特定的分類器相聯(lián)系，根據(jù)分類器的決策準(zhǔn)則來設(shè)計(jì)維數(shù)約簡(jiǎn)算法是很有必要的。于是，Huang等[19]根據(jù)LLRC的決策準(zhǔn)則提出了局部線性回歸判別分析(locality-regularized linear regression discriminant analysis，LLRDA)。LLRDA 根據(jù)LLRC的決策準(zhǔn)則分別定義了類內(nèi)局部重構(gòu)誤差和類間局部重構(gòu)誤差，然后使用最大特征值分解方法求解一個(gè)跡比問題以得到最優(yōu)解。然而，在LLRDA算法中，線性回歸系數(shù)在原始空間進(jìn)行計(jì)算并且假定系數(shù)恒定，但是實(shí)際上回歸系數(shù)與投影矩陣是相關(guān)的，不是獨(dú)立的，在求解目標(biāo)函數(shù)的過程中投影矩陣的改變會(huì)對(duì)回歸系數(shù)產(chǎn)生影響，所以不能假定系數(shù)恒定。另外，LLRDA的目標(biāo)函數(shù)是一個(gè)跡比問題，但是為了便于處理，LLRDA將跡比問題隱式地轉(zhuǎn)換成了比跡問題，并用最大特征值分解方法進(jìn)行求解，因而得到的結(jié)果會(huì)與原來的目標(biāo)函數(shù)存在偏差。

為了克服LLRDA的缺點(diǎn)，本文提出了面向局部線性回歸分類器的判別分析方法(localityregularized linear regression classification based discriminant analysis，LLRC-DA)。LLRC-DA 根據(jù)LLRC的決策準(zhǔn)則設(shè)計(jì)目標(biāo)函數(shù)，通過最大化類間局部重構(gòu)誤差并最小化類內(nèi)局部重構(gòu)誤差來尋找最優(yōu)的特征子空間。在求解目標(biāo)函數(shù)的過程中，本文利用投影矩陣與線性回歸系數(shù)之間的關(guān)系，使用解析解表示線性回歸系數(shù)，從而消除了回歸系數(shù)對(duì)求解投影矩陣產(chǎn)生的影響。另外，在求解目標(biāo)函數(shù)過程中使用了一種新的跡比優(yōu)化方法，直接解決跡比問題而不是使用廣義特征值分解的方法近似求解。文獻(xiàn)[20]的研究顯示，直接解決跡比問題是可行的并且比使用廣義特征值分解效果更好。在本文提出的方法中，使用了正交投影來消除冗余信息，提高性能。本文在FERET、ORL人臉庫(kù)上進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。

1 局部線性回歸分類器

2 LLRC-DA算法

2.1 LLRC-DA提出

LLRC-DA的目標(biāo)是將樣本投影到一個(gè)特征子空間，使得類內(nèi)局部重構(gòu)誤差最小，同時(shí)類間局部重構(gòu)誤差最大。用表示優(yōu)化投影矩陣，原始空間中的訓(xùn)練樣本矩陣投影到維子空間為，即每個(gè)訓(xùn)練樣本投影為，其中表示第i類的第個(gè)訓(xùn)練樣本。線性回歸系數(shù)是通過式(2)來計(jì)算得到的。

同樣地，在特征子空間中，可以計(jì)算類間局部重構(gòu)誤差，即

2.2 LLRC-DA優(yōu)化

LLRC-DA是一個(gè)跡比最小化問題，通常此類問題可以使用廣義特征值分解的方法近似求解。最近的研究顯示[20]，直接解決跡比問題是可行的并且比使用廣義特征值分解效果更好。

其中：

因?yàn)槟繕?biāo)函數(shù)要在正交約束條件下進(jìn)行求解，所以首先要對(duì)其進(jìn)行求導(dǎo)。對(duì)求導(dǎo)得

3 實(shí)驗(yàn)

為了驗(yàn)證LLRC-DA的有效性，本文分別在FERET和ORL人臉庫(kù)上進(jìn)行實(shí)驗(yàn)，并與PCA[13]、LDA[14]、LPP[15]、RDA[24]和 LLRDA[19]等先進(jìn)的維數(shù)約簡(jiǎn)算法進(jìn)行比較。在維數(shù)約簡(jiǎn)之后，分別使用 NNC[25]、MDC[26]、LRC[17]和 LLRC[18]分類器來比較每種維數(shù)約簡(jiǎn)方法在不同分類器下的分類性能。本文中的實(shí)驗(yàn)通過MATLAB編程實(shí)現(xiàn)，硬件環(huán)境為酷睿i7處理器、主頻2.6 GHz、內(nèi)存8 GB。

3.1 FERET人臉庫(kù)上的實(shí)驗(yàn)

FERET人臉庫(kù)包含1 400幅人臉圖像，共計(jì)200類，其中每類7幅圖像，包括兩張面部表情圖，兩張左側(cè)圖，兩張右側(cè)圖和一張光照?qǐng)D，圖1所示為一個(gè)人的7幅圖像。實(shí)驗(yàn)中所有的圖像均被裁剪為 80像素像素。在實(shí)驗(yàn)之前，首先使用PCA方法將原始圖像降到180維，然后在每類中選擇前4幅圖像作為訓(xùn)練集，剩余的作為測(cè)試集，最近鄰類，每類中的最近鄰個(gè)數(shù)，在FERET上的識(shí)別率如表1所列。

圖1 FERET庫(kù)中一個(gè)人的7幅圖像Fig. 1 Seven images of a person from the FERET database

表1 FERET庫(kù)上的識(shí)別率Table 1 Recognition accuracy when using the FERET database

通過表1可以看出：1)與PCA、LPP等非監(jiān)督學(xué)習(xí)方法相比，監(jiān)督學(xué)習(xí)的降維方法明顯具有更好的性能，因?yàn)楸O(jiān)督學(xué)習(xí)方法利用了類別信息，使識(shí)別率顯著提高；2)同一種降維方法，在不同的分類器上的實(shí)驗(yàn)結(jié)果不同，甚至?xí)泻艽蟛町悾鏛LRC-DA在MDC與LLRC這兩種分類器上的識(shí)別率相差很大，這也說明選擇合適的分類器對(duì)于識(shí)別性能至關(guān)重要；3)在所有的降維方法與分類器的組合中，LLRC-DA與LLRC的組合具有最高的識(shí)別率，由于使用了LLRC的決策準(zhǔn)則，因此和其他降維方法相比，LLRC-DA學(xué)習(xí)的特征子空間與LLRC更加契合；4)LLRC-DA在LRC、LLRC上的識(shí)別率均明顯高于LLRDA，證明本文提出的方法對(duì)于提高分類率是有效的。

3.2 ORL人臉庫(kù)上的實(shí)驗(yàn)

ORL人臉庫(kù)的400幅圖像來自40個(gè)人，其中每人10幅圖像，圖像在不同條件下進(jìn)行采集，如光照、面部表情、面部細(xì)節(jié)等，圖2所示為一個(gè)人的10幅圖像。實(shí)驗(yàn)中所有的圖像均壓縮成 56像素像素。在實(shí)驗(yàn)之前，首先使用PCA方法將原始圖像降到50維，然后在每類中選擇前5幅圖像作為訓(xùn)練集，剩余的所有圖像作為測(cè)試集。

圖2 ORL庫(kù)中一個(gè)人的10幅圖像Fig. 2 Ten images of a person from the ORL database

在ORL人臉庫(kù)上，本文對(duì)LLRC-DA在不同參數(shù)下的性能進(jìn)行評(píng)估。首先，對(duì)每類中的最近鄰參數(shù)進(jìn)行實(shí)驗(yàn)，使用 NNC、MDC、LRC、LLRC分類器，固定，的值為1～4，實(shí)驗(yàn)結(jié)果如圖3所示。從圖3中可以看出，在NNC、LRC、LLRC分類器下，的取值為3時(shí)，識(shí)別率最高，這表明利用樣本之間的鄰域結(jié)構(gòu)，選擇而不是全部樣本來表示測(cè)試樣本，可以提高識(shí)別性能。

圖3 LLRC-DA在不同k下的識(shí)別率Fig. 3 Recognition rate of LLRC-DA with varied k

圖4 LLRC-DA在不同K下的識(shí)別率Fig. 4 Recognition rate of LLRC-DA with varied K

表2 ORL庫(kù)上的識(shí)別率Table 2 Recognition accuracy when using the ORL database

4 結(jié)束語

本文提出了面向局部線性回歸分類器的判別分析方法LLRC-DA，根據(jù)LLRC的決策準(zhǔn)則設(shè)計(jì)目標(biāo)函數(shù)，通過最大化類間局部重構(gòu)誤差并最小化類內(nèi)局部重構(gòu)誤差來尋找最優(yōu)的特征子空間。本文利用了投影矩陣與線性回歸系數(shù)之間的關(guān)系，消除了線性回歸系數(shù)的影響，使得目標(biāo)函數(shù)只和投影矩陣相關(guān)。LLRC-DA通過對(duì)投影矩陣添加正交約束來消除冗余信息，并得到更好的特征子空間。相比于傳統(tǒng)算法使用最大特征值分解來求解跡比問題，本文利用了一種新的跡比優(yōu)化算法來有效地求解投影矩陣。本文在FERET、ORL人臉庫(kù)上進(jìn)行了實(shí)驗(yàn)，與先進(jìn)的維數(shù)約簡(jiǎn)算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明，本文提出的方法具有更好的性能。對(duì)于LLRC-DA中的最近鄰參數(shù)的選擇問題，將尋找合適的參數(shù)選擇技術(shù)來確定值。在接下來的工作中，打算引入核方法來研究改進(jìn)本文的方法。