基于路徑選擇的層次多標簽分類

張春焰，李 濤，劉 崢

(南京郵電大學 計算機學院，江蘇 南京 210046)

0 引 言

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

HMC算法一般通過優化局部或者全局的損失函數來選擇層次標簽樹上一條或者多條路徑以標示實例[13]。執行局部學習的算法嘗試挖掘類層次結構的區域特征，然后將預測結果進行組合得到最終分類結果。而基于全局的方法往往由單個分類器組成，并且能夠一次性找出實例相關聯的類標簽。傳統的分類任務主要解決的是一個樣本e只會對應于單個標簽y∈L的問題，其中L是標簽的集合，標簽的數量大于等于二，即通常所說的多類分類。然而，有些分類問題會更加復雜，因為一個樣本可以對應多個標簽。一個多標簽數據集D由N個樣本組成，每一個樣本會對應一個標簽集合Y，其中Y∈L。當這些標簽之間存在某種預定義的結構(樹形或者有向無環圖)時，該任務稱為層次多標簽分類。樹形結構與有向無環圖的主要區別在于圖形結構中一個節點可以有多于一個的父節點,為了簡化問題，文中只考慮樹形層次結構。

基于局部分類方法，在層次結構中的每一個標簽節點訓練一個分類器的基礎上提出新的HMC方法，通過分解問題來達到層次多標簽分類。對比之前的層次多標簽分類方法，該方法的主要改進有以下幾點：

·為層次樹的節點加權，使得每個節點標簽分類錯誤的權重隨著層次標簽樹層次的下降而衰減。

·通過組合各節點的概率值和節點在路徑中的位置，對所有可能的預測路徑進行打分，從而選出最佳路徑，即預測標簽集。

·通過在尋找最優的預測路徑之前對層次樹進行裁剪，解決預測路徑不在層次樹葉子節點終止的層次多標簽分類任務，即最具體的類別并未到達葉子節點。對層次標簽樹進行裁剪可以拋棄那些在真實標簽集中不大可能出現的分支，減少了計算量和潛在的錯誤。

1 相關工作

在HMC任務中，屬于某個類的示例自動屬于這個類的所有超類(層次約束)。這里有兩種預測結果[1]：強制性葉節點預測，返回的是從根節點到葉子節點的完整路徑；非強制性葉節點預測，預測出來的路徑可能未到達葉子節點。

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

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

LCN方法為層次樹中的所有節點都訓練一個二分類器(除了根節點)。Bi和Kwok[15-16]提出了HIROM方法，該方法使用獨立于局部模型的局部預測方法，同時使用貪心算法在層次標簽樹中搜索滿足層次約束的結果標簽集。采用貝葉斯決策理論，通過最小化條件風險來得出最優預測。該方法的局限性在于該優化指標在其他評估措施中不一定有效。LCNP方法為層次標簽樹中的所有父節點訓練一個多標簽分類器，以區分各個子節點。在預測階段，該方法也可以結合上述自頂向下的預測方法。

2 路徑選擇

在機器學習領域，多標簽分類[17-20]受到廣泛關注，基于差別排名的方法已在文獻[21]提出,同時通過標簽之間的依賴性來優化分類結果，但是當標簽分層次組織時，卻很難發揮作用[2]。圖1為一棵層次標簽樹，針對該任務，提出了基于路徑選擇的層次多標簽分類(based on path seletion，BPS)。該方法通過探索層次樹中標簽節點和該節點的所有祖先節點的上下文關系來得到最優的分類結果，同時使用計算規則評估從根到葉或中間節點的每個可能路徑，該計算規則考慮了預測標簽節點所在的層次來計算各個路徑的得分，并最終返回滿足閾值條件和層次約束的最優節點集。

圖1 層次標簽樹

2.1 訓練分類器

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

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

圖2 基分類器

2.2 裁剪層次標簽樹

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

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

2.3 計算層次標簽樹路徑得分

該合并規則將路徑上每個局部分類器的預測結果合并為一個分值，并且考慮標簽節點在層次結構中的層次，以確定該節點在所有分值中的權重。錯誤的分類發生在層次標簽樹的頂部的代價往往比發生在層次標簽樹的底部大，在層次樹的頂部有更多的訓練樣本并且類別之間也有更大的差異，對分類的貢獻也就更大。

為了達到該目的，節點yi的權重定義如式1。

(1)

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

式2定義了每條路徑的得分計算方法，它是沿著路徑節點上預測概率的加權和。

(2)

其中，q為路徑中的節點數；yi為路徑中的第i個節點；p(yi|xe)為實例xe在節點yi被局部分類器預測為真的概率；下標k表示第k條路徑，則scorek為第k條路徑的得分。

圖3描述了計算路徑得分的執行過程。首先計算概率和權重，然后利用式2合并成一個分值，選定相應的閾值σ，分值大于σ的路徑都作為最終預測返回。閾值σ可以根據測試數據集進行訓練得出，返回路徑上除了根節點以外的節點標簽組成的集合就是預測樣本對應的預測標簽集。假設訓練得到閾值σ為0.5,在圖3的層次標簽樹各路徑的得分中有兩條路徑得分大于0.5，故返回的集合為{y1,y2,y6,y7,y10}。

圖3 路徑得分計算示例

3 實驗結果與分析

實驗使用了三種數據集，其中兩種來自功能基因組學領域[6,8],一種來自圖像分類領域[22-23]，見表1，其中|L|為類別標簽的個數，A為特征維度，N為樣本個數，D為層次標簽樹的高度。

表1 實驗數據

算法描述如下：

算法1：Prune裁剪層次標簽樹算法，LC(yi)表示在節點yi運行局部分類器

輸入：confidences(一個由在位置j的標簽節點yj的概率值p(yi|xe)組成的數組)，yi(層次標簽樹的根節點)，C(由層次標簽樹中除葉子節點外每個標簽節點的基分類器組成的集合)

輸出：裁剪之后的層次標簽樹

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 評估指標

在HMC的情況下，評估指標的定義并不像二分類那么直觀，因為預測可以是部分正確的，對于該問題已提出相關針對多標簽分類[24]和HMC[25]的特殊的評估指標。

Full-Match:式3表示測試集中預測的標簽路徑完全正確的樣本占全部樣本的比例，即預測的標簽集和真實的標簽集完全相同。

(3)

Accuracy[26]：式4表示預測標簽集和真實標簽集交集的大小與并集的大小的比例。

(4)

(5)

用向量Z替換向量Yi。對于多標簽分類，有多種方法對F1-measure進行平均，主要取以下兩種方法:

F1-macroD是對樣本個數取平均：

(6)

其中，zi≡Yi，N為樣本個數。

F1-macroL是對標簽個數取平均：

(7)

F1-macroL指標對每一個標簽節點的分類效果進行評估，而F1-macroD指標是對每一個樣本的分類效果進行評估。

3.2 基分類器

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

實驗結果見表2。

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

可以觀察到，隨機森林在所有評估指標中表現最好，其次是樸素貝葉斯。因為隨機森林能夠處理比較大的不平衡數據，并且能夠有效處理存在噪聲的數據，所選擇的驗證數據都存在這些特征。因此，選用隨機森林作為其余實驗的基分類器。

3.3 與多類分類和多標簽分類的比較

在該實驗中，將文中方法與兩個未考慮層次結構的替代方法進行對比。

(1)多類分類(multi-class classification，MC):一種僅預測層次結構葉子節點的多類分類器。

(2)鏈式分類器(classification chains，CC)：為層次標簽樹中每一個標簽節點分別建立一個二分類器，并且各個分類器根據父子關系構成鏈式結構的多標簽分類方法。在預測階段，它根據鏈式結構將先前分類器的輸出結果作為附加屬性，然后在層次標簽樹中選擇最優子樹標簽集作為最終結果輸出[28-29]。

實驗結果見圖4。

圖4 三種分類方法在數據集上的表現

所有數據都是在各個數據集上相應指標的平均值，同時記錄了對應的標準差。從圖中可以看出，盡管MC方法在大多數指標下都是較優的，并且有一些顯著優越的結果，但是BPS在層次標簽樹較淺或者葉子節點較少的數據集中具有競爭力(Fun數據集層次結構為4層，大約15個葉子節點)。可以看到該方法在Accuracy和Full-match兩個指標有較好的結果，這些指標對預測結果中出現的錯誤進行了度量。這意味著文中方法如果基分類器輸出的概率值過低，會對層次標簽樹進行裁剪，而MC方法返回完整的路徑可能是不正確的。對于層次標簽樹高度較高但標簽節點不是很稠密的數據集(GO數據集層次結構為11層，大約24個葉子節點)，大多數情況下，文中方法比MC方法能獲得更好的結果。

在基因組數據集中，文中方法和MC方法的性能差異很小，是因為在葉子節點較少的層次結構中，MC方法往往能返回良好的結果。然而，從Caltech數據集的實驗結果可以看到，當層次標簽樹中有較多的葉子節點時就很難用單一的分類器來區分不同的路徑。Caltech數據集含有256和84個葉子節點，五個度量指標數據都表明筆者的方法要優于MC方法。故在大型層次結構中文中方法要優于MC方法。同時基于路徑選擇的層次多標簽分類(BPS)對于多標簽鏈分類(CC)也是很有競爭力的，除了在Full-match指標下BPS要明顯優于CC，其他指標都有相似的結果，但是BPS計算性能要優于CC。

4 結束語

提出了一種新穎的基于路徑選擇的層次多標簽分類方法，可以用于解決標簽節點路徑在層次標簽樹內節點終止的數據集。BPS為層次標簽樹中每一個內節點訓練一個多類分類器，同時用含有該節點兄弟節點標簽的數據集構成未知標簽樣本，用于層次樹的裁剪。該方法在層次標簽樹中選擇路徑得分超過一定閾值的一條或多條路徑，其中路徑得分是結合路徑上對應標簽節點基分類器的預測值和該節點在層次標簽樹中的層次賦予不同的權重計算得到。為了使預測的標簽路徑在層次標簽樹的內節點終止，需要根據各標簽節點基分類器對應的子節點概率值進行層次標簽樹的裁剪，從而消除可能性較低的分支。使用三份不同的數據對基于路徑選擇的層次多標簽分類方法進行驗證，同時與現有方法進行比較，結果表明該方法均能取得較好的結果，并且在層次較深且葉子節點較多的層次結構表現更優。