面向泛娛樂文本的層次多標(biāo)簽分類方法

陳若愚 劉秀磊 于汝意

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

0 引 言

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

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

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

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

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

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

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

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

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

圖2 標(biāo)簽體系

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

圖5 路徑得分計(jì)算示意圖

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

2.1 實(shí)驗(yàn)描述

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

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

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

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

2.2 性能評估

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

表3 實(shí)驗(yàn)結(jié)果對比表

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

(3)

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

圖6 實(shí)驗(yàn)結(jié)果對比

3 結(jié) 語

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