基于改進Tri-training算法的中文問句分類

王 雷，楊思春（安徽工業(yè)大學計算機科學與技術(shù)學院，安徽馬鞍山243032）

基于改進Tri-training算法的中文問句分類

王 雷，楊思春
（安徽工業(yè)大學計算機科學與技術(shù)學院，安徽馬鞍山243032）

原始Tri-training算法對有標記的數(shù)據(jù)集通過隨機采樣方法，形成3個訓練集去訓練3個分類器。但是由這種隨機采樣形成的訓練集中，可能出現(xiàn)有標記數(shù)據(jù)集中的不同類別數(shù)據(jù)數(shù)量相差較大，從而導致訓練集中樣本類別不平衡問題，影響分類器的分類正確率。本文通過分類采樣對Tri-training算法的隨機采樣方法進行改進，根據(jù)該改進的Tri-training算法，建立分類模型，并利用其對哈工大中文問句集和本文擴展問句集進行分類實驗。結(jié)果表明，本文算法有良好的適應性，且分類正確率明顯提高；適當增大訓練集和未標記樣本數(shù)據(jù)可以增強分類器的泛化能力，從而使分類正確率提高。

Tri-training算法；隨機采樣；問句分類

問句分類作為問答系統(tǒng)中重要的組成部分，直接影響問答系統(tǒng)的性能。目前，問句分類的方法主要有兩大類［1-2］：基于人工規(guī)則的方法；基于機器學習的方法。機器學習方法包括監(jiān)督學習、無監(jiān)督學習和半監(jiān)督學習。目前基于監(jiān)督學習的問句分類方法占據(jù)主流。在英文問句分類研究方面，Li等［3］采用語義詞典WordNet問題分類取得了良好的效果；Le等［4］提出基于細粒度的POS標注特征提取算法提高了問句的分類正確率。在中文問句分類研究方面，牛彥清等［5］對中文問句分類的特征進行了研究，Liu等［6］提出一種結(jié)合句法依存關(guān)系和詞性問題性質(zhì)的核函數(shù)方法，在中文問句分類中取得了良好的效果。

監(jiān)督學習的方法主要利用已標記樣本，忽略未標記樣本對于問句分類的意義，分類正確率難以提升，且分類靈活性較低。半監(jiān)督學習是一種綜合利用已標記樣本和未標記樣本進行學習的方法，能獲得較好的學習泛化能力和學習效果。目前該類方法開始應用于中文問句分類中，如Yu等［7］利用半監(jiān)督學習中的Co-training算法將中文問句進行分類，趙全［8］利用Co-training算法將云南旅游領(lǐng)域的中文問句進行分類。在半監(jiān)督學習的諸多分類算法中Tri-training算法［9］在自然語言處理領(lǐng)域有良好的分類效果。其中，張雁等［10］對基于Tri-training的半監(jiān)督分類算法進行了研究；高嘉偉等［11］提出一種基于Tri-training的半監(jiān)督多標記學習文檔分類算法，在文檔分類中取得了良好的效果。因此本文將Tri-training算法應用于中文問句分類。

原始Tri-training算法從有標記樣本集中通過隨機采樣形成3個訓練集。這種方法形成的訓練集中可能不會涵蓋有標記樣本集中的所有類別，導致訓練集中有標記樣本數(shù)量不平衡。針對此問題，本文通過對Tri-training算法［12］的理論分析，和受于重重等［13］提出的DSCC（semi-supervised collaboration classification algorithm with enhanced difference）算法啟發(fā)，提出一種基于類別分類采樣的Tri-training算法。

1　Tri-training分類算法的改進

1.1算法描述

改進Tri-training算法初始采樣形成3個有標記的樣本集，先提取出每一類，再從提取出的每類樣本中隨機采樣，其基本流程如圖1所示。

圖1　改進的Tri-training算法流程Fig.1 Flow chart of improved Tri-training algorithm

該算法中基于標記類別的隨機采樣方法首先統(tǒng)計出標記樣本集中類別的數(shù)量，記為H。再分別統(tǒng)計出每一類中標記樣本的數(shù)量。然后利用可重復隨機采樣函數(shù)Bootstrap分別從每個類別中隨機采樣標記樣本，從而形成3個有標記的樣本集。改進Tri-training算法的詳細步驟如下。

輸入：有標記樣本集L，未標記樣本集U，測試集T，分類器H。輸出：測試集T通過分類模型分類之后的分類精度。

1）根據(jù)L訓練分類器

2）基于類別分類采樣方法將L分為3份，形成3個有標記樣本集

3）用Li（i=1，2，3）分別去訓練3個分類器Hi（i=1，2，3），即Hi（i=1，2，3）←Learn（Li）。

4）設(shè)定分類器初始分類錯誤率ei←0.5。

5）對未標記樣本集進行預測分類。對于一個分類器而言，如果另外兩個分類器對未標記樣本預測分類。結(jié)果一致，即將此樣本加入到該分類器的有標記樣本集中，并且對該分類器進行迭代訓練。

6）重復3）～5）步驟，直至分類錯誤率ei不再發(fā)生變化。即分類器迭代訓練結(jié)束。

7）用迭代訓練好的分類器將測試集中樣本分類，測算分類器的分類正確率。

8）算法結(jié)束。

1.2算法分析

在原始Tri-training算法的模型更新過程中，對于樣本Lt采用隨機采樣的方法，可能會因為樣本選取不當而使模型在第t輪更新后，并不如t-1輪的模型。并且在初始形成3個有標記樣本集的時候，很可能不會涵蓋有標記樣本集中的所有類別，或者有的樣本類別包含的多，有的類別包含的少，導致訓練集中有標記樣本數(shù)量不平衡，從而影響分類器的分類準確率。

基于標記類別的分類采樣方法采樣時，先將有標記的樣本集中的每個類別樣本提取出來，再分別從提取出來的每個類別樣本中通過隨機采樣，最終形成3個有標記的樣本集。這樣就可以保證這3個樣本集中的標記樣本會涵蓋標記樣本的所有類別，不會出現(xiàn)有標記樣本數(shù)量不平衡的情況，進一步增強分類器的泛化能力，避免多個分類器的協(xié)同訓練退化為單分類器的自訓練而失去半監(jiān)督學習和協(xié)同訓練的價值和意義的可能，提高分類器的分類正確率。

2　基于改進Tri-training算法的中文問句分類

基于改進Tri-training算法建立半監(jiān)督分類模型。模型主要包括原始數(shù)據(jù)導入、數(shù)據(jù)預處理、協(xié)同訓練和分類結(jié)果輸出4個部分。其流程如圖2。

圖2　半監(jiān)督協(xié)同分類模型工作流程Fig.2 Flow chart of semi-supervised collaboration classification model

2.1數(shù)據(jù)預處理

一般來說，中文問句集均不是分類算法中所用分類器所需的數(shù)據(jù)格式。對于中文來說，中文問句包含詞袋、詞性、命名實體和依存關(guān)系等基本特征。數(shù)據(jù)預處理部分主要是將中文問句中的基本特征提取出來，并選擇合適的基本特征將中文問句中所包含的屬性進行量化，形成分類器所需數(shù)據(jù)格式。本文利用程序?qū)崿F(xiàn)數(shù)據(jù)預處理，在建立的中文問句分類模型中，選用中文問句的詞袋這一基本特征，旨在驗證改進Tri-training算法對于中文問句分類的有效性。對于中文問句中不同的基本特征組合，不再一一驗證。

2.2協(xié)同訓練

協(xié)同訓練部分利用數(shù)據(jù)預處理得到的中文問句集，對分類器進行訓練、測試的過程。文中在基于類別分類采樣的Tri-training算法基礎(chǔ)上，運用3個分類器協(xié)同訓練。

基于類別分類采樣方法將有標記樣本集中的每一類中文問句提取出來，然后分別對提取出來的每類問句進行隨機采樣，形成3個有標記的樣本集。用形成的3個有標記樣本集分別去訓練3個分類器，再利用訓練得到的3個分類器協(xié)同對未標記樣本集中的樣本進行標記。對于一個分類器而言，如果另外兩個分類器對這些未標記樣本標記了相同的分類結(jié)果，這些樣本則被當成是已標記樣本加入到該分類器的有標記樣本集中參加對該分類器進行迭代訓練。對每個分類器而言，均如此的進行迭代訓練，直至分類器不再更新，則迭代訓練結(jié)束。

3　實驗結(jié)果及分析

3.1實驗數(shù)據(jù)

所用實驗數(shù)據(jù)主體來自哈爾濱工業(yè)大學的中文問句集。該問句集分為6大類，共包含6 266個已標記好問句類別的問句。在該問句集的基礎(chǔ)上，本文又利用網(wǎng)絡(luò)資源人工將每類問句數(shù)量進行擴展，擴展的總問句數(shù)為4 000個。將擴展的中文問句加入到哈爾濱工業(yè)大學的中文問句集中，形成新的中文問句集。

3.2實驗設(shè)置

1）樣本集分配

針對哈爾濱工業(yè)大學的中文問句集，選用25%的數(shù)據(jù)作為測試樣本集，剩余75%的數(shù)據(jù)作為訓練集，其中，訓練樣本集中未標記樣本的比例依次選用20%，40%，60%，80%。將本文擴展的問句集加入至哈爾濱工業(yè)大學的中文問句集中，形成一個新的問句集，再將此問句集按照哈工大中文問句集的樣本分配比例進行實驗數(shù)據(jù)分配。

2）分類器選擇

本實驗選用了3個SVM分類器，旨在驗證基于問句類別分類采樣方法對問句分類的影響。對于其他不同分類器的組合用法對分類實驗的效果影響，李心磊等［14］已經(jīng)通過實驗驗證。

3）評價指標

對分類結(jié)果進行測試時，采用分類正確率（A）作為評價標準，其定義如下

3.3問句分類實驗及結(jié)果分析

1）哈爾濱工業(yè)大學的中文問句集實驗

采用圖2分類模型，利用哈爾濱工業(yè)大學的中文問句集進行實驗。分別得出單個SVM分類器的自訓練、原始的Tri-training算法以及改進的Tri-training算法在此問句集上的分類正確率。表1給出了在4種不同的未標記比率下，上述3種方法的分類正確率。其中：T1為單個SVM分類器的自訓練方法；T2為原始Tritraining算法；T3為改進Tri-training算法。

2）擴展的新問句集實驗

表2為在擴展問句集上，分別采用單個SVM分類器自訓練、原始Tri-training算法以及改進Tri-training算法在4種不同未標記比率下的分類正確率。

表1　不同未標記比率下各種分類方法在哈爾濱工業(yè)大學問句集上的分類正確率（%）Tab.1 Classification accuracy of various classification methods with different unlabeled ratios on HIT question set（%）

表2　不同未標記比率下各種分類方法在擴展問句集上的分類正確率（%）Tab.2 Classification accuracy of various classification methods with different unlabeled ratios on expanded set（%）

從表1中的試驗結(jié)果可以看出：在原問句集上，改進Tri-training算法和原始Tri-training算法的分類正確率均高于單SVM分類器自訓練方法的分類正確率，分別高出4.16%和2.78%；且改進Tri-training算法的分類正確率更高于原始Tri-training算法的分類正確率，高出其1.38%。表2表明，在擴展問句集的基礎(chǔ)上，改進Tri-training算法的分類正確率高出原始Tri-training算法的分類正確率1.70%。比較表1，2中的實驗數(shù)據(jù)可以看出，適當增大訓練集和未標記樣本數(shù)據(jù)可以提高分類器的泛化能力，從而使分類正確率提高。

綜上所述，本文提出的基于類別分類抽樣的Tri-training算法相對于原始Tri-training算法和單個SVM分類器自訓練的分類方法而言，在處理中文問句分類問題上，性能提高，說明本文算法在中文問句分類問題上的適用性。

4　結(jié)　語

本文的主要工作是根據(jù)在前期研究過程中提出的基于類別分類采樣的Tri-training算法，建立了半監(jiān)督協(xié)同分類模型，并利用哈爾濱工業(yè)大學的中文問句集以及人工擴展的問句集進行分類實驗。實驗結(jié)果表明，基于類別分類采樣的Tri-training算法較原始Tri-training算法分類正確率，分別提高2.78%和1.70%。

本文算法的分類實驗主要是在哈爾濱工業(yè)大學的中文問句集基礎(chǔ)上展開的，對于更大規(guī)模的中文問句集而言，算法是否有效，還有待驗證。希望本文的算法能夠為其他分類領(lǐng)域的研究者提供參考。

［1］鄭實福，劉挺，秦兵，等.中文自動問答系統(tǒng)綜述［J］.中文信息學報，2002，6（16）：46-52.

［2］鎮(zhèn)麗華，王小林，楊思春.自動問答系統(tǒng)中問句分類研究綜述［J］.安徽工業(yè)大學學報（自然科學版），2015，32（1）：48-66.

［3］LI X，ROTH D.Learning question classifiers：the role of semantic information［J］.Natural Language Engineering，2006，12（3）：229-249.

［4］LE J，NIU Z D，ZHANG C X.Question classification based on fine-grained pos annotation of nouns and interrogative pronouns［J］. Lecture Notes in Computer Science，2014，8862：680-693.

［5］牛彥清，陳俊杰，段利國，等.中文問句分類特征的研究［J］.計算機應用與軟件，2012，29（3）：108-111.

［6］LIU L，YU Z T，GUO J Y，et al.Chinese question classification based on question property kernel［J］.International Journal of Machine Learning and Cybernetics，2013，5（5）：713-720.

［7］YU Z T，SU L，LI L N，et al.Question classification based on co-training style semi-supervised learning［J］.Pattern Recognition Letters，2010，31（13）：1975-1980.

［8］趙全.基于半監(jiān)督學習的中文問句分類研究［D］.昆明：昆明理工大學，2010.

［9］ZHOU Z H，LI M.Tri-training：exploiting unlabeled data using three classifiers［J］.IEEE Trans on Knowledge and Data Engineer，2005，17（11）：1529-1541.

［10］張雁，呂丹桔，吳保國.基于Tri-training半監(jiān)督分類算法的研究［J］.計算機技術(shù)與發(fā)展，2013，23（7）：77-80.

［11］高嘉偉，梁吉業(yè)，劉楊磊，等.一種基于Tri-training的半監(jiān)督多標記學習文檔分類算法［J］.中文信息學報，2015，29（1）：104-10.

［12］周志華，王玨.機器學習及其應用［M］.北京：清華大學出版社，2007.

［13］于重重，商利利，譚勵，等.半監(jiān)督學習在不平衡樣本集分類中的應用研究［J］.計算機應用研究，2013，30（4）：1085-1089.

［14］李心磊，楊思春，彭月娥.Tri-training算法中分類器組合的改進［J］.蘇州科技學院學報（自然科學版），2014，31（2）：52-56.

責任編輯：丁吉海

Chinese Question Classification Based on Improved Tri-trainingAlgorithm

WANG Lei，YANG Sichun
（School of Computer Science and Technology，Anhui University of Technology，Ma'anshan 243032，China）

The originalTri-training algorithm classifies the labeled data by the method of random sampling，forming three training sets for three classifiers.There is an phenomenon that the number of different categories may have huge differences between the exiting labeled data sets in this training sets formed by random sampling three classifiers，which may lead the categories of training sets into imbalance，and influence the accuracy of classifier. By employing a method of classification sampling to replace the random sampling，Tri-training algorithm wasimprovedandaclassificationmodelwasestablished.ClassificationexperimentwereperformedonHITquestion set and expanded question set.The results were compared with those of original Tri-training algorithm on the same data sets，which indicates that the new algorithm has good adaptability，and the accuracy of the algorithm is improved.With the increase of training set and the number of unlabeled samples，the generalization ability and the accuracy of the classifier are improved.

Tri-training algorithm；random sampling；question classification

TP391

Adoi：10.3969/j.issn.1671-7872.2016.02.015

1671-7872（2016）02-0172-05

2015-07-08

安徽省高校自然科學研究重點項目（KJ2011A048，KJ2016A098）

王雷（1990-），男，安徽定遠人，碩士生，主要研究方向為自然語言處理。

楊思春（1970-），男，安徽六安人，博士，教授，主要研究方向為自然語言處理、信息檢索、粗糙集和概念格。