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

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

0 引言

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

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

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

稀疏正則化通常被用于維數(shù)約簡和特征選擇，并且取得了良好效果。通過引入l1范數(shù)正則項，l1-SVM被用于特征選擇[18]。通過對特征選擇建立損失最小化問題模型，具有組稀疏性質(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ù)的情況，當0＜p＜1時，表示系數(shù)矩陣的非零行將會比標準的l2，1范數(shù)約束時更少。為了進一步增強系數(shù)矩陣的稀疏性，將考慮p=0的極限情況，其正則項為l2，0范數(shù)約束。同時，為了消除離群點帶來的負面影響，使用標準的l2，1范數(shù)來約束損失項。使用一種改進的IRLS（迭代重加最小二乘法）算法求解0＜p＜1時的模型并保證其收斂[17]。而p=0時模型是非凸的且不可微的，無法使用IRLS方法求解，因此，利用ALM（增廣拉格朗日法）求解該問題[21]，確保迭代算法為局部收斂。通過真實數(shù)據(jù)集的實驗，表明所提模型比標準的l2，1范數(shù)正則化和其他流行的特征選擇方法在分類和聚類性能具有更突出的優(yōu)勢。

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

1.1 問題描述

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

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

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

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

1.2 損失項和正則項

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

集聚所有特征向量可得：

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

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

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

對于0＜p＜1的情況，可定義一個正則項形式R（·）=||·。 對于 p=0 的情況，正則化形式為

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

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

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

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

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

2 優(yōu)化和算法

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

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

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

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

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

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

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

算法1：IRLS求解0＜p＜1時的凹型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ù)進行。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法2：ALM求解p=0時的凹型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ù)進行。

3 試驗

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

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

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

表2 分性精度性能對比

表3 聚類NMI性能對比

3.1 分類性能

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

3.2 聚類性能

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

4 結(jié)語

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