基于l1,2懲罰典型相關分析的特征選擇

趙迎利 王凱明 肖玉柱 宋學力

(長安大學理學院 陜西 西安 710064)

0 引 言

從古至今，人們認識(學習)事物的渠道都是多樣的。比如，對某疾病診斷，古代中醫通過望、聞、問、切四種方式來了解患者；而現代的醫生可以通過化驗體液、B超、CT、核磁共振和腦電圖等多種檢查手段來采集患者的數據，以此了解患者的狀況。以機器學習的觀點，患者可以稱為醫生學習的一個樣本，醫生以不同方式采集到患者的數據稱作樣本的特征，不同的采集方式稱為不同的模態。然而，高維特征的多模態數據中不可避免地會含有不相關和冗余的特征。事實上，在機器學習領域，這是一個普遍的現象。對于特定的學習任務，數據的真實維度[1]往往比采樣數據的維度低得多[2]。所以，需要對樣本特征的所在空間降維，防止維數災難[3]或者過擬合。降維的方法大致可分為特征提取和特征選擇兩類。按照某種學習準則或者統計準則，最大可能地保留相關的特征，去除不相關或者冗余特征，這就是特征選擇[4]問題。

特征選擇的統計準則有很多，稀疏典型相關分析[5-6](Sparse canonical correlation analysis，SCCA)是一種通過提取具有最大相關性的典型相關變量，并且通過稀疏典型向量來實現特征選擇的方法。 l1范數是稀疏典型向量的一種常用的具有凸性和連續性的正則化方法[7]，文獻[8]就是通過l1范數懲罰典型相關向量來實現特征選擇。由于數據的群組信息是數據固有的系統機理信息或者滿足某種統計信息的特征子集，所以在特征選擇的任務里考慮特征的群組信息是必要而且重要的。為了在特征選擇里兼顧數據的群組信息，文獻[9]引入了l2,1范數懲罰的典型相關分析(CCA)模型，該懲罰對數據特征實現了組間稀疏。事實上，對于某些特定問題的數據，不僅不同的群組之間會有不相關或者冗余特征，而且組內往往也會存在不相關或者冗余特征，所以，特征的組內稀疏也是重要的甚至必要的。文獻[10]發現了l1,2范數作為學習目標的正則約束可實現組內稀疏的作用。綜上，無論l2,1還是l1,2約束，都需要數據的群組信息。當數據集中的群組信息未知或者不可用時，這種組間或者組內稀疏方法的應用會受到限制。文獻[11]提出的特征隨機分組方法，使得組信息缺失條件下的組內稀疏成為可能。所以，本文主要研究多模態高維數據的特征選擇問題，應用l1,2范數兼顧群組信息作為稀疏懲罰項，通過優化數據之間的相關性來實現特征選擇。

本文的主要思想有：1) 考慮數據的組內稀疏問題，選擇向量的l1,2范數懲罰CCA；2) 對于組信息缺失的數據，應用隨機分組方法產生組信息；3) 從應用的角度，這種方法可以更完整地選取相關特征，所以適用于對特征查全要求較高的實際問題，如某些惡性傳染病或者腫瘤疾病的特征選擇問題。

1 基礎知識

1.1 典型相關分析

給定兩個數據集X∈Rn×p、Y∈Rn×q，其中，X包含有n個樣本、p個特征；Y包含有n個樣本、q個特征。CCA[5]是以最大的相關性找到數據X和Y特征之間的典型相關變量，模型表示如下:

(1)

s.t.uTXTXu=1,vTYTYv=1

式中:u和v分別表示X和Y對應的典型向量。

1.2 懲罰項的提出

向量w=[w1,w2,…,wd]T∈Rd的l1，2范數可表示為[10]:

(2)

式中: 將w按分量分成G個組,wg表示第g個組。

基于此范數，構造本文優化目標所需的懲罰項P1、P2。

假設數據X按特征分為G組，對其典型向量u=[u1,u2,…,up]T構造懲罰項P1，表示為:

(3)

式中：πg是第g組的指標集。相應地，把數據集Y的特征分為H組，對應的v=[v1,v2,…,vq]T構造懲罰項P2，表示為:

(4)

式中:πh是第h組的指標集。

1.3 模型的提出

本文針對數據組信息不全甚至缺失的特征選擇問題，分別將數據X、Y按特征隨機分成互不相交的G、H組并盡可能地讓每組包含相同數目的特征，在典型相關分析的框架內引入懲罰項P1、P2，構造目標函數如下：

(5)

s.t.uTXTXu=1，vTXTXv=1

式中:ug和vh分別表示根據特征被隨機分組后對應的第g組和第h組。

這樣，我們通過正則項P1、P2懲罰X和Y的典型向量u、v，以及稀疏隨機分組后的組內特征，實現攜帶組關聯信息的特征選擇。

1.4 模型的求解以及算法設計

由于大多數應用l1稀疏約束的正則優化問題都采用軟閾值算法求解，而為了求解簡便，都會假設特征之間正交，即XTX=I、YTY=I[12]。然而，在大多數真實數據中，這個假設是不合理的，因為特征之間往往不具有正交的特性。所以這個假設將會不可避免的限制識別有意義的關聯信息。為了克服這個局限性，本文利用拉格朗日乘子法，采用交替最小二乘法解決這個優化問題。為了求解方便，將式(5)轉化為如下等價形式：

(6)

s.t.uTXTXu=1,vTXTXv=1

首先對式(6)構造拉格朗日方程:

L(u,v,λ,β)=-uTXTYv+λ1‖u‖G+λ2‖v‖H+

(7)

式中：β1、β2為拉格朗日乘子，可利用交叉驗證估計。 考慮到本文使用的懲罰項P1、P2中含有l1范數，如果|ui|=0、|vj|=0，則目標函數L在0點處不可微，可以通過分別給ui、vj加上一個很小的正數ξ來改善。

然后對u和v分別求偏導，利用極值存在的必要條件得到：

(8)

(9)

即:

(10)

(11)

最后求解式(10)和式(11)得到:

(12)

(13)

模型算法的偽代碼如算法1所示。

算法1模型算法

Input:X=[x1,x2,…,xn]T，Y=[y1,y2,…,yn]T

Output: 典型變量u和v

1) 初始值t=0,ut,vt;

2) While not converged do

4) 固定vt,解ut+1;

7) 固定ut+1,解vt+1;

9)t=t+1;

10) end while

11) 返回u和v的值

1.5 算法的收斂性分析

受文獻[13]的啟發，下面給出本文算法的收斂性分析。算法的目標的是求解式(6)的最小值，所以根據單調有界原理，算法的收斂性證明可轉化為驗證目標函數具有以下兩個性質：1) 目標函數有下界;2) 目標函數單調遞減。

首先驗證目標函數有下界。為方便起見，在式(7)中，記:

(14)

下面證明式(14)中函數N(λ,β)有下界。

根據式(6)和式(7)可知，顯然N(λ,β)≤-uTXTYv。

分別對N中的β1、β2求偏導，有：

(15)

(16)

這表明: 1) 當u,v∈[-1,1]、-uTXTYv∈[-1,1];2) maxN(λ,β)=-uTXTYv。

令:

-uTXTYv

(17)

即N*∈[-1,1],即證得目標函數有下界。

然后驗證目標函數單調遞減。為了證明目標函數的單調遞減性質，對向量w的l1,2范數引入如下引理。

引理1[10]：

(18)

式中：wt、w表示兩個非零向量，wt表示w更新后的值，w、wt按分量分成G個組,wg、(wt)g表示第g個組中的部分分量。

利用引理1，把目標函數單調遞減證明分為兩步。

第一步，對于目標函數L(u,v,λ,β)，固定v解u時，關于u的目標函數變為如下形式：

(19)

由引理1并且從算法的第8)步可得:

(20)

這就證明了第一步，L(ut,v)≤L(u,v)。

第二步，類似地，對于目標函數L(u,v,λ,β)，固定ut解v時，同第一步證明，可得L(ut,vt)≤L(ut,v)。

綜上，可以證明L(ut,vt)≤L(u,v)，即算法在每次的迭代過程中，目標函數是單調遞減的，所以由單調有界原理，模型的算法是收斂的。

2 模型仿真

2.1 構造模擬數據

為了驗證算法的有效性和正確性，本文構造了一組模擬數據對算法進行測試。給定X、Y的樣本數為80，特征數分別為100、120，模擬實驗的數據集生成方法如下[14]：1) 預先設定數據集X、Y的結構，分別產生u和v；2) 生成潛在變量ξ～N(0,In×n)；3) 生成數據X，其樣本滿足xi～N(ξiu,Σx)， (Σx)pl=exp-|up-ul|，uρ、ul分別為u的第ρ、l個坐標；4) 生成數據集Y，其樣本滿足yi～N(ξiv,Σy)，其中(Σy)pl=exp-|vp-vl|，vρ、vl分別為v的第ρ、l個坐標。將X中的特征隨機分為10個不相交的組，將Y中的特征隨機分為12個不相交的組。

2.2 參數選取

式(12)和式(13)中有四個可調參數，采用五折交叉驗證，將所有的樣本隨機分成五份，其中四份作為訓練集，剩余的一份樣本作為測試集進行測試，從[10-2,10-1,100,101,102]中產生最優的參數。

2.3 評價標準

實驗的評價標準為找到與真實相關系數最接近的一組，為了盡可能地減小因選擇訓練集與測試集的差異而對結果造成的影響，本文選擇5次實驗中訓練集與測試集所得的相關系數之差最小的一組u和v作為最終的結果，具體形式為：

(21)

式中:corr表示Pearson相關系數，k表示交叉驗證的次數(此處k=5)，corrtrain=corr(Xtrainu,Ytrainv)，Xtrain、Ytrain表示訓練集，corrtest=corr(Xtestu,Ytestv)，Xtest、Ytest表示測試集，u、v分別表示由訓練集得到的典型向量。

2.4 實驗結果與分析

本文對同一組數據集采用五折交叉驗證的方法將基于l2范數和基于l2,1范數的典型相關分析的特征選 擇方法與本文的方法作對比,分別得到三種方法下的每一折的相關系數與其對應的平均值對比表,分別關于典型變量u、v的實驗效果對比圖和估計的典型變量的AUC對比表，如表1所示。

表1 模擬數據集上的五折交叉驗證結果

續表1

表1給出了三種方法下的五折交叉驗證后訓練集與測試集的相關系數的估計值。可以看出，在訓練集上，基于l2,1范數特征選擇的方法有較小的平均估計誤差；但是在測試集上，基于l1,2范數特征選擇的方法有較小的平均估計誤差。一般而言，測試集上的結果比訓練集上的結果更能體現模型的泛化性能[13]。

圖1和圖7給出了典型向量u、v設計的真實值(后均稱為真實值)。圖2和圖8分別表示基于l2范數的特征選擇方法得到的u和v。圖3和圖5分別表示基于l2,1范數和l1,2范數的特征選擇方法應用隨機分組得到的u。圖9和圖11分別表示基于l2,1范數和l1,2范數的特征選擇方法應用隨機分組得到的v。為了更清晰直觀地展示實驗效果，將圖3、圖5中的u和圖9、圖11中的v按照特征索引還原之后分別得到圖4、圖6和圖10、圖12。

圖1 典型向量u的真實值

圖2 l2懲罰下的典型向量u

圖3 隨機分組后l2,1懲罰下的典型向量u

圖4 隨機分組l2,1懲罰下u的位置還原圖

圖5 隨機分組后l1,2懲罰下的典型向量u

圖8 l2懲罰下的典型向量v

圖9 隨機分組后l2,1懲罰下的典型向量v

圖10 隨機分組后l2,1懲罰下v的位置還原圖

圖11 隨機分組后l1,2懲罰下的典型向量v

圖12 隨機分組后l1,2懲罰下v的位置還原圖

從圖2、圖4與圖1的對比中可以看出,基于l2范數和基于l2,1范數的特征選擇的方法估計出的u的非零坐標位置與真實位置存在較大差異。具體的，在圖1中可以看到20

表2給出了三種方法的典型變量的AUC(ROC曲線下方的面積)，一般來說，AUC越大表明模型的預測性能越好。從表中可以看出基于l1,2范數特征選擇的方法估計出的u和v的AUC明顯大于基于l2范數和基于l2,1范數的特征選擇方法估計出的u和v的AUC。

表2 三種方法估計的典型向量的AUC

實驗結果表明，本文提出的基于l1,2范數典型相關分析的特征選擇的方法不僅能夠估計出兩模態數據間精確的相關系數，而且在去掉不相關特征的同時能夠準確識別出兩模態數據中所有重要的特征。

3 結 語

本文提出了一種無先驗組內稀疏典型相關的特征選擇方法。通過將數據特征隨機分成互不相交的組并盡可能地讓每組包含相同數目的特征，以l1.2范數作為正則項懲罰CCA，對組內信息應用l1范數，組間信息應用l2范數，實現了關聯特征的選擇。模擬數據的實驗表明，基于隨機分組的組內稀疏特征選擇模型選擇的特征更加全面，漏選的特征更少，適用于某些惡性傳染病或者腫瘤疾病的特征選擇。

本文的方法對于兩模態數據取得較好的效果，現實生活中也存在三模態甚至更多模態的數據，所以需擴展本文的模型至三模態甚至更高模態的模型，實現特征選擇將是下一步研究的重點。