基于內(nèi)積正則化的自表示無(wú)監(jiān)督特征選擇算法

武 文， 段雪峰

(桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,廣西 桂林 541004)

用跡函數(shù)表示為‖B‖2,1=tr(BTGB)，其中G為對(duì)角矩陣，滿足Gii=1/2‖Bi‖2，Bi為矩陣B的第i個(gè)行向量。

特征選擇按有無(wú)標(biāo)簽分為有監(jiān)督和無(wú)監(jiān)督兩類(lèi)。在實(shí)際應(yīng)用中，大多數(shù)數(shù)據(jù)無(wú)標(biāo)簽信息，所以要通過(guò)已有的數(shù)據(jù)對(duì)信息進(jìn)行加工過(guò)濾，選擇其中有限個(gè)特征來(lái)組成一個(gè)可以代表整個(gè)特征空間的特征子集。該子集比原始特征空間的維數(shù)低，但具有原始特征空間的特性。越來(lái)越多的新技術(shù)被引入特征選擇算法模型中，如稀疏學(xué)習(xí)[1]、圖正則化[2]、譜聚類(lèi)[3]、自表示[4]和矩陣分解[5-6],通過(guò)增強(qiáng)特征之間的局部結(jié)構(gòu)信息和應(yīng)用局部結(jié)構(gòu)在特征的表示上，可以有效地提高特征選擇的準(zhǔn)確率?？紤]到l2,1范數(shù)的魯棒性及其可以降低數(shù)據(jù)的冗余性，魯棒無(wú)監(jiān)督特征選擇方法[5]和自表示特征選擇方法[4]使用l2,1范數(shù)作為損失函數(shù)和正則項(xiàng)。

在信息時(shí)代，結(jié)構(gòu)化矩陣的低秩逼近頻繁出現(xiàn)在各個(gè)領(lǐng)域。對(duì)于對(duì)稱(chēng)半正定矩陣的低秩逼近問(wèn)題，白建超等[7]基于矩陣的滿秩分解和非負(fù)矩陣分解算法構(gòu)造了一種新的乘性迭代算法。針對(duì)對(duì)稱(chēng)半正定矩陣的正則化低秩逼近問(wèn)題，張雪偉等[8]基于對(duì)稱(chēng)半正定矩陣的Gramian分解將原問(wèn)題轉(zhuǎn)化為等價(jià)的無(wú)約束優(yōu)化問(wèn)題，并通過(guò)構(gòu)造非線性共軛梯度方法進(jìn)行求解。黃瓊慧等[9]利用滿秩分解來(lái)刻畫(huà)問(wèn)題的可行集，從而將非負(fù)矩陣的正則化逼近問(wèn)題轉(zhuǎn)化為等價(jià)的非負(fù)矩陣分解問(wèn)題，并通過(guò)構(gòu)造交替最小二乘方法進(jìn)行問(wèn)題求解。

研究如下問(wèn)題：

問(wèn)題1對(duì)于一個(gè)給定的高維數(shù)據(jù)矩陣X=[x1,x2,…,xn]T∈Rn×m，特征選擇過(guò)程可表述為以下無(wú)約束優(yōu)化問(wèn)題：

(1)

其中Y∈Rn×m為偽標(biāo)簽矩陣。

對(duì)于問(wèn)題1的損失函數(shù)，用l2,1范數(shù)替代Frobenius范數(shù)。正則化項(xiàng)的選擇也至關(guān)重要，常用的正則項(xiàng)有l(wèi)0范數(shù)、l1范數(shù)、l2范數(shù)、跡范數(shù)、Frobenius范數(shù)及核范數(shù)。對(duì)于正則項(xiàng)，由于內(nèi)積正則化項(xiàng)最近在許多研究成果中使用且取得良好的聚類(lèi)效果[10]，用內(nèi)積正則化項(xiàng)替代l2,1范數(shù)。 特征權(quán)重矩陣W的內(nèi)積正則項(xiàng)為

且有

考慮到特征與特征之間的線性非負(fù)相關(guān)性，即

X=XW+R,W≥0，

其中R為殘余矩陣，只有保證‖R‖2,1的值盡可能地小，才能保證特征選擇的精確性。

基于以上分析，將問(wèn)題1重構(gòu)為如下問(wèn)題：

問(wèn)題2對(duì)于給定的數(shù)據(jù)矩陣X∈Rn×m和特征權(quán)矩陣W∈Rm×m，W的元素均為非負(fù)，特征選擇過(guò)程可表述為

(2)

1 求解問(wèn)題2的乘式更新算法

令

F(W)=‖X-XW‖2,1+λΩ(W)=

‖X-XW‖2,1+λ(tr(EWWT)-tr(WWT)),

(3)

對(duì)于非負(fù)約束W≥0,引入拉格朗日乘子矩陣α∈Rm×m，則式(2)的拉格朗日函數(shù)為

L(W)=‖X-XW‖2,1+λΩ(W)-tr(αW)=

tr(X-XW)TP(X-XW)+λ(tr(EWWT)-

tr(WWT))-tr(αW)，

其中P為對(duì)角矩陣，且

根據(jù)矩陣跡函數(shù)對(duì)矩陣求導(dǎo)法則，可得

根據(jù)KKT條件αijWij=0，可得W的乘式更新表達(dá)式：

(4)

算法1內(nèi)積正則化自表示特征選擇算法

輸入：X∈Rn×m，k為特征選擇的個(gè)數(shù)，平衡參數(shù)λ>0，t為迭代次數(shù)，δ>0為充分小的正數(shù)。

輸出：被選擇的特征的指標(biāo)集{Zx1,Zx2,…,Zxk}。

1.初始化W，且記W=[w1,w2,…,wm]T；

2.開(kāi)始循環(huán)；

4.按式(4)更新W，

5.當(dāng)滿足收斂標(biāo)準(zhǔn)時(shí)，停止循環(huán)；

6.求出‖wi‖2,i=1,2,…,m，按降序排列并選擇前k個(gè)特征，輸出對(duì)應(yīng)的指標(biāo)集。

定義1若以下2個(gè)條件同時(shí)成立：

1)Φ(u,v)>Ψ(u)；

2)Φ(u,u)=Ψ(u)。

則Φ(u,v)是Ψ(u)的輔助函數(shù)。

引理1若Φ是Ψ的輔助函數(shù)，則Ψ在如下更新法則下是一個(gè)單調(diào)遞減函數(shù)：

其中t為迭代次數(shù)。

證明由更新法則

可得

Φ(u(t+1),u(t))≤Φ(u(t),u(t))，

又已知Φ是Ψ的輔助函數(shù)，則有

Ψ(u(t+1))≤Φ(u(t+1),u(t))≤

Φ(u(t),u(t))=Ψ(u(t)),

即Ψ是一個(gè)單調(diào)遞減函數(shù)，證畢。

引理2函數(shù)

是Ψij(Wij)的輔助函數(shù)。

證明令式(3)中關(guān)于W的函數(shù)為Ψ(W)，則

Ψ(W)=-2tr(XTPXW)+tr(WTXTPXW)+

λ(tr(EWWT)-tr(WWT))。

對(duì)Ψij關(guān)于Wij求導(dǎo)，得

Ψij(Wij)=(-2XTPX+2WXTPX+2λEW-2λW)ij,

(5)

根據(jù)矩陣乘法的運(yùn)算法則，有以下2個(gè)不等式成立：

故顯然有式(5)成立。因此，

Φij(Wij,Wij(t))≥Ψij(Wij)，

且

Φij(Wij,Wij)=Ψij(Wij)

成立。由定義1知，Φij(Wij,Wij(t))是Ψij(Wij)的輔助函數(shù)。

定理1由算法1產(chǎn)生的迭代序列收斂于問(wèn)題2的解。

證明由引理2可得，Ψ(W)是一個(gè)單調(diào)函數(shù)，進(jìn)而F(W)也是單調(diào)函數(shù)且有界，故其一定是收斂的，即存在一個(gè)W*，使得

所以收斂點(diǎn)W*即為問(wèn)題(2)的解。

2 數(shù)值實(shí)驗(yàn)

用4個(gè)國(guó)際標(biāo)準(zhǔn)數(shù)據(jù)集驗(yàn)證算法1的可行性和有效性。所有實(shí)驗(yàn)在MATLAB R2014a環(huán)境下進(jìn)行，其中相對(duì)誤差的計(jì)算式為

數(shù)值實(shí)驗(yàn)的停機(jī)標(biāo)準(zhǔn)為ε(t)<10-4，數(shù)據(jù)集描述如表1所示。

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

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

選取的4個(gè)國(guó)際標(biāo)準(zhǔn)數(shù)據(jù)集如下。

1)COIL20數(shù)據(jù)集，包含20個(gè)不同類(lèi)別的物體，將每個(gè)物體放在一個(gè)轉(zhuǎn)盤(pán)上，每隔5°進(jìn)行一次拍照，共1 440張圖片。

2)PIE數(shù)據(jù)集，包括53個(gè)不同的人，每人在不同光線條件下以不同的姿勢(shì)和表情拍攝22張人臉圖片，共1 166張。

3)ORL數(shù)據(jù)集，包括40個(gè)不同的人，每人對(duì)應(yīng)10張不同面部表情的人臉圖片，共400張。

4)Yale數(shù)據(jù)集，包含15個(gè)不同的人，每人拍攝11張不同光線、動(dòng)作和神情的人臉圖片，共165張。

2.2 對(duì)比算法

選取3種特征選擇算法作為對(duì)比算法，分別為最大方差法[12]、拉普拉斯得分法[11]和正則判別信息特征選擇法[13]。

最大方差法MaxVar直接對(duì)原特征矩陣計(jì)算每個(gè)特征的方差，選出方差最大的前k個(gè)特征。拉普拉斯得分法Lapscore[11]利用原始特征建立鄰接圖，通過(guò)鄰接矩陣和度矩陣得到拉普拉斯矩陣，從而計(jì)算出每個(gè)特征的拉普拉斯得分，然后選出得分最高的前k個(gè)特征。正則判別信息特征選擇方法UDFS通過(guò)數(shù)據(jù)的局部判別信息和特征的相關(guān)性選擇最有區(qū)別性的特征，通過(guò)計(jì)算局部散度矩陣和類(lèi)間散度矩陣，利用線性分類(lèi)器將每個(gè)樣本映射到一個(gè)低維空間，并用一個(gè)l2,1范數(shù)正則化項(xiàng)進(jìn)行特征選擇，得到的稀疏系數(shù)矩陣按照其行向量的l2范數(shù)值的排名選出排名靠前的數(shù)據(jù)特征。

2.3 評(píng)價(jià)標(biāo)準(zhǔn)

對(duì)于不同算法選出來(lái)的特征子集，經(jīng)過(guò)K均值聚類(lèi)后可得到聚類(lèi)標(biāo)簽，通過(guò)聚類(lèi)標(biāo)簽與原標(biāo)簽可計(jì)算特征選擇的準(zhǔn)確率(RACC) 和標(biāo)準(zhǔn)互信息(VNMI)的值，它們的值介于0與1之間，值越高，說(shuō)明聚類(lèi)效果越好，即所選出來(lái)的特征子集越具代表性。設(shè)si為聚類(lèi)后得到的標(biāo)簽，ti為真正的標(biāo)簽，則

對(duì)于給定的2個(gè)變量P、Q，VNMI的計(jì)算式為

其中：I(P,Q)為P和Q的互信息值；H(P)和H(Q)分別為P和Q的熵。

2.4 參數(shù)選擇

正則系數(shù)λ選自集合{10-4,10-2,1,102,104}。被選擇的特征數(shù)k選自集合{20,40,60,…,200}，最大迭代次數(shù)設(shè)置為300。固定λ=100,充分小的正數(shù)δ=10-4。

2.5 數(shù)值結(jié)果分析

圖1為算法1在4個(gè)數(shù)據(jù)集上進(jìn)行特征選擇后得到的相對(duì)誤差變化曲線。從圖1可看出，當(dāng)應(yīng)用算法1對(duì)數(shù)據(jù)集進(jìn)行特征選擇時(shí)，經(jīng)過(guò)數(shù)次迭代就可以使相對(duì)誤差達(dá)到充分小且穩(wěn)定的狀態(tài)，這表明算法是收斂且有效的。

圖1 算法1在數(shù)據(jù)集上的相對(duì)誤差變化曲線

表2、3為不同算法在不同數(shù)據(jù)集上通過(guò)K均值聚類(lèi)[14]后得到的準(zhǔn)確率與標(biāo)準(zhǔn)互信息的值。每種算法在每個(gè)數(shù)據(jù)集上選擇不同數(shù)目的特征，使得所選特征的個(gè)數(shù)遍歷指標(biāo)集{20,40,…,180,200}，然后求出選擇不同特征數(shù)之后得到的準(zhǔn)確率的平均值與標(biāo)準(zhǔn)互信息的平均值。從表2、3可看出，與最大方差法、拉普拉斯得分法和正則判別信息特征選擇法相比，算法1的準(zhǔn)確率更高，標(biāo)準(zhǔn)互信息值也最高，從而說(shuō)明該特征選擇方法是有效且可行的。

表2 不同算法的準(zhǔn)確率

表3 不同算法的標(biāo)準(zhǔn)互信息值

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

提出了一種用l2,1范數(shù)自表示作為損失函數(shù)并與內(nèi)積正則化項(xiàng)相結(jié)合的無(wú)監(jiān)督特征選擇算法，利用l2,1范數(shù)、內(nèi)積正則化項(xiàng)與跡函數(shù)的關(guān)系將目標(biāo)函數(shù)轉(zhuǎn)換為可以求導(dǎo)的跡函數(shù)形式，并用拉格朗日乘子法對(duì)問(wèn)題進(jìn)行優(yōu)化求解。數(shù)值實(shí)驗(yàn)結(jié)果表明，該算法對(duì)于特征選擇是可行且有效的。