1、基于向量空間模型的文本自動分類系統的研究與實現龐劍鋒,卜東波,白碩(中國科學院計算技術研究所,北京100080摘要:隨著網絡信息的迅猛發展,信息處理已經成為人們獲取有用信息不可缺少的工具。文本自動分類系統是信息處理的重要研究方向,它是指在給定的分類體系下,根據文本的內容自動判別文本類別的過程。對文本分類中所涉及的關鍵技術,包括向量空間模型、特征提取、機器學習方法等進行了研究和探討,并且提出了基于向量空間模型的文本分類系統的結構,并給出了評估方法和實驗結果。關鍵詞:文本分類;中文信息處理;向量空間模型R esearch and Implementation of Text C ategoriza

2、tionSystem B ased on VSMPANGJian2feng,BU D ong2bo,BAI Shuo(Institute o f Computing Technology,Chinese Academy o f Sciences,Beijing100080,ChinaAbstract:In recent years,in formation processing turns m ore and m ore im portant for us to get useful in formation.T ext categ oriza2 tion,the automated assi

3、gning of natural language texts to predefined categ ories based on their contents,is a task of increasing im por2 tance.This paper gives a research to several key techniques about text categ orization,including vector space m odel,feature extrac2 tion,machine learning.It als o describes a text categ

4、 orization m odel based on VS M,and gives the evaluations and results.K ey w ords:T ext categ orization;Chinese in formation processing;Vector space m odel1引言20世紀90年代以來,Internet以驚人的速度發展起來,它容納了海量的各種類型的原始信息,包括文本信息、聲音信息、圖象信息等等。如何在浩若煙海而又紛繁蕪雜的文本中掌握最有效的信息始終是信息處理的一大目標?；谌斯ぶ悄芗夹g的文本分類系統能依據文本的語義將大量的文本自動分門別類,從而

5、更好地幫助人們把握文本信息。近年來,文本分類技術已經逐漸與搜索引擎、信息推送、信息過濾等信息處理技術相結合,有效地提高了信息服務的質量。2問題描述211系統任務簡單地說,文本分類系統的任務是:在給定的分類體系下,根據文本的內容自動地確定文本關聯的類別。從數學角度來看,文本分類是一個映射的過程,它將未標明類別的文本映射到已有的類別中。該映射可以是一一映射,也可以是一對多的映射,因為通常一篇文本可以同多個類別相關聯,用數學公式表示如下: f:AB其中,A為待分類的文本集合,B為分類體系中的類別集合。文本分類的映射規則是系統根據已經掌握的每類若干樣本的數據信息,總結出分類的規律性而建立的判別公式和判

6、別規則;然后在遇到新文本時,根據總結出的判別規則,確定文本相關的類別。212評估方法因為文本分類從根本上說是一個映射過程,所以評估文本分類系統的標志是映射的準確程度和映射的速度。映射的速度取決于映射規則的復雜程度,而評估映射準確程度的參照物是通過專家思考判斷后對文本的分類結果(這里假設人工分類完全正確并且排除個人思維差異的因素。與人工分類結果越相近,分類的準確程度就越高。這里隱含了評估文本分類系統的兩個指標:準確率和查全率。準確率是所有判斷的文本中與人工分類結果吻合的文本所占的比率,其數學公式表示如下:準確率(Precision=分類的正確文本數實際分類的文本數查全率是人工分類結果應有的文本中

7、分類系統吻合的文本所占的比率,其數學公式表示如下:查全率(Recall=分類的正確文本數應有文本數準確率和查全率反映了分類質量的兩個不同方面,兩者必須綜合考慮,不可偏廢。因此,存在一種新收稿日期:2000212221的評估指標F1測試值,其數學公式如下:F1測試值=準確率查全率2準確率+查全率另外,有微平均和宏平均兩種計算準確率、查全率和F1值的方法。微平均:計算每一類的準確率、查全率和F1值。宏平均:計算全部類的準確率、查全率和F1值。所有文本分類系統的目標都是使文本分類過程更準確,更快速。3關鍵技術311文本的表示計算機并不具有人類的智能,人在閱讀文章后,根據自身的理解能力可以產生對文章內

8、容的模糊認識;而計算機并不能輕易地“讀懂”文章,從根本上說,它只認識0和1,所以必須將文本轉換為計算機可以識別的格式。根據“貝葉斯假設”,假定組成文本的字或詞在確定文本類別的作用上相互獨立,這樣,可以就使用文本中出現的字或詞的集合來代替文本。不言而喻,這將丟失大量關于文章內容的信息,但是這種假設可以使文本的表示和處理形式化,并且可以在文本分類中取得較好的效果。目前,在信息處理方向上,文本的表示主要采用向量空間模型(VS M。向量空間模型的基本思想是以向量來表示文本:(W1,W2,W3,Wn,其中Wi為第i個特征項的權重。那么選取什么作為特征項呢?一般可以選擇字、詞或詞組。根據實驗結果,普遍認為

9、選取詞作為特征項要優于字和詞組,因此,要將文本表示為向量空間中的一個向量,就首先要將文本分詞,由這些詞作為向量的維數來表示文本。最初的向量表示完全是0,1形式,即:如果文本中出現了該詞,那么文本向量的該維為1,否則為0。這種方法無法體現這個詞在文本中的作用程度,所以0,1逐漸被更精確的詞頻代替,詞頻分為絕對詞頻和相對詞頻。絕對詞頻,即使用詞在文本中出現的頻率表示文本;相對詞頻為歸一化的詞頻,其計算方法主要運用TF2I DF公式。目前存在多種TF2I DF公式,我們在系統中采用了一種比較普遍的TF2I DF公式:W(t,d=tf(t,dlog(N/n t+0101tdtf(t,dlog(N/n

10、t+01012其中,W(t,d為詞t在文本d中的權重,而tf(t,d為詞t 在文本d中的詞頻,N為訓練文本的總數,n t為訓練文本集中出現t的文本數,分母為歸一化因子。另外還存在其它的TF2I DF公式,例如:W(t,d=(1+log2tf(t,dlog2(N/n ttd1+log2tf(t,dlog2(N/n t2該式中參數的含義與上式相同。文本經過分詞程序分詞后,首先去除停用詞,合并數字和人名等詞匯;然后統計詞頻,最終表示為上面描述的向量。312特征項的抽取構成文本的詞匯,數量是相當大的,所以,表示文本的向量空間的維數也相當大,可以達到幾萬維。因此我們需要進行維數壓縮的工作,這樣做的目的主

11、要有兩個:第一,為了提高程序的效率,提高運行速度;第二,所有幾萬個詞匯對文本分類的意義是不同的,一些通用的、各個類別都普遍存在的詞匯對分類的貢獻小;在某特定類中出現比重大而在其它類中出現比重小的詞匯對文本分類的貢獻大。為了提高分類精度,對于每一類,我們應去除那些表現力不強的詞匯,篩選出針對該類的特征項集合,存在多種篩選特征項的算法,如下所列:(1根據詞和類別的互信息量判斷(2根據詞熵判斷(3根據K L距離判斷在我們的系統中采用了詞和類別的互信息量進行特征項抽取的判斷標準,其算法過程如下:初始情況下,該特征項集合包含所有該類中出現的詞。對于每個詞,計算詞和類別的互信息量logP(W|C jP(W

12、其中,P(W|Cj=1+|D|i=1N(W,d i|V|+|V|s=1|D|i=1N(W s,d iP(W|C j為W在C j中出現的比重,|D|為該類的訓練文本數,N(W,d i為詞W在d i中的詞頻,|V|為總詞數,|V|s=1|D|i=1N(W s,d i為該類所有詞的詞頻和。而P(W同上面的計算公式相同,只是計算詞在所有訓練文本中的比重,其中,|D|為全體訓練文本數。對于該類中所有的詞,依據上面計算的互信息量排序。抽取一定數量的詞作為特征項。具體需要抽取多少維的特征項,目前無很好的解決方法,一般采用先定初始值,然后根據實驗測試和統計結果確定最佳值。一般初始值定在幾千左右。將每類中所有的

13、訓練文本,根據抽取的特征項進行向量維數壓縮,精簡向量表示。其它抽取特征項的算法,除判斷函數上有所差別外,主要過程類似。313訓練方法與分類算法訓練方法和分類算法是分類系統的核心部分,目前存在多種基于向量空間模型的訓練算法和分類算法,例如,支持向量機算法、神經網絡方法、最大平均熵方法、最近K鄰居方法和貝葉斯方法等等。以下具體介紹三種分類算法:(1簡單向量距離分類法該方法的分類思路十分簡單,根據算術平均為每類文本集生成一個代表該類的中心向量;然后在新文本來到時,確定新文本向量,計算該向量與每類中心向量間的距離(相似度;最后判定文本屬于與文本距離最近的類。具體步驟如下:計算每類文本集的中心向量;計算

14、方法為所有訓練文本向量簡單的算術平均。新文本到來后分詞,將文本表示為特征向量。計算新文本特征向量和每類中心向量間的相似度,公式為:S im(d i,d j=Mk=1W ikW jk (Mk=1W2ik(Mk=1W2jk其中,d i為新文本的特征向量,d j為第j類的中心向量,M為特征向量的維數,W k為向量的第K維。比較每類中心向量與新文本的相似度,將文本分到相似度最大的那個類別中。(2貝葉斯算法該算法的基本思路是計算文本屬于類別的概率。文本屬于類別的幾率等于文本中每個詞屬于類別的幾率的綜合表達式,具體算法步驟如下:(1,2,3,n,其中,W k=P(W k|C j=1+|D|i=1N(W k

15、,d i|V|+|V|s=1|D|i=1N(W s,d i計算公式與計算互信息量的公式相同。在新文本到達時,根據特征詞分詞,然后按下面的公式計算該文本d i屬于類C j的幾率:P(C j|d i=P(C j|n k=1P(W k|C j;N(W k,d i|C|r=1P(C r|n k=1P(W k|C r;N(W k,d i其中,P(C j|=C j 訓練文檔數總訓練文檔數P(C r|為相似含義,|C|為類的總數,N(W k,d i為W k在d i中的詞頻,n為特征詞總數。比較新文本屬于所有類的幾率,將文本分到幾率最大的那個類別中。(3K NN(K最近鄰居算法該算法的基本思路是:在給定新文本

16、后,考慮在訓練文本集中與該新文本距離最近(最相似的K篇文本,根據這K篇文本所屬的類別判定新文本所屬的類別。具體的算法步驟如下:根據特征項集合重新描述訓練文本向量。在新文本到達后,根據特征詞分詞新文本,確定新文本的向量表示。在訓練文本集中選出與新文本最相似的K個文本,計算公式為:sim(d i,d j=Mk=1W ikW jk (Mk=1W2ik(Mk=1W2jk其中,K值的確定目前沒有很好的方法,一般采用先定一個初始值,然后根據實驗測試的結果調整K值。一般初始值定為幾百到幾千之間。在新文本的K個鄰居中,依次計算每類的權重,計算公式如下:p(x,C j=diK NNSim(x,d iy(d i,

17、C j其中,x為新文本的特征向量;Sim(x,d i為相似度計算公式,與上一步驟的計算公式相同;而y(d i,C j為類別屬性函數,即:如果d i屬于類C j,那么函數值為1,否則為0。比較類的權重,將文本分到權重最大的那個類別中。除此以外,支持向量機和神經網絡算法在文本分類系統中應用得較為廣泛。支持向量機的基本思想是使用簡單的線形分類器劃分樣本空間。對于在當前特征空間中線形不可分的模式,則使用一個核函數把樣本映射到一個高維空間中,使得樣本能夠線形可分。而神經網絡算法采用感知算法進行分類。在這種模型中,分類知識被隱式地存儲在連接的權值上,使用迭代算法來確定權值向量。當網絡輸出判別正確時,權值向

18、量保持不變,否則進行增加或降低的調整,因此也稱為獎懲法。314閾值的確定上面的算法都是將新文本歸于分類體系中的一個類,即與該文本關聯最大的類。而事實上,分類體系中的類別不是完全互斥的,存在這樣一些既屬于其中一個類別,又同時屬于其它類別的文本。對于這種文本,上述的分類算法無法確定文本所屬的所有類別;因此,需要對每個類別確定閾值,當文本在該類的閾值之上時,就將文本歸于該類中。但是,閾值的確定是十分困難的,理論上,沒有很好地解決方法,一般采用預定初始值,然后給出測試文本,使用分類器進行分類,再根據分類的準確程度調整初始值。這樣的方法有兩個缺點:首先,初始值的確定不容易,完全是根據經驗或簡單的測試而定

19、;其次,調整的幅度無法確定,當初始值過高或過低需要增減時,增減的幅度無法很好地確定,只能反復測試,反復調整,這樣就大大地增加了工作量。而且,一個分類系統的閾值由于測試文本的不同也無法完全應用于另一個分類系統中。我們在系統中考慮了一種確定閾值的方法,稱為百分比閾值確定法,它的基本思想是:首先依據上述訓練算法和分類算法構造分類器;然后對于要確定閾值的類,用分類器對該類中所有的訓練文本進行分類,從而使每個文本都得到一個相關的值。以上述算法為例:簡單向量距離分類法文本與本類中心向量間的相似度值貝葉斯算法文本歸屬于類的幾率K NN算法K個鄰居中的類權重然后按遞減順序排列所有本類訓練文本得到的值。假定本類

20、有n 篇文本,那么這些文本的值為d 1,d 2,d n ,那么本類閾值y 確定為:y =d sn %其中,s 為初始值。根據訓練文本的質量程度,可以確定為80或更高,這樣就確定了本類的初始閾值。可以想象,S 越大,該分類器的查全率就越高,準確度就越低;相反地,S 越小,查全率就越低,準確率就越高。然后根據測試進行調整。相應地,調整閾值可以轉化為調整s 值,如果對查全率滿意而對準確率不滿意,那么可以減少s 值,否則就增加s 值。4系統的結構框架我們實現的文本分類系統,研究并結合了上述的關鍵技術,其結構如圖1所示。 圖1系統的結構框架,我們實現了上述的三種訓練算法和分類算法,并對其效率和結果進行了

21、一定的比較和測試。5測試數據和實驗結果我們在一個具有2830篇中文文本的語料庫上測試我們系統實現的分類算法,并對其效率和結果進行了比較分析。語料庫中的文本都是新聞電訊稿,絕大部分采自新華社,還有200余篇采自中國新聞社和人民日報。所有的新聞稿都由領域專家事先進行分類,按照中圖分類法分成政治、經濟、軍事等共38類。我們選擇訓練集和測試集的方法如下:將這些分好類的語料平均分成10份,選擇其中1份作為開放測試集,剩余的9份作為訓練集和封閉測試集。這樣每1份都依次輪流作為開放測試集,運行分類算法,共執行10次分類操作,計算其平均值,實驗結果如表1所示。表1算法封閉測試查全率封閉測試準確率封閉測試F1值

22、開放測試查全率開放測試準確率開放測試F1值簡單向量距離87.08%87.08%87.08%80.23%80.23%80.23%貝葉斯82.39%83.78%83.08%76.17%77.26%76.71%K NN 89.11%91.42%90.25%83.29%85.12%84.20%另外,從算法的時間花費考慮,假設系統的訓練文本集包括m 篇文本(向量,分別屬于k 個類,而抽取的特征項為n 維,則這三種算法的時間花費見表2。表2算法訓練算法分類過程簡單向量距離O (mn O (kn 貝葉斯O (mn O (kn K NN無O (km +nm 因此,從測試結果看來,K NN 算法在分類效果上是最

23、佳的,同時在訓練過程中投入的時間最少,但是在分類過程中花費的時間最多,不利于文本的實時處理;而貝葉斯算法和簡單向量距離算法的時間花費近似,其分類效果也近似,簡單距離算法的效果略好。6將來的工作今后,我們在文本分類方向上的研究工作主要圍繞三個方面展開:在向量空間模型方面,結合計算語言學,使用概念空間代替詞空間;目前的分類體系為平面體系,可以在層次分類體系中考慮文本分類系統;新算法的研究及舊算法的改進。7結束語本文探討了文本分類系統的關鍵技術,比較和分析了三種訓練和分類算法,并提出了文本分類系統的結構模型,同時給出了實驗結果和分析,將來還將繼續在層次分類體系中進行文本分類系統的進一步研究。參考文獻

24、:1David D Lewis 1Feature Selection and Feature Extraction for T extCateg orizationA 1In Proceedings of S peech and Natural Lan 2guage W orkshop C .Defense Advanced Research Projects A 2gency ,M organ K au fmann ,1992,212221712Y iming Y ang 1An Evaluation of S tatistical Approaches to T extCateg orizationJ 1In Journal of In formation Retrieval ,1999,1(1/2:6728813David D Lewis ,M arc Ringuette 1A C om paris on of T ow LearningAlg orithms of T ext Categ orizationA1In Third Annual S ym posium on D ocument Analysis and In formatio