面向高維數據的凹型自表示特征選擇方法

朱國榮，馮 昊，葉玲節

（國網浙江省電力有限公司經濟技術研究院，杭州 310008）

0 引言

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

一般來說，特征選擇方法根據有無標簽可以分為2類：有監督特征選擇和無監督特征選擇。隨著網絡和社交媒體的廣泛使用，產生了大量無標記數據，因此無監督的特征學習引起了更多的關注。

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

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

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

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

1.1 問題描述

現實數據集通常具有許多冗余離群點。一個高效無監督特征選擇算法，需要從給定的無標簽數據集中，選擇一個可以有效描述數據集屬性和結構的特征子集。

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

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

式中：l（Y-XW）是損失項；新引入的R（W）是正則項；λ是正則項參數，幫助動態選擇最優特征子集，并選擇和計算最優的權值矩陣。

1.2 損失項和正則項

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

集聚所有特征向量可得：

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

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

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

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

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

式中：λ是非負平衡系數。

l2，p范數的形式定義為：

l2，0范數可以表示為：

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

2 優化和算法

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

2.1 迭代重加權最小二乘法求解l2，p模型

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

式（12）是關于W的二次函數，將其導數置0很容易得到閉式解：

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

為提升最優解的穩定性，定義了一個足夠小的非負值ε：

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

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

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

輸出：特征權值矩陣W。

（1）初始化W；

（2）迭代次數T=1；

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

（6）檢查T≥TN是否滿足，若是，則終止算法；否則，令T=T+1，算法循環至第3步繼續進行。

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

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

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

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

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

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

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

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

式（20）是一個二次規劃問題，具有最優閉式解：

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

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

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

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

則其具有如下性質：

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

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

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

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

輸出：特征權值矩陣W。

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

（2）迭代次數T=1；

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

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

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

（8）μ=μ×μτ；

（9）檢查T≥TN是否滿足，若是，則終止算法；否則，令T=T+1，算法循環至第3步繼續進行。

3 試驗

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

表1 測試數據集匯總描述

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

表2 分性精度性能對比

表3 聚類NMI性能對比

3.1 分類性能

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

3.2 聚類性能

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

4 結語

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