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

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

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

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

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

1 相關工作

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

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

(1)自步學習。

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

(2)魯棒學習。

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

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

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

2 研究方法

2.1 方法的提出

圖1 算法過程示意圖

NIDF模型如下

(1)

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

2.2 方法的優(yōu)化

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

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

(2)

對于式(2),通過求其關于λ的導數,并令其等于0,則可求出

(3)

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

(4)

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

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

(5)

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

(6)

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

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

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

初始化:z,w;

重復:

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

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

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

直到λ收斂。

輸出:z

算法2NIDF模型的過程

輸入:數據集X,樣本標簽Y,所選特征數m;

步驟:

3.利用算法1求解NIDF模型,實現對特征選擇和近似的數據區(qū)間聯合學習,得出最終的特征分數z;

4.對特征分數z進行降序排序,并選出其前m個特征。

輸出:選出前m個特征。

3 實驗

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

3.1 數據集

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

表1 數據集的大小

3.2 實驗對比算法

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

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

(1)第一組。

LapScore[14]:基于原始數據集,利用拉普拉斯特征選擇算法進行特征選擇。

LapScore_GRM[16]:基于原始數據集,將GRM框架應用于拉普拉斯特征選擇算法中進行特征選擇。

LapScore_AGRM[17]:基于原始數據集,將AGRM框架應用于拉普拉斯特征選擇算法中進行特征選擇。

LapScore_NIDF:新提出的方法,基于構建的區(qū)間近似數據集,將NIDF框架應用于拉普拉斯特征選擇算法中進行特征選擇。

(2)第二組。

MCFS[15]:基于原始數據集,利用多類簇特征選擇算法進行特征選擇。

MCFS_GRM:基于原始數據集,將GRM框架應用于多類簇特征選擇算法中進行特征選擇。

MCFS_AGRM:基于原始數據集,將AGRM框架應用于多類簇特征選擇算法中進行特征選擇。

MCFS_NIDF:新提出的方法,基于構建的區(qū)間近似數據集,將NIDF框架應用于多類簇特征選擇算法中進行特征選擇。

(3)第三組。

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

KLMFS_GRM:基于原始數據集,將GRM框架應用于KL散度最小化算法中進行特征選擇。

KLMFS_AGRM:基于原始數據集,將AGRM框架應用于KL散度最小化算法中進行特征選擇。

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

3.3 評價指標

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

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

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

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

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

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

3.4 實驗結果分析

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

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

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

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

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

圖4 不同數據集上ACC值的直觀展示

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

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

3.5 參數設置

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

4 結束語

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