基于Schatten-p范數和特征自表示的無監督特征選擇

彭 明，張海澎

1.龍巖學院 數學與信息工程學院，福建 龍巖 364012

2.國網山西省電力公司 沁源縣供電公司，山西 長治 046500

1 引言

隨著科學技術的快速發展，各應用領域收集的數據量越來越大，而這些數據往往具有高維特征，并且含有大量噪聲和冗余信息。直接對這些高維數據進行建模學習，通常會有預測效果低、數據陷入“維數災難”等問題。為了解決這些問題，現有的模型算法通過利用高維數據中固有的一些關聯結構，例如數據的流形結構和低秩結構等，來提高模型的預測效果；通過特征選擇方法有效地選出高維數據的重要特征，去除大量不重要的噪聲和冗余特征進而避免“維數災難”問題。同時，在現實世界中存在大量的無標簽高維數據，對這些數據進行標記是昂貴和耗時的，甚至是不可行的。因此，對高維數據進行無監督特征選擇算法[1-2]的研究是有很大現實意義的。

近年來，國內外許多專家學者基于高維數據中固有的流形結構和低秩結構對無監督特征選擇算法進行了大量的研究?；诶绽勾蚍痔卣鬟x擇LS[3]將數據的流形結構運用到無監督特征選擇模型中，即利用高維流形上數據點間的近鄰結構在低維嵌入中得以保持的特性，構建的近鄰圖，獨立計算每個特征的得分進而選擇特征；為了得到判別性的特征子集，文獻[4]將譜聚類方法和流形結構結合在一起，提出了基于非負譜分析的無監督特征選擇算法NDFS；針對基因表達數據，文獻[5]提出了基于譜聚類的無監督特征選擇算法FSSC，對所有特征進行譜聚類，將相似性較高的特征聚成一類，并定義特征的區分度與特征獨立性來度量特征重要性，從各特征簇選取代表性特征，構造特征子集；基于魯棒譜學習的無監督特征選擇算法RSFS[6]提高了圖拉普拉斯嵌入和稀疏譜回歸的魯棒性，進而降低了原始數據中因噪聲和冗余特征對構建的圖拉普拉斯的影響；根據不同的稀疏正則化方法，基于最大熵和?2,0范數約束的無監督特征選擇算法ENUF[7]使用了具有唯一確定含義的?2,0范數等式約束來確定選擇特征的數量，并結合譜分析探索數據的局部幾何結構和基于最大熵原理自適應的構造相似矩陣；在保持流形結構下，嵌入式的無監督特征選擇算法EUFS[8]通過稀疏學習將特征選擇直接嵌入到聚類算法中，不需要偽標簽的轉換；基于重構的無監督特征選擇算法REFS[9]是根據數據重構誤差準則，將特征相關性定義為特征通過重構函數逼近原始數據，并結合重構后的流形結構保持，進而選擇重要的特征；文獻[10]在保持流形結構下，運用拉普拉斯矩陣的特征向量和特征值得到具有代表性的特征子集；文獻[11]運用自表示方法[12]形式化特征選擇算法，結合低秩近似、結構學習和稀疏正則，提出了基于低秩近似和結構學習的無監督特征選擇算法LRSL，并根據Ky Fan定理對低秩進行凸優化求解；基于圖學習和低秩約束的無監督特征選擇算法[13]運用對系數矩陣的低秩約束控制流形結構進而減少冗余特征對性能的影響；文獻[14]整合了特征選擇和特征提取兩種降維方式，提出了基于低秩嵌入和對偶拉普拉斯正則的無監督線性特征選擇映射算法FSP，運用系數矩陣的低秩約束去重構樣本點；已有算法大都運用的是流形結構中的單邊信息，文獻[15]提出了基于低秩稀疏非負矩陣分解的對偶無監督特征選擇算法NMF-LRSR，運用低秩稀疏表示去重構拉普拉斯圖，在特征選擇過程中考慮數據的局部和全局結構，進而使選擇的特征子集更為精確。

然而，已有的算法大都是基于凸優化的目標函數，本文基于高維數據中固有的低秩結構，提出了一種基于Schatten-p范數和特征自表示的非凸無監督特征選擇算法（SPSR）。首先運用特征自表示重構無監督特征選擇問題中的系數矩陣，其次結合Schatten-p范數正則項逼近秩最小化問題，即低秩結構，然后使用增廣拉格朗日乘子法和交替方向法乘子法框架對目標函數進行優化，同時運用奇異值分解方法對Schatten-p范數近似的秩最小化問題進行優化求解。最后在6 個公開數據集上與RSFS算法、EUFS算法、REFS算法、LRSL算法等經典的無監督特征選擇算法進行實驗比較，證明本文提出的基于Schatten-p范數和特征自表示的無監督特征選擇SPSR算法是有效的。

2 問題形式化

先介紹一下本文中使用的一些符號，其中，大寫粗斜體表示矩陣，小寫粗斜體表示向量。對于任意列向量它的?2范數為對于任意矩陣，它的 Frobenius 范數矩陣的秩和轉置分別用rank(M)和MT表示。對于任意方陣方陣A的跡為，可逆矩陣表示為A-1。In∈?n×n表示單位矩陣。

特征自表示是每個特征可以由其他的特征線性表示[12]，即，對于數據集X的每一個特征fi，有：

對于所有的特征向量，則有：

其中，#-范數 ‖ ? ‖#表示某種殘差度量，比如，Frobenius范數用來處理高斯噪聲[16]，?2,1-范數 ‖ ? ‖2，1用于描述特定的樣本異常點[17]，?1-范數 ‖ ? ‖1用來處理隨機或者稀疏數據[18]。然而，當W是單位陣時，就會得到一個平凡解，即殘差E=0。因此，為了指導特征子集的選擇和避免平凡解，引入一個正則項R(W)，則無監督特征選擇可以被形式化為：

其中，λ是用來權衡擬合精度和正則項的系數，且λ＞0。令W=[w1;w2;…;wd]，wi是系數矩陣W的第i行，wi是d維向量，且 ‖wi‖2可以表示第i個特征的重要度，則 ‖wi‖2的值越大，表示第i個特征越重要。

一方面，特征選擇的目的是尋找一個低維的特征子集盡可能地刻畫原來的特征空間，另一方面，已有研究表明噪聲和冗余特征會導致數據矩陣的秩增大[19]，同時為了避免平凡解，引入低秩正則項來約束系數矩陣W。同時，Frobenius 范數可以利用低秩矩陣來近似單一的數據矩陣。則本文的無監督特征選擇形式化為如下形式：

由于秩函數是非凸且不連續的，公式（5）是一個NP難問題，即無法在多項式時間內求解。為了解決這個問題，文獻[20]中提出利用Schatten-p范數來逼近矩陣的秩。因此，公式（5）轉化為如下問題，即，本文提出的基于Schatten-p范數和特征自表示的無監督特征選擇SPSR算法的目標函數：

當σi=0 時，=0 ，否則=1。根據公式（7），可知也就是說，當p→0，近似等于矩陣W的秩。類似的，當p=1 時，矩陣W的Schatten-1范數為：

Schatten-1 范數又被稱為核范數，記為 ‖W‖*。文獻[21]用核函數作為秩最小化問題的最緊凸松弛，然而，基于核范數的模型會對數據的低秩成分進行過多的收縮。因此，用Schatten-p范數最小化問題逼近秩最小化問題[22-23]。同時，有理論證明[24]Schatten-p范數能夠取得更好的效果。

3 算法模型優化

本章為基于Schatten-p范數和特征自表示的無監督特征選擇SPSR 算法模型進行優化求解。首先，引入輔助變量M，將公式（6）轉換為如下等價優化問題：

該優化問題可以用增廣拉格朗日乘子法（ALM）算法有效地求解。優化問題（9）的增廣拉格朗日函數如下：

其中，Y是拉格朗日乘子，μ＞0 是一個控制懲罰強度的懲罰參數。

本文通過交替方向法乘子法（ADMM）框架將公式（10）分解為若干子問題迭代求解W,M,Y,μ，具體迭代更新規則如下：

（1）固定變量M,Y和μ，更新變量W

關于W的優化問題可以等價轉換為如下形式：

對任意矩陣A∈?n×d，有，同時，對于 任 意 矩 陣A1∈ ?n×d和A2∈ ?d×n，有 t rA1A2=trA2A1。則：

根據公式（12），對W進行求導，可得：

（2）固定變量W,Y和μ，更新變量M

關于M的優化問題，公式（10）可以等價轉換為：

對上面式子做一下簡單變換，得到：

根據矩陣M的Schatten-p范數的p次方則有：

為了便于對公式（16）的求解，引入文獻[20]中的一個定理。

定理1對任意兩個矩陣B,C∈?n×d，令σ(B)和σ(C)表示對角矩陣，其對角元素分別為矩陣B和C相同排序下的有序特征值，則有trBTC≤trσ(B)Tσ(C)。

根據定理1，有：

因此，根據公式（17）和公式（18），最小化公式（16）中的L(M)可以被簡化為如下的最小化問題：

令δi≥0 是Δ的第i個對角元素，ai是的第i個對角元素，也就是說，δi≥0 和ai分別是矩陣M和矩陣A的第i個奇異值，則公式（19）可以等價轉換為如下最小化形式：

用f(δ)表示公式（20）中的目標函數，即：

根據δ≥0 的約束，求得f(δ)的梯度如下：

繼續求f(δ)的二次梯度，得到一個拐點如下：

根據以上公式，最小化問題（20）的最優解可以通過如下公式求得：

其中，?是一次梯度函數f′(δ)=0 的解。

（3）固定變量W和M，更新變量Y和μ

矩陣Y的迭代更新公式為：

其中，懲罰系數μ的迭代更新公式為：

以上是運用增廣拉格朗日乘子法和交替方向法乘子法框架關于SPSR 算法模型的求解過程，具體算法步驟如算法1所示。

算法1基于Schatten-p范數和特征自表示的無監督特征選擇算法（SPSR）。

輸入：數據集X∈?n×d（n個樣本，d個特征），選擇的特征個數m和兩個參數p,λ。

1.初始化μ=0.1,ρ=1.3,μmax=108,Y=0,W=M=Id；

2.repeat

3.通過公式（14）更新W；

4.通過問題（16）的最優解更新M；

5.通過公式（25）更新Y；

6.通過公式（26）更新μ；

7. until 滿足收斂條件

輸出：降序排列 ‖wi‖2，i=1,2,…,d，選出前m個特征作為特征子集。

4 實驗與結果分析

本章通過現實世界中的數據集來驗證所提算法SPSR的有效性。

4.1 實驗數據集

實驗選用了6個現實世界中的數據集進行研究，相關數據集可從feature selection dataset（shttp：//featureselection.asu.edu/datasets.php）中獲取。數據集的詳細信息如表1所示。這些數據集包含了人臉數據集Yale 和PIE10P，基因表達數據集 ly mphoma、GLIOMA 和 T OX-171，數字識別數據集gisette。

表1 實驗數據集描述

4.2 度量準則

為了驗證算法的有效性，文中采用聚類精度（clustering accuracy，ACC）作為判斷標準，來衡量不同算法選擇不同特征子集時的效果，其中，ACC的值越大表示算法效果越好。

聚類精度（ACC）：

其中，n為樣本數，l(xi)和l′(xi)分別為樣本xi自帶的類別標簽和聚類算法得到的類別標簽，δ(x,y)是指示函數，當x=y時，值為1，否則為0。

4.3 實驗參數設計

為了驗證所提算法基于Schatten-p范數和特征自表示的無監督特征選擇SPSR的性能，實驗比較了SPSR算法與基于魯棒譜學習的無監督特征選擇算法RSFS[6]、嵌入式的無監督特征選擇算法EUFS[8]、基于重構的無監督特征選擇算法REFS[9]、基于低秩近似和結構學習的無監督特征選擇算法LRSL[11]，以及選擇所有特征（Baseline）在表1數據集上的實驗結果。

對比算法 L RSL、EUFS 和 R SFS 中關于?2,1范數正則項和局部結構學習正則項的超參數均設置為1，LRSL中關于低秩近似的正則項超參數設置為1E4，同時RSFS中譜學習約束正則項和?1范數正則項的參數均設置為1；對比算法REFS中懲罰沒有被選擇的特征重構錯誤的正則項和控制重構后保持原有特征結構的正則項參數均設置為0.1；4 個對比算法LRSL、REFS、EUFS、RSFS中涉及到的近鄰數均設置為5；所有的實驗將公式（6）中的正則化參數λ設置為，其中d是數據集的特征維數，Schatten-p范數中參數p設置為{0.1，0.2，…，0.9，1}。對表1 中所有的數據集，特征選擇的個數設置為{20，30，…，100}。同時，實驗選用K-means 算法進行聚類，而K-Means算法對初始選取的聚類中心點是敏感的，因此，K-means 算法對選取的特征子集運行30 次實驗記錄平均值。

4.4 結果分析

為了比較分析不同無監督特征選擇算法的性能，表2和圖1給出了不同算法的聚類精度。其中，表2給出了所有對比算法在不同數據集上的最大聚類精度，圖1展示了所有對比算法的聚類精度與選擇的特征個數的關系。從表2 中可以看出，所提算法SPSR 的聚類精度都高于保留所有特征（Baseline）的聚類精度，其中，在數據集 Y ale、lymphoma、GLIOMA 和 T OX-171 上，SPSR 比Baseline 的聚類精度高出5～8 個百分點，而在數據集gisette 和 P IE10P 上，SPSR 均比 B aseline 的聚類精度高出20個百分點。同時，除了lymphoma數據集上的聚類精度僅低于REFS 算法，所提算法SPSR 的聚類精度均優于其他對比算法。由圖1 中算法的聚類精度與選擇特征數量的關系可看出，所提算法SPSR在數據集Yale、gisette 和PIE10P 上的聚類精度均高于其他對比算法。尤其是，相對比于有低秩近似約束的LRSL算法來說，所提算法SPSR 無論選擇特征的個數為{20，30，…，100}，在數據集Yale、lymphoma、gisette 和 P IE10P 上都以絕對的優勢高于LRSL 的聚類精度；在數據集GLIOMA 和TOX-171上，所選擇特征數在60個以內，所提算法SPSR均高于LRSL的聚類精度。說明了相對于LRSL中的低秩約束優化，所提算法SPSR 中的Schatten-p范數更能捕捉到數據集中真實的低秩結構。

綜合表2和圖1的對比信息可知，對比LRSL、REFS、EUFS、RSFS 等經典的無監督特征選擇算法，本文所提基于Schatten-p范數和特征自表示的無監督特征選擇SPSR算法的聚類效果更好。這也驗證了，SPSR能選擇出更有代表性的特征子集，同時也說明Schatten-p范數正則在特征選擇算法中是非常有用的。

表2 在不同的數據集身上不同無監督特征選擇算法的最大聚類精度（ACC±std）%

4.5 參數 p 和λ 的敏感性分析

參數p和λ是所提算法SPSR 中最重要的參數，本節分析它們對所提算法的影響。為了較好地展示SPSR 在不同參數下的聚類性能，只從一定范圍內記錄采樣點的變化搜索區域。使用網格搜索策略，參數p的搜索區域為{0.1，0.2，…，0.9，1}，參數λ的搜索區域，其中d是相應數據集的特征維數。

圖2展示了SPSR關于參數p的聚類精度，其中參數λ設置為d-1。從圖2 中，可以看出除了數據集gisette，SPSR在其他5個數據集上在不同的p值處聚類精度是有所波動的。但SPSR在6個數據集上均在p=0.1 處得到較好的聚類精度，驗證了參數p越低越逼近原始數據集的秩。

圖3 所提算法SPSR關于參數λ 的聚類精度(p=0.1)

圖3 展示了SPSR 關于參數λ的聚類精度，其中參數p設置為0.1。從圖3中，可以看出數據集Yale和TOX-171在λ=d-1處取得較高的聚類精度，gisette、GLIOMA和PIE10P 在λ=d0處取得較高的聚類精度，lymphoma在λ=d-1/2處取得較高的聚類精度。也就是說，對于不同的數據集，SPSR 的目標函數中損失項和低秩正則項的平衡系數λ是不相同的。對于如何自適應獲得不同數據集對應的平衡系數λ依舊是一個開放式的問題。

5 結束語

本文提出了一種Schatten-p范數和特征自表示的無監督特征選擇SPSR 算法，通過特征自表示重構無監督特征選擇中的系數矩陣，并運用Schatten-p范數正則項挖掘重構系數矩陣中真實的低秩結構，進而利用增廣拉格朗日乘子法和交替方向法乘子法框架求解得到有效的特征子集。實驗證明本文提出的SPSR算法是有效可行的。

所提算法SPSR為特征選擇問題的研究提供了一個有趣的低秩近似方法，但在未來的研究中仍有一些問題需要解決，例如：SPSR算法能否整合數據固有的流形結構為統一的框架、能否根據數據集本身自適應地選擇特征個數、如何有效地處理類別不平衡數據集，這些問題都將是下一步所關注和解決的問題。