基于后綴樹模型的文本實時分類系統(tǒng)的研究和實現(xiàn)(

1、基于后綴樹模型的文本實時分類系統(tǒng)的研究和實現(xiàn)作者簡介：張吉，出生于1979，女，碩士，主要研究方向網(wǎng)絡安全、數(shù)據(jù)流管理；譚建龍，1974，男，博士，主要研究方向網(wǎng)絡安全、數(shù)據(jù)流管理；郭莉，1969，女，碩士，副研究員，主要研究方向網(wǎng)絡安全、數(shù)據(jù)流管理。 張吉1, 郭莉1, 譚建龍1 1(中科院計算所,北京市 100084)(zhangji) 摘 要:本文在面向網(wǎng)絡內(nèi)容分析的前提下，提出了一種基于后綴樹的文本向量空間模型(VSM)，并在此模型之上實現(xiàn)了文本分類系統(tǒng)。對比基于詞的VSM，該模型利用后綴樹的快速匹配，實時獲得文本的向量表示，不需要對文本進行分詞、特征抽取等復雜計算。同時，該模型能夠保

2、證訓練集中文本的更改，對分類結(jié)果產(chǎn)生實時影響。實驗結(jié)果和算法分析表明，我們系統(tǒng)的文本預處理的時間復雜度為O(N)，遠遠優(yōu)于分詞系統(tǒng)的預處理時間復雜度。此外，由于不需要分詞和特征抽取，分類過程與具體語種無關(guān)，所以是一種獨立語種的分類方法。關(guān)鍵詞:實時文本分類；向量空間模型；后綴樹中圖法分類號:TP391Resarch and Implementation of On-line Text Categorization System Based on Suffix TreeCHANG Ji1,GUO Li 1, TAN Jian-Long1 1(Institute of Computing Tech

3、nology, Chinese Academy of Sciences, BeiJing, 100084) (zhangji)Abstract: We propose a text vector space model(VSM) based on suffix tree and implement a text categorizing system on the model. The model can perform fast matching by the support of suffix tree, obtain the vector presentation of text and

4、 avoid the complex computation such as word segmentation or feature extraction of the text. In addition, this model can guarantee that the alteration of the training set can affect the result of classification in real time. Experiment and analysis of the algorithm show that, the time complexity of t

5、ext preprocessing in our system is O(N), which is much better than that of word segmentation method. Besides, the avoidance of word segmentation and feature extraction shows that the categorizing process is irrelevant to do with the concrete language and is a language independent method.Key words:On

6、line Text Categorization; Vector Space Model; suffix tree1 引言隨著信息技術(shù)的發(fā)展，特別是Internet應用的普及，人們已經(jīng)從信息缺乏的時代過渡到信息極為豐富的時代。如何從大量信息中迅速有效地提取出所需信息也就成為一項重要的研究課題。由于分類可以在較大程度上解決目前網(wǎng)絡信息雜亂的現(xiàn)象，方便用戶準確定位所需信息，因此分類尤其是文本分類的研究日益重要1。文本分類是指在給定分類體系下，根據(jù)文本的內(nèi)容自動確定文本類別的過程。通常來說，文本分類是面向自然語言處理的。在這種分類中分類的正確性遠比分類的速度更重要。但是在網(wǎng)絡內(nèi)容分析中，我們認為分類

7、的速度和分類的正確性都必須充分考慮。在實時內(nèi)容分析中，目前技術(shù)尚不足以直接高效地利用大量語義特征，但是我們至少可以綜合分析某些字結(jié)構(gòu)在文本中出現(xiàn)的量化統(tǒng)計特征。因此我們在面向網(wǎng)絡內(nèi)容分析前提下，提出了基于后綴樹模型的實時分類系統(tǒng)，并做了部分測試工作。本文主要探討了新的文本表示模型和這種模型下的一個分類系統(tǒng)的實現(xiàn)，第一部分為引言，介紹了實時文本分類系統(tǒng)的應用需求和研究現(xiàn)狀；第二部分探討了基于后綴樹的文本分類方法，著重介紹了文本表示；第三部分給出了我們的實時文本分類系統(tǒng)的實現(xiàn)；第四部分是該系統(tǒng)的實驗結(jié)果和相關(guān)分析；第五部分進行總結(jié)，并展望下一步的工作。1.1 實時分類系統(tǒng)的應用隨著因特網(wǎng)在全世界的

8、普及，網(wǎng)絡傳輸技術(shù)的迅速發(fā)展，每天世界上有驚人數(shù)目的信息在互聯(lián)網(wǎng)上流動。如何快速地從這個巨大的信息流中得到自己想要的信息、過濾掉無用的信息，成為一個重要的課題。這些實時性較強的需求包括：垃圾郵件判別、網(wǎng)絡情報分析、實時新聞分類等等。但是由于自然語言處理算法的復雜度一般比較高，很多基于自然語言處理的信息處理技術(shù)（包括語法分析，組塊分析）目前在實時內(nèi)容分析的環(huán)境中，尚無法應用。垃圾郵件是互聯(lián)網(wǎng)上一個日益嚴峻的問題，據(jù)科技日報報道：“去年垃圾郵件給美國公司帶來了89億美元的損失，給歐洲企業(yè)帶來了25億美元的損失。美國研究人員估計，2002年，美國人均收到2200封垃圾郵件，而2007年將會達到360

9、0封?！崩]件的判斷一般來說也是一個分類問題：新來的郵件是正常郵件還是垃圾郵件。實時分類系統(tǒng)還可以應用于實時新聞分類。在競爭日趨激烈的傳媒界，第一時間報道突發(fā)性事件是所有的編輯夢寐以求的事情；實時分類系統(tǒng)將這些信息迅速判斷其類別，一旦有用戶感興趣的信息，可以馬上向用戶反饋。實時分類系統(tǒng)對于新聞機構(gòu)和情報系統(tǒng)的實時采編是非常有幫助的4。自有人類以來，情報分析一直是一項很重要的工作。傳統(tǒng)的方法是對情報進行定性分析、推理，從而作出決策，整個過程需要大量的人力勞動。而且在日趨復雜化的當今世界，已經(jīng)很難根據(jù)個人經(jīng)驗知識和對當前形式的分析、認識，作出準確、快速的判斷和預測。實時分類系統(tǒng)對網(wǎng)絡情報進行快速

10、分類，有利于提高情報分析的效率，并為進一步分析工作提供信息。1.2 分類方法研究現(xiàn)狀文本分類方法主要有基于統(tǒng)計與基于規(guī)則兩大類?；谝?guī)則的文本分類方法在一定范圍內(nèi)可以得到較好的分類效果，但是需要人為設定規(guī)則，從而介入大量的人力，無法滿足實時、自動分類的要求。基于統(tǒng)計的分類主要算法有：k近鄰(KNN)，樸素貝葉斯法，貝葉斯網(wǎng)絡，神經(jīng)網(wǎng)絡算法，支持向量機，EM算法，SOM算法等。其中SVM分類器和KNN分類器是目前分類性能較好的兩種分類器。但是，這兩種分類器所采用的方法都需要較長的預處理時間，并不適用于訓練集動態(tài)變化的情況。所以，我們提出了基于后綴樹模型的文本分類方法，因為其線性增長的特性9,10

11、，能夠滿足訓練集動態(tài)變化的情況。2 基于后綴樹模型的分類方法2.1 問題描述簡單地說，文本分類系統(tǒng)的任務是：在給定的分類體系下，根據(jù)文本的內(nèi)容自動地確定文本關(guān)聯(lián)的類別。從數(shù)學角度來看，文本分類是一個映射的過程，它將未標明類別的文本映射到已有的類別中，該映射可以是一一映射，也可以是一對多的映射，因為通常一篇文本可以同多個類別相關(guān)聯(lián)。用數(shù)學公式表示如下：文本分類的映射規(guī)則是系統(tǒng)根據(jù)已經(jīng)掌握的每類若干樣本的數(shù)據(jù)信息，總結(jié)出分類的規(guī)律性而建立的判別公式和判別規(guī)則。然后在遇到新文本時，根據(jù)總結(jié)出的判別規(guī)則，確定文本相關(guān)的類別。2.2 文本表示一個中文文本表現(xiàn)為一個由漢字和標點符號組成的字符串，由字組成詞

12、，由詞組成短語，進而形成句、段、節(jié)、章、篇等結(jié)構(gòu)。直接使用整個字符串作為分類的原始輸入是很不方便的，有必要尋找一種更精練的形式化表示方法。目前，在信息處理方向上，文本的表示主要采用向量空間模型 (VSM)。經(jīng)典的向量空間模型（Vector Space Model，VSM）是Salton等人于60年代末提出的，并成功地應用于著名的SMART系統(tǒng)，已成為最簡便高效的文本表示模型之一。我們系統(tǒng)的一個重要改進在于不需要分詞或特征提取，即不是通過提取特征值來得到表示文本的向量，而是采用后綴樹結(jié)構(gòu)，為訓練集中的每個文件建樹，再通過后綴樹匹配，從而得到以測試文本為基準的向量表示。在本章中，將依次介紹后綴樹結(jié)

13、構(gòu)，以及在此之上的向量化方法和權(quán)重計算。2.2.1 后綴樹結(jié)構(gòu)后綴樹是一種基礎的數(shù)據(jù)結(jié)構(gòu)，它能快速解決很多字符串方面的問題。下面是和后綴樹相關(guān)的一些定義。定義1.1（輸入字符集）：字符串中可能出現(xiàn)的所有字符的集合。定義1.2（后綴）：假設字符串S s1s2.sisn，其中，si屬于輸入字符集，那么Si sisi1sn是S從位置i開始的后綴。定義1.3（后綴樹）：一個有m個字符的串S，它的后綴樹是一棵有根的有向樹，共有m個葉子，分別標號為1到m。每一條邊都用S的非空子串來表示。從任一節(jié)點出來的兩條邊，它們必須以不同的字符開始。從根節(jié)點到葉子節(jié)點i，順序經(jīng)過的樹邊的串聯(lián)，恰好為S從i位置開始的后綴

14、，即Si。此外，為保證所有的后綴都結(jié)束在葉子節(jié)點，在字符串末尾添加不屬于輸入字符集的字符$。見圖1。圖1字符串a(chǎn)bab$的后綴樹2.2.2 向量化算法在已有的分詞系統(tǒng)中，有些用詞語作為特征項粒度，那么在分類時不得不對輸入文檔分詞，而分詞是個很復雜、很耗時的過程；另外一些系統(tǒng)，直接使用N元字串，以避免分詞過程。但兩者都需要再進行繁瑣的特征提取過程，所以，我們提出針對給定文本的多元字串文本表示方法，即同時統(tǒng)計1元到N元子串在給定文本中的出現(xiàn)次數(shù)。例如：中華人民共和國1元漢字串疊加：中 華 人 民 共 和 國；3元漢字串疊加：中華人 華人民 人民共 民共和 共和國；那么，對于長度為L的文本，其N元子

15、串的個數(shù)為(L-N+1)個。在2.2.1節(jié)中我們已經(jīng)將文檔Di表示為后綴樹Ti，令測試文本為D，對于文本中任意位置k，在樹Ti中查找從k開始的1元到N元子串的出現(xiàn)頻率，記錄在ac1，ac2，acN中。然后，利用公式得到位置K的對應值。其中p是字符串長度權(quán)重因子。為了強調(diào)相匹配字符串長度越大，文本之間的相似度越高，一般取p大于6。例如，設文檔Di=“abcaba$”，N=2，測試文本D=“abc”,對于D的文本位置k=0，1元子串為“a”，其在Di中出現(xiàn)頻率為3；2元子串為“ab”, 其在Di中出現(xiàn)頻率為2；所以tf(0,Di)=3*1p+2*2p。同理可得，tf(1,Di)=2*1p+1*2p

16、，tf(2,Di)=1*1p。通過上述步驟，后綴樹Ti就轉(zhuǎn)換為長度為（LN+1）的向量tf(0,Di) tf(1, Di) tf(L-N, Di)。2.2.3 權(quán)重計算算法在2.2.2節(jié)中，我們以測試文本為基準，得到了文檔Di的初始向量tf(0,Di) tf(1, Di) tf(L-N, Di)，對文本向量化面臨著怎樣計算權(quán)重，即向量各個分量的值的問題。給每個項賦權(quán)重時，應使得文本中越重要的項權(quán)重越大4。在我們的系統(tǒng)中采用歸一化的tf-idf公式計算權(quán)重，即TFC權(quán)重，但計算idf值稍有不同，公式如下：其中，w(t,Di) 為位置t開始的多元組（1元到N元子串）在文本 Di 中的權(quán)重， M 為

17、訓練文本的總數(shù)，mt 為訓練文本集中出現(xiàn)該多元組的文本數(shù)，分母為歸一化因子。2.3 分類算法當文檔被表示為文檔空間的向量時，兩個文檔Di和Dj之間文本相似度Sim（Di，Dj）就可以借助于向量之間的某種距離來度量。我們用夾角余弦值來表示相似度。考慮到消除文本長度對生成向量的影響，采用歸一化的tf-idf公式計算文本的向量，得到的都是單位向量。本文使用k-近鄰決策方法，就是將最近鄰法擴展成找測試樣本的k個最近樣本作為決策依據(jù)的方法，其基本規(guī)則是，在所有N個訓練樣本中找到與測試樣本最近鄰的k個樣本，其中屬于第i類的文本近似度之和表示成ki，i=1,c，則決策規(guī)則是：如果，則決策K-近鄰算法的訓練過

18、程十分簡單，它僅僅存儲文本向量和文本對應的類別，而不進行歸納和分析，即不從訓練樣本中發(fā)掘類別的含義。換句話說，它允許類中全部樣本點都具有代表類的資格。綜上所述，當新文本到達時，該算法計算新文本與所有樣本點之間的距離，選擇 K 個距離最近的樣本點，然后檢查這些樣本點的類別，按公式計算每個類別的比重值，將新文本歸入比重最大的一類中。3 系統(tǒng)實現(xiàn)和以前的分類系統(tǒng)一樣，我們的基于后綴樹的實時文本分類系統(tǒng)也分為訓練部分和實時分類部分，其整體框架如圖2：訓練過程分類過程訓練文本預處理向量化處理測試文本輸入分類和輸出測試文本預處理訓練文本輸入圖2 實時分類系統(tǒng)整體框架圖在訓練過程中，為訓練集中的所有文本建樹

19、，完成預處理；在分類過程中，首先，采用后綴樹中多元文本匹配，得到初始向量；然后根據(jù)一定規(guī)則，對初始向量進行權(quán)重處理；最后利用分類算法，得到測試文本所屬的類別。3.1 預處理模塊該模塊主要為給定文本建立后綴樹。若采用直接的方法，為長度為n的字符串構(gòu)建后綴樹，其算法的復雜度為O(n2)。1973年Weiner第一次提出了線性時間的建樹算法。幾年后，McCreight提出了更節(jié)約空間的算法。但是他們的算法都難以理解，因此限制了后綴樹的廣泛使用。直到Ukkonen提出了改進的線性時間建樹算法，它易于理解，而且具有在線特性，即從左到右依次處理每個字符6。所以，Ukkonen的算法在應用中被廣泛接收。此外

20、，本系統(tǒng)需要統(tǒng)計絕對詞頻，因此對后綴樹算法略加改進，在樹中的每個節(jié)點中記錄其葉子節(jié)點的個數(shù)，即該子串在后綴樹表示的整個文檔中出現(xiàn)的次數(shù)。3.2 向量化模塊在該模塊中，需要將后綴樹表示的文檔轉(zhuǎn)換成向量表示。主要利用后綴樹匹配算法，得到初始向量；再對初始向量進行權(quán)重計算，得到歸一化處理后的tf-idf向量。后綴樹的匹配算法相對簡單，設S= s1s2sism1sm，從根節(jié)點出發(fā)，依次匹配邊上的每個字符。如果匹配成功，即sm已經(jīng)匹配完成，那么匹配結(jié)束的那個節(jié)點（如果匹配結(jié)束在邊上，則取該邊指向的子節(jié)點）下的所有葉子節(jié)點的位置信息都是該節(jié)點出現(xiàn)的位置。圖3中，從根節(jié)點出發(fā)匹配字符串a(chǎn)b，匹配結(jié)束在三角號

21、表示的節(jié)點上，那么ab字符串出現(xiàn)的位置為該節(jié)點的葉子節(jié)點的位置信息1,3。在本文中，為了統(tǒng)計絕對詞頻，后綴樹的節(jié)點中記錄了子節(jié)點的個數(shù)，所以可以直接得到ab字符串出現(xiàn)的次數(shù)為2。如果需要分類的文本長度為L，那么需要進行L次匹配，每次匹配的最大深度為N(1元到N元的多元匹配)，那么在訓練集大小為M的情況下，得到初始向量的時間復雜度為O(L*N*M)。得到以絕對詞頻表示的向量后，再利用前面的tf-idf公式計算歸一化后的向量。圖3在表示字符串a(chǎn)bab$的后綴樹上查找字符串a(chǎn)b3.3 分類模塊在我們的實現(xiàn)中，由于實時進行向量化，所以在分類開始前，需要調(diào)用文本向量化模塊對文本進行向量化，得到歸一化的t

22、f-idf向量。然后利用前面的夾角余弦公式計算文本向量和各個文檔向量的距離，根據(jù)KNN方法對該文本歸類。4 實驗結(jié)果與分析4.1 實驗說明我們在一個具有3043篇中文文本的語料庫上測試上述基于后綴樹模型的實時分類算法。語料庫中的文檔都是新聞電訊稿，絕大部分采自新華社，還有200余篇采自中國新聞社和人民日報。所有的新聞稿都由領(lǐng)域?qū)＜沂孪冗M行分類，分成政治、經(jīng)濟、軍事等共47類。我們對這些分類文檔進行開放測試。在測試中，我們把所有3043篇中文隨機分成10份，每次抽取1份作為測試集，而剩余的9份作為訓練集。我們主要從準確率和處理性能兩方面評價文本分類系統(tǒng)。準確率即經(jīng)過分類系統(tǒng)處理，正確判斷為所屬類

23、別的文本數(shù)占總文本的百分比。處理性能則指在訓練集固定或者變動情況下，分類系統(tǒng)處理一個文本所需的平均時間。4.2 準確率測試下面是我們的測試結(jié)果：類別文件數(shù)正確率類別文件數(shù)正確率Agriculture11266.96%Auto2466.67%Biology944.44%Computer3278.13%Economy16659.04%Language4280.95%Law8870.45%LightIndust3275.00%Medical5868.97%CheIndustry2781.48%Military8141.98%OilGas2382.61%New21180.09%Mine3491.18%

24、New218192.27%nMetallurgy3170.97%New34372.09%Mechanic1283.33%New45673.21%Construct2986.21%New52360.87%Water4072.50%New64488.64%Material5392.45%New72875.00%Transpor1070.00%Other3330.30%Ltheory7766.23%Politics43586.44%Airport9873.47%Sport20278.71%Enviornment2968.97%Chemistry4564.44%Art8180.25%Space1952

25、.63%Literate4134.15%Earth4285.71%Education8962.92%nPsychology6282.26%Philosaphy5875.86%Service2445.83%History6081.68%Energy5078.00%nMaths837.50%Electrony4060.00%Physics2958.62%Commun3378.78%每類文檔數(shù)范圍0,3031,6061,500平均準確率67.69%73.36%76.21%表1 基于后綴樹模型的分類系統(tǒng)的測試結(jié)果及統(tǒng)計結(jié)果測試結(jié)果顯示，文本數(shù)較多的類結(jié)果比較好，因為從概率的角度來說，文本數(shù)多的類別入選

26、K個最近距離的概率要遠大于文本數(shù)少的類別。當每類測試文本數(shù)相近時，即僅采用每類文本數(shù)在范圍25，65的26個類時，實驗得到平均分類正確率91%。在此語料上，基于分詞和N元漢字的分類方法準確率如表2所示：分類方法準確率 特征項數(shù)目10002000300040005000N元語法54.9458%64.9359%70.5882%73.9402%76.3391%基于分詞時間62.4712%68.978%72.3628%73.8745%78.1466%基于后綴樹74.57%表2 不同分類方法準確率對比從準確率上看，基于后綴樹的分類方法達到74.57%，基本等同于基于分詞、N元語法抽取4000特征項的情況

27、。因為特征項數(shù)目越多，分類時的信息量也越大，有可能達到或者超過基于后綴樹方法的信息量，從而得到更好的準確率。但是，準確率的增加是以分類速度為代價的，隨著準確率的增加，分類所需要的時間也逐步增長。4.3 處理性能測試我們在內(nèi)存為512M，處理器為AMD OpteronTM 1.6GHz的計算機上進行性能的對比測試，得到基于分詞、N元語法和基于后綴樹分類的預處理的時間分別為74s，155s，4s。這是由于基于分詞與N元語法的方法在預處理階段都進行了文本表示、特征提取和向量化，而基于后綴樹的分類方法在預處理階段只進行了文本表示，這是由該方法的特性決定的：對于不同的測試文本，訓練集的向量化結(jié)果不同，需

28、要在分類階段進行實時向量化。基于后綴樹的分類方法在分類階段需要進行向量化、分類輸出，其處理時間約為7kb/s,在處理時間上要遠多于基于分詞、N元語法的方法。但當訓練集變動的情況下，基于分詞和N元語法都需要重新訓練，而基于后綴樹的分類方法只需要進行幾乎不占用時間的后綴樹增刪。對于測試語料中的單個文本，處理平均時間如表3所示：分類方法處理時間（s）訓練集固定的情況下訓練集變動的情況下基于分詞0.174N元語法0.1155基于后綴樹55表3 不同方法的文本分類處理平均時間在基于后綴樹的分類方法中，文本的預處理時間，即對所有文本的建后綴樹時間，與文本總長度成線性關(guān)系。向量化時間為O(N*L*M)，其中

29、，N為最大元項，L為要分類的文本長度，M為訓練集中文本個數(shù)。分類時間為O(m*L+logM)，即將向量轉(zhuǎn)換成兩個文檔之間的距離值，然后對M個距離值進行排序，取最接近的K個距離的時間。此外，在訓練集中添加或者刪除長度為N的文本，所需時間為0(N)。通過實驗對比和理論分析，我們認為基于后綴樹模型的文本分類系統(tǒng)適用于訓練集頻繁變動的情況，例如郵件過濾、實時網(wǎng)頁分類等。5 總結(jié)與展望本文提出了一種新的文本分類方法，在不需要特征提取和分詞的前提下，基于后綴樹模型對文本進行實時分類。其優(yōu)越性在于，預處理時間較短；實時生成向量，適合于訓練集需要經(jīng)常進行添刪的情況；沒有分詞過程，獨立于具體語種。但是，該系統(tǒng)的分類效果不是非常理想，特別是在每類文本數(shù)差別較大的情況下。而且，由于沒有經(jīng)過特征提取過程，所以噪音對最終結(jié)果產(chǎn)生了比較大的影響，這也是導致分類結(jié)果不理想的原因之一。我們將在該系統(tǒng)的基礎上進行改進，并繼續(xù)保留其不需要特征提取和分詞的優(yōu)勢。針對其不同于傳統(tǒng)分類方式的特征，重點對向量化過程和分類過程進行優(yōu)化。參 考 文 獻1 李曉黎，劉繼敏，史忠植：概念推理網(wǎng)機器在文本分類中的應用J. 計算機研究與發(fā)展,