王 進(jìn),陳知良,李 航，李智星,卜亞楠,陳喬松,鄧 欣

(1.重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 數(shù)據(jù)工程與可視計(jì)算重點(diǎn)實(shí)驗(yàn)室，重慶 400065；2.重慶郵電大學(xué) 軟件工程學(xué)院, 重慶 400065)

0 引 言

多標(biāo)簽分類問(wèn)題是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)。在多標(biāo)簽分類問(wèn)題中，一個(gè)樣本被同時(shí)賦予多個(gè)類別標(biāo)簽。層次多標(biāo)簽分類是一種特殊的多標(biāo)簽分類問(wèn)題。在層次多標(biāo)簽分類問(wèn)題中，一個(gè)樣本不僅同時(shí)具有多個(gè)類別標(biāo)簽，而且這些類別標(biāo)簽被組織在一定的層次結(jié)構(gòu)中。層次多標(biāo)簽分類方法被廣泛應(yīng)用于許多領(lǐng)域，如文本分類[1-2]，圖像分類[3-4]，基因功能預(yù)測(cè)[5-8]等。

與多標(biāo)簽分類問(wèn)題相比，層次多標(biāo)簽分類問(wèn)題要求分類方法所預(yù)測(cè)的標(biāo)簽集合必須滿足標(biāo)簽的層次約束。層次約束是指只有父節(jié)點(diǎn)出現(xiàn)，其子節(jié)點(diǎn)才有出現(xiàn)的可能性。目前，針對(duì)層次多標(biāo)簽約束問(wèn)題主要有2種解決方法。一種是根據(jù)傳統(tǒng)的多標(biāo)簽分類模型對(duì)層次樣本數(shù)據(jù)進(jìn)行分類，之后再對(duì)分類結(jié)果根據(jù)層次結(jié)構(gòu)進(jìn)行約束。由于父節(jié)點(diǎn)比其孩子標(biāo)簽更靠近根節(jié)點(diǎn)，且越靠近下層節(jié)點(diǎn)的標(biāo)簽不平衡性越高，預(yù)測(cè)出的父標(biāo)簽的置信度必定大于子標(biāo)簽的置信度，因此在分類后，一般根據(jù)父節(jié)點(diǎn)的預(yù)測(cè)結(jié)果對(duì)子節(jié)點(diǎn)進(jìn)行層次約束。例如，當(dāng)父標(biāo)簽預(yù)測(cè)為0，其所有孩子標(biāo)簽根據(jù)層次結(jié)構(gòu)的約束全部為0。另一種是在分類過(guò)程中就考慮標(biāo)簽間層次結(jié)構(gòu)的約束問(wèn)題。文本數(shù)據(jù)標(biāo)簽層次結(jié)構(gòu)示例如圖1，只有“糧食”和“風(fēng)景”標(biāo)簽節(jié)點(diǎn)出現(xiàn)后，再對(duì)“小麥”和“天空”標(biāo)簽節(jié)點(diǎn)是否出現(xiàn)進(jìn)行預(yù)測(cè)。

圖1 文本數(shù)據(jù)標(biāo)簽層次結(jié)構(gòu)示例Fig.1 Example of textual data label hierarchy

此外，在層次標(biāo)簽結(jié)構(gòu)中，越靠近下層節(jié)點(diǎn)的標(biāo)簽往往具有更為豐富的語(yǔ)義，具有更重要的分類意義和價(jià)值，因此，針對(duì)越靠近下層節(jié)點(diǎn)的標(biāo)簽分類價(jià)值越大。圖1中，相比“糧食”和“風(fēng)景”標(biāo)簽節(jié)點(diǎn)，“小麥”和“天空”標(biāo)簽節(jié)點(diǎn)具有更為豐富的語(yǔ)義，更重要的分類價(jià)值。但是，在層次多標(biāo)簽分類問(wèn)題中，越靠近下層的標(biāo)簽節(jié)點(diǎn)出現(xiàn)的頻率越低，造成類別標(biāo)簽分布不平衡的問(wèn)題。圖2為ImageCLEF07A[9]數(shù)據(jù)集的層次標(biāo)簽結(jié)構(gòu)中，每層標(biāo)簽在訓(xùn)練集中出現(xiàn)頻率的平均值。從圖2中可以看出，該數(shù)據(jù)集的標(biāo)簽隨著層數(shù)的增加，深層次的類別標(biāo)簽出現(xiàn)的頻率急劇減少。在機(jī)器學(xué)習(xí)領(lǐng)域，類別不平衡問(wèn)題對(duì)機(jī)器學(xué)習(xí)方法的性能造成很大的影響。所以，如何降低標(biāo)簽的不平衡性對(duì)分類性能起著決定性的作用。

圖2 ImageCLEF07A數(shù)據(jù)層次標(biāo)簽的統(tǒng)計(jì)Fig.2 Statistics of ImageCLEF07A data level label

利用超網(wǎng)絡(luò)模型處理多標(biāo)簽分類問(wèn)題可以提高多標(biāo)簽分類問(wèn)題性能、為解決多標(biāo)簽分類問(wèn)題提供了新的理論和方法[10-12]。但由于層次多標(biāo)簽分類問(wèn)題中，標(biāo)簽具有的特殊結(jié)構(gòu)，傳統(tǒng)的多標(biāo)簽超網(wǎng)絡(luò)無(wú)法滿足分類后層次標(biāo)簽之間的約束問(wèn)題。針對(duì)層次多標(biāo)簽分類問(wèn)題，本文對(duì)傳統(tǒng)超網(wǎng)絡(luò)模型進(jìn)行改進(jìn)，提出了一種基于增量式超網(wǎng)絡(luò)的多標(biāo)簽分類方法。該方法首先考慮標(biāo)簽的層次結(jié)構(gòu)以及標(biāo)簽的稀疏性，將超網(wǎng)絡(luò)的超邊按照給定的標(biāo)簽層次結(jié)構(gòu)進(jìn)行組織，構(gòu)建層次多標(biāo)簽超網(wǎng)絡(luò)模型；然后采用增量式的學(xué)習(xí)方法對(duì)層次多標(biāo)簽超網(wǎng)絡(luò)模型進(jìn)行演化學(xué)習(xí)；最后通過(guò)增量式超網(wǎng)絡(luò)方法對(duì)未知樣本進(jìn)行標(biāo)簽預(yù)測(cè)。增量式超網(wǎng)絡(luò)學(xué)習(xí)方法不僅可以滿足層次多標(biāo)簽分類問(wèn)題中的標(biāo)簽結(jié)構(gòu)約束，而且還能夠通過(guò)利用標(biāo)簽之間的關(guān)聯(lián)關(guān)系，有效地減少不平衡問(wèn)題對(duì)分類性能的影響。

1 相關(guān)工作

層次多標(biāo)簽分類問(wèn)題是一類特殊的多標(biāo)簽分類問(wèn)題。國(guó)內(nèi)外學(xué)者對(duì)其進(jìn)行了深入的研究[13-16]。層次多標(biāo)簽分類方法大致可以分為局部方法和全局方法2類。局部層次分類策略通過(guò)自上而下的方式[17]在標(biāo)簽層次結(jié)構(gòu)中的每一層訓(xùn)練一個(gè)多標(biāo)簽分類器。局部層次分類策略總結(jié)為以下幾種[18]：①對(duì)每個(gè)節(jié)點(diǎn)建立一個(gè)二分類器(local classifier per node, LCN)；②對(duì)每個(gè)節(jié)點(diǎn)的孩子建立一個(gè)多分類器(local classifier per parent node, LCPN)；③對(duì)每一層訓(xùn)練一個(gè)多分類器(local classifier per level, LCL)。LCN方法[19]旨在對(duì)每個(gè)節(jié)點(diǎn)建立一個(gè)二分類器，然后再進(jìn)行節(jié)點(diǎn)的分類預(yù)測(cè)；LCPN是每個(gè)父節(jié)點(diǎn)為了區(qū)分其子類類別建立的多分類器[20]；LCL策略采用為層次標(biāo)簽的每一層建立一個(gè)多標(biāo)簽分類器，這樣就可以考慮到每一層預(yù)測(cè)類別之間都可能存在著一定的關(guān)聯(lián)性。由Cerri等[21]提出的HMC_LP是一種非分層的層次多標(biāo)簽分類方法。HMC_LP采用標(biāo)簽組合的方法，將原問(wèn)題轉(zhuǎn)化為一個(gè)分層的HMC的單標(biāo)簽問(wèn)題。這個(gè)標(biāo)簽組合過(guò)程考慮同一層兄弟標(biāo)簽之間的關(guān)系。文獻(xiàn)[22]中提出了一種基于決策樹的層次多標(biāo)簽分類方法Clus，主要基于決策樹為基分類器對(duì)層次多標(biāo)簽分類模型進(jìn)行訓(xùn)練。根據(jù)不同的層次分類策略分為Clus-SC，Clus-HSC和Clus-HMC，而Clus-ens是該方法的集成模型。由于該方法對(duì)每個(gè)節(jié)點(diǎn)或每層節(jié)點(diǎn)都使用一個(gè)樹形分類器進(jìn)行分類。全局層次分類策略不同于局部層次分類策略，該方法只訓(xùn)練一個(gè)分類器來(lái)處理所有層次結(jié)構(gòu)類。新實(shí)例的分類僅在一步中實(shí)現(xiàn)。由于全局層次分類策略的分類器必須考慮層次多標(biāo)簽分類問(wèn)題的標(biāo)簽結(jié)構(gòu)特殊性，因此，除非算法適合處理類層次結(jié)構(gòu)，否則一般不可能使用傳統(tǒng)的多標(biāo)簽分類算法。HMC_predict是基于神經(jīng)網(wǎng)絡(luò)的一個(gè)改進(jìn)算法，分別使用RP和BP作為不同神經(jīng)網(wǎng)絡(luò)基分類器進(jìn)行方法思路的討論，旨在將學(xué)習(xí)過(guò)程分成若干個(gè)步驟，結(jié)合神經(jīng)網(wǎng)絡(luò)模型降低損失函數(shù)來(lái)訓(xùn)練模型[23]。該方法最大的優(yōu)點(diǎn)是學(xué)習(xí)過(guò)程中滲入增廣特征矢量來(lái)增加標(biāo)簽的依賴，通過(guò)使用真實(shí)標(biāo)簽作為特征向量的一部分，保證標(biāo)簽之間的關(guān)聯(lián)性。該方法由于使用神經(jīng)網(wǎng)絡(luò)作為基分類器，因此不具有層次可解釋性。

多標(biāo)簽超網(wǎng)絡(luò)是一種結(jié)構(gòu)靈活、模型簡(jiǎn)單的多標(biāo)簽分類方法[24-25]。該方法能夠有效地挖掘類別標(biāo)記之間的關(guān)聯(lián)關(guān)系，并利用類別標(biāo)記之間的關(guān)聯(lián)提高多標(biāo)簽分類問(wèn)題的分類性能。在文獻(xiàn)[24]中，提出一種利用協(xié)同演化的學(xué)習(xí)方法，挖掘利用標(biāo)簽之間高階關(guān)聯(lián)關(guān)系。文獻(xiàn)[10]中提出一種2階段演化學(xué)習(xí)方法，通過(guò)利用標(biāo)簽之間關(guān)聯(lián)關(guān)系，處理多標(biāo)簽分類問(wèn)題中的標(biāo)簽分布不平衡問(wèn)題。雖然超網(wǎng)絡(luò)方法可以利用標(biāo)簽的關(guān)聯(lián)性有效地解決多標(biāo)簽分類問(wèn)題，但在層次多標(biāo)簽分類問(wèn)題中，標(biāo)簽之間的關(guān)聯(lián)關(guān)系是通過(guò)標(biāo)簽層次結(jié)構(gòu)體現(xiàn)的，而一般的多標(biāo)簽超網(wǎng)絡(luò)方法并沒(méi)有考慮這種具有層次結(jié)構(gòu)的關(guān)聯(lián)關(guān)系，因此，一般的多標(biāo)簽超網(wǎng)絡(luò)分類方法并不能直接用于解決層次多標(biāo)記分類問(wèn)題。

2 層次多標(biāo)簽增量式超網(wǎng)絡(luò)分類方法

2.1 層次多標(biāo)簽定義

圖3 標(biāo)簽層次結(jié)構(gòu)示例Fig.3 Example of the label hierarchy

2.2 多標(biāo)簽超網(wǎng)絡(luò)模型

根據(jù)人類認(rèn)知學(xué)習(xí)的3個(gè)基本準(zhǔn)則：持續(xù)性、Glolity準(zhǔn)則以及組合準(zhǔn)則，B.T.Zhang[26]提出了一種基于概率統(tǒng)計(jì)的超網(wǎng)絡(luò)模型，其結(jié)構(gòu)靈活、分類模型簡(jiǎn)單、能夠有效地表示對(duì)象之間的高階關(guān)聯(lián)。在多標(biāo)簽問(wèn)題中，超網(wǎng)絡(luò)模型同樣發(fā)揮著很好的作用。文獻(xiàn)[24-25]中分別提出了2種多標(biāo)簽超網(wǎng)絡(luò)算法MLHN和Co-MLHN。通過(guò)將傳統(tǒng)的超網(wǎng)絡(luò)模型針對(duì)多標(biāo)簽分類問(wèn)題進(jìn)行改進(jìn)，多標(biāo)簽超網(wǎng)絡(luò)可以有效地表示和利用標(biāo)簽之間的關(guān)聯(lián)來(lái)提高多標(biāo)簽分類的性能。此外，與大多數(shù)多標(biāo)簽分類方法相比，多標(biāo)簽超網(wǎng)絡(luò)算法的時(shí)間復(fù)雜度較低，它能以標(biāo)簽數(shù)量的線性時(shí)間復(fù)雜度，有效地挖掘標(biāo)記之間的關(guān)聯(lián)。超網(wǎng)絡(luò)[24]是一種基于超圖的認(rèn)知學(xué)習(xí)模型，是由大量超邊組成的概率超圖模型，通過(guò)超邊庫(kù)表達(dá)模式空間中數(shù)據(jù)的分布概率，以達(dá)到預(yù)測(cè)的效果。多標(biāo)簽超網(wǎng)絡(luò)模型是一種基于加權(quán)的隨機(jī)超圖模型，不僅分類效果較好，而且超邊可以反映頂點(diǎn)之間的高階可關(guān)聯(lián)性。圖4表示多標(biāo)簽超網(wǎng)絡(luò)模型，多標(biāo)簽超網(wǎng)絡(luò)可以用一個(gè)3元組H={V,E,W}表示，其中，V={x1,x2,…,xn}為頂點(diǎn)集，E為超邊集合，其由頂點(diǎn)子集，標(biāo)簽和權(quán)重3部分組成，W為超邊對(duì)應(yīng)標(biāo)簽權(quán)重。通過(guò)類別標(biāo)簽向量和權(quán)值向量，多標(biāo)簽超網(wǎng)絡(luò)分類模型能夠表示標(biāo)簽類別之間任意階關(guān)聯(lián)。

圖4 多標(biāo)簽超網(wǎng)絡(luò)模型Fig.4 Multi-labelhypernetwork model

給定一個(gè)具有m個(gè)類別標(biāo)簽的多標(biāo)簽訓(xùn)練樣本數(shù)據(jù)集，多標(biāo)簽超網(wǎng)絡(luò)模型通過(guò)含有大量超邊的超邊集合及其類別標(biāo)簽向量和權(quán)值向量，表示數(shù)據(jù)樣本與類別標(biāo)簽向量之間的聯(lián)合概率分布P(x,yi|W)(1≤i≤m)為

(1)

(1)式中Z(W)為規(guī)范化項(xiàng)；yi∈{0,1}；ε為能量函數(shù)，其計(jì)算方法定義為

(2)

(2)式中wji為超邊ej中類別標(biāo)簽i的權(quán)值；I為匹配函數(shù)，表達(dá)式為

(3)

(3)式中dist(x,ej)表示產(chǎn)生超邊ej的樣本特征數(shù)據(jù)與該條樣本特征數(shù)據(jù)x之間的距離；δj表示設(shè)定的閾值δj。

多標(biāo)簽超網(wǎng)絡(luò)模型輸出：給定一個(gè)待分類多標(biāo)簽數(shù)據(jù)樣本x，多標(biāo)簽超網(wǎng)絡(luò)首先計(jì)算該樣本與各類別標(biāo)簽的條件概率，輸出一個(gè)概率向量P=[P(y1=1|x),P(y2=1|x),…,P(ym=1|x)]，P中的每一維向量表示相應(yīng)類別標(biāo)簽被預(yù)測(cè)給待分類樣本的概率，最后選取條件概率大于閾值t(t一般設(shè)置成0.5)的類別標(biāo)簽作為預(yù)測(cè)類別標(biāo)簽。多標(biāo)簽超網(wǎng)絡(luò)算法主要分成訓(xùn)練階段和測(cè)試階段，訓(xùn)練階段主要步驟：①超邊庫(kù)的生成；②超邊替代；③權(quán)重更新。測(cè)試階段主要對(duì)輸入的樣本進(jìn)行標(biāo)簽預(yù)測(cè)。

2.3 基于增量式超網(wǎng)絡(luò)的多標(biāo)簽分類方法

改進(jìn)的層次多標(biāo)簽增量式超網(wǎng)絡(luò)分類算法的輸出結(jié)果能滿足層次分類的限制條件，由于層次結(jié)構(gòu)的遞增出現(xiàn)標(biāo)簽不平衡問(wèn)題，該算法在分類中能夠巧妙地降低下一層標(biāo)簽的不平衡程度，因此，在標(biāo)簽層次分類中表現(xiàn)出較好的效果。層次多標(biāo)簽增量式超網(wǎng)絡(luò)模型通過(guò)演化學(xué)習(xí)，可以使多標(biāo)簽超網(wǎng)絡(luò)模型解決層次分類的問(wèn)題。針對(duì)層次多標(biāo)簽結(jié)構(gòu)，在初始化標(biāo)簽向量的時(shí)候，根據(jù)其父節(jié)點(diǎn)的標(biāo)簽與近鄰樣本的概率權(quán)重和進(jìn)行設(shè)置與調(diào)整。由于每次預(yù)測(cè)該層的標(biāo)簽是基于父節(jié)點(diǎn)結(jié)果的分類基礎(chǔ)上，因此，基于該父節(jié)點(diǎn)的子標(biāo)簽的正負(fù)樣本數(shù)據(jù)概率差異減少，在對(duì)樣本進(jìn)行分類時(shí)，很大程度地減少了不平衡標(biāo)簽造成的分類精度差。當(dāng)層次多標(biāo)簽增量式超網(wǎng)絡(luò)模型演化學(xué)習(xí)完成后，根據(jù)學(xué)習(xí)模型，對(duì)測(cè)試樣本數(shù)據(jù)進(jìn)行預(yù)測(cè)。只有當(dāng)父節(jié)點(diǎn)的權(quán)重值大于閾值t，即父節(jié)點(diǎn)預(yù)測(cè)為1的前提下，才對(duì)其子節(jié)點(diǎn)進(jìn)行預(yù)測(cè)，所以層次多標(biāo)簽增量式超網(wǎng)絡(luò)分類方法的輸出結(jié)果滿足層次結(jié)構(gòu)的約束?？紤]到每個(gè)樣本中出現(xiàn)標(biāo)簽的概率占整個(gè)標(biāo)簽集合的極小部分，因此，層次多標(biāo)簽增量式超網(wǎng)絡(luò)分類方法在演化學(xué)習(xí)時(shí)，把標(biāo)簽向量分成正(PW)、負(fù)標(biāo)簽向量(NW)。正標(biāo)簽向量表示該標(biāo)簽的權(quán)重信息對(duì)于出現(xiàn)該標(biāo)簽起積極作用，負(fù)標(biāo)簽向量則反之。這樣設(shè)定可以減少空間復(fù)雜度的開銷，顯示了算法的優(yōu)勢(shì)。正、負(fù)標(biāo)簽的組織結(jié)構(gòu)相同，只是在計(jì)算時(shí)，一個(gè)權(quán)重對(duì)標(biāo)簽預(yù)測(cè)為1產(chǎn)生正影響(PW)，一個(gè)產(chǎn)生負(fù)影響(NW)?；谠隽渴匠W(wǎng)絡(luò)的多標(biāo)簽分類模型流程圖如圖5，只有當(dāng)label1的父節(jié)點(diǎn)預(yù)測(cè)為1(即yi1m)時(shí)，label2的子節(jié)點(diǎn)(yi2)才能進(jìn)行下一步的預(yù)測(cè)，以此類推。

接下來(lái)將分別詳細(xì)介紹增量式超網(wǎng)絡(luò)多標(biāo)簽分類方法的分類學(xué)習(xí)與預(yù)測(cè)階段。

1)增量式超網(wǎng)絡(luò)多標(biāo)簽分類方法分類階段。主要對(duì)未知樣本進(jìn)行標(biāo)簽分類。對(duì)于增量式超網(wǎng)絡(luò)多標(biāo)簽分類方法分類階段的具體步驟如下。

算法1分類階段的偽代碼。

輸入：增量式超網(wǎng)絡(luò)模型H=(V,E,W)；未知標(biāo)簽的特征數(shù)據(jù)：x；匹配臨界值&；閾值標(biāo)簽向量：t=|t1,t2,…,tn|；k近鄰樣本個(gè)數(shù)K；標(biāo)簽層次數(shù)m；

輸出：預(yù)測(cè)的閾值P；標(biāo)簽向量y；

1.查找該條測(cè)試樣本x的K近鄰樣本

2.從該樣本的k近鄰樣本所產(chǎn)生的超邊集合中選取與其小于臨界值&所匹配的超邊集M

3.for eachei∈M

4. 把yj加入集合countlabel(y)中，并對(duì)其統(tǒng)計(jì)數(shù)加1

5. 根據(jù)yj屬于ei的正向集pos(y)或負(fù)向集neg(y)，對(duì)相應(yīng)的正向集權(quán)重Wneg(yj)或者負(fù)向集Wneg(yj)權(quán)重統(tǒng)計(jì)

6. for each yq∈countlabel(y)

7. pro(yq)=pos(yq)/(pos(yq)+neg(yq))

8. end

9. end

10.for pro (hj)∈pro &P(y)=1≤hpy(hj)

11.ifpro(hj)>t

12.yhj=1

13. else

14.yhj=0

15. end if

16.end

2)增量式超網(wǎng)絡(luò)多標(biāo)簽分類方法學(xué)習(xí)階段。具體步驟如下。

算法2演化學(xué)習(xí)層次多標(biāo)簽超網(wǎng)絡(luò)模型偽代碼。

輸入：訓(xùn)練樣本集合D={(xi,xj)|1≤i≤N|}；學(xué)習(xí)速率μ；標(biāo)簽層次關(guān)系P；學(xué)習(xí)次數(shù)T；每條樣本的k近鄰樣本；閾值δ；

輸出：演化層次多標(biāo)簽超網(wǎng)絡(luò)模型H*。

1．初始化超網(wǎng)絡(luò)模型H0=(E,Y,W)；

2．替換層次多標(biāo)簽超網(wǎng)絡(luò)模型中fitness較低超邊；

3．fort=1 toTdo

4． forn=1 toNdo

5． 獲取第n條訓(xùn)練樣本(xn,yn)

6． 根據(jù)算法1對(duì)當(dāng)前超網(wǎng)絡(luò)模型H進(jìn)行分類，預(yù)測(cè)該條樣本標(biāo)簽y*=[y1,y2,…,yn]

7． 從超邊集合M中選取近鄰超邊集合Mk

8． forj=1 tom

9． if (yij≠yj) &yj>δ

10． for eachek∈Mk

11． 更新權(quán)重Wpos(yj)=Wpos(yj)-ΔWpos(yj)

12． 更新權(quán)重Wneg(yj)=Wneg(yj)+ΔWneg(yj)

13． end

14． end if

15． if (yij≠yj) &yj<δ

16． for eachek∈Mk

17． 更新權(quán)重Wpos(yj)=Wpos(yj)+ΔWpos(yj)

18． 更新權(quán)重Wneg(yj)=Wneg(yj)-ΔWneg(yj)

19． end

20． end if

21． end

22． Ht= H(t-1)+DH(t-1)

23． end

24．end

3 實(shí)驗(yàn)

本文采用的實(shí)驗(yàn)環(huán)境為2.30 GHz CPU，8.0 GB內(nèi)存，Windows7操作系統(tǒng)，Java語(yǔ)言，Eclipse環(huán)境。實(shí)驗(yàn)部分主要包括：①包括實(shí)驗(yàn)數(shù)據(jù)；②評(píng)價(jià)指標(biāo)以及參數(shù)的說(shuō)明；③實(shí)驗(yàn)結(jié)果及分析。

3.1 實(shí)驗(yàn)數(shù)據(jù)

本次實(shí)驗(yàn)的數(shù)據(jù)集如表1所示，數(shù)據(jù)來(lái)源于公開數(shù)據(jù)集[9]，除了WIPO標(biāo)簽數(shù)據(jù)具有4層結(jié)構(gòu)外，其余數(shù)據(jù)的標(biāo)簽都具有3層的層次結(jié)構(gòu)。因?yàn)閃IPO數(shù)據(jù)集標(biāo)簽結(jié)構(gòu)含有根節(jié)點(diǎn)，因此，該數(shù)據(jù)的標(biāo)簽結(jié)構(gòu)為樹形結(jié)構(gòu)，其余數(shù)據(jù)的標(biāo)簽層次結(jié)構(gòu)為森林。文本數(shù)據(jù)集Reuters和Enron為多路徑層次標(biāo)簽集合，其余數(shù)據(jù)集都為單路徑層次標(biāo)簽結(jié)合。

表1 實(shí)驗(yàn)數(shù)據(jù)集介紹

3.2 評(píng)價(jià)指標(biāo)以及參數(shù)的說(shuō)明

1)層次損失[27](hierarchical loss, H-loss) 。H-loss是專門針對(duì)HMC任務(wù)提出來(lái)的，假設(shè)層次標(biāo)簽滿足樹形結(jié)構(gòu)。該度量基于漢明損失或?qū)ΨQ損失返回一個(gè)層次多標(biāo)簽向量的預(yù)測(cè)值與真實(shí)值之間的對(duì)稱差。在該度量中，如果已經(jīng)懲罰了超類的錯(cuò)誤，就不再懲罰子類中的錯(cuò)誤。例如，當(dāng)已經(jīng)懲罰了層次結(jié)構(gòu)中的某個(gè)標(biāo)簽，那么該評(píng)測(cè)指標(biāo)不再對(duì)其標(biāo)簽的子類產(chǎn)生任何損失。

(4)

(4)式中，anc(i)表示節(jié)點(diǎn)i的超類集合；c1,c2,…,ck表示固定成本系數(shù)。Cesa-Bianchi等[28]提出了2種計(jì)算成本系數(shù)的方法：均勻損失和歸一化損失。本文采用的是均勻損失方法來(lái)計(jì)算成本系數(shù)。

2)層次多標(biāo)簽分類損失(HMC-loss)[27]。由于層次損失(H-loss)沒(méi)有考慮到相同的假陽(yáng)性預(yù)測(cè)在較低層比較高層產(chǎn)生更大的損失，因此，提出了層次多標(biāo)簽分類損失(HMC-loss)為

(5)

(5)式中，c1,c2,…,ck表示在標(biāo)準(zhǔn)的樹狀層次結(jié)構(gòu)中定義的H-loss固定成本系數(shù)。對(duì)于DAGs結(jié)構(gòu)來(lái)說(shuō)，非根節(jié)點(diǎn)的損失定義為ci=∑jcj/|child(j)|，j為i的父親節(jié)點(diǎn)。對(duì)于假正例(FP)和假反例(FN)的不同權(quán)重系數(shù)α和β，進(jìn)行損失敏感設(shè)置。當(dāng)α=β=1，層次多標(biāo)簽分類損失(HMC-loss)就等于等權(quán)重值的漢明損失，或者說(shuō)是均勻損失。層次多標(biāo)簽分類損失(HMC-loss)有效地解決了層次損失(H-loss)的空預(yù)測(cè)問(wèn)題，因?yàn)樵撛u(píng)測(cè)指標(biāo)不是只懲罰預(yù)測(cè)錯(cuò)的根節(jié)點(diǎn)，同時(shí)考慮了每個(gè)節(jié)點(diǎn)預(yù)測(cè)錯(cuò)誤所導(dǎo)致的損失。

3)層次F1值。該評(píng)價(jià)措施是對(duì)每個(gè)標(biāo)簽分類結(jié)果精度和召回率信息的一個(gè)融合。

(6)

3.3 實(shí)驗(yàn)結(jié)果及分析

本節(jié)主要根據(jù)上述評(píng)價(jià)指標(biāo)對(duì)層次多標(biāo)簽分類和不平衡數(shù)據(jù)標(biāo)簽的分類進(jìn)行實(shí)驗(yàn)并進(jìn)行結(jié)果分析。HMC_MLHN方法是利用傳統(tǒng)的超網(wǎng)絡(luò)對(duì)層次數(shù)據(jù)進(jìn)行分類，由于輸出結(jié)果不滿足層次約束的限制條件，文獻(xiàn)[23]對(duì)第3步方法進(jìn)行了糾正，對(duì)傳統(tǒng)的超網(wǎng)絡(luò)進(jìn)行層次約束。因?yàn)樵隽渴匠W(wǎng)絡(luò)方法輸出的是測(cè)試樣本的置信度，而置信度由近鄰超邊的正負(fù)權(quán)重產(chǎn)生，如果標(biāo)簽預(yù)測(cè)出的置信度大于閾值t(本文設(shè)置為0.5)，則表明近鄰超邊產(chǎn)生的正影響大于負(fù)影響，則增量式超網(wǎng)絡(luò)分類器對(duì)該標(biāo)簽的預(yù)測(cè)值為1，反之為0。由于LMLP和clus_HMC方法針對(duì)不同的閾值產(chǎn)生不同的實(shí)驗(yàn)結(jié)果，本文在對(duì)比試驗(yàn)中，采用步長(zhǎng)以0.02為增量，從0到1的范圍內(nèi)，選取該方法最優(yōu)F1值的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，不同層次分類方法參數(shù)閾值的選擇如表2所示。本文采用的增量式超網(wǎng)絡(luò)方法的具體實(shí)驗(yàn)參數(shù)如表3。從實(shí)驗(yàn)結(jié)果可以看出，比較bp_LMLP, rp_LMLP以及clus_HMC, clus_HMC_ens, HMC_MLHN方法，增量式超網(wǎng)絡(luò)方法具有較好的分類性能，并且對(duì)不平衡數(shù)據(jù)標(biāo)簽的分類性能也是比較好的。

表2 不同層次多標(biāo)簽算法閾值選擇

表3 多標(biāo)簽增量式超網(wǎng)絡(luò)方法實(shí)驗(yàn)參數(shù)

3.3.1 層次多標(biāo)簽分類精度以及時(shí)間復(fù)雜度分析

本文分別采用上述3種評(píng)價(jià)指標(biāo)進(jìn)行試驗(yàn)。實(shí)驗(yàn)結(jié)果如表4～表6所示，從不同層次多標(biāo)簽分類算法在不同指標(biāo)進(jìn)行對(duì)比結(jié)果可以看出，相對(duì)于其他5種多標(biāo)簽分類方法，HMC_IMLHN和bp_LMLP,rp_LMLP,clus_HMC,clus_HMC_ens,HMC_MLHN,HMC_IMLHN具有很好的層次分類效果，整體效果較好優(yōu)于其他算法，尤其是F1值指標(biāo)具有很好的實(shí)驗(yàn)結(jié)果。其中，需要說(shuō)明的是對(duì)于WIPO數(shù)據(jù)來(lái)說(shuō)，由于其標(biāo)簽結(jié)構(gòu)與其他數(shù)據(jù)集的標(biāo)簽結(jié)構(gòu)不同，為一棵單一的樹，因此，根節(jié)點(diǎn)默認(rèn)預(yù)測(cè)全部為1且正確。

表4 不同層次多標(biāo)簽算法在H_loss指標(biāo)下的實(shí)驗(yàn)對(duì)比結(jié)果

表5 不同層次多標(biāo)簽算法在HMC_loss指標(biāo)下的實(shí)驗(yàn)對(duì)比結(jié)果

表6 不同層次多標(biāo)簽算法在F1指標(biāo)下的實(shí)驗(yàn)對(duì)比結(jié)果

表7 不同層次多標(biāo)簽算法運(yùn)行時(shí)間

設(shè)定訓(xùn)練集的有N個(gè)樣本，測(cè)試集樣本有T個(gè)，平均有m個(gè)標(biāo)簽，數(shù)據(jù)樣本平均有L層，c為超邊的維度，層次多標(biāo)簽增量式超網(wǎng)絡(luò)方法訓(xùn)練階段的時(shí)間復(fù)雜度O(N2+L(cKN+mN))，測(cè)試樣本的時(shí)間復(fù)雜度為O(TN+L(cKN+mN))。表7展示的是不同的層次分類方法在不同的數(shù)據(jù)集上的運(yùn)行時(shí)間。

3.3.2 不平衡指標(biāo)分析

該部分主要對(duì)層次標(biāo)簽數(shù)據(jù)集的不平衡性進(jìn)行分析，探究各種方法對(duì)緩解不平衡性標(biāo)簽的性能影響。通過(guò)統(tǒng)計(jì)HMC_IMLHN和bp_LMLP,rp_LMLP,clus_HMC,clus_HMC_ens,HMC_MLHN層次多標(biāo)簽分類方法在不同數(shù)據(jù)集中的平均層次F1值，區(qū)別于上述3.3.1部分中對(duì)層次F1值的統(tǒng)計(jì)，該部分主要是統(tǒng)計(jì)實(shí)驗(yàn)結(jié)果中，每層標(biāo)簽的平均層次F1值。具體結(jié)果如圖6～圖11所示，橫軸表示某層次標(biāo)簽，縱軸表示每層標(biāo)簽的平均層次F1值。

針對(duì)多標(biāo)簽層次數(shù)據(jù)中標(biāo)簽具有的不平衡性問(wèn)題，HMC_IMLHN首先在訓(xùn)練階段的超邊初始化過(guò)程中，對(duì)超邊的結(jié)構(gòu)進(jìn)行了調(diào)整，在分類中能夠有效降低下一層標(biāo)簽的不平衡程度；其次，預(yù)測(cè)過(guò)程中針對(duì)標(biāo)簽存在不平衡因素的問(wèn)題，加入了緩解不平衡的措施，使得子標(biāo)簽的正負(fù)樣本數(shù)據(jù)概率差異減少，在預(yù)測(cè)階段，很大程度地減少了不平衡標(biāo)簽造成的分類精度差；最后，HMC_IMLHN方法利用標(biāo)簽之間的關(guān)聯(lián)減少子標(biāo)簽存在不平衡性問(wèn)題對(duì)分類性能的影響。根據(jù)結(jié)果可以看出HMC_IMLHN在緩解不平衡性標(biāo)簽的分類性能上具較好的分類效果。

圖6 ImageCLEF07A每層標(biāo)簽的平均F1值Fig.6 Average F1 value of ImageCLEF07A per layer

圖7 ImageCLEF07D每層標(biāo)簽的平均F1值Fig.7 Average F1 value of ImageCLEF07D per layer

圖8 Diatoms每層標(biāo)簽的平均F1值Fig.8 Average F1 value of Diatoms per layer

圖9 Enron每層標(biāo)簽的平均F1值Fig.9 Average F1 value of Enron per layer

3.3.3 部分標(biāo)簽的分類精確度分析

該部分的工作主要是分別對(duì)實(shí)驗(yàn)結(jié)果數(shù)據(jù)集中的部分標(biāo)簽進(jìn)行概率統(tǒng)計(jì)以及不同層次多標(biāo)簽分類方法對(duì)該標(biāo)簽的正確度統(tǒng)計(jì)，選出部分標(biāo)簽進(jìn)行圖表展示，圖12～圖17的橫軸表示某個(gè)標(biāo)簽，左縱軸表示該標(biāo)簽的分類精確度，右縱軸表示該標(biāo)簽的出現(xiàn)概率。

HMC_IMLHN方法對(duì)傳統(tǒng)的多標(biāo)簽超網(wǎng)絡(luò)方法進(jìn)行改進(jìn)，滿足層次標(biāo)簽約束的同時(shí)，考慮了層次標(biāo)簽之間的不平衡性，并且在初始化標(biāo)簽向量的時(shí)候，根據(jù)其父節(jié)點(diǎn)的標(biāo)簽與近鄰樣本的概率權(quán)重和進(jìn)行設(shè)置與調(diào)整，使得在分類中能夠巧妙地降低下一層標(biāo)簽的不平衡程度，提高方法的分類性能。從圖12～圖17中可以看出，相比較其他層次多標(biāo)簽分類方法，HMC_IMLHN在不同數(shù)據(jù)集上都具有較好的穩(wěn)定性以及分類精確度。

圖10 Reuters每層標(biāo)簽的平均F1值Fig.10 Average F1 value of Reuters per layer

圖11 WIPO每層標(biāo)簽的平均F1值Fig.11 Average F1 value of WIPO per layer

圖12 ImageCLEF07A部分標(biāo)簽的分類精度Fig.12 Classification accuracy of ImageCLEF07A partial label

圖13 ImageCLEF07D部分標(biāo)簽的分類精度Fig.13 Classification accuracy of ImageCLEF07D partial label

圖14 Diatoms部分標(biāo)簽的分類精度Fig.14 Classification accuracy of Diatoms partial label

圖15 Enron部分標(biāo)簽的分類精度Fig.15 Classification accuracy of Enron partial label

4 結(jié)束語(yǔ)

本文提出了一種用于層次多標(biāo)簽的增量式超網(wǎng)絡(luò)分類算法，該算法的輸出能夠滿足層次分類的限制條件，同時(shí)通過(guò)標(biāo)簽間的關(guān)聯(lián)性減弱層次標(biāo)簽分類中出現(xiàn)的越靠近葉子標(biāo)簽的標(biāo)簽不平衡性。相比較其他層次多標(biāo)簽分類方法，該方法在文本分類和圖像分類中有較好的分類準(zhǔn)確性。

圖16 Reuters部分標(biāo)簽的分類精度Fig.16 Classification accuracy of Reuters partial label

下一步的工作主要針對(duì)父節(jié)點(diǎn)對(duì)子節(jié)點(diǎn)的信息量的增加以及超邊更優(yōu)的產(chǎn)生過(guò)程進(jìn)行研究分析。