邸 鵬 段利國(guó)

（太原理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原，030024）

引 言

自動(dòng)文本分類是自然語言處理領(lǐng)域中的一個(gè)研究熱點(diǎn)，其研究目的是借助自動(dòng)分類技術(shù)判斷文本的類別。數(shù)量急劇增長(zhǎng)的網(wǎng)絡(luò)文本成為人們獲取信息的主要來源，借助文本分類技術(shù)，可以更加快捷、準(zhǔn)確地獲取用戶需要的信息。此外，文本分類技術(shù)在電子政務(wù)、垃圾郵件過濾、文本情感分析、網(wǎng)絡(luò)輿情監(jiān)控等領(lǐng)域都有著廣泛的應(yīng)用。［1］

在英文文本分類方面，Dublin大學(xué)Finn等人［2］研究主客觀句分類，得出基于詞性標(biāo)注的特征選擇方法比詞袋效果好。Columbia大學(xué)Yu等人［3］對(duì)新聞這類主要講“事實(shí)”的文本進(jìn)行主客觀句子識(shí)別，利用SimFinder工具計(jì)算句子相似度，構(gòu)造訓(xùn)練集，結(jié)合各類詞性信息構(gòu)建貝葉斯分類器，提出多分類器的構(gòu)建以解決訓(xùn)練集構(gòu)造的不確定性和訓(xùn)練集質(zhì)量的問題。Cornell大學(xué)Pang等人［4］利用屬性相同的句子位置分布較近的特點(diǎn)，將候選句子構(gòu)成一幅圖，從而將主客觀句分類轉(zhuǎn)化為求圖的最小割問題，實(shí)現(xiàn)Cut-based分類器，對(duì)主客觀句進(jìn)行分類識(shí)別。

在中文文本分類方面，文獻(xiàn)［5］提出了一種K近鄰元分析分類算法，該算法利用NCA算法對(duì)訓(xùn)練集進(jìn)行距離測(cè)度學(xué)習(xí)和降維，使用了K近鄰方法，通過測(cè)試集的類條件概率進(jìn)行類別判定，取得了很好的分類效果。文獻(xiàn)［6］提出了一種基于屬性頻率的樸素貝葉斯算法，該方法放松了屬性之間相互獨(dú)立的假設(shè)條件，利用RoughSet可辨識(shí)矩陣，對(duì)不同屬性賦予不同權(quán)值，在最后的實(shí)驗(yàn)中取得了良好的分類效果。文獻(xiàn)［7］提出了一種歸一化向量的分類算法，將單個(gè)類別中的詞頻及文檔頻率用到矩陣投影運(yùn)算中去，將文本特征的三維空間投影到二維空間上，有效地降低了特征空間維數(shù)，提高了分類效率。

綜合分析現(xiàn)有研究成果，沒有文獻(xiàn)對(duì)先驗(yàn)概率的計(jì)算進(jìn)行改進(jìn)，對(duì)貝葉斯算法的研究也普遍是為了提高分類的準(zhǔn)確率，而很少考慮分類的時(shí)間，并且在后驗(yàn)概率的計(jì)算中存在的一個(gè)小誤差沒能被很好地改進(jìn)。因此，本文對(duì)傳統(tǒng)的貝葉斯算法進(jìn)行改進(jìn)，提出了一種新的文本分類算法。

1 貝葉斯相關(guān)理論

用于文本分類的機(jī)器學(xué)習(xí)算法主要有SVM，Bayes，KNN，LLSF和決策樹等。其中，樸素貝葉斯算法是一種以貝葉斯相關(guān)理論為基礎(chǔ)的最常用的方法，它以屬性之間的相互獨(dú)立性為前提，當(dāng)該前提成立時(shí)，與其他分類算法相比，樸素貝葉斯算法的準(zhǔn)確率往往最高［8］。而在樸素貝葉斯算法中經(jīng)常會(huì)用到全概率公式以及貝葉斯公式。

1.1 全概率公式

設(shè)A，B是隨機(jī)試驗(yàn)的兩個(gè)隨機(jī)事件，事件B發(fā)生的概率P（B）＞0，則稱

為在事件B發(fā)生的條件下，事件A發(fā)生的條件概率［9］。

全概率公式的定義如下：設(shè)隨機(jī)試驗(yàn)E的樣本空間為Ω，A為E的一個(gè)事件，B1，B2，…，Bn是對(duì)空間Ω的一個(gè)有限劃分，且P（Bi）＞0（i＝1，2，…，n），則

稱為全概率公式［9］。也可以通俗的理解為：事件A發(fā)生有B1，B2，…，Bn這n種方法，將每一種方法下事件A發(fā)生的概率相加，就可得到事件A發(fā)生的概率。

1.2 貝葉斯公式

設(shè)隨機(jī)試驗(yàn)E的樣本空間為Ω，A為E的事件，B1，B2，…，Bn為Ω的一個(gè)劃分，則

稱為貝葉斯公式［9］。

1.3 樸素貝葉斯算法

在樸素貝葉斯算法中會(huì)用到先驗(yàn)概率，它是指一個(gè)假設(shè)能夠成立的背景知識(shí)。在本文中，某個(gè)假設(shè)h在未進(jìn)行訓(xùn)練之前的初始概率用P（h）表示，即假設(shè)h的先驗(yàn)概率。在實(shí)際處理中，當(dāng)沒有先驗(yàn)概率時(shí)，可以為每一種假設(shè)賦予一個(gè)相同的先驗(yàn)概率。同理，用P（D）表示訓(xùn)練樣本數(shù)據(jù)D的先驗(yàn)概率。對(duì)于P（D/h），它表示當(dāng)假設(shè)h成立時(shí)觀察到數(shù)據(jù)D的條件概率。在機(jī)器學(xué)習(xí)中，通常需要研究的是P（h/D），即給定一個(gè)訓(xùn)練樣本數(shù)據(jù)D之后，判斷在數(shù)據(jù)D的基礎(chǔ)上假設(shè)h成立的條件概率，也把它叫做后驗(yàn)概率，它表示訓(xùn)練樣本數(shù)據(jù)D出現(xiàn)時(shí)假設(shè)h成立的置信度。

根據(jù)貝葉斯公式

可以去掉公式中的P（D），因?yàn)镻（D）通常是不依賴于假設(shè)h的常量，則公式中后驗(yàn)概率P（h｜D）的值就取決于P（D｜h）P（h）這個(gè)乘積，這就是本文所要用到的樸素貝葉斯算法的核心思想。在給定了候選假設(shè)集合H以及訓(xùn)練數(shù)據(jù)D之后，從假設(shè)集合H中找出D出現(xiàn)時(shí)可能性最大的假設(shè)h。簡(jiǎn)而言之，就是當(dāng)給定一些訓(xùn)練樣本數(shù)據(jù)集之后，如何讓計(jì)算機(jī)去學(xué)習(xí)這個(gè)訓(xùn)練樣本數(shù)據(jù)集，從而當(dāng)碰到新的數(shù)據(jù)時(shí)，可以自動(dòng)將新數(shù)據(jù)歸類到已經(jīng)定義好的某一個(gè)類別中去。

一個(gè)數(shù)據(jù)通常包含多個(gè)屬性，這里假設(shè)數(shù)據(jù)D中包含a1，a2，…，an這n個(gè)屬性，而樸素貝葉斯算法基于這樣一個(gè)假設(shè)：給定數(shù)據(jù)的屬性值之間相互獨(dú)立。該假設(shè)說明當(dāng)給定一個(gè)具體的目標(biāo)值時(shí)，a1，a2，…，an同時(shí)發(fā)生的聯(lián)合概率等于每個(gè)屬性單獨(dú)發(fā)生的概率的乘積，用公式表達(dá)

則樸素貝葉斯算法中的后驗(yàn)概率就可以表示成［10］

2 樸素貝葉斯分類器設(shè)計(jì)

當(dāng)給定一篇中文文本時(shí)，計(jì)算機(jī)只能將其識(shí)別成一個(gè)很長(zhǎng)的字符串，如何讓計(jì)算機(jī)更加細(xì)致地識(shí)別這篇文本是首先要面對(duì)的問題。因此，在利用樸素貝葉斯算法進(jìn)行文本分類之前，需要對(duì)文本進(jìn)行一些預(yù)處理。

2.1 預(yù)處理

中文不像英文那樣詞與詞之間都有空格分開，因此中文文本需要進(jìn)行分詞才能夠進(jìn)行下一步的處理。在本次樸素貝葉斯分類器的設(shè)計(jì)過程中，直接調(diào)用了中國(guó)科學(xué)院計(jì)算技術(shù)研究所研制的漢語詞法分析系統(tǒng)ICTCLAS［11］。

在分詞過后，作者利用哈爾濱工業(yè)大學(xué)信息檢索研究中心提供的中文停用詞表，對(duì)分詞結(jié)果進(jìn)行特征提?。?2］，以去除那些對(duì)分類結(jié)果無影響的詞，比如“的”、“在”這一類詞，降低文本向量的維數(shù)，提高運(yùn)算的效率［13］。

2.2 樸素貝葉斯分類器設(shè)計(jì)

樸素貝葉斯分類器就是將樸素貝葉斯算法應(yīng)用在分類器的設(shè)計(jì)上。根據(jù)貝葉斯

在特征提取之后，待分類的文本就會(huì)被表示成一個(gè)特征向量X（x1，x2，…，xn），下一步的任務(wù)就是將該向量X（x1，x2，…，xn）歸類到它最可能屬于的類別C（C1，C2，…，Cj）中去。其中，X（x1，x2，…，xn）表示文本的特征向量，C1，C2，…，Cj為給定的j種類別。換句話說，就是求解向量X（x1，x2，…，xn）分別屬于C1，C2，…，Cj的概率值（P1，P2，…，Pj），其中，Pj表示將X（x1，x2，…，xn）歸類到Cj的概率，那么 max（P1，P2，…，Pj）所對(duì)應(yīng)的結(jié)果就是文本X所屬的類別［14］。

根據(jù)樸素貝葉斯算法可以得到

式中：P（Cj）為待分類文本屬于Cj的先驗(yàn)概率；P（x1，x2，…，xn｜Cj）表示待分類文本屬于Cj時(shí)；類別Cj中包含文本特征向量（x1，x2，…，xn）的后驗(yàn)概率。所以求解 max（P1，P2，…，Pj）就可以轉(zhuǎn)化

根據(jù)樸素貝葉斯算法的假設(shè)，文本的特征屬性x1，x2，…，xn之間相互獨(dú)立，則其聯(lián)合概率就等于各個(gè)屬性的概率的乘積，所以，最后用來進(jìn)行分類的函數(shù)就是為求解式（9）的最大值

3 算法改進(jìn)

在研究的過程中，主要從以下兩個(gè)方面進(jìn)行了改進(jìn)。

（1）通常在給定一篇中文文本時(shí)，人們可能會(huì)有一個(gè)背景知識(shí)，根據(jù)這個(gè)背景知識(shí)可以對(duì)該篇文本進(jìn)行大概的分類，這便是傳統(tǒng)的樸素貝葉斯算法中的先驗(yàn)概率所起的作用。但在某些實(shí)際情況中，事先并不知道它屬于哪一類，也就是沒有相關(guān)的背景知識(shí)，因此本著公平的原則，該篇文檔屬于某一類的先驗(yàn)概率應(yīng)該相同，不能因?yàn)橛?xùn)練文本集中某一類的文本數(shù)量多，就認(rèn)為屬于這一類的概率大，這是不公平、不科學(xué)的。因此本文就只針對(duì)先驗(yàn)概率相等的情況進(jìn)行后續(xù)研究。根據(jù)以上觀點(diǎn)，就可以去除分類函數(shù)中的先驗(yàn)概率的計(jì)算，則分類函數(shù)為

因?yàn)樽詈笫且ㄟ^比較得出最大的概率值，所以都去掉先驗(yàn)概率的計(jì)算不會(huì)影響最后的分類結(jié)果。同時(shí)，去掉先驗(yàn)概率的計(jì)算可以大幅減少計(jì)算機(jī)的I/O操作，從而增加計(jì)算的速度。

（2）在實(shí)驗(yàn)中，定義了一個(gè)double類型的變量來存放計(jì)算出來的后驗(yàn)概率，每個(gè)特征詞計(jì)算出來的后驗(yàn)概率往往都是一個(gè)非常小的數(shù)，有時(shí)候待分類的文本比較長(zhǎng)，其特征詞就比較多，根據(jù)樸素貝葉斯算法計(jì)算出來的概率值往往非常小，在實(shí)驗(yàn)中發(fā)現(xiàn)很多時(shí)候計(jì)算出來的后驗(yàn)概率都為0.0，當(dāng)預(yù)先定義好的類別數(shù)目比較少時(shí)，就很有可能影響最后的分類精度。為克服這種誤差傳播，為每個(gè)特征詞求解出來的后驗(yàn)概率引入一個(gè)放大系數(shù)K，這不會(huì)影響實(shí)驗(yàn)結(jié)果，因?yàn)樽詈笫且ㄟ^比較得出最大的概率值，適當(dāng)放大一定倍數(shù)更有利于減少誤差傳播，提高分類精度。K值的確定會(huì)在下面的實(shí)驗(yàn)中給出。分類函數(shù)為

4 實(shí)驗(yàn)結(jié)果與分析

構(gòu)建樸素貝葉斯分類器需要大量的訓(xùn)練文本集和測(cè)試集，本文實(shí)驗(yàn)數(shù)據(jù)來自搜狗實(shí)驗(yàn)室提供的reduced版本互聯(lián)網(wǎng)語料庫(kù)，該版本包含財(cái)經(jīng)、IT、健康、體育、旅游、教育、招聘、文化、軍事等9類文檔，每一類文檔包含1 990篇文檔，實(shí)驗(yàn)中隨機(jī)從每一類文檔中抽取出一定數(shù)量的文本作為訓(xùn)練文本，再?gòu)氖Ｏ碌拿恳活愇谋局谐槿∫恍┪谋咀鳛闇y(cè)試文本，最后使用準(zhǔn)確率作為評(píng)價(jià)指標(biāo)，其中

實(shí)驗(yàn)時(shí)所用機(jī)器型號(hào)為惠普Compaq 6515b，機(jī)器主要配置為AMD Turion 64處理器，1GB內(nèi)存，2.2GHz主頻，使用JAVA 編程語言，Myeclipse8.5開發(fā)環(huán)境。實(shí)驗(yàn)分別對(duì)改進(jìn)前后的算法進(jìn)行驗(yàn)證，實(shí)驗(yàn)數(shù)據(jù)如表1所示。

表1 分類結(jié)果對(duì)比Table 1 Classification results comparison

通過表1實(shí)驗(yàn)可以看到樸素貝葉斯分類器的準(zhǔn)確率還是非常高的，去掉先驗(yàn)概率的計(jì)算對(duì)分類結(jié)果的影響并不是很大，除了軍事類和IT類在改進(jìn)前后的準(zhǔn)確率相同之外，其他幾類文本的準(zhǔn)確率，改進(jìn)后的分類算法都比改進(jìn)前的分類算法有小幅度的提高。

此外，實(shí)驗(yàn)還從每一類文本中抽取出一篇文本作為測(cè)試文本，對(duì)其改進(jìn)前后的計(jì)算時(shí)間進(jìn)行了統(tǒng)計(jì)，結(jié)果如表2所示。計(jì)算時(shí)間因測(cè)試文本的字?jǐn)?shù)而異。

表2 計(jì)算時(shí)間對(duì)比Table 2 Computer time comparison s

從表2的實(shí)驗(yàn)結(jié)果可以看出，改進(jìn)后的算法在計(jì)算速度上有了明顯的提升，9類測(cè)試文本在算法改進(jìn)后所用的時(shí)間都比改進(jìn)前要少。綜合表1，2的實(shí)驗(yàn)結(jié)果，可以得出結(jié)論：改進(jìn)后的算法效率更高。

在改進(jìn)的算法中，為減小誤差傳播，為后驗(yàn)概率的計(jì)算引入了一個(gè)放大系數(shù)K，因?yàn)樽詈罄梅诸惡瘮?shù)計(jì)算出來的后驗(yàn)概率值非常小，結(jié)果有時(shí)會(huì)顯示為0.0。起初將K的值設(shè)置為10，但在實(shí)驗(yàn)中發(fā)現(xiàn)，有些時(shí)候放大倍數(shù)過大時(shí)也會(huì)使后驗(yàn)概率的計(jì)算結(jié)果為0.0。隨機(jī)從9類文本中，每類隨機(jī)抽取了100篇測(cè)試文本，其中包含一些篇幅比較長(zhǎng)的文本，當(dāng)計(jì)算一篇文本分別屬于9種類別的后驗(yàn)概率時(shí)，9個(gè)后驗(yàn)概率中只要出現(xiàn)一次0.0，就將這篇文本標(biāo)記出來，最后統(tǒng)計(jì)了每一類的100篇文本在擴(kuò)大倍數(shù)分別為3，4，5，6，7，8，9，10時(shí)被標(biāo)記出來的文本數(shù)，放大系數(shù)為1～2倍時(shí)對(duì)分類性能的影響太小，所以沒有列出對(duì)應(yīng)的統(tǒng)計(jì)結(jié)果。實(shí)驗(yàn)結(jié)果如表3所示。

通過表3的實(shí)驗(yàn)結(jié)果可以看出，放大倍數(shù)集中于4，5，6，7時(shí)被標(biāo)記出來的文本數(shù)相對(duì)較少，放大的效果比較好。其中，當(dāng)放大系數(shù)為5時(shí)，取得的實(shí)驗(yàn)結(jié)果相對(duì)更好。

表3 放大倍數(shù)實(shí)驗(yàn)結(jié)果Table 3 Experiment results of amplification factor

5 結(jié)束語

通過樸素貝葉斯算法構(gòu)造文本分類器，是一種簡(jiǎn)單有效的方法，分類的準(zhǔn)確率非常高，速度也相對(duì)較快。但由于樸素貝葉斯算法是一種基于機(jī)器學(xué)習(xí)的算法，它的準(zhǔn)確率在很大程度上依賴于訓(xùn)練集，因此，如何確定訓(xùn)練文本集的數(shù)量將是今后的一個(gè)研究方向。在本次放大系數(shù)的實(shí)驗(yàn)中，只是初步選取了一些整數(shù)倍，初步確定了放大倍數(shù)的范圍，具體放大到什么程度，也有待日后做進(jìn)一步的研究。此外，當(dāng)文本中包含一些較復(fù)雜的句式時(shí)，往往會(huì)影響分類的精度，這也將是今后一個(gè)主要的研究方向。

［1］Sebastiani F.Machine learning in automated text categorization［J］.ACM Computing Surveys，2002，34（1）：1-9.

［2］Finn A，Kushmeick N，Smyth B.Genre classification and domain transfer for information filtering［C］∥Proceedings of the 24th BCS-IRSG European Colloquium on Information Retrieval Research：Advances in Information Retrieval. UK：Springer，2002：353-362.

［3］Yu H，Hatzivassiloglou V.Towards answering opinion questions：Separating facts from opinions and identifying the polarity of opinion sentences［C］∥Proceedings of the 2003Conference on EMNLP.USA：ACL，2003：129-136.

［4］Pang B，Lee L.A sentimental education：sentiment analysis using subjectivity summarization based on minimum cuts［C］∥Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics.Morristown，NJ，USA：ACL，2004：271-278.

［5］劉叢山，李祥寶，楊煜普.一種基于近鄰元分析的文本分類算法［J］.計(jì)算機(jī)工程，2012，38（15）：139-141.

Liu Congshan，li Xiangbao，Yang Yupu.Text classification algorithm based on neighborhood component analysis［J］.Computer Engineering，2012，38（15）：139-141.

［6］張春英，王晶.一種新型加權(quán)樸素貝葉斯分類算法［J］.微計(jì)算機(jī)信息：管控一體化，2010，26（10）：222-224.

Zhang Chunying，Wang Jing.A new weighted naive Bayesian classification algorithm［J］.Microcomputer Information，2010，26（10）：222-224.

［7］鐘將，孫啟干，李靜.基于歸一化向量的文本分類算法［J］.計(jì)算機(jī)工程，2011，37（8）：47-49.

Zhong Jiang，Sun Qigan，Li Jing.Text classification algorithm based on normalized vector［J］.Computer Engineering，2011，37（8）：47-49.

［8］呂國(guó)云，趙榮椿，張艷寧，等.基于三音素動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)模型的大詞匯量連續(xù)語音識(shí)別［J］.數(shù)據(jù)采集與處理，2009，24（1）：1-6.

LüGuoyun，Zhao Rongchun，Zhang Yanning.Continuous speech recognition for large vocabulary based on triphone DBN model［J］.Journal of Data Acquisition and Processing，2009，24（1）：1-6.

［9］盛驟.概率論與數(shù)理統(tǒng)計(jì)［M］.北京：高等教育出版社，2010：26-33.

［10］Mitchell T M.機(jī)器學(xué)習(xí)［M］.北京：機(jī)械工業(yè)出版社，2003：126-128.Mitchell T M.Machine learning［M］.Beijing：Chine Machine Press，2003：126-128.

［11］中國(guó)科學(xué)院計(jì)算技術(shù)研究所.ICTCLAS特色［EB/OL］.http：//ictclas.org/index.html，2008/2013.

Institute of Computing Technology.ICTCLAS［EB/OL］.http：//ictclas.org/index.html，2008/2013.

［12］趙世奇，張宇，劉挺，等.基于類別特征域的文本分類特征選擇方法［J］.中文信息學(xué)報(bào)，2005，19（6）：21-27.

Zhao Shiqi，Zhang Yu，Liu Ting.A feature selection method based on class feature domains for text categorization［J］.Journal of Chinese Information Processing，2005，19（6）：21-27.

［13］史岳鵬，朱顥東.基于類別相關(guān)性和優(yōu)化的ID3特征選擇［J］.數(shù)據(jù)采集與處理，2011，26（2）：231-234.

Shi Yuepeng，Zhu Haodong.Feature selection based on category correlation and improved ID3［J］.Journal of Data Acquisition and Processing，2011，26（2）：231-234.

［14］李曉歐，樂建威.基于小波預(yù)處理和貝葉斯分類器的P300識(shí)別算法［J］.數(shù)據(jù)采集與處理，2011，26（4）：420-423.

Li Xiaoou，Le Jianwei.P300detection algorithm based on wavelet preprocessing and bayesian classification［J］.Journal of Data Acquisition and Processing，2011，26（4）：420-423.