基于鄰域區(qū)間擾動融合的無監(jiān)督特征選擇算法框架

呂曉林,杜 亮,2,周 芃,吳 鵬,2

(山西大學(xué) 1.計算機(jī)與信息技術(shù)學(xué)院;2.大數(shù)據(jù)科學(xué)與產(chǎn)業(yè)研究院,山西 太原 030006;3.安徽大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,安徽 合肥 230601)

高維大數(shù)據(jù)在許多領(lǐng)域隨處可見,科技的進(jìn)步更是加快了大數(shù)據(jù)的產(chǎn)生,每天都會有數(shù)億的數(shù)據(jù)產(chǎn)生,以文本、圖像、音頻、視頻等形式存在,覆蓋于各個領(lǐng)域。面對如此龐大的數(shù)據(jù),從中選擇出合適的信息對學(xué)習(xí)工作進(jìn)行指導(dǎo)變得極為困難。在這種境況下,特征選擇技術(shù)顯得尤為重要。特征選擇技術(shù)的主要目的是在一個特定的評估標(biāo)準(zhǔn)下,從原始的高維特征中選擇出最重要的特征子集,然后利用選擇出的特征子集結(jié)合一些有效的算法去完成數(shù)據(jù)聚類、分類等任務(wù)。

根據(jù)數(shù)據(jù)樣本是否含有標(biāo)簽信息,特征選擇算法可分為有監(jiān)督特征選擇[1,2]、半監(jiān)督特征選擇[3-5]和無監(jiān)督特征選擇[6-8]3類。有監(jiān)督和半監(jiān)督特征選擇通常會用到樣本的標(biāo)簽信息,通過特征和標(biāo)簽信息之間的相關(guān)性來評定特征的重要性。現(xiàn)實中采集到的數(shù)據(jù)很少有標(biāo)簽信息,并且標(biāo)記標(biāo)簽信息的代價很昂貴,在大規(guī)模數(shù)據(jù)中更是難以實現(xiàn),因此,研究無監(jiān)督場景下的特征選擇更具有實用價值。

無監(jiān)督特征選擇方法可分為3類:過濾式方法[9]、包裝式方法[10]和嵌入式方法[11-13]。過濾式方法的主要思路是對每一維的特征打分,即給每一維的特征賦予權(quán)重,權(quán)重代表該維特征的重要性,然后依據(jù)權(quán)重排序。過濾式方法是獨立于學(xué)習(xí)算法的,它的計算量很低,它的性能也有所欠缺。包裝式方法是將子集的選擇看作是一個搜索尋優(yōu)的問題,首先生成不同的組合,對組合進(jìn)行評價,然后再與其他的組合進(jìn)行比較。包裝式方法是與特定的學(xué)習(xí)算法相聯(lián)系的,雖然有較好的性能,但是它的計算量很大,不適用于對大規(guī)模數(shù)據(jù)的處理。嵌入式方法的思路是在模型既定的情況下得出對提高模型準(zhǔn)確性最好的屬性,即在確定模型的過程中,選出對模型有重要意義的屬性。具體而言,嵌入式方法是將特征選擇的學(xué)習(xí)過程嵌入進(jìn)模型中,故嵌入式方法能獲得一個較好的性能,但其計算量很大,不具備通用性。

1 相關(guān)工作

近年來,研究者基于無監(jiān)督特征選擇方法已經(jīng)做了大量的工作,其中最具有代表性的是拉普拉斯特征選擇算法(Laplacian score for feature selection,LapScore)[14]和多類簇特征選擇算法(Unsupervised feature selection for multi-cluster data,MCFS)[15]。LapScore是一種基于過濾式的無監(jiān)督特征選擇方法,是由何曉飛于2005年提出的,LapScore主要是基于拉普拉斯特征映射和局部保留投影,它的主要思想是距離近的兩個樣本點更可能屬于同一類。因此,LapScore認(rèn)為,數(shù)據(jù)的局部結(jié)構(gòu)比全局結(jié)構(gòu)更重要。LapScore是通過特征保留數(shù)據(jù)局部結(jié)構(gòu)的能力來評估其重要性的。MCFS是一種基于嵌入式的無監(jiān)督特征選擇方法,是由蔡登于2010年提出的,其主要思想是通過譜分析展開數(shù)據(jù)流形,然后利用L1譜分析回歸來決定特征的重要性。這兩種方法都是從改造模型的角度出發(fā)進(jìn)行特征選擇,并且都沒有考慮特征的冗余性,所選出的特征具有很大的冗余性。對此,Wang等[16]于2015年提出了一種基于全局冗余最小化的特征選擇框架(Feature selection via global redundancy minimization,GRM)。進(jìn)一步地,Nie等[17]于2019年提出了一種基于全局冗余最小化的自動加權(quán)特征選擇框架(General framework for auto-weighted feature selection via global redun-dancy minimization,AGRM)。這兩個框架都能夠選擇出不冗余的特征,既適用于有監(jiān)督特征選擇方法,也適用于無監(jiān)督特征選擇方法。

另外,在以往的無監(jiān)督特征選擇工作中發(fā)現(xiàn),對不同數(shù)據(jù)集進(jìn)行降維,選擇特征的能力是不同的,甚至有很大差異。數(shù)據(jù)的準(zhǔn)確與否會對所選擇的特征產(chǎn)生很大影響,提出的模型抗干擾能力差,性能極易受到個別異常點的破壞。為此,研究者們從不同的維度提出了一系列的解決辦法,包括自步學(xué)習(xí)、魯棒學(xué)習(xí)等。

(1)自步學(xué)習(xí)。

自步學(xué)習(xí)是近年來被提出的一種學(xué)習(xí)策略,它從簡單到復(fù)雜逐步增加訓(xùn)練實例,可以典型地降低局部最優(yōu)的風(fēng)險?；诰垲惾蝿?wù)現(xiàn)存的一些問題,如聚類結(jié)果很容易陷入局部最優(yōu)、聚類結(jié)果容易受到少量異常值的影響、聚類結(jié)果對初始參數(shù)非常敏感等,很多研究者發(fā)現(xiàn),通過加入自步學(xué)習(xí)框架可以大大緩解此類問題。具體地,Yu等[18]于2020年提出了一種基于自步學(xué)習(xí)的K-means聚類算法。其核心思想是通過自步學(xué)習(xí)方法來模擬人類學(xué)習(xí)知識的過程,即從易到難地學(xué)習(xí)知識。該方法首先使用一個自步正則化因子來選擇樣本的一個特定子集加入訓(xùn)練,然后自動調(diào)整自步學(xué)習(xí)的參數(shù)逐步地增加樣本的數(shù)量和難度,從而逐漸提高聚類模型的性能和泛化能力。

(2)魯棒學(xué)習(xí)。

為了克服異常點對模型的影響,增強(qiáng)算法的穩(wěn)定性,研究者們針對聚類任務(wù)提出了許多魯棒的算法[19,20]。這些方法大致可歸為兩類:一類是基于懲罰正則化的方法,另一類是基于裁剪函數(shù)的方法。Georgogiannis于2016年通過借鑒回歸中離群點檢測的思想,提出了一個經(jīng)典二次K-均值算法的變量魯棒性和一致性的理論分析——魯棒K-means[21]。在這項工作中,Georgogiannis發(fā)現(xiàn),一個數(shù)據(jù)集中的兩個離群值足以分解這個聚類過程。然而,如果關(guān)注的是“結(jié)構(gòu)良好的”數(shù)據(jù)集,那么盡管有離群值,魯棒K-means最終還是可以恢復(fù)底層的集群結(jié)構(gòu)。

可以看出,針對數(shù)據(jù)集中的離群點,為了降低其對模型性能的影響,研究者們都是努力地提升模型的穩(wěn)定性,不可否認(rèn)的是,這種做法確實能緩解離群點對模型整體性能的破壞,但是,正如Georgogiannis在魯棒K-means的工作中所提出的,對于“結(jié)構(gòu)良好的”數(shù)據(jù)集,魯棒K-means可以克服離群值的影響,恢復(fù)數(shù)據(jù)的底層集群結(jié)構(gòu),而對于某些數(shù)據(jù)集,這個數(shù)據(jù)集中的兩個離群值足以破壞整個聚類過程,這足以說明對于一個“非結(jié)構(gòu)良好的”數(shù)據(jù)集,離群值的破壞力很大。

為此,本文從兩方面來提高聚類的準(zhǔn)確性。一方面,采用區(qū)間的方式對數(shù)據(jù)進(jìn)行近似,相較于直接使用某個樣本自身的信息,本文采用其鄰近的幾個樣本來刻畫這個樣本,這樣可以有效地降低離群點的影響。另一方面,基于上述產(chǎn)生的多種數(shù)據(jù)表示,提出了一種新的模型——基于鄰域區(qū)間擾動融合的無監(jiān)督特征選擇算法框架(Unsupervised feature selection algorithm framework based on neighborhood interval disturbance fusion,NIDF)。此模型可實現(xiàn)對特征的最終得分和近似數(shù)據(jù)區(qū)間的聯(lián)合學(xué)習(xí),最終達(dá)到一個不錯的聚類效果。

2 研究方法

2.1 方法的提出

圖1 算法過程示意圖

NIDF模型如下

(1)

式中:Ai∈Rd×d是一個冗余矩陣,用來刻畫第i個近似數(shù)據(jù)集上所有特征間的冗余性;si∈Rd×1代表的是對第i個近似數(shù)據(jù)集進(jìn)行無監(jiān)督特征選擇后得到的特征分?jǐn)?shù);wi代表的是第i個近似數(shù)據(jù)集的權(quán)重;λ是一個自動加權(quán)的參數(shù),用來平衡第一項和第二項;z∈Rd×1是利用式(1)聯(lián)合學(xué)習(xí)特征選擇和近似的數(shù)據(jù)區(qū)間后得出的最終特征分?jǐn)?shù)。

2.2 方法的優(yōu)化

式(1)可通過迭代地更新λ、z、w來求解,詳細(xì)過程如下。

(1)固定z和w,更新λ。則式(1)可等價于求解以下問題

(2)

對于式(2),通過求其關(guān)于λ的導(dǎo)數(shù),并令其等于0,則可求出

(3)

(2)固定λ和w,更新z。則式(1)可等價于求解以下問題

(4)

很明顯,上述問題是一個帶有線性約束的凸二次規(guī)劃問題,該問題可用現(xiàn)有的優(yōu)化工具輕松解決。

(3)固定λ和z,更新w。則式(1)可等價于求解以下問題

(5)

這里,引入矩陣H∈Rd×d,f∈Rd×1,其中H是一個對角矩陣,其主對角線元素為Hii=zTAiz,矩陣f中的元素為fi=zTsi。則式(5)可被重寫為

(6)

同樣,這是一個帶有線性約束的凸二次規(guī)劃問題,可用現(xiàn)有的優(yōu)化工具解決。

總體來說,式(1)的解法如算法1所示。另外,整個NIDF模型的過程總結(jié)在算法2中。

算法1式(1)的優(yōu)化解法

初始化:z,w;

重復(fù):

1.更新λ通過式(3);

2.更新z通過解決式(4);

3.更新w通過解決式(6);

直到λ收斂。

輸出:z

算法2NIDF模型的過程

輸入:數(shù)據(jù)集X,樣本標(biāo)簽Y,所選特征數(shù)m;

步驟:

3.利用算法1求解NIDF模型,實現(xiàn)對特征選擇和近似的數(shù)據(jù)區(qū)間聯(lián)合學(xué)習(xí),得出最終的特征分?jǐn)?shù)z;

4.對特征分?jǐn)?shù)z進(jìn)行降序排序,并選出其前m個特征。

輸出:選出前m個特征。

3 實驗

本節(jié)通過在8個公開的數(shù)據(jù)集上進(jìn)行實驗,驗證本文所提模型的有效性。

3.1 數(shù)據(jù)集

在實驗中,本文使用了多種數(shù)據(jù)集,包括2個文本數(shù)據(jù)集,4個圖像數(shù)據(jù)集,1個生物數(shù)據(jù)集,1個其他數(shù)據(jù)集,這些數(shù)據(jù)集都是進(jìn)行特征選擇的常用數(shù)據(jù)集,數(shù)據(jù)集的大小如表1所示。

表1 數(shù)據(jù)集的大小

3.2 實驗對比算法

提出的模型作為一個后處理過程,可用于無監(jiān)督特征選擇方法中,這里使用了3個現(xiàn)有的無監(jiān)督特征選擇方法:拉普拉斯算法(LapScore)、多類簇特征選擇算法(MCFS)和基于圖結(jié)構(gòu)的Kullback-Leibler(KL)散度最小化算法(Gragh-based Kullback-Leibler divergence minimization for unsupervised selection,KLMFS)。

另外,GRM和AGRM框架也可用于無監(jiān)督特征選擇中的后處理過程,此處將這兩個框架應(yīng)用于已有的無監(jiān)督特征選擇方法,可以得出以下幾組對比算法。

(1)第一組。

LapScore[14]:基于原始數(shù)據(jù)集,利用拉普拉斯特征選擇算法進(jìn)行特征選擇。

LapScore_GRM[16]:基于原始數(shù)據(jù)集,將GRM框架應(yīng)用于拉普拉斯特征選擇算法中進(jìn)行特征選擇。

LapScore_AGRM[17]:基于原始數(shù)據(jù)集,將AGRM框架應(yīng)用于拉普拉斯特征選擇算法中進(jìn)行特征選擇。

LapScore_NIDF:新提出的方法,基于構(gòu)建的區(qū)間近似數(shù)據(jù)集,將NIDF框架應(yīng)用于拉普拉斯特征選擇算法中進(jìn)行特征選擇。

(2)第二組。

MCFS[15]:基于原始數(shù)據(jù)集,利用多類簇特征選擇算法進(jìn)行特征選擇。

MCFS_GRM:基于原始數(shù)據(jù)集,將GRM框架應(yīng)用于多類簇特征選擇算法中進(jìn)行特征選擇。

MCFS_AGRM:基于原始數(shù)據(jù)集,將AGRM框架應(yīng)用于多類簇特征選擇算法中進(jìn)行特征選擇。

MCFS_NIDF:新提出的方法,基于構(gòu)建的區(qū)間近似數(shù)據(jù)集,將NIDF框架應(yīng)用于多類簇特征選擇算法中進(jìn)行特征選擇。

(3)第三組。

KLMFS[22]:基于原始數(shù)據(jù)集,利用KL散度最小化算法進(jìn)行特征選擇。

KLMFS_GRM:基于原始數(shù)據(jù)集,將GRM框架應(yīng)用于KL散度最小化算法中進(jìn)行特征選擇。

KLMFS_AGRM:基于原始數(shù)據(jù)集,將AGRM框架應(yīng)用于KL散度最小化算法中進(jìn)行特征選擇。

KLMFS_NIDF:新提出的方法,基于構(gòu)建的區(qū)間近似數(shù)據(jù)集,將NIDF框架應(yīng)用于KL散度最小化算法中進(jìn)行特征選擇。

3.3 評價指標(biāo)

在實驗中,使用了聚類方法常用的兩個評價指標(biāo)來評估方法的性能,即聚類準(zhǔn)確性(Accuracy,ACC)和歸一化互信息(Normalized mutual information,NMI)。這兩個指標(biāo)的值越大,表示聚類性能越好。

聚類準(zhǔn)確性:聚類準(zhǔn)確性主要是用來刻畫所聚的類和樣本原始類之間的一對一關(guān)系。給定一個樣本點xi,pi和qi分別用來表示聚類結(jié)果和樣本的真實標(biāo)簽,則ACC為

式中:n是樣本數(shù),δ(x,y)是一個這樣的函數(shù),若x=y,δ(x,y)的值為1,否則為0。map(·)是一個置換函數(shù),將每一個簇索引映射到一個真實的類標(biāo)簽中。

歸一化互信息:歸一化互信息主要是用來刻畫聚類的質(zhì)量。記C是真實類標(biāo)簽的集合,C′是通過聚類算法計算的類集合,則它們的互信息MI(C,C′)為

式中:p(ci)和p(c′j)分別是從數(shù)據(jù)集中任意選定的一個樣本點屬于類ci和c′j的概率,p(ci,c′j)是這個數(shù)據(jù)點同時屬于這兩個類的概率。實驗中,使用的歸一化互信息NMI為

式中:H(C)和H(C′)分別是C和C′的熵。

3.4 實驗結(jié)果分析

本文進(jìn)行了多組實驗,以驗證所提模型的有效性。

圖2 原始數(shù)據(jù)集和區(qū)間近似數(shù)據(jù)集上LapScore的特征選擇效果

其次,針對區(qū)間近似數(shù)據(jù)集對特征選擇的不穩(wěn)定影響,包括積極的和消極的,本文聯(lián)合學(xué)習(xí)區(qū)間近似數(shù)據(jù)集和特征選擇——NIDF模型。這里同樣以PIE數(shù)據(jù)集中的第一個樣本圖像進(jìn)行LapScore特征選擇為例。在這組實驗中,本文以原始的LapScore特征選擇方法、經(jīng)GRM和AGRM處理過的LapScore_GRM和LapScore_AGRM方法作為對比,實驗得出,經(jīng)本文提出的NIDF處理后的LapScore_NIDF能一定程度上提高特征選擇的效果。直觀的特征選擇效果如圖3所示,從圖中可以看出,經(jīng)NIDF處理后的LapScore_NIDF選擇出的特征更集中,更具有代表性。

圖3 3種框架基于LapScore的特征選擇效果

最后,通過在大批量的數(shù)據(jù)集上分別進(jìn)行3組對比算法的特征選擇能力測試,可以看出本文提出的模型能一定程度上提高無監(jiān)督特征選擇方法的性能,聚類結(jié)果分別如表2和表3所示,其中最好的結(jié)果加粗表示,次好的結(jié)果加下劃線表示。另外,3組算法在不同數(shù)據(jù)集上ACC值的直觀展示如圖4所示。

圖4 不同數(shù)據(jù)集上ACC值的直觀展示

通過分析可以得出,經(jīng)本文提出的NIDF模型處理后,LapScore_NIDF、MCFS_NIDF以及KLMFS_NIDF相比較于原始的LapScore、MCFS和KLMFS方法,在準(zhǔn)確性ACC上分別能提高將近17.51%、15.26%和10.50%。然而,由圖4可以直觀看出,本文提出的NIDF模型并不能絕對優(yōu)于現(xiàn)有的GRM和AGRM框架,但是從總體上看,經(jīng)本文提出的NIDF模型處理后的新方法,相比較于經(jīng)GRM和AGRM處理后方法的平均值,在準(zhǔn)確性ACC上分別能提高將近7.40%、5.41%和8.16%。

總的來說,盡管本文提出的NIDF模型不能絕對優(yōu)于現(xiàn)有的GRM和AGRM框架,但是在大多數(shù)情況下可以達(dá)到比這兩個框架更好的效果,少數(shù)情況下效果相差無幾。另外,本文提出的NIDF作為一個后處理框架,相比較于原始的無監(jiān)督特征選擇方法,可以達(dá)到對其性能的進(jìn)一步提升,因此有一定的實用意義。

3.5 參數(shù)設(shè)置

在求數(shù)據(jù)集的近似區(qū)間數(shù)據(jù)集時,涉及到鄰域k和參數(shù)alpha,這里設(shè)置的鄰域數(shù)k是15,alpha是3。由于K-means聚類的結(jié)果受初始值影響較大,故本文在每一次評估算法性能時重復(fù)進(jìn)行K-means聚類20次,最終給出平均值。本文在利用所選特征評估算法性能時,所選擇的特征數(shù)集合是[10:10:100],最終取所有結(jié)果的平均數(shù)。

4 結(jié)束語

本文首先采用區(qū)間的方式對數(shù)據(jù)集進(jìn)行近似。將一個數(shù)據(jù)集表示成與其相關(guān)幾個數(shù)據(jù)集的組合,然后基于上述得到的多種數(shù)據(jù)表示,本文通過實驗驗證了其優(yōu)劣性,并思考從全局角度對這些數(shù)據(jù)集進(jìn)行處理,進(jìn)而提出了一種新的模型——基于鄰域區(qū)間擾動融合的無監(jiān)督特征選擇算法框架NIDF。實驗證明,通過對特征的最終得分和區(qū)間近似數(shù)據(jù)集的聯(lián)合學(xué)習(xí),該模型能一定程度上提高原始特征選擇方法的性能,并且在大多數(shù)情況下優(yōu)于現(xiàn)有的兩個后處理框架GRM和AGRM。