彭 明，張海澎

1.龍巖學(xué)院 數(shù)學(xué)與信息工程學(xué)院，福建 龍巖 364012

2.國網(wǎng)山西省電力公司 沁源縣供電公司，山西 長治 046500

1 引言

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

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

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

2 問題形式化

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

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

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

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

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

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

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

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

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

3 算法模型優(yōu)化

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

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

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

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

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

關(guān)于W的優(yōu)化問題可以等價轉(zhuǎn)換為如下形式：

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

根據(jù)公式（12），對W進行求導(dǎo)，可得：

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

關(guān)于M的優(yōu)化問題，公式（10）可以等價轉(zhuǎn)換為：

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

根據(jù)矩陣M的Schatten-p范數(shù)的p次方則有：

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

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

根據(jù)定理1，有：

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

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

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

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

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

根據(jù)以上公式，最小化問題（20）的最優(yōu)解可以通過如下公式求得：

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

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

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

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

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

算法1基于Schatten-p范數(shù)和特征自表示的無監(jiān)督特征選擇算法（SPSR）。

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

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

2.repeat

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

4.通過問題（16）的最優(yōu)解更新M；

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

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

7. until 滿足收斂條件

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

4 實驗與結(jié)果分析

本章通過現(xiàn)實世界中的數(shù)據(jù)集來驗證所提算法SPSR的有效性。

4.1 實驗數(shù)據(jù)集

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

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

4.2 度量準(zhǔn)則

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

聚類精度（ACC）：

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

4.3 實驗參數(shù)設(shè)計

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

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

4.4 結(jié)果分析

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

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

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

4.5 參數(shù) p 和λ 的敏感性分析

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

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

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

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

5 結(jié)束語

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

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