基于L2,P稀疏子空間和局部結(jié)構(gòu)保持降維
2019-11-12 09:37:18莊姍姍
網(wǎng)絡(luò)安全與數(shù)據(jù)管理 2019年11期
關(guān)鍵詞：結(jié)構(gòu)方法
莊姍姍
(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350108)
0 引言
目前，高維數(shù)據(jù)已廣泛存在于實(shí)際應(yīng)用中，如生物工程、信息檢索和計(jì)算機(jī)視覺等領(lǐng)域，在蘊(yùn)含大量信息的同時(shí)也存在許多噪聲與冗余信息，產(chǎn)生“過擬合”和“維數(shù)災(zāi)難”的問題。因此，對高維數(shù)據(jù)進(jìn)行降維是十分有必要的。
降維方法大致可分為三類：有監(jiān)督降維、半監(jiān)督降維和無監(jiān)督降維。有監(jiān)督方法是在事先知道樣本類別信息下進(jìn)行降維；半監(jiān)督方法根據(jù)少量已知類別和大量未知類別樣本數(shù)據(jù)進(jìn)行降維；無監(jiān)督方法事先無樣本類別信息，一般以保持樣本間結(jié)構(gòu)不變?yōu)樵瓌t進(jìn)行降維。本文主要針對無監(jiān)督降維方法進(jìn)行研究。
在無樣本類別先驗(yàn)信息下，樣本間的局部結(jié)構(gòu)和全局結(jié)構(gòu)信息在降維過程中成為重要的考慮因素。文獻(xiàn)[1]通過自適應(yīng)投影保持降維前后樣本間的局部幾何結(jié)構(gòu)盡可能不變；文獻(xiàn)[2]通過L2,1范數(shù)構(gòu)造相似矩陣圖刻畫局部幾何結(jié)構(gòu)；文獻(xiàn)[3]盡可能保持所有樣本間的相似關(guān)系不變；文獻(xiàn)[4]通過譜聚類的引導(dǎo)學(xué)習(xí)全局稀疏子空間結(jié)構(gòu)進(jìn)行降維；文獻(xiàn)[5]引入圖正則項(xiàng)進(jìn)行特征選擇使得降維前后樣本間的流行結(jié)構(gòu)保持一致。
綜上所述，多數(shù)降維方法只考慮樣本間的單一結(jié)構(gòu)，故本文提出基于L2,p稀疏子空間和局部結(jié)構(gòu)保持降維方法，同時(shí)考慮樣本間的全局子空間結(jié)構(gòu)和局部幾何結(jié)構(gòu)，通過刻畫局部相似性關(guān)系圖，保持降維前后樣本間局部流行結(jié)構(gòu)一致；通過更一般化的L2,p范數(shù)約束(0 s.t.X=XZ,diag(Z)=0 (1) 其中，Z∈Rn×n為相似矩陣。‖·‖0表示對矩陣Z作稀疏約束。 在實(shí)際生活中，由于客觀或主觀原因，觀測得到的數(shù)據(jù)往往含有噪聲，因此松弛式(1)得到： s.t.diag(Z)=0 (2) 由于去掉diag(Z)=0約束條件也不會(huì)造成平凡解，故式(2)可等價(jià)于： (3) 其中，λ>0為平衡參數(shù)。由于L0范數(shù)求解過程中不可導(dǎo)，在全局優(yōu)化時(shí)屬于“NP難問題”，因而，往往對其進(jìn)行近似求解，用‖·‖1或‖·‖2,1等近似求得稀疏解。 任意給定一矩陣B∈Rm×n，bi為B的第i行，bj為B的第j列，Bij為B的第i行第j列元素，對矩陣B定義Lr,p范數(shù)(r>0,p>0)如下： (4) 其中，‖b‖r是關(guān)于向量b的Lr范數(shù)。由式(4)可知，當(dāng)r=2，p=1時(shí)，‖·‖r,p為L2,1范數(shù)；當(dāng)r=2，p=2時(shí)，‖·‖r,p為Frobenius范數(shù)。由于L2,p(0 無監(jiān)督降維方法在無樣本類別先驗(yàn)信息下，樣本間的局部結(jié)構(gòu)和全局結(jié)構(gòu)信息在降維過程中成為重要的考慮因素，多數(shù)降維方法只考慮樣本間的單一結(jié)構(gòu)因素。往往高維數(shù)據(jù)本質(zhì)上存在于多個(gè)低維子空間中[6],子空間學(xué)習(xí)對樣本數(shù)據(jù)重構(gòu)，通過稀疏等約束，獲得全局的子空間結(jié)構(gòu)。文獻(xiàn)[7]表明，在無監(jiān)督降維方法中刻畫數(shù)據(jù)的局部結(jié)構(gòu)具有重要意義。局部結(jié)構(gòu)可描述樣本間的局部近鄰關(guān)系，一般以k-近鄰方法來刻畫。同時(shí)，文獻(xiàn)[8]表明，L2,P范數(shù)(0 基于上述考慮，本文提出基于L2,p(0 基于L2,p(0 (5) Sij= (6) 為避免平凡解，增加約束項(xiàng)PTXXTP=I，其中I為單位陣，目標(biāo)函數(shù)(5)轉(zhuǎn)化為： s.t.PTXXTP=I (7) 模型(7)有兩個(gè)變量，本文運(yùn)用交替優(yōu)化方法求解P和Z，將問題分為以下幾個(gè)階段：固定P學(xué)習(xí)Z、固定Z學(xué)習(xí)P。 (1)更新變量Z：將P固定，Z的子問題等價(jià)于 (8) 式(8)對Z進(jìn)行求導(dǎo)，令其導(dǎo)數(shù)為零，可得: AP-αXTPPTX+αXTPPTXZ=0 ?Z=(αXTPPTX)-1(αXTPPTX-AP) (9) (2)更新變量P：將Z固定，P的子問題等價(jià)于 s.t.PTXXTP=I (10) 利用拉格朗日乘子法，令 ρTr(PTXXTP-I) (11) 式(11)對P進(jìn)行求導(dǎo)，令其導(dǎo)數(shù)為零，可得: XBXTP=ρXXTP (12) 其中，B=α(I-Z-ZT+ZTZ)+βL。投影矩陣P通過求解式(12)的廣義特征值，由其前d個(gè)最大特征值所對應(yīng)的特征向量組成。 在許多實(shí)際應(yīng)用中，D>>n，在特征值求解過程中，若對式(11)直接進(jìn)行求解，矩陣有可能出現(xiàn)不可逆的情況，且計(jì)算過程中的時(shí)間復(fù)雜度和空間復(fù)雜度都較高。參照文獻(xiàn)[9]，投影矩陣P可用樣本的線性關(guān)系來表示，令P=XW，則式(11)可化為： s.t.WTXTXXTXW=I (13) 令K=XTX為核矩陣，Kij=K(xi,xj)，樣本通過核技巧被映射到Hilber空間，式(13)可轉(zhuǎn)化為: s.t.WTKKW=I (14) 進(jìn)一步考慮，可采用不同的核函數(shù)，對式(14)進(jìn)行擴(kuò)展。當(dāng)其為線性核函數(shù)時(shí)，式(14)等價(jià)于式(13)。 L2,pSLPP算法描述如下： 算法:L2,PSLPP (1)輸入:數(shù)據(jù)矩陣X,參數(shù)α、β、ρ和p (2)初始化:t=0,ε=10-8,maxIter=500,At=I以及Zt,Pt,Wt (3)repeat: (4)根據(jù)式(9)更新Zt+1; (5)根據(jù)式(12)或式(13)更新Pt+1; (6)更新At+1第i個(gè)對角元素p/2‖Pit+1‖22-p; (7)t=t+1; (8)until滿足收斂條件{‖Pt+1-Pt‖∞,‖Zt+1-Zt‖∞}<ε或者t>maxIter (9)輸出:降維后的樣本矩陣Y=PTX 為驗(yàn)證本文方法的有效性，將本文所提的方法L2,pSLPP同6種先進(jìn)的無監(jiān)督降維方法對比：URAFS[5]、ANMMP[1]、LPP_L2、1[2]、KCRP[10]、SPFS[3]和CGSSL[4]。 實(shí)驗(yàn)選用8個(gè)公開的標(biāo)準(zhǔn)數(shù)據(jù)集：4個(gè)圖像數(shù)據(jù)集(YALE，ORL，JAFFE，COIL20)和4個(gè)生物基因數(shù)據(jù)集(LEUKEMIA2，LUNG_CANCER，DLBCL,BRAIN_TUMOR)，主要信息如下： (1)YALE：該數(shù)據(jù)集由耶魯大學(xué)所搜集的人臉圖像數(shù)據(jù)組成，包括165幅圖，為15個(gè)人在不同光照、表情以及姿態(tài)下的人臉圖像，每個(gè)人有11幅。 (2)ORL：該數(shù)據(jù)集由劍橋大學(xué)AT&T實(shí)驗(yàn)室所搜集的人臉圖像數(shù)據(jù)組成，包括400幅圖，為40個(gè)人在不同光照、爭閉眼等表情以及其他細(xì)節(jié)的人臉圖像，每個(gè)人有10幅。 (3)JAFFE：該數(shù)據(jù)集是關(guān)于女性面部表情的數(shù)據(jù)，包括213幅圖，由10位女性的7種面部表情(開心、難過、生氣等)組成，每種表情有3～4幅。 (4)COIL20：該數(shù)據(jù)集由哥倫比亞大學(xué)所搜集的目標(biāo)識(shí)別圖像數(shù)據(jù)組成，包括1 440幅圖，為20個(gè)目標(biāo)在不同旋轉(zhuǎn)角度下的圖像，每個(gè)目標(biāo)有72幅。 (5)LEUKEMIA2：該數(shù)據(jù)集為白血病數(shù)據(jù)，包括72個(gè)樣本，3種亞型白血病類型，每個(gè)樣本的基因特征數(shù)有11 225個(gè)。 (6)LUNG_CANCER：該數(shù)據(jù)集為肺癌數(shù)據(jù)，包括203個(gè)樣本，5種類型：4種不同患病類型和1種不患病類型，每個(gè)樣本的基因特征數(shù)有12 600個(gè)。 (7)DLBCL：該數(shù)據(jù)集為淋巴瘤數(shù)據(jù)，包括77個(gè)樣本，兩組淋巴瘤類型，每個(gè)樣本的基因特征數(shù)有5 469個(gè)。 (8)BRAIN_TUMOR：該數(shù)據(jù)集為腦部腫瘤數(shù)據(jù)，包括90個(gè)樣本，5種類型：4種不同患病類型和1種不患病類型，每個(gè)樣本的基因特征數(shù)有5 920個(gè)。 數(shù)據(jù)集描述如表1所示。 表1 數(shù)據(jù)集描述 本文所提方法的參數(shù)設(shè)置與對比方法的參數(shù)設(shè)置相同，近鄰參數(shù)k=5，投影矩陣P維數(shù)空間為d，聚類個(gè)數(shù)為C。 若無具體說明，所有方法參數(shù)均采用“網(wǎng)格搜索”方式選取，平衡參數(shù)取值范圍為{10-6,10-5,10-4,10-3,10-2,10-1,1,101,102,103,104,105,106}，維數(shù)空間d取值范圍為{5,10,15,20,25,30,35,40,45,50}。降維后的數(shù)據(jù)均通過K-MEANS聚類，實(shí)驗(yàn)結(jié)果用聚類準(zhǔn)確率(ACC)進(jìn)行比較。為避免隨機(jī)性，每種算法均運(yùn)行10次并取聚類準(zhǔn)確率的均值。實(shí)驗(yàn)環(huán)境為Windows7系統(tǒng)，內(nèi)存4 GB，所有方法用MATLAB 2015a編程實(shí)現(xiàn)。 觀察p的不同取值對L2,pSLPP性能的影響。p的取值范圍為{0.01,0.25,0.50,0.75,1.0}，其他參數(shù)的設(shè)置同3.2節(jié)。對上述8個(gè)數(shù)據(jù)集觀察p的不同取值下的平均聚類準(zhǔn)確率(ACC)，其中性能最優(yōu)的通過加粗顯示，具體如表2所示。 從表2可看出，L2,pSLPP的聚類準(zhǔn)確率在不同數(shù)據(jù)集下隨著對p的不同取值而變化，并且最優(yōu)值不總是在p=1下取得，對所有的數(shù)據(jù)集并沒有普適的最優(yōu)p值。因此，相對于固定p=1，對不同數(shù)據(jù)集令p值保持靈活性是更為可取的方法。 表2 不同p值下L2,pSLPP聚類準(zhǔn)確率 (%) 將本文L2,pSLPP與其他6種先進(jìn)的無監(jiān)督降維方法對比，觀察上述8個(gè)數(shù)據(jù)集不同算法的平均聚類準(zhǔn)確率(ACC)，結(jié)果如表3所示。 由表3可看出，本文L2,pSLPP算法在上述數(shù)據(jù)集下均取得最高聚類準(zhǔn)確率。對比LPP_L2,1和CGSSL稀疏子空間無監(jiān)督降維算法，L2,pSLPP取得更優(yōu)的聚類效果，這是由于L2,P范數(shù)約束(0 本文在降維過程中考慮混合結(jié)構(gòu)，提出基于L2,p(0 表3 不同算法的聚類準(zhǔn)確率 (%)1 相關(guān)工作
1.1 稀疏子空間結(jié)構(gòu)
1.2 Lr,p范數(shù)
2 本文方法
2.1 基本思想與動(dòng)機(jī)
2.2 目標(biāo)函數(shù)
2.3 目標(biāo)函數(shù)求解與算法
3 實(shí)驗(yàn)
3.1 數(shù)據(jù)集
3.2 參數(shù)設(shè)置
3.3 L2,p(0
3.4 同其他方法的對比
4 結(jié)論
猜你喜歡
哲學(xué)評(píng)論(2021年2期)2021-08-22 01:53:34中華詩詞(2019年7期)2019-11-25 01:43:04模具制造(2019年3期)2019-06-06 02:10:54兒童故事畫報(bào)(2019年5期)2019-05-26 14:26:14影視與戲劇評(píng)論(2016年0期)2016-11-23 05:26:01Coco薇(2016年2期)2016-03-22 02:42:52Coco薇(2015年1期)2015-08-13 02:47:34小雪花·成長指南(2015年7期)2015-08-11 15:03:12小雪花·成長指南(2015年4期)2015-05-19 14:47:56現(xiàn)代企業(yè)(2015年9期)2015-02-28 18:56:50
