莊姍姍，陳曉云

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

0 引 言

基因表達(dá)數(shù)據(jù)高維小樣本的特點(diǎn)，易產(chǎn)生維數(shù)災(zāi)難問題，從而降低聚類算法的性能[1]。因此，針對(duì)基因表達(dá)數(shù)據(jù)聚類的降維方法進(jìn)行研究是有重要意義的?，F(xiàn)有降維方法大多直接對(duì)基因表達(dá)數(shù)據(jù)進(jìn)行一次降維，再利用降維后的數(shù)據(jù)進(jìn)行聚類，未考慮降維和聚類之間的聯(lián)系，降維后的數(shù)據(jù)未必能很好地適應(yīng)聚類任務(wù)。

集成學(xué)習(xí)可提高模型的泛化能力，但較少將集成學(xué)習(xí)思想應(yīng)用于降維模型中。而基于加權(quán)的集成學(xué)習(xí)模型，常見的加權(quán)策略有兩種。一是由人為控制參數(shù)權(quán)重，比如平均加權(quán)[2]；二是將集成的全部數(shù)據(jù)集函數(shù)目標(biāo)值最小化[3]，即目標(biāo)值越小的數(shù)據(jù)集的權(quán)重越大，但是，目標(biāo)值越小的數(shù)據(jù)集，其模型的聚類性能不一定越好。

綜上所述，本文將集成學(xué)習(xí)思想和基于聚類能力的加權(quán)方法用于降維模型中，對(duì)高維基因表達(dá)數(shù)據(jù)抽取特征組合生成多個(gè)樣本子集，每個(gè)新樣本子集進(jìn)行降維，根據(jù)譜擾動(dòng)理論基于聚類能力學(xué)習(xí)獲得權(quán)重，加權(quán)組合得到最終降維結(jié)果，該方法將集成思想和譜擾動(dòng)加權(quán)用于降維模型，對(duì)特征多次學(xué)習(xí)充分利用高維特征，基于聚類能力加權(quán)組合多個(gè)降維結(jié)果，使得最終降維結(jié)果能夠更好地適應(yīng)聚類任務(wù)。

1 相關(guān)工作

1.1 投影降維方法

為解決維數(shù)災(zāi)難問題，許多研究假設(shè)高維觀測(cè)數(shù)據(jù)在其環(huán)繞空間中具有低維結(jié)構(gòu)，旨在尋找一投影將高維空間降維到低維子空間中[4]。

局部保持投影(LPP)意在維持投影前后樣本間的近鄰關(guān)系一致，是一種基于譜圖理論的降維方法[5]。LPP運(yùn)用k近鄰的關(guān)系來構(gòu)造樣本間的權(quán)圖，假設(shè)數(shù)據(jù)集X∈RD×n，有n個(gè)樣本和D個(gè)特征，如下定義相似矩陣Z

(1)

其中，Nk(xi)是xi的k近鄰組成的集合。LPP的目標(biāo)函數(shù)為

(2)

基于最小二乘優(yōu)化的低秩投影(LPLSR)[6]將觀測(cè)數(shù)據(jù)矩陣X∈RD×n分為兩部分X=Y+E，其中Y是真實(shí)數(shù)據(jù)，E是噪聲項(xiàng)，利用低秩方法將真實(shí)數(shù)據(jù)Y投影到潛在低維子空間中。LPLSR的目標(biāo)函數(shù)為

(3)

1.2 譜擾動(dòng)

Laplacians矩陣中元素任何微小的變化都會(huì)導(dǎo)致特征向量巨大的變化。譜聚類的聚類結(jié)果依賴于Laplacians矩陣的前k個(gè)特征向量，故可用一組特征向量的聚類表現(xiàn)來衡量聚類能力。如果聚類能力差異越小的兩組特征向量，它們之間的聚類結(jié)果就越相近。兩組特征向量之間聚類能力的差異采用歐式距離衡量，會(huì)出現(xiàn)兩特征向量組歐式距離大但聚類能力相近的情況,進(jìn)一步可用兩組特征向量之間的劃分特征空間的規(guī)范角來衡量聚類能力的差異。因此，可基于譜擾動(dòng)理論用兩組特征空間的最大規(guī)范角來衡量聚類結(jié)果之間的差異。

θj=arccosγj

(4)

2 本文方法

2.1 集成降維

圖1 模塊的劃分組合

對(duì)c個(gè)新樣本子集X1,…,Xc應(yīng)用文獻(xiàn)[6]中基于最小二乘優(yōu)化的低秩投影(LPLSR)進(jìn)行降維

(5)

其中，Pa、Za和Ea分別為樣本子集Xa的低秩投影矩陣、相似矩陣和噪聲項(xiàng)。每個(gè)樣本子集Xa降維后的數(shù)據(jù)為Ya=PaTXa，集成降維為

(6)

其中，μa是降維后樣本子集Xa的權(quán)重。降維過程中應(yīng)用集成學(xué)習(xí)思想，對(duì)特征多次學(xué)習(xí)，加權(quán)組合多個(gè)降維結(jié)果，充分利用基因表達(dá)數(shù)據(jù)的高維特征。

權(quán)重μ=[μ1,…,μc]不同的定義得到不同的模型：可根據(jù)降維后每個(gè)子集的誤差為權(quán)獲取權(quán)重，誤差越小的數(shù)據(jù)子集其權(quán)重越大，得到EM-IDR

(7)

然而，目標(biāo)值越小的數(shù)據(jù)子集，所對(duì)應(yīng)模型的聚類效果不一定越好。也有直接人為定義權(quán)重的，大多采用平均加權(quán)，即A-IDR

μa=1/c，a∈{1,…,c}

(8)

但是每個(gè)樣本子集Xa的數(shù)據(jù)不同，降維后的數(shù)據(jù)對(duì)最終的聚類結(jié)果的影響不盡相同。

綜上分析，本文進(jìn)一步改進(jìn)加權(quán)方法，基于譜擾動(dòng)理論衡量聚類能力來學(xué)習(xí)權(quán)重μ，可用一組特征向量即Laplacians矩陣的前k個(gè)特征向量來衡量聚類能力，用兩組特征向量之間的劃分特征空間的規(guī)范角來衡量聚類能力的差異。理想情況下，由于樣本子集X1,…,Xc的每個(gè)樣本都源于同一原始樣本，每個(gè)樣本子集的聚類結(jié)果應(yīng)該和一致的聚類結(jié)果相同，因而每個(gè)樣本子集真實(shí)的相似矩陣應(yīng)該是相同的，即所有樣本子集之間存在一個(gè)相同的真實(shí)的Laplacians矩陣。然而在一般情況下，真實(shí)的Laplacians矩陣是未知的，通過μ加權(quán)組合每個(gè)樣本子集的Laplacians矩陣獲得一致Laplacians矩陣

(9)

本文基于兩個(gè)原則學(xué)習(xí)權(quán)重μ：一是將一致聚類結(jié)果與每個(gè)子集聚類結(jié)果的差異最小化原則，二是聚類能力相近的樣本子集應(yīng)有近似權(quán)重原則，通過樣本子集間的聚類能力更好地集成降維，使降維后的數(shù)據(jù)更適用于聚類任務(wù)。

2.2 加權(quán)策略

(10)

(11)

原則二：聚類能力相近的樣本子集應(yīng)有近似權(quán)重。如上所述，根據(jù)譜擾動(dòng)理論，兩樣本子集間的聚類能力越相似，特征空間中的最大規(guī)范角越小，權(quán)重越相近。令Cab∈[0,π]為Xa與Xb間的最大規(guī)范角，Rab=π-Cab，則有

(12)

最后，將式(11)和式(12)相結(jié)合，得到最終譜擾動(dòng)加權(quán)目標(biāo)函數(shù)

(13)

其中，式(13)中最后一項(xiàng)為正則項(xiàng)。保證每個(gè)樣本子集Xa降維后的數(shù)據(jù)Ya都對(duì)最終降維結(jié)果Y有貢獻(xiàn)，η和β均為平衡參數(shù)。

式(13)去掉與μ無關(guān)項(xiàng)，可得

(14)

式(14)是標(biāo)準(zhǔn)的二次規(guī)劃問題，可用Matlab的quadprog求解μ。

2.3 譜擾動(dòng)集成降維算法

算法：譜擾動(dòng)集成降維算法(SD-IDR)

輸入：數(shù)據(jù)矩陣X，參數(shù)λ、η、β，樣本劃分?jǐn)?shù)B,組合數(shù)b

輸出：降維后的樣本矩陣Y

步驟2 根據(jù)式(5)求解X1,X2,…,Xc的投影矩陣P1,P2,…,Pc與相似矩陣Z1,Z2,…,Zc；

步驟3 根據(jù)式(14)求解μ；

步驟4 根據(jù)式(6)計(jì)算降維后的樣本矩陣。

SD-IDR算法的時(shí)間復(fù)雜度主要有兩方面：

一是求解投影矩陣和相似矩陣，該時(shí)間復(fù)雜度同LPLSR的時(shí)間復(fù)雜度相同，即為O(n3+n2d)，由于基因表達(dá)數(shù)據(jù)中d>>n，故時(shí)間復(fù)雜度為O(n2d)。二是求解權(quán)重，該過程主要在于計(jì)算Ta、Sa和Q，時(shí)間復(fù)雜度為O(c3n2)。

綜上所述，最終SD-IDR算法的時(shí)間復(fù)雜度為O(c3n2+n2d)。

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

實(shí)驗(yàn)選用6個(gè)公開應(yīng)用較為廣泛的基因表達(dá)數(shù)據(jù)集[8,9]：Leukemia0，Leukemia1，Leukemia2，Lung_Can-cer，DLBCL和Lymphoma，信息整理見表1。

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

3.1 實(shí)驗(yàn)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果與分析

本文對(duì)降維后樣本采用K-means聚類，降維質(zhì)量以聚類準(zhǔn)確率ACC來衡量。選用3種集成加權(quán)降維方法：EM-IDR、A-IDR和S-ELM[3]，4種非集成降維方法：LPLSR[6]、URAFS[10]、SOGFS[11]和JELSR[12]，與本文SD-IDR方法對(duì)比。所有方法的平衡參數(shù)也均在[10-3,10-2,…,102,103]中遍歷取優(yōu)，為盡可能避免隨機(jī)性的因素，所有方法都運(yùn)行10次取均值。

由表2可見，譜擾動(dòng)集成降維SD-IDR在所有數(shù)據(jù)集下的聚類準(zhǔn)確率最高。對(duì)比LPLSR、URAFS、SOGFS和JELSR單一降維方法，SD-IDR方法的聚類效果更為理想，這表明將集成學(xué)習(xí)思想用于降維模型，對(duì)特征進(jìn)行多次學(xué)習(xí)，能夠充分利用基因表達(dá)數(shù)據(jù)的高維特征，提高聚類準(zhǔn)確率。對(duì)比EM-IDR、A-IDR和S-ELM集成降維方法，SD-IDR基于聚類能力的集成降維方法的聚類效果更為理想，這表明本文利用譜擾動(dòng)理論的加權(quán)集成方法通過聚類能力更好地指導(dǎo)降維，使得最終降維后的樣本能夠更好地適應(yīng)聚類任務(wù)。

表2 聚類準(zhǔn)確率對(duì)比/%

4 結(jié)束語(yǔ)

本文將集成學(xué)習(xí)思想和基于聚類能力的加權(quán)方法用于降維模型中，對(duì)高維數(shù)據(jù)抽取特征組合生成多個(gè)樣本子集，每個(gè)新樣本子集進(jìn)行降維，根據(jù)譜擾動(dòng)理論基于兩個(gè)原則：一致聚類結(jié)果與每個(gè)子集聚類結(jié)果差異最小化原則和聚類能力相近的樣本子集應(yīng)有近似權(quán)重原則，學(xué)習(xí)獲得權(quán)重μ，加權(quán)組合得到最終降維結(jié)果。該方法將集成思想和譜擾動(dòng)加權(quán)用于降維模型中，對(duì)特征多次學(xué)習(xí),充分利用高維特征，利用聚類能力加權(quán)組合多個(gè)降維結(jié)果，通過聚類能力更好地集成降維，使得降維能夠更好地適應(yīng)聚類任務(wù)。