莊姍姍

(福州大學(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)難”的問題。因此，對(duì)高維數(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)行降維。本文主要針對(duì)無監(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

1 相關(guān)工作

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

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

(1)

其中，Z∈Rn×n為相似矩陣?！ぁ?表示對(duì)矩陣Z作稀疏約束。

在實(shí)際生活中，由于客觀或主觀原因，觀測(cè)得到的數(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難問題”，因而，往往對(duì)其進(jìn)行近似求解，用‖·‖1或‖·‖2,1等近似求得稀疏解。

1.2 Lr,p范數(shù)

任意給定一矩陣B∈Rm×n，bi為B的第i行，bj為B的第j列，Bij為B的第i行第j列元素，對(duì)矩陣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為L(zhǎng)2,1范數(shù)；當(dāng)r=2，p=2時(shí)，‖·‖r,p為Frobenius范數(shù)。由于L2,p(0

2 本文方法

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

無監(jiān)督降維方法在無樣本類別先驗(yàn)信息下，樣本間的局部結(jié)構(gòu)和全局結(jié)構(gòu)信息在降維過程中成為重要的考慮因素，多數(shù)降維方法只考慮樣本間的單一結(jié)構(gòu)因素。往往高維數(shù)據(jù)本質(zhì)上存在于多個(gè)低維子空間中[6],子空間學(xué)習(xí)對(duì)樣本數(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

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

基于L2,p(0

(5)

Sij=

(6)

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

s.t.PTXXTP=I

(7)

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

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

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

(8)

式(8)對(duì)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)對(duì)P進(jìn)行求導(dǎo)，令其導(dǎo)數(shù)為零，可得:

XBXTP=ρXXTP

(12)

其中，B=α(I-Z-ZT+ZTZ)+βL。投影矩陣P通過求解式(12)的廣義特征值，由其前d個(gè)最大特征值所對(duì)應(yīng)的特征向量組成。

在許多實(shí)際應(yīng)用中，D>>n，在特征值求解過程中，若對(duì)式(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ù)，對(duì)式(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è)對(duì)角元素p/2‖Pit+1‖22-p; (7)t=t+1; (8)until滿足收斂條件{‖Pt+1-Pt‖∞,‖Zt+1-Zt‖∞}<ε或者t>maxIter (9)輸出:降維后的樣本矩陣Y=PTX

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

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

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

實(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è)人在不同光照、爭(zhēng)閉眼等表情以及其他細(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ù)集描述

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

本文所提方法的參數(shù)設(shè)置與對(duì)比方法的參數(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)。

3.3 L2,p(0

觀察p的不同取值對(duì)L2,pSLPP性能的影響。p的取值范圍為{0.01,0.25,0.50,0.75,1.0}，其他參數(shù)的設(shè)置同3.2節(jié)。對(duì)上述8個(gè)數(shù)據(jù)集觀察p的不同取值下的平均聚類準(zhǔn)確率(ACC)，其中性能最優(yōu)的通過加粗顯示，具體如表2所示。

從表2可看出，L2,pSLPP的聚類準(zhǔn)確率在不同數(shù)據(jù)集下隨著對(duì)p的不同取值而變化，并且最優(yōu)值不總是在p=1下取得，對(duì)所有的數(shù)據(jù)集并沒有普適的最優(yōu)p值。因此，相對(duì)于固定p=1，對(duì)不同數(shù)據(jù)集令p值保持靈活性是更為可取的方法。

表2 不同p值下L2,pSLPP聚類準(zhǔn)確率 (%)

3.4 同其他方法的對(duì)比

將本文L2,pSLPP與其他6種先進(jìn)的無監(jiān)督降維方法對(duì)比，觀察上述8個(gè)數(shù)據(jù)集不同算法的平均聚類準(zhǔn)確率(ACC)，結(jié)果如表3所示。

由表3可看出，本文L2,pSLPP算法在上述數(shù)據(jù)集下均取得最高聚類準(zhǔn)確率。對(duì)比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)降維范數(shù)

Three-Body’s epic scale and fiercely guarded fanbase present challenges to adaptations

漢語世界(The World of Chinese)(2024年2期)2024-01-01 00:00:00

格絨追美小說敘事的空間結(jié)構(gòu)

阿來研究(2020年1期)2020-10-28 08:10:22

降維打擊

海峽姐妹(2019年12期)2020-01-14 03:24:40

基于加權(quán)核范數(shù)與范數(shù)的魯棒主成分分析

中國校外教育(下旬)(2017年8期)2017-10-30 17:32:36

矩陣酉不變范數(shù)H?lder不等式及其應(yīng)用

數(shù)學(xué)物理學(xué)報(bào)(2017年3期)2017-07-01 16:18:48

徐州安美固建筑空間結(jié)構(gòu)有限公司

新世紀(jì)水泥導(dǎo)報(bào)(2016年1期)2016-07-01 03:59:37

基于社會(huì)空間結(jié)構(gòu)流變的統(tǒng)戰(zhàn)工作組織策略研究

中央社會(huì)主義學(xué)院學(xué)報(bào)(2016年2期)2016-05-04 04:18:28

一類具有準(zhǔn)齊次核的Hilbert型奇異重積分算子的范數(shù)及應(yīng)用

數(shù)學(xué)年刊A輯(中文版)(2014年1期)2014-10-30 01:48:06

拋物化Navier-Stokes方程的降維仿真模型

計(jì)算物理(2014年1期)2014-03-11 17:00:18

基于特征聯(lián)合和偏最小二乘降維的手勢(shì)識(shí)別

燕山大學(xué)學(xué)報(bào)(2014年1期)2014-03-11 15:28:11

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

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

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

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

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

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

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

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