基于自適應(yīng)鄰域和自表示正則的無監(jiān)督特征選擇算法

彭 明,張繼炎,王慧玲,黃宏昆,劉艷芳

(1.龍巖學(xué)院 數(shù)學(xué)與信息工程學(xué)院,福建 龍巖 364012;2.伊犁師范大學(xué) 電子與信息工程分院,新疆 伊寧 835000)

隨著技術(shù)的發(fā)展,大量高維數(shù)據(jù)已成為許多應(yīng)用領(lǐng)域的問題,例如計(jì)算機(jī)視覺[1,2],數(shù)據(jù)挖掘[3-5]和模式識別[6]。高維數(shù)據(jù)不僅增加了運(yùn)算的時間復(fù)雜度和空間復(fù)雜度,也會導(dǎo)致學(xué)習(xí)模型的過擬合現(xiàn)象。同時,高維數(shù)據(jù)通常包含很多與學(xué)習(xí)任務(wù)無關(guān)的噪聲和冗余信息。特征選擇是從原始數(shù)據(jù)中選擇最具代表性和區(qū)分性的特征子集,是處理高維數(shù)據(jù)的最重要方法之一。

根據(jù)數(shù)據(jù)中是否有標(biāo)簽信息,特征選擇分為監(jiān)督特征選擇、半監(jiān)督特征選擇和無監(jiān)督特征選擇。在許多場合下獲取標(biāo)簽很費(fèi)力,因此在實(shí)際應(yīng)用中,無監(jiān)督特征選擇更為實(shí)用,它通過聚類[7,8]將無標(biāo)簽的數(shù)據(jù)根據(jù)某種評估標(biāo)準(zhǔn)劃分成有意義或有用的簇,但不可避免會遇到很多挑戰(zhàn)。在過去的幾十年中,國內(nèi)外許多研究人員在無監(jiān)督特征選擇方面做出了巨大的努力。流形學(xué)習(xí)[9]驗(yàn)證了高維空間的數(shù)據(jù)可以在低維空間表示,且被成功應(yīng)用于無監(jiān)督特征選擇算法中,構(gòu)造出了一系列性能良好的基于圖正則的無監(jiān)督特征選擇算法。主要算法有:基于拉普拉斯打分的特征選擇(Laplacian score,LS)[10]根據(jù)同類數(shù)據(jù)較緊湊的特性,利用K近鄰得到數(shù)據(jù)的局部幾何結(jié)構(gòu)圖,然后計(jì)算每個特征的得分選擇特征;基于非負(fù)譜分析的無監(jiān)督特征選擇算法[11]通過K近鄰的相似矩陣得到譜聚類以學(xué)習(xí)數(shù)據(jù)集的偽標(biāo)簽,進(jìn)而和2,1正則結(jié)合起來,獲得了具有判別性的特征子集;魯棒的無監(jiān)督特征選擇算法[12]利用了魯棒非負(fù)矩陣分解、局部學(xué)習(xí)和魯棒特征學(xué)習(xí)的優(yōu)勢,并用2,1正則來約束標(biāo)簽和特征之間的關(guān)系,刪除冗余和噪聲特征;嵌入無監(jiān)督特征選擇(Embedded unsupervised feature setection,EUFS)[13]算法通過稀疏學(xué)習(xí)將特征選擇直接嵌入到聚類算法中,而無需進(jìn)行變換,并用交替方向乘子法(Alternating direction method of multipliers,ADMM)來優(yōu)化目標(biāo)函數(shù);隨著無監(jiān)督特征選擇數(shù)據(jù)重構(gòu)誤差[14]的出現(xiàn),大多數(shù)相關(guān)算法往往假設(shè)線性重構(gòu),但重構(gòu)函數(shù)依賴于數(shù)據(jù),而高維數(shù)據(jù)不總是線性的,因此,基于重構(gòu)的無監(jiān)督特征選擇(Reconstruction-based unsupervised feature selection,REFS)[15]算法研究了如何從數(shù)據(jù)中自動學(xué)習(xí)用于無監(jiān)督特征選擇的重構(gòu)函數(shù),并將重構(gòu)函數(shù)的學(xué)習(xí)嵌入到特征選擇的過程中;大多數(shù)的無監(jiān)督特征選擇算法首先根據(jù)計(jì)算出的特征降序選擇最前面的特征子集,然后執(zhí)行K-means聚類,而這樣得到的是一組次優(yōu)特征,因此依賴指導(dǎo)的無監(jiān)督特征選擇算法[16]以聯(lián)合的方式選擇特征和劃分?jǐn)?shù)據(jù)集,同時增強(qiáng)了原始數(shù)據(jù)集、聚類標(biāo)簽和所選特征之間的關(guān)系,并提出了基于2,0等式約束的無投影特征選擇模型;基于鄰域保持學(xué)習(xí)的無監(jiān)督特征選擇算法[17]利用K近鄰重構(gòu)權(quán)重系數(shù),引入中間矩陣構(gòu)造低維空間,并在低維空間內(nèi)運(yùn)用拉普拉斯乘子法優(yōu)化目標(biāo)函數(shù)進(jìn)而選擇特征子集;根據(jù)高維數(shù)據(jù)的稀疏性,魯棒鄰域嵌入的無監(jiān)督特征選擇算法[18]通過K近鄰構(gòu)造權(quán)重系數(shù)矩陣,并利用1正則約束刪除數(shù)據(jù)中的噪聲和異常點(diǎn),運(yùn)用ADMM優(yōu)化方法得到具有代表性和判別性的特征子集。

上述基于圖正則的無監(jiān)督特征選擇算法構(gòu)造的相似矩陣都是來自原始數(shù)據(jù)集,沒有嵌入到學(xué)習(xí)過程,且在后續(xù)過程中保持不變。為了解決這個問題,自適應(yīng)結(jié)構(gòu)學(xué)習(xí)的無監(jiān)督特征選擇算法[19]為結(jié)構(gòu)學(xué)習(xí)和特征選擇提供了一個統(tǒng)一的框架,從特征選擇的結(jié)果中自適應(yīng)地學(xué)習(xí)結(jié)構(gòu),并重新選擇重要特征以保留數(shù)據(jù)的精確結(jié)構(gòu);結(jié)構(gòu)圖優(yōu)化的無監(jiān)督特征選擇算法[20]融合了特征選擇和局部結(jié)構(gòu)學(xué)習(xí),可以自適應(yīng)地更新相似矩陣,通過約束相似矩陣使其包含更準(zhǔn)確的數(shù)據(jù)結(jié)構(gòu)信息,從而選擇更有代表性的特征;基于自適應(yīng)圖和約束的無監(jiān)督特征選擇算法(Unsupervised feature selection via adaptive graph learning and constraint,EGCFS)[21]將相似矩陣的結(jié)構(gòu)納入優(yōu)化過程以自適應(yīng)地學(xué)習(xí)圖結(jié)構(gòu),同時,將最大化類間散布矩陣和自適應(yīng)圖結(jié)構(gòu)的思想集成到一個統(tǒng)一的框架中,不僅可以獲得出色的結(jié)構(gòu)性能,也可以選擇不相關(guān)但有區(qū)別的特征。

然而,無論來自原始數(shù)據(jù)集的相似矩陣是否嵌入到模型的學(xué)習(xí)中,相似矩陣都是由相同且固定的近鄰數(shù)構(gòu)造或更新的。在現(xiàn)實(shí)世界中,高維數(shù)據(jù)往往是分布不均勻的,為每個樣本選取相同而固定的近鄰數(shù)是不能很好地適應(yīng)每個樣本的局部幾何結(jié)構(gòu)的[22],這使得由相同且固定近鄰數(shù)來構(gòu)造的相似矩陣是不可靠的。為了解決這個問題,本文基于文獻(xiàn)[22]中提出的自適應(yīng)鄰域思想,提出了一種基于自適應(yīng)鄰域和自表示正則的無監(jiān)督特征選擇算法(Adaptive neighborhood regularized self-representation,ANRSR)。首先,根據(jù)數(shù)據(jù)集自身的稀疏稠密情況,為每個樣本自適應(yīng)的選擇近鄰數(shù),進(jìn)而構(gòu)建拉普拉斯矩陣。其次,將拉普拉斯圖嵌入到目標(biāo)函數(shù)中,以保持原始數(shù)據(jù)的局部結(jié)構(gòu)。然后,用迭代算法優(yōu)化目標(biāo)函數(shù)。最后,在公開的UCI數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),驗(yàn)證所提算法ANRSR的有效性。

1 問題形式化

1.1 符號說明

首先介紹本文中使用的一些符號,其中,大寫粗體表示矩陣,小寫粗體表示向量。對于任列向量v=[v1,v2,…,vn]T,它的2范數(shù)為對于任意矩陣M=[mij]n×d∈Rn×d,M的2,1范數(shù)定義為對于任意方陣A=[aij]n×n∈Rn×n,它的跡為可逆矩陣表示為A-1,In∈Rn×n是單位矩陣。

數(shù)據(jù)集X=[x1;x2;…;xn]=[f1,f2,…,fd]∈Rn×d,表示有n個樣本和d個特征,其中xi是一個d維的樣本向量,fj是一個n維的特征向量。令樣本集S={x1,x2,…,xn},特征集F={f1,f2,…,fd}。

1.2 所提算法ANRSR

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

(1)

則對于所有的特征向量有

X=XW+E

(2)

式中:W=[wij]d×d∈Rd×d是特征自表示系數(shù)矩陣。顯然,系數(shù)矩陣W反映了不同特征的重要性,令W=[w1;w2;…;wd],其中wi是W的第i行?！瑆i‖2表示第i個特征的重要度,則‖wi‖2的值越大,表示第i個特征越重要。通過數(shù)據(jù)集的特征自表示,無監(jiān)督特征選擇問題轉(zhuǎn)化為如下形式

minW‖X-XW‖2,1+α‖W‖2,1

(3)

式中:α>0是平衡損失項(xiàng)和2,1正則項(xiàng)的參數(shù)。

譜圖理論和流形學(xué)習(xí)的研究表明,可以通過數(shù)據(jù)樣本的最近鄰圖有效地建模局部幾何結(jié)構(gòu)[10,24]。因此,將拉普拉斯圖嵌入到式(3)中進(jìn)行優(yōu)化,如下所示

minW‖X-XW‖2,1+α‖W‖2,1+βtr(WTXTLXW)

(4)

式中:參數(shù)β>0,L是拉普拉斯圖。

(5)

由于所有樣本采用相同且固定的近鄰數(shù)不能很好地適應(yīng)每個樣本的局部流形結(jié)構(gòu)。文獻(xiàn)[22]根據(jù)數(shù)據(jù)自身的稀疏稠密情況自適應(yīng)選擇近鄰數(shù)。首先,為數(shù)據(jù)集中的每個樣本引入一個有序序列。

定義1有序序列[22]數(shù)據(jù)集X=[x1;x2;…;xn]∈Rn×d,樣本集S={x1,x2,…,xn},令i∈{1,2,…,n},對于樣本xi的有序序列定義為

list(xi)=(x(i,1),x(i,2),…,x(i,n-1))

(6)

式中:Δ(xi,x(i,1))≤Δ(xi,x(i,2))≤…≤Δ(xi,x(i,n-1)),S={xi,x(i,1),x(i,2),…,x(i,n-1)},Δ(xi,xj)是樣本xi和樣本xj之間的歐式距離。簡單起見,將Δ(xi,x(i,j))記為Δi(x(i,j))。

(7)

式(4)中的拉普拉斯圖是根據(jù)數(shù)據(jù)自身的稀疏稠密情況自適應(yīng)選擇近鄰數(shù)來構(gòu)建的,則這個模型就被稱為基于自適應(yīng)鄰域和自表示正則的無監(jiān)督特征選擇算法ANRSR。

不同于K近鄰法,在定義2中,數(shù)據(jù)集中每個樣本點(diǎn)獲得的最近鄰個數(shù)是不同的,能夠反映出數(shù)據(jù)集的樣本稀疏稠密情況。算法1[22]給出了自適應(yīng)鄰域集的求解過程。

算法1自適應(yīng)鄰域集

輸入:數(shù)據(jù)集X∈Rn×d(d個特征,n個樣本)中的樣本xi(i=1,2,…,n);

輸出:自適應(yīng)鄰域集AN(xi);

1: 運(yùn)用歐式距離,分別計(jì)算樣本xi與樣本x1,…,xi-1,xi+1,…,xn的距離,得到距離向量disi;

2: 升序排列更新disi,根據(jù)定義1得到xi的有序序列l(wèi)ist(xi);

4: 根據(jù)list(xi),采用式(7)計(jì)算xi的自適應(yīng)鄰域集AN(xi)。

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

ANRSR模型實(shí)際上是凸的,但是損失函數(shù)和正則項(xiàng)都不平滑。因此在本節(jié)中,使用迭代方法解決ANRSR的優(yōu)化問題。

(8)

(9)

算法2基于自適應(yīng)鄰域和自表示正則的無監(jiān)督特征選擇算法ANRSR

輸入:數(shù)據(jù)集X∈Rn×d(n個樣本,d個特征),參數(shù)α,β,選擇的特征個數(shù)m;

輸出:所選的特征子集I;

2: fori=1∶n

3: 調(diào)用算法1,獲得樣本xi的自適應(yīng)鄰域集AN(xi);

4: 根據(jù)式(5),計(jì)算樣本xi與AN(xi)中樣本的相似權(quán)重系數(shù)si;

5: end if

6: 樣本相似矩陣S=[s1;…;sn];

8: repeat

9: 用式(9)更新Wt+1;

11:t=t+1;

12:until收斂;

13:W=[w1;w2;…;wd],降序排列‖wi‖2,i=1,2,…,d,則I是前m個向量的下標(biāo)集所對應(yīng)的特征子集。

在ANRSR算法中,首先需要根據(jù)自適應(yīng)鄰域計(jì)算拉普拉斯矩陣,其計(jì)算復(fù)雜度為O(n2d);其次是迭代更新W,每次迭代的時間復(fù)雜度為O(n2d+d3)。則ANRSR的總時間復(fù)雜度為O(n2d+T(n2d+d3)),其中T是迭代的次數(shù)。又迭代次數(shù)T通常是大于1的,因此,ANRSR的時間復(fù)雜度為O(T(n2d+d3))。

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

實(shí)驗(yàn)選用了4個公開的人臉數(shù)據(jù)集對算法進(jìn)行測試研究,包括JAFFE、IMM40、ATT40、warpAR10P,其中,JAFFE、IMM40、ATT40是來自于文獻(xiàn)[21]的數(shù)據(jù)集,可從https://github.com/LilyLSL/EGCFS中獲取,warpAR10P可從FEATURE SELECTION DATASETS(http://featureselection.asu.edu/datasets.php)中獲取。數(shù)據(jù)集的詳細(xì)信息如表1所示。

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

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

為了驗(yàn)證本文提出的基于自適應(yīng)鄰域和自表示正則的無監(jiān)督特征選擇算法ANRSR的優(yōu)勢,將其和選擇所有特征(Baseline)以及4種經(jīng)典的無監(jiān)督特征選擇算法進(jìn)行了比較,包括基于拉普拉斯打分的特征選擇LS[10]、嵌入無監(jiān)督特征選擇EUFS[13]算法、基于重構(gòu)的無監(jiān)督特征選擇REFS[15]算法、基于自適應(yīng)圖和約束的無監(jiān)督特征選擇EGCFS[21]算法。對比算法LS、EUFS、REFS和本文所提算法ANRSR采用熱核相似性度量和帶寬參數(shù)t=1得到拉普拉斯圖,EGCFS在學(xué)習(xí)過程中自動更新拉普拉斯圖。同時,ANRSR的近鄰數(shù)是根據(jù)數(shù)據(jù)集本身的分布自適應(yīng)得到的,其他對比算法LS、EUFS、REFS、EGCFS的近鄰數(shù)k均設(shè)置為5。為了公平比較,通過網(wǎng)格搜索范圍{10-4,10-3,10-2,10-1,1,101,102,103,104}為所有對比算法調(diào)整其正則化參數(shù),并記錄其最佳性能。對所有的數(shù)據(jù)集,特征選擇的個數(shù)設(shè)置為{20,30,…,100}。實(shí)驗(yàn)選用K-means算法進(jìn)行聚類,由于K-means算法對初始選取的聚類中心點(diǎn)是敏感的,因此,K-means算法對選取的特征子集運(yùn)行30次實(shí)驗(yàn)記錄平均值。

3.2 度量標(biāo)準(zhǔn)

為了驗(yàn)證算法的有效性,文中采用兩種判斷標(biāo)準(zhǔn):聚類精度(Clustering accuracy,ACC)和歸一化互信息(Normalized mutual information,NMI)來衡量不同算法選擇不同特征子集時的效果,其中,ACC和NMI的值越大表示算法效果越好。

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

本節(jié)比較了所提算法ANRSR算法與LS、EUFS、REFS、EGCFS和Baseline在表1數(shù)據(jù)集上的性能,并對性能指標(biāo)進(jìn)行了分析。

為了說明參數(shù)α,β對所提算法ANRSR的敏感程度,圖1展示了參數(shù)對IMM40數(shù)據(jù)集的影響。從圖1中可以看出,算法ANRSR對β不敏感,而對α敏感。當(dāng)α較大時,獲取W的更多行稀疏,從而在某種程度上獲取更精確的特征重要度排序。但是對于如何自適應(yīng)獲得較好的參數(shù)值依舊是一個開放式的問題。

圖1 在數(shù)據(jù)集IMM40上所提算法ANRSR關(guān)于參數(shù)的影響

表2和表3分別記錄了不同算法在表1的4個數(shù)據(jù)集上最高的聚類精度和歸一化互信息結(jié)果,其中最好的結(jié)果用粗體標(biāo)注,次優(yōu)用下劃線標(biāo)注。與保留全部特征(Baseline)的聚類精度相比,ANRSR不僅大幅度地降低了特征維數(shù),而且提高了聚類性能,這表明ANRSR選擇的特征子集相對具有代表性和判別性。同時,ANRSR的聚類精度在3個數(shù)據(jù)集上優(yōu)于其他對比算法,而在歸一化互信息上均優(yōu)于其他對比的無監(jiān)督特征選擇算法。

從表2和表3的信息可知,所提算法ANRSR在總體性能上高于其他對比算法。盡管所有對比的無監(jiān)督特征選擇算法LS、EUFS、REFS和EGCFS在模型學(xué)習(xí)過程中均保持了原有數(shù)據(jù)集的局部幾何結(jié)構(gòu),但本文所提算法得到的聚類性能更好,原因可以歸結(jié)為以下兩點(diǎn):(1)ANRSR采用的是能捕捉原數(shù)據(jù)集稀疏稠密的局部幾何結(jié)構(gòu),而LS、EUFS、REFS均采用的是忽略數(shù)據(jù)集分布結(jié)構(gòu)的相同且固定的鄰域數(shù);(2)EGCFS在IMM40數(shù)據(jù)集上的聚類精度高于ANRSR,但只高出了0.2%。EGCFS算法在優(yōu)化過程中是自適應(yīng)學(xué)習(xí)且更新局部結(jié)構(gòu),但每次更新時依舊固定了鄰域數(shù)目。

表2 所有無監(jiān)督特征選擇對比算法的最大聚類精度

表3 所有無監(jiān)督特征選擇對比算法的最大歸一化互信息

為了進(jìn)一步說明ANRSR所選擇的特征子集是重要的且具有判別性,本節(jié)展示了ANRSR在ATT40數(shù)據(jù)集上的效果示例圖。首先,從ATT40中隨機(jī)的選擇兩個樣本;然后,執(zhí)行ANRSR算法,為這兩個樣本分別選擇出20、40、60、80、100個特征。具體效果如圖2所示,其中,從左到右依次是原圖、選擇20、40、60、80、100個特征所對應(yīng)的圖,白色“方塊”表示所選擇的特征。從圖2可以看出,ANRSR算法所選擇的特征傾向于有判別性的部分,如眼、鼻子、唇和臉頰,這些特征通常用來描述一個人臉的特性。這也意味著ANRSR在一定程度上可以獲得最優(yōu)的特征子集。

圖2 ANRSR算法作用在ATT40數(shù)據(jù)集上的示例圖

4 結(jié)束語

本文提出了一種基于自適應(yīng)鄰域和自表示正則的無監(jiān)督特征選擇算法。不同于已存在的基于流形結(jié)構(gòu)的無監(jiān)督特征選擇算法,本文所提算法不需要人為地對不同的數(shù)據(jù)集指定相同且固定的鄰域個數(shù),而是根據(jù)數(shù)據(jù)集自身的稀疏稠密分布情況來確定每個樣本的近鄰數(shù),進(jìn)而構(gòu)造拉普拉斯圖,并將其與具有魯棒性的特征自表示無監(jiān)督特征選擇框架相結(jié)合。實(shí)驗(yàn)表明,本文所提算法可以選擇出具有判別性的特征子集,進(jìn)而取得較好的聚類效果。然而,本文中嵌入的拉普拉斯圖在模型學(xué)習(xí)過程中保持不變,拉普拉斯圖是由原始數(shù)據(jù)集構(gòu)造的,而原始的高維數(shù)據(jù)集往往有噪聲和異常,導(dǎo)致自適應(yīng)鄰域集可能不可靠,在接下來的工作中需要探索如何在優(yōu)化過程中更新鄰域集構(gòu)造的拉普拉斯圖。