張海翔,李培培,胡學鋼

(1.蚌埠醫(yī)學院附屬合肥市第二人民醫(yī)院 訊息處,安徽 合肥 230012;2.合肥工業(yè)大學 大數(shù)據(jù)知識工程教育部重點實驗室,安徽 合肥 230601)

0 引 言

多標簽分類處理特征數(shù)據(jù)對應多個標簽問題[1-4]。例如老年人群體就醫(yī)時可能患有多種常見基礎病:高血壓、糖尿病、血脂異常等。藥物治療時遺漏病因或過敏史都將產(chǎn)生嚴重醫(yī)療事故。同時多標簽數(shù)據(jù)通常伴有高維度、冗余特性,在分類過程耗費更多時間和空間,分類精準度也會受到影響[5]。因而,在多標簽學習預處理階段需要采取特征降維操作。

特征降維方法分為兩種:特征提取和特征選擇。特征提取方法[6]將原空間映射或變換低維空間,該過程會破壞數(shù)據(jù)特征的原有結構,不利于后續(xù)操作。特征選擇方法[7-8]從原空間提取具有代表意義的特征子集,保留原特征空間結構,分類時可直觀體現(xiàn)性能與特征的關系,常見方法如:過濾器、包裝器和嵌入技術。過濾技術[9-11]獨立于算法根據(jù)訓練數(shù)據(jù)的一般特性(如互信息、粗糙集理論)選擇合適特征,基于一組標準對特征進行評分刪除評分較低的特征。包裝器技術[12]利用一個特定的算法作為特征選擇過程的組成部分其結果更有效,但該方法耗時較長。嵌入式技術[13]將特征選擇過程集成到學習模型的構建中,需要迭代矩陣反演計算。以上方法考慮數(shù)據(jù)事先全部獲取,現(xiàn)實數(shù)據(jù)并非一次性全部到來。例如,隨時間推移和用藥影響患者病情和生命體征在不斷變化,傳統(tǒng)離線批處理特征降維方法無法滿足病情診斷精準判斷[14]。

流特征選擇方法隨著時間推移,特征一個接一個地流入,必須在每個時間戳中決定保留還是丟棄新到達的特征,并且在學習之前不知道整個特征空間的信息,最終從已到來數(shù)據(jù)中選出代表特征子集。例如,利用模糊互信息作為相關性和冗余度評價指標的OSFS(在線流特征選擇)[15]方法,該方法包括兩個步驟:在線相關性分析決定最新到來的特征是否保留或丟棄;在線冗余分析去除已選特征子集中的冗余特征。根據(jù)這兩步分析原理,OM-NRS[16]用鄰域粗糙集代替模糊互信息作為評價指標。I-SFS[17]基于互信息的相關性和冗余度,利用多目標布谷鳥搜索技術優(yōu)化兩個目標,但以上多標簽流特征方法需要預先設定參數(shù)值,不同數(shù)據(jù)集上如何確定統(tǒng)一參數(shù)閾值存在一定困難?；诟倪M鄰域粗糙集的多標簽流特征選擇方法(ML-OFS-ANRS[18])采用新的GAP鄰域關系,在學習前不需要域信息,也不需要預先指定任何參數(shù),采用最大依賴和最大重要性標準進行特征冗余分析,且該方法的重要性最優(yōu)閾值參數(shù)對不同數(shù)據(jù)集需要設置不同值。

基于此,該文提出自適應密度鄰域關系的多標簽在線流特征選擇方法(ML-OFS-ADNR),在依賴關系計算時根據(jù)周圍實例的密度信息自動確定鄰域個數(shù),不需要預先指定任何參數(shù)。同時采用模糊等價約束方法可以挑選出高依賴度低冗余度的特征,使得所選特征子集規(guī)模較小且具有判別性。迭代執(zhí)行以上步驟,直到數(shù)據(jù)全部到來。該文主要貢獻如下:(1)基于鄰域粗糙集理論,提出自適應密度鄰域關系的多標簽在線流特征選擇方法(ML-OFS-ADNR),該方法在特征依賴計算時無需領域知識;(2)根據(jù)周圍實例的密度信息提出新的鄰域關系,利用該關系可以在在線特征選擇過程中自動選擇適當數(shù)量的鄰域,不需要預先指定任何參數(shù);(3)ML-OFS-ADNR采用模糊等價約束進行冗余分析,使所選特征子集具有較低的冗余度?；诖植诩奶卣鬟x擇方法通常采用特征顯著性等于零的條件進行特征冗余分析。然而,在真實的數(shù)據(jù)集中,完全相等的約束過于嚴格。在模糊等價約束下,可以考慮更多的候選特征進行特征冗余分析,使得最終選擇的特征子集小且具有鑒別性。10個基準數(shù)據(jù)集實驗結果顯示,ML-OFS-ADNR在相同數(shù)量的特征下,比傳統(tǒng)特征選擇方法和現(xiàn)有在線流特征選擇方法具有更好的性能。

1 相關工作

1.1 批處理特征選擇方法

特征選擇在處理高維數(shù)據(jù)上可以實現(xiàn)更快的模型訓練,降低過擬合的敏感性,抵消維數(shù)災難帶來的影響,減少數(shù)據(jù)分析期間的存儲、內(nèi)存資源消耗。近十年來,研究人員提出許多離線環(huán)境下的降維方法,可分為特征提取[19-20]和特征選擇[21]。前者是通過對原始特征進行線性或非線性組合來構造一些輔助特征,后者是從給定原始特征中選擇最具區(qū)分能力的子集。根據(jù)標簽分類應用場景又可分為單標簽特征選擇和多標簽特征選擇[22]。然而上述大多數(shù)方法考慮離線環(huán)境下,數(shù)據(jù)全部已知的批處理模式,在流特征環(huán)境中這些批處理方法無法直接應用,該環(huán)境下數(shù)據(jù)集無法一次性全部獲取,無法提前獲取全部數(shù)據(jù)信息。為增強學習模型的可解釋性,便于在現(xiàn)實環(huán)境中廣泛應用,研究人員更加重視特征選擇方法,進一步從靜態(tài)數(shù)據(jù)擴展到流數(shù)據(jù)環(huán)境[15]。

1.2 多標簽流特征選擇方法

流數(shù)據(jù)環(huán)境下特征會隨著時間的推移到來(理論上無限制),在按順序提取新特征的過程中還要剔除已到來特征數(shù)據(jù)的冗余,確保每一輪獲得最優(yōu)特征子集。已有多標簽流特征選擇方法包括OMGFS[23]和ML-OFS-ANRS[18],SFSCI[24],PSO[10],G-SFS[17]。OMGFS基于鄰域對稱不確定性和鄰域互信息,考慮在線特征固有群結構,根據(jù)不同數(shù)據(jù)集類型設置相關性參數(shù)閾值。ML-OFS-ANRS提出新的GAP鄰域在線流特征方法,采用最大依賴最大重要性進行特征冗余分析,對數(shù)據(jù)集環(huán)境要求較高,且重要性閾值最優(yōu)參數(shù)根據(jù)不同數(shù)據(jù)集需要設置不同值。針對類不平衡數(shù)據(jù)環(huán)境,SFSCI根據(jù)特征和標簽之間依賴關系進行特征選擇,模型學習前需提前確定最近鄰參數(shù)值。PSO提出一種三相濾波過程,在多目標優(yōu)化設置中將進化粒子群優(yōu)化技術應用新到來特征組,檢查當前組中選擇特征對已選擇特征的冗余性,丟棄已選擇特征列表中相對新到來特征而言不重要的特征。G-SFS將多目標布谷鳥搜索技術交替應用新到來特征組,從I-SFS構建相應的G-SFS。

傳統(tǒng)的特征降維方法需要事先獲取數(shù)據(jù)集的內(nèi)容,在流特征環(huán)境下由于特征并非一次性全部到來,因而傳統(tǒng)方法無法直接應用。已有的流特征方法大多需要預設相關參數(shù),在實際應用中不同數(shù)據(jù)集的來源和空間結構不同,無法做到為每一個數(shù)據(jù)集預設最優(yōu)統(tǒng)一參數(shù)值,且改進鄰域粗糙集方法在特征冗余篩選過程中對真實數(shù)據(jù)集過于嚴格導致所選特征子集中存在冗余特征,在參數(shù)設置上也無法做到完全自適應。針對現(xiàn)有問題,基于模糊粗糙集理論,所提出的方法在學習之前不需要指定任何參數(shù),并被證明在處理現(xiàn)實世界的數(shù)據(jù)集時是有效的。

2 在線流特征選擇多標簽分類方法

定義流特征選擇OSFS=(U,C∪D,t),其中U為非空有限數(shù)據(jù)集,C為條件屬性集,D為決策屬性集。C=[x1,x2,…,xn]T∈Rn×d,由d維特征空間上F=[f1,f2,…,fd]T∈Rd的n個樣本組成。D=[y1,y2,…,yn]T∈Rn×l,由決策特征空間上L={l1,l2,…,lm}的n個樣本組成。時間戳t時,到來新特征f,學習映射函數(shù)h:xi→L(xi∈C),得到具有代表意義的最佳特征子集。

2.1 基于自適應密度鄰域的多標簽特征依賴

鄰域關系現(xiàn)有技術分為兩種:距離固定(δ鄰域)或鄰域數(shù)固定(k最近鄰域)。不同數(shù)據(jù)集數(shù)據(jù)分布不同,無法做到預設統(tǒng)一的參數(shù)。借鑒數(shù)據(jù)實例分布關系確定參數(shù)值作為一種新特征依賴方法受到關注。文中鄰域關系確定由實例周圍的密度信息自動確定鄰域個數(shù)。

(1)

(2)

其中,k為xi密度鄰居個數(shù),表示在標簽yl下標簽和相同時值為1,不同為0。第四步,根據(jù)求出ft在標簽yl下的特征依賴值總和最后重復三、四步得到每一個標簽下ft的依賴值

2.2 自適應密度鄰域粗糙集的在線特征選擇

(3)

實現(xiàn)新到來特征篩選后,如果直接將其加入已篩選特征子集Ft,容易產(chǎn)生較多冗余特征,導致模型性能降低,因而新特征篩選后還需對特征子集進行冗余優(yōu)化。對新到來數(shù)據(jù)ft,根據(jù)依賴計算度計算方法得到依賴值Dept。其次比較Ave_Dept-1與Dept,如果Dept中均小于Ave_Dept-1,則認為ft較已選特征子集Ft-1依賴性較低,丟棄。若滿足,再比較已選特征集Ft-1與合并特征集Ft-1∪ft的依賴關系,當Ave_DepFt-1∪ft大于Ave_Dept-1,意味著添加新特征ft會增加已選特征集Ft-1的依賴性,那么將ft加入Ft-1中,否則判斷Ave_Dept-1與Ave_DepFt-1∪ft之差對Ave_Dept-1的比值分析特征冗余性。對特征集Ft-1∪ft中的每一特征從候選特征集合中隨機選擇一個特征f,計算f顯著性值(即Ave_DepFt-1∪ft與Ave_Dep(Ft-1∪ft)-f的差值),將顯著性等于0的特征丟棄。通過這種新的在線流特征選擇算法,可以選擇高相關性、高依賴性和低冗余度的特征。

3 實驗及其結果分析

3.1 實驗數(shù)據(jù)集與評價指標

本節(jié)給出在實驗數(shù)據(jù)集上所提方法的實驗結果優(yōu)勢,其中選取的數(shù)據(jù)集均為常見多標簽分類方法實驗數(shù)據(jù)集,數(shù)據(jù)來源于Mulan(http://mulan.sourceforge.net/datasets.html)和Meka(https://waikato.github.io/meka/datasets/),詳細信息見網(wǎng)站內(nèi)容介紹。表1給出了10個實驗數(shù)據(jù)集介紹,包括:樣本數(shù)、特征數(shù)、標簽數(shù)、數(shù)據(jù)領域。數(shù)據(jù)領域包括網(wǎng)頁文本、電子郵件、音樂及基因功能,例如電子郵件Enron數(shù)據(jù)集共有1 702個數(shù)據(jù),每條數(shù)據(jù)至少從屬53種標簽的一種或多種。

表1 數(shù)據(jù)集

將所提方法與5個批處理方法和2個流特征選擇方法進行對比。其中MDDMspc[6]通過判別特征與標簽間依賴最大化實現(xiàn)降維。GLOCAL[26]通過學習潛在標簽和標簽流形化實現(xiàn)降維并考慮標簽的全局、局部相關性。LLSF[27]學習各標簽的特定數(shù)據(jù)實現(xiàn)多標簽特征選擇。LSML[28]解決在缺失標簽環(huán)境下的多標簽特征選擇問題。MCLS[29]通過將原始邏輯標簽轉化數(shù)字標簽實現(xiàn)實例相似度約束。SFSCI[24]處理在類標簽不平衡環(huán)境下流特征選擇。ML-OFS-ANRS[18]提出自適應鄰域粗糙集流特征選擇方法,利用最大依賴、最大重要指標篩選特征子集。所提方法模糊等價約束參數(shù)按照相關參數(shù)設置0.05[25],其余無需任何參數(shù),使用MLKNN分類模型評估算法性能。

3.2 實驗結果分析

3.2.1 所提方法與批處理方法對比

(4)

其中,Ri(yj)是樣本xi的標簽yj預測等級。

Ranking Loss描述樣本標簽對被反向排序的平均比例:

RL=

(5)

Coverage計算平均所需的步驟數(shù),以向下推進標簽列表并覆蓋所有實例的適當標簽:

(6)

One-error計算一個不相關的標簽被排在首位的次數(shù):

(7)

Hamming Loss計算錯誤分類標簽的平均得分:

(8)

Δ表示兩組間對稱差。

表2 在0.05顯著性水平條件下FF每種評估方法的臨界值

在5個評價指標上均顯著優(yōu)于MDDMspc和CLS,原因在于MDDM在標簽處理上忽略了標簽之間潛在的關聯(lián)關系,所提方法引入密度鄰域關系且利用平均依賴度最大限度考慮標簽之間的內(nèi)在聯(lián)系,而MCLS在特征選擇過程未對特征冗余進行過濾,取得的特征子集非最優(yōu),而ML-OFS-ADNR不僅對單個特征進行依賴度分析,而且分析新特征加入后是否對原有特征產(chǎn)生冗余。在線篩選過濾得到最優(yōu)特征子集。

與LLSF,GLOCAL和LSML的對比中,雖然沒有在所有指標上取得全部優(yōu)勢,但是無論在具體數(shù)據(jù)集還是CD圖上綜合排名所提方法最好。由于在密度鄰域依賴度計算過程中僅考慮在密度信息范圍內(nèi)忽略密度范圍以外的標簽信息,無法最大化利用標簽空間相關性信息,所提方法的CD非顯著最優(yōu)。

圖1 所提方法與對比算法的Nemenyi檢驗比較結果

3.2.2 所提方法與流特征選擇方法對比

除與批處理方法對比外,還在多標簽特征流環(huán)境下與最新的SFSCI[24],ML-OFS-ANRS[18]在指標Average Precision和Ranking Loss上進行比較,實驗結果見表3。

表3 ML-OFS-ADNR與SFSCI,ML-OFS-ANRS對比結果

根據(jù)表3可知:(1)基于密度鄰域粗糙集無需預設參數(shù),根據(jù)密度信息自動確定鄰域個數(shù)而SFSCI在實驗前需要手動設置最大鄰居數(shù)K,表明所提方法在Average Precision明顯優(yōu)于SFSCI,Ranking Loss上也有超過一半數(shù)據(jù)結果優(yōu)勢。(2)在其他數(shù)據(jù)集上,所提方法均優(yōu)于SCSFI,原因在于密度鄰域關系可以根據(jù)數(shù)據(jù)集的不同類型自動選擇合適的鄰域個數(shù),而SCSFI的K值設定忽略數(shù)據(jù)集內(nèi)容,限制模型的可擴展性,在數(shù)據(jù)集上無法發(fā)揮全部優(yōu)勢。(3)與ML-OFS-ANRS對比,兩種算法在鄰域處理均采取自適應的方法,保證了算法在不同數(shù)據(jù)都可最大化適應,在特征冗余篩選處理中,ML-OFS-ANRS依賴最大重要性標準,且針對不同數(shù)據(jù)集需要找出相應最優(yōu)重要性閾值參數(shù)值,而所提方法采用模糊等價約束,模糊等價約束參數(shù)統(tǒng)一且特征冗余性參數(shù)設置依賴前一個已選特征子集數(shù)據(jù),實現(xiàn)了自適應變化。(4)相比所提方法采用模糊等價約束進行特征冗余分析,ML-OFS-ANRS采用最大依賴和最大重要性標準進行特征冗余分析選擇了更多的特征,造成一定的冗余。而在模糊等價約束下,可以考慮更多的候選特征進行特征冗余分析,使得最終所選特征子集最優(yōu)。(5)圖2給出實驗過程中隨著特征子集不斷被篩選出來在數(shù)據(jù)集上的分類性能逐步提升。為保證實驗效果圖美觀,僅展示了在Average Precision和Ranking Loss評價指標上的結果。可以看出在Birds和Yeast數(shù)據(jù)集上,所提方法分別篩選的特征子集數(shù)目達到50和35個左右時,表現(xiàn)出的分類性能趨于穩(wěn)定。同特征子集數(shù)量下,所提方法在實驗精度上優(yōu)于另外兩個對比算法。當其他算法特征子集篩選結果趨于穩(wěn)定完成篩選,從實驗精度上所提方法依舊領先。

圖2 在3個代表數(shù)據(jù)集上調(diào)整特征子集所得到的實驗結果

4 結束語

提出一種基于密度鄰域粗糙集的多標簽流特征選擇方法(ML-OFS-ADNR)。該方法參照單標簽密度鄰域關系理論在多標簽分類環(huán)境中予以拓展,在依賴計算時根據(jù)周圍實例的密度信息自動決定鄰域數(shù)量,不需要預先指定任何參數(shù)。同時,采用模糊等價約束進行冗余分析,使所選特征子集小且具有鑒別性。與5種傳統(tǒng)特征選擇和2種流特征選擇算法相比,該方法在相同特征數(shù)量的情況下優(yōu)于傳統(tǒng)特征選擇方法,并在在線方式下優(yōu)于流特征選擇算法。未來的工作中,考慮實現(xiàn)模糊等價約束參數(shù)閾值自適應變化和模糊粗糙集理論應用流特征選擇,實現(xiàn)更加精準、自適應無參化的流特征方法研究。