面向泛娛樂文本的層次多標簽分類方法

陳若愚 劉秀磊 于汝意

1(北京信息科技大學網絡文化與數字傳播北京市重點實驗室 北京 100101) 2(北京信息科技大學數據與科學情報分析實驗室 北京 100101)

0 引 言

泛娛樂指的是以知識產權(Intellectual Property,IP)資源為核心，創建以互聯網和移動互聯網為基礎多個領域共生的粉絲經濟[1]。泛娛樂化現象的表現形式為內容生產的娛樂化，信息的內容、形式和包裝等各方面都滲入了娛樂元素[2]。隨著論壇、博客、網絡雜志及微博等互聯網媒體和手機等移動終端媒體的普及，大眾對網絡的使用由工作學習擴大到生活娛樂中。泛娛樂化現象延伸至互聯網等新型媒體中，同時互聯網等新型媒體的迅猛發展也加快了泛娛樂信息傳播速度。

在多標簽分類中，若類別標簽存在樹形結構或者有向無環圖等預定義結構時，將其稱之為層次多標簽分類。目前針對多標簽分類問題的解決主要有問題轉換和算法適應兩種方法[3-5]。問題轉換中常見的方法有二元關聯、分類器鏈等算法。二元關聯方法不考慮標簽關聯性，將多標簽學習問題進行轉化，將原問題轉換為多個獨立二分類問題。Read等[6]提出了分類器鏈算法，將原問題轉化為呈鏈式結構的二分類問題，基于前面分類器的輸出來預測后續分類器的結果[7]。該方法雖然考慮了標簽相關性，但因鏈式結構的串行化特點而無法實現并行化。算法適應中常見的方法有MLKNN、IMLIA和RankSVM等。MLKNN算法基于K近鄰算法改進而來，使得該算法可以處理多標簽分類問題，具有較好的表現[8]。但是MLKNN算法缺乏對標簽相關性的處理，因此張敏靈[9]對該算法進行改進，通過融合標簽相關性進而提出了IMLIA算法。RankSVM提出了一種新的思路，將原來的排序問題轉換成可以使用SVM算法解決的分類問題[10]。

層次多標簽分類在蛋白質功能預測、基因功能預測等領域具有較為廣泛的研究。在蛋白質功能預測領域，Otero等[11]提出了一種針對蛋白質功能預測的分層多標簽分類問題的蟻群優化算法，在涉及數百個或數千個類別標簽的十六個具有挑戰性的生物信息學數據集上進行評估，并將其與用于分層多標簽分類的最新決策樹歸納算法進行比較，取得了較好的效果。Cerri等[12]提出了一種名為HMC-LMLP的局部方法，該方法在每個層次級別使用一個多層感知器，上一級的預測結果作為下一級預測的網絡的輸入，而且利用兩種截然不同的多層感知器算法：反向傳播和彈性反向傳播。另外，該方法還使用專門針對多標簽問題的錯誤度量來訓練網絡。在蛋白質功能預測數據集中，該方法具有競爭性的預測準確性。Yuan等[13]提出了具有多個頭部和多個末端的深度神經網絡(DNN)模型，該方法在基準數據集上相較于傳統方法有明顯提升。在基因功能預測領域，Barutcuoglu等[14]提出了一個貝葉斯框架，利用基于功能分類約束來組合多個分類器。通過在貝葉斯框架中組合預測，以獲得最可能的一致預測集；該方法在GO的105個節點的子層次結構中，該框架改進了對93個節點的預測，取得了較好的效果。Stojanova等[15]提出了一種基于樹的算法，用于在分層多標簽分類(HMC)設置中，該算法考慮網絡自相關，利用2個不同的PPI網絡，在12個酵母數據集上取得了顯著的效果。Fodeh等[16]提出了一種創新的預測系統的開發和評估方法，利用非負矩陣分解(NMF)進行特征縮減，使用二進制相關方法對基因進行分類，并嘗試了幾種分類器，表明二元關聯和K最近鄰(KNN)分類器的組合效果最好，在UniProtKB/Swiss-Prot數據集的評估顯示，按照F1量度，最佳性能為0.84。Li等[17]通過使用基因本體層次結構注釋基因功能來改進多實例層次聚類，該方法將基因本體層次結構與多實例多標簽學習框架結構結合在一起。使用多標簽支持向量機(MLSVM)和多標簽K最近鄰算法(MLKNN)來預測基因的功能。

雖然上述算法在各自領域數據集上取得了較好的效果，但是并未對泛娛樂領域層次結構中有向無環圖結構的數據處理提供解決方法。本文在總結分析現有的層次多標簽分類算法的基礎上，提出一種基于最優路徑的層次多標簽分類方法。該方法首先根據現有標簽構建DAG結構并將DAG結構轉化為較易處理的樹形結構；然后，采用局部策略為樹形結構中每個節點分別訓練基分類器，同時為每個節點設置貢獻值，貢獻值由分類器輸出概率與層次權重組合而成，貢獻值大于閾值時該節點設置為1，否則為0；最后，對樹形結構進行深度優先遍歷生成路徑，計算各路徑得分，選擇滿足層次約束且得分最高的路徑作為最終預測集合。

1 基于最優路徑層次多標簽分類方法

泛娛樂領域層次多標簽分類中，標簽之間一般具有層次結構特征，如圖1所示。針對現有標簽的層次結構，為了融合標簽間關聯性，提高分類器分類性能，本文提出基于最優路徑層次多標簽分類方法。首先，根據標簽層次結構構建有向無環圖結構并隨后轉化為樹形結構；然后，采用局部策略為結構中的每個節點對應的標簽訓練一個分類器；其中，基分類器采用支持向量機方法；最后，通過組合各路徑中各節點的預測結果得到整體預測結果，設計路徑打分策略，根據閾值和層次約束，選擇最優路徑作為最終預測標簽集合。

圖1 泛娛樂文本情報類別標簽層次結構

1.1 層次結構構建

當前的主要標簽體系如圖2所示。一級標簽“文化娛樂”；二級標簽有“新聞傳媒”“網絡視頻”“網絡文學”“直播”和“用戶業務”；三級標簽有“綜合資訊”“其他資訊”“游戲直播”“娛樂直播”“知識付費”和“用戶付費”等。其中“其他資訊”標簽下的數據由“媒體號”“科技資訊”“軍事資訊”和“報紙雜志”等合并而成。正如圖2中二級標簽下實線框內的標簽，此類標簽下的數據量較少，不再為該標簽訓練分類器，后期由人工標注。本文處理的標簽為圖2中虛線框內的標簽。

圖2 標簽體系

層次多標簽分類中，根據面臨的標簽體系，分為樹形結構和有向無環圖結構。不同于樹形結構，有向無環圖結構節點能存在多個父節點。目前的標簽體系中，三級標簽“短視頻”“在線視頻”屬于二級標簽“網絡視頻”，也屬于二級標簽“直播”，存在一個節點有多個父節點的結構特征。因此，根據當前面對的標簽結構特征，構建有向無環圖結構，用于挖掘標簽的層次結構信息。

本文將有向無環圖結構轉化為樹形結構進行層次多標簽文本分類。初始時設置DAG結構中所有節點的Visited屬性為False,對DAG結構進行廣度優先遍歷，如果遍歷到的節點Visited屬性為True,則復制該節點及其子節點，并且子節點的Visited屬性設置為False，更新該節點的父節點的指針，指向新增節點；如果遍歷到的節點Visited屬性為False，則將該節點的Visited屬性設置為True。

如圖3所示，將DAG結構轉換成Tree結構。節點D第二次遍歷時，Visited屬性已經設置為True，因此復制D節點，生成節點D2，并更改父節點的指針，指向節點D2，轉化后如圖3中的TREE。

圖3 DAG結構轉TREE結構

1.2 局部分類器訓練

SVM在解決問題時將結構風險以及經驗風險最小化作為考察因素，所以具有穩定性。SVM采用鉸鏈損失函數作為代價函數，由于支持向量唯一決定了決策邊界，其取值特點導致支持向量機具有稀疏性。考慮到支持向量機穩定性、稀疏性的優點，以及本文研究內容使用的數據集特點，采用支持向量機作為基分類器。

對于具有N個實例的語料，分配80%的實例作為訓練集，記為D，其他實例作為測試集T。Le=(Xe,Ye)，其中：Xe為300維的特征向量，Ye∈L;L={y1,y2,…,yn}，表示實例所屬的類別或標簽的有限集合。Ye是L的元素，若某實例在某類別下判定為正，則yi=1，若實例在某類別下判定為負，則yi=0，因此Ye∈{0,1}n。

除了根節點之外，在層次結構中的所有節點都表示一個類別或者標簽，用yi表示，針對每一個非葉節點，yi訓練一個分類器Ci。基分類器Ci可以選擇能給出預測類別的概率值或者可以把返回值轉化成概率值的多類分類器。基分類器預測的樣本包含yi標簽下的樣本以及yi標簽的子標簽下的樣本，記為child(yi)，不歸屬于yi和child(yi)的樣本，記為unchild(yi)。基分類器的訓練正樣本由child(yi)為1的樣本構成，這些樣本的標注的標簽集合都含有yi的子節點標簽，用PS(Ci)表示。基分類器訓練集的負樣本由不歸屬于yi和child(

yi)的樣本組成，用NS(Ci)表示。考慮到訓練數據的平衡性，有需要時對數據進行欠采樣，欠采樣數據的數量與yi及child(yi)對應的訓練樣本數量的均值成正比。圖4給出了節點y1基分類器訓練集構造過程。正樣本PS(C1)包含的數據為歸類到子標簽y3、y4的數據，負樣本NS(C1)包含的數據為不屬于y1標簽的y2、y5和y6標簽下的數據。考慮到正負樣本的均衡，定義正樣本的標簽個數為lc，樣本數量為InsC，則負樣本的樣本數量為正樣本各標簽數量的平均數，即：count=InsC/lc。

1.3 最優路徑選擇

基于最優路徑的層次多標簽分類技術通過局部策略為每個標簽訓練基分類器。每個節點的貢獻值C由該節點所在層次的權重ω以及基分類器預測為正的概率P組合而成。通過組合路徑上各節點的貢獻值，將預測結果合并為一個二進制分值y。其中，權重由當前標簽在結構中所處的層次決定。錯誤的分類發生在頂部的代價往往比發生在底部的代價更大，同時層次高的標簽擁有更多的訓練數據以及類別之間具有大的差異性，對分類具有更高的貢獻，因此，層次越深，則權重越小，權重的計算式表示為：

(1)

式中：level(i)為節點i的層次深度；maxL為最長路徑長度；權重隨著層次加深而線性減小，保證權重延層均勻分布。每條路徑的得分計算為：

(2)

式中：scorem表示第m條路徑的得分；n表示路徑中的節點數；C(yi)表示節點yi的貢獻值；ω(yi)示節點yi的權重；P(yi|xe)表示對實例xe在局部基分類器yi預測為正的概率。

以圖5為例，圖中除root根節點外，每個節點均計算該節點的權重與概率輸出值。路徑得分為每條路徑上節點貢獻值的和，圖中有{y1,y3}、{y1,y4}、{y2,y5}、{y2,y6}四條路徑，對四條路徑的得分做排序，選擇最大的得分路徑作為預測標簽集合。圖中四條路徑對應的得分分別為1.025、0.950、0.625、0.725,則實例xe預測的標簽集合為{y1,y3}。特別地，選擇作為候選預測集合的路徑需滿足層次約束，父節點預測為正的路徑才能作為有效路徑進行后續的選擇最優路徑操作。

圖5 路徑得分計算示意圖

2 實驗與結果分析

2.1 實驗描述

本文使用的語料來源于互聯網中抓取的泛娛樂領域的“文化娛樂”公開資訊數據，數據標簽由領域專家進行標注，該數據已經過多個領域專家審核，共43 852條。表1給出了各級別標簽更詳細的統計數據。

表1 數據統計表

表2中，|P|表示類別標簽總數，PM表示每個樣本實例中平均擁有的標簽數量，D表示特征的維度，N表示樣本的總數，H表示層次標簽的深度。

表2 統計信息表

2.2 性能評估

本部分進行了5組實驗，分類器分別采用分類器鏈(CC)、二元關聯(BR)、MLKNN、SVM多標簽分類，以及基于最優路徑層次多標簽分類器(本文方法)。評價指標采用多標簽分類常用的漢明損失(Hamming Loss)、準確率(Accuracy)和宏平均Macro-F1值。對比實驗結果如表3所示。

表3 實驗結果對比表

其中漢明損失是常用的衡量多標簽分類效果的評價指標。漢明損失計算數據中被誤分類的標簽個數，漢明損失的值越小，則說明模型的效果越好，當漢明損失的值為0時，則說明該分類方法完全擬合所有數據，其計算公式如式(3)所示。

(3)

由圖6可知，本文提出的基于最優路徑的層次多標簽分類技術相比二元關聯、分類器鏈、SVMMLKNN算法，漢明損失更低，說明預測的標簽集合中錯誤樣本的比例相對更低。本文方法的準確率高于MLKNN的準確率、二元分類算法的準確率及分類器鏈算法的準確率。但是，準確率可能會受樣本影響，因此不能僅憑該評價指標衡量分類器性能的好壞。通過對比Macro-F1值，可以看出本文方法的Macro-F1值高于其他算法的Macro-F1值。通過對比分類器鏈、二元分類、SVM多標簽分類和MLKNN四種分類方法的實驗結果可知，本文方法的分類器性能更為優越。

圖6 實驗結果對比

3 結 語

由于泛娛樂文本情報預測類別標簽具備有向無環圖結構特性，本文針對該特性提出一種基于最優路徑層次多標簽分類方法。實驗證明，該方法相比未明確考慮標簽相關性的分類器鏈、二元關聯、MLKNN和SVM多標簽分類等算法，效果更優。該研究為泛娛樂領域文本情報層次多標簽分類提供了一種有效的實踐。然而，該方法基分類器采用的SVM，未針對不同節點的數據進行優化，同時隨著標簽的增加，每個節點訓練分類器的時間成本增加，因此，針對各節點個性化訓練基分類器以及訓練基分類器并行化將是下一步工作的重點和難題。