基于改進(jìn)Rocchio算法的短文本自動分類研究

鄭秋生，翟琳琳

（中原工學(xué)院，鄭州450007）

隨著互聯(lián)網(wǎng)的快速普及和發(fā)展，人們的生活方式也在發(fā)生著變化，博客、論壇、微博、聚合新聞（RSS）等成為人們表達(dá)感情、傳播思想的主要渠道.短文本信息，通常是指文本篇幅較短、字?jǐn)?shù)不超過200個的文本，比如來自微博、即時通訊、新聞評論、貼吧等的信息，都可以歸結(jié)為短文本信息.近年來，短文本信息因其內(nèi)容長度較短、表達(dá)方式靈活而備受人們青睞.面對撲面而來的大量短文本，如何能夠快速分門別類，找到用戶所關(guān)注的信息和類別？這就使短文本的自動分類問題的研究顯得尤為重要.

目前，對長文本信息的自動分類研究很多，提出了多種分類算法，如K近鄰算法、樸素貝葉斯算法、決策樹算法、支持向量機(jī)算法等.但是，這些適用于長文本的自動分類算法在短文本信息分類的應(yīng)用中有一定的局限性.基于此，本文提出利用簡單向量距離算法（Rocchio）［1］來對短文本進(jìn)行分類，在實(shí)施分類過程中，改進(jìn)了訓(xùn)練集和分類算法，使得分類效果更好.

1 Rocchio算法描述

簡單向量距離法是一種基于向量空間模型的分類算法.該算法的分類思路十分簡單，根據(jù)算數(shù)平均為每類文本集生成一個代表該類的原型向量，然后在新文本到來時，確定新文本向量，計(jì)算該向量與每個類的原型向量的距離（相似度），最后判定文本屬于與文本距離最近的類.具體步驟如下：

（1）計(jì)算每類文本集的原型向量，計(jì)算方法為訓(xùn)練集中所有文本的算數(shù)平均.

（2）新文本到來后經(jīng)過預(yù)處理，然后將文本表示為特征向量.

（3）計(jì)算新文本特征向量與每個類原型向量的相似度.

（4）比較每個類原型向量與新文本向量的相似度，將文本分到相似度最大的那個類別中.

2 基于改進(jìn)Rocchio算法的文本分類

文本自動分類的過程通常包括文本預(yù)處理、文本特征表示、特征選取、建立模型并分類、模型評價.

2.1 文本預(yù)處理

預(yù)處理是進(jìn)行文本分類的必經(jīng)階段，主要是對訓(xùn)練集中的文本和新到來的文本進(jìn)行去除停用詞和稀有詞、過濾非法字符、進(jìn)行分詞等［2］工作.短文本信息內(nèi)容精煉，噪音相對較少，預(yù)處理過程主要是分詞.目前的分詞工具很多，這里采用中科院的ICTCLAS對文本進(jìn)行分詞和詞性標(biāo)注.

從詞性方面來說，對文本所屬類別影響最大的是名詞.因此，預(yù)處理過程中選擇保留所有的名詞，并將這些名詞作為文本的特征項(xiàng).這樣，訓(xùn)練集中已經(jīng)分好類別的文本集經(jīng)過預(yù)處理就形成了一部由若干個“小詞典”（每個類中的名詞組成的詞典）組成的“大詞典”（整個訓(xùn)練集中的名詞組成的詞典）.對于訓(xùn)練集，這里選擇搜狗實(shí)驗(yàn)室和復(fù)旦大學(xué)提供的長文本語料庫，這樣可以豐富、擴(kuò)充形成的“大詞典”，提高分類精度.

2.2 文本表示

文本表示模型有3種：布爾邏輯模型；向量空間模型（VSM）；概率模型.其中，向量空間模型使用最為廣泛.VSM的思想是將預(yù)處理后的文本D表示成一個向量V＝（T1，W1；T2，W2；T3，W3；…；Tn，Wn）.其中，T表示短文本中的特征項(xiàng)；W 表示特征項(xiàng)在文本中的權(quán)重值（特征項(xiàng)在文本中的重要程度），簡單記為V＝（W1，W2，W3，…，Wn）［3］.

目前廣泛使用的權(quán)重計(jì)算方法是TF－IDF.TF－IDF是一種統(tǒng)計(jì)方法，多用來評估某個字或者詞在一個文件集或語料庫中的某份文件中的重要程度.字或者詞的重要程度與它在文件中出現(xiàn)的頻率成正比，與它在文件集或語料庫中出現(xiàn)的頻率成反比［4］.TF－IDF公式表示為：

其中，Wik表示文本Di中第k個特征項(xiàng)的權(quán)重值；TFik表示特征項(xiàng)Tk在文本Di中出現(xiàn)的頻率；IDFik是反文檔頻率.TF－IDF公式經(jīng)過歸一化處理后表示為：

其中，N代表所有訓(xùn)練文本的數(shù)目；n代表訓(xùn)練文本中出現(xiàn)該特征項(xiàng)的文本數(shù)；m代表文本Di中特征項(xiàng)的數(shù)目.

本文采用的權(quán)重計(jì)算方法是將原有TF－IDF公式作了改進(jìn)，使其更適用于短文本信息的自動分類.改進(jìn)后TF－IDF公式表示為：

其中，Y和y分別表示第k個特征項(xiàng)在“大詞典”和“小詞典”中出現(xiàn)的次數(shù).

改進(jìn)后的TF－IDF公式經(jīng)過歸一化處理后表示為：

其中，m代表文本Di中特征項(xiàng)的數(shù)目.

2.3 特征選取

在對長文本分類過程中，通常采用文本頻率（DF）、信息增益（IG）、x2統(tǒng)計(jì)量、互信息（MI）等方法進(jìn)行特征提取，這樣既可以降低文本向量空間維度，還能提高分類效率和精度［5］.短文本內(nèi)容短小，文本表示成向量后的維數(shù)也不高，并且預(yù)處理中留下的名詞就能夠代表文本的類別特征，所以將文本中的名詞都作為特征項(xiàng)，這也是本文中特征選取方法的特別之處.文本表示成向量的維數(shù)沒有一定的限制，可以根據(jù)實(shí)驗(yàn)結(jié)果做適當(dāng)?shù)恼{(diào)整.

2.4 建立模型并分類

建立分類模型是實(shí)施文本分類的核心部分.分類模型主要由分類方法來完成.一般將分類方法劃分為訓(xùn)練和分類2個子過程.訓(xùn)練是通過對訓(xùn)練集進(jìn)行學(xué)習(xí)，建立分類器，然后使用該分類器對新到來的短文本信息進(jìn)行分類［6］.訓(xùn)練集的大小和質(zhì)量對分類的結(jié)果有很大的影響.考慮到短文本內(nèi)容較短、字?jǐn)?shù)較少等原因，本文使用的訓(xùn)練集中的文本全是長文本，這樣既可以豐富詞典，還可以提高分類器的準(zhǔn)確度.

在Rocchio算法基礎(chǔ)上，本文對訓(xùn)練集中每個類別的原型向量的計(jì)算方法做了改進(jìn)，改進(jìn)后計(jì)算方法如公式（5）所示.

對于訓(xùn)練集中的文本類別C，其原型向量中第k項(xiàng)特征的權(quán)重Vk定義如下：

其中，Vk是文本類別C的原型向量中第k項(xiàng)的權(quán)重值；｜Rc｜是文本類別C中的總文本數(shù)；i是文本類別C中的文本序號；Wik是第i個文本中第k項(xiàng)特征的權(quán)重值.從公式（5）中可以看出，原型向量就是文本類別C中所有訓(xùn)練文本對應(yīng)的特征項(xiàng)權(quán)重的平均值.

對于新到來的短文本信息，將其表示成向量后，本文采用計(jì)算新文本向量與每個原型向量夾角的cosine值來度量兩者的相似度sim（di，dj），其公式表示為：

其中，v（di）表示新到來的短文本向量；v（dj）表示原型向量；h是短文本向量的維數(shù).計(jì)算得出的相似度值越大，表示新文本與該類別越相似；反之，兩者的差距越大.根據(jù)公式（6）計(jì)算新到來的短文本與訓(xùn)練集中所有類別的原型向量的相似度，最終將新文本歸入相似度值最大的類別中.

2.5 模型評價

模型評價主要考慮分類結(jié)果的效率和準(zhǔn)確度兩方面［7］.目前真正適用于短文本信息分類的模型不多，并且每種模型都不完美，都有一定的局限性；這就需要不斷地實(shí)驗(yàn)，并在實(shí)驗(yàn)過程中做適當(dāng)調(diào)整和改進(jìn)，盡量使效率和準(zhǔn)確度都有所提高.

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)中采用的2個語料庫分別來自搜狗實(shí)驗(yàn)室和復(fù)旦大學(xué).搜狗實(shí)驗(yàn)室提供的語料庫中共有9個類別，其中每個類別有訓(xùn)練文本1 999篇［8］；復(fù)旦大學(xué)語料庫提供的語料庫中共有20個類別，去除部分重復(fù)文本和損壞文本后，有訓(xùn)練文本8 214篇［9］.這里從2個語料庫中選取6個文本類別進(jìn)行實(shí)驗(yàn)，如表1所示.測試文本選用從互聯(lián)網(wǎng)上搜取的短文本信息，共計(jì)1 336篇，如表2所示.

表1 訓(xùn)練語料庫情況篇

表2 測試文本集情況篇

采用3個通用的評價指標(biāo)對分類結(jié)果進(jìn)行評價：準(zhǔn)確率P、召回率R 和平均F1值［10－11］.

準(zhǔn)確率P＝c／a＊100%召回率R＝c／r＊100%

其中，c是正確分到某類的文本數(shù)；a是實(shí)際分到某類的文本數(shù)；r是應(yīng)分到某類的文本數(shù).

其中，｜C｜是訓(xùn)練集中類別的數(shù)目；b是訓(xùn)練集中的某個類別；Pb和Rb分別表示某個類別的準(zhǔn)確率和召回率.

采用改進(jìn)的Rocchio算法實(shí)現(xiàn)短文本的分類，并與改進(jìn)之前進(jìn)行對比，比較結(jié)果如表3所示.

表3 兩種分類算法在不同語料庫中的比較

根據(jù)F1值的計(jì)算方法，可以得到各個類別的F1值，結(jié)果對比如圖1所示.

圖1 兩種分類方法的F1值對比圖

從表3和圖1可以看出，改進(jìn)后的Rocchio算法的平均F1值整體上要高于改進(jìn)前的算法.

4 結(jié) 語

本文采用大量長文本作為訓(xùn)練集，以此形成詞典，并對傳統(tǒng)Rocchio算法中的特征項(xiàng)權(quán)重計(jì)算公式（TF－IDF）做了改進(jìn)，最后利用改進(jìn)的Rocchio算法對短文本信息進(jìn)行分類.實(shí)驗(yàn)結(jié)果表明，改進(jìn)的Rocchio算法分類效果較好.

［1］王治和，楊延?jì)?對簡單向量距離文本分類算法的改進(jìn)［J］.計(jì)算機(jī)科學(xué)，2009，36（1）：236－238.

［2］張愛華，荊繼武，向繼.中文文本分類中的文本表示因素比較［J］.中國科學(xué)院研究生院學(xué)報，2009，26（3）：401－403.

［3］郭慶琳，李艷梅，唐琦.基于 VSM 的文本相似度計(jì)算的研究［J］.計(jì)算機(jī)應(yīng)用研究，2008，25（11）：3257－3258.

［4］施聰鶯，徐朝軍，楊曉江.TFIDF算法研究綜述［J］.計(jì)算機(jī)應(yīng)用，2009，29（6）：168－170.

［5］Salton G，Wong A，Yang C S.A Vector Space Model for Automatic Indexing［J］.Communications of ACM，1975，18（11）：613－620.

［6］David D Lewis.Feature Selection and Feature Extraction for Text Categorization ［C］／／Proceedings of Speech and Natural Language Workshop.Morgan Kaufmann：Defense Advanced Research Projects Agency，l992：212－217.

［7］Yang Yiming.An Evaluation of Statistical Approaches to Text Categorization［J］.Information Retrieval，1999，1（2）：69－90.

［8］Jasper’s Java Jacal.關(guān)于復(fù)旦大學(xué)自然語言處理實(shí)驗(yàn)室基準(zhǔn)資料［EB／OL］.（2008－06－21）.http：／／www.sogou.com／labs／dl／c.html.

［9］Jasper’s Java Jaca.文本分類技術(shù)［EB／OL］.［2012－11－02］.http：／／www.nlp.org.cn／docs／doclist.php？cat＿id＝16＆type＝15.

［10］Zelikovitz S，Marquez F.Transductive Learning for Short Text Classification Problems Using Latent Semantic Indexing［J］.International Journal of Pattern Recognition and Artificial Intelligence，2005，19（2）：143－163.

［11］Fabrizio Sebastiani.Machine Learning in Automated Text Categorization［J］.ACM Computing Surveys，2002，19（5）：1－34.