第7章稀疏大數(shù)據(jù)的維數(shù)約簡7.1稀疏矩陣的應(yīng)用及概念7.2稀疏表示理論及重構(gòu)7.3線性回歸模型7.4稀疏保持映射7.5基于Lasso的稀疏主成分7.6稀疏判別分析

7.1稀疏矩陣的應(yīng)用及概念

1.稀疏矩陣的應(yīng)用

隨著信息技術(shù)及網(wǎng)絡(luò)的迅速發(fā)展,非結(jié)構(gòu)化數(shù)據(jù)大量涌現(xiàn),如文本、圖像、音頻、視頻等,其特點可歸結(jié)為多樣性、高維、海量、非線性以及不能為人的感知所單獨處理。對非結(jié)構(gòu)化數(shù)據(jù)發(fā)現(xiàn)其內(nèi)在關(guān)系信息豐富的描述,是一個具有廣泛應(yīng)用背景而又迫切需要的富有挑戰(zhàn)性的研究課題,如識別與檢索、圖像識別與檢索、DNA序列提取等。

2.稀疏矩陣的研究及概念

稀疏矩陣是指非零元素占全部元素的百分比很小(5%以下)的矩陣或者是非零元素占全部元素的百分比較大(近50%)的矩陣。由于稀疏矩陣的研究非常重要,關(guān)于其的研究成果已有很多,本章主要介紹最經(jīng)典的稀疏矩陣方法,通過將某些回歸系數(shù)退化或設(shè)為0,來達到降維的目的。

7.2稀疏表示理論及重構(gòu)

7.2.1范數(shù)稀疏解考慮到一個實向量x=(x1,x2,…xn)∈Rn,則所謂l2范式的數(shù)學(xué)定義為

SRE的一個假設(shè)是樣本點是從一個線性空間采樣的,因此,其面臨的問題類似于給定限制條件y-kx=b,并分別以l2范式、l1范式最小為限制條件的兩個求解最優(yōu)化問題,如圖7-2所示。

圖7-1l2范式、l1范式和l0范式的定義

在圖7-2中,x0表示尋找到的最優(yōu)解,中心處的黑色箭頭表示尋找最優(yōu)解的過程。從圖中可以發(fā)現(xiàn),在尋找最優(yōu)解時,只要所求的解是稀疏的,那么以l1范式最小為限制條件總能找到該稀疏解,相反,以l2范式最小化為限制條件的求解問題雖然也能尋找到最優(yōu)解,但該解并不稀疏。稀疏表示算法的核心思想就在于在降維過程中保持原始數(shù)據(jù)稀疏線性重建的特性,因此以l1范式最小為限制條件是替代以l0范式最小為限制條件的最佳方式。圖7-2l2范式和l1范式的求解過程

7.2.2稀疏表示理論概述

假定樣本X={x1,x2,x3,…,xn}∈RD×n,稀疏表示的目的是盡可能用少量的X的樣本來表示xi∈X,具體的數(shù)學(xué)定義描述如下

7.2.4基于稀疏表示的算法流程

基于稀疏表示的算法流程如下:

(1)給定一共n個訓(xùn)練樣本,其中每個樣本是D維的,那么所有的訓(xùn)練樣本可以用X=[X1,X2,…,Xn]∈RD×n來表示。

(2)對每個訓(xùn)練樣本都進行歸一化處理。

(3)對任意輸入的測試樣本y,求其稀疏表示,使稀疏的l1范數(shù)最小。

(4)針對每一個類i,計算只用這個類對測試樣本進行重構(gòu)時的重構(gòu)誤差。

(5)將重構(gòu)誤差最小的類別i作為測試樣本y的類別。

7.3線性回歸模型

令XnD=(x1,x2,…,xn)T是樣本自變量組成的矩陣,令yn×1=(y1,y2,…,yn)T是樣本響應(yīng)變量組成的向量。

7.3.1最小二乘法

假定X是滿秩矩陣,則此時XTX是正定的。當(dāng)

時,RSS(β)會取到極小值:

上式有一定的局限性,使用最小二乘法來模擬估計參數(shù)β的值,所能達到的精度不夠,一些學(xué)者認為可通過收縮β或把一些系數(shù)直接設(shè)為0可使預(yù)測精確度得到提高。

7.3.2嶺回歸

嶺回歸(RidgeRegression)的思想是對目標(biāo)函數(shù)中的回歸系數(shù)β上增加些限制條件來縮小β的值,其形式如下:

式中,λ為控制β收縮的參數(shù),隨著λ的值不斷增大,相應(yīng)的回歸系數(shù)β的值也越來越向0值靠攏。

該式進一步改寫為如下:

使得

上式確切的顯示出了目標(biāo)函數(shù)中對系數(shù)β大小的限制,式(7-15)中的λ和式(7-16)存在著對應(yīng)關(guān)系。上式進一步寫成矩陣的形式,目標(biāo)函數(shù)最小化公式變?yōu)?/p>

上述兩種回歸模型公式中采用的最小二乘法和嶺回歸方法所得到的回歸模型系數(shù)βi

(1≤i≤D)的值都是非零的值,說明所有自變量X對相應(yīng)變量y值的生成都起著一定的作用。通常在實際的問題中,我們會最想知道哪些自變量對相應(yīng)變量起著關(guān)鍵性作用,即哪些變量最具有決定性,通過模型選擇(變量選擇),以提高回歸模型的解釋性和預(yù)測的精度。為了得到稀疏的回歸模型系數(shù),即部分βi(1≤i≤D)的值為0,TibshiraniR.提出了lasso回歸[4]的方法。

7.3.3套索回歸

套索回歸(LassoRegression)模型算法的目標(biāo)函數(shù)定義為

7.4稀疏保持映射

7.4.1稀疏保持映射原理受稀疏表示的啟發(fā),qiao等人提出稀疏保持映射方法。假設(shè)樣本集合為X=[x1,x2,…,xn

]∈RD*n,xi∈RD,i=1,2,…,n。根據(jù)稀疏表示理論,SPP首先重構(gòu)每個樣本xi并獲取其對應(yīng)的稀疏重構(gòu)系數(shù)向量si。si的求取可轉(zhuǎn)化為最小化問題

式中,I為標(biāo)量1,In

是元素全為1的n維列向量;si=[si,1,…,si,i-1,0,si,i+1,…,si,n]是n維且第i個元素為0的列向量。

由此可見,與傳統(tǒng)的稀疏表示理論相比,SPP算法中,在為每一個樣本進行稀疏重構(gòu)時,所采用的數(shù)據(jù)字典X是整個樣本集,其中被重構(gòu)樣本本身的重構(gòu)系數(shù)強制為0,即該樣本在對應(yīng)的字典中不起作用。而得到的稀疏重構(gòu)稀疏向量中較大的系數(shù)所對應(yīng)的是與被重構(gòu)樣本相似的樣本,因此可以說該方法保留了原始樣本的局部近鄰信息。

可以看出,兩種方式的不同之處在于誤差容忍度的不同,方式1的誤差容忍度是一個固定的值,而方式2將si和ti同時優(yōu)化,所以ti就是根據(jù)每個樣本所自動調(diào)節(jié)得到的誤差容忍度。

式(7-22)和式(7-23)中的l1范數(shù)最小化問題可以通過轉(zhuǎn)換成標(biāo)準線性規(guī)劃問題來求解,因此可對兩種方式計算并優(yōu)化得到每一個樣本的系數(shù)向量,得到稀疏重構(gòu)系數(shù)矩陣S定義為

對系數(shù)矩陣進行降維優(yōu)化,從原始的高維空間投影到低維子空間時,總是希望保留所需要的特征信息。為探尋最優(yōu)的特征向量,定義目標(biāo)函數(shù)

7.4.2稀疏保持映射算法流程

1.計算權(quán)重矩陣

有n個訓(xùn)練樣本點,每個訓(xùn)練樣本點是D維的,令X=[x1,x2,…,xn],現(xiàn)在重構(gòu)每一個訓(xùn)練樣本點xj,i=1,…,n,找到稀疏重構(gòu)稀疏向量si,使得

2.計算投影矩陣

我們期望在高維空間中的特性在降維后的低維空間中可以得到很好地保持,所以類似于近鄰保持嵌入(NPE),為了保持其局部結(jié)構(gòu),定于如下目標(biāo)函數(shù)

化簡得

即該問題的最優(yōu)解w對應(yīng)于以下特征值問題的d(低維空間的維數(shù))個最大的特征值所對應(yīng)的特征向量。

7.4.3SPP優(yōu)點

(1)SPP含有LPP和許多其他線性降維方法的優(yōu)點。例如,SPP是線性的,其權(quán)重矩陣是稀疏的,所以能更有效快速的計算。

(2)SPP不需要處理模型參數(shù)問題,例如在LPP和NPE中近鄰的大小,熱核的寬度等,因此SPP比較方便有效。

(3)SPP雖然屬于全局方法,但在其的稀疏表示過程中會擁有一些局部的特性。

(4)能容易的被擴展成在監(jiān)督的和半監(jiān)督的情況下的算法。

7.5基于Lasso的稀疏主成分

稀疏主成分分析即是為了解決這個問題而引進的一個算法。它會把主成分系數(shù)(構(gòu)成主成分時每個變量前面的系數(shù))變的稀疏,也即是把大多數(shù)系數(shù)都變成零,通過這樣一種方式,我們就可以把主成分的主要的部分凸現(xiàn)出來,這樣主成分就會變得較為容易解釋。

實現(xiàn)主成分分析稀疏化,最終會轉(zhuǎn)化為優(yōu)化問題,也即對本來的主成分分析中的問題增加一個懲罰函數(shù)。這個懲罰函數(shù)包含有稀疏度的信息。當(dāng)然,最終得到的問題是NP困難問題,為了解決它,我們需要采用一些方法逼近這個問題的解。這也是不同稀疏主成分分析算法不同的由來。

1.稀疏主成分原理

受Lasso的啟發(fā),ZouH.[8]等人則直接將主成分的求解問題轉(zhuǎn)化為Lasso回歸問題,這樣稀疏主成分的求解就有效地轉(zhuǎn)化成了線性模型的變量選擇問題,在此基礎(chǔ)上再引入彈性網(wǎng)(E-LasticNet)懲罰結(jié)構(gòu),就提出了基于Lasso的稀疏主成分(SimplifiedComponentTechniqueLasso,SCTLASSO)。為此,所有關(guān)于Lasso的想法都可以直接運用于稀疏主成分了。

1)基于Lasso的簡化主成分

一個很直觀的想法是直接將Lasso懲罰結(jié)構(gòu)應(yīng)用于主成分的求解,這也正是I.T.Jolliffe[9]在2003年提出SCTLASSO的想法。SCTLASSO可表述為如下優(yōu)化問題

這樣主成分的求解就可以轉(zhuǎn)化為線性模型的求解問題。注意當(dāng)n>D且X是列滿秩時,該定理中可取λ=0。但當(dāng)D>n且λ=0時,普通的最小二乘問題的解不唯一,這與n>D且X不是列滿秩的情形類似。引入λ>0后,就可以得到唯一解。由此可知引入λ>0可以得到一個統(tǒng)一的處理框架。下面將更進一步推廣以上結(jié)論。

定理3:如果?λ>0

由于定理3只是定理4的一種特殊情況,因此我們這里只給出定理4的證明。

通過以上定理我們比較系統(tǒng)地給出了稀疏主成分與懲罰回歸的關(guān)系。由前面的敘述可知,稀疏主成分的求解可以有效地轉(zhuǎn)化為懲罰回歸問題。而一般的Lasso懲罰回歸問題又可以通過最小角回歸算法來解決。因此稀疏主成分的計算也可以利用最小角回歸算法方便給出。

2.稀疏主成分的算法

一般的稀疏主成分算法如下:

算法:

(1)計算一般主成分的前k個主成分對應(yīng)的向量αi并令A(yù)=V[,1:K]。

(2)在給定A=(α1,…,αk)的情況下解如下的“elasticnet”回歸問題:

(3)對于給定的B=(β1,…,βk)計算XTXB=UDVT的SVD,并且令A(yù)=UVT。

(4)重復(fù)(2)、(3)至收斂。

(5)

其中,λ1,j是一個參數(shù),這個值是先給定一系列值計算出β,再回頭確定最優(yōu)的λ1,j,V︿是普通的最小二乘的分量。

實際上第2步求解“elasticnet”就是李永樂最小角回歸算法。

注意到以上算法的第2步中求解“elasticnet”回歸問題時所用的懲罰是“elasticnet”,實際上這里也可以用“adaptive-Lasso”懲罰結(jié)構(gòu),由此可以得到簡單自適應(yīng)稀疏主成分(SAS-PCA)。RonZass(2006)考慮到主成分應(yīng)用中更實際的一些問題提出了非負稀疏主成分(NS-PCA)并給出了相應(yīng)的算法。但是該算法相對比較復(fù)雜,并且不太方便給出選擇懲罰參數(shù)的方法。考慮到上面算法的第2步相當(dāng)于Lasso懲罰結(jié)構(gòu),直接可以用最小角回歸算法求解。

BradleyEfron等人(2004)在最小角回歸算法的基礎(chǔ)上改進給出了求解非負Lasso懲罰問題的解路徑,該算法可以用來求解非負稀疏主成分(NS-PCA),不過此時的非負稀疏主成分相當(dāng)于求解下面的優(yōu)化問題:

式中,β的各分量均加上非負條件的限制。

7.6稀疏判別分析

Clemmensen等人[12]提出稀疏判別分析(SparseDiscriminantAnalysis,SDA)算法,其在LDA中加入稀疏正則項,將分類、特征選擇和降維合并為一步。

通過評分法進行優(yōu)化后的SDA的準則函數(shù)為

評分向量θj給每類i分配一個實數(shù)θji,i=1,2,…,K。Yθ是一個n×q大小的評分后的訓(xùn)練樣本矩陣,根據(jù)Yθ對預(yù)測變量矩陣Xn×D進行回歸分析