面向高維數(shù)據(jù)的凹型自表示特征選擇方法

朱國(guó)榮，馮 昊，葉玲節(jié)

（國(guó)網(wǎng)浙江省電力有限公司經(jīng)濟(jì)技術(shù)研究院，杭州 310008）

0 引言

隨著電子傳感器和網(wǎng)絡(luò)的蓬勃發(fā)展，大量高維數(shù)據(jù)涌現(xiàn)[1]，不僅增加了進(jìn)程時(shí)間和空間復(fù)雜度，且其伴隨的維數(shù)災(zāi)難嚴(yán)重影響了聚類和分類性能[2]。特征選擇不僅可以有效去除非相關(guān)和冗余特征，降低計(jì)算和存儲(chǔ)成本，也能有效增強(qiáng)分類、聚類等機(jī)器學(xué)習(xí)模型的泛化能力[3-4]。近年來，許多研究都致力于開發(fā)新的特征選擇算法[5-8]。

一般來說，特征選擇方法根據(jù)有無標(biāo)簽可以分為2類：有監(jiān)督特征選擇和無監(jiān)督特征選擇。隨著網(wǎng)絡(luò)和社交媒體的廣泛使用，產(chǎn)生了大量無標(biāo)記數(shù)據(jù)，因此無監(jiān)督的特征學(xué)習(xí)引起了更多的關(guān)注。

無監(jiān)督的特征學(xué)習(xí)方法可以大致分為3類：過濾式模型、包裹式模型和嵌入式模型。過濾式模型通過如數(shù)據(jù)統(tǒng)計(jì)屬性等評(píng)價(jià)標(biāo)準(zhǔn)選擇相應(yīng)特征子集[7]。包裹式模型可以進(jìn)行大規(guī)模的密集計(jì)算[9-10]。嵌入式模型在學(xué)習(xí)模型中加入選擇過程，發(fā)現(xiàn)顯著特征的同時(shí)學(xué)習(xí)最優(yōu)分類器[11]。早期的無監(jiān)督特征選擇主要使用一些評(píng)價(jià)指標(biāo)來搜索每個(gè)特征或特征子集的重要性。這些評(píng)價(jià)指標(biāo)包括聚類性能、冗余度、樣本相似性、流形結(jié)構(gòu)以及拉普拉斯分?jǐn)?shù)[5]、方差[3]和跟蹤比[12]等典型指標(biāo)。而基于搜索的算法需要高昂的計(jì)算代價(jià)，為了減少計(jì)算，文獻(xiàn)[13]提出了一種非搜索式特征聚類方法，依據(jù)特征相似度挖掘顯著性特征。為更好地保存樣本的相似性，一系列基于譜聚類的特征選擇方法被提出[14-16]。近年來，朱等人提出一種基于正則化自表示方法的無監(jiān)督特征選擇，將任意特征表示為其他特征的線性組合，通過最小化自表示誤差，可以學(xué)習(xí)一個(gè)特征權(quán)重矩陣，進(jìn)而選擇特定特征子集[17]。

稀疏正則化通常被用于維數(shù)約簡(jiǎn)和特征選擇，并且取得了良好效果。通過引入l1范數(shù)正則項(xiàng)，l1-SVM被用于特征選擇[18]。通過對(duì)特征選擇建立損失最小化問題模型，具有組稀疏性質(zhì)的l2，1范數(shù)也被用來消除特征中的冗余[4，19-20]。朱等人將l2，1范數(shù)用于約束特征權(quán)值矩陣和自表示誤差，獲得了較好的效果[17]。

在此使用l2，p范數(shù)約束特征權(quán)值矩陣，其中0≤p＜1。類似于向量l1范數(shù)與lp范數(shù)的情況，當(dāng)0＜p＜1時(shí)，表示系數(shù)矩陣的非零行將會(huì)比標(biāo)準(zhǔn)的l2，1范數(shù)約束時(shí)更少。為了進(jìn)一步增強(qiáng)系數(shù)矩陣的稀疏性，將考慮p=0的極限情況，其正則項(xiàng)為l2，0范數(shù)約束。同時(shí)，為了消除離群點(diǎn)帶來的負(fù)面影響，使用標(biāo)準(zhǔn)的l2，1范數(shù)來約束損失項(xiàng)。使用一種改進(jìn)的IRLS（迭代重加最小二乘法）算法求解0＜p＜1時(shí)的模型并保證其收斂[17]。而p=0時(shí)模型是非凸的且不可微的，無法使用IRLS方法求解，因此，利用ALM（增廣拉格朗日法）求解該問題[21]，確保迭代算法為局部收斂。通過真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)，表明所提模型比標(biāo)準(zhǔn)的l2，1范數(shù)正則化和其他流行的特征選擇方法在分類和聚類性能具有更突出的優(yōu)勢(shì)。

1 凹型正則化自表示特征模型

1.1 問題描述

現(xiàn)實(shí)數(shù)據(jù)集通常具有許多冗余離群點(diǎn)。一個(gè)高效無監(jiān)督特征選擇算法，需要從給定的無標(biāo)簽數(shù)據(jù)集中，選擇一個(gè)可以有效描述數(shù)據(jù)集屬性和結(jié)構(gòu)的特征子集。

給定數(shù)據(jù)集X∈Rm×n，其中m是樣本數(shù)，n是特征維數(shù)。使用fi∈Rm來表示X的第i個(gè)特征向量，令X=[f1，…，fi，…，fn]。常見方法都使用樣本相似性或流形結(jié)構(gòu)構(gòu)造系數(shù)矩陣，因此，特征選擇可表示為多輸出回歸問題：

式中：D={1，2，…，n}表示維度；K是選定的子集；XK是X對(duì)應(yīng)的K列；W是對(duì)應(yīng)的特征權(quán)值矩陣；l（·）是損失項(xiàng)，用于評(píng)估特征選擇的性能。

式中：l（Y-XW）是損失項(xiàng)；新引入的R（W）是正則項(xiàng)；λ是正則項(xiàng)參數(shù)，幫助動(dòng)態(tài)選擇最優(yōu)特征子集，并選擇和計(jì)算最優(yōu)的權(quán)值矩陣。

1.2 損失項(xiàng)和正則項(xiàng)

受樣本自表示模型的啟發(fā)[17]，利用特征自表示的性質(zhì)實(shí)現(xiàn)特征選擇。類似RSR[17]，使用原數(shù)據(jù)矩陣X作為字典矩陣，即Y=X，每個(gè)特征都可以用所有其他特征線性表示，假設(shè)fi是X中第i個(gè)特征，則其可以表示為：式中：Wji是權(quán)值矩陣W中第j行第i列元素；bi∈Rm是偏移量。

集聚所有特征向量可得：

式中： B=[b1， b2， …， bn]∈Rm×n。

在此模型中，使用特征學(xué)習(xí)權(quán)值矩陣W衡量在偏移量很小時(shí)不同特征的重要性。令W=[，…，，其中wi是矩陣W的第i行。||wi||2可以代表自表示模型中第i個(gè)特征的重要程度。如果第i個(gè)特征對(duì)特征表示模型最小化沒有貢獻(xiàn)度，則||wi||2=0；相反，若第i個(gè)特征的貢獻(xiàn)度很大，則||wi||2的值也會(huì)變大。顯然，行稀疏是權(quán)值矩陣W這種性質(zhì)的理想狀態(tài)。

根據(jù)稀疏表示模型，l0范數(shù)可以保證稀疏性，但其是非凸的。l1范數(shù)在一定條件下等價(jià)于l0范數(shù)[22]，故通常作為l0范數(shù)的凸型替代。文獻(xiàn)[23]指出0＜p＜1的lp范數(shù)比l1范數(shù)更接近l0范數(shù)且更具稀疏性。為保證權(quán)值矩陣W在行上更具有稀疏性，選擇l2，p范數(shù)作為正則項(xiàng)約束，并采用p=0與0＜p＜1 兩種形式。

對(duì)于0＜p＜1的情況，可定義一個(gè)正則項(xiàng)形式R（·）=||·。 對(duì)于 p=0 的情況，正則化形式為

pR0||·||2，0。 為減緩對(duì)離群點(diǎn)的敏感度， 使用 l2，1范數(shù)作為約束誤差，定義為l（·）=|·|||2，1，通過上述形式定義，可以得到2個(gè)目標(biāo)函數(shù)：

式中：λ是非負(fù)平衡系數(shù)。

l2，p范數(shù)的形式定義為：

l2，0范數(shù)可以表示為：

式中：δ（x）是邏輯判斷函數(shù)，表示式見式（9）。

2 優(yōu)化和算法

本部分描述了模型的優(yōu)化過程。當(dāng)p＜1時(shí)，目標(biāo)函數(shù)非凸，必須使用迭代方法進(jìn)行優(yōu)化。使用IRLS方法可以有效優(yōu)化0＜p＜1情況下的目標(biāo)函數(shù)，而且可以確定局部最優(yōu)。對(duì)于p=0的情況則利用增廣拉格朗日法求解，同時(shí)得以保證局部收斂。

2.1 迭代重加權(quán)最小二乘法求解l2，p模型

如上所述，式（5）是凹約束問題，可使用迭代重加權(quán)最小二乘法求解。根據(jù)IRLS算法，給定一個(gè)當(dāng)前權(quán)值矩陣Wt，則對(duì)角權(quán)值矩陣和可以被定義為：

式（12）是關(guān)于W的二次函數(shù)，將其導(dǎo)數(shù)置0很容易得到閉式解：

因此Wt+1的解可以表示為：

為提升最優(yōu)解的穩(wěn)定性，定義了一個(gè)足夠小的非負(fù)值ε：

獲得W的最優(yōu)解之后，根據(jù)w值的大小順序選擇包含前k個(gè)特征的非零子集，該方法同樣可用于式（6）。對(duì)于式（5）的解法見算法1。

算法1：IRLS求解0＜p＜1時(shí)的凹型RSR模型。

輸入： 數(shù)據(jù)矩陣X∈Rm×n， λ＞0， 最大迭代次數(shù)TN。

輸出：特征權(quán)值矩陣W。

（1）初始化W；

（2）迭代次數(shù)T=1；

（5）利用式（14）求解Wt+1；

（6）檢查T≥TN是否滿足，若是，則終止算法；否則，令T=T+1，算法循環(huán)至第3步繼續(xù)進(jìn)行。

2.2 增廣拉格朗日方法求解l2，0模型

如前文所述，當(dāng)p=0時(shí)，l2，0范數(shù)可以更好地提升目標(biāo)變量的稀疏性，而l2，0范數(shù)是一種不可微且極度非凸的優(yōu)化問題，不能直接使用IRLS。本節(jié)使用增廣拉格朗日方法求解此問題。

根據(jù)拉格朗日法則，引入輔助變量V和E，式（6）可以被重寫為：

式中：μ是1個(gè)正標(biāo)量，可以提升迭代速度；Π1，Π2是2個(gè)拉格朗日算子，可以隨著樣本集的變化而變化。式（14）包括3個(gè)變量E，W和V，固定其他2個(gè)變量交替更新1個(gè)變量，最終可以獲得模型的最優(yōu)解。

為求解E，式（14）可以改寫為：

令Y=XW-X+1/μΠ1， 將式（17）寫為行向量形式：

根據(jù)文獻(xiàn)[25]，該子問題具有閉式解：

為求解W，式（16）可以改寫為如下子問題：

式（20）是一個(gè)二次規(guī)劃問題，具有最優(yōu)閉式解：

類似對(duì)E的求解，令Z=W+1/μΠ2，將式（22）改寫成行向量形式：

為求解V，式（16）可以改寫為如下子問題：

根據(jù)文獻(xiàn)[26]，式（23）具有如下閉式解：

式（24）只是高維向量空間中一種硬閾值算子，類似于vi是標(biāo)量的情況。值得一提的是，如果將式（24）作為一個(gè)具體的正則化函數(shù)：

則其具有如下性質(zhì)：

該函數(shù)是文獻(xiàn)[27]中一維向量在歐幾里得距離上的自然擴(kuò)展。當(dāng)趨于無窮時(shí)，式（26）會(huì)收斂于式（9），因此，可以使用正則化函數(shù)式（26）作為l2，0范數(shù)約束。對(duì)于式（16）的最后2項(xiàng)除卻Π2可以近似為φ（wi）。實(shí)際上，Π2的目的是為了加快收斂速度，因此可以使用 φ（wi）作為式（16）最后兩項(xiàng)的正則項(xiàng)。 如此意味著，式（16）是l2，1范數(shù)損失項(xiàng)與近似l2，0范數(shù)正則項(xiàng)的聯(lián)合優(yōu)化，且在迭代過程中稀疏約束會(huì)持續(xù)增強(qiáng)，近似形式的l2，0范數(shù)會(huì)逐步接近其實(shí)質(zhì)形式。

綜上所述，對(duì)于式（6）的解法如下算法2所描述。

算法2：ALM求解p=0時(shí)的凹型RSR模型。

輸入： 數(shù)據(jù)矩陣X∈Rm×n， λ＞0， μτ， 最大迭代次數(shù)TN。

輸出：特征權(quán)值矩陣W。

（1）初始化W， Π1， Π2， μ；

（2）迭代次數(shù)T=1；

（3）利用式（22）求解Vt+1；

（4）利用式（17）求解Et+1；

（5）利用式（19）求解Wt+1；

（8）μ=μ×μτ；

（9）檢查T≥TN是否滿足，若是，則終止算法；否則，令T=T+1，算法循環(huán)至第3步繼續(xù)進(jìn)行。

3 試驗(yàn)

為驗(yàn)證以上所提出的凹型約束特征選擇方法，將算法應(yīng)用在7個(gè)公開數(shù)據(jù)庫(kù)：orlraws，pixraw，warPIE，TOX， Prostate，Carcinoma[28]和 LUNG[29]。所有數(shù)據(jù)集的特征數(shù)在2 400～11 340之間，且歸一化為N（0，1）分布。表1給出了7個(gè)數(shù)據(jù)集的詳細(xì)信息。將凹型自表示特征選擇的2種形式與標(biāo)準(zhǔn)l2，1RSR算法以及5種典型的無監(jiān)督特征選擇方法：Laplacian score[5]，UDFS[7]，SPEC[14]和FSFS[13]做對(duì)比。同時(shí)，為了檢驗(yàn)該算法性能的廣泛意義，所有方法在分類與聚類2種任務(wù)下進(jìn)行對(duì)比。

表1 測(cè)試數(shù)據(jù)集匯總描述

試驗(yàn)將檢驗(yàn)此算法當(dāng)p=[0，0.4，0.6，0.8]時(shí)的算法性能。對(duì)于Laplacian score和UDFS，設(shè)置所有數(shù)據(jù)集的鄰域數(shù)k=5。UDFS和l2，1RSR的正則項(xiàng)參數(shù)通過搜索優(yōu)選。Laplacian score和SPFS中高斯核函數(shù)寬度參數(shù)也經(jīng)過遍歷搜索。為了公平對(duì)比，所有正則項(xiàng)參數(shù)和寬度參數(shù)都在{0.001,0.005，0.01，0.05，0.1，0.5，1，5，10，100}中選取使算法性能最優(yōu)的參數(shù)?？紤]到所提算法的稀疏性，當(dāng)特征選擇數(shù)較少時(shí)，算法的優(yōu)勢(shì)才能被體現(xiàn)。因此，特征選擇的數(shù)目在{10，15，20，25，30}中進(jìn)行優(yōu)選。為量化算法性能，使用2種性能指標(biāo)：ACC（分類精度）和NMI（聚類歸一化互信息）。

表2 分性精度性能對(duì)比

表3 聚類NMI性能對(duì)比

3.1 分類性能

所有算法的分類精度（%）如表2所示，所有數(shù)值都是通過10次運(yùn)行的平均值，其中在同條件下最高值由黑斜表示，次高值由黑體表示，第3值則采用下劃線表示。從表2可以看出，此提算法相比l2，1RSR和其他對(duì)比算法，在多數(shù)情況下具有突出的性能優(yōu)勢(shì)。在部分?jǐn)?shù)據(jù)集中，如TOX和Carcinoma，雖然所提算法沒有取得最優(yōu)的精度值，但依然占據(jù)著同類算法中的次高值以及第3值。同時(shí)，在一些數(shù)據(jù)集上，稀疏設(shè)置具有優(yōu)異的表現(xiàn)，尤其是p趨于0值時(shí)，其在LUNG和Prostate等數(shù)據(jù)集上具有絕對(duì)的優(yōu)勢(shì)。

3.2 聚類性能

選中特征子集后，試驗(yàn)使用kmeans方法完成最終聚類。表3給出了所有算法在不同數(shù)據(jù)集上10次運(yùn)行的NMI平均值。從中可見，此算法在所有數(shù)據(jù)集中的聚類結(jié)果都優(yōu)于其他對(duì)比算法，其中pixraw數(shù)據(jù)集中占據(jù)了前3個(gè)最優(yōu)值，進(jìn)一步驗(yàn)證了凹型約束的優(yōu)越性。

4 結(jié)語(yǔ)

提出了一種面向高維數(shù)據(jù)的凹型自表示特征選擇方法。基于自表示性質(zhì)與lp范數(shù)約束增強(qiáng)稀疏性，所提無監(jiān)督特征選擇模型采用l2，p范數(shù)約束。當(dāng)0＜p＜1時(shí)，函數(shù)變成非凸優(yōu)化問題，采用IRLS算法進(jìn)行有效求解。當(dāng)p=0時(shí)，則使用增廣拉格朗方法求解l2，0范數(shù)約束問題。在7個(gè)數(shù)據(jù)集與標(biāo)準(zhǔn)l2，1RSR和現(xiàn)存流行算法的對(duì)比試驗(yàn)表明，所提算法具有明顯的性能優(yōu)勢(shì)。未來將研究其他形式的凹型約束，并將此處所提模型擴(kuò)展到有監(jiān)督特征選擇。