一種非完全標(biāo)注的文本分類訓(xùn)練方法*

段軍紅，李曉宇，慕德俊

（西北工業(yè)大學(xué)深圳研究院, 深圳518057）

1 引 言

對于完全標(biāo)注的文本，通過深度學(xué)習(xí)、分布式隨機(jī)森林、梯度提升決策樹等分類方法在標(biāo)準(zhǔn)測試集上能實(shí)現(xiàn)較高精度的文本分類[1]。但在當(dāng)前的分類體系下，對于非完全標(biāo)注的文本分類器，無法有效識別出某類別與其它類別的邊界，甚至這些類別本身就是與其它類別重合的。在標(biāo)準(zhǔn)測試集上性能良好的分類算法，往往在實(shí)際數(shù)據(jù)分類中性能表現(xiàn)不佳。分類器性能低下的原因在于樣本分類體系不滿足互斥原則[2]。例如，類別名稱中既包括“中石油”、“中石化”等以關(guān)注對象為分類基準(zhǔn)的類別，又包括“國內(nèi)新聞”、“國外新聞”等以事件地點(diǎn)為基準(zhǔn)的類別，以及各種其它欄目劃分方法，分類標(biāo)準(zhǔn)非常不統(tǒng)一。在不統(tǒng)一的分類標(biāo)準(zhǔn)下，一篇文檔完全可能既屬于“中石油”，又屬于“國內(nèi)新聞”，但在信息采編中，出于避免重復(fù)的原因，編輯最終要將文章僅劃歸在一個(gè)欄目下。這種由于分類邏輯上的不統(tǒng)一以及文章內(nèi)容本質(zhì)上的多樣性，最終將導(dǎo)致分類器無法得到與訓(xùn)練數(shù)據(jù)一致的分類。

總之，由于樣本數(shù)據(jù)類別標(biāo)示不完備，每個(gè)樣本僅標(biāo)識了實(shí)際所屬分類中的一個(gè)，導(dǎo)致機(jī)器學(xué)習(xí)訓(xùn)練出的分類器性能低下，這就是“非完全標(biāo)注”帶來的問題。針對此問題，將原來的分類體系拆分成多個(gè)分類體系，使每個(gè)分類體系下的類別是互斥的，再在每個(gè)拆分出的分類體系下，對數(shù)據(jù)進(jìn)行訓(xùn)練，可提高分類器的精度[3]。而多個(gè)分類器并聯(lián)，分別輸出樣本對應(yīng)的類別，即可得到樣本實(shí)際所屬的所有類別。

2 基于遺傳算法的最優(yōu)分組

2.1 最優(yōu)類別分組

將原始分類拆分為多個(gè)分類體系的最優(yōu)組合，是指將原始分類拆分成相互獨(dú)立的多個(gè)分類體系的組合，使得在每個(gè)分類體系中，該體系內(nèi)包含類別的訓(xùn)練樣本通過指定的分類器誤分?jǐn)?shù)量之和最小[4]。

按照一般監(jiān)督學(xué)習(xí)的定義[5-6]，給定包含N 個(gè)訓(xùn)練樣本的訓(xùn)練集{(x1,y1),(x2,y2),…,(xN,yN)}，其中xi是第i 個(gè)樣本的特征向量，yi是第i 個(gè)樣本的類別序號，yi∈{1,2,…,M}，分類學(xué)習(xí)算法就是在假設(shè)空間（Hypothesis Space）中尋找一個(gè)函數(shù)g：X→Y，其中X 是輸入空間，Y 是輸出空間，使得對于一個(gè)指定的評分函數(shù)（Scoring Function）f：X×Y→R，函數(shù)g 可以返回使得評分函數(shù)取值最大的y，即gg(xx）=。

為了表征函數(shù)與訓(xùn)練集的擬合程度，一般均會定義一個(gè)損失函數(shù)（Loss Function）L：X×Y→R≥0，以及一個(gè)風(fēng)險(xiǎn)函數(shù)（Risk Function），定義為損失函數(shù)的期望值，該期望值可通過訓(xùn)練樣本進(jìn)行估計(jì)，即。此外，為了防止過擬合，在訓(xùn)練時(shí)還會引入正則化懲罰因子（Regularization Penalty）先驗(yàn)分布C(g)，常見的選擇包括L1范數(shù)、L2范數(shù)等。因此，分類學(xué)習(xí)算法即是在假設(shè)空間中尋找一個(gè)函數(shù)g 使得結(jié)構(gòu)化風(fēng)險(xiǎn)J(g)=Remp(g)＋λC(g)最小。

而在“非完全標(biāo)注”問題中，則是要尋找一個(gè)輸出空間（分類標(biāo)簽）的K 劃分，使得對任意的α≠β均有，且通過給定的監(jiān)督學(xué)習(xí)算法生成K 個(gè)映射gi：X→Yi,i=1,2,…,k，使得J(gi)最小。

機(jī)器學(xué)習(xí)訓(xùn)練過程時(shí)間復(fù)雜度一般較高。若在優(yōu)化的每一個(gè)迭代過程中均需要對訓(xùn)練后的結(jié)構(gòu)化風(fēng)險(xiǎn)J(gi)進(jìn)行計(jì)算，則計(jì)算事件復(fù)雜度往往會增大到不可接受的程度。對于分類訓(xùn)練后得到的融合矩陣，由于其表征了經(jīng)過特定的監(jiān)督學(xué)習(xí)算法后的樣本標(biāo)注類別與訓(xùn)練出的分類器預(yù)測的類別之間的差異，因此，可直接采用訓(xùn)練數(shù)據(jù)的融合矩陣作為最優(yōu)化分組的依據(jù)[7-8]。

在分類問題中，希望對于整個(gè)訓(xùn)練集而言，錯(cuò)分類的樣本數(shù)量占所有樣本數(shù)量的比例盡可能小。在分組后，設(shè)置實(shí)際優(yōu)化目標(biāo)如下：

設(shè)融合矩陣SN×N=[si,j]，矩陣中元素si,j為標(biāo)注為第yi類但經(jīng)過給定分類算法預(yù)測為第yj類的訓(xùn)練樣本數(shù)量。那么，最優(yōu)分組是尋找一個(gè)類別集合Y 的K劃分且YYαα∩IYYββ==Φ?，可使得誤分率ER=最小化。

例如，圖1 為A、B、C、D、E 五個(gè)類別的融合矩陣，顯然，僅有對角線上的元素S1,1,S2,2,…,S5,5為正確分類的樣本數(shù)量，其它元素均為誤分類，那么，整個(gè)樣本集在該分類器下的誤分率即為：

若將所有類別做一個(gè)2-劃分，例如，{A,C}劃分為一組，{B,D,E}劃分為一組，那么，在{A,C}組內(nèi)，s1,1+s3,3仍為正確劃分的樣本數(shù)量，而錯(cuò)誤劃分的樣本數(shù)量為s1,3+s3,1。同樣，在{B,D,E}組內(nèi)，s2,2+s4,4+s5,5為正確劃分的樣本數(shù)量，s2,4+s2,5+s4,2+s4,4+s5,2+s5,4則是錯(cuò)誤劃分的樣本數(shù)量。故此，在這種劃分下，樣本的誤分率為：

而優(yōu)化目標(biāo)，則是找到一個(gè)最優(yōu)的劃分，使得誤分率達(dá)到最小[9-10]。

圖1 分組優(yōu)化目標(biāo)

2.2 遺傳算法

在明確最優(yōu)化目標(biāo)后，要設(shè)法對這一優(yōu)化過程進(jìn)行計(jì)算。首先，需要評估的是解空間的大小。在確定分組數(shù)量K 的前提下，將N 個(gè)元素分為K 組，每組至少包括一個(gè)元素，其組合數(shù)量為第二類Stirling數(shù)S（N,K），其遞推計(jì)算公式為：

以50 個(gè)類別分為3 組為例，有：

S(50,3) =4,081,990,278,659,592,354

顯然，對此不可能通過窮舉遍歷的方式進(jìn)行，需要采用一種優(yōu)化算法[11-12]。遺傳算法是一類借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象發(fā)展出來的最優(yōu)化方法，是進(jìn)化算法的一種。在遺傳算法中，優(yōu)化問題的解被稱為個(gè)體，表示為變量序列，一般稱其為染色體（Chrome）。染色體一般表達(dá)為簡單的字符串或數(shù)字串，這一過程稱為編碼。算法在起始時(shí)隨機(jī)生成一定數(shù)量的個(gè)體，在每一代中，每一個(gè)個(gè)體都被評價(jià)，并通過計(jì)算適應(yīng)度函數(shù)得到一個(gè)適應(yīng)度數(shù)值。隨后，按照一定的選擇策略（一般而言適應(yīng)度越高被選中的概率越高），選擇一定量的個(gè)體進(jìn)入繁殖階段。在繁殖階段中一般包括交叉（Crossover）與變異（Mutation）兩個(gè)算子。交叉是指在一定的交叉概率下（一般范圍是0.6~1），兩個(gè)被選中的個(gè)體的染色體在交配點(diǎn)互換，生成兩個(gè)新的染色體以代替原有個(gè)體；而變異則是指按照一定的變異概率（通常小于0.1）在隨機(jī)位置改變原有染色體。通過多次迭代，新產(chǎn)生的個(gè)體一代代向增加適應(yīng)度的方向發(fā)展，直至得到滿足條件的解。算法過程如圖2 所示。

圖2 遺傳算法

在最優(yōu)分組問題中，設(shè)遺傳算法相關(guān)要素如下：

(1) 融合矩陣：采用GBM 算法訓(xùn)練生成的融合矩陣；

(2) 編碼方式：采用整數(shù)編碼，染色體長度為類別數(shù)量N，染色體上每條基因的取值范圍為{1,2,…,K}，其中K 為分組數(shù)量，染色體上取同一個(gè)值的類別代表分在同一組內(nèi)，這樣一條染色體就代表一個(gè)可行解，并且所有的可行解均可用染色體來表示，任意染色體經(jīng)過交叉和變異算子處理后，生成的子代仍為可行解；

(3) 適應(yīng)度函數(shù)：由于遺傳算法是選擇適應(yīng)度高的個(gè)體，因此不直接采用誤分率ER 作為適應(yīng)度，而是采用正確率P=1-ER 作為適應(yīng)度；

(4) 種群數(shù)量：10000 條；

(5) 交叉概率：0.35；

(6) 變異概率：1/12；

(7) 最大迭代次數(shù)：100 次；

(8) 樣本數(shù)量：184415 個(gè)（刪除了樣本個(gè)數(shù)過少的類別）；

(9) 類別數(shù)量：101 個(gè)（刪除了樣本個(gè)數(shù)過少的類別）；

(10) 分組數(shù)量：3 組。

經(jīng)過遺傳算法計(jì)算，在第100 代時(shí)，適應(yīng)度達(dá)到了0.9343。

按照計(jì)算出的分組，對各個(gè)分組進(jìn)行了GBM 分類訓(xùn)練，組內(nèi)訓(xùn)練結(jié)果如表1 所示。

表1 組內(nèi)分類效果

可以看出，在各個(gè)分組內(nèi)，分類器的分類效果都明顯優(yōu)于未分組前。即組內(nèi)的類別對于該分類算法而言，具備較好的可區(qū)分性，類別獨(dú)立性較強(qiáng)，重疊性較低。由此可確定，該分組方式可以達(dá)到將原始分類拆分成相互獨(dú)立的多個(gè)分類體系組合的作用。將通過三組數(shù)據(jù)分別訓(xùn)練出的分類器對所有數(shù)據(jù)進(jìn)行標(biāo)注，且若認(rèn)為任一個(gè)分類器給出的標(biāo)簽符合原始標(biāo)簽即認(rèn)為分類正確，則得到的分類正確率即為1－0.2174＝78.26%，準(zhǔn)確度有明顯的提升[13]。

以圖3 所示的頁面作為一個(gè)實(shí)例，對分類器給出的標(biāo)簽進(jìn)行主觀判斷。從抽樣結(jié)果看，標(biāo)簽的合理性可以得到肯定[14-15]。例如，在原始樣本中，《勝利油田高溫分布式光纖測溫技術(shù)成功應(yīng)用》一文被劃歸在“石油科技·科技動態(tài)·物探測井”欄目下，而經(jīng)過最優(yōu)分組后，該文還被識別為“石油科技·科技動態(tài)·勘探開發(fā)”以及“工程服務(wù)·物探測井”等幾個(gè)額外類別。

圖3 分類實(shí)例

3 分組數(shù)量確定

通過指定分組數(shù)量，利用分類算法在測試集上的融合矩陣，即可借助例如遺傳算法來獲取最優(yōu)分組，解決由于樣本標(biāo)注不完全帶來的分類器性能低下的問題。

隨著分組數(shù)量的增加，最優(yōu)分組對應(yīng)的適應(yīng)度逐漸增加，但增加趨勢逐漸變緩。最優(yōu)分組需要指定分組數(shù)量K，可以通過計(jì)算不同分組數(shù)量下的適應(yīng)度，從而得到適當(dāng)?shù)姆纸M數(shù)量。

通過分析可以發(fā)現(xiàn)，按照上述方法獲得的最優(yōu)適應(yīng)度，與二項(xiàng)分布規(guī)律高度吻合：在最優(yōu)K 分組上的適應(yīng)度，近似等于分類算法在K 次分類實(shí)驗(yàn)中至少成功一次的概率。從數(shù)據(jù)上看，兩者非常吻合。

對之前提及的其它分類算法，包括深度學(xué)習(xí)、分布式隨機(jī)森林等都進(jìn)行了基于融合矩陣的最優(yōu)分組，可得到類似的結(jié)論。因此認(rèn)為，基于融合矩陣的最優(yōu)化分組，可以解決由非完全標(biāo)注帶來的分類器性能下降的問題，并得到了具備一定通用性的兩步分類框架：

(1) 利用分類算法對訓(xùn)練數(shù)據(jù)進(jìn)行訓(xùn)練，得到針對訓(xùn)練集的融合矩陣S 以及精確度p;

(3) 以最大化正確率為優(yōu)化目標(biāo)，采用優(yōu)化算法（如遺傳算法等）計(jì)算最優(yōu)分組方案；

(4) 按照最優(yōu)分組，采用與之前相同的分類算法以及算法超參數(shù)，分別訓(xùn)練各組數(shù)據(jù)的分類器；

(5) 并聯(lián)分類器，對每一個(gè)待分類樣本進(jìn)行分類，得到的分類結(jié)果均作為該樣本的類別標(biāo)簽。

表2 為根據(jù)中國石油天然氣集團(tuán)公司（China National Petroleum Corporation, CNPC）語料庫選用梯度增強(qiáng)機(jī)（Gradient boosting machine, GBM）分類算法獲得的融合矩陣，進(jìn)而通過遺傳算法得到的分組數(shù)量（第一行）與適應(yīng)度（第二行）的關(guān)系，表中第三行為依據(jù)二項(xiàng)分布X~B(K,p)計(jì)算出的K 次貝努利實(shí)驗(yàn)至少成功一次的概率prob=1- （1- p）K，其中p 為GBM 分類算法對未分組的整個(gè)數(shù)據(jù)集進(jìn)行訓(xùn)練后得到的分類器的精確度。在其它數(shù)據(jù)集上也發(fā)現(xiàn)了類似的規(guī)律。

表2 分組數(shù)量的經(jīng)驗(yàn)分布與實(shí)際分布

按照上述規(guī)律，就可以直接估計(jì)達(dá)到指定的適應(yīng)度閾值所需的分組數(shù)量，即：

適應(yīng)度越高，意味著分類器在分組后的訓(xùn)練集上表現(xiàn)越好，同時(shí)在驗(yàn)證集上也能表現(xiàn)出較好的性能，例如在對CNPC 語料庫進(jìn)行最優(yōu)5-劃分后，分類器在驗(yàn)證集上的精度提升至88.61%，較3-劃分上的精度78.26%又有較大提升。

4 結(jié)束語

在當(dāng)前分類體系下，非完全標(biāo)注的文本分類器無法有效識別出與其它類別的邊界，甚至這些類別本身就是與其它類別重合，造成實(shí)際數(shù)據(jù)中分類性能低下。針對此類問題，通過最優(yōu)類別分組和遺傳算法，嘗試建立了一種非完全標(biāo)注的文本分類訓(xùn)練方法，將原來的分類體系拆分成多個(gè)分類體系，使得每個(gè)分類體系下的類別彼此互斥，在每個(gè)拆分出的分類體系下，對數(shù)據(jù)進(jìn)行訓(xùn)練，提高分類器的精度。經(jīng)過多個(gè)分類器并聯(lián)，分別輸出樣本對應(yīng)的類別，就可以得到樣本實(shí)際所屬的所有類別。通過中國石油天然氣集團(tuán)公司語料庫選用梯度增強(qiáng)機(jī)分類算法獲得的融合矩陣，用所提方法進(jìn)行了仿真，結(jié)果表明：適應(yīng)度越高，分類器在分組后的訓(xùn)練集上表現(xiàn)越好，同時(shí)在驗(yàn)證集上也能表現(xiàn)出較好的性能，分類器在驗(yàn)證集上的精度有較大的提升，證實(shí)了該方法的有效性。