基于Schatten-p范數(shù)和特征自表示的無監(jiān)督特征選擇

彭 明，張海澎

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

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

1 引言

隨著科學(xué)技術(shù)的快速發(fā)展，各應(yīng)用領(lǐng)域收集的數(shù)據(jù)量越來越大，而這些數(shù)據(jù)往往具有高維特征，并且含有大量噪聲和冗余信息。直接對(duì)這些高維數(shù)據(jù)進(jìn)行建模學(xué)習(xí)，通常會(huì)有預(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ù)的重要特征，去除大量不重要的噪聲和冗余特征進(jìn)而避免“維數(shù)災(zāi)難”問題。同時(shí)，在現(xiàn)實(shí)世界中存在大量的無標(biāo)簽高維數(shù)據(jù)，對(duì)這些數(shù)據(jù)進(jìn)行標(biāo)記是昂貴和耗時(shí)的，甚至是不可行的。因此，對(duì)高維數(shù)據(jù)進(jìn)行無監(jiān)督特征選擇算法[1-2]的研究是有很大現(xiàn)實(shí)意義的。

近年來，國內(nèi)外許多專家學(xué)者基于高維數(shù)據(jù)中固有的流形結(jié)構(gòu)和低秩結(jié)構(gòu)對(duì)無監(jiān)督特征選擇算法進(jìn)行了大量的研究。基于拉普拉斯打分特征選擇LS[3]將數(shù)據(jù)的流形結(jié)構(gòu)運(yùn)用到無監(jiān)督特征選擇模型中，即利用高維流形上數(shù)據(jù)點(diǎn)間的近鄰結(jié)構(gòu)在低維嵌入中得以保持的特性，構(gòu)建的近鄰圖，獨(dú)立計(jì)算每個(gè)特征的得分進(jìn)而選擇特征；為了得到判別性的特征子集，文獻(xiàn)[4]將譜聚類方法和流形結(jié)構(gòu)結(jié)合在一起，提出了基于非負(fù)譜分析的無監(jiān)督特征選擇算法NDFS；針對(duì)基因表達(dá)數(shù)據(jù)，文獻(xiàn)[5]提出了基于譜聚類的無監(jiān)督特征選擇算法FSSC，對(duì)所有特征進(jìn)行譜聚類，將相似性較高的特征聚成一類，并定義特征的區(qū)分度與特征獨(dú)立性來度量特征重要性，從各特征簇選取代表性特征，構(gòu)造特征子集；基于魯棒譜學(xué)習(xí)的無監(jiān)督特征選擇算法RSFS[6]提高了圖拉普拉斯嵌入和稀疏譜回歸的魯棒性，進(jìn)而降低了原始數(shù)據(jù)中因噪聲和冗余特征對(duì)構(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)保持，進(jìn)而選擇重要的特征；文獻(xiàn)[10]在保持流形結(jié)構(gòu)下，運(yùn)用拉普拉斯矩陣的特征向量和特征值得到具有代表性的特征子集；文獻(xiàn)[11]運(yùn)用自表示方法[12]形式化特征選擇算法，結(jié)合低秩近似、結(jié)構(gòu)學(xué)習(xí)和稀疏正則，提出了基于低秩近似和結(jié)構(gòu)學(xué)習(xí)的無監(jiān)督特征選擇算法LRSL，并根據(jù)Ky Fan定理對(duì)低秩進(jìn)行凸優(yōu)化求解；基于圖學(xué)習(xí)和低秩約束的無監(jiān)督特征選擇算法[13]運(yùn)用對(duì)系數(shù)矩陣的低秩約束控制流形結(jié)構(gòu)進(jìn)而減少冗余特征對(duì)性能的影響；文獻(xiàn)[14]整合了特征選擇和特征提取兩種降維方式，提出了基于低秩嵌入和對(duì)偶拉普拉斯正則的無監(jiān)督線性特征選擇映射算法FSP，運(yùn)用系數(shù)矩陣的低秩約束去重構(gòu)樣本點(diǎn)；已有算法大都運(yùn)用的是流形結(jié)構(gòu)中的單邊信息，文獻(xiàn)[15]提出了基于低秩稀疏非負(fù)矩陣分解的對(duì)偶無監(jiān)督特征選擇算法NMF-LRSR，運(yùn)用低秩稀疏表示去重構(gòu)拉普拉斯圖，在特征選擇過程中考慮數(shù)據(jù)的局部和全局結(jié)構(gòu)，進(jìn)而使選擇的特征子集更為精確。

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

2 問題形式化

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

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

對(duì)于所有的特征向量，則有：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了便于對(duì)公式（16）的求解，引入文獻(xiàn)[20]中的一個(gè)定理。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入：數(shù)據(jù)集X∈?n×d（n個(gè)樣本，d個(gè)特征），選擇的特征個(gè)數(shù)m和兩個(gè)參數(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個(gè)特征作為特征子集。

4 實(shí)驗(yàn)與結(jié)果分析

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集

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

表1 實(shí)驗(yàn)數(shù)據(jù)集描述

4.2 度量準(zhǔn)則

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

聚類精度（ACC）：

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

4.3 實(shí)驗(yàn)參數(shù)設(shè)計(jì)

為了驗(yàn)證所提算法基于Schatten-p范數(shù)和特征自表示的無監(jiān)督特征選擇SPSR的性能，實(shí)驗(yàn)比較了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ù)集上的實(shí)驗(yàn)結(jié)果。

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

4.4 結(jié)果分析

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

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

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

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

參數(shù)p和λ是所提算法SPSR 中最重要的參數(shù)，本節(jié)分析它們對(duì)所提算法的影響。為了較好地展示SPSR 在不同參數(shù)下的聚類性能，只從一定范圍內(nèi)記錄采樣點(diǎn)的變化搜索區(qū)域。使用網(wǎng)格搜索策略，參數(shù)p的搜索區(qū)域?yàn)閧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個(gè)數(shù)據(jù)集上在不同的p值處聚類精度是有所波動(dòng)的。但SPSR在6個(gè)數(shù)據(jù)集上均在p=0.1 處得到較好的聚類精度，驗(yàn)證了參數(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處取得較高的聚類精度。也就是說，對(duì)于不同的數(shù)據(jù)集，SPSR 的目標(biāo)函數(shù)中損失項(xiàng)和低秩正則項(xiàng)的平衡系數(shù)λ是不相同的。對(duì)于如何自適應(yīng)獲得不同數(shù)據(jù)集對(duì)應(yīng)的平衡系數(shù)λ依舊是一個(gè)開放式的問題。

5 結(jié)束語

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

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