基于AP聚類和互信息的弱標(biāo)記特征選擇方法

孫 林,施恩惠,司珊珊,徐久成

(河南師范大學(xué)計算機與信息工程學(xué)院,河南 新鄉(xiāng) 453007)

目前,多標(biāo)記學(xué)習(xí)在神經(jīng)網(wǎng)絡(luò)、機器學(xué)習(xí)等領(lǐng)域引起了廣泛關(guān)注,且被應(yīng)用于各種現(xiàn)實任務(wù)中,作為多標(biāo)記學(xué)習(xí)的重要內(nèi)容,特征選擇旨在消除冗余特征、降維獲取有用的信息以提升分類性能[1]. 傳統(tǒng)的多標(biāo)記特征選擇算法假設(shè)多標(biāo)記數(shù)據(jù)集的標(biāo)記空間是完整且不缺失的[2]. 但在實際應(yīng)用中,標(biāo)記會因為人為或者設(shè)備的原因缺失或者無法獲取,由此產(chǎn)生了大量的弱標(biāo)記數(shù)據(jù),即數(shù)據(jù)存在標(biāo)記缺失或無標(biāo)記的情況[3]. 然而,不完整的標(biāo)記空間將導(dǎo)致特征和標(biāo)記集相關(guān)性度量不準(zhǔn)確,并且在特征選擇過程中會丟失一些有價值的特征[4-7]. 因此,如何處理帶缺失標(biāo)記的弱標(biāo)記數(shù)據(jù)問題顯得尤為重要. 目前,缺失標(biāo)記的處理方法有兩種較為普遍,分別是填補法、粗糙集模型擴展法[3,8]. 例如,Zhu等[9]利用線性回歸模型來填補缺失標(biāo)記,并將正則化作用于特征選擇矩陣,選擇最優(yōu)特征子集;Jiang等[10]基于標(biāo)記壓縮和局部特征相關(guān)性,補全缺失標(biāo)記. 由于粗糙集模型[11]處理缺失標(biāo)記的方法不多,而填補法簡單方便、直接有效[8],因而本文采用填補法處理缺失標(biāo)記. 目前,回歸填補需要花費大量時間[8];K最近鄰填補需要設(shè)定K值且處理大規(guī)模數(shù)據(jù)集的效果不佳[12-13];而基于聚類的填補方法不受缺失數(shù)據(jù)的影響,時間復(fù)雜度相對較小,具有普遍的適用性[8,13]. 另外,基于AP聚類的填補方法與其他聚類算法相比,不需要預(yù)先設(shè)定聚類個數(shù),可以將所有的樣本都看作聚類中心,按照樣本間的信息傳遞實現(xiàn)聚類,根據(jù)類中相似對象進行填補,且多次運行后的聚類結(jié)果比較穩(wěn)定[8,13]. 因此,本文借鑒AP聚類算法優(yōu)勢來處理缺失標(biāo)記,結(jié)合原有完整標(biāo)記信息和樣本相似性,有效補齊所有的缺失標(biāo)記.

由于互信息能夠檢測變量之間的非線性關(guān)系,實現(xiàn)有效的特征選擇[2],因此很多基于互信息的多標(biāo)記特征選擇算法被提出. 例如,Lee等[14]提出通過最大化特征和標(biāo)記之間的相關(guān)性選擇特征子集;Lin等[15]結(jié)合互信息,按照特征和標(biāo)記的最大相關(guān)、特征間的最小冗余準(zhǔn)則,篩選特征;Sun等[16]將最大相關(guān)最小冗余轉(zhuǎn)化為約束凸優(yōu)化函數(shù),構(gòu)造應(yīng)用于多標(biāo)記學(xué)習(xí)的特征選擇算法. 但是,上述這些算法都假設(shè)標(biāo)記空間中所有標(biāo)記具有相同的占比,而忽略了標(biāo)記空間中標(biāo)記占比可能會對特征和標(biāo)記集相關(guān)性的影響,進而導(dǎo)致相關(guān)性計算的不準(zhǔn)確. 為了解決這個問題,Shi等[17]提出標(biāo)記占比并應(yīng)用于多標(biāo)記特征選擇. 基于此,引入標(biāo)記占比改進互信息公式,度量特征和標(biāo)記集之間的相關(guān)性,選擇最優(yōu)特征子集.

針對以上問題,本文運用AP聚類算法將樣本編號,按照缺失標(biāo)記數(shù)排序,結(jié)合樣本相似度和概率填補預(yù)測缺失標(biāo)記值,補全缺失標(biāo)記;將標(biāo)記先驗概率作為標(biāo)記的占比,結(jié)合互信息構(gòu)建相關(guān)性度量評估特征和標(biāo)記集之間的相關(guān)程度,降序排列選擇最優(yōu)特征子集. 實驗表明該算法的性能比目前相關(guān)算法更好.

1 AP聚類

AP聚類[18]是Frey和Dueck提出的高效聚類算法. 該聚類算法是通過數(shù)據(jù)點間的消息傳遞,確定聚類中心,以及給每個聚類中心分配數(shù)據(jù)點[13]. 相似度矩陣的計算是消息傳遞的基礎(chǔ),在AP聚類中用歐式距離衡量數(shù)據(jù)點之間的相似度. 假設(shè)X={x1,x2,…,xn}∈Rn×f表示樣本空間,對于任意樣本xi,xk∈X,相似度公式[8,13]表示為:

s(xi,xk)=-‖xi-xk‖2.

(1)

AP聚類有吸引度和依賴度兩類消息傳遞,用來確定聚類中心,以及給每個聚類中心分配數(shù)據(jù)點.假設(shè)R表示吸引度矩陣,A表示依賴度矩陣.對于任意樣本xi,xk∈X,吸引度矩陣更新公式[13]表示為:

r(xi,xk)←s(xi,xk)-max{a(xi,xk′)+s(xi,xk′)},k′≠k.

(2)

對于任意樣本xi,xk∈X,依賴度矩陣更新公式[13]表示為:

(3)

2 弱標(biāo)記特征選擇方法

2.1 基于AP聚類的缺失標(biāo)記填補

定義1假設(shè)X={x1,x2,…,xn}∈Rn×f表示樣本空間,Y={y1,y2,…,yn}∈Rn×L表示標(biāo)記空間,數(shù)據(jù)集X經(jīng)過聚類劃分為k個不相交的簇C={c1,c2,…,ck},根據(jù)樣本是否含有缺失標(biāo)記將數(shù)據(jù)集劃分為完備數(shù)據(jù)集D1和不完備數(shù)據(jù)集D2.如果樣本xi有第j個標(biāo)記,則xi(lj)=1,否則xi(lj)=-1.如果樣本xi的第j個標(biāo)記值缺失,則設(shè)xi(lj)=0.

定義2假設(shè)X={x1,x2,…,xn}∈Rn×f表示樣本空間,Y={y1,y2,…,yn}∈Rn×L表示標(biāo)記空間,xi∈D2,xi(lj)=0,xm(lj)=1或-1,且xi,xm∈Cq(q=1,2,…,k).xi與同一簇Cq中所有xm的相似度累加和表示為:

s=∑s(xi,xm).

(4)

定義3假設(shè)X={x1,x2,…,xn}∈Rn×f表示樣本空間,Y={y1,y2,…,yn}∈Rn×L表示標(biāo)記空間,xi∈D2,xi(lj)=0,xm(lj)=1或-1,且xi,xm∈Cq(q=1,2,…,k),缺失標(biāo)記預(yù)測值可表示為:

(5)

由于相似樣本之間具有相似標(biāo)記,利用式(4)和式(5)預(yù)測缺失標(biāo)記的值.pre_label即為xi(lj)的預(yù)測值,且取值范圍為[-1,1].

定義4假設(shè)X={x1,x2,…,xn}∈Rn×f表示樣本空間,Y={y1,y2,…,yn}∈Rn×L表示標(biāo)記空間,xi(lj)=0,根據(jù)計算得到pre_label值,xi(lj)可表示為:

(6)

2.2 基于互信息的特征選擇

定義5假設(shè)X={x1,x2,…,xn}∈Rn×f表示樣本空間,Y={y1,y2,…,yn}∈Rn×L表示標(biāo)記空間,F={p1,p2,…,pf}∈Rf表示特征空間.對于任意特征pi∈F和標(biāo)記lj∈L,pi和lj的互信息公式定義為:

I(pi;lj)=H(pi)-H(lj|pi),

(7)

式中,H(pi)表示特征pi的信息熵,H(lj|pi)表示標(biāo)記lj的條件熵.式(7)計算特征和標(biāo)記之間的相關(guān)性.

定義6假設(shè)X={x1,x2,…,xn}∈Rn×f表示樣本空間,Y={y1,y2,…,yn}∈Rn×L表示標(biāo)記空間,對于任意標(biāo)記lj∈L,lj的占比公式定義為:

(8)

式中,n表示樣本的個數(shù),n(lj)表示包含標(biāo)記lj的樣本個數(shù).如果標(biāo)記lj的占比很高,則表明很多樣本包含標(biāo)記lj,因此可認為標(biāo)記lj相對重要.另外,根據(jù)式(8)可知,一般情況下每個標(biāo)記的W(lj)值相差不大.

因為在大多數(shù)多標(biāo)記數(shù)據(jù)集中,特征值通常是連續(xù)或者高度離散的,所以當(dāng)使用互信息衡量特征之間的冗余度時,結(jié)果幾乎為0.文獻[19]指出,如果使用互信息度量特征和標(biāo)記之間的相關(guān)度,則可以根據(jù)相關(guān)度值選擇特征子集,忽略特征冗余的影響.因此,本文將不考慮特征間的冗余.

定義7假設(shè)X={x1,x2,…,xn}∈Rn×f表示樣本空間,Y={y1,y2,…,yn}∈Rn×L表示標(biāo)記空間,F={p1,p2,…,pf}∈Rf表示f維的特征空間.對于任意特征pi∈F和標(biāo)記lj∈L,pi和L的相關(guān)度被定義為:

(9)

2.3 算法描述

假設(shè)多標(biāo)記數(shù)據(jù)集有N個樣本、L個標(biāo)記和f個特征,聚類產(chǎn)生k個簇,標(biāo)記隨機缺失后,共有p個樣本具有缺失標(biāo)記.WFSAM的時間復(fù)雜度計算如下:步驟1聚類的時間復(fù)雜度為O(N2logN);步驟2-步驟5補全標(biāo)記的時間復(fù)雜度為O(kpL);步驟6-步驟8特征和標(biāo)記之間相關(guān)度計算的時間復(fù)雜度為O(Nf),由此可計算出WFSAM算法總的時間復(fù)雜度為O(N2logN+Nf).

3 實驗結(jié)果與討論

3.1 實驗數(shù)據(jù)與準(zhǔn)備

本文選用6個多標(biāo)記數(shù)據(jù)集,數(shù)據(jù)集來自http://mulan.sourceforge.net,如表1所示. 將基于k最近鄰的多標(biāo)記方法(multi-labelk-nearest neighbors,MLKNN)[20]作為特征選擇的分類器(近鄰數(shù)為10,平滑參數(shù)為1). 使用平均精度(average precision,AP)、排序損失(ranking loss,RL)、覆蓋率(coverage,CV)和1-錯誤率(one error,OE)作為評價指標(biāo)[3,7]. 其中,AP值越大,表示算法性能越好,用“↑”表示,且最優(yōu)值為1;其他指標(biāo)值越小,則表示算法性能越好,用“↓”表示,且最優(yōu)值為0.

表1 多標(biāo)記數(shù)據(jù)集信息Table 1 Multi-label datasets information

3.2 不同缺失比率下多標(biāo)記特征選擇算法的分類結(jié)果

為了驗證算法的有效性,將所提的WFSAM算法與MFML[7]、PMU[14]、MDMR[15]、MDDMspc[21]、MDDMproj[21]、MLNB[22]和MLFRS[23]算法進行比較. 這些算法均使用對應(yīng)文獻中的最佳實驗參數(shù). 實驗選取特征排序的前30%作為特征子集,對比的實驗數(shù)據(jù)與結(jié)果選自文獻[7]. 表2-表5展示了8個多標(biāo)記特征選擇算法分別在0%、20%、40%和60%的缺失比率下在6個多標(biāo)記數(shù)據(jù)集上的實驗結(jié)果. 最優(yōu)結(jié)果為粗體表示.

表2 0%缺失標(biāo)記下4個指標(biāo)的實驗結(jié)果對比Table 2 Comparison results of four metrics under 0% missing labels

表3 20%缺失標(biāo)記下4個指標(biāo)的實驗結(jié)果對比Table 3 Comparison results of four metrics under 20% missing labels

表4 40%缺失標(biāo)記下4個指標(biāo)的實驗結(jié)果對比Table 4 Comparison results of four metrics under 40% missing labels

表5 60%缺失標(biāo)記下4個指標(biāo)的實驗結(jié)果對比Table 5 Comparison results of four metrics under 60% missing labels

對表2分析可知:(1)在AP指標(biāo)對比結(jié)果中,WFSAM在Enron數(shù)據(jù)集上僅優(yōu)于MDDMproj、MLNB和MLFRS,比其余4個算法低0.006 3～0.010 2,但WFSAM的平均值最優(yōu). (2)在RL指標(biāo)對比結(jié)果中,WFSAM在Enron數(shù)據(jù)集上僅優(yōu)于MLFRS,但與分類最優(yōu)的MDMR僅差0.006,且WFSAM在其余5個數(shù)據(jù)集上表現(xiàn)最優(yōu). (3)在CV指標(biāo)對比結(jié)果中,WFSAM在Computers、Enron數(shù)據(jù)集上比MFML分別略相差0.003 3、0.473 2,但是WFSAM在其余4個數(shù)據(jù)集上表現(xiàn)最優(yōu). (4)在OE指標(biāo)對比結(jié)果中,WFSAM在Computers數(shù)據(jù)集上與MLNB僅差0.002;在Enron數(shù)據(jù)集上,WFSAM與MDMR、MFML相差0.036 2;在其余4個數(shù)據(jù)集上,WFSAM表現(xiàn)最優(yōu). 總體來說,在標(biāo)記缺失比率為0%時,WFSAM明顯優(yōu)于其他7種算法.

對表3分析可知:(1)在AP指標(biāo)對比結(jié)果中,WFSAM在Computers數(shù)據(jù)集上僅次于MFML;在Enron數(shù)據(jù)集上,WFSAM僅優(yōu)于MLFRS,略差于其余6種算法. 但是WFSAM的平均值最優(yōu). (2)在RL對比結(jié)果中,WFSAM在Enron數(shù)據(jù)集上僅優(yōu)于MLFRS,但在其余5個數(shù)據(jù)集上WFSAM表現(xiàn)最優(yōu),同時WFSAM的平均值也最優(yōu). (3)在CV指標(biāo)對比結(jié)果中,WFSAM在Enron數(shù)據(jù)集上僅優(yōu)于MLFRS,與其余6個算法相差0.150 3～0.613 1;在其余5個數(shù)據(jù)集上WFSAM表現(xiàn)最優(yōu). (4)在OE指標(biāo)對比結(jié)果中,WFSAM在 Computers、Enron數(shù)據(jù)集上與MFML分別僅相差0.008 7、0.041 4;在其余4個數(shù)據(jù)集上WFSAM表現(xiàn)最優(yōu). 同時WFSAM的平均值也最優(yōu). 總體來說,在標(biāo)記缺失比率為20%時,WFSAM分類性能最優(yōu).

對表4分析可知:(1)在AP指標(biāo)對比結(jié)果中,WFSAM在Computers數(shù)據(jù)集上僅優(yōu)于MDDMproj和MLFRS;在Enron數(shù)據(jù)集上,WFSAM略差于其他7種算法,與最優(yōu)算法MDMR僅相差0.052 5;在其余4個數(shù)據(jù)集上WFSAM性能最優(yōu). (2)在RL和CV指標(biāo)對比結(jié)果中,WFSAM在Computers數(shù)據(jù)集上的RL結(jié)果與MDDMspc和MFML僅相差0.000 2,CV結(jié)果與MFML僅相差0.021 0;在Enron數(shù)據(jù)集上,WFSAM的RL和CV結(jié)果僅優(yōu)于MLFRS;在其余4個數(shù)據(jù)集上WFSAM表現(xiàn)最優(yōu). 同時WFSAM的平均值也最優(yōu). (3)在OE指標(biāo)對比結(jié)果中,WFSAM在Computers、Enron數(shù)據(jù)集上與最優(yōu)算法MLNB、MDDMspc分別僅相差 0.019 0、0.069 1;在其余4個數(shù)據(jù)集上WFSAM表現(xiàn)最優(yōu). 同時WFSAM的平均值也最優(yōu). 總體來說,在標(biāo)記缺失比率為40%時,WFSAM分類效果最佳.

對表5分析可知:(1)WFSAM在Enron數(shù)據(jù)集上的AP、RL和CV結(jié)果略次于MDMR,但在其余5個數(shù)據(jù)集上均取得最優(yōu)的分類效果. (2)在OE指標(biāo)對比結(jié)果中,WFSAM在Computers數(shù)據(jù)集上與MFML僅相差0.007 3;在Enron數(shù)據(jù)集上,與MDMR僅相差0.164 0;在其余4個數(shù)據(jù)集上WFSAM分類性能最佳. 同時WFSAM的平均值最優(yōu). 總體來說,在標(biāo)記缺失比率為60%時,WFSAM優(yōu)于其他對比算法.

綜上所述,根據(jù)表2-表5的結(jié)果,隨著標(biāo)記缺失比率的增加,所有算法分類效果均越來越差,標(biāo)記缺失時的分類效果明顯低于標(biāo)記完整時的分類效果,這充分說明標(biāo)記的有效利用有益于弱標(biāo)記特征選擇.

3.3 統(tǒng)計分析

本文使用Friedman和Bonferroni-Dunn測試[24-26]來分析所有實驗結(jié)果的統(tǒng)計意義,計算公式為:

(10)

(11)

式中,T表示不同評價指標(biāo)下總的數(shù)據(jù)集個數(shù),s表示算法的個數(shù),Ri表示某一算法在所有數(shù)據(jù)集上的平均排序.臨界距離[26]可以表示為:

(12)

式中,qα是測試的臨界列表值,α是Bonferroni-Dunn測試的重要度.

表6 Friedman測試的FF值(s=8且T=24)Table 6 FF of the Friedman test(s=8 and T=24)

表6展示了在不同的標(biāo)記缺失比率下統(tǒng)計計算的FF值.由表6分析可知,當(dāng)α=0.1時,Friedman檢驗下零假設(shè)被拒絕. 因而,可以利用Bonferroni-Dunn測試進一步比較8種算法在統(tǒng)計分析上的不同,進而討論算法之間的相對性能[7]. 為了直觀地顯示W(wǎng)FSAM與其他比較算法的相對性能,圖1呈現(xiàn)了8種算法在不同標(biāo)記缺失比率下的CD值,其中每個算法的平均排序沿數(shù)軸繪制,軸上的最小值位于左側(cè),因此,左側(cè)排序的算法更好[2-3,7]. 在圖1中,當(dāng)所有算法兩兩比較時,將沒有顯著差異的算法用粗線連接起來,如圖1(a)所示,WFSAM與MDDMspc、MLNB與MDDMproj之間有粗線相連,表明每對算法之間無顯著差異. 根據(jù)圖1可得:(1)標(biāo)記缺失比率為0%和60%時,WFSAM明顯優(yōu)于其他算法;(2)標(biāo)記缺失比率為20%和40%時,WFSAM略低于MFML,但與其余算法相比,優(yōu)勢仍然明顯. 綜上所述,在不同標(biāo)記缺失比率下,WFSAM與MFML效果大致相同,但優(yōu)于其他6種比較算法. 根據(jù)Bonferroni-Dunn測試,當(dāng)α=0.1,qα=2.45時,CD=1.732,其中s=8,T=24.

圖1 WFSAM與其他比較算法的Bonferroni-Dunn檢驗Fig.1 The Bonferroni-Dunn test of WFSAM against the other compared algorithms

4 結(jié)論

本文提出一種基于AP聚類和互信息的弱標(biāo)記特征選擇方法. 該方法在AP聚類的基礎(chǔ)上,結(jié)合剩余標(biāo)記信息和樣本相似性,對缺失標(biāo)記進行填補,使用標(biāo)記占比改進互信息,度量特征和標(biāo)記集的相關(guān)性,設(shè)計弱標(biāo)記特征選擇算法,搜索最優(yōu)特征子集. 在6個多標(biāo)記數(shù)據(jù)集上,與7種算法對比,實驗結(jié)果顯示,缺失標(biāo)記的填補技術(shù)和互信息的改進均是有效的. 但是,本文僅依靠特征和標(biāo)記集的相關(guān)性選擇特征子集,忽略了標(biāo)記間的依賴關(guān)系,因此,在未來的研究工作中,針對大規(guī)模復(fù)雜的弱標(biāo)記數(shù)據(jù)集,需要考慮標(biāo)記相關(guān)性,結(jié)合線性回歸、稀疏正則化等理論,進一步研究多標(biāo)記分類的弱監(jiān)督學(xué)習(xí)問題.