基于改進ReliefF的無監督特征選擇方法①

丁雪梅, 王漢軍, 王炤光, 周心圓

1(中國科學院 沈陽計算技術研究所,沈陽 110168)

2(中國科學院大學,北京 100049)

3(國家電網公司東北分部,沈陽 110180)

4(吉林大學 計算機科學與技術學院,長春 130000)

特征選擇是指從原始特征集中選出一個使得評估標準達到最優的特征子集的過程[1]. 對于一個概念學習問題,優秀的學習樣本是訓練分類器的關鍵,樣本中的不相關或冗余特征會使學習算法陷入混亂導致分類器過擬合[2],影響訓練性能. 因此有效的特征選擇對于加速學習速度和提高概念質量具有重要作用.

特征選擇根據是否包含類別信息分為有監督的特征選擇和無監督的特征選擇. 無監督特征選擇的目的是根據一定的評判標準,選擇出一個足夠簡練又能夠充分描繪原始特征集的重要特性同時保障數據集原生分類性的特征子集. 針對無監督特征選擇,已經提出了一些方法,根據是否于后續的學習方法相關,可分為過濾式(Filter) 和封裝式(Wrapper)兩種[3]. Filter模型獨立于學習算法,利用所有訓練數據的統計性能,選取相關性評價準則進行特征評估. 文獻[4]引入核空間距離測度,通過計算兩類樣本點在核空間的距離度量相關性,有效提高了線性不可分數據的特征選擇能力. 文獻[5]采用互信息來度量相關性,以此達到無監督最小冗余最大相關(UmRMR)的特征選擇的標準. 文獻[6]使用拉普拉斯分值評價特征的重要程度,以極大程度保留原始特征集和整體幾何結構信息為原則選擇分值較小的部分特征形成特征子集. Tabakhi S[7]以特征作為結點,特征間余弦相似度作為邊的權值建立圖模型; 使用蟻群算法,引入信息素的概念啟發式搜索相似度最小的路徑,所歷結點形成最終特征子集. 然而以上過濾式方法單純以數據本身的統計信息或關系作為依據進行特征選擇,沒有考慮特征對于數據原生性分類的影響.特征選擇知識理論中分類性能也可作為所選特征子集的度量標準. 在Wrapper模型中,特征選擇算法與學習算法耦合在一起,利用學習算法的分類準確率評估特征子集. 針對無監督問題則是以特定聚類算法的聚類結果的質量來估量特征子集. 例如Yuan等人[8]對數據域進行特征聚類,然后通過構建熵測度來揭示不同特征子集的最優值以此評估該特征子集的重要性.Zhu等人[9]提出了一種子空間聚類指導特征選擇的方法,該方法維持并迭代更新一個特征選擇矩陣,矩陣的列向量反饋每個子空間聚類的代表性特征. 但是該類方法計算量大,時間復雜度較高,無法適用于大規模數據的特征選擇.

ReliefF是公認的效果較好的過濾式(Filter)特征評估方法[10],不同于上述過濾式方法,ReliefF利用特征對于分類的影響來評估特征權重,同時對數據類型沒有限制,運行效率高,能夠應對大規模的數據. 針對其易忽略小類樣本、不能削減冗余特征等不足,本文提出了一種基于改進ReliefF的無監督特征選擇算法(UFS-IR),繼承ReliefF優點的同時特征選擇結果更可靠、更準確,獲得符合UmRMR標準的特征子集.

1 無監督特征選擇

無監督特征選擇是指按照某一評價準則從原始高維特征集中篩選出部分特征形成最優特征子集,使它對原始數據的自然分類效果的影響足夠小或者沒有.

定義已知包含n個特征X1,X2,…,Xn的數據集D,其中Xi=(S1,S2,S3,…,Sk),k∈N*(非零自然數); 給定方法Method,按照某一準則J評價各個特征Xi,篩選出其中部分特征Xi,Xj,…,Xm(1≤i,j,m≤n且i,j,m∈N*)獲取最終的特征子集.

2 改進ReliefF算法

2.1 ReliefF算法

Relief系列算法一種高效的過濾式特征選擇方法,最早于1992年由Kira和Rendell提出用于二分類問題的特征選擇算法[11]. 1994年Kononenko對Relief進行分析和擴展,使得ReliefF能夠用來處理噪聲、不完整和多類數據集[12].

ReliefF基于特征對各個類的近距離樣本的區分能力,賦予特征不同的權重來評估特征,特征權值越大意味著它更有助于區分類別. 當特征與分類相關性極低時,特征的權值將足夠小接近0; 特征權值計算結果可能出現負值,表示同類近鄰樣本的距離比不同類近鄰樣本的距離大,這也意味著該特征對于分類的影響是負面的.

對于樣本集Q,每次從中隨機選擇一個樣本S,然后S的同類樣本集中尋找k個S的近鄰樣本NH,同時每個與S不同類別的樣本集中各尋找k個近鄰樣本NM. 迭代更新每個特征的權重ω(x),更新公式為：

式中,m表示迭代次數,NHj表示同類的第j個近鄰樣本,NM(C)j表示不同類的C類樣本的第j個近鄰樣本,P(C)表示第C類目標的概率,Class(S)表示樣本S所屬的類別,diff(X,S,S')表示樣本S和S'關于特征X的距離.

2.2 改進ReliefF算法

雖然ReliefF算法不限制數據類型為離散或是連續型,能應對多類別的數據,擁有較高的評估效率和有效性,但它仍存在以下不足.

(1) 算法隨機采樣的次數m將影響最終得出的各個特征的權值.

(2) 隨機采樣的策略使得小類樣本被選中的幾率很低甚至不被選中,如果忽略小類別樣本對更新特征權重的影響,那么最終的結果準確性和合理性是不可靠的.

(3) 隨機采樣可能存在重復抽樣的情況,重復抽樣的樣本將對特征權值的更新產生無意義的重復影響,使得有限抽樣次數內的有效抽樣率降低,從而降低了特征權值結果的有效性和可靠性.

(4) 算法得出的特征權值,只能評估特征對分類的貢獻值并不能幫助刪除冗余特征.

本文針對以上不足的(2)(3)(4)對ReliefF算法加以改善. 在抽樣的隨機性不變的前提下,控制每一類樣本被抽樣到的次數,以各類樣本占所有有效樣本的比例ξ設置每一類樣本被抽樣的次數ξm,彌補ReliefF算法隨機選樣時小類別樣本被選中概率低的不足. 同時控制每一次抽樣的樣本不是重復抽樣,總是對特征權值更新賦予新的影響,充分發揮數據集在有限次數內對特征評估的效用. 針對ReliefF算法無法刪除冗余特征,引進調整的余弦相似度來衡量特征間的相關性,結合特征評估結果去除相關特征對中的一個元素.

2.3 調整的余弦相似度

余弦相似度通過計算兩個向量的夾角余弦值來評估他們的相似度. 余弦值的范圍在[-1,1]之間,值越趨近于1,代表兩個向量的方向越接近越相似; 越趨近于-1,他們的方向越相反; 接近于0,表示兩個向量近乎于正交.

向量X=(X1,X2,…,Xn)和Y=(Y1,Y2,…,Yn)的余弦相似度為：

余弦相似度衡量的是空間向量的夾角,僅僅從方向上區分向量的差異,而對絕對數值不敏感,向量數值的成比例縮放不改變余弦相似度計算結果. 余弦相似度對數值的不敏感導致了結果的誤差,調整的余弦相似度ACS修正了這種不合理性,在向量所有維度上的數值Xi都減去一個均值[13],也使得衡量向量的相似性轉變為衡量相關性.

向量X=(X1,X2,…,Xn)和向量Y=(Y1,Y2,…,Yn)的調整余弦相似度為：

3 算法設計

3.1 基礎算法

傳統ReliefF算法的設計是針對于有監督的特征選擇,數據的類別信息是算法的主要支撐. 引入ReliefF算法進行無監督特征選擇的首要任務就是獲知數據類別. 聚類是將樣本觀測值,數據項或特征向量劃分成簇的無監督分類模式[14],能夠完成對無監督樣本的分類. DBSCAN是一種基于密度聚類算法的典型代表,它能夠把具有足夠密度的區域劃分為簇,聚類速度快,對聚類簇的形狀毫無偏倚,能夠在具有噪聲的空間數據庫中發現任意形狀的簇,同時有效處理噪聲數據防止對有效樣本形成的評估結果產生干擾. 因此本文以DBSCAN聚類結果形成的簇定義數據的類別,以此支撐UFS-IR算法.

DBSCAN定義參數eps來表示每個對象的鄰域半徑,對象o的eps鄰域是以o為中心、以eps為半徑的空間. 鄰域的大小由參數eps確定,鄰域的密度用鄰域內的對象數度量. 通過另一參數minPts,即指定稠密區域的密度閾值,來衡量鄰域是否稠密. 如果一個對象的eps鄰域至少包含minPts個對象,則稱該對象為核心對象. 通過連接核心對象及其鄰域內其他核心對象的鄰域,形成稠密區域作為簇.

算法1. DBSCAN

輸入： 數據集D,半徑eps,核心點鄰域內點最少數目

輸出： 所有簇集合

1. 標記D中每一個點為unvisited

2. for eachainD

3. if (aisunvisited)

4. if (ois not核心點) 標記點o為噪音;

5. else //ais核心點

6. 點o及其鄰域E內的所有點形成一個新簇C;

7. for (eachpina的鄰域)

8. if (pisunvisited)

9. if (pis核心點)

10. 將點p的鄰域內的所有點加入簇C;

11. else

12. if (p沒有加入其它任何一個簇)

13. 將p加入簇C;

14. if (p被標記為噪音) 取消標記p為噪音;

15. end

3.2 基于改進ReliefF的無監督特征選擇算法UFS-IR

UFS-IR (Unsupervised Feature Selection based on Improved ReliefF)算法通過DBSCAN聚類算法給樣本標注聚類標簽來指定樣本數據的類別,為將ReliefF算法應用到無監督特征選擇提供數據基礎. 采用DB INDEX (Davies Bouldin index,DBI)準則來判斷DBSCAN聚類的有效性,選擇DBI值較小的一組(eps,minPts)參數對數據進行聚類. 使用不同采樣策略控制每個類別樣本被抽樣總次數ξm,確保m次抽樣中不出現重復抽取樣本,彌補ReliefF算法隨機選樣時小類別樣本對更新特征權重的影響容易被忽略這一不足的同時充分發揮每一次采樣對特征評估的效用. 至此改進的ReliefF算法得到分類相關的特征集合T保證最終得到的特征子集F的最大相關性,但是它仍舊無法保證特征子集內部的低冗余度,在對含有類別信息的數據處理時有些學者使用分類器的正確率來篩選特征[15,16],但是無法適用無監督特征選擇中. 所以本文改進ReliefF使用ACS系數來衡量特征間的相關性,結合集合T保留強相關特征對中權值較大的特征來保障F的最小冗余性.

UFS-IR算法描述如下：

定義已知包含n個特征X1,X2,…,Xn的數據集D,其中Xi=(S1,S2,S3,…,Sk); 使用聚類算法DBSCAN,分別為D中k個樣本劃分類別指定標簽Y,使用改進ReliefF評價各個特征Xi對于這種分類的影響,計算ACS(Xi,Xj)衡量特征間的相關性,削減特征子集的冗余度,獲取最終特征子集.

輸入： 樣本數據集D,迭代次數n,鄰域半徑eps,樣本閾值minPts,抽樣次數m,最近鄰樣本的個數k,ACS閾值λ

輸出： 最優特征子集

1. 初始化所有特征的權值為0,標記所有樣本點為unvisited

2. 使用DBSCAN算法處理D,計算本次聚類的DBI

3. fori=2 ton

4. 調整(eps,minPts),計算DBI2

5. if (DBI2＜DBI)DBI=DBI2并記錄當前(eps,minPts)

6. 以最終(eps,minPts)作為DBSCAN的參數對D進行聚類,標記聚類結果,刪除噪音得到數據集D'

7. 初始化每個聚類簇在m次抽樣中被抽中的次數n=ξm,其中ξ為各聚類簇樣本占D'中總樣本數的比例

8. fori=1 tom

9. 從D’中隨機抽取一個標記為unvisited的樣本R;

10. 判斷R所屬類別允許抽中次數的剩余值n是否等于0;

11. if (R所屬類別的n==0) 回到(5);

12. else將R標記為visited;

13. 從R的同簇樣本集中尋找k個最近鄰樣本NHj(j=1,2,…,k),從R的每一個不同簇樣本集中尋找k個最近鄰樣本NM(C)j(j=1,2,…,k);

14. forX=1 toN//N為特征總數

15. 根據公式(1)更新特征權值;

16. 刪除權值為負數或小于非負權值的均值的特征,將剩余特征按權值降序排列得到集合T;

17. 基于D,一個特征的所有值形成一個向量,計算T中特征兩兩間的ACS系數;

18. 保留值大于等于閾值λ的特征對pairs集合Q;

19. for eachpairsinQ

20. if (pairs中的元素都在T中)

21. 保留權值較大的特征Y;

22. if(F不包含Y) 將Y加入集合F;

23. 輸出F,得到最優特征子集;

24. end

4 實驗分析

4.1 實驗數據

為了體現算法的有效性,實驗選擇了如表1所示來自UCI (University of California Irvin)機器學習數據庫和多倫多大學Delve Datasets的四個不同規模數據集,數據質量較高基本無量綱的影響. 使用支持向量機SVM對特征選擇后的數據進行分類,以分類正確率來驗證算法的有效性,使用10折交叉驗證的結果作為最終分類正確率.

表1 數據集介紹

4.2 參數的設置

UFS-IR算法涉及眾多參數,其中影響算法性能的主要包括ReliefF中的抽樣次數m和DBSCAN中的鄰域半徑eps、樣本閾值minPts. 如2.2節所述參數m將影響最終得出的各個特征的權值,理論上而言m的值增加,算法將獲得更多數據本身的結構信息或統計信息等,使得特征評估結果更準確. 事實上也是如此,實驗改變對satimage數據集的抽樣次數m,當m=100時,UFS-IR-Accuracy為 0.895; 當m=200時,UFS-IRAccuracy為0.922,當m=300時,UFS-IR-Accuracy為0.931. 分類正確率隨m的增加而增加,但同時運行時間也在增加. 出于實驗目的是驗證UFS-IR對ReliefF算法如2.2節所述其他三點的改進可行性和有效性,本文對于參數m以保障最終分類結果優良,運行時間精煉為原則適當選擇.

DBSCAN對輸入參數(eps,minPts)敏感,若參數選擇不當將造成聚類質量下降,并最終影響對特征評估的準確性. DBSCAN參數的選擇通常依賴于經驗,但當數據內部結構較復雜時,事先確定合適參數值是比較困難的. 針對這種情況,在聚類過程中使用DB INDEX評價聚類結果,并以此為依據適當調整參數.以satimage數據集的測試集為例,設置調整次數n=10(n是一個與聚類結果無關的變量,其值可適當調整)分析不同(eps,minPts)參數值相應的DB INDEX值以及最終使用UFS-IR算法的分類正確率,如表2所示DB INDEX對不同參數下聚類效果的評價值越低,對特征選擇的影響更積極使得相應的分類正確率更高,說明使用DB INDEX方法來確定聚類的參數是有效準確的.

表2 DBSCAN聚類評估情況

4.3 實驗與結果分析

(1) 驗證抽樣策略和ACS有效性

以splice數據集為基礎,以原始類別信息作為類別標簽,對比分析ReliefF算法和改進抽樣策略的ReliefF算法對各特征的評估情況如圖1所示.

圖1 ReliefF和改進ReliefF對splice中60個特征的評估情況

圖1中,橫坐標代表splice的60個特征,縱坐標代表兩個算法對每個特征的評估值. 從圖1可以看出,改進的ReliefF對特征的評估各特征間的相對大小和整體趨勢與ReliefF的評估結果基本一致,因此改進ReliefF算法不會改變特征對于分類的影響因子. 改進抽樣策略的ReliefF對各特征的評估值明顯突出于ReliefF的評估結果,說明不重復抽樣充分發揮了每次抽樣樣本的使用價值,既定各類樣本的抽樣概率,也使得小類別樣本穩定發揮作用,增加了結果準確性和合理性的可靠程度,證明對ReliefF抽樣策略的改進是有效的.

ReliefF家族算法對所有特征進行評估計算相應的權重然后以降序排列,選擇排序后特征的相應比例作為特征子集. 以splice和satimage數據集的原始規模和類別信息分別訓練各自的SVM分類模型model,對比分析使用ReliefF,改進的ReliefF以及改進的ReliefF結合ACS三種方法后,model對不同維度的數據集的分類正確率.

圖2和圖3中縱坐標表示特征維度,即ReliefF體系算法對所有特征排序之后選取前百分之多少構成最終特征選擇子集,橫坐標表示分類正確率. 可以看出改進的ReliefF相比ReliefF算法分類率有所提高,使用ACS刪除冗余特征后,分類率的提高更加明顯.實驗說明改進的抽樣策略和ACS的使用是有效的、可靠的.

圖2 Splice數據集各維度分類正確率

圖3 Satimage數據集各維度分類正確率

(2) 驗證UFS-IR的有效性

UFS-IR算法對原始數據集的特征有兩個刪減過程,第1次是在完成改進ReliefF算法之后,刪除特征評估權重為負值的特征,負值意味著該特征對于分類具備消極影響. 第2次是使用ACS對特征間相關性進行衡量,刪減大于閾值λ特征對中特征評估權重較小的特征. 本文設定的閾值λ為0.75,相關性系數不小于0.75表示兩個特征是顯著相關關系. 圖4展示了各數據集原始特征維度Original,第1次刪減后特征維度First-cut以及第2次刪減后特征維度Second-cut的情況. 從圖4可以看出,UFS-IR顯著刪減了原始數據集中的特征數,使得最終特征子集符合最大相關最小冗余準則.

圖4 UFS-IR特征選擇前后維度對比

以各數據集的原始規模和類別信息分別訓練各自的SVM分類模型model,并得到對原始數據集的分類正確率Accuracy. 為驗證UFS-IR的有效性,忽略原始數據的類別信息作為UFS-IR的實驗數據集. DBSCAN聚類迭代n=10次,選擇DB INDEX值較小的一組(eps,minPts)參數對數據進行聚類,并以聚類結果指定數據的類別信息. 用與model相同的參數對UFS-IR特征選擇后數據集進行訓練和測試,得到分類正確率UFS-IR-Accuracy. 如表3所示4個不同數據集的UFSIR- Accuracy值明顯大于Accuracy,實驗證明本文提出的UFS-IR無監督特征選擇方法是合理的、有效的.

表3 特征選擇前后分類正確率

5 結論與展望

本文首先分析了無監督特征選擇的基礎體系,然后介紹了ReliefF算法并對其不足進行分析,基于此提出改進方案. 本文將DBSCAN與改進ReliefF加以融合,提出了基于改進ReliefF的無監督特征選擇方法UFS-IR,構成無監督特征選擇的基本結構體系. 實驗結果證明,使用DB INDEX準則判定DBSCAN有效性并確定參數的方法是有效的,這也使得DBSCAN指導分類更加準確和可靠,抽樣策略的改進使得特征評估的結果更加可信和合理,調整的余弦相似度有效解決了改進ReliefF算法無法辨識冗余特征的不足,方法間優勢互補更提高了UFS-IR的有效性和可靠性.UFS-IR涉及眾多參數,選擇更快速有效的方法確定DBSCAN的參數,研究改進ReliefF中的參數m對特征評估的影響以及參數m的選擇策略或準則是今后工作的重點.

1Liu H,Yu L. Toward integrating feature selection algorithms for classification and clustering. IEEE Transactions on Knowledge and Data Engineering,2005,17(4)： 491-502.

2Yu L,Liu H. Efficient feature selection via analysis of relevance and redundancy. The Journal of Machine Learning Research,2004,5(12)： 1205-1224.

3姚旭,王曉丹,張玉璽,等. 特征選擇方法綜述. 控制與決策,2012,27(2)： 161-166,192.

4蔡哲元,余建國,李先鵬,等. 基于核空間距離測度的特征選擇. 模式識別與人工智能,2010,23(2)： 235-240.

5徐峻嶺,周毓明,陳林,等. 基于互信息的無監督特征選擇.計算機研究與發展,2012,49(2)： 372-382.

6歐璐,于德介. 基于拉普拉斯分值和模糊C均值聚類的滾動軸承故障診斷. 中國機械工程,2014,25(10)： 1352-1357.[doi： 10.3969/j.issn.1004-132X.2014.10.015]

7Tabakhi S,Moradi P,Akhlaghian F. An unsupervised feature selection algorithm based on ant colony optimization.Engineering Applications of Artificial Intelligence,2014,(32)： 112-123. [doi： 10.1016/j.engappai.2014.03.007]

8Yuan HN,Wang SL,Li Y,et al. Feature selection with data field. Chinese Journal of Electronics,2014,23(4)： 661-665.

9Zhu PF,Zhu WC,Hu QH,et al. Subspace clustering guided unsupervised feature selection. Pattern Recognition,2017,(66)： 364-374. [doi： 10.1016/j.patcog.2017.01.016]

10張麗新,王家廞,趙雁南,等. 基于Relief的組合式特征選擇. 復旦學報 (自然科學版),2004,43(5)： 893-898.

11Kira K,Rendell LA. The feature selection problem：Traditional methods and a new algorithm. Proceedings of 10th National Conference on Artificial Intelligence. San Jose,CA,USA. 1992. 129-134.

12Kononenko I. Estimating attributes： Analysis and extensions of RELIEF. Proceedings of the European Conference on Machine Learning. Catania,Italy. 1994. 171-182.

13Sarwar B,Karypis G,Konstan J,et al. Item-based collaborative filtering recommendation algorithms.Proceedings of the 10th International Conference on World Wide Web. Hong Kong,China. 2001. 285-295.

14Jain AK,Murty MN,Flynn PJ. Data clustering： A review.ACM Computing Surveys,1999,31(3)： 264-323. [doi： 10.1145/331499.331504]

15譚臺哲,梁應毅,劉富春. 一種ReliefF特征估計方法在無監督流形學習中的應用. 山東大學學報(工學版),2010,40(5)： 66-71.

16劉杰,金弟,杜惠君,等. 一種新的混合特征選擇方法RRK.吉林大學學報(工學版),2009,39(2)： 419-423.