莊姍姍

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

0 引言

目前，高維數(shù)據(jù)已廣泛存在于實際應(yīng)用中，如生物工程、信息檢索和計算機視覺等領(lǐng)域，在蘊含大量信息的同時也存在許多噪聲與冗余信息，產(chǎn)生“過擬合”和“維數(shù)災(zāi)難”的問題。因此，對高維數(shù)據(jù)進行降維是十分有必要的。

降維方法大致可分為三類：有監(jiān)督降維、半監(jiān)督降維和無監(jiān)督降維。有監(jiān)督方法是在事先知道樣本類別信息下進行降維；半監(jiān)督方法根據(jù)少量已知類別和大量未知類別樣本數(shù)據(jù)進行降維；無監(jiān)督方法事先無樣本類別信息，一般以保持樣本間結(jié)構(gòu)不變?yōu)樵瓌t進行降維。本文主要針對無監(jiān)督降維方法進行研究。

在無樣本類別先驗信息下，樣本間的局部結(jié)構(gòu)和全局結(jié)構(gòu)信息在降維過程中成為重要的考慮因素。文獻[1]通過自適應(yīng)投影保持降維前后樣本間的局部幾何結(jié)構(gòu)盡可能不變；文獻[2]通過L2,1范數(shù)構(gòu)造相似矩陣圖刻畫局部幾何結(jié)構(gòu)；文獻[3]盡可能保持所有樣本間的相似關(guān)系不變；文獻[4]通過譜聚類的引導學習全局稀疏子空間結(jié)構(gòu)進行降維；文獻[5]引入圖正則項進行特征選擇使得降維前后樣本間的流行結(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ù)求解過程中不可導，在全局優(yōu)化時屬于“NP難問題”，因而，往往對其進行近似求解，用‖·‖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)可知，當r=2，p=1時，‖·‖r,p為L2,1范數(shù)；當r=2，p=2時，‖·‖r,p為Frobenius范數(shù)。由于L2,p(0

2 本文方法

2.1 基本思想與動機

無監(jiān)督降維方法在無樣本類別先驗信息下，樣本間的局部結(jié)構(gòu)和全局結(jié)構(gòu)信息在降維過程中成為重要的考慮因素，多數(shù)降維方法只考慮樣本間的單一結(jié)構(gòu)因素。往往高維數(shù)據(jù)本質(zhì)上存在于多個低維子空間中[6],子空間學習對樣本數(shù)據(jù)重構(gòu)，通過稀疏等約束，獲得全局的子空間結(jié)構(gòu)。文獻[7]表明，在無監(jiān)督降維方法中刻畫數(shù)據(jù)的局部結(jié)構(gòu)具有重要意義。局部結(jié)構(gòu)可描述樣本間的局部近鄰關(guān)系，一般以k-近鄰方法來刻畫。同時，文獻[8]表明，L2,P范數(shù)(0

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

2.2 目標函數(shù)

基于L2,p(0

(5)

Sij=

(6)

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

s.t.PTXXTP=I

(7)

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

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

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

(8)

式(8)對Z進行求導，令其導數(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進行求導，令其導數(shù)為零，可得:

XBXTP=ρXXTP

(12)

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

在許多實際應(yīng)用中，D>>n，在特征值求解過程中，若對式(11)直接進行求解，矩陣有可能出現(xiàn)不可逆的情況，且計算過程中的時間復(fù)雜度和空間復(fù)雜度都較高。參照文獻[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)

進一步考慮，可采用不同的核函數(shù)，對式(14)進行擴展。當其為線性核函數(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種先進的無監(jiān)督降維方法對比：URAFS[5]、ANMMP[1]、LPP_L2、1[2]、KCRP[10]、SPFS[3]和CGSSL[4]。

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

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

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

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

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

(4)COIL20：該數(shù)據(jù)集由哥倫比亞大學所搜集的目標識別圖像數(shù)據(jù)組成，包括1 440幅圖，為20個目標在不同旋轉(zhuǎn)角度下的圖像，每個目標有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é)果用聚類準確率(ACC)進行比較。為避免隨機性，每種算法均運行10次并取聚類準確率的均值。實驗環(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的不同取值下的平均聚類準確率(ACC)，其中性能最優(yōu)的通過加粗顯示，具體如表2所示。

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

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

3.4 同其他方法的對比

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

由表3可看出，本文L2,pSLPP算法在上述數(shù)據(jù)集下均取得最高聚類準確率。對比LPP_L2,1和CGSSL稀疏子空間無監(jiān)督降維算法，L2,pSLPP取得更優(yōu)的聚類效果，這是由于L2,P范數(shù)約束(0

4 結(jié)論

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

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

猜你喜歡

空間結(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ù)學物理學報(2017年3期)2017-07-01 16:18:48

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

新世紀水泥導報(2016年1期)2016-07-01 03:59:37

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

中央社會主義學院學報(2016年2期)2016-05-04 04:18:28

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

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

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

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

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

燕山大學學報(2014年1期)2014-03-11 15:28:11

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

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

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

惡意計算機程序基因形式化研究*

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

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

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

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