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

楊娟，王未央

（上海海事大學信息工程學院，上海201306）

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

楊娟，王未央

（上海海事大學信息工程學院，上海201306）

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

文本分類；監督學習；組合選擇；推薦

0　引言

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

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

先給出文本分類的一般算法流程和半監督學習的文本分類流程圖如下：

圖1　文本分類的一般流程

圖2　基于半監督學習的文本分類流程

1　常用文本分類方法思想

1.1類中心向量法

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

1.2KNN近鄰算法

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

1.3樸素貝葉斯算法

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

1.4自訓練學習

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

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

1.5基于生成模型的半監督分類

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

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

2　實驗和分類評估指標

2.1實驗數據集

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

表1　有監督訓練數據集

半監督分類的測試數據與有監督分類相同，訓練數據部分劃分為兩部分，一部分作為初始標記樣本數據，另一部分作為訓練數據，如下表2：

表2　半監督訓練數據集

2.2分類評估指標

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

精確率（pecision）:

召回率（recall）：

F1測試值：

3　實驗分析

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

有監督分類結果：

表3　類中心向量的有監督分類精度

表4　KNN（K=5）的有監督分類精度

表5　貝葉斯的有監督分類精度

半監督分類結果——試驗1：

表6　類中心向量+自訓練的半監督分類精度（訓練數據）

表7　類中心向量+自訓練的半監督分類精度（測試數據）

半監督分類結果——試驗2：

表8　類中心向量+自訓練的半監督分類精度（訓練數據）

表9　類中心向量+自訓練的半監督分類精度（測試數據）

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

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

1.僅采用標注集合L（部分訓練數據）進行初始化訓練，得到第一個中間分類器A0；

2.Estep：根據A0中的參數值計算所有類關于每個未標注樣本（測試數據）的后驗概率；

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

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

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

圖3　半監督分類3次試驗各測試值折線圖

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

4　結語

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

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

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

［2］張浩，汪楠．文本分類技術研究進展．計算機科學與技術.2007，23:95-96.

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

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

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

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

［7］李永平，程莉，葉衛國.基于隱含語義的KNN文本分類研究［J］.計算機工程與應用.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-），女，安徽安慶人，碩士研究生，學生，研究方向為數據庫開發與應用王未央（1963-），女，江蘇常熟人，碩士研究生導師，副教授，研究方向為數據處理與挖掘

2016-04-19

2016-09-02