徐久成,孫元豪+,韓子欽
(1.河南師范大學(xué) 計算機(jī)與信息工程學(xué)院,河南 新鄉(xiāng) 453007;2.河南師范大學(xué) 智慧商務(wù)與物聯(lián)網(wǎng)技術(shù)河南省工程實(shí)驗室,河南 新鄉(xiāng) 453007)
特征選擇是一種常見的數(shù)據(jù)預(yù)處理技術(shù)[1,2]。傳統(tǒng)的特征選擇假定特征空間是不變的[3],然而在實(shí)際情況中,特征往往隨著時間逐個或逐組地獲得,特征空間信息未知[4]。如何在流特征環(huán)境中進(jìn)行高效的特征選擇具有重要的實(shí)際應(yīng)用價值。
根據(jù)特征組的原始結(jié)構(gòu)信息,在線流特征選擇可分為在線流單特征選擇和在線流組特征選擇[5,6]。在線流單特征選擇方法對特征單獨(dú)處理,忽略了特征流存在的組結(jié)構(gòu)信息[7-10]。而對特征組執(zhí)行特征選擇比單獨(dú)對特征執(zhí)行特征選擇效果更好[11]。Yu等[12]提出一種可擴(kuò)展的流特征選擇方法,可在群組和個體兩個層面對特征組進(jìn)行有效選擇。Zhou等[5]考慮到流特征組內(nèi)和組間的交互作用,并通過彈性網(wǎng)回歸模型中的懲罰函數(shù)將變量的系數(shù)進(jìn)行調(diào)整,選擇有價值的變量,設(shè)計了一種新的群組流特征選擇方法。然而,現(xiàn)有的在線流特征選擇方法不能有效地處理模糊和不確定性環(huán)境下的任務(wù)。
近年來,基于模糊粗糙集的特征選擇方法在處理具有模糊性和不確定性的分類問題中得到了廣泛的應(yīng)用[13-15]。Xu等[16]重新定義了模糊鄰域關(guān)系并將其引入到條件熵中,提出了一種新的模糊鄰域條件熵。Wang等[17]提出一種鄰域判別指數(shù),與香農(nóng)熵具有相似的性質(zhì),可反映特征子集的區(qū)分能力。但這些基于模糊粗糙集理論的方法不能解決流環(huán)境下的特征選擇問題。
因此,為了解決模糊性和不確定性背景下的流特征選擇問題,本文提出一種基于模糊鄰域判別指數(shù)的在線流組特征選擇方法,并通過與5種流行算法的對比實(shí)驗,論證了該方法的有效性。
設(shè)OGDS= 為在線流組決策系統(tǒng)。其中U={x1,x2,…,xm} 為樣本的論域集合,G={G1,G2,…,Gt} 為條件特征集合,t為時間序列,Gi={f1,f2,…,fn} 為G中的一組特征,D為決策特征集合,在t時刻特征組Gt流入特征空間,h為映射函數(shù)。
令A(yù)?G為U上的一個條件特征子集,則屬性A引出的一組模糊二元關(guān)系表示為RA,RA(x,y)=1-|xA-yA|,若RA同時滿足:①自反性:RA(x,y)=1,?x∈U;②對稱性:RA(x,y)=RA(y,x),?x,y∈U。則稱RA為U上的一組模糊相似關(guān)系。
定義1[16]設(shè)λ為模糊鄰域半徑,則對于?x∈U,x關(guān)于A的參數(shù)化的模糊鄰域信息粒定義為
(1)
關(guān)于A的模糊鄰域熵定義為
(2)
定義2[16]假設(shè)D將樣本集合U劃分為l個等價類,U/D={D1,D2,…,Dl},由D生成的模糊決策為FD={FD1T,F(xiàn)D2T,…,F(xiàn)DlT},其中FDj為樣本決策的模糊等價類,則x在Dj上的隸屬度表示為
(3)
式中:j=1,2,…,l,|·|表示基數(shù),|λA(x)∩Dj|表示樣本對λA(x)的隸屬度不大于Dj的個數(shù)。
(4)
鄰域判別指數(shù)的計算基于鄰域相似關(guān)系的基數(shù),具有與香農(nóng)熵及其變體相似的性質(zhì),是一種度量特征子集區(qū)分能力的有效方法[18]。
Lasso模型是彈性網(wǎng)策略的一種特殊形式,令X為數(shù)據(jù)矩陣,ê為投影向量,則決策類向量表示為Y=XTê,設(shè)γ為調(diào)節(jié)正則化數(shù)目的參數(shù),Lasso方法通過最小化以下目標(biāo)函數(shù)來選擇最佳的ê
(5)
本節(jié)首先定義了模糊鄰域判別指數(shù),然后提出了模糊鄰域互判別指數(shù)和模糊對稱不確定性的概念,在此基礎(chǔ)上擴(kuò)展了一些不確定性度量方法。
定義4 給定OGDS= 為在線流組決策系統(tǒng),其中U={x1,x2,…,xm},設(shè)A?G,λA(x) 為x關(guān)于A的參數(shù)化的模糊鄰域粒,則關(guān)于A的模糊鄰域判別指數(shù)定義為
(6)
根據(jù)式(6)可知,模糊鄰域判別指數(shù)通過模糊鄰域粒的基數(shù)來計算,而式(2)中模糊鄰域熵通過累加模糊鄰域相似類的基數(shù)獲得。因此,模糊鄰域判別指數(shù)的計算復(fù)雜度略小于模糊鄰域熵。
性質(zhì)1 若A?B,則FNDIλ(A)≤FNDIλ(B)。
證明:令 (xi,xj)∈λB(x),可得RB(xi,xj)≤λ,由A?B可得RA(xi,xj)≤λ,因此 (xi,xj)∈λA(x),由模糊鄰域粒的性質(zhì)可知λB(x)?λA(x),且|λB(x)|≤|λA(x)|。根據(jù)定義4可得FNDIλ(A)≤FNDIλ(B)。
性質(zhì)1表明模糊鄰域判別指數(shù)的大小隨著特征組的增大單調(diào)遞增。
定義5 設(shè)A,B?G,則A和B的模糊鄰域互判別指數(shù)定義為
(7)
特別地,當(dāng)B=D時,使用樣本生成的模糊決策FD來計算特征與決策類的模糊鄰域互判別指數(shù),可以更充分地利用決策信息,進(jìn)而更好地處理模糊性和不確定性數(shù)據(jù)。
模糊鄰域互判別指數(shù)的值越大,表明該特征與決策類越相關(guān),該特征就越重要。
性質(zhì)2
FNMDIλ(A;B)=
FNDIλ(A)+FNDIλ(B)-FNDIλ(A,B)
證明
FNDIλ(A)+FNDIλ(B)-FNDIλ(A,B)
定義6 設(shè)A,B?G,則A和B的模糊對稱不確定性定義為
(8)
模糊鄰域互判別指數(shù)和模糊對稱不確定性都可以用于評價相關(guān)特征的重要性,利用兩種度量標(biāo)準(zhǔn)有利于選擇更佳的特征子集,提升算法的性能。
接下來將在線流組特征選擇分為組內(nèi)特征選擇和組間特征選擇兩部分,并擴(kuò)展了一些不確定性度量方法。首先計算特征的重要度在組內(nèi)選擇具有強(qiáng)近似能力的特征流入特征空間,然后根據(jù)交互增益和對比度選擇具有交互作用的特征。
2.2.1 組內(nèi)特征選擇
定義7 給定OGDS= 為一個在線流組決策系統(tǒng),設(shè)A?Gt,a∈A,則特征a關(guān)于決策D的重要度定義為
Sig(a,A,D)=
FNMDIλ(A;D)-FNMDIλ(A-{a};D)
(9)
定理1 若Sig(a,A,D)>0,則稱特征a是重要的,否則稱特征a是不重要的。
證明:當(dāng)Sig(a,A,D)>0時,由式(9)可得FNMDIλ(A;D)>FNMDIλ(A-{a};D),這表明去掉特征a導(dǎo)致模糊鄰域互判別指數(shù)的值變小,特征組提供的近似能力變?nèi)?,因此特征a是重要的。顯然,當(dāng)不滿足該條件時,特征a是不重要的。
通過將式(9)應(yīng)用到組內(nèi)特征選擇,可以遍歷特征組Gi中的所有特征,選擇重要的特征,并將選擇后的特征組S′t流入特征空間。
2.2.2 組間特征選擇
定義8 給定OGDS= 為一個在線流組決策系統(tǒng),設(shè)f為S′t中的一個特征,St-1為t-1時刻已選擇的特征集合,則特征f關(guān)于St-1的交互增益定義為
IGλ(f,St-1)=FSUλ(f,St-1;D)-
FSUλ(f;D)-FSUλ(St-1;D)
(10)
定理2 若IGλ(f,St-1)>0,則特征f具有交互作用。
證明:當(dāng)IGλ(f,St-1)>0時,由式(10)可得FSUλ(f,St-1;D)>FSUλ(f;D)+FSUλ(St-1;D),這表明f和St-1在一起所提供的信息大于二者分開所提供信息之和,因此特征f具有交互作用。
如果特征f具有交互作用,那么需進(jìn)一步對該特征進(jìn)行分析。
定義9 給定OGDS= 為一個在線流組決策系統(tǒng),設(shè)f1為S′t中有交互作用的特征,f2為St-1中的特征,則特征f2關(guān)于f1的對比度定義為
Cλ(f1,f2)=FSUλ(f1,D)-FSUλ(f2;D)
(11)
定理3 若Cλ(f1,f2)>0,則特征f1是重要的,特征f2是冗余的。
證明:定義9衡量了新到達(dá)特征與已選特征集合的相關(guān)性。當(dāng)Cλ(f1,f2)>0時,由式(11)可得FSUλ(f1;D)>FSUλ(f2;D),這表明特征f1所提供的信息是大于特征f2所提供的信息的,因此特征f1是重要的,特征f2是冗余的。
當(dāng)沒有新特征流入時,使用Lasso方法對所有選定的特征進(jìn)行重新評估,丟棄不相關(guān)的特征。
基于上述理論,本文提出了一種基于模糊鄰域判別指數(shù)的在線流組特征選擇(online group streaming feature selection based on fuzzy neighborhood discrimination index,OGSFS-FNDI) 算法。算法描述如下:
算法1:OGSFS-FNDI
輸入:OGDS=,模糊鄰域半徑λ,組規(guī)模g;
輸出:已選特征子集S.
(1)初始化:S=?;
(2)在t時刻流入新的特征組Gt;
(3)/*組內(nèi)特征選擇*/
(4)fori=1 to|Gt|
(5) 計算fi的重要度Sig(fi,Gt,D);
(6) ifSig(fi,Gt,D)>0
(7) LetS′t=S′t∪{fi};
(8) end if
(9)end for
(10)/*組間特征選擇*/
(11)forj=1 to|S′t|
(12) 計算fj的交互增益IGλ(fj,St-1);
(13) ifIGλ(fj,St-1)>0
(14) fork=1 to|St-1|
(15) 計算fj和fk的對比度Cλ(fj,fk);
(16) ifCλ(fj,fk)>0
(17) LetS=S∪{fj};S=S-{fk};
(18) end if
(19) end for
(20) end if
(21)end for
(22)直到?jīng)]有Gt流入,使用Lasso選擇特征子集S;
(23)returnS.
在算法1中,OGSFS-FNDI算法的時間復(fù)雜度由步驟(11)的循環(huán)決定,設(shè)組內(nèi)特征選擇階段選擇的特征個數(shù)為|S′t|,t-1時刻已選擇的特征個數(shù)為|St-1|,樣本個數(shù)為m。步驟(15)的時間復(fù)雜度在最壞情況下為O(m2),因此,OGSFS-FNDI算法的時間復(fù)雜度在最壞情況下為O(m2×|S′t|×|St-1|)。顯然|S′t|和|St-1|的值遠(yuǎn)小于特征維度|G|,可見OGSFS-FNDI算法選擇最佳特征子集的效率較高。
為了驗證OGSFS-FNDI算法的有效性,實(shí)驗選取8個公共數(shù)據(jù)集,包括3個UCI數(shù)據(jù)集(Wpbc、Sonar、Heart)和5個DNA微陣列數(shù)據(jù)集(Colon、DLBCL、Lymphoma、Breast、MLL)。上述數(shù)據(jù)集可從http://arc-hive.ics.uci.edu/ml/index.php和http://csse.sz u.edu.cn/staff/zhuzx免費(fèi)下載,表1給出相關(guān)數(shù)據(jù)集的詳細(xì)信息。
表1 數(shù)據(jù)集描述
本文實(shí)驗均在Windows 10 PC,Intel Core i5-3470 CPU@3.20 GHz,4.0 GB RAM環(huán)境下進(jìn)行,并使用Matlab2016a實(shí)現(xiàn)和完成所有對比實(shí)驗。為了減少不同量綱對實(shí)驗結(jié)果的影響,通過以下公式對數(shù)據(jù)集進(jìn)行歸一化
F(xi)=(xi-xmin)/(xmax-xmin)
(12)
經(jīng)過預(yù)處理操作,數(shù)據(jù)被歸一化到[0,1]區(qū)間。借鑒文獻(xiàn)[5]中的實(shí)驗設(shè)置,本節(jié)選取KNN(k=3)和CART分類器對特征子集進(jìn)行評估,并將分類準(zhǔn)確率和選擇特征個數(shù)作為評價指標(biāo),分析了OGSFS-FNDI算法和對比算法在相關(guān)數(shù)據(jù)集上的分類性能。
本節(jié)采用十折交叉驗證以測試算法分類性能的準(zhǔn)確性,每個數(shù)據(jù)集被隨機(jī)分成10份,輪流將其中9份作為訓(xùn)練數(shù)據(jù)集,另外一份作為測試數(shù)據(jù)集,取10次分類準(zhǔn)確率的平均值作為最終的結(jié)果。所有的對比算法都基于相同的設(shè)計方法。
OGSFS-FNDI算法中有兩個參數(shù),模糊鄰域半徑λ用于調(diào)節(jié)模糊鄰域的大小,組規(guī)模g用于控制在線流組特征選擇的特征組大小。為了分析兩個參數(shù)的取值對算法的影響,本節(jié)將λ的值設(shè)置為0.1到1,步長為0.1,并根據(jù)文獻(xiàn)[5]的組規(guī)模,將g的值設(shè)置為50、100、200、400、800,這個區(qū)間設(shè)置針對高維數(shù)據(jù)集是有效的,但是面對低維數(shù)據(jù)集時并不能發(fā)揮劃分特征組的作用,因此對于低維數(shù)據(jù)集將g的值設(shè)置為5、10、20、30、60,這更有利于模擬實(shí)際工作中特征流的組劃分情況。本節(jié)重點(diǎn)討論了不同參數(shù)對OGSFS-FNDI算法在分類準(zhǔn)確率方面的影響,使用KNN和CART分類器得到的分類準(zhǔn)確率隨參數(shù)變化的曲面圖大致相似,因此本文僅列出了使用KNN分類器的情況。
圖1呈現(xiàn)了所提算法在3個低維數(shù)據(jù)集上的分類準(zhǔn)確率隨參數(shù)的變化曲面。由圖1可知,參數(shù)的變化會對不同的數(shù)據(jù)集產(chǎn)生不同程度的影響。對于Wpbc和Sonar數(shù)據(jù)集,當(dāng)λ的值大于0.4時分類性能整體趨勢較為平穩(wěn),在大多數(shù)參數(shù)上均達(dá)到了較高的分類準(zhǔn)確率,由于數(shù)據(jù)集的特征維度較低,此時g的值對其分類性能的影響并不明顯。而對于Heart數(shù)據(jù)集,分類性能隨著參數(shù)的變化呈現(xiàn)不規(guī)律性,但整體的分類準(zhǔn)確率仍保持在一個穩(wěn)定的區(qū)間內(nèi)。
圖1 3個低維數(shù)據(jù)集在不同參數(shù)下分類準(zhǔn)確率的變化曲面
圖2為OGSFS-FNDI算法在5個高維數(shù)據(jù)集上的分類準(zhǔn)確率隨參數(shù)的變化曲面。觀測圖2,模糊鄰域半徑和組規(guī)模的大小在DNA微陣列數(shù)據(jù)集上更能呈現(xiàn)出規(guī)律性。對于Colon、DLBCL和Lymphoma數(shù)據(jù)集,算法的分類性能隨著參數(shù)變化的趨勢大致相同,隨著λ的增大分類準(zhǔn)確率也呈現(xiàn)上升的狀態(tài),尤其是當(dāng)λ的值大于0.4時分類準(zhǔn)確率具有明顯的提升,且隨著g的增大分類準(zhǔn)確率同時也在增加。在Breast和MLL數(shù)據(jù)集上,當(dāng)λ的值小于0.6時的分類準(zhǔn)確率整體呈現(xiàn)較低的水平,在λ大于0.6且g的值較大時達(dá)到分類精度的最優(yōu)值。這表明由于DNA微陣列數(shù)據(jù)集的特征維數(shù)較高,數(shù)據(jù)具有模糊性和不確定性,模糊鄰域判別指數(shù)作為一種有效的度量方法,可以有效地考慮到特征之間的相關(guān)性,而使用較大的模糊鄰域半徑和組規(guī)模往往可以充分利用特征組的分類信息,從而提高特征子集的強(qiáng)近似能力。
圖2 5個高維數(shù)據(jù)集在不同參數(shù)下分類準(zhǔn)確率的變化曲面
總的來說,OGSFS-FNDI算法可以在大部分?jǐn)?shù)據(jù)集上找到最優(yōu)的參數(shù)以達(dá)到較高的分類準(zhǔn)確率,但對于不同的數(shù)據(jù)集所適用的參數(shù)是不同的。
為了評價算法的有效性,本節(jié)選擇了目前較流行的5種算法與OGSFS-FNDI算法進(jìn)行比較,其中包括兩種在線流組特征選擇算法(OGSFS-FI[5]、Group-SAOLA[12]),兩種在線流單特征選擇算法(SFS-FI[7]、K-OFSD[8])和一種基于模糊鄰域條件熵的特征選擇算法(FNCE[16])。對比算法的參數(shù)設(shè)置均與原論文描述一致,且下文呈現(xiàn)的數(shù)據(jù)均為算法所達(dá)到的最優(yōu)值。接下來分析了算法在分類準(zhǔn)確率和選擇特征個數(shù)方面的性能對比。
表2和表3分別呈現(xiàn)了對比算法在KNN和CART分類器上取得的分類準(zhǔn)確率,加粗字體表示某一算法在該數(shù)據(jù)集上取得最佳分類準(zhǔn)確率,最后一行列出了算法在所有數(shù)據(jù)集上的平均準(zhǔn)確率。
表2 6種算法在KNN分類器上的分類準(zhǔn)確率對比
表3 6種算法在CART分類器上的分類準(zhǔn)確率對比
由表2和表3可見,基于KNN和CART分類器,OGSFS-FNDI算法在Wpbc、Sonar、Heart、Lymphoma數(shù)據(jù)集上的表現(xiàn)均優(yōu)于其它5種對比算法,且在8個數(shù)據(jù)集上分類準(zhǔn)確率的平均值均排名第一。盡管OGSFS-FI和Group-SAOLA算法都可以處理在線流組特征選擇問題,但其在兩個分類器上的分類準(zhǔn)確率都低于本文所提算法。K-OFSD算法與本文所提算法在分類準(zhǔn)確率方面保持在同一水平,且在處理DLBCL、MLL這類高維類不平衡數(shù)據(jù)集時該算法可以實(shí)現(xiàn)更高的分類準(zhǔn)確率。SFS-FI算法具有最差的分類性能,且K-OFSD和SFS-FI算法僅能在單特征層面進(jìn)行在線流特征選擇。FNCE算法整體的分類性能較差,且只能處理靜態(tài)的特征選擇。OGSFS-FNDI算法在高維數(shù)據(jù)集上的分類準(zhǔn)確率明顯高于其它對比算法,這是因為該算法基于粗糙集理論進(jìn)行推廣,在處理DNA微陣列數(shù)據(jù)集這類不確定性數(shù)據(jù)時有著明顯的優(yōu)勢。同時,算法還考慮到了數(shù)據(jù)的模糊概念,使用參數(shù)化的模糊鄰域信息粒構(gòu)建隸屬度函數(shù),實(shí)驗結(jié)果表明該算法對具有模糊性和不確定性數(shù)據(jù)的處理有較好的效果。
為了更直觀地展示OGSFS-FNDI算法的有效性,本節(jié)繪制了盒型圖來描述對比算法的分類準(zhǔn)確率之間的離散分布差異,圖3和圖4指出了所有算法在KNN和CART分類器上所獲得分類準(zhǔn)確率的分布情況,盒型圖中間的橫線表示中位數(shù),“+”表示離群的異常值。
圖3 6種算法在KNN分類器上的盒型圖對比
圖4 6種算法在CART分類器上的盒型圖對比
由圖3和圖4可知,OGSFS-FNDI算法在兩個分類器上分類準(zhǔn)確率的平均性能(中位數(shù))都是最強(qiáng)的。在KNN和CART分類器上,算法在上四分位數(shù)和下四分位數(shù)的多數(shù)集中在分類準(zhǔn)確率較高的區(qū)間,且并未出現(xiàn)異常值。對比算法的分類準(zhǔn)確率表現(xiàn)較差,中位線所在水平均明顯低于所提算法,且其分布并不穩(wěn)定。Group-SAOLA和SFS-FI算法在整體上處于較低水平;OGSFS-FI和FNCE算法呈現(xiàn)的數(shù)值區(qū)間較大;而K-OFSD算法在CART分類器上出現(xiàn)了離群的異常值,這表明對比算法雖然在部分?jǐn)?shù)據(jù)集上分類性能較好,但其表現(xiàn)并不穩(wěn)定。由此可得,OGSFS-FNDI算法的分類性能和其它5種算法相比更為穩(wěn)定。
表4描述了6種算法在8個數(shù)據(jù)集上選擇的特征個數(shù)。觀察表4發(fā)現(xiàn),OGSFS-FNDI算法在8個數(shù)據(jù)集上能夠?qū)崿F(xiàn)特征約簡的目的,但在所有的對比算法中表現(xiàn)并未達(dá)到最優(yōu)。盡管Group-SAOLA和SFS-FI算法在選擇特征個數(shù)上體現(xiàn)了很大的優(yōu)勢,但通過表2和表3可見其分類精度明顯低于其它算法,這表明在特征選擇過程中丟失了較為重要的特征信息。
表4 6種算法在8個數(shù)據(jù)集上選擇的特征個數(shù)
與OGSFS-FNDI算法相比,Group-SAOLA和SFS-FI算法的時間復(fù)雜度分別為O(|St-1|×|G|) 和O(m2),盡管其表現(xiàn)較優(yōu),但結(jié)合實(shí)驗結(jié)果可知其分類準(zhǔn)確率較低。此外,K-OFSD和FNCE算法的時間復(fù)雜度均為O(m2×|G|),而OGSFS-FI算法的時間復(fù)雜度為O(k3+k2×|St-1|),其中k為算法調(diào)用彈性網(wǎng)的次數(shù),時間復(fù)雜度較高。根據(jù)實(shí)驗結(jié)果可知,OGSFS-FNDI算法最終選擇的特征子集很小,即所提算法在實(shí)際應(yīng)用中的時間復(fù)雜度遠(yuǎn)低于最壞情況。因此,與其它5種特征選擇算法相比,本文算法在時間復(fù)雜度上的表現(xiàn)較優(yōu)。
綜上所述,本文所提的OGSFS-FNDI算法能夠在選擇較少特征個數(shù)的同時呈現(xiàn)出較優(yōu)且穩(wěn)定的分類性能。
針對大多數(shù)在線流組特征選擇方法無法處理模糊性和不確定性數(shù)據(jù)的問題,本文提出了一種基于模糊鄰域判別指數(shù)的在線流組特征選擇算法。該算法基于模糊鄰域判別指數(shù)擴(kuò)展了相關(guān)的不確定性度量,同時使用組內(nèi)特征選擇和組間特征選擇兩種策略,以在線的方式選擇能夠提高分類性能的特征。通過一系列實(shí)驗對比及分析,驗證了所提算法可以有效且穩(wěn)定地選擇最佳特征子集。雖然OGSFS-FNDI算法在大部分?jǐn)?shù)據(jù)集上達(dá)到更高的分類精度,但窮舉法尋找最佳參數(shù)的方式效率較低,因此未來的工作將重點(diǎn)研究自動尋找最優(yōu)參數(shù)的在線流組特征選擇方法。