陳可華

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

文本自動(dòng)分類新探究

陳可華

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

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

文本分類；多代表點(diǎn)；Rocchio；KNN

1 介紹

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

近年來，隨著如垃圾郵件過濾[3]等需求的激勵(lì)，基于機(jī)器學(xué)習(xí)的文本自動(dòng)分類技術(shù)的研究取得了很大的進(jìn)展，提出 了 很 多 有 效 的 分 類 模 型[4]， 如 基 于 類 中 心 的 方 法 ，N a ?v e B a y e s算法，支持向量機(jī) 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)用，但是該方法的精度常常不能令人滿意，其只適用于各個(gè)類之間差異比較明顯的簡單分類問題，而對(duì)于較復(fù)雜的情況，特別是遇到不平衡類問題時(shí)它的分類結(jié)果通常要相對(duì)差一些；K N N(k近鄰)也是一個(gè)常用的分類算法，并且在許多領(lǐng)域(簡單情況和復(fù)雜情況)都顯示出良好的性能，但是該方法是一種懶惰的方法，它不用經(jīng)過任何的訓(xùn)練學(xué)習(xí)過程，只是在分類時(shí)在所有實(shí)例中選擇最相近的k的實(shí)例，再根據(jù)這k個(gè)實(shí)例的類分布選擇最可能的若干的類別作為目標(biāo)類別，所以該方法的一個(gè)致命弱點(diǎn)就是它分類時(shí)的計(jì)算量較大：當(dāng)它為一個(gè)未見實(shí)例分類時(shí)，它通常要遍歷訓(xùn)練實(shí)例空間以找到查詢實(shí)例的k個(gè)最近的鄰居.而其他大多數(shù)分類算法如決策樹等都因?yàn)橛?jì)算復(fù)雜度太高而不適用于大規(guī)模的場合，而且當(dāng)訓(xùn)練樣本集增大時(shí)，都需要重新生成分類器，因而可擴(kuò)展性差.

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

2 基于多代表點(diǎn)的文本分類模型

2.1 文本分類模型

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

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

2.2 基于多代表點(diǎn)的文本分類模型

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

2.3 多代表點(diǎn)挖掘方法

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

3 實(shí)驗(yàn)與分析

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

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

3.2 評(píng)價(jià)指標(biāo)

準(zhǔn)確率和召回率是評(píng)價(jià)分類性能的兩種常用的指標(biāo).對(duì)于給定的某個(gè)類別，令a表示被正確分到該類的實(shí)例的個(gè)數(shù)，b表示被誤分到該類的實(shí)例的個(gè)數(shù)，c表示屬于該類但被誤分到其它類別的實(shí)例的個(gè)數(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)重.

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

3.3 實(shí)驗(yàn)設(shè)計(jì)及時(shí)間復(fù)雜度分析

我們使用 T R表示 2.2節(jié)中方法一的分類方法，T K表示方法二的分類方法，并且在代表點(diǎn)挖掘方法上我們分別用 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)模型進(jìn)行比較.

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

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

3.4 參數(shù)選擇

該方法一個(gè)重要的步驟就是確定每個(gè)類的代表點(diǎn)，代表點(diǎn)個(gè)數(shù)的不同將會(huì)對(duì)分類結(jié)果產(chǎn)生很大的影響.下面分別通過實(shí)驗(yàn)說明如何選擇以使結(jié)果更優(yōu)，為了簡化過程，我們?cè)O(shè)每個(gè)類別的代表點(diǎn)個(gè)數(shù)相同，下一小節(jié)的實(shí)驗(yàn)也表明這樣的設(shè)置(各類擁有相同的代表點(diǎn)數(shù))使得該方法能很好的解決不平衡類問題.我們分別驗(yàn)證代表點(diǎn)個(gè)數(shù)從 2到 1 0對(duì)分類結(jié)果的影響，由于方法 T K還有參數(shù) k需要調(diào)整則此處省略.實(shí)驗(yàn)數(shù)據(jù)隨機(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 不同代表點(diǎn)個(gè)數(shù)對(duì)應(yīng)的分類準(zhǔn)確率

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

3.5 結(jié)果及分析

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

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

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

4 總結(jié)與展望

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

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

注 釋：

① 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〕蘇金樹,張博鋒,徐昕.基于機(jī)器學(xué)習(xí)的文本 分類技術(shù)研 究進(jìn)展[J].軟件學(xué)報(bào)，2006，17(9):1848-1859.

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

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

〔5〕石志偉，劉濤，吳功宜.一種快速高效的文本分類方法[J].計(jì)算機(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 類科研項(xiàng)目(JB09235);寧德師范學(xué)院科研資助項(xiàng)目(2009303)