一種非完全標注的文本分類訓練方法*

段軍紅，李曉宇，慕德俊

（西北工業大學深圳研究院, 深圳518057）

1 引 言

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

總之，由于樣本數據類別標示不完備，每個樣本僅標識了實際所屬分類中的一個，導致機器學習訓練出的分類器性能低下，這就是“非完全標注”帶來的問題。針對此問題，將原來的分類體系拆分成多個分類體系，使每個分類體系下的類別是互斥的，再在每個拆分出的分類體系下，對數據進行訓練，可提高分類器的精度[3]。而多個分類器并聯，分別輸出樣本對應的類別，即可得到樣本實際所屬的所有類別。

2 基于遺傳算法的最優分組

2.1 最優類別分組

將原始分類拆分為多個分類體系的最優組合，是指將原始分類拆分成相互獨立的多個分類體系的組合，使得在每個分類體系中，該體系內包含類別的訓練樣本通過指定的分類器誤分數量之和最小[4]。

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

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

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

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

在分類問題中，希望對于整個訓練集而言，錯分類的樣本數量占所有樣本數量的比例盡可能小。在分組后，設置實際優化目標如下：

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

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

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

而優化目標，則是找到一個最優的劃分，使得誤分率達到最小[9-10]。

圖1 分組優化目標

2.2 遺傳算法

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

以50 個類別分為3 組為例，有：

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

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

圖2 遺傳算法

在最優分組問題中，設遺傳算法相關要素如下：

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

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

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

(4) 種群數量：10000 條；

(5) 交叉概率：0.35；

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

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

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

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

(10) 分組數量：3 組。

經過遺傳算法計算，在第100 代時，適應度達到了0.9343。

按照計算出的分組，對各個分組進行了GBM 分類訓練，組內訓練結果如表1 所示。

表1 組內分類效果

可以看出，在各個分組內，分類器的分類效果都明顯優于未分組前。即組內的類別對于該分類算法而言，具備較好的可區分性，類別獨立性較強，重疊性較低。由此可確定，該分組方式可以達到將原始分類拆分成相互獨立的多個分類體系組合的作用。將通過三組數據分別訓練出的分類器對所有數據進行標注，且若認為任一個分類器給出的標簽符合原始標簽即認為分類正確，則得到的分類正確率即為1－0.2174＝78.26%，準確度有明顯的提升[13]。

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

圖3 分類實例

3 分組數量確定

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

隨著分組數量的增加，最優分組對應的適應度逐漸增加，但增加趨勢逐漸變緩。最優分組需要指定分組數量K，可以通過計算不同分組數量下的適應度，從而得到適當的分組數量。

通過分析可以發現，按照上述方法獲得的最優適應度，與二項分布規律高度吻合：在最優K 分組上的適應度，近似等于分類算法在K 次分類實驗中至少成功一次的概率。從數據上看，兩者非常吻合。

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

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

(3) 以最大化正確率為優化目標，采用優化算法（如遺傳算法等）計算最優分組方案；

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

(5) 并聯分類器，對每一個待分類樣本進行分類，得到的分類結果均作為該樣本的類別標簽。

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

表2 分組數量的經驗分布與實際分布

按照上述規律，就可以直接估計達到指定的適應度閾值所需的分組數量，即：

適應度越高，意味著分類器在分組后的訓練集上表現越好，同時在驗證集上也能表現出較好的性能，例如在對CNPC 語料庫進行最優5-劃分后，分類器在驗證集上的精度提升至88.61%，較3-劃分上的精度78.26%又有較大提升。

4 結束語

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