陳可華

（寧德師范學(xué)院 計算機與信息工程系，福建 寧德 352100）

文本自動分類新探究

陳可華

（寧德師范學(xué)院 計算機與信息工程系，福建 寧德 352100）

文本自動分類是一種有效的組織信息和管理信息的工具.傳統(tǒng)分類方法一般在分類效果和運行效率兩者上不可兼得.通過綜合 Rocchio 和 KNN 兩種分類方法的優(yōu)點，設(shè)計了一種基于多代表點的文本分類方法，該方法通過對各類挖掘出多個有效的代表點(真實或虛擬的)，再使用基于這些代表點的 Rocchio 和 KNN 方法進行分類.實驗表明，該方法以較少的訓(xùn)練時間達到令人滿意的分類效果，并且能很好解決不平衡類問題，實驗結(jié)果顯示該方法能達到與 SVM 相當(dāng)?shù)姆诸愋Ч?

文本分類；多代表點；Rocchio；KNN

1 介紹

隨著因特網(wǎng)等信息技術(shù)的發(fā)展，各類信息資源的增長都呈現(xiàn)海量特征，而其中文本數(shù)據(jù)始終占據(jù)重要地位.如何有效地組織、管理和使用這些文本信息成為當(dāng)前的迫切需求,這促進了文本自動分類技術(shù)的迅速發(fā)展和廣泛應(yīng)用[1,2,4].

近年來，隨著如垃圾郵件過濾[3]等需求的激勵，基于機器學(xué)習(xí)的文本自動分類技術(shù)的研究取得了很大的進展，提出 了 很 多 有 效 的 分 類 模 型[4]， 如 基 于 類 中 心 的 方 法 ，N a ?v e B a y e s算法，支持向量機 S V M，K N N，神經(jīng)網(wǎng)絡(luò)，決策樹，B o o s t i n g等.

在這些分類方法中，基于類中心的 R o c c h i o方法由于其簡單快速而得到了廣泛的應(yīng)用，但是該方法的精度常常不能令人滿意，其只適用于各個類之間差異比較明顯的簡單分類問題，而對于較復(fù)雜的情況，特別是遇到不平衡類問題時它的分類結(jié)果通常要相對差一些；K N N(k近鄰)也是一個常用的分類算法，并且在許多領(lǐng)域(簡單情況和復(fù)雜情況)都顯示出良好的性能，但是該方法是一種懶惰的方法，它不用經(jīng)過任何的訓(xùn)練學(xué)習(xí)過程，只是在分類時在所有實例中選擇最相近的k的實例，再根據(jù)這k個實例的類分布選擇最可能的若干的類別作為目標(biāo)類別，所以該方法的一個致命弱點就是它分類時的計算量較大：當(dāng)它為一個未見實例分類時，它通常要遍歷訓(xùn)練實例空間以找到查詢實例的k個最近的鄰居.而其他大多數(shù)分類算法如決策樹等都因為計算復(fù)雜度太高而不適用于大規(guī)模的場合，而且當(dāng)訓(xùn)練樣本集增大時，都需要重新生成分類器，因而可擴展性差.

為了解決上述問題，提高分類效率但又不丟失分類的精度，需要研究新的分類算法.該工作不論在科學(xué)研究還是實際應(yīng)用中都有重要的意義.本文通過對文本分類的研究，結(jié)合基于類中心和 K N N的優(yōu)點，提出了一種新的簡單有效的文本分類方法，通過給各類提取多個代表點，這些代表點可能是實際存在的文本也可能是虛擬的類中心，然后基于這些代表點對待分類文檔使用 R o c c h i o和 K N N等方法進行分類.從而能夠利用較少的時間獲得較高的分類精度并且能很好的解決不平衡類分類問題.

2 基于多代表點的文本分類模型

2.1 文本分類模型

R o c c h i o算法來源于向量空間模型理論，在向量空間法中，每個文檔被看成一個詞袋，然后被表示成詞項權(quán)重的向量：di=(wi,1,wi,2,……,wi,n)，其中 di表示文檔，n表示詞項空間的維數(shù)，wi,k表示文檔詞項 k在文檔 i中的權(quán)重，該權(quán)重表示該詞項 在文 檔中 的重要 程度 ，通常 使用 t f-i d f方法 或者 其 他 權(quán)重表示方法.兩文檔的相似度可使用對應(yīng)文檔向量的余弦夾角 計 算（也 可 用 其 他 方 法 如 歐 氏 距 離 等）.首先訓(xùn)練分類模型時，每個類使用一 個中 心向 量(C e n t r o i d)代 表,然后在 分類 時通 過檢查 待 分類文檔和這些中心向量的相似度，把它分到最相似的中心向量所代表的類中.令表示預(yù)定義的類別 集合，每個類中包含所屬該類的文檔集合.

K N N是一種懶散的方法，即它沒有學(xué)習(xí)過程，只是存放所有的訓(xùn)練例直到接到未知文本的時候才建立分類.對于每個待分類文檔，首先計算其于訓(xùn)練集中所有文檔的相似度，然后按照相似度從大到小選擇前 K的文檔(k近鄰)，最后返回包含這 k個文檔中最多的類標(biāo)簽.令表示預(yù)定義的類別集合，每個類中包含所屬該類的文檔集合，l(d)表示文檔d的類標(biāo)簽.

2.2 基于多代表點的文本分類模型

第二種方法類似于 K N N方法，不過此時待分類文檔不是與訓(xùn)練實例表中的文檔進行相似度計算，而是與所有代表點進行計算，其他過程與 K N N類似，此處不累述.

2.3 多代表點挖掘方法

對類代表點的挖掘是本文所提出方法非常重要的一個步驟，我們使用兩種方法進行代表點的挖掘，一種是基于聚類的方式，另一種是基于文檔密度的方式.基于聚類的方式首先對每個類別都進行聚類，聚成若干個簇，使用簇中心作為類的代表點，我們使用 K-M e a n s[4]算法進行文檔聚類；基于文檔密度的方式認(rèn)為類中密度大的文檔能代表該類的大部分性質(zhì)，首先計算類中任意文檔間的余弦相似度，然后通過如下公式計算每個文檔的度其中 #C(di)表示文檔 di所屬類別的文檔數(shù)，最后返回度值較大的若干篇文檔為該類的代表點.

3 實驗與分析

3.1 文本分類數(shù)據(jù)集

現(xiàn)在用兩個數(shù)據(jù)集上驗證我們模型的效果，中文數(shù)據(jù)集選用復(fù)旦文本分類語料庫①，英文數(shù)據(jù)集選用 2 0-N e w sg r o u p s②.其中 2 0-N e w s g r o u p s共有 2 0個類別，各類別文本數(shù)大致相等，每個類別約有 1 0 0 0篇左右的文檔，我們隨機選擇若干篇文本為訓(xùn)練集，保持訓(xùn)練集與測試集比例約為 7:3.復(fù)旦文本分類語料庫提供者已分好訓(xùn)練集和測試集.我們使用所提供的訓(xùn)練集進行訓(xùn)練分類模型，其類別總數(shù)也是 2 0，各類文檔數(shù)目不等(每類文檔數(shù)從 2 5到 1 6 0 0)，是個不均衡類問題，并使用測試集驗證模型.實驗中使用中科院分詞軟件 I C T C L A S③對中文文本做分詞處理，英文詞項使用 P o r t e r算法進行詞干化處理，中英文文本同樣去除停用詞.使用L T C權(quán)重公式計算詞項的權(quán)重，D F作為特征選擇方法，刪除 D F小于 3的詞項.

3.2 評價指標(biāo)

準(zhǔn)確率和召回率是評價分類性能的兩種常用的指標(biāo).對于給定的某個類別，令a表示被正確分到該類的實例的個數(shù)，b表示被誤分到該類的實例的個數(shù)，c表示屬于該類但被誤分到其它類別的實例的個數(shù)，則準(zhǔn)確率(p)和召回率(r)分別被定義為：r=a/(a+c)，p=a/(a+b).一般使用 F-指標(biāo)平衡準(zhǔn)備率和召回率，其定義為

其中參數(shù) β 用來為準(zhǔn)確率(p)和召回率(r)賦予不同的權(quán)重.

為了評估算是每一個類的性能指標(biāo)的算術(shù)平均值，而微平均是每一個實例(文檔)的性能指標(biāo)的算術(shù)平法在整個數(shù)據(jù)集上的性能，一般使用兩種平均的方法，分別稱為宏平均和微平均.宏平均均.對于單個實例而言，它的準(zhǔn)確率和召回率是相同的(要么都是 1，要么都是 0).因此準(zhǔn)確率和召回率的微平均是相同的，對于同一個數(shù)據(jù)集的準(zhǔn)確率、召回率和 F 1的微平均指標(biāo)是相同的.

3.3 實驗設(shè)計及時間復(fù)雜度分析

我們使用 T R表示 2.2節(jié)中方法一的分類方法，T K表示方法二的分類方法，并且在代表點挖掘方法上我們分別用 K M 和 D B表 示 K-M e a n s和基 于密 度 (D e n s i t y B a s e d)兩種不同方法，所以通過組合我們有四種不同的分類方法，分別 用 T R+K M,T R+D B,T K+K M 和 T K+D B表 示 .我 們 使 用R o c c h i o，K N N，l i b S V M[6]作為基準(zhǔn)模型進行比較.

在訓(xùn)練階段，基于 K-M e a n s聚類算法的時間復(fù)雜度為O(I k n)，其中 I為迭代次數(shù)，k為聚成的簇數(shù)目，n為該類中文檔總數(shù)，一般來說 K-M e a n s能很快達到收斂狀態(tài).基于密度的方法的時間開銷主要用于計算文檔間相似度和選擇度最大的 k個文檔其時間復(fù)雜度大約為 O(n2+k n).在分類階段，方法一和方法二的時間復(fù)雜度都正比于代表點個數(shù).幾個算法的時間復(fù)雜度比較可見表 1，m表示類數(shù)，k表示每類的代筆點數(shù)，N表示訓(xùn)練集中文檔總數(shù)，一般 k*m遠(yuǎn)小于 N.

表1 三種算法的時間復(fù)雜度比較

3.4 參數(shù)選擇

該方法一個重要的步驟就是確定每個類的代表點，代表點個數(shù)的不同將會對分類結(jié)果產(chǎn)生很大的影響.下面分別通過實驗說明如何選擇以使結(jié)果更優(yōu)，為了簡化過程，我們設(shè)每個類別的代表點個數(shù)相同，下一小節(jié)的實驗也表明這樣的設(shè)置(各類擁有相同的代表點數(shù))使得該方法能很好的解決不平衡類問題.我們分別驗證代表點個數(shù)從 2到 1 0對分類結(jié)果的影響，由于方法 T K還有參數(shù) k需要調(diào)整則此處省略.實驗數(shù)據(jù)隨機選擇 2 0-N e w s g r o u p s中的 3類和 4類，限 于 篇 幅 只 給 出 3類 數(shù) 據(jù) (分 別 是 h a r d w a r e,f o r s a l e和m i d e a s t)的準(zhǔn)確率結(jié)果.

圖1 不同代表點個數(shù)對應(yīng)的分類準(zhǔn)確率

從圖1可看出，每類5個代表點分類結(jié)果即達到很好效果，并且隨著代表點個數(shù)的增加分類準(zhǔn)確率不增反而有稍許遞減，我們認(rèn)為5個左右的代表點就能夠很好的表示該類的性質(zhì)，過多反而會帶來噪音.并且可以看到基于虛擬代表點的 K M方法效果大大好于基于真實代表點的 D B方法，這是因為 D B方法在選擇代表點后就丟失了該類其他文檔的信息，而 K M是通過綜合簇中所有點形成質(zhì)心所以不會丟失過多關(guān)鍵信息.

3.5 結(jié)果及分析

我們使用 K M方法挖掘代表點并設(shè)置每類代表點個數(shù)為 5，對于 T K方法我們分別選擇了 k為 3和 5，并設(shè)置基準(zhǔn)模 型 K N N中 k分別為 5、1 5和 3 0，l i b S V M 所 有 參 數(shù) 為 默 認(rèn)值.表 2和表 3分別為這些方法在 2 0 N e w s g r o u p s和復(fù)旦數(shù)據(jù)集上的分類結(jié)果.從分類結(jié)果可以看出該方法能表現(xiàn)出很好的性能.對于兩種分類方法 T R和 T K，我們發(fā)現(xiàn)還是基于 K N N的改進方法(T K)效果更好，這也從另一方面說明了K N N方法比 R o c c h i o方法在分類效果上更好.由于每類只有5個代表點(共 5*2 0個代表點)，對于 T K方法的 k值我們分別選擇了 3和 5，我們認(rèn)為讓 k過大對分類效果不會有太大提高，反而會因為代表點的增加給分類器帶來更多干擾因素.另外，從宏平均(大小類對宏平均貢獻相同)結(jié)果可以看出，對于平衡類問題(2 0 N e w s g r o u p s)，我們所提出方法最好表現(xiàn)與 S V M相當(dāng)；而對于不平衡類問題(復(fù)旦數(shù)據(jù)集)，我們的方法表現(xiàn)更優(yōu)，我們認(rèn)為原因是傳統(tǒng)方法在遇到不平衡類問題時會偏向大類別使得分類效果會急劇下降，而我們的方法通過對各個類提取相同數(shù)量的代表點，消除了大類會淹沒小類的可能.

表 2 算法在 2 0 N e w s g r o u p s上的分類結(jié)果

表3 算法在復(fù)旦數(shù)據(jù)集上的分類結(jié)果

4 總結(jié)與展望

本文通過對文本自動分類技術(shù)的研究，結(jié)合基于 R o cc h i o方法和 K N N方法的優(yōu)點，提出了一種新的簡單有效的文本分類方法，通過基于聚類和基于密度兩種方法提取類的多個代表點，這些代表點可能是實際存在的文本也可能是虛擬的類中心，然后對這些代表點使用 R o c c h i o和 K N N的方法進行分類.從而能夠利用較少的時間獲得較高的分類精度并且能很好地解決不平衡類的分類問題.

該方法一個重要的步驟就是代表點的挖掘，本文使用了兩種基本的挖掘方法.近年來，概率主題模型得到了廣泛的研究和應(yīng)用，我們將考慮使用更精確的概率主題模型挖掘文檔集中的主題信息，如 L D A[7].并且在 K M方法中我們設(shè)置各代表點權(quán)重相同，這也是我們需要加以改進的地方，不僅應(yīng)該找到類中很好的代表點，還應(yīng)該刻畫該代表的代表性，對該類性質(zhì)描述的貢獻程度等.

注 釋：

① http://www.nlp.org.cn/docs/download.php?doc_id =294 http://www.nlp.org.cn/docs/download.php?doc_id=295

② http://www.cs.cmu.edu/afs/cs/project/theo -11/www/ naive-bayes/20_newsgroups.tar.gz

③http://ictclas.org/

〔1〕Sebastiani F.Machine learning in automated text categorization[J].ACM Computing Surveys,2002,34(1):1-47.

〔2〕蘇金樹,張博鋒,徐昕.基于機器學(xué)習(xí)的文本 分類技術(shù)研 究進展[J].軟件學(xué)報，2006，17(9):1848-1859.

〔3〕詹川.反垃圾郵件技術(shù)的研究[D].電子科技大學(xué)計算機 系統(tǒng)結(jié)構(gòu)系博士畢業(yè)論文,2005：1-3.

〔4〕范明，范宏建.數(shù)據(jù)挖掘?qū)д揫M].北京:人民郵電出版社，2006.

〔5〕石志偉，劉濤，吳功宜.一種快速高效的文本分類方法[J].計算機工程與應(yīng)用,2005,41(29):180-183.

〔6〕Chih-Chung Chang and Chih-Jen Lin,LIBSVM:a library for support vector machines,2001.Software available at http://www.csie.ntu.edu.tw/～cjlin/libsvm.

〔7〕Blei,D.M.,Ng,A.Y.,&Jordan,M.I.(2003).Latent Dirichlet Allocation.Journal of Machine Learning Research,3,993-1022.

T P 3 9 1

A

1673-260X（2011）04-0034-03

福建省教育廳 B 類科研項目(JB09235);寧德師范學(xué)院科研資助項目(2009303)