基于層次粒化的特征選擇算法

陳輝皇，　林耀進，　王晨曦，　童先群，　胡敏杰

(1.閩南師范大學 計算機學院　福建 漳州 363000；2.漳州職業技術學院 計算機工程系　福建 漳州 363000)

?

基于層次粒化的特征選擇算法

陳輝皇1，林耀進1，王晨曦2，童先群1，胡敏杰1

(1.閩南師范大學 計算機學院福建 漳州 363000；2.漳州職業技術學院 計算機工程系福建 漳州 363000)

許多實際應用問題中,特征空間存在著層次粒化結構.首先，提出基于核方法度量的層次聚類來對特征空間進行層次粒化.其次,在層次粒化后的各個子空間上,基于鄰域互信息考量特征和標記間最大相關以及特征與特征間最小冗余性,在某一指定的層次上對特征進行排序.在此基礎上,選擇各個子空間具有代表性的部分特征,組成最終的特征子集.最后,在6個UCI數據集和2個不同基分類器上的實驗表明所提算法的有效性.

特征選擇; 粒計算; 層次粒化; 互信息

0　引言

特征選擇是數據預處理中重要的步驟，通過刪除與決策目標無關的特征或冗余的特征，在不降低原始特征空間學習性能的條件下縮減特征集合的維數，有利于提高學習器的性能和效率，是數據挖掘與機器學習的關鍵問題之一[1-5].在面向圖像分類、太陽耀斑檢測、疾病診斷等各種分類應用中,樣本中是否存在不相關或冗余特征將影響分類器的性能.因此,通過一定策略進行特征選擇,可以有效地降低數據的特征維數，保持有差異性能力的特征[6-7],提高分類模型的泛化能力,且在一定程度上避免噪聲干擾.

目前,常用的特征選擇方法主要包含搜索策略和特征評價兩步驟.通常的搜索策略可分為前向啟發式搜索、后向啟發式搜索及全局隨機搜索等策略[2].一個好的評價準則通常能夠有效地評價特征的質量.常見的評價準則如下:距離度量[8]、依賴性度量[9]、一致性度量[10]和信息度量[11].其中,粒計算中基于粗糙集的依賴度度量由于模型簡單、能處理不確定信息及物理內涵明確,受到了廣泛的關注[1,9-10].

圖1　一個層次特征空間樣本Fig.1　The example of hierarchical feature space

迄今為止,已有很多學者利用粒計算方法從不同角度對特征選擇進行研究.文獻[12]提出了基于最大近鄰粗糙逼近的特征選擇算法.文獻[10]提出了鄰域多粒度融合的特征選擇算法.文獻[13]提出了基于鄰域軟邊緣的特征評估和選擇.但上述特征選擇算法只考慮“平面特征”選擇算法,即把特征看成相互獨立的平級特征,忽略了特征之間存在的層次化結構.在許多實際應用中,特征是存在著層次化結構的.如圖1所示,在疾病診斷中[14],如果一個病人要做血常規檢查,需要檢查紅細胞、白細胞、血小板.同時在紅細胞檢查中又能細劃分為紅細胞大小、紅細胞形態等檢查內容.

針對上述問題,本文提出了一種基于層次粒化的特征選擇算法.首先利用核函數來計算特征之間的相似性,進而得到特征之間的相似矩陣;其次對特征按照相似性進行層次聚類,從而得到一棵特征層次樹.這不僅保留了特征的層次結構，還使得特征也存在于非葉子節點中,即相同特征可以出現在不同層次上.在層次化的特征簇上，樹中同一節點的特征簇表明特征間有較大相關性，不同節點的特征簇中的特征有較大差異性.在指定的特征層次上針對每個節點特征簇,基于鄰域互信息按照特征與標記的相關性強弱進行特征排序,選出具有代表性的特征.最后,在6個UCI數據集和2個不同基分類器上的實驗表明所提算法的有效性.

綜上,本文分為4節:第1節介紹領域信息系統的基本概念;第2節提出了基于層次粒化的特征選擇模型;第3節驗證算法的性能及實驗結果;最后,總結全文.

1　鄰域系統的信息度量

基于Shannon的信息理論僅能夠處理離散型數據,文獻[15]將鄰域理論應用到信息熵中,提出了鄰域熵和鄰域互信息等概念,形成了鄰域近似空間的不確定性理論模型,

(1)

定義 1[16]設是非空度量空間, x∈U,δ≥0稱點集為x在度量空間的鄰域.該鄰域可以表示為以x為球心,半徑為δ的閉球.若度量函數Δ采用歐式距離時,則樣本x的鄰域是球心在x點，半徑為δ的超球體.

定義 2[16]給定論域U,集合C是用來描述U的條件屬性,而D是分類的決策屬性.將C生成一組論域上的鄰域關系R,稱NDT=為鄰域近似空間.

定義 3[16]給定論域空間U={x1,x2,…,xn},C是用來描述論域空間的特征集A?C,NA表示為特征子集A誘導的鄰域關系.則記xi在屬性A下計算得到的鄰域為δA(xi),那么鄰域粒子的不確定性為

(2)

相應地，鄰域近似空間的不確定性為

(3)

定義 4[16]A,B?C是刻畫論域的兩組特征集合, xi在A∪B的特征空間上的鄰域記δA∪B(xi) ,那么A和B的聯合熵可定義為

(4)

當A是輸入變量、C是決策屬性時,有δA∪B(xi)=δA(xi)∩cxi,此時有

(5)

定義 5[16]A,B?C是刻畫論域的兩組特征集合,A和B的鄰域互信息可定義為

(6)

2　基于層次粒化的特征選擇模型

2.1特征空間的層次粒化

本小節將介紹特征層次粒化的流程.首先,基于核函數度量特征之間的相似度獲得特征相似矩陣.

定義6給定兩個特征向量fi和fj,則fi和fj之間的相似值為

(7)

其中:該度量公式描述了兩個特征之間的相似性，而且該公式滿足自反性和對稱性,即Rij=Rji,Rii=1.

定義7給定兩個特征向量fi和fj,其中m代表特征集合維度.則利用特征與特征之間的相似值Rij得到特征與特征之間的相似矩陣,定義為

(8)

基于特征相似矩陣M,為了將原始特征空間進行層次聚類,借鑒一種有效的層次聚類算法.該算法類似于傳遞閉包方法,但不同于傳統的層次聚類算法.該算法將特征以樹型結構進行組織,每個樹節點表示一個特征簇,節點由高到低意味著特征簇中特征數量的增加及置信度的提高.算法1如下.

算法1特征空間層次聚類.

輸入: F為特征空間; n為特征空間維度; λ為置信度; Q為隊列;M為特征相似矩陣.

輸出:T為特征聚類.

while特征空間F不為空do

for特征空間F中的每個特征fido

T=?, 初始化隊列Q;

j=0;

whilej小于特征空間維度ndo

if特征fi,fj的相似性Rij大于置信度λandfj不屬于特征空間Fthen

T=T∪{fj} ,從隊列Q中刪除特征fj;

j=j+1;

endif

endwhile

if隊列Q為空then

輸出聚類結果T;

F=F-T;

endif

endfor

從隊列Q中溢出特征fi;

endwhile

圖2　一顆特征層次樹Fig.2　A tree of feature hierarchy

根據算法1，原始特征空間層次粒化為一顆特征層次樹，如圖2所示.

2.2節點特征簇內的特征選擇

通過算法1,可將特征的平面結構轉換為層次化結構.在此基礎上,本節將介紹在指定層次如何進行特征選擇.在特征層次樹上,在某一個指定的層次,節點特征簇內的特征表示具有較強的相關性,不同特征簇之間的特征表示具有描述樣本的多樣性.因此,接下來將利用最大相關性和最小冗余性策略對某一層次的特征進行排序.

定義8給定決策表(U,C,l),其中fi∈C,l為決策屬性,則特征fi與標記之間的相關性為

maxP(fi,l),P=NMIδ(fi,l)，

(9)

通過最大相關性可找到一個特征,使其滿足特征fi和標記l的相關性最大.P表示特征與標記的互信息,P值越大,表明特征fi跟標記l的相關性越大,特征和標記的關系越緊密.P值越小,特征和標記的關系越遠.

定義9 給定特征空間C,fi∈C,l是決策屬性,n代表特征空間維度的大小,則fi與其他特征的冗余性為：

(10)

依照最大相關策略得到的特征可能包含冗余，于是,當兩個特征間相依賴程度較高的時候,刪除其中的一個特征并不會使分類性能產生較大改變.因此,采用最小冗余策略來減少特征間的冗余.Q表示特征fi與其他特征之間的平均互信息.Q值越大,表明特征fi和其他特征之間的平均冗余越大. Q越小,表明特征fi和其他特征之間的平均冗余越小，

maxΦ(P,Q),Φ=P/Q.

(11)

基于啟發式的搜索策略能夠通過Φ(·)對特征質量進行評價.假定已經得到一個特征集合Sm-1,特征集合帶有m-1個特征.為了從集合{C-Sm-1}找到第m個特征，通過選擇當前特征滿足最大化Φ(·)，

(12)

依據此思想，在層次聚類得到了一棵層次特征樹后,在某一指定的層次基于層次樹葉子節點特征簇進行特征選擇,本文提出了基于層次粒化的特征選擇算法.

算法2基于層次粒化的特征選擇算法(Hierarchicalgranulationfeatureselection,HFS).

輸入：數據集

輸出：一個特征子集feature_sel

1)feature_sel=?.

2)subspacei_feature_sel=?.

3) 對?fi,fj∈C計算特征fi和特征fj的相似系數Rij,進而得到特征與特征間的相似性矩陣M.

4) 利用算法1對相似性度量矩陣進行層次粒化.

5) 在指定的層次上對subspacei(i=1,2,3)中的特征fi∈subspacei分別計算特征的最大相關最小冗余值q(fi,l).

6) 選擇特征fk加入subspacei_feature_sel中,滿足fk∈subspacei且q(fk)=max(q(fi))(fi∈subspacei);

if(length(subspacei_feature_sel)

subspacei_feature_sel=subspacei_feature_sel{fk};

subspacei=subspacei-{fi};

返回4);

elsefeature_sel=subspacei_feature_sel;

i=i+1;

end

3　實驗設計與結果

3.1實驗數據

為了驗證本文所提算法的性能,從UCI數據集中選取了6個數據集進行模擬仿真實驗,數據集具體的描述信息見表1.

表1　實驗數據描述Tab.1　Experimental data description

3.2實驗設置

為了驗證本文所提算法HFS的性能,第1部分比較HFS算法與NRS[15]、FCBF[17]、RELIEF[9]、T-test[18]等特征算法進行特征選擇后的特征數量.第2部分對比這5種算法得到的特征子集的分類精度.

在5個對比算法中,RELIEF和T-test得到的是特征的排序序列,取前K個特征作為最終的特征選擇結果,K與本文所提算法得到的特征的個數相同即「m/2?,m為特征數量.對于NRS特征選擇方法,需要對其鄰域參數值進行設置,實驗中NRS算法的鄰域參數值δ取0.1.

為了實驗的無偏性,采用十折交叉驗證法得到分類精度,將其作為評價特征子集優劣的標準.另外,采用KNN(K=1)、LSVM(線性支持向量機)這兩個基分類器進行評價分類精度.最后,實驗中涉及到的距離公式統一采用歐式距離.

3.3實驗結果

為了清晰直觀地比較這5種特征選擇算法所獲得的特征數量,表2中的第2列作為原始數據集的特征數量,第3、4、5、6、7列分別表示T-test、NRS、FCBF、RELIEF、HFS等5種算法最終得到的特征數量.在表2中增加最后一行表示每種算法在6個數據集下選擇得到的平均特征數量.

表2　不同算法選擇的特征數量的對比Tab.2　The numbers of selected features with different algorithms

為了測試算法的分類性能,在表3～4中給出了用KNN(K=1)、LSVM這2個不同的基分類器下的分類精度.為了能夠更加清晰準確地比較,將表3～4中括號外面的數值表示分類精度,括號里面的數值表示結果的標準差.最后一行的數值代表各算法的平均分類精度.

表3　不同特征選擇算法在KNN分類器下的分類精度比較Tab.3　Classification accuracies of feature selection with different algorithms based on KNN　%

注：*分類精度在5個對比算法中最高值；△分類精度在5個算法中的次高值；★平均分類精度最高值.

結合表2和表3～4的實驗結果可知：

1) 對比這5個算法,我們可以發現在KNN基分類器下,HFS算法在6個數據集下的分類精度有3個是最好的,2個是次好的;同樣在LSVM基分類器下,HFS算法在6個數據集下的分類精度有5個是最好的,1個是次好的.

2) 從特征數量取值相等的角度進行分析,本文的實驗將HFS算法和獲得特征序列的算法T-test及Relief進行對比.不論是在KNN基分類器還是LSVM基分類器下,HFS算法的平均分類精度都是最好的.

表4　不同特征選擇算法在LSVM分類器下的分類精度比較Tab.4　Classification accuracies of feature selection with different algorithms based on LSVM　%

注：*、△、★表示意義同表3.

4　總結

本文依據特征間的層次結構關系,從數據驅動的特征層次結構及節點特征簇內的特征質量分析兩方面出發,對特征存在結構化下如何進行特征選擇進行了建模,并提出了特征層次粒化算法和特征層次樹上的特征選擇算法.在UCI數據集上進行實驗,實驗結果表明本文所提層次粒化的特征選擇算法能夠取得較好的分類性能.

[1]LIANGJY,WANGF,DANGCY,etal.Anefficientroughfeatureselectionalgorithmwithamulti-granulationview[J].IntJApproxReason, 2012, 53(6): 912-926.

[2]GUYONI,ELISSEEFFA.Anintroductiontovariableandfeatureselection[J].JMachLearnRes, 2003, 3(6): 1157-1182.

[3]李霞, 蔣盛益, 郭艾俠. 基于聚類和信息熵的特征選擇算法[J]. 鄭州大學學報(理學版), 2009, 41(1): 77-80.

[4]何華平, 陳光建. 一種最小測試代價約簡的改進算法[J]. 鄭州大學學報(理學版), 2015, 47(1): 74-77.

[5]王杰, 蔡良健, 高瑜. 一種基于決策樹的多示例學習算法[J]. 鄭州大學學報(理學版), 2016, 48(1): 81-84.

[6]TANGJ,ALELYANIS,LIUH.Dataclassification:algorithmsandapplications[M].Florida:ChemicalRubberCompanyPress, 2014.

[7]LIY,GAOSY,CHENS.Ensemblefeatureweightingbasedonlocallearninganddiversity[C]//Proceedingsofthe26thAAAIconferenceonartificialintelligence.Edmonton, 2012.

[8]LIANGJ,WANGF,DANGC,etal.Anefficientroughfeatureselectionalgorithmwithamulti-granulationview[J].IntJApproxReason, 2012, 53(6): 912-926.

[9]ZHUW,SIG,ZHANGY,etal.Neighborhoodeffectiveinformationratioforhybridfeaturesubsetevaluationandselection[J].Neurocomputing, 2013, 99(1): 25-37.

[10]LINYJ,LIJJ,LINPR,etal.Featureselectionvianeighborhoodmulti-granulationfusion[J].Knowl-basedSyst, 2014, 67(1): 162-168.

[11]LINYJ,HUXG,WUXD,Qualityofinformation-basedsourceassessmentandselection[J].Neurocomputing, 2014, 133(1): 95-102.

[12]劉景華, 林夢雷, 王晨曦, 等. 基于最大近鄰粗糙逼近的特征選擇算法[J]. 小型微型計算機系統, 2015, 36(8): 1832-1836.

[13]HUQH,CHEX,ZHANGL,etal.Featureevaluationandselectionbasedonneighborhoodsoftmargin[J].Neurocomputing, 2010, 73(10): 2114-2124.

[14]彭鵬, 閆曉琳. 血常規檢驗中的常見誤差觀察研究[J]. 中國衛生標準管理, 2015, (15): 172-174.

[15]胡清華, 于達仁, 謝宗霞. 基于鄰域粒化和粗糙逼近的數值屬性約簡[J]. 軟件學報, 2008, 19(3):640-649.

[16]HUQH,ZHANGL,ZHANGD,etal.Measuringrelevancebetweendiscreteandcontinuousfeaturesbasedonneighborhoodmutualinformation[J].ExpertSystAppl, 2011, 38(9):10737-10750.

[17]YUL,LIUH.Efficientfeatureselectionviaanalysisofrelevanceandredundancy[J].JMachLearnRes, 2004, 5(10):1205-1224.

[18]ZHOUN,WANGL.AmodifiedT-testfeatureselectionmethodanditsapplicationontheHapMapenotypedata[J].Genomicsproteomicsbioinformatics, 2007, 5(Z1): 242-249.

(責任編輯：王浩毅)

FeatureSelectionAlgorithmBasedonHierarchicalGranulation

CHENHuihuang1,LINYaojin1,WANGChenxi2,TONGxianqun1,HUMinjie1

(1.School of Computer Science, Minnan Normal University, Zhangzhou 363000, China;2.Department of Computer Engineering, Zhangzhou Institute of Technology, Zhangzhou 363000, China)

Inmanypracticalapplicationproblems,thereisahierarchicalgranularstructureinfeaturespace.Firstly,hierarchicalclusteringbasedonkernelmethodwasproposedtoconducthierarchicalgranulationinfeaturespace.Secondly,afterhierarchicalgranulation,featuresweresortedataspecifiedlevelineachsubspacebymeasuringthemaximumcorrelationbetweenlabelsandfeatures,andtheminimumredundancybetweenfeaturesbasedontheneighborhoodmutualinformation.Onthisbasis,somerepresentativefeatureswerechosenineachsubspacetoformthefinalfeaturesubset.Finally,theresultwithsixUCIdatasetsandtwodifferentbaseclassifiersconfirmedtheeffectivenessoftheproposedalgorithm.

featureselection;granularcomputing;hierarchicalgranulation;mutualinformation

2016-06-25

國家自然科學基金資助項目(61303131,61672272);福建省高校新世紀優秀人才、福建省教育廳科技項目(JA14192).

陳輝皇(1992—)，男，福建莆田人，碩士研究生，主要從事數據挖掘研究，E-mail:vvchenhuihuang@163.com;

林耀進(1980—)，男，福建漳浦人，副教授，主要從事數據挖掘研究，E-mail:yjlin@mnnu.edu.cn.

TP18

A

1671-6841(2016)03-0069-06

10.13705/j.issn.1671-6841.2016096

引用本文:陳輝皇，林耀進，王晨曦，等.基于層次粒化的特征選擇算法[J].鄭州大學學報(理學版)，2016，48(3)：69-74.