陳若愚 劉秀磊 于汝意

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

0 引 言

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

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

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

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

1 基于最優(yōu)路徑層次多標簽分類方法

泛娛樂領(lǐng)域?qū)哟味鄻撕灧诸愔校瑯撕炛g一般具有層次結(jié)構(gòu)特征，如圖1所示。針對現(xiàn)有標簽的層次結(jié)構(gòu)，為了融合標簽間關(guān)聯(lián)性，提高分類器分類性能，本文提出基于最優(yōu)路徑層次多標簽分類方法。首先，根據(jù)標簽層次結(jié)構(gòu)構(gòu)建有向無環(huán)圖結(jié)構(gòu)并隨后轉(zhuǎn)化為樹形結(jié)構(gòu)；然后，采用局部策略為結(jié)構(gòu)中的每個節(jié)點對應(yīng)的標簽訓(xùn)練一個分類器；其中，基分類器采用支持向量機方法；最后，通過組合各路徑中各節(jié)點的預(yù)測結(jié)果得到整體預(yù)測結(jié)果，設(shè)計路徑打分策略，根據(jù)閾值和層次約束，選擇最優(yōu)路徑作為最終預(yù)測標簽集合。

圖1 泛娛樂文本情報類別標簽層次結(jié)構(gòu)

1.1 層次結(jié)構(gòu)構(gòu)建

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

圖2 標簽體系

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

本文將有向無環(huán)圖結(jié)構(gòu)轉(zhuǎn)化為樹形結(jié)構(gòu)進行層次多標簽文本分類。初始時設(shè)置DAG結(jié)構(gòu)中所有節(jié)點的Visited屬性為False,對DAG結(jié)構(gòu)進行廣度優(yōu)先遍歷，如果遍歷到的節(jié)點Visited屬性為True,則復(fù)制該節(jié)點及其子節(jié)點，并且子節(jié)點的Visited屬性設(shè)置為False，更新該節(jié)點的父節(jié)點的指針，指向新增節(jié)點；如果遍歷到的節(jié)點Visited屬性為False，則將該節(jié)點的Visited屬性設(shè)置為True。

如圖3所示，將DAG結(jié)構(gòu)轉(zhuǎn)換成Tree結(jié)構(gòu)。節(jié)點D第二次遍歷時，Visited屬性已經(jīng)設(shè)置為True，因此復(fù)制D節(jié)點，生成節(jié)點D2，并更改父節(jié)點的指針，指向節(jié)點D2，轉(zhuǎn)化后如圖3中的TREE。

圖3 DAG結(jié)構(gòu)轉(zhuǎn)TREE結(jié)構(gòu)

1.2 局部分類器訓(xùn)練

SVM在解決問題時將結(jié)構(gòu)風險以及經(jīng)驗風險最小化作為考察因素，所以具有穩(wěn)定性。SVM采用鉸鏈損失函數(shù)作為代價函數(shù)，由于支持向量唯一決定了決策邊界，其取值特點導(dǎo)致支持向量機具有稀疏性?？紤]到支持向量機穩(wěn)定性、稀疏性的優(yōu)點，以及本文研究內(nèi)容使用的數(shù)據(jù)集特點，采用支持向量機作為基分類器。

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

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

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

1.3 最優(yōu)路徑選擇

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

(1)

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

(2)

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

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

圖5 路徑得分計算示意圖

2 實驗與結(jié)果分析

2.1 實驗描述

本文使用的語料來源于互聯(lián)網(wǎng)中抓取的泛娛樂領(lǐng)域的“文化娛樂”公開資訊數(shù)據(jù)，數(shù)據(jù)標簽由領(lǐng)域?qū)＜疫M行標注，該數(shù)據(jù)已經(jīng)過多個領(lǐng)域?qū)＜覍徍?，?3 852條。表1給出了各級別標簽更詳細的統(tǒng)計數(shù)據(jù)。

表1 數(shù)據(jù)統(tǒng)計表

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

表2 統(tǒng)計信息表

2.2 性能評估

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

表3 實驗結(jié)果對比表

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

(3)

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

圖6 實驗結(jié)果對比

3 結(jié) 語

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