汪正凱,沈東升,王晨曦
(1.福建省粒計算及其應(yīng)用重點實驗室,福建 漳州 363000;2.閩南師范大學(xué) 計算機學(xué)院,福建 漳州 363000)
在傳統(tǒng)的單標記監(jiān)督學(xué)習(xí)中,樣本僅由一個標記屬性描述,這種假設(shè)常違背現(xiàn)實生活的真實情況。在一類非互斥屬性中,樣本的標記屬性可能同時包含多個語義信息,例如,一部電影可能是喜劇電影的同時也是愛情電影,在這種情況下,單一屬性標記無法有效地對樣本進行類別劃分,因此一種多標記學(xué)習(xí)框架[1-3]被提出。相對于單標記學(xué)習(xí),在多標記學(xué)習(xí)中,每一個樣本具有多個以上的屬性標記,在非分層任務(wù)中,樣本在屬性標記下僅有二值取值,即為正或負,將樣本所有標記中具有正值的標記稱為標記集合,樣本的標記集合即構(gòu)成了對樣本屬性的完整描述。隨著數(shù)據(jù)挖掘技術(shù)與移動互聯(lián)網(wǎng)技術(shù)的發(fā)展,數(shù)據(jù)的規(guī)模不斷增長,描述樣本屬性的標記集合的規(guī)模也隨之增長,而豐富的標記集合往往需要高維的特征空間描述[4]。但過高的特征維度會使得學(xué)習(xí)器的消耗提升,同時一些噪聲特征也會對分類結(jié)果產(chǎn)生影響,最終降低分類精度[5]。因此,高維特征帶來的維度災(zāi)難[6]已經(jīng)成為多標記學(xué)習(xí)面臨的重要挑戰(zhàn)之一。
作為一種有效的特征降維技術(shù),特征選擇[7]的目的是在保持學(xué)習(xí)器性能不改變太多的前提下能夠有效地約簡數(shù)據(jù)集的維度。目前,針對多標記學(xué)習(xí)任務(wù)的特征選擇算法已有很多,這些算法按照與學(xué)習(xí)器的關(guān)系可以分為過濾式[7-9]、包裝式[10]和嵌入式3 種。其中過濾式不依賴于學(xué)習(xí)器,而是尋找獨立指標來評價每個特征對分類能力的貢獻大小,以此過濾出含有更豐富信息的特征子集[11-12],或以某個評價指標結(jié)合搜索算法來搜索特征子集[13-14],前者需要預(yù)設(shè)閾值,而后者可根據(jù)搜索策略自動結(jié)束算法;相對于過濾式特征選擇算法,包裝式特征選擇算法以特征子集在分類器上的分類性能作為搜索指標指導(dǎo)搜索方向,嵌入式特征選擇算法在進行特征選擇的過程中即同時進行了學(xué)習(xí)器的訓(xùn)練。因此,在算法運行時間和計算資源的消耗以及模型的普適性上,過濾式特征選擇算法具有更大的優(yōu)勢。
Fisher Score(FS)作為一種基于距離度量的特征評價指標,通過計算類間散度與類內(nèi)聚度的關(guān)系度量特征分類能力的強弱,在單標記監(jiān)督學(xué)習(xí)中已有了較多的研究與應(yīng)用。XIE 等[15]提出一種基于改進的F-score 和支持向量機的包裝式特征選擇方法,以SVM 分類器的分類結(jié)果指導(dǎo)搜索方向;SONG 等[16]提出了不均勻分布下的FS 特征選擇算法,以兩兩類別之間的距離代替類與總體中心的距離作為類間散度的計算方式;MUHAMMED[17]等提出一種結(jié)合FS評價準則和貪心搜索的特征選擇算法,在阿爾茨海默病的分類上取得了較好的結(jié)果;SONG[16]等提出一種基于Fisher 判別分析(FDA)和F-score 的特征排序方法用以多類樣本分類,BEHESHTI[18]提出一種集合FS 評價準則和T 檢驗分數(shù)來尋找最優(yōu)的特征集的特征選擇算法。
然而,以上的算法都忽略了樣本極值對類中心帶來的偏差影響,以距離度量的類中心的意義僅在統(tǒng)計學(xué)上得以體現(xiàn),在實際應(yīng)用中很容易被異常值影響,當(dāng)方差很小的一類樣本中加入一個相對量綱較大的樣本時,會使得該類樣本的中心發(fā)生偏移,此時需要對該異常值進行處理以避免最終FS 得分產(chǎn)生誤差。同時,上述算法都僅能應(yīng)用于單標記特征選擇,而多標記任務(wù)更能體現(xiàn)生活中的實際情況,因此將單標記任務(wù)下的FS 算法應(yīng)用于多標記任務(wù)具有一定的實際研究意義。基于此,本文提出一種多標記FS 特征選擇算法,計算每個樣本在各個標記下經(jīng)過去極值后的特征集合的FS 得分,若多標記任務(wù)中標記包含信息對分類的貢獻,則根據(jù)樣本具有的標記數(shù)量可以得到該樣本標記集合的標記權(quán)值,以此更新樣本在特征空間下的FS 得分。
FS 是一種經(jīng)典的評價特征對分類貢獻能力的指標,特征的FS 得分越高,表明在該特征下類內(nèi)樣本間間距盡可能得小,類間樣本間距盡可能得大,即類間樣本間距與類內(nèi)樣本間距的比值越大。在傳統(tǒng)單標記學(xué)習(xí)中FS 的相關(guān)描述如下:
disinner和disouter分別表示在特征fj下所有類別的類內(nèi)距離與所有類與樣本中心類間距離的和,可分別稱為特征fj下的類內(nèi)聚度與類間散度。當(dāng)類內(nèi)聚度越小時,樣本類內(nèi)分布越稠密,類間散度越大,樣本類間分布越稀疏,由于特征辨識類別的能力與該特征下的類間散度和類內(nèi)聚度比值成正相關(guān),則定義特征fj對類別辨識的能力評價指標FS 如下:
式(3)為單個特征下的FS 得分計算公式,若以單個特征的FS 得分作為評價指標,則可計算出所有特征的FS 得分,通過設(shè)置閾值篩選出特征子集。若采用啟發(fā)式搜索的方式篩選特征子集,則需要設(shè)置合適的搜索策略,不斷迭代搜索當(dāng)前候選子集中的最優(yōu)特征,直至滿足搜索終止條件,得到最終的特征子集。相對于啟發(fā)式搜索,前者的時間復(fù)雜度更低,算法性能消耗更少。
式(3)給出了在單標記學(xué)習(xí)下任意特征的FS 得分的計算公式,但都是直接對一類樣本計算其均值作為類中心,并沒考慮到極值帶來的方差增大的影響,假設(shè)某一特征下所有樣本的劃分情況如圖1 所示。其中,直線兩邊表示各自不同的一類樣本,圓圈選中的樣本代表多數(shù)真實樣本的分布,圓圈的圓心代表這些樣本的中心點,而圓圈外樣本會使得類樣本的中心點發(fā)生偏移,極端值樣本距離多數(shù)樣本越遠,偏移程度越大,而在理想狀況下是同類樣本盡可能分布在一起,因此,需要根據(jù)類別樣本的分布情況對已劃分的樣本進行處理,去除其中距離多數(shù)樣本較遠的樣本,再對剩下的樣本進行FS 得分計算。
圖1 類中心偏差示意圖Fig.1 Schematic diagram of class center deviation
同時式(3)僅能應(yīng)用于單標記特征選擇,但在更復(fù)雜的多標記學(xué)習(xí)中,式(3)無法直接應(yīng)用,若將多標記任務(wù)簡單地分解為多個單標記任務(wù)再應(yīng)用式(3),則會損失多標記任務(wù)中標記集合之間的關(guān)聯(lián)信息,基于此,考慮從樣本角度對標記集合進行遍歷,且針對各個標記對整體標記集合的貢獻值,將樣本的標記集合下的全體特征的FS 得分與根據(jù)樣本本身具有的標記集合所得出的標記權(quán)值系數(shù)相乘,以此更新FS 的計算公式。
下文將給出相關(guān)定義來描述本文算法模型。假設(shè)存在一個決策系統(tǒng)其中論域U={x1,x2,…,xn}∈?n×m為全體樣 本組成的 非空有限 集合,xi∈U是維度為1×m的一維向量,表示論域U中的第i個樣本,A={f1,f2,…,fm}為全體特征組成的集合,fj∈A表示特征集合中第j個特征,為論域U中的一個實值,表示樣本xi在特征fj下的取值,D={y1,y2,…,yn}∈?n×l為樣本的標記集合,yi∈D是維度為1×l的一維向量,表示標記集合D中第i個樣本xi在全體決策屬性上的標記結(jié)果為xi在第k個標記上的標記結(jié)果,在多標記學(xué)習(xí)中,xi在標記k下被標記時,反之=0,且對任意 一個樣本xi,有≥1。綜合上述條件,有如下定義:
定義1假設(shè)存在一個隨機樣本xi∈U,xi的標記集合為yi,定義xi在標記空間上的真實標記集合y_truei如下:
定義2假設(shè)存在一個隨機樣本xi∈U,xi的真實標記集合為y_truei,對任意標記k∈y_truei,則標記k將論域U劃分如下:
其中:c表示樣本xr在標記k下的值表示論域U中在標記k下具有值為c的樣本組成的集合。
xi的真實標記集合y_truei對論域U的劃分結(jié)果分布如下:
定義3假設(shè)存在一個隨機樣本xi∈U,有一個劃分情況Uk∈Ui,Uk中的任意一類樣本集合在特征fj下的均值如下:
定義4假設(shè)存在一個隨機樣本xi∈U,在標記k劃分的論域空間中存在一個樣本類別集合,其中距離該類中心點最遠的一個樣本為xmax,則定義該類中心點的有效樣本集合如下:
其中:dis_xmax表示xmax距離中心點的距離;δ∈(0,1]表示半徑系數(shù),且δ和樣本數(shù)量正相關(guān),當(dāng)δ=1 時,即相當(dāng)于不做中心偏移操作。
定義5假設(shè)存在一個隨機樣本xi∈U,有劃分情況Uk∈Ui,Uk中任一類樣本集合在特征fj上經(jīng)過中心偏移之后的樣本集合為,則特征fj在隨機樣本xi的標記k劃分論域U加中心偏移處理之后的FS 得分如下:
其中:分子表示類間散度,相對于原始的每一類減去總體中心,在類別之間計算距離可以避免不均勻分布情況下的類間散度差異表示隨機樣本xi的標記k的權(quán)值系數(shù),為k與xi的真實標記集合y_truei中的其余標記的余弦系數(shù)的和再加1,如果樣本只具有1 個標記,則為1,可以理解為標記k與其余標記的額外信息,顯然隨機樣本的真實標記數(shù)量越多,任一標記k的權(quán)值系數(shù)越大,因為標記數(shù)量越大,其中包含的分類信息應(yīng)當(dāng)更多,所以FS 分數(shù)計算更加重視具有更多標記的情況。
定義6假設(shè)存在一個隨機樣本xi∈U,xi的真實標記集合為y_truei,根據(jù)式(11)得出特征fj在xi的標記k上的FS 得分,則定義fj在整體標記集合y_truei上的FS 得分如下:
根據(jù)式(12)可得出特征fj在全體樣本上的FS得分如下:
式(13)是單個特征的FS 得分,則最終全體特征集合A的FS 得分為:
式(14)為全體特征的FS 得分分布,對FS 進行降序可以得到分類能力更強的特征,從而實現(xiàn)特征選擇的目標。
上述定義中之所以采用全體采樣,是因為對全體樣本的遍歷使得所提算法的結(jié)果具有較強的魯棒性,避免隨機采樣所導(dǎo)致結(jié)果產(chǎn)生不確定性。定義3和定義4 對一類樣本進行了中心偏移操作,前提是該類樣本數(shù)量較多,因為數(shù)量較少時,并不足以準確地決定多數(shù)樣本的類中心,但并不是全部數(shù)據(jù)集中每個標記下每類的樣本數(shù)量都足夠多,基于此在后續(xù)實驗中進行到中心偏移操作前都會對該類樣本數(shù)量進行檢測,當(dāng)該類樣本數(shù)量占總體樣本數(shù)量比例小于0.05 時,即不進行中心偏移操作。式(11)中類間散度計算沒有采用原始FS 計算類間散度的方式,而是改用了文獻[18]中提出的方式,該計算方式如式(15)所示:
其中:D(fi)表示特征fi的類間散度;p、q分別表示類別p和類別q;np表示類別p的數(shù)量;N為全體樣本數(shù)量;表示類別p在特征fi上的均值。可以看出,式(15)是采用類別間的序關(guān)系來實現(xiàn)類別間的兩兩距離計算,以避免類間重復(fù)計算。本文模型的算法流程如算法1 所示。
算法1MLFS 算法
在算法MLFS 中,主要的計算消耗在于對每個標記k計算其FS 得分,若假設(shè)某數(shù)據(jù)集有n個樣本、m個特征和l個標記,平均每個樣本在標記空間上的標記數(shù)量為LC,則計算全體特征的FS 得分的代價為O(m),步驟3 計算全體標記下的FS 得分的代價為O(m·l),步驟4~步驟6 并沒有太多計算消耗,計算代價為O(n·LC),步驟7 的排序代價為O(mlogam),算法MLFS 的主要計算消耗在于計算每個標記下的FS 得分,且并不依賴于任何分類器。
為驗證本文算法的有效性,選取MuLan 庫中的8 個公開多標記數(shù)據(jù)集進行實驗。由于數(shù)據(jù)集在MuLan 庫中已經(jīng)分好,訓(xùn)練集和測試集會直接采用已經(jīng)分好的結(jié)果,在訓(xùn)練集中對所提算法進行特征選擇,再將特征選擇結(jié)果應(yīng)用于測試集進行分類測試,數(shù)據(jù)集的詳細信息如表1 所示。
表1 多標記數(shù)據(jù)集Table 1 Multi-label datasets
實驗運行環(huán)境為Pycharm Professional 2019.2.3+Python 3.7.1 64 位,硬件環(huán)境 為Inter?Xeon?CPU E5-26xx series 2.49 Hz,16 GB內(nèi)存,操作系統(tǒng) 為Windows10 64 位。實驗采用5 種評價指標[14]:Average Precision,Hamming Loss,One Error,Ranking Loss,Coverage,分別簡寫為AP、HL、OE、RL、Cov,其中,HL、OE 的計算基于標記預(yù)測,AP、RL、Cov 基于標記排序,AP 指標表示數(shù)值越高,分類性能越好,其余指標表示數(shù)值越低,分類性能越好。
本文算法是通過設(shè)置半徑系數(shù)δ來選擇有效樣本集合的,因此不同大小的半徑系數(shù)會選取不同規(guī)模的樣本集合,實驗會首先比較不同大小的半徑系數(shù)對實驗結(jié)果產(chǎn)生的影響。
為比較本文算法的有效性,選擇了各類型的多標記特征選擇算法作為對比算法,分別為基于蟻群優(yōu)化的多標簽特征選擇算法(MLACO)[19]、多標記ReliefF 特征選擇算法(MLRF)[8]、基于多變量互信息的多標記特征選擇算法(PMU)[9]和多標簽樸素貝葉斯分類的特征選擇算法(MLNB)[14],其中MLACO為PANIRI 等提出的一種基于蟻群算法(ACO)的多標記特征選擇算法,通過同時引入計算標記相關(guān)性的有監(jiān)督啟發(fā)式函數(shù)與計算特征空間冗余性的無監(jiān)督啟發(fā)式函數(shù)在特征空間迭代搜索最優(yōu)子集,是一種最新的性能優(yōu)異的多標記特征選擇算法;MLRF算法是基于距離度量的多標記ReliefF 算法,通過引入漢明距離在標記集合上尋找樣本的同類與異類近鄰;PMU 算法是LEE 等提出的基于互信息度量的特征選擇算法,通過三元互信息度量特征子集與標記集合間的相關(guān)性;MLNB 是ZHOU 等提出的基于主成分提取PCA 和遺傳算法(GA)的混合型特征降維算法。
上述算法兼顧各種類型,便于本文所提算法與各類型算法進行比較。在對比算法的參數(shù)設(shè)置上,MLACO 算法參數(shù)與原文保持不變;MLRF 采用全體采樣方式,近鄰個數(shù)設(shè)為5;PMU 算法需要先進行離散化,以PMU 算法離散化方式為標準對實驗數(shù)據(jù)預(yù)先進行了兩折離散化;MLNB 設(shè)置一階段預(yù)留特征比例ratio 為0.7,平滑因子默認為1。在特征數(shù)量的選擇上,由于MLNB 算法可以直接得到一個特征子集,而其他算法得到排序后的特征集,則按照MLNB算法得到的特征子集數(shù)量,在其他算法排序后的特征子集上取相同數(shù)量的特征子集進行對比。
此外,實驗所采用的分類器為MLKNN[20]分類器,默認近鄰個數(shù)為10,平滑因子為1。
本文首先比較所提算法中參數(shù)δ對實驗結(jié)果的影響,由于δ是一類樣本中心點選擇樣本的距離范圍占一類樣本中距離該類樣本中心點最遠的樣本到中心點的距離的比例,實驗設(shè)置3 個數(shù)據(jù)集在δ∈(0,]1 上進行實驗,實驗結(jié)果如圖2 所示。
圖2 各數(shù)據(jù)集上不同半徑系數(shù)隨著特征比例變化的情況Fig.2 Variation of different radius coefficients with feature proportion on each datasets
圖2 中選擇 了Computer、Health、Recreation 3 個數(shù)據(jù)集,在每一類數(shù)據(jù)集中,橫線表示不做中心偏移的算法取全部特征的分類結(jié)果。可以看出,在文本類數(shù)據(jù)集中,基本符合半徑系數(shù)越大分類性能越好的預(yù)期,這是由于文本類數(shù)據(jù)集中特征空間較為稀疏,在半徑系數(shù)較小時會損失多數(shù)樣本,而期望效果是僅去除小部分極端值樣本,因此分類結(jié)果較差。隨著半徑系數(shù)的增大,Computer 數(shù)據(jù)集中分類性能逐漸提升,而其余數(shù)據(jù)集中并沒有很明顯的變化,這是由于半徑系數(shù)是基于離類中心點最遠樣本的比例確定的,可能存在一種情況,當(dāng)該樣本離類中心點足夠遠時,此時半徑系數(shù)選擇0.5 或者0.9,而篩選的樣本數(shù)量是一樣的,對于這種情況,可以選擇加入數(shù)量判定,當(dāng)不同比例下半徑系數(shù)篩選的樣本數(shù)量不變時,選擇原有類別樣本數(shù)量的80%或者90%作為新的一類樣本。但所提的算法模型是基于全體樣本遍歷的,且在多標記任務(wù)下每個標記的劃分情況不同,盡管上述異常情況可能出現(xiàn),但在全體樣本數(shù)量n×LC(LC 為每個樣本的平均標記數(shù)量)個標記的平均下,異常情況的影響會盡可能地被降低,因此所提算法沒有加入數(shù)量篩選這一步驟。
綜合以上分析可以得出,半徑系數(shù)的確定需要預(yù)先知道平均類樣本的分布情況,而在多數(shù)文本數(shù)據(jù)集中,特征空間是較為稀疏的,這使得在文本數(shù)據(jù)集中可以預(yù)先設(shè)定較大的半徑系數(shù),基于此,在后續(xù)實驗中,將所有實驗數(shù)據(jù)集的半徑系數(shù)設(shè)定為0.9。
為了更加詳細地驗證所提算法的有效性,將所提算法與4 種對比算法在所有數(shù)據(jù)集中進行實驗,實驗結(jié)果如表2~表7 所示,其中加粗字體為結(jié)果最優(yōu)。
表2 各數(shù)據(jù)集選擇特征數(shù)Table 2 Numbers of selected features of each datasets
表3 AP 評價指標下各算法的性能比較Table 3 Performance comparison of each algorithms under AP evaluation index
表4 HL 評價指標下各算法的性能比較Table 4 Performance comparison of each algorithms under HL evaluation index
表5 Cov 評價指標下各算法的性能比較Table 5 Performance comparison of each algorithms under Cov evaluation index
表6 OE 評價指標下各算法的性能比較Table 6 Performance comparison of each algorithms under OE evaluation index
表7 RL 評價指標下各算法的性能比較Table 7 Performance comparison of each algorithms under RL evaluation index
由以上實驗結(jié)果可以看出,本文MLFS 算法在Art、Business、Computer、Education、Enter、Health、Recreation、Reference 等8 個數(shù)據(jù)集中的各項指標的平均值都為最優(yōu),表明所提算法在整體上相對其余算法具有一定優(yōu)勢,對比各個指標可以發(fā)現(xiàn):
1)在AP 指標上,MLFS算法僅在Reference 數(shù)據(jù)集中排名第2,在其余數(shù)據(jù)集中都是排名第1,且平均排序結(jié)果排名第1。綜合比較4 種對比算法,MLFS 算法選擇的特征子集分類性能達到最優(yōu)。
2)在HL 指標上,MLFS 算法僅 在Computer 數(shù)據(jù)集中排名第2,在其余數(shù)據(jù)集中都是排名第1,且平均排序結(jié)果排名第1。綜合比較4 種對比算法,MLFS 算法選擇的特征子集分類性能達到最優(yōu)。
3)在Cov 指標上,MLFS 算法僅在Art、Health 數(shù)據(jù)集中排名第2,在其余數(shù)據(jù)集中都是排名第1,且平均排序結(jié)果排名第1。綜合比較4 種對比算法,MLFS 算法選擇的特征子集分類性能達到最優(yōu)。
4)在OE 指標上,MLFS 算法僅在Reference 數(shù)據(jù)集中排名第2,在其余數(shù)據(jù)集中都是排名第1,且平均排序結(jié)果排名第1。綜合比較4 種對比算法,MLFS 算法選擇的特征子集分類性能達到最優(yōu)。
5)在RL 指標上,MLFS 算法在Art、Computer、Health 數(shù)據(jù)集中排名第2,在其余數(shù)據(jù)集中都是排名第1,且平均排序結(jié)果排名第1。綜合比較4 種對比算法,MLFS 算法選擇的特征子集分類性能達到最優(yōu)。
6)在約簡特征數(shù)量上,MLFS 算法相對于原始特征空間約簡了70%以上的特征比例仍具有較好的效果,表明所提算法實現(xiàn)了特征選擇的降維目標。
7)綜合比較8 個數(shù)據(jù)集在5 個指標上的40 種分類情況,所提算法MLFS 具有最優(yōu)結(jié)果的有32 種,占比80%,表明所提算法具有較好的穩(wěn)定性。
上述實驗結(jié)果表明,所提算法選擇的特征子集在后續(xù)的分類結(jié)果的各個指標上相比其余4 種算法具有領(lǐng)先優(yōu)勢,同時具有較高的約簡比例,驗證了所提算法的有效性和魯棒性。
為避免出現(xiàn)局部優(yōu)勢帶來的誤差影響,下文將給出部分數(shù)據(jù)集各特征選擇算法在不同特征比例下的分類情況,由于所選數(shù)據(jù)集較多,且針對每一種指標共有40 種對比情況,限于篇幅,只選擇了其中6 個數(shù)據(jù)集在5 種指標上的結(jié)果進行展示,其中,MLNB算法因為只能得到一個特征子集,并不能與其他算法一起比較特征比例上的分類性能,所以未給出變化情況。變化趨勢如圖3~圖7 所示。
圖3 AP 評價指標下各算法分類性能的變化情況Fig.3 Change situation of classification performance of each algorithms under AP evaluation index
圖4 HL 評價指標下各算法分類性能的變化情況Fig.4 Change situation of classification performance of each algorithms under HL evaluation index
圖5 Cov 評價指標下各算法分類性能的變化情況Fig.5 Change situation of classification performance of each algorithms under Cov evaluation index
圖6 OE 評價指標下各算法分類性能的變化情況Fig.6 Change situation of classification performance of each algorithms under OE evaluation index
圖7 RL 評價指標下各算法分類性能的變化情況Fig.7 Change situation of classification performance of each algorithms under RL evaluation index
從圖3~圖7 的變化趨勢可以看出:本文算法MLFS在各個指標上均優(yōu)于其余算法,且在AP、HL 指標中的優(yōu)勢較為明顯,在其余指標中除MLACO 算法外,均大幅優(yōu)于其余算法。在選取的特征比例上,本文算法在特征比例較小時即能達到較好的分類性能,表明本文算法基本能夠?qū)崿F(xiàn)特征選擇的目標。
為從統(tǒng)計學(xué)意義上進一步檢測所提算法與4種對比算法在各項指標上是否存在顯著差異,將采用顯著 性水平為10% 的Nemenyi test[18]對所提算法和其余算法進行比較。根據(jù)表3~表7 獲得各個算法在所有數(shù)據(jù)上的平均排序,排序結(jié)果如表8所示。
表8 各算法在不同評價指標下的平均排序Table 8 Average ranking of each algorithm under different evaluation indexes
在表8 中,若2 個算法在所有數(shù)據(jù)集上的平均排序的差值小于臨界差值(Critical Difference,CD),則認為2 個算法并沒有性能上的顯著性差異,由于實驗所采用數(shù)據(jù)集個數(shù)為8,總算法個數(shù)為5,根據(jù)臨界差值計算公式可以得出CD 為1.944,則根據(jù)臨界差值給出各算法在不同指標上的臨界差值圖,其中算法根據(jù)平均排名在坐標軸中由左向右排列,且與所提算法沒有明顯性能差異的算法用一根加粗的實線相連,臨界差值如圖8 所示。從圖8 可以看出,本文算法在5 種評價指標中性能均排名第1,在除RL指標外的其余指標中,本文算法與MLNB、PMU、MLRF 算法具有顯著的性能差異,與MLACO 算法沒有顯著差異,在RL 指標中,本文算法與MLNB、MLRF 算法具有顯著的性能差異,與PMU、MLACO算法沒有顯著的性能差異。綜合上述情況,本文算法與4 種對比算法的統(tǒng)計結(jié)果中,性能處于最優(yōu),表明所提算法的有效性和魯棒性。
圖8 各算法綜合性能比較Fig.8 Comprehensive performance comparison of each algorithms
此外,由于不同的特征選擇算法應(yīng)有其適用的學(xué)習(xí)任務(wù),在實際應(yīng)用中應(yīng)根據(jù)不同的情況選擇適合的算法。在上述實驗中,本文算法與其他算法均是在Yahoo網(wǎng)頁文本數(shù)據(jù)集上進行實驗,數(shù)據(jù)類型較為單一,為驗證所提算法的普適性,本文選擇2 個不同類型的數(shù)據(jù)集Scene 和Yeast 進行實驗。Scene 數(shù)據(jù)集是一類語義索引類圖像數(shù)據(jù)集,樣本數(shù)為2 407,特征數(shù)為294,標記數(shù)為6,Yeast是一類關(guān)于酵母菌基因的生物數(shù)據(jù)集,樣本數(shù)量為2 417,特征數(shù)為103,標記數(shù)為14。由于未知數(shù)據(jù)集特征空間的密集程度,因此無法事先確定所提算法中的半徑系數(shù)δ,基于此,測試3 個不同尺度的半徑系數(shù),分別為0.1、0.5、0.9,將3 種不同的半徑系數(shù)作為算法的參數(shù)與4 種對比算法在Scene 和Yeast 數(shù)據(jù)集上進行了實驗,實驗結(jié)果如圖9 所示。從圖9 可以看出:并不是半徑系數(shù)越大越好,因為相對于特征空間較為稀疏的文本類數(shù)據(jù)集,Scene 數(shù)據(jù)集上的樣本分布更為密集,較小的半徑系數(shù)已足以覆蓋類別中多數(shù)樣本。半徑系數(shù)越大,整體類別中心點產(chǎn)生的偏移越大,分類結(jié)果就越差,而Yeast 數(shù)據(jù)集上半徑系數(shù)為0.5 時分類性能相對最優(yōu),這與數(shù)據(jù)集本身樣本的分布有關(guān),當(dāng)半徑系數(shù)為0.5 時篩選的樣本集合的類中心與預(yù)期樣本的類中心距離最近,此時半徑系數(shù)過小或過大都會影響最終的分類性能。在與對比算法比較中可以發(fā)現(xiàn),當(dāng)特征數(shù)量較少時,PMU 算法性能最優(yōu),而在文本類數(shù)據(jù)集中表現(xiàn)優(yōu)異的MLFS 和MLACO 算法性能反而較差,這說明不同的特征算法應(yīng)該選擇其適用的學(xué)習(xí)任務(wù),對于所提算法應(yīng)更適用于文本類數(shù)據(jù)集,而對于非文本類數(shù)據(jù)集,則需要預(yù)先分析其數(shù)據(jù),獲取標記劃分下樣本的分布情況,然后根據(jù)確定的半徑系數(shù)進行特征選擇。
圖9 非文本數(shù)據(jù)集的AP 指標比較Fig.9 Comparison of AP index in non text datasets
此外,對于非文本類數(shù)據(jù)集,可以使用基于距離排序的方式去除極值樣本,以此避免未知樣本分布情況下的半徑系數(shù)的確定問題。距離排序是指對某一類樣本中每一個樣本到該類樣本中心點的距離進行排序,然后去除恒定數(shù)量的樣本。相對于半徑系數(shù)的方式,距離排序的計算復(fù)雜度較高。假設(shè)現(xiàn)在存在某一類樣本,該類樣本數(shù)量是n個,經(jīng)過計算存在一個極值點樣本距離該類樣本中心點最遠,那么以該極值點到類樣本中心點的距離乘以某一比例δ得到距離r,并以類樣本中心點為圓心,以r為半徑去構(gòu)造圓,顯然在圓外的是需要去除的樣本,這里的計算復(fù)雜度主要在于找到最大距離的樣本以及遍歷該類樣本集合中的每個樣本,判斷每個樣本的距離與r的關(guān)系,前者最壞情況下的時間復(fù)雜度為O(n),后者的時間復(fù)雜度也為O(n),則總的時間復(fù)雜度為2O(n)。對于距離排序的方式,假設(shè)條件不變,則需要對樣本集合中所有樣本進行距離排序,再根據(jù)給定的去除樣本的數(shù)量去除距離最大的一些樣本,則最壞情況下的時間復(fù)雜度為O(n2),顯然半徑系數(shù)的方式在計算復(fù)雜度上要優(yōu)于距離排序的方式,所以在比較好確定半徑系數(shù)的稀疏類文本數(shù)據(jù)集中采用半徑系數(shù)的方式去去除極值樣本來減少計算消耗,而在不好確定半徑系數(shù)的非文本類數(shù)據(jù)集中采用距離排序的方式。為了驗證距離排序的效果,選擇了兩個較小的非文本類數(shù)據(jù)集Birds、Emotion 數(shù)據(jù)集來進行實驗。其中Birds 數(shù)據(jù)集是記錄鳥的叫聲的數(shù)據(jù)集,有645 個樣本、260 個特征、20 個標記;Emotion 數(shù)據(jù)集是音樂情感類數(shù)據(jù)集,有593 個樣本、72 個特征、6 個標記。實驗中設(shè)去除樣本的比例占該類樣本集合的10%,實驗結(jié)果如圖10 所示。
圖10 基于距離排序的模型與對比算法的AP 指標比較Fig.10 AP index comparison between model based on distance ranking and comparison algorithms
從圖10 可以看出,本文算法在特征比例較少時并沒有顯著優(yōu)勢,但是隨著特征比例逐漸提升,分類性能逐漸提高。在Birds 數(shù)據(jù)集中當(dāng)特征比例超過0.45 時即超過原始特征下的分類性能,且在特征比例為0.6 時達到最優(yōu),同時領(lǐng)先其余算法;在Emotion數(shù)據(jù)集中當(dāng)特征比例超過0.35 時即超過原始特征下的分類性能,且在特征比例為0.9 時達到最優(yōu),同時領(lǐng)先其余算法。這表明所提算法在使用距離排序去除極值樣本上具有一定效果,能夠一定程度應(yīng)用在非文本數(shù)據(jù)集上。
綜上實驗可以得出,本文算法主要適用在樣本分布較為稀疏的文本類數(shù)據(jù)集上,在此類數(shù)據(jù)集上,每一維特征的重要度都較小,但是卻可能與標記集合中某一個標記有關(guān)聯(lián)信息,所以無法輕易去除特征。而本文算法能夠有效計算每一維特征下樣本被標記劃分后的兩類樣本的區(qū)分程度,根據(jù)區(qū)分程度可以過濾出對整體分類貢獻能力弱的特征,但本文算法的局限性在于無法去除特征子集中的冗余特征,當(dāng)數(shù)據(jù)集中存在大量冗余特征時,本文算法將無法有效地應(yīng)對這種情況。
本文通過改進單標記下的FS 計算方式,去除一類樣本中的極端值,使得在統(tǒng)計意義上的樣本中心更符合實際生活中的樣本集合,即通過原始數(shù)據(jù)的中心偏移完成樣本的過濾,并結(jié)合標記的權(quán)值系數(shù),將其應(yīng)用于多標記任務(wù)。實驗結(jié)果證明了所提算法具有一定的有效性和魯棒性。但本文在實驗過程中還存在算法難以適用較密集數(shù)據(jù)集,以及對于多標記權(quán)值系數(shù)的確定較為簡單等問題,這將是下一步需要完善的工作。