莊姍姍

(福州大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，福建 福州 350108)

0 引言

目前，高維數(shù)據(jù)已廣泛存在于實際應(yīng)用中，如生物工程、信息檢索和計算機(jī)視覺等領(lǐng)域，在蘊(yùn)含大量信息的同時也存在許多噪聲與冗余信息，產(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)行研究。

在無樣本類別先驗信息下，樣本間的局部結(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]引入圖正則項進(jìn)行特征選擇使得降維前后樣本間的流行結(jié)構(gòu)保持一致。

綜上所述，多數(shù)降維方法只考慮樣本間的單一結(jié)構(gòu)，故本文提出基于L2,p稀疏子空間和局部結(jié)構(gòu)保持降維方法，同時考慮樣本間的全局子空間結(jié)構(gòu)和局部幾何結(jié)構(gòu)，通過刻畫局部相似性關(guān)系圖，保持降維前后樣本間局部流行結(jié)構(gòu)一致；通過更一般化的L2,p范數(shù)約束(0

1 相關(guān)工作

1.1 稀疏子空間結(jié)構(gòu)

s.t.X=XZ,diag(Z)=0

(1)

其中，Z∈Rn×n為相似矩陣。‖·‖0表示對矩陣Z作稀疏約束。

在實際生活中，由于客觀或主觀原因，觀測得到的數(shù)據(jù)往往含有噪聲，因此松弛式(1)得到：

s.t.diag(Z)=0

(2)

由于去掉diag(Z)=0約束條件也不會造成平凡解，故式(2)可等價于：

(3)

其中，λ>0為平衡參數(shù)。由于L0范數(shù)求解過程中不可導(dǎo)，在全局優(yōu)化時屬于“NP難問題”，因而，往往對其進(jìn)行近似求解，用‖·‖1或‖·‖2,1等近似求得稀疏解。

1.2 Lr,p范數(shù)

任意給定一矩陣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時，‖·‖r,p為L2,1范數(shù)；當(dāng)r=2，p=2時，‖·‖r,p為Frobenius范數(shù)。由于L2,p(0

2 本文方法

2.1 基本思想與動機(jī)

無監(jiān)督降維方法在無樣本類別先驗信息下，樣本間的局部結(jié)構(gòu)和全局結(jié)構(gòu)信息在降維過程中成為重要的考慮因素，多數(shù)降維方法只考慮樣本間的單一結(jié)構(gòu)因素。往往高維數(shù)據(jù)本質(zhì)上存在于多個低維子空間中[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-近鄰方法來刻畫。同時，文獻(xiàn)[8]表明，L2,P范數(shù)(0

基于上述考慮，本文提出基于L2,p(0

2.2 目標(biāo)函數(shù)

基于L2,p(0

(5)

Sij=

(6)

為避免平凡解，增加約束項PTXXTP=I，其中I為單位陣，目標(biāo)函數(shù)(5)轉(zhuǎn)化為：

s.t.PTXXTP=I

(7)

2.3 目標(biāo)函數(shù)求解與算法

模型(7)有兩個變量，本文運(yùn)用交替優(yōu)化方法求解P和Z，將問題分為以下幾個階段：固定P學(xué)習(xí)Z、固定Z學(xué)習(xí)P。

(1)更新變量Z：將P固定，Z的子問題等價于

(8)

式(8)對Z進(jìn)行求導(dǎo)，令其導(dǎo)數(shù)為零，可得:

AP-αXTPPTX+αXTPPTXZ=0

?Z=(αXTPPTX)-1(αXTPPTX-AP)

(9)

(2)更新變量P：將Z固定，P的子問題等價于

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個最大特征值所對應(yīng)的特征向量組成。

在許多實際應(yīng)用中，D>>n，在特征值求解過程中，若對式(11)直接進(jìn)行求解，矩陣有可能出現(xiàn)不可逆的情況，且計算過程中的時間復(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ù)時，式(14)等價于式(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個對角元素p/2‖Pit+1‖22-p; (7)t=t+1; (8)until滿足收斂條件{‖Pt+1-Pt‖∞,‖Zt+1-Zt‖∞}<ε或者t>maxIter (9)輸出:降維后的樣本矩陣Y=PTX

3 實驗

為驗證本文方法的有效性，將本文所提的方法L2,pSLPP同6種先進(jìn)的無監(jiān)督降維方法對比：URAFS[5]、ANMMP[1]、LPP_L2、1[2]、KCRP[10]、SPFS[3]和CGSSL[4]。

3.1 數(shù)據(jù)集

實驗選用8個公開的標(biāo)準(zhǔn)數(shù)據(jù)集：4個圖像數(shù)據(jù)集(YALE，ORL，JAFFE，COIL20)和4個生物基因數(shù)據(jù)集(LEUKEMIA2，LUNG_CANCER，DLBCL,BRAIN_TUMOR)，主要信息如下：

(1)YALE：該數(shù)據(jù)集由耶魯大學(xué)所搜集的人臉圖像數(shù)據(jù)組成，包括165幅圖，為15個人在不同光照、表情以及姿態(tài)下的人臉圖像，每個人有11幅。

(2)ORL：該數(shù)據(jù)集由劍橋大學(xué)AT&T實驗室所搜集的人臉圖像數(shù)據(jù)組成，包括400幅圖，為40個人在不同光照、爭閉眼等表情以及其他細(xì)節(jié)的人臉圖像，每個人有10幅。

(3)JAFFE：該數(shù)據(jù)集是關(guān)于女性面部表情的數(shù)據(jù)，包括213幅圖，由10位女性的7種面部表情(開心、難過、生氣等)組成，每種表情有3～4幅。

(4)COIL20：該數(shù)據(jù)集由哥倫比亞大學(xué)所搜集的目標(biāo)識別圖像數(shù)據(jù)組成，包括1 440幅圖，為20個目標(biāo)在不同旋轉(zhuǎn)角度下的圖像，每個目標(biāo)有72幅。

(5)LEUKEMIA2：該數(shù)據(jù)集為白血病數(shù)據(jù)，包括72個樣本，3種亞型白血病類型，每個樣本的基因特征數(shù)有11 225個。

(6)LUNG_CANCER：該數(shù)據(jù)集為肺癌數(shù)據(jù)，包括203個樣本，5種類型：4種不同患病類型和1種不患病類型，每個樣本的基因特征數(shù)有12 600個。

(7)DLBCL：該數(shù)據(jù)集為淋巴瘤數(shù)據(jù)，包括77個樣本，兩組淋巴瘤類型，每個樣本的基因特征數(shù)有5 469個。

(8)BRAIN_TUMOR：該數(shù)據(jù)集為腦部腫瘤數(shù)據(jù)，包括90個樣本，5種類型：4種不同患病類型和1種不患病類型，每個樣本的基因特征數(shù)有5 920個。

數(shù)據(jù)集描述如表1所示。

表1 數(shù)據(jù)集描述

3.2 參數(shù)設(shè)置

本文所提方法的參數(shù)設(shè)置與對比方法的參數(shù)設(shè)置相同，近鄰參數(shù)k=5，投影矩陣P維數(shù)空間為d，聚類個數(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聚類，實驗結(jié)果用聚類準(zhǔn)確率(ACC)進(jìn)行比較。為避免隨機(jī)性，每種算法均運(yùn)行10次并取聚類準(zhǔn)確率的均值。實驗環(huán)境為Windows7系統(tǒng)，內(nèi)存4 GB，所有方法用MATLAB 2015a編程實現(xiàn)。

3.3 L2,p(0

觀察p的不同取值對L2,pSLPP性能的影響。p的取值范圍為{0.01,0.25,0.50,0.75,1.0}，其他參數(shù)的設(shè)置同3.2節(jié)。對上述8個數(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)確率 (%)

3.4 同其他方法的對比

將本文L2,pSLPP與其他6種先進(jìn)的無監(jiān)督降維方法對比，觀察上述8個數(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

4 結(jié)論

本文在降維過程中考慮混合結(jié)構(gòu)，提出基于L2,p(0

表3 不同算法的聚類準(zhǔn)確率 (%)

猜你喜歡

結(jié)構(gòu)方法

《形而上學(xué)》△卷的結(jié)構(gòu)和位置

哲學(xué)評論(2021年2期)2021-08-22 01:53:34

論結(jié)構(gòu)

中華詩詞(2019年7期)2019-11-25 01:43:04

新型平衡塊結(jié)構(gòu)的應(yīng)用

模具制造(2019年3期)2019-06-06 02:10:54

學(xué)習(xí)方法

兒童故事畫報(2019年5期)2019-05-26 14:26:14

可能是方法不對

意林原創(chuàng)版(2016年10期)2016-11-25 10:28:30

論《日出》的結(jié)構(gòu)

影視與戲劇評論(2016年0期)2016-11-23 05:26:01

用對方法才能瘦

Coco薇(2016年2期)2016-03-22 02:42:52

四大方法 教你不再“坐以待病”！

Coco薇(2015年1期)2015-08-13 02:47:34

賺錢方法

小雪花·成長指南(2015年7期)2015-08-11 15:03:12

捕魚

小雪花·成長指南(2015年4期)2015-05-19 14:47:56

網(wǎng)絡(luò)安全與數(shù)據(jù)管理2019年11期

網(wǎng)絡(luò)安全與數(shù)據(jù)管理的其它文章

螢火蟲算法參數(shù)分析與優(yōu)化*

惡意計算機(jī)程序基因形式化研究*

基于成對約束的半監(jiān)督聚類方法

基于改進(jìn)RNN的多變量時間序列缺失數(shù)據(jù)填充算法*

基于FPGA的CNN加速器設(shè)計與實現(xiàn)*

檢驗機(jī)構(gòu)報價系統(tǒng)的實現(xiàn)