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

基于改進(jìn)Tri-training算法的中文問句分類

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

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

Tri-training算法；隨機(jī)采樣；問句分類

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

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

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

1　Tri-training分類算法的改進(jìn)

1.1算法描述

改進(jìn)Tri-training算法初始采樣形成3個(gè)有標(biāo)記的樣本集，先提取出每一類，再?gòu)奶崛〕龅拿款悩颖局须S機(jī)采樣，其基本流程如圖1所示。

圖1　改進(jìn)的Tri-training算法流程Fig.1 Flow chart of improved Tri-training algorithm

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

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

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

2）基于類別分類采樣方法將L分為3份，形成3個(gè)有標(biāo)記樣本集

3）用Li（i=1，2，3）分別去訓(xùn)練3個(gè)分類器Hi（i=1，2，3），即Hi（i=1，2，3）←Learn（Li）。

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

5）對(duì)未標(biāo)記樣本集進(jìn)行預(yù)測(cè)分類。對(duì)于一個(gè)分類器而言，如果另外兩個(gè)分類器對(duì)未標(biāo)記樣本預(yù)測(cè)分類。結(jié)果一致，即將此樣本加入到該分類器的有標(biāo)記樣本集中，并且對(duì)該分類器進(jìn)行迭代訓(xùn)練。

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

7）用迭代訓(xùn)練好的分類器將測(cè)試集中樣本分類，測(cè)算分類器的分類正確率。

8）算法結(jié)束。

1.2算法分析

在原始Tri-training算法的模型更新過程中，對(duì)于樣本Lt采用隨機(jī)采樣的方法，可能會(huì)因?yàn)闃颖具x取不當(dāng)而使模型在第t輪更新后，并不如t-1輪的模型。并且在初始形成3個(gè)有標(biāo)記樣本集的時(shí)候，很可能不會(huì)涵蓋有標(biāo)記樣本集中的所有類別，或者有的樣本類別包含的多，有的類別包含的少，導(dǎo)致訓(xùn)練集中有標(biāo)記樣本數(shù)量不平衡，從而影響分類器的分類準(zhǔn)確率。

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

2　基于改進(jìn)Tri-training算法的中文問句分類

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

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

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

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

2.2協(xié)同訓(xùn)練

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

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

3　實(shí)驗(yàn)結(jié)果及分析

3.1實(shí)驗(yàn)數(shù)據(jù)

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

3.2實(shí)驗(yàn)設(shè)置

1）樣本集分配

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

2）分類器選擇

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

3）評(píng)價(jià)指標(biāo)

對(duì)分類結(jié)果進(jìn)行測(cè)試時(shí)，采用分類正確率（A）作為評(píng)價(jià)標(biāo)準(zhǔn)，其定義如下

3.3問句分類實(shí)驗(yàn)及結(jié)果分析

1）哈爾濱工業(yè)大學(xué)的中文問句集實(shí)驗(yàn)

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

2）擴(kuò)展的新問句集實(shí)驗(yàn)

表2為在擴(kuò)展問句集上，分別采用單個(gè)SVM分類器自訓(xùn)練、原始Tri-training算法以及改進(jìn)Tri-training算法在4種不同未標(biāo)記比率下的分類正確率。

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

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

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

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

4　結(jié)　語(yǔ)

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

本文算法的分類實(shí)驗(yàn)主要是在哈爾濱工業(yè)大學(xué)的中文問句集基礎(chǔ)上展開的，對(duì)于更大規(guī)模的中文問句集而言，算法是否有效，還有待驗(yàn)證。希望本文的算法能夠?yàn)槠渌诸愵I(lǐng)域的研究者提供參考。

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

［2］鎮(zhèn)麗華，王小林，楊思春.自動(dòng)問答系統(tǒng)中問句分類研究綜述［J］.安徽工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），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］牛彥清，陳俊杰，段利國(guó)，等.中文問句分類特征的研究［J］.計(jì)算機(jī)應(yīng)用與軟件，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)督學(xué)習(xí)的中文問句分類研究［D］.昆明：昆明理工大學(xué)，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］張雁，呂丹桔，吳保國(guó).基于Tri-training半監(jiān)督分類算法的研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（7）：77-80.

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

［12］周志華，王玨.機(jī)器學(xué)習(xí)及其應(yīng)用［M］.北京：清華大學(xué)出版社，2007.

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

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

責(zé)任編輯：丁吉海

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

安徽省高校自然科學(xué)研究重點(diǎn)項(xiàng)目（KJ2011A048，KJ2016A098）

王雷（1990-），男，安徽定遠(yuǎn)人，碩士生，主要研究方向?yàn)樽匀徽Z(yǔ)言處理。

楊思春（1970-），男，安徽六安人，博士，教授，主要研究方向?yàn)樽匀徽Z(yǔ)言處理、信息檢索、粗糙集和概念格。