基于自適應鄰域嵌入的無監(jiān)督特征選擇算法

劉艷芳 李文斌 高 陽

1(計算機軟件新技術國家重點實驗室(南京大學) 南京 210023)2(龍巖學院數(shù)學與信息工程學院 福建龍巖 364012)(liuyanfang003@163.com)

隨著全球信息化的發(fā)展，許多應用領域得到的原始數(shù)據(jù)往往具有很高的特征維數(shù).對高維數(shù)據(jù)的處理不僅增加了運算的時間復雜度和空間復雜度，也會導致學習模型的過擬合現(xiàn)象.而在高維數(shù)據(jù)中，只有部分特征是和學習任務相關的，同時，流形學習中驗證高維空間的數(shù)據(jù)可以在低維空間表示[1]，因此，對這些高維數(shù)據(jù)進行降維是有必要的.

特征選擇是一種重要的降維方法[2]，它一般是根據(jù)每個特征的重要性排序來選擇特征子集，保留了原始特征的物理意義，為學習的模型提供了可解釋性，這在許多研究領域是十分重要的.根據(jù)數(shù)據(jù)中是否有標簽信息，特征選擇分為監(jiān)督特征選擇[3-4]、半監(jiān)督特征選擇[5-6]和無監(jiān)督特征選擇[7-9].而在現(xiàn)實世界中存在大量的無標簽高維數(shù)據(jù)，對這些數(shù)據(jù)進行標記是昂貴和耗時的，甚至是不可行的，比如醫(yī)療圖像數(shù)據(jù)是需要非常專業(yè)的人士進行標注.因此，對無監(jiān)督特征選擇方法的研究是具有很大現(xiàn)實意義的.

近年來，國內(nèi)外許多研究人員對無監(jiān)督特征選擇算法進行了大量的研究.在已有的無監(jiān)督特征選擇算法中，很多學者將k近鄰法得到的樣本相似矩陣嵌入到目標函數(shù)中，在高維無標記的數(shù)據(jù)集中得到了不錯的結果.主要算法有：基于拉普拉斯打分的特征選擇LS[10]根據(jù)同一類別數(shù)據(jù)較緊湊的特性，利用近鄰得到數(shù)據(jù)的局部幾何結構圖，然后計算每個特征的得分選擇特征；多類簇無監(jiān)督特征選擇MCFS[11]通過對拉普拉斯矩陣的譜分析獲得特征之間的關系，然后利用1正則回歸選擇特征子集；無監(jiān)督判別特征選擇算法UDFS[12]基于樣本可以由線性分類器分類的假設，采用k近鄰挖掘的局部判別信息和2,1正則得到具有判別性的特征子集；基于非負譜分析的無監(jiān)督特征選擇算法NDFS[13]將k近鄰得到數(shù)據(jù)的局部幾何結構、譜聚類方法和正則結合起來，獲得了更加精確的偽標簽信息和判別性的特征子集；魯棒的無監(jiān)督特征選擇算法RUFS[14]利用了魯棒非負矩陣分解、局部學習、魯棒特征學習，以及正則來處理標簽和特征之間的關系，并刪除冗余和噪聲特征；自適應結構學習的無監(jiān)督特征選擇FSASL[15]為結構學習和特征選擇提供了一個統(tǒng)一的框架，用特征選擇的結果自適應更新結構信息，同時用更新后的結構去重新選擇具有代表性的特征子集；冗余和噪聲特征的存在導致原數(shù)據(jù)集得到的相似性矩陣不完全可信，因此，結構圖優(yōu)化的無監(jiān)督特征選擇算法SOGFS[16]融合了特征選擇和局部結構學習，可以根據(jù)所選的特征子集自適應地更新相似性矩陣，并且通過約束相似性矩陣選擇更有價值的特征；已有特征選擇算法往往假設線性重構函數(shù)，而重構函數(shù)是依賴于數(shù)據(jù)本身的，而在高維情況下數(shù)據(jù)集往往是線性不可分的，因此，基于重構的無監(jiān)督特征選擇REFS[17]將重構函數(shù)的學習嵌入到特征選擇過程中，同時，為保留原有特征結構，加入了拉普拉斯矩陣的正則項，進而選擇具有判別性的特征子集；依賴指導的無監(jiān)督特征選擇算法DGUFS[18]給出了2種依賴關系：一種是原數(shù)據(jù)集和學習到的聚類標簽集的依賴關系，另一種是所選擇的特征子集和聚類標簽的依賴關系，同時加入了2,0等式約束，進而獲得具有代表性和判別性的特征子集；基于鄰域保持學習的無監(jiān)督特征選擇[19]利用k鄰域重構系數(shù)，引入中間矩陣構造低維空間，繼而運用拉普拉斯乘子法優(yōu)化目標函數(shù)，選擇有效的特征子集；基于結構正則的自適應特征選擇[20]首先用k鄰域重構圖，然后低秩約束重構圖對應的拉普拉斯矩陣，并在優(yōu)化過程學習重構圖和所選特征矩陣，進而在過程中自適應局部結構；為了減少噪聲數(shù)據(jù)對數(shù)據(jù)分布的影響，基于局部學習和組系數(shù)回歸的無監(jiān)督特征選擇JLLGSR[21]首次結合基于局部學習的聚類和組稀疏正則項，并利用一個新的偏置項來提高模型的泛化性，進而選擇相關的特征子集；基于廣義不相關回歸和自適應圖的無監(jiān)督特征選擇URAFS[22]將通過最大熵得到的自適應圖嵌入到流形學習中，并加入到廣義不相關的回歸模型中，通過閉式解得到不相關、無冗余的判別性特征子集；根據(jù)高維數(shù)據(jù)的稀疏性，文獻[23]提出了魯棒鄰域嵌入的無監(jiān)督特征選擇RNE，通過k近鄰構造系數(shù)矩陣，并加入1范數(shù)正則約束數(shù)據(jù)中的噪聲和異常點，進而利用ADMM優(yōu)化方法得到重要的特征子集；基于譜聚類的無監(jiān)督特征選擇FSSC[24]分別運用self-tuning[25]、樣本標準差和距離矩陣[26]等3種自適應鄰域方法對所有特征進行譜聚類，將相似性高的特征聚成一類，并通過特征的區(qū)分度與特征獨立性之積度量特征重要性,從各特征簇選取代表性特征，構造特征子集.

已有的融合了流形學習、結構學習和譜聚類學習的無監(jiān)督特征選擇算法，大都采用k近鄰得到局部相似矩陣或者相似圖.然而，高維數(shù)據(jù)集大都不是均勻分布的，為每個樣本選取相同而固定的近鄰數(shù)是不能很好地適應每個樣本的局部幾何結構的.因此，本文提出了一種基于自適應鄰域嵌入的無監(jiān)督特征選擇算法(adaptive neighborhood embedding based unsupervised feature selection, ANEFS).首先，根據(jù)數(shù)據(jù)集自身的稀疏稠密情況，為每個樣本自適應地選擇近鄰數(shù).其次，計算樣本和其自適應鄰域的權重系數(shù)，進而構造局部相似矩陣.然后，引入具有正交化的中間矩陣構建低維空間，并運用拉普拉斯乘子法選出有效的特征子集.最后，在公開的6個UCI數(shù)據(jù)集的實驗結果表明，所提出的算法能夠選出具有更高聚類精度和歸一化互信息的特征子集.

1 自適應鄰域

本節(jié)將介紹本文中使用的一些符號以及根據(jù)數(shù)據(jù)稀疏稠密情況構造自適應鄰域.

1.1 符號說明

1.2 自適應鄰域構造

通常運用k近鄰法，采用歐氏距離，為每個樣本找到k個近鄰點.基于任何2個對象之間的歐氏距離不受分析中添加新樣本的影響，同時，相較于其他度量方式，歐氏距離往往擁有較少的計算時間[27]，本文繼續(xù)采用歐氏距離度量樣本之間距離.然而，所有樣本采用相同的近鄰數(shù)，不能很好地適應每個樣本的局部流形結構特征.文獻[28]在樣本固定、特征逐個到來的背景下根據(jù)數(shù)據(jù)自身的稀疏稠密情況自適應選擇鄰域，進而運用鄰域粗糙集來選擇特征.本文在文獻[28]自適應鄰域的基礎上，明確使用的定義，并改進可接受的最大距離.首先，我們?yōu)閿?shù)據(jù)集中的每個樣本定義了一個有序序列.

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

(1)

其中，Δ(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之間的歐氏距離.

如果數(shù)據(jù)集X服從均勻分布，將Δ(xi,x(i,n-1))分成n-1段，那么每一段中應包含一個樣本.在實際應用中，數(shù)據(jù)集往往不是均勻分布的.為了根據(jù)數(shù)據(jù)集實際分布尋找鄰域，我們在有序序列的基礎上，根據(jù)每個樣本和其他樣本之間的最大距離和最小距離，即樣本自身的稀疏稠密情況來定義樣本的自適應鄰域.簡單起見，我們將Δ(xi,x(i,j))記為Δi(x(i,j)).

(2)

1.3 人造數(shù)據(jù)集的自適應鄰域分析

Fig. 1 Neighbors based on kNN and the adaptive neighborhood圖1 基于k近鄰和自適應鄰域構造法的近鄰點分布

由圖1(a)可知，原始50個樣本點是非均勻分布的，其中樣本a處數(shù)據(jù)樣本分布稀疏，樣本b相對于樣本a處數(shù)據(jù)樣本分布更為稀疏，而樣本c處數(shù)據(jù)樣本分布較為稠密.圖1(b)為k=5時k近鄰法得到的近鄰分布結果，樣本a，b和c的近鄰數(shù)均相等，無法反映數(shù)據(jù)分布的稠密稀疏情況.圖1(c)是根據(jù)式(2)得到的自適應鄰域分布結果，從圖中可以看到，樣本，和的近鄰樣本數(shù)分別為4，1和18.因此，可以說明，自適應鄰域構造方法得到的鄰域個數(shù)已經(jīng)考慮到數(shù)據(jù)分布的稀疏稠密程度.

2 自適應鄰域嵌入的特征選擇算法

運用k近鄰法得到的樣本相似矩陣可以捕獲到比全局結構更加關鍵的局部幾何數(shù)據(jù)結構[29].在無監(jiān)督特征選擇中，很多學者將k近鄰法得到的樣本相似矩陣嵌入到目標函數(shù)中，在高維無標記的數(shù)據(jù)集中得到了不錯的結果.然而，k近鄰法得到的局部幾何結構不能反映數(shù)據(jù)分布的稠密稀疏情況.因此，本文將反映數(shù)據(jù)分布情況的自適應鄰域引入到無監(jiān)督特征選擇算法中，提出了基于自適應鄰域嵌入的無監(jiān)督特征選擇算法(adaptive neighborhood embedding based unsupervised feature selection, ANEFS).

自適應鄰域嵌入的無監(jiān)督特征選擇算法分為4部分：1)利用式(2)中的自適應鄰域構造方法得到數(shù)據(jù)樣本的近鄰點；2)求解每個樣本的權重系數(shù)向量；3)引入中間矩陣構建低維空間；4)運用拉普拉斯乘子法選出有效的特征子集.

2.1 構造自適應鄰域集

不同于k近鄰法，定義2中數(shù)據(jù)集中每個樣本點獲得的自適應鄰域個數(shù)是不同的，能夠反映出數(shù)據(jù)集的樣本稀疏稠密情況.

算法1.自適應鄰域集.

輸出：自適應鄰域集AN(xi).

① 運用歐氏距離，分別計算樣本xi與樣本x1,…,xi-1,xi+1,…,xn的距離，得到距離向量disi；

② 升序排列更新disi，并得到xi的有序序列l(wèi)ist(xi)；

④ 根據(jù)list(xi)，采用式(2)計算xi的自適應鄰域集AN(xi)；

根據(jù)上述的算法1的步驟，每步的時間復雜度分別為：步驟①中計算一個樣本與其他樣本間的距離需要O(nd)；步驟②對距離進行排序需要O(nlogn)；步驟③和④計算最大可接受均值，并尋找一個樣本的自適應鄰域需要O(1+n).因此，算法1的整體時間復雜度為O(nd+nlogn+1+n).在高維數(shù)據(jù)下，特征維數(shù)d大于樣本數(shù)n，則算法1的時間復雜度是O(nd).

2.2 求解自適應鄰域權重系數(shù)

求解每個數(shù)據(jù)樣本與其自適應近鄰點之間線性關系的權重系數(shù)，可以形式化為一個回歸問題.采用均方差作為目標函數(shù)，即:

(3)

其中，wi=(wi1,wi2,…,wi|AN(xi)|)T是|AN(xi)|維的列向量，|AN(xi)|是xi自適應鄰域的個數(shù).為了方便求解，我們將式(3)轉換為形式:

(4)

(5)

其中，zi=(xi-xj)(xi-xj)T，xj∈AN(xi)，λ≥0是一個常數(shù).式(5)對wi(i=1,2,…,n)進行求導:

(6)

2.3 基于自適應鄰域嵌入的低維空間

其中，x(i,k)是定義1中樣本xi的有序序列l(wèi)ist(xi)中的第k個樣本.式(8)中是數(shù)據(jù)集在原有高維空間根據(jù)自適應鄰域構造方法得到的樣本相似權重系數(shù).根據(jù)式(8)，可以將式(3)等價形式化為

(9)

為了保持原始樣本集的局部幾何結構，即相似矩陣S在低維空間中保持不變，通過選出有效的特征子集I?F，構造低維空間的最小誤差可表示為

根據(jù)式(11)可知，中間矩陣H的每一行的元素中有且只有一個元素為1，其他全部為0，因此，中間矩陣H是正交矩陣，即HHT=Im.則式(10)可以轉換為

(12)

2.4 優(yōu)化目標函數(shù)

(13)

其中，M=X(In-S)(In-S)TXT.式(13)對H進行求導并令其等于0，同時，根據(jù)約束條件HHT=Im，則有：

(14)

即：

MHT=μHT.

(15)

從式(15)中可知，HT和μ是由矩陣M的特征向量和特征值構成的.為了從數(shù)據(jù)中選擇有效的特征子集，只需取M中最小的m個特征值對應的特征向量.

算法2.自適應鄰域嵌入的無監(jiān)督特征選擇算法.

輸出：特征子集I.

① fori=1:n

② 調(diào)用算法1，尋找樣本xi的自適應鄰域集AN(xi)；

③ 根據(jù)式(7)，計算樣本xi與AN(xi)中樣本的相似權重系數(shù)wi；

④ end if

⑤ 根據(jù)式(8)，構造數(shù)據(jù)集中樣本相似矩陣S；

⑥ 計算矩陣M=X(In-S)(In-S)TXT的特征向量矩陣V和特征值矩陣μ；

⑦ 根據(jù)μ的升序更新V，令更新后的V=(v1,v2,…,vd)，其中vi是d維度列向量，則HT=(v1,v2,…,vm)T；

3 實驗與結果分析

實驗選用了6個公開數(shù)據(jù)集對算法進行測試研究，實驗數(shù)據(jù)集可從FEATURE SELECTION DATASETS(1)http://featureselection.asu.edu/datasets.php中獲取.數(shù)據(jù)集詳細信息如表1所示，其中，Yale，warpAR10P和orlraws10P是人臉數(shù)據(jù)集，GLIOMA和ALLAML屬于基因表達數(shù)據(jù)集，madelon屬于人工數(shù)據(jù)集.

3.1 實驗參數(shù)設計

為了驗證提出的自適應鄰域嵌入的無監(jiān)督特征選擇算法ANEFS的性能，實驗比較了ANEFS與基于拉普拉斯打分的特征選擇LS[10]、多類簇無監(jiān)督特征選擇MCFS[11]、自適應結構學習的無監(jiān)督特征選擇FSASL[15]、基于重構的無監(jiān)督特征選擇REFS[17]、依賴指導的無監(jiān)督特征選擇DGUFS[18]、基于廣義不相關回歸和自適應圖的無監(jiān)督特征選擇URAFS[22]以及選擇所有特征(Baseline)在表1數(shù)據(jù)集的實驗結果.對比算法LS和MCFS采用熱核相似性度量特征相似性，帶寬參數(shù)t=1.根據(jù)相關參考文獻中的參數(shù)敏感分析，選用文獻中運行結果較好的參數(shù)設置，其中，對比算法FSASL中控制全局結構的參數(shù)α=0.01，控制局部結構的參數(shù)β=0.1，控制特征選擇的稀疏性參數(shù)γ=0.1；對比算法REFS中懲罰沒有被選擇的特征重構錯誤的參數(shù)α=0.1，控制重構后保持原有特征結構的參數(shù)β=0.1；對比算法DGUFS中控制學習得到的聚類標簽相關矩陣的低秩參數(shù)α=100，控制原數(shù)據(jù)集、學習得到的聚類標簽和所選特征子集之間內(nèi)部依賴關系的參數(shù)β=0.5；對比算法URAFS中控制圖正則項的參數(shù)α和最大熵得到的相似矩陣的參數(shù)β均設置為1，控制特征選擇的行稀疏性參數(shù)λ=100.同時，除了本文提出算法ANEFS的近鄰數(shù)是根據(jù)數(shù)據(jù)集本身的分布自適應得到以及URAFS中是優(yōu)化自適應的，其他對比算法LS,MCFS,FSASL,REFS,DGUFS的近鄰數(shù)k均設置為5.對所有的數(shù)據(jù)集，特征選擇的個數(shù)設置為{20,30,…,100}.實驗選用K-means算法進行聚類，而K-Means算法對初始選取的聚類中心點是敏感的，因此，K-means算法對選取的特征子集運行30次實驗記錄平均值.

3.2 度量標準

為了驗證算法的有效性，文中采用2種判斷標準：聚類精度(clustering accuracy,ACC)和歸一化互信息(normalized mutual information,NMI)，來衡量不同算法選擇不同特征子集時的效果，其中，ACC和NMI的值越大表示算法效果越好.

1) 聚類精度(ACC)：

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

2) 歸一化互信息(NMI)：

3.3 實驗結果分析

本節(jié)比較了所提的ANEFS算法與6種無監(jiān)督特征選擇算法LS,MCFS,FSASL,REFS,DGUFS和URAFS在表1數(shù)據(jù)集上的性能，并對性能指標值進行了分析.

3.3.1 示例分析

本節(jié)展示了所提算法ANEFS的效果示例圖.首先，隨機地從Yale數(shù)據(jù)集中選擇2個樣本作為示例.然后，在這2個樣本上執(zhí)行ANEFS算法，并分別選擇出20,40,60,80,100個特征.為了便于說明，所選擇的特征用白色“方框”表示，未被選擇的特征保留原有的值，如表2所示.從表2可以看出，所提出的ANEFS算法所選擇的特征是相對集中的，并且傾向于選擇有辨別性的部分，如眼、唇和臉頰，可以描述一個人臉的特性.這也意味著所提算法在一定程度上可以得到最優(yōu)的特征子集.

Tabel 2 Toy Examples of ANEFS on Yale Dataset表2 ANEFS算法作用在Yale數(shù)據(jù)集上的示例圖

3.3.2 實驗結果分析

由于所選最優(yōu)特征數(shù)目是未知的，為了更好地評估無監(jiān)督特征選擇算法的性能，我們記錄了在不同特征子集上最好的結果.表3和表4分別記錄了不同算法在表1的6個數(shù)據(jù)集上最高的聚類精度和歸一化互信息結果，其中最好的結果用粗體表示，次優(yōu)用下劃線標注，最后一行是各個算法在6個數(shù)據(jù)集上的平均結果.與保留全部特征(Baseline)的聚類性能相比，這些無監(jiān)督特征選擇算法不僅大幅度的降低了特征維數(shù)，而且提高了聚類效果.尤其是所提算法ANEFS選擇了15%以內(nèi)的特征數(shù)在聚類精度和歸一化互信息上分別提高了7.84%和10.8%，這表明ANEFS選擇的特征子集相對具有代表性和判別性.同時，ANEFS在平均聚類效果上優(yōu)于其他6種無監(jiān)督特征選擇算法，其中，聚類精度上提高了4.29%～9.68%，歸一化互信息上提高了7.88%～11.75%.

Table 3 Maximum Clustering Accuracy (%) of the Compared Algorithms表3 無監(jiān)督特征選擇對比算法的最大聚類精度

Table 4 Maximum Normalized Mutual Information (%) of the Compared Algorithms表4 無監(jiān)督特征選擇對比算法的最大歸一化互信息

圖2和圖3分別所提ANEFS算法、對比算法LS,MCFS,FSASL,REFS,DGUFS,URAFS以及全部特征Baseline在表1的6個數(shù)據(jù)集上對應不同特征數(shù)目的實驗結果.從圖2和圖3的實驗結果中，我們可知在人臉數(shù)據(jù)集Yale,warpAR10P,orlraws10P和基因數(shù)據(jù)集ALLAML上，所提算法ANEFS的聚類精度和歸一化互信息絕對的優(yōu)于其他6種對比算法，較大的提高了聚類效果.在基因數(shù)據(jù)集GLIOMA上，除了對比算法DGUFS，所提算法ANEFS的聚類效果優(yōu)于其他對比算法.在人工數(shù)據(jù)集madelon上，ANEFS選擇特征數(shù)目為70或者80時聚類性能優(yōu)于其他對比算法.

Fig. 2 Relationships between clustering accuracy of compared algorithms and the number of selected features圖2 對比算法的聚類精度與特征選擇數(shù)目的關系

Fig. 3 Relationships between normalized mutual information of compared algorithms and thenumber of selected features圖3 對比算法的歸一化互信息與特征選擇數(shù)目的關系

綜合表3,4和圖2,3的對比信息可知，所提算法ANEFS在數(shù)據(jù)集上只需選擇較少的特征數(shù)量就能達到不錯的效果.從總體性能上，對比LS,MCFS,FSASL,REFS,DGUFS和URAFS等6種無監(jiān)督特征選擇算法和保留全部特征(Baseline)，本文所提ANEFS的聚類效果更好.這可能的原因可以歸結為2點：1)降維后的數(shù)據(jù)集保持了原有數(shù)據(jù)集的局部幾何結構；2)ANEFS采用的是能捕捉原數(shù)據(jù)集稀疏稠密的局部幾何結構，而LS，MCFS，REFS，DGUFS這4種對比算法都采用了忽略數(shù)據(jù)集分布結構的固定鄰域數(shù)目，F(xiàn)SASL和URAFS算法在優(yōu)化過程中自適應學習局部結構，但FSASL依舊固定了鄰域數(shù)目，URAFS是通過最大熵得到相似矩陣，均不能很好地捕捉數(shù)據(jù)本身的局部結構.

4 總 結

本文提出了一種基于自適應鄰域嵌入的無監(jiān)督特征選擇算法，根據(jù)數(shù)據(jù)樣本自身的稀疏稠密情況來確定去其近鄰數(shù)，進而構造樣本相似矩陣，同時，通過引用具有正交性質(zhì)的中間矩陣，從原始空間直接選取特征子空間得到低維空間，從而實現(xiàn)在低維空間進行高維數(shù)據(jù)的聚類分析.實驗表明：本文提出的算法可以取得更好的聚類效果.本文將能接受的自適應鄰域距離由樣本與其他樣本的最大、最小距離來確定，接下來需要進一步探索更好的自適應鄰域選取方法，同時，重構系數(shù)矩陣在學習過程中是保持不變的，會進一步探索在優(yōu)化過程中采用自適應鄰域的結果.