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

2、證訓(xùn)練集中文本的更改，對(duì)分類結(jié)果產(chǎn)生實(shí)時(shí)影響。實(shí)驗(yàn)結(jié)果和算法分析表明，我們系統(tǒng)的文本預(yù)處理的時(shí)間復(fù)雜度為O(N)，遠(yuǎn)遠(yuǎn)優(yōu)于分詞系統(tǒng)的預(yù)處理時(shí)間復(fù)雜度。此外，由于不需要分詞和特征抽取，分類過(guò)程與具體語(yǔ)種無(wú)關(guān)，所以是一種獨(dú)立語(yǔ)種的分類方法。關(guān)鍵詞:實(shí)時(shí)文本分類；向量空間模型；后綴樹中圖法分類號(hào):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應(yīng)用的普及，人們已經(jīng)從信息缺乏的時(shí)代過(guò)渡到信息極為豐富的時(shí)代。如何從大量信息中迅速有效地提取出所需信息也就成為一項(xiàng)重要的研究課題。由于分類可以在較大程度上解決目前網(wǎng)絡(luò)信息雜亂的現(xiàn)象，方便用戶準(zhǔn)確定位所需信息，因此分類尤其是文本分類的研究日益重要1。文本分類是指在給定分類體系下，根據(jù)文本的內(nèi)容自動(dòng)確定文本類別的過(guò)程。通常來(lái)說(shuō)，文本分類是面向自然語(yǔ)言處理的。在這種分類中分類的正確性遠(yuǎn)比分類的速度更重要。但是在網(wǎng)絡(luò)內(nèi)容分析中，我們認(rèn)為分類

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

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

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

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

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

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

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

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

15、串的個(gè)數(shù)為(L-N+1)個(gè)。在2.2.1節(jié)中我們已經(jīng)將文檔Di表示為后綴樹Ti，令測(cè)試文本為D，對(duì)于文本中任意位置k，在樹Ti中查找從k開始的1元到N元子串的出現(xiàn)頻率，記錄在ac1，ac2，acN中。然后，利用公式得到位置K的對(duì)應(yīng)值。其中p是字符串長(zhǎng)度權(quán)重因子。為了強(qiáng)調(diào)相匹配字符串長(zhǎng)度越大，文本之間的相似度越高，一般取p大于6。例如，設(shè)文檔Di=“abcaba$”，N=2，測(cè)試文本D=“abc”,對(duì)于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。通過(guò)上述步驟，后綴樹Ti就轉(zhuǎn)換為長(zhǎng)度為（LN+1）的向量tf(0,Di) tf(1, Di) tf(L-N, Di)。2.2.3 權(quán)重計(jì)算算法在2.2.2節(jié)中，我們以測(cè)試文本為基準(zhǔn)，得到了文檔Di的初始向量tf(0,Di) tf(1, Di) tf(L-N, Di)，對(duì)文本向量化面臨著怎樣計(jì)算權(quán)重，即向量各個(gè)分量的值的問(wèn)題。給每個(gè)項(xiàng)賦權(quán)重時(shí)，應(yīng)使得文本中越重要的項(xiàng)權(quán)重越大4。在我們的系統(tǒng)中采用歸一化的tf-idf公式計(jì)算權(quán)重，即TFC權(quán)重，但計(jì)算idf值稍有不同，公式如下：其中，w(t,Di) 為位置t開始的多元組（1元到N元子串）在文本 Di 中的權(quán)重， M 為

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

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

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

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

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

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

23、別的文本數(shù)占總文本的百分比。處理性能則指在訓(xùn)練集固定或者變動(dòng)情況下，分類系統(tǒng)處理一個(gè)文本所需的平均時(shí)間。4.2 準(zhǔn)確率測(cè)試下面是我們的測(cè)試結(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平均準(zhǔn)確率67.69%73.36%76.21%表1 基于后綴樹模型的分類系統(tǒng)的測(cè)試結(jié)果及統(tǒng)計(jì)結(jié)果測(cè)試結(jié)果顯示，文本數(shù)較多的類結(jié)果比較好，因?yàn)閺母怕实慕嵌葋?lái)說(shuō)，文本數(shù)多的類別入選

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

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

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

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