【正文】 性能目標(biāo)來尋找線性變換 W ，以實(shí)現(xiàn)對高維數(shù)據(jù)的降維：安徽工程大學(xué)畢業(yè)設(shè)計(jì)（論文）。,12.,?TjjyWxl已知存在 l 個(gè)訓(xùn)練樣本 ,令 為 的 k 個(gè)近鄰點(diǎn)。變換矩陣 W??1??lmiXxR??kiNxi就可以通過最小化如下目標(biāo)函數(shù)來得到：\* MERGEFORMAT (313)2,in????????TijijjWS其中 S 是權(quán)值矩陣可采用 k 近鄰方法來確定。\* MERGEFORMAT (314)????2exp0?????????????ijjkijkjotherwisxNorxijS其中 t 是一個(gè)大于 0 的常量。對式(313)進(jìn)行代數(shù)變換，如下： ??212?TijijijWxS??Tiji ijij ijDxWTX \* LMERGEFORMAT (315)是拉普拉斯矩陣，則上式就可轉(zhuǎn)化為特征求解問題,ijijDSL???\* MERGEFORMAT (316)??TTDX由于基于子空間的 LPP 算法具有描述性強(qiáng)、計(jì)算代價(jià)小、易實(shí)現(xiàn)及可分性好等特點(diǎn)，成為計(jì)算機(jī)視覺、模式識別等領(lǐng)域的研究熱點(diǎn)。由于算法本身并沒有考慮樣本類別信息，鑒于此許多學(xué)者通過增加樣本類別信息、正交化基向量以及加入核函數(shù)來改進(jìn) LPP 算法。 本章小結(jié)本章對目前較著名的一些降維算法進(jìn)行了簡單介紹，從線性算法和非線性算法兩方面出發(fā)，介紹了主成分分析、線性判別分析、等度映射、局部線性嵌入、拉普拉斯映射、核方法和局部保持算法。根據(jù)相關(guān)的文獻(xiàn)，核方法具有很多優(yōu)點(diǎn)，接下去的一章針對 KPCA、MMC ，學(xué)習(xí)和研究了改進(jìn)算法 KMMC。李亞龍： 基于核化 MMC 的人臉識別系統(tǒng)第 4 章 基于核方法的最大間距準(zhǔn)則算法在眾多算法中，線性判別分析 LDA、主成分分析 PCA 在實(shí)際應(yīng)用中經(jīng)常會(huì)遇到小樣本問題，為了解決這一問題，研究者提出了很多改進(jìn)算法，其中較著名的有MMC(Maximum Margin Criterion)算法，但是同 LDA 一樣，它是全局算法，沒有考慮局部信息，但是相關(guān)研究者指出局部信息在某些情況下起著非常重要的作用，比如在用最近鄰分類器時(shí)。為了解決這些問題，本章學(xué)習(xí)和研究基于核方法的最大間距準(zhǔn)則算法。 引言在第 3 章中，已經(jīng)詳細(xì)介紹了主成分分析、線性判別分析和保局算法等主要的數(shù)據(jù)降維算法，其中主成分分析通過最大化 n 維樣本的總體散布獲得由總體散布矩陣的前 l(l n)個(gè)最大特征值對應(yīng)的主元特征向量張成的低維線性子空間，保局算法通過保持投影前后樣本的相鄰關(guān)系獲得從 n 維圖像空間到 l 維特征空間的變換矩陣。這兩種方法最終都?xì)w結(jié)為求解廣義特征值問題，但是它們都是非監(jiān)督學(xué)習(xí)，因此不利于模式分類。線性判別分析是以分類為目的的線性特征提取算法，通過最大化樣本的類間散布和類內(nèi)散布的比率將樣本的類別信息加入到特征提取的過程中，其目的是保留樣本的判別信息和整體的幾何結(jié)構(gòu)，然而，相關(guān)研究者指出保持樣本的局部信息對分類問題更有意義。同時(shí)線性判別分析在實(shí)際操作中會(huì)遇到小樣本問題，即類內(nèi)矩陣往往是奇異的。在本章中，考慮樣本的局部信息，同時(shí)考慮樣本的類別信息，運(yùn)用核技巧將算法非線性化，學(xué)習(xí)和研究基于核間距最大準(zhǔn)則算法，并在 ORL、Yale 人臉庫上驗(yàn)證了算法的性能。 算法推導(dǎo) KPCA 算法現(xiàn)設(shè)有訓(xùn)練集 ，核映射 將它們映射到核空間 F 中，核空間中的12:,.NSxX??訓(xùn)練集為 。記 。????1,n????????1212,.,.N nxXxx????????1. 核空間中的 PCA在核空間中作子空間降維變換，即\* MERGEFORMAT (41)Tyw降維變換也稱為投影變換，w 就是投影方向。降維后數(shù)據(jù)的總體離散度為\* MERGEFORMAT (42)????1 1NNT TTtii ii ti iCyxwS? ????????????? ???其中 是核空間中的樣本均值。iix??????將核空間中的樣本中心化，即令 ，并記??iix???安徽工程大學(xué)畢業(yè)設(shè)計(jì)（論文），則核空間中的總體樣本協(xié)方差陣????12,.NXxx??????\* MERGEFORMAT (43)??????1 11NTTTt ii iii iS xX? ??????????核空間中的 PCA 通過最大化總體離散度 獲得最佳的投影方向 w，即最大化如下的準(zhǔn)tC?則函數(shù)：\* MERGEFORMAT (44)??TKPAtJwS?最大化準(zhǔn)則函數(shù) 需要對 作特征分解，但由于核空間的維數(shù)高，這個(gè)過??KPCAJt?程難以實(shí)現(xiàn)。不過下面將看到，核空間中的 PCA 所涉及的操作可由內(nèi)積表示，從而由核函數(shù)表示。2. 核函數(shù)表示由于最大化 就是對 作特征值分解，w 就是 的特征向量，因此有??KPCAJtS? tS?\* MERGEFORMAT (45)????11NNTTt ii iii ixxw??????????????這說明，投影方向 w 是核空間中的中心化數(shù)據(jù)的線性組合，因此可令\* MERGEFORMAT (46)1NiiX????其中 是線性組合系數(shù)。這樣，尋找最優(yōu)的投影方向 w 就轉(zhuǎn)化為??12,.TN??尋找最優(yōu)的線性組合系數(shù) 。首先將公司(46)代入降維變換式(41) 中，有??????TTT TNywxxxE???????????\* MERGEFORMAT (47),NkXEk????其中 ， 為元素 的 N 階矩陣?？梢姾丝??12,.TkXxk?????1間中的降維變換可由核函數(shù)表示。其次，將式（46）代入準(zhǔn)則函數(shù)式（44）中，并結(jié)合式（43） ，有\(zhòng)* MERGEFORMAT (48)??????221T TT TKPCAt tJwSXSXKN???????????????其中 ??TTNNEE?????????\* MERGEFORMAT (49)NKK?K 為式（ 410）定義的核矩陣。這樣，準(zhǔn)則函數(shù)也可由核函數(shù)表示。KPCA 的實(shí)現(xiàn)對核空間中的總體樣本協(xié)方差陣 作特征值分解：tS?\* MERGEFORMAT (410)??w?式中的 N 是樣本容量。將式（46）代入式（410） ，并兩邊同時(shí)左乘 ，有??TX??\* MERGEFORMAT (411)????T TtXNX???????根據(jù)式（48 ）和式（49 ） ，可將式（411）寫為\* MERGEFORMAT (412)2K?李亞龍： 基于核化 MMC 的人臉識別系統(tǒng)進(jìn)一步簡化，得\* MERGEFORMAT (413)K???即最佳組合系數(shù) 就是矩陣 的最大特征值所對應(yīng)的特征向量。?由于投影軸 w 主要用來表示投影方向，因此一般要求 。由于1Tw?\* MERGEFORMAT (414)??TTX??所以組合系數(shù)應(yīng)滿足的條件為\* MERGEFORMAT (415)1???其中 是特征向量 所對應(yīng)的特征值。??綜上所述，KPCA 的實(shí)施步驟可歸納如下：（1） 針對訓(xùn)練集 S，給定一個(gè)核函數(shù) k。（2） 由式（410）計(jì)算核矩陣 K，并由式（49）計(jì)算矩陣 。K（3） 對 作特征值分解，得到 和 ，即特征值與相應(yīng)的單位特征Ki???1,?量，將特征值從大到小排列，取前 D 個(gè)特征向量，并令 ，記降維矩??1,???陣為 。??12,.DQ??（4） 對于任一樣本向量 x，通過 KPCA 降維后的數(shù)據(jù)為\* MERGEFORMAT (416)??,TyQkXx? MMC 方法MMC 方法的提出LDA 方法應(yīng)用于人臉識別特征提取中存在小樣本問題，雖然解決小樣本問題的方法不斷提出，然而并沒有改變小樣本問題存在的根本，近年來，Li 等人提出了一種新的基于最大類間邊緣準(zhǔn)則的 MMC 方法，從根本上解決了 LDA 方法小樣本問題。最大類間邊緣準(zhǔn)則是基于特征空間的類間散度與類內(nèi)散度的差的最大化，其目的是尋求一組最佳鑒別矢量為投影軸進(jìn)行投影變換，使得特征空間樣本的類間散度最大，類內(nèi)散度最小。Zheng 等人提出了加權(quán)最大類間邊緣準(zhǔn)則(weighted maximum margin criterion , WMMC)特征抽取方法，重新構(gòu)造 ，基于最大類間邊緣準(zhǔn)則進(jìn)行特征提,BWS取。給定 N 維空間 c 類訓(xùn)練樣本， ，樣本 X 的類內(nèi)散度矩陣 、類??12,.NXx? WS間散度矩陣 、總體散度矩陣 分別由式（417） （418） （419）給出。BSTS\* MERGEFORMAT (417)??1ic tWiiixDm????\* MERGEFORMAT (418)c tBiii\* MERGEFORMAT (419)??1NtTTkkSxuX??其中 c 為類別數(shù)目， 為第 i 類的樣本均值向量， 為第 i 類的樣本集合， 為其中imi iN的樣本數(shù)目，且有，m 為所有樣本的均值向量。定義兩類樣本 i， j 之間的邊緣距離為安徽工程大學(xué)畢業(yè)設(shè)計(jì)（論文）\* MERGEFORMAT (420)????,ijdijmdij??其中 是兩類樣本均值之間的距離， ， 分別是 i， j 類內(nèi)樣本點(diǎn)到各自??,ijdm類內(nèi)中心的平均距離。在數(shù)理統(tǒng)計(jì)中，用類內(nèi)方差 來表示 ， ，,ijtrS??dij其中 分別是 i， j 類的類內(nèi)散度矩陣。在一定的距離測度下， 越大，i ， j 兩,ijS ,j個(gè)類具有越大的類間邊緣，兩個(gè)類具有越好的可分性。對于一個(gè) c 類問題，顯然當(dāng)平均類間邊緣大時(shí)，c 類問題顯然具有更好的可分性，定義平均類間邊緣\* MERGEFORMAT (421)??21,cijijDNd??代入 ，整理得??,dij\* MERGEFORMAT (422)????2 21 1,c cijij ijij ijNdmidj? ???引入歐式距離\* MERGEFORMAT (423)?,tijiim\* MERGEFORMAT (424)?tdrS類間散布矩陣\* MERGEFORMAT (425)??21c tBijiiijSN???將（423 ） （424） （425）代入（422 ）式得????2 21 1c ctijii ijijij ijDNmNtrSt? ???\* MERGEFORMAT (426)??BwBWrStrS?圖 41 直觀上說明了二維空間中的四類問題，假設(shè)四個(gè)類樣本個(gè)數(shù)相同，類內(nèi)均值分別為 ，類內(nèi)方差均為???1234,uuum?，則平均類間邊緣 ，如圖中虛線20,bwSSm?????????? ???21bwDtrS????所示。李亞龍： 基于核化 MMC 的人臉識別系統(tǒng)類 2 類 1類 4類 3圖 41 二維空間中的四個(gè)類及其邊緣距離MMC 方法的求解MMC 特征提取中，我們希望尋找一組最佳投影方向 W，使得投影后的平均類間邊緣 最大，在投影后的低維空間，樣本具有更好的可分性，投影后的類間邊緣可表示D為\* MERGEFORMAT (427)??????t tBWBwBwtrSrSS??????最佳投影方向 可由下式給出MC\* MERGEFORMAT (428)argmxtC求解（428 ）式也就是求解 的特征值和特征向量， 是 的前 mBwSMCWBwS個(gè)特征值對應(yīng)的特征向量，這與 PCA 方法求解特征值和特征向量的方法相同。MMC 方法是一種最大化平均類間邊緣的特征提取算法，在分類識別方面它的性能高于 PCA 方法，與 LDA 方法近似，它有效克服了小樣本情況下 奇異的問題，穩(wěn)定性與可靠性好。在一些限制條件下，MMC 方法與 LDA 方法是相同的，可以由 MMC 方法推導(dǎo)出LDA 方法。 KMMC 算法核最大間距準(zhǔn)則 設(shè) C 為模式類別數(shù)， 表示原輸入空間的第 i 類的第 j 個(gè)訓(xùn)練樣本，其中injXR?， 表示第 i 類訓(xùn)練樣本的數(shù)目， 。經(jīng)過,2.。1,.iijN?i ??非線性映射 變換后， 表示高維特征空?????????112,.,.,.CCNXX??間 H 上 N 個(gè)訓(xùn)練樣本。高維特征空間 H 上的訓(xùn)練樣本的類內(nèi)散布矩陣 ，類間散布wS?矩陣 和總體散布矩陣 分別定義為bStS安徽工程大學(xué)畢業(yè)設(shè)計(jì)（論文）\* MERGEFORMAT (429)??1CTibiiNSm??????\* MERGEFORMAT (430)?i iwjijiijXm??\* MERGEFORMAT (431)tbwS???其中 。???11。ji NNCi iji jij jim???特征空間 H 上最大間距準(zhǔn)則（MMC）函數(shù)為\* MERGEFORMAT (432)?1axdTjbwjjJWS?????其中 為特征空間內(nèi)的任意非零矢量，目的是基于準(zhǔn)??12,.,LdLdiWwRw??則式（432 ）最大的情形下，在特征空間 H 上尋找一組最優(yōu)鑒別矢量 ，并以12,.dw此構(gòu)成投影矩陣進(jìn)行鑒別特征提取。由于非線性映射 的形式上的未知，直接利用準(zhǔn)?則式（432 ）求解 是不可行的。在高維特征空間 H 中尋找最優(yōu)鑒別矢量，需要得到i僅包含核函數(shù)的準(zhǔn)則函數(shù)形式。如果設(shè)高維特征空間 H 中所有 N 個(gè)訓(xùn)練樣本表示為，根據(jù)再生核理論，式（432）的解矢量 w 一定位于高維特征????12,.NXX??空間 H 中的 N 個(gè)訓(xùn)練樣本矢量 所張成的空間內(nèi)，即????12,.NX??\* MERGEFORMA