幾種文本分類算法性能比較與分析

楊娟，王未央

（上海海事大學(xué)信息工程學(xué)院，上海201306）

幾種文本分類算法性能比較與分析

楊娟，王未央

（上海海事大學(xué)信息工程學(xué)院，上海201306）

針對常用的文本分類算法，給定五種文本類型的數(shù)據(jù)集，通過使用典型的文本分類算法進(jìn)行實驗分析，通過精確率、召回率和測試值的精度來評估這些文本分類器的性能，并給出分析結(jié)果和改進(jìn)的組合訓(xùn)練方法。結(jié)果表明：將半監(jiān)督學(xué)習(xí)訓(xùn)練和監(jiān)督學(xué)習(xí)相結(jié)合能達(dá)到更好的分類效果。為了提高文本推薦速度，前期工作就是要選擇合適的分類算法方法，組合選擇算法，提高準(zhǔn)確度和效率。

文本分類；監(jiān)督學(xué)習(xí)；組合選擇；推薦

0　引言

隨著互聯(lián)網(wǎng)信息技術(shù)的發(fā)展，各種文本類型的信息海量產(chǎn)生，在面對網(wǎng)絡(luò)社交化的時代，需要對文本信息進(jìn)行分類處理，從而進(jìn)行個性化推薦給相關(guān)度高的用戶。于是，各種文本分類算法被提出。文本分類［2］就是把某文檔歸屬于哪一個類別。當(dāng)需要處理大量文本信息分類的時候，必須按照一定的模型標(biāo)準(zhǔn)，建立合適的分類器模型，把大量文本劃分為預(yù)先設(shè)定好的幾個類別中，實現(xiàn)自動文本分類。于是基于機(jī)器學(xué)習(xí)的文本挖掘技術(shù)被相應(yīng)的提出來，自動化文本分類也得以實現(xiàn)。國內(nèi)外學(xué)者研究提出來的許多分類方法，有支持向量機(jī)（SVM）算法［9］，樸素貝葉斯（NB）算法［6］，K最近鄰（KNN）算法［7］等。本文主要針對基于機(jī)器學(xué)習(xí)的幾種算法，選擇有監(jiān)督和半監(jiān)督學(xué)習(xí)訓(xùn)練方法，對已知五種類型進(jìn)行分類實驗，通過分析結(jié)果精確度和分類結(jié)果的穩(wěn)定性，提出文本推薦的時候該怎樣選擇合適的算法進(jìn)行建模。

在文獻(xiàn)［8］提到了在機(jī)器學(xué)習(xí)的過程中，先將樣本數(shù)據(jù)分成三個集合：訓(xùn)練集、驗證集、測試集。驗證集用來對模型參數(shù)進(jìn)行調(diào)整，訓(xùn)練集的目的是用來估計模型結(jié)構(gòu)，測試集是用來驗證模型的分類效果如何。訓(xùn)練集一般用在有指導(dǎo)的監(jiān)督學(xué)習(xí)中，監(jiān)督學(xué)習(xí)是指在有標(biāo)記的樣本集合中訓(xùn)練數(shù)據(jù)，建立學(xué)習(xí)模型，然后去預(yù)測大量的沒有標(biāo)記的樣本。與監(jiān)督學(xué)習(xí)相比，半監(jiān)督學(xué)習(xí)則不需要人工的操作，且在處理只有少量標(biāo)注樣本和不均勻數(shù)據(jù)集時，能夠利用大量未標(biāo)記樣本進(jìn)行學(xué)習(xí)。這更好地避免了在標(biāo)記文本時候代價大，以及主觀判斷所帶來的缺陷。本文也通過實驗，在同一數(shù)據(jù)集上對樣本進(jìn)行監(jiān)督訓(xùn)練和半監(jiān)督訓(xùn)練，又通過期望最大化算法（EM）對貝葉斯分類器（監(jiān)督學(xué)習(xí)）訓(xùn)練，對比其他算法更好地實現(xiàn)了分類效果。

先給出文本分類的一般算法流程和半監(jiān)督學(xué)習(xí)的文本分類流程圖如下：

圖1　文本分類的一般流程

圖2　基于半監(jiān)督學(xué)習(xí)的文本分類流程

1　常用文本分類方法思想

1.1類中心向量法

類中心向量算法源于向量空間模型理論，是情報檢索領(lǐng)域經(jīng)典的算法，基本思想是：在訓(xùn)練階段計算訓(xùn)練樣本集中各類的中心點，即已建立分類器；當(dāng)測試文本D需要分類時，將其進(jìn)行向量表示后，計算與各類中心向量的相似度，最后將D標(biāo)定為相似度最大的那個類別。

1.2KNN近鄰算法

KNN（K Nearest Neighbor）算法是一種基于實例統(tǒng)計的文本分類方法。該算法思想為：給定一個帶標(biāo)注的訓(xùn)練文本集，在對新文本進(jìn)行分類時，從訓(xùn)練集的特征空間中找出與新文本最相似的K篇文本，這些K篇文本所屬的類別是已經(jīng)訓(xùn)練好的了，已經(jīng)正確分類的了，那么目標(biāo)新文本也劃分到該類別中。

1.3樸素貝葉斯算法

樸素貝葉斯（Naive Bayes）算法是來自概率統(tǒng)計的貝葉斯決策理論。基本思想是：給出待分類項，在該項出現(xiàn)的條件下求解出各個類別出現(xiàn)的概率，選取最大的那一個，把待分類項分到那個類別。簡單來說，就是利用關(guān)鍵詞語在類中出現(xiàn)的概率，概率越大的，就推測給定文檔屬于該類。NB方法的樸素是因為它的特征屬性單詞獨立性假設(shè)，即不同單詞在給定類別下的條件概率是互相獨立的（文檔中的每個詞都是相互獨立出現(xiàn)的，且詞的出現(xiàn)沒有線性順序關(guān)系）。

1.4自訓(xùn)練學(xué)習(xí)

自訓(xùn)練（Self-Training）算法是半監(jiān)督學(xué)習(xí)中比較常見的方法之一，首先對已標(biāo)作過標(biāo)注的少量樣本進(jìn)行監(jiān)督學(xué)習(xí)訓(xùn)練，再將沒有標(biāo)注過的樣本添加到通過訓(xùn)練集所得的初始分類器中訓(xùn)練，進(jìn)行預(yù)測，得出的數(shù)值越大代表分類取得的效果越好，將該分類得到數(shù)值大的文本和其分類標(biāo)注一起添加到訓(xùn)練集合中，作為新的訓(xùn)練樣本集進(jìn)行又學(xué)習(xí)，迭代訓(xùn)練直到滿足條件為止。

另外還有一種經(jīng)典的被稱作上帝的算法的是期望最大（Expectation-Maximization）方法，它與樸素貝葉斯方法都是來源于概率統(tǒng)計模型。期望最大化算法是一用來解決數(shù)據(jù)不完整的參數(shù)估計問題，需要循環(huán)迭代，最后收斂于最大似然參數(shù)的一種估計方法。定義一個最大化函數(shù)，收集一些訓(xùn)練數(shù)據(jù)集，就可以使用EM算法進(jìn)行若干次迭代后即可得到所需模型，這是提出的最早的一種半監(jiān)督學(xué)習(xí)方法，很好用，一般迭代三四次，所定義的目標(biāo)函數(shù)就能收斂。

1.5基于生成模型的半監(jiān)督分類

樣本生成模型（Generative Models）是根據(jù)統(tǒng)計學(xué)的觀點提出來的，需要把樣本數(shù)據(jù)分為標(biāo)記樣本和未標(biāo)記樣本，該模型的參數(shù)一般先由標(biāo)記樣本計算確定，然后結(jié)合標(biāo)記樣本并利用當(dāng)前模型訓(xùn)練出未標(biāo)記樣本后再進(jìn)行共同調(diào)整。首先對模型的參數(shù)進(jìn)行初始估計，采用上文提到的期望最大化算法（EM），再進(jìn)行重復(fù)執(zhí)行E步和M步，直至收斂。E步稱為期望步，根據(jù)當(dāng)前參數(shù)計算每個對象關(guān)于各個簇的隸屬概率；M步稱為最大化步，使用E步計算的概率來更新參數(shù)估計。

使用不同的生成式模型作為基分類器，會產(chǎn)生不一樣的分類結(jié)果，例如混合高斯（Mixture of Gaussians）、混合專家（Mixture of Experts）、樸素貝葉斯等。生成式模型會讓半監(jiān)督學(xué)習(xí)更簡單方便，預(yù)測結(jié)果比較直觀，當(dāng)標(biāo)記樣本非常稀少的時候，通過訓(xùn)練樣本得到的生成式模型較其他模型具有更好的性能，如果假設(shè)模型不能準(zhǔn)確地得出數(shù)據(jù)的分布，需要利用大量的未標(biāo)記數(shù)據(jù)來估計模型參數(shù)，必定會大大降低訓(xùn)練出的模型的泛化能力。文本分類中另一個重要的考慮其實就是需要標(biāo)記數(shù)據(jù)的可用性。數(shù)據(jù)標(biāo)記是非常耗時的任務(wù)，因此，在許多情況下，它們在數(shù)量上有限。如果可能的話，我們想利用這個有限的標(biāo)簽信息，以及在我們的分類時將無標(biāo)簽的數(shù)據(jù)加入到訓(xùn)練集合中，一起構(gòu)成訓(xùn)練樣本，有了這個目標(biāo)，我們采用了半監(jiān)督和監(jiān)督相結(jié)合的學(xué)習(xí)方法，利用這些標(biāo)記和未標(biāo)記的數(shù)據(jù)得出更適合的分類器模型。在實際進(jìn)行數(shù)據(jù)建模的時候，怎樣選擇合適的半監(jiān)督學(xué)習(xí)方法來訓(xùn)練分類器？本文來做一個實驗對比下它們的分類精度，提出改進(jìn)方法，讓訓(xùn)練出來的分類器盡可能地提高正確分類的比例。

2　實驗和分類評估指標(biāo)

2.1實驗數(shù)據(jù)集

實驗數(shù)據(jù)集來源是搜狗實驗室測試文本分類文章語料庫（http://www.sogou.com/labs/dl/c.html），共有九類，為了便于實驗，計算機(jī)自動抽取的524篇文章里，對有把握分類的488篇重新分為五類，實驗分別在有監(jiān)督學(xué)習(xí)和半監(jiān)督學(xué)習(xí)下對數(shù)據(jù)集進(jìn)行分類，有監(jiān)督下分類分為訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集，如下表1：

表1　有監(jiān)督訓(xùn)練數(shù)據(jù)集

半監(jiān)督分類的測試數(shù)據(jù)與有監(jiān)督分類相同，訓(xùn)練數(shù)據(jù)部分劃分為兩部分，一部分作為初始標(biāo)記樣本數(shù)據(jù)，另一部分作為訓(xùn)練數(shù)據(jù)，如下表2：

表2　半監(jiān)督訓(xùn)練數(shù)據(jù)集

2.2分類評估指標(biāo)

本實驗采用準(zhǔn)確率，召回率和F1的值（F1值越大分類效果越好）三個數(shù)據(jù)來評估文本分類器的性能，它們分別計算的公式如下：

精確率（pecision）:

召回率（recall）：

F1測試值：

3　實驗分析

本實驗環(huán)境是：聯(lián)想B460筆記本上，處理器Intel i3，內(nèi)存4GB，硬盤320G，操作系統(tǒng)：Windows 10，實驗算法是在MATLAB7上進(jìn)行的。有監(jiān)督訓(xùn)練學(xué)習(xí)選擇了類中心向量算法，KNN算法（先取K=5）和樸素貝葉斯算法。半監(jiān)督學(xué)習(xí)訓(xùn)練采用類向量+自訓(xùn)練相組合算法：即對于標(biāo)記樣本的數(shù)采用類中心向量訓(xùn)練，再結(jié)合未標(biāo)記樣本，用自訓(xùn)練算法迭代循環(huán)訓(xùn)練得出最終分類器和分類結(jié)果。

有監(jiān)督分類結(jié)果：

表3　類中心向量的有監(jiān)督分類精度

表4　KNN（K=5）的有監(jiān)督分類精度

表5　貝葉斯的有監(jiān)督分類精度

半監(jiān)督分類結(jié)果——試驗1：

表6　類中心向量+自訓(xùn)練的半監(jiān)督分類精度（訓(xùn)練數(shù)據(jù)）

表7　類中心向量+自訓(xùn)練的半監(jiān)督分類精度（測試數(shù)據(jù)）

半監(jiān)督分類結(jié)果——試驗2：

表8　類中心向量+自訓(xùn)練的半監(jiān)督分類精度（訓(xùn)練數(shù)據(jù)）

表9　類中心向量+自訓(xùn)練的半監(jiān)督分類精度（測試數(shù)據(jù)）

為了保證試驗的可比性，又取同樣的數(shù)據(jù)進(jìn)行了試驗3，結(jié)果和試驗2一樣，用折線圖來表示算法精確度對比情況：

為了更好地表示半監(jiān)督分類算法的效果，本文又設(shè)計了一組半監(jiān)督分類算法（貝葉斯+EM）試驗，從表3可以看出樸素貝葉斯算法在對小樣本數(shù)據(jù)集處理時表現(xiàn)出很差的分類效果，沒有用平滑處理零概率文本，因此我們決定用期望最大化算法來訓(xùn)練貝葉斯分類器，期望通過這種組合，可以得出更好的分類效果。具體步驟如下：

1.僅采用標(biāo)注集合L（部分訓(xùn)練數(shù)據(jù)）進(jìn)行初始化訓(xùn)練，得到第一個中間分類器A0；

2.Estep：根據(jù)A0中的參數(shù)值計算所有類關(guān)于每個未標(biāo)注樣本（測試數(shù)據(jù)）的后驗概率；

3.Mstep：利用包括了標(biāo)注和未標(biāo)注樣本的訓(xùn)練集D以及P訓(xùn)練出新的中間分類器A1。

EM步驟一直迭代（迭代次數(shù)k=2或者3次），直到A1收斂，最終即可得到比較好的分類器。

還是使用相同的數(shù)據(jù)集，只不過這次單以測試數(shù)據(jù)作為建模對象，得出試驗圖4如下：

圖3　半監(jiān)督分類3次試驗各測試值折線圖

圖4　貝葉斯+EM測試分類圖

4　結(jié)語

通過觀察半督分類結(jié)果可以發(fā)現(xiàn)，兩次試驗的測試精度有三類（分類編號為1，2，5）都達(dá)到了要求（F1測試值＞70%），沒有達(dá)到要求的兩類都為數(shù)據(jù)樣本稀少的小類（總共49篇、25篇，分類編號分別為3和4）。通過觀察實驗結(jié)果，還會發(fā)現(xiàn)上述幾種方法在稀有類別上的準(zhǔn)確性都較低，然而，KNN和類中心向量法對樣本分布的穩(wěn)定性要好于NB等方法。其中我們知道NB方法是基于假設(shè)一個特征單詞在一個分類文檔中的發(fā)生概率與該文檔中的其他單詞無關(guān)，從而使得計算復(fù)雜度簡單，具有較高的效率。但是，該假設(shè)在現(xiàn)實中對于絕大多數(shù)文本都不能得到很好的保證，其中有的還出現(xiàn)了零概率的情況。故后來我們又采用了半監(jiān)督的分類（貝葉斯+EM）的組合方法，通過試驗對比，給出了相對較好的分類效果。

現(xiàn)實中，網(wǎng)絡(luò)上大量的沒有處理過的數(shù)據(jù)集在類別的分布上常常都是偏斜的，十分不均衡的，導(dǎo)致了分類效果很不理想。而實驗環(huán)境下驗證一個分類器效果好不好，用這種分類算法來訓(xùn)練分類器得到了改善，它們所選的數(shù)據(jù)集大都是均勻的，所以結(jié)論都得到很好的分類效果。如果在數(shù)據(jù)偏斜的情況下進(jìn)行實驗分類，分類器往往會忽視少量稀疏類的樣本，因為樣本無法準(zhǔn)確反映整個空間的數(shù)據(jù)分布情況。通過查閱文獻(xiàn)，得知Yang［9］研究的支持向量機(jī)（SVM）、NB及KNN等許多分類算法均控制了樣本的分布，再做實驗分析從理論上來對比分析分類效果與數(shù)據(jù)分布之間的關(guān)系，其結(jié)果大部分都表明:SVM和KNN對樣本分布的魯棒性要優(yōu)于NB等方法，這也印證了SVM的泛化性能以及NB對類別先驗概率的依賴性。這也是這些分類算法的缺陷，因為各種方法在稀有類別上的分類效果準(zhǔn)確性均很低。本文就是在實驗時，特意選擇樣本數(shù)據(jù)集有一部分是稀疏的做了實驗，這一結(jié)論同樣體現(xiàn)在我們的數(shù)據(jù)結(jié)果上。

［1］張俊麗．文本分類中關(guān)鍵技術(shù)研究．華中師范大學(xué)，2008．［4］孫麗華．中文文本自動分類的研究．哈爾濱工程大學(xué)，2002．

［2］張浩，汪楠．文本分類技術(shù)研究進(jìn)展．計算機(jī)科學(xué)與技術(shù).2007，23:95-96.

［3］盧葦，彭雅.幾種常用文本分類算法性能比較與分析［J］.湖南大學(xué)學(xué)報，2007.03.02.

［4］陳琳，王箭.三種中文文本自動分類算法的比較和研究［J］.計算機(jī)與現(xiàn)代化，2011.06.15.

［5］汪傳建，李曉光，王大玲，于戈.一種基于混合模型的文本分類器的設(shè)計與實現(xiàn).計算機(jī)研究與發(fā)展增刊，2004，VoL41，96-100.

［6］DudaP E，Richard O.Hart，Pattern Classification and Scene Analysis［J］.1973.

［7］李永平，程莉，葉衛(wèi)國.基于隱含語義的KNN文本分類研究［J］.計算機(jī)工程與應(yīng)用.2004.

［8］Sebast，nai，.F，2002.Machine Learning Automated Text Categorization［J］.ACM Computing Suvreys，34（1），1-47.

［9］Yang M H，Ahuja N.A Geometric Approach to Train Support Vector Machines［C］.Proceedings of CVPR 2000.Hilton Head Island，2000:430-437.

Performance Comparison and Analysis of Several Text Classification Algorithms

YANG Juan，WANG Wei-yang
（College of Information Engineering，Shanghai Maritime Univeristy，Shanghai 201306）

Analyzes several typical text classification algorithms，gives five types of text data sets，the classic text categorization algorithm test comparison by precision，recall accuracy rate and test value to evaluate the performance of the text classifier，and gives the analysis result and the improved combination training method.The results show that the combination of semi supervised learning training and supervised learning can achieve better classification results.In order to improve the speed of text recommendation，the preliminary work is to choose the appropriate classification algorithm，combine selection algorithm to improve the accuracy and efficiency.

Text Categorization；Supervised Learning；Portfolio Selection；Recommendation

1007-1423（2016）25-0012-05DOI：10.3969/j.issn.1007-1423.2016.25.003

楊娟（1991-），女，安徽安慶人，碩士研究生，學(xué)生，研究方向為數(shù)據(jù)庫開發(fā)與應(yīng)用王未央（1963-），女，江蘇常熟人，碩士研究生導(dǎo)師，副教授，研究方向為數(shù)據(jù)處理與挖掘

2016-04-19

2016-09-02