張春焰，李 濤，劉 崢

(南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210046)

0 引 言

層次分類(hierarchical classification，HC)問(wèn)題是分類問(wèn)題的一個(gè)分支，在層次分類問(wèn)題中類別是不相交的，而是以分層結(jié)果組織的。在該情況下，一個(gè)樣本會(huì)與給定的類別標(biāo)簽及該標(biāo)簽的父標(biāo)簽相關(guān)聯(lián)，而組織類的層次結(jié)構(gòu)可以采用樹(shù)或者有向無(wú)環(huán)圖(directed acyclic graph，DAG)的形式。存在復(fù)雜HC問(wèn)題的子集，其中每個(gè)樣本可以與類層次結(jié)構(gòu)中的多個(gè)路徑相關(guān)聯(lián)，即層次多標(biāo)簽分類(HMC)[1-3]。典型的HMC問(wèn)題是文本分類[4-6]和生物信息學(xué)任務(wù)，如蛋白質(zhì)功能檢測(cè)[7-8]、圖像分類[9-12]等。

HMC算法一般通過(guò)優(yōu)化局部或者全局的損失函數(shù)來(lái)選擇層次標(biāo)簽樹(shù)上一條或者多條路徑以標(biāo)示實(shí)例[13]。執(zhí)行局部學(xué)習(xí)的算法嘗試挖掘類層次結(jié)構(gòu)的區(qū)域特征，然后將預(yù)測(cè)結(jié)果進(jìn)行組合得到最終分類結(jié)果。而基于全局的方法往往由單個(gè)分類器組成，并且能夠一次性找出實(shí)例相關(guān)聯(lián)的類標(biāo)簽。傳統(tǒng)的分類任務(wù)主要解決的是一個(gè)樣本e只會(huì)對(duì)應(yīng)于單個(gè)標(biāo)簽y∈L的問(wèn)題，其中L是標(biāo)簽的集合，標(biāo)簽的數(shù)量大于等于二，即通常所說(shuō)的多類分類。然而，有些分類問(wèn)題會(huì)更加復(fù)雜，因?yàn)橐粋€(gè)樣本可以對(duì)應(yīng)多個(gè)標(biāo)簽。一個(gè)多標(biāo)簽數(shù)據(jù)集D由N個(gè)樣本組成，每一個(gè)樣本會(huì)對(duì)應(yīng)一個(gè)標(biāo)簽集合Y，其中Y∈L。當(dāng)這些標(biāo)簽之間存在某種預(yù)定義的結(jié)構(gòu)(樹(shù)形或者有向無(wú)環(huán)圖)時(shí)，該任務(wù)稱為層次多標(biāo)簽分類。樹(shù)形結(jié)構(gòu)與有向無(wú)環(huán)圖的主要區(qū)別在于圖形結(jié)構(gòu)中一個(gè)節(jié)點(diǎn)可以有多于一個(gè)的父節(jié)點(diǎn),為了簡(jiǎn)化問(wèn)題，文中只考慮樹(shù)形層次結(jié)構(gòu)。

基于局部分類方法，在層次結(jié)構(gòu)中的每一個(gè)標(biāo)簽節(jié)點(diǎn)訓(xùn)練一個(gè)分類器的基礎(chǔ)上提出新的HMC方法，通過(guò)分解問(wèn)題來(lái)達(dá)到層次多標(biāo)簽分類。對(duì)比之前的層次多標(biāo)簽分類方法，該方法的主要改進(jìn)有以下幾點(diǎn)：

·為層次樹(shù)的節(jié)點(diǎn)加權(quán)，使得每個(gè)節(jié)點(diǎn)標(biāo)簽分類錯(cuò)誤的權(quán)重隨著層次標(biāo)簽樹(shù)層次的下降而衰減。

·通過(guò)組合各節(jié)點(diǎn)的概率值和節(jié)點(diǎn)在路徑中的位置，對(duì)所有可能的預(yù)測(cè)路徑進(jìn)行打分，從而選出最佳路徑，即預(yù)測(cè)標(biāo)簽集。

·通過(guò)在尋找最優(yōu)的預(yù)測(cè)路徑之前對(duì)層次樹(shù)進(jìn)行裁剪，解決預(yù)測(cè)路徑不在層次樹(shù)葉子節(jié)點(diǎn)終止的層次多標(biāo)簽分類任務(wù)，即最具體的類別并未到達(dá)葉子節(jié)點(diǎn)。對(duì)層次標(biāo)簽樹(shù)進(jìn)行裁剪可以拋棄那些在真實(shí)標(biāo)簽集中不大可能出現(xiàn)的分支，減少了計(jì)算量和潛在的錯(cuò)誤。

1 相關(guān)工作

在HMC任務(wù)中，屬于某個(gè)類的示例自動(dòng)屬于這個(gè)類的所有超類(層次約束)。這里有兩種預(yù)測(cè)結(jié)果[1]：強(qiáng)制性葉節(jié)點(diǎn)預(yù)測(cè)，返回的是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的完整路徑；非強(qiáng)制性葉節(jié)點(diǎn)預(yù)測(cè)，預(yù)測(cè)出來(lái)的路徑可能未到達(dá)葉子節(jié)點(diǎn)。

HMC根據(jù)其用于解決分類問(wèn)題的探測(cè)策略進(jìn)行分類，其中比較常見(jiàn)的方法為：直接法、全局法、自頂向下。直接法的分類策略借鑒于傳統(tǒng)的多標(biāo)簽分類，只能預(yù)測(cè)層次樹(shù)中的葉子節(jié)點(diǎn)，預(yù)測(cè)出一個(gè)葉子節(jié)點(diǎn)則到達(dá)該葉子節(jié)點(diǎn)路徑上的所有節(jié)點(diǎn)都被標(biāo)記為正，該方法有一個(gè)顯著的缺點(diǎn)是完全忽略了標(biāo)簽之間的層次關(guān)系。然而，這種簡(jiǎn)單的分類策略必須解決的是，需要訓(xùn)練一個(gè)分類器來(lái)區(qū)分一個(gè)龐大的目標(biāo)標(biāo)簽集(所有葉子節(jié)點(diǎn))，并且沒(méi)有利用標(biāo)簽集提供的層次關(guān)系。當(dāng)然，這種方法只能預(yù)測(cè)層次樹(shù)中的葉子節(jié)點(diǎn)，所以對(duì)于非強(qiáng)制性葉節(jié)點(diǎn)的數(shù)據(jù)集也就無(wú)能為力。全局方法對(duì)標(biāo)簽集中的所有類學(xué)習(xí)一個(gè)單一的模型來(lái)預(yù)測(cè)層次樹(shù)中的所有類，例如，對(duì)于一個(gè)深度為3的二叉樹(shù)，總共有14個(gè)非葉子節(jié)點(diǎn)和葉子節(jié)點(diǎn)，所以基于全局的分類方法需要訓(xùn)練一個(gè)針對(duì)14個(gè)標(biāo)簽的分類器。該分類算法生成的模型在一次運(yùn)行期間考慮了類層次結(jié)構(gòu)上所有的類標(biāo)簽。基于全局方法的主要限制是隨著數(shù)據(jù)集的增大，模型會(huì)過(guò)于復(fù)雜并且訓(xùn)練模型會(huì)花費(fèi)大量時(shí)間。該方面已有不少研究成果，Vens[13]，Blockeel和Bruynooghe[14]等都是基于預(yù)測(cè)聚類樹(shù)(PCT)的決策樹(shù)歸納算法來(lái)解決HMC問(wèn)題，后者根據(jù)層次樹(shù)中的多個(gè)節(jié)點(diǎn)的距離來(lái)導(dǎo)出預(yù)測(cè)類向量與真實(shí)類向量的距離度量。

基于局部分類器的HMC通過(guò)挖掘節(jié)點(diǎn)在層次結(jié)構(gòu)中的局部信息來(lái)考慮類標(biāo)簽的層次關(guān)系，該方法可以根據(jù)局部上下文信息的組織方式和本地分類器構(gòu)建方式的不同加以區(qū)分。特別地，主要有三種利用局部信息的方式：為每一個(gè)節(jié)點(diǎn)建立一個(gè)分類器(LCN)，為每一個(gè)父節(jié)點(diǎn)建立一個(gè)分類器(LCNP)，為每一個(gè)層次建立一個(gè)分類器(LCL)。這三種局部層次分類算法在模型訓(xùn)練階段存在顯著差異，但是在預(yù)測(cè)階段都是基于相似的自頂向下方法。在預(yù)測(cè)階段，這種自頂向下的方法先預(yù)測(cè)該層次樹(shù)的根節(jié)點(diǎn)的類，然后根據(jù)預(yù)測(cè)出來(lái)的類縮小在下一層次所需預(yù)測(cè)的類的數(shù)目，如此循環(huán)直至所有特殊的節(jié)點(diǎn)都被預(yù)測(cè)出來(lái)。該自頂向下模式的限制是上層的分類錯(cuò)誤將在層次結(jié)構(gòu)中向下傳播。

LCN方法為層次樹(shù)中的所有節(jié)點(diǎn)都訓(xùn)練一個(gè)二分類器(除了根節(jié)點(diǎn))。Bi和Kwok[15-16]提出了HIROM方法，該方法使用獨(dú)立于局部模型的局部預(yù)測(cè)方法，同時(shí)使用貪心算法在層次標(biāo)簽樹(shù)中搜索滿足層次約束的結(jié)果標(biāo)簽集。采用貝葉斯決策理論，通過(guò)最小化條件風(fēng)險(xiǎn)來(lái)得出最優(yōu)預(yù)測(cè)。該方法的局限性在于該優(yōu)化指標(biāo)在其他評(píng)估措施中不一定有效。LCNP方法為層次標(biāo)簽樹(shù)中的所有父節(jié)點(diǎn)訓(xùn)練一個(gè)多標(biāo)簽分類器，以區(qū)分各個(gè)子節(jié)點(diǎn)。在預(yù)測(cè)階段，該方法也可以結(jié)合上述自頂向下的預(yù)測(cè)方法。

2 路徑選擇

在機(jī)器學(xué)習(xí)領(lǐng)域，多標(biāo)簽分類[17-20]受到廣泛關(guān)注，基于差別排名的方法已在文獻(xiàn)[21]提出,同時(shí)通過(guò)標(biāo)簽之間的依賴性來(lái)優(yōu)化分類結(jié)果，但是當(dāng)標(biāo)簽分層次組織時(shí)，卻很難發(fā)揮作用[2]。圖1為一棵層次標(biāo)簽樹(shù)，針對(duì)該任務(wù)，提出了基于路徑選擇的層次多標(biāo)簽分類(based on path seletion，BPS)。該方法通過(guò)探索層次樹(shù)中標(biāo)簽節(jié)點(diǎn)和該節(jié)點(diǎn)的所有祖先節(jié)點(diǎn)的上下文關(guān)系來(lái)得到最優(yōu)的分類結(jié)果，同時(shí)使用計(jì)算規(guī)則評(píng)估從根到葉或中間節(jié)點(diǎn)的每個(gè)可能路徑，該計(jì)算規(guī)則考慮了預(yù)測(cè)標(biāo)簽節(jié)點(diǎn)所在的層次來(lái)計(jì)算各個(gè)路徑的得分，并最終返回滿足閾值條件和層次約束的最優(yōu)節(jié)點(diǎn)集。

圖1 層次標(biāo)簽樹(shù)

2.1 訓(xùn)練分類器

令D為具有N個(gè)實(shí)例的訓(xùn)練集,Ee=(Xe,Ye)，其中Xe為d維特征向量，Ye∈L，L={y1,y2,…,y|l|}，表示|l|可能的標(biāo)簽或類組成的有限集合，即所有樣本對(duì)應(yīng)的標(biāo)簽集合。需要注意的是與L相比，Ye是一個(gè)較小的集合。Ye可以用一個(gè)0/1向量來(lái)表示，即Ye∈{0,1}|l|，當(dāng)且僅當(dāng)yi∈Ye時(shí)，yi=1，否則yi=0。基于路徑選擇的層次多標(biāo)簽分類算法，除了根節(jié)點(diǎn)外，在層次樹(shù)中的所有其他節(jié)點(diǎn)都表示一個(gè)標(biāo)簽或者一個(gè)類，用yi表示，其中i為層次樹(shù)按層次遍歷的次序。對(duì)于每一個(gè)非葉子節(jié)點(diǎn)yi，訓(xùn)練一個(gè)標(biāo)簽多類分類器Ci，后面稱之為基分類器。使用該方法對(duì)較大的層次結(jié)構(gòu)具有很好的擴(kuò)展性，只要返回與預(yù)測(cè)類相關(guān)聯(lián)的概率值或其返回值可以轉(zhuǎn)化為概率值的多類分類器都可以作為基分類器。對(duì)于多類分類器Ci所包含的預(yù)測(cè)類別標(biāo)簽有節(jié)點(diǎn)標(biāo)簽yi的所有孩子節(jié)點(diǎn)標(biāo)簽(child(yi)),再加上一個(gè)“unknown”標(biāo)簽代表那些不屬于child(yi)的樣本。

把多類分類器Ci的訓(xùn)練樣本分成兩部分，其中一部分樣本由child(yi)=1的實(shí)例組成，即這些實(shí)例對(duì)應(yīng)的標(biāo)簽集都含有yi的孩子節(jié)點(diǎn)標(biāo)簽(child(yi)∈Ye),用Tr+(Ci)表示。在這部分訓(xùn)練樣本集中，每一個(gè)樣本都會(huì)打上對(duì)應(yīng)的child(yi)標(biāo)簽。另一部分樣本由那些含有yi的兄弟節(jié)點(diǎn)標(biāo)簽(sib(yi))的不同樣本組成，用Tr-(Ci)表示。如果yi沒(méi)有兄弟節(jié)點(diǎn)，則在層次標(biāo)簽樹(shù)中向上搜索，找到離yi最近的含有兄弟節(jié)點(diǎn)的祖先節(jié)點(diǎn)(sib(pa(yi)))，這些兄弟節(jié)點(diǎn)由yi父節(jié)點(diǎn)的所有子節(jié)點(diǎn)的集合除去節(jié)點(diǎn)yi的子集構(gòu)成。Tr-(Ci)對(duì)應(yīng)樣本集的標(biāo)簽不會(huì)含有yi的孩子標(biāo)簽，把這部分樣本標(biāo)記為“unknown”標(biāo)簽。同時(shí)考慮到訓(xùn)練數(shù)據(jù)的平衡性，需要對(duì)這部分?jǐn)?shù)據(jù)集進(jìn)行欠采樣，欠采樣的數(shù)量與每個(gè)yi孩子節(jié)點(diǎn)對(duì)應(yīng)訓(xùn)練樣本的平均值成正比。圖2描繪了構(gòu)造標(biāo)簽節(jié)點(diǎn)y5局部分類器C5的訓(xùn)練集實(shí)例的過(guò)程。數(shù)據(jù)集Tr+(C5)由滿足條件child(y5)={y6,y7}=1的樣本組成，這些樣本都標(biāo)記為對(duì)應(yīng)的child(y5)標(biāo)簽。而Tr-(C5)由sib(y5)={y8}的樣本組成，該數(shù)據(jù)集的樣本都標(biāo)記為“unknown”。同時(shí)需要對(duì)該數(shù)據(jù)集進(jìn)行欠采樣，從而保證該樣本集的數(shù)量與訓(xùn)練集中child(yi)的平均樣本數(shù)成比例。

圖2 基分類器

2.2 裁剪層次標(biāo)簽樹(shù)

某些情況下根據(jù)現(xiàn)有的信息不能很有把握地估計(jì)一個(gè)樣本在層次標(biāo)簽樹(shù)底部的標(biāo)簽，為了讓預(yù)測(cè)的標(biāo)簽節(jié)點(diǎn)路徑在未到葉子節(jié)點(diǎn)前終止，需要對(duì)層次標(biāo)簽樹(shù)進(jìn)行裁剪。裁剪可以以自下而上或者自上而下的方式進(jìn)行，這取決于層次結(jié)構(gòu)如何遍歷修剪，同時(shí)可以在分類階段之前執(zhí)行，或者首先修剪分類階段所選擇的路徑，同時(shí)裁剪可以根據(jù)不同的條件進(jìn)行。文獻(xiàn)[2]中進(jìn)行了幾個(gè)實(shí)驗(yàn)評(píng)估裁剪的最優(yōu)策略，根據(jù)該結(jié)果選用自頂向下測(cè)試標(biāo)簽節(jié)點(diǎn)的每條后代分支進(jìn)行裁剪。為了對(duì)一個(gè)新的實(shí)例進(jìn)行分類，實(shí)例的標(biāo)簽集對(duì)應(yīng)于層次標(biāo)簽樹(shù)的一條路徑或者多條路徑。為了選出對(duì)應(yīng)的路徑，需要為每條可能的路徑計(jì)算出相應(yīng)的概率值。對(duì)層次樹(shù)裁剪需要在計(jì)算各路徑得分之前進(jìn)行，裁剪路徑的條件是節(jié)點(diǎn)最可能的子節(jié)點(diǎn)的概率值小于“unkown”標(biāo)簽的概率。該方法的理由是，當(dāng)一個(gè)分類器預(yù)測(cè)的最可能的類不是該分類器對(duì)應(yīng)標(biāo)簽節(jié)點(diǎn)的孩子節(jié)點(diǎn)時(shí)，就有很大的把握對(duì)該路徑進(jìn)行剪枝。

裁剪過(guò)程由算法1進(jìn)行描述，該過(guò)程發(fā)生在獲得針對(duì)給定樣本xi的情況下層次標(biāo)簽樹(shù)中每個(gè)節(jié)點(diǎn)的概率值。從根節(jié)點(diǎn)開(kāi)始，將節(jié)點(diǎn)yi最可能的孩子節(jié)點(diǎn)的概率值(maxConfidence)與節(jié)點(diǎn)未知的概率值(unknown)相繼進(jìn)行比較。如果maxConfidence大于unknown,則該過(guò)程在節(jié)點(diǎn)yi的各子節(jié)點(diǎn)上迭代進(jìn)行，否則節(jié)點(diǎn)yi的子孫節(jié)點(diǎn)都將剪去，如果一個(gè)節(jié)點(diǎn)沒(méi)有兄弟節(jié)點(diǎn)，則在層次標(biāo)簽樹(shù)中向上搜索其祖先節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。為了在修剪后的層次標(biāo)簽樹(shù)中搜索出最優(yōu)的一條或者多條路徑，需要為層次標(biāo)簽樹(shù)中的路徑計(jì)算相應(yīng)的得分。

2.3 計(jì)算層次標(biāo)簽樹(shù)路徑得分

該合并規(guī)則將路徑上每個(gè)局部分類器的預(yù)測(cè)結(jié)果合并為一個(gè)分值，并且考慮標(biāo)簽節(jié)點(diǎn)在層次結(jié)構(gòu)中的層次，以確定該節(jié)點(diǎn)在所有分值中的權(quán)重。錯(cuò)誤的分類發(fā)生在層次標(biāo)簽樹(shù)的頂部的代價(jià)往往比發(fā)生在層次標(biāo)簽樹(shù)的底部大，在層次樹(shù)的頂部有更多的訓(xùn)練樣本并且類別之間也有更大的差異，對(duì)分類的貢獻(xiàn)也就更大。

為了達(dá)到該目的，節(jié)點(diǎn)yi的權(quán)重定義如式1。

(1)

其中，level(yi)表示節(jié)點(diǎn)標(biāo)簽yi在層次標(biāo)簽樹(shù)的層次，即該節(jié)點(diǎn)的父節(jié)點(diǎn)層次加1；maxlevel表示層次標(biāo)簽樹(shù)中最長(zhǎng)路徑的長(zhǎng)度。式1定義的節(jié)點(diǎn)權(quán)重可以隨著節(jié)點(diǎn)層次的降低而線性衰減，從而保證權(quán)重沿層次分布均勻。使得較低層次節(jié)點(diǎn)的權(quán)重既不會(huì)快速下降為0[12]，也不會(huì)衰減得太慢[13]。

式2定義了每條路徑的得分計(jì)算方法，它是沿著路徑節(jié)點(diǎn)上預(yù)測(cè)概率的加權(quán)和。

(2)

其中，q為路徑中的節(jié)點(diǎn)數(shù)；yi為路徑中的第i個(gè)節(jié)點(diǎn)；p(yi|xe)為實(shí)例xe在節(jié)點(diǎn)yi被局部分類器預(yù)測(cè)為真的概率；下標(biāo)k表示第k條路徑，則scorek為第k條路徑的得分。

圖3描述了計(jì)算路徑得分的執(zhí)行過(guò)程。首先計(jì)算概率和權(quán)重，然后利用式2合并成一個(gè)分值，選定相應(yīng)的閾值σ，分值大于σ的路徑都作為最終預(yù)測(cè)返回。閾值σ可以根據(jù)測(cè)試數(shù)據(jù)集進(jìn)行訓(xùn)練得出，返回路徑上除了根節(jié)點(diǎn)以外的節(jié)點(diǎn)標(biāo)簽組成的集合就是預(yù)測(cè)樣本對(duì)應(yīng)的預(yù)測(cè)標(biāo)簽集。假設(shè)訓(xùn)練得到閾值σ為0.5,在圖3的層次標(biāo)簽樹(shù)各路徑的得分中有兩條路徑得分大于0.5，故返回的集合為{y1,y2,y6,y7,y10}。

圖3 路徑得分計(jì)算示例

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)使用了三種數(shù)據(jù)集，其中兩種來(lái)自功能基因組學(xué)領(lǐng)域[6,8],一種來(lái)自圖像分類領(lǐng)域[22-23]，見(jiàn)表1，其中|L|為類別標(biāo)簽的個(gè)數(shù)，A為特征維度，N為樣本個(gè)數(shù)，D為層次標(biāo)簽樹(shù)的高度。

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

算法描述如下：

算法1：Prune裁剪層次標(biāo)簽樹(shù)算法，LC(yi)表示在節(jié)點(diǎn)yi運(yùn)行局部分類器

輸入：confidences(一個(gè)由在位置j的標(biāo)簽節(jié)點(diǎn)yj的概率值p(yi|xe)組成的數(shù)組)，yi(層次標(biāo)簽樹(shù)的根節(jié)點(diǎn))，C(由層次標(biāo)簽樹(shù)中除葉子節(jié)點(diǎn)外每個(gè)標(biāo)簽節(jié)點(diǎn)的基分類器組成的集合)

輸出：裁剪之后的層次標(biāo)簽樹(shù)

ifyiis not a left and has not been visited before then

if all pa(yi) have been visited then

markyivisited

maxConfidence=0

totalConfidence= 0

for allyj∈child(yi) do

totalConfidence=toalConfidence+confidences[j]

if confidences[j]>maxConfidence then

maxConfidence=confidences[j]

end if

end for

Unknown=1-totalConfidences

if maxConfidence>unknown then

for allyj∈child(yi) do

LC(yi)

end for

else

Prune descendants ofyi

end if

else

continue with another node

end if

end if

3.1 評(píng)估指標(biāo)

在HMC的情況下，評(píng)估指標(biāo)的定義并不像二分類那么直觀，因?yàn)轭A(yù)測(cè)可以是部分正確的，對(duì)于該問(wèn)題已提出相關(guān)針對(duì)多標(biāo)簽分類[24]和HMC[25]的特殊的評(píng)估指標(biāo)。

Full-Match:式3表示測(cè)試集中預(yù)測(cè)的標(biāo)簽路徑完全正確的樣本占全部樣本的比例，即預(yù)測(cè)的標(biāo)簽集和真實(shí)的標(biāo)簽集完全相同。

(3)

Accuracy[26]：式4表示預(yù)測(cè)標(biāo)簽集和真實(shí)標(biāo)簽集交集的大小與并集的大小的比例。

(4)

(5)

用向量Z替換向量Yi。對(duì)于多標(biāo)簽分類，有多種方法對(duì)F1-measure進(jìn)行平均，主要取以下兩種方法:

F1-macroD是對(duì)樣本個(gè)數(shù)取平均：

(6)

其中，zi≡Yi，N為樣本個(gè)數(shù)。

F1-macroL是對(duì)標(biāo)簽個(gè)數(shù)取平均：

(7)

F1-macroL指標(biāo)對(duì)每一個(gè)標(biāo)簽節(jié)點(diǎn)的分類效果進(jìn)行評(píng)估，而F1-macroD指標(biāo)是對(duì)每一個(gè)樣本的分類效果進(jìn)行評(píng)估。

3.2 基分類器

該節(jié)設(shè)計(jì)了一個(gè)實(shí)驗(yàn)來(lái)分析不同基分類器對(duì)基于路徑選擇的層次多標(biāo)簽分類算法性能的影響,并選擇最適合該數(shù)據(jù)集的基分類器對(duì)算法進(jìn)行測(cè)試。使用十折交叉驗(yàn)證對(duì)三份數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，根據(jù)3.1節(jié)介紹的四種不同的層次度量方法來(lái)比較該層次多標(biāo)簽分類算法的性能。使用四種常見(jiàn)的方法作為基分類器：支持向量機(jī)(SVM)，核函數(shù)使用多項(xiàng)式核函數(shù)；C4.5，用于剪枝的置信度設(shè)置為0.35，每個(gè)葉子的最小實(shí)例數(shù)設(shè)置為3；樸素貝葉斯(NB)；隨機(jī)森林(RF)，生成十棵樹(shù)。

實(shí)驗(yàn)結(jié)果見(jiàn)表2。

表2 不同基分類器的性能度量 %

可以觀察到，隨機(jī)森林在所有評(píng)估指標(biāo)中表現(xiàn)最好，其次是樸素貝葉斯。因?yàn)殡S機(jī)森林能夠處理比較大的不平衡數(shù)據(jù)，并且能夠有效處理存在噪聲的數(shù)據(jù)，所選擇的驗(yàn)證數(shù)據(jù)都存在這些特征。因此，選用隨機(jī)森林作為其余實(shí)驗(yàn)的基分類器。

3.3 與多類分類和多標(biāo)簽分類的比較

在該實(shí)驗(yàn)中，將文中方法與兩個(gè)未考慮層次結(jié)構(gòu)的替代方法進(jìn)行對(duì)比。

(1)多類分類(multi-class classification，MC):一種僅預(yù)測(cè)層次結(jié)構(gòu)葉子節(jié)點(diǎn)的多類分類器。

(2)鏈?zhǔn)椒诸惼?classification chains，CC)：為層次標(biāo)簽樹(shù)中每一個(gè)標(biāo)簽節(jié)點(diǎn)分別建立一個(gè)二分類器，并且各個(gè)分類器根據(jù)父子關(guān)系構(gòu)成鏈?zhǔn)浇Y(jié)構(gòu)的多標(biāo)簽分類方法。在預(yù)測(cè)階段，它根據(jù)鏈?zhǔn)浇Y(jié)構(gòu)將先前分類器的輸出結(jié)果作為附加屬性，然后在層次標(biāo)簽樹(shù)中選擇最優(yōu)子樹(shù)標(biāo)簽集作為最終結(jié)果輸出[28-29]。

實(shí)驗(yàn)結(jié)果見(jiàn)圖4。

圖4 三種分類方法在數(shù)據(jù)集上的表現(xiàn)

所有數(shù)據(jù)都是在各個(gè)數(shù)據(jù)集上相應(yīng)指標(biāo)的平均值，同時(shí)記錄了對(duì)應(yīng)的標(biāo)準(zhǔn)差。從圖中可以看出，盡管MC方法在大多數(shù)指標(biāo)下都是較優(yōu)的，并且有一些顯著優(yōu)越的結(jié)果，但是BPS在層次標(biāo)簽樹(shù)較淺或者葉子節(jié)點(diǎn)較少的數(shù)據(jù)集中具有競(jìng)爭(zhēng)力(Fun數(shù)據(jù)集層次結(jié)構(gòu)為4層，大約15個(gè)葉子節(jié)點(diǎn))?？梢钥吹皆摲椒ㄔ贏ccuracy和Full-match兩個(gè)指標(biāo)有較好的結(jié)果，這些指標(biāo)對(duì)預(yù)測(cè)結(jié)果中出現(xiàn)的錯(cuò)誤進(jìn)行了度量。這意味著文中方法如果基分類器輸出的概率值過(guò)低，會(huì)對(duì)層次標(biāo)簽樹(shù)進(jìn)行裁剪，而MC方法返回完整的路徑可能是不正確的。對(duì)于層次標(biāo)簽樹(shù)高度較高但標(biāo)簽節(jié)點(diǎn)不是很稠密的數(shù)據(jù)集(GO數(shù)據(jù)集層次結(jié)構(gòu)為11層，大約24個(gè)葉子節(jié)點(diǎn))，大多數(shù)情況下，文中方法比MC方法能獲得更好的結(jié)果。

在基因組數(shù)據(jù)集中，文中方法和MC方法的性能差異很小，是因?yàn)樵谌~子節(jié)點(diǎn)較少的層次結(jié)構(gòu)中，MC方法往往能返回良好的結(jié)果。然而，從Caltech數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可以看到，當(dāng)層次標(biāo)簽樹(shù)中有較多的葉子節(jié)點(diǎn)時(shí)就很難用單一的分類器來(lái)區(qū)分不同的路徑。Caltech數(shù)據(jù)集含有256和84個(gè)葉子節(jié)點(diǎn)，五個(gè)度量指標(biāo)數(shù)據(jù)都表明筆者的方法要優(yōu)于MC方法。故在大型層次結(jié)構(gòu)中文中方法要優(yōu)于MC方法。同時(shí)基于路徑選擇的層次多標(biāo)簽分類(BPS)對(duì)于多標(biāo)簽鏈分類(CC)也是很有競(jìng)爭(zhēng)力的，除了在Full-match指標(biāo)下BPS要明顯優(yōu)于CC，其他指標(biāo)都有相似的結(jié)果，但是BPS計(jì)算性能要優(yōu)于CC。

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

提出了一種新穎的基于路徑選擇的層次多標(biāo)簽分類方法，可以用于解決標(biāo)簽節(jié)點(diǎn)路徑在層次標(biāo)簽樹(shù)內(nèi)節(jié)點(diǎn)終止的數(shù)據(jù)集。BPS為層次標(biāo)簽樹(shù)中每一個(gè)內(nèi)節(jié)點(diǎn)訓(xùn)練一個(gè)多類分類器，同時(shí)用含有該節(jié)點(diǎn)兄弟節(jié)點(diǎn)標(biāo)簽的數(shù)據(jù)集構(gòu)成未知標(biāo)簽樣本，用于層次樹(shù)的裁剪。該方法在層次標(biāo)簽樹(shù)中選擇路徑得分超過(guò)一定閾值的一條或多條路徑，其中路徑得分是結(jié)合路徑上對(duì)應(yīng)標(biāo)簽節(jié)點(diǎn)基分類器的預(yù)測(cè)值和該節(jié)點(diǎn)在層次標(biāo)簽樹(shù)中的層次賦予不同的權(quán)重計(jì)算得到。為了使預(yù)測(cè)的標(biāo)簽路徑在層次標(biāo)簽樹(shù)的內(nèi)節(jié)點(diǎn)終止，需要根據(jù)各標(biāo)簽節(jié)點(diǎn)基分類器對(duì)應(yīng)的子節(jié)點(diǎn)概率值進(jìn)行層次標(biāo)簽樹(shù)的裁剪，從而消除可能性較低的分支。使用三份不同的數(shù)據(jù)對(duì)基于路徑選擇的層次多標(biāo)簽分類方法進(jìn)行驗(yàn)證，同時(shí)與現(xiàn)有方法進(jìn)行比較，結(jié)果表明該方法均能取得較好的結(jié)果，并且在層次較深且葉子節(jié)點(diǎn)較多的層次結(jié)構(gòu)表現(xiàn)更優(yōu)。