一種基于TF-IDF的樸素貝葉斯算法改進(jìn)

許甜華，吳明禮

(北方工業(yè)大學(xué) 信息學(xué)院，北京 100144)

0 引 言

隨著信息技術(shù)的發(fā)展，網(wǎng)絡(luò)信息量急劇增加，其中文本信息是海量網(wǎng)絡(luò)數(shù)據(jù)中的一大主體，但海量文本數(shù)據(jù)混亂存儲(chǔ)，極大影響了信息獲取的效率。如何快速準(zhǔn)確地獲取自己想要的信息便成為了一個(gè)重要問(wèn)題。而現(xiàn)今廣泛應(yīng)用的分類技術(shù)可以幫助人們快速地篩選信息，并且從海量數(shù)據(jù)中提取信息進(jìn)而構(gòu)造高效的分類器，是數(shù)據(jù)挖掘領(lǐng)域中一個(gè)熱門的研究方向。其中文本分類的過(guò)程一般分為以下步驟：數(shù)據(jù)預(yù)處理、數(shù)據(jù)特征提取、構(gòu)建分類器、進(jìn)行分類。

現(xiàn)今數(shù)據(jù)挖掘領(lǐng)域有多種分類算法，比如決策樹(shù)、支持向量機(jī)、貝葉斯分類器和神經(jīng)網(wǎng)絡(luò)等。其中貝葉斯分類器通過(guò)某對(duì)象的先驗(yàn)概率，利用貝葉斯公式計(jì)算出其后驗(yàn)概率，然后選擇多種分類中的最大后驗(yàn)概率作為該對(duì)象所屬分類的分類器。其計(jì)算過(guò)程簡(jiǎn)單快速，在多分類問(wèn)題上計(jì)算復(fù)雜度比較均衡，且在多分布獨(dú)立的假設(shè)下，分類器效果很好，所需樣本少。貝葉斯分類器以其上述優(yōu)點(diǎn)在文本分類、垃圾文本過(guò)濾、情感判別、多分類實(shí)時(shí)預(yù)測(cè)、推薦系統(tǒng)等領(lǐng)域中被廣泛應(yīng)用。在貝葉斯分類器中，樸素貝葉斯分類假定各個(gè)特征相互獨(dú)立，互不干擾，能夠處理多分類任務(wù)，適合增量式訓(xùn)練，尤其在數(shù)據(jù)量超過(guò)一定程度時(shí)，可以進(jìn)行批次訓(xùn)練，所以在垃圾郵件過(guò)濾，文檔分類中效果很好。

但是樸素貝葉斯網(wǎng)絡(luò)在進(jìn)行特征計(jì)算以及分類的過(guò)程中，默認(rèn)所有特征的權(quán)重是一致的，這樣的前提忽略了各文本特征的特性。而實(shí)際上，不同特征項(xiàng)在分類過(guò)程中起到的作用是不一樣的，將特征的權(quán)重視為一致，會(huì)在一定程度上降低分類的準(zhǔn)確率。比如：當(dāng)一篇文章中多次出現(xiàn)了“霧霾”一詞，便可認(rèn)為文章主題和天氣相關(guān)的概率是很大的，而當(dāng)文章中只提到一次“霧霾”時(shí)，幾乎是不能確定該文章主題和天氣相關(guān)的。因此在使用樸素貝葉斯網(wǎng)絡(luò)時(shí)，多與其他的特征加權(quán)算法共同使用，進(jìn)行特征加權(quán)計(jì)算，以得到更好的分類效果。目前文本分類中常用的特征權(quán)重算法TF-IDF(term frequency-inverse document frequency)是一種基于詞頻的特征權(quán)重算法[1]，通過(guò)計(jì)算詞頻和逆文本頻率來(lái)計(jì)算特征權(quán)重，在兼顧效率的同時(shí)也能得到較滿意的效果。但是該算法沒(méi)有體現(xiàn)特征詞在文檔類間和類內(nèi)的分布信息。文獻(xiàn)[2]中加入特征類間比重信息，使其對(duì)文檔分布不敏感，從而對(duì)文檔集有更好的適應(yīng)性；文獻(xiàn)[3]通過(guò)計(jì)算特征詞間的相似度，選擇最大相似度作為特征權(quán)重，提高分類效果；文獻(xiàn)[4]提出新詞發(fā)現(xiàn)特征權(quán)重算法，改進(jìn)TF-IDF對(duì)網(wǎng)絡(luò)新詞的識(shí)別能力，優(yōu)化文本分類效果；文獻(xiàn)[5]通過(guò)改進(jìn)特征選擇算法和特征加權(quán)算法，增加位置選擇信息來(lái)提高文本分類效果；文獻(xiàn)[6-9]均對(duì)TF-IDF權(quán)重進(jìn)行了類間改進(jìn)優(yōu)化。

雖然這些文獻(xiàn)對(duì)權(quán)重進(jìn)行了改進(jìn)，但均未兼顧文檔詞頻的分布位置和算法在正負(fù)樣本不均衡的傾斜數(shù)據(jù)集上的不同。鑒于傳統(tǒng)TF-IDF算法的不足，文中提出一種基于TF-IDF的樸素貝葉斯改進(jìn)算法TF-IDF-DL樸素貝葉斯算法。相對(duì)于以上各種改進(jìn)方法，文中擬打算從特征詞詞頻及其位置與類別之間的關(guān)系出發(fā)，對(duì)詞頻進(jìn)行去中心化處理并引入特征詞位置影響因子，以達(dá)到分類算法對(duì)不同的文檔有更強(qiáng)的分類適應(yīng)性，并能夠在分類結(jié)果的準(zhǔn)確率、召回率和F1值方面有所提高的目的。

1 相關(guān)研究

1.1 樸素貝葉斯算法

樸素貝葉斯算法假設(shè)各條件特征相互獨(dú)立[10]，計(jì)算文本中某些特征出現(xiàn)的情況下，該文本屬于某分類的概率，最后通過(guò)對(duì)比各個(gè)分類概率的大小，找出最高概率值，從而得出當(dāng)前文本所屬分類。樸素貝葉斯的分類公式為：

(1)

其中，P(Cn)代表所要分類的文本屬于類別Cn的概率，P(Xm|Cn)代表類別Cn中包含特征項(xiàng)Xm的概率。在樸素貝葉斯中，要求各特征獨(dú)立，且將特征權(quán)重看作是一致的。但在實(shí)際應(yīng)用中，各特征的權(quán)重是不一致的，為了讓算法更加準(zhǔn)確，使用特征加權(quán)算法進(jìn)行特征權(quán)重的計(jì)算，從而提高分類性能[11]。

1.2 特征項(xiàng)頻率TF

TF(term frequency)是特征詞在文檔中出現(xiàn)的詞頻，其表達(dá)式為：

(2)

其中，分子ni,j表示該詞在文件中的出現(xiàn)次數(shù)，分母為文件中所有字詞出現(xiàn)的次數(shù)總和。但是由于文檔長(zhǎng)度不一，為了防止同一詞語(yǔ)在較長(zhǎng)文檔中出現(xiàn)的頻率比在較短文檔中出現(xiàn)的頻率高的現(xiàn)象，一般會(huì)對(duì)詞頻進(jìn)行正規(guī)化處理的改進(jìn)。

1.3 逆向文件頻率IDF

詞頻計(jì)算，在傳統(tǒng)計(jì)算中是將所有特征詞的權(quán)重看作是相同的。而特征詞的權(quán)重在實(shí)際應(yīng)用中并不一致，所以在文本分類中要提升主要特征項(xiàng)的作用，降低次要特征項(xiàng)的作用。

IDF(inverse document frequency)可以計(jì)算出給定詞的重要性。某一特定詞的IDF，由文件總數(shù)目除以包含該詞語(yǔ)文件的數(shù)目進(jìn)行表示[6]。如果一個(gè)特征項(xiàng)在一個(gè)文本中出現(xiàn)的頻率較高，而在其他文本中出現(xiàn)的頻率較低，那么說(shuō)明此特征項(xiàng)能夠很好地區(qū)分此類文本和其他文本。公式如下：

(3)

但在計(jì)算過(guò)程中，會(huì)出現(xiàn)某一詞并未在某一文本中出現(xiàn)的情況。為了防止出現(xiàn)這種分母為零的現(xiàn)象，最常用的方法是使用拉普拉斯平滑對(duì)上述公式進(jìn)行處理，進(jìn)行平滑處理后的公式為：

(4)

最后，TF-IDF傳統(tǒng)計(jì)算公式為TF*IDF，即：

(5)

其中，wdt為計(jì)算出的特征項(xiàng)t在文本d中的權(quán)重，tfdt為特征詞在文本d中出現(xiàn)的頻率，N為文本語(yǔ)料庫(kù)中文本的總數(shù)，nt為文本語(yǔ)料庫(kù)中包含特征項(xiàng)t的文本數(shù)。

2 TF-IDF的改進(jìn)

2.1 去中心化詞頻因子

在TF-IDF的計(jì)算過(guò)程中，將特征詞詞頻作為特征詞權(quán)重大小的判斷依據(jù)，以特征詞出現(xiàn)的次數(shù)，以及特征詞文檔比例來(lái)進(jìn)行權(quán)重計(jì)算。但是各個(gè)特征詞表達(dá)的意義并不相同，某些特征詞出現(xiàn)頻率較少，屬于日常用詞，對(duì)于文本分類的貢獻(xiàn)并不大，但是在權(quán)重計(jì)算中被賦予較高的權(quán)重；某些特征詞屬于生僻詞，能夠代表某一類文本，出現(xiàn)次數(shù)較少，但是在權(quán)重計(jì)算中被賦予較低的權(quán)重。

針對(duì)以上不足，文中采用去中心化特征詞頻因子對(duì)特征詞出現(xiàn)的次數(shù)進(jìn)行去中心化處理。在計(jì)算特征詞頻時(shí)，根據(jù)特征詞出現(xiàn)的相對(duì)次數(shù)對(duì)權(quán)重進(jìn)行增加或者減少的處理，在這兩個(gè)方面進(jìn)行改進(jìn)后對(duì)結(jié)果再進(jìn)行正值化處理，最終去中心化特征詞頻因子(decentralization term frequency)公式如下:

DTFd,t=eNd,t-Nt

(6)

將DTF添加到TF-IDF中，即分子變?yōu)椋?/p>

(7)

若一個(gè)詞在此文檔中出現(xiàn)的頻率低于該特征詞出現(xiàn)的平均頻率，那么DTF值小于1，則最終權(quán)重降低；反之則權(quán)重增加。通過(guò)去中心化處理，可以降低常用詞和生僻詞在詞頻上的差異性。

2.2 特征詞位置信息

在文檔中，大多數(shù)文章都會(huì)在開(kāi)始和結(jié)束包含文章的主題，所以從分類角度來(lái)看，文章的開(kāi)始和結(jié)束部分的信息較為重要，應(yīng)該給予更高的權(quán)重[12]，所以文中將特征詞所在位置增加為權(quán)重計(jì)算的一個(gè)因子[13]。

將文檔中所有特征詞第一次出現(xiàn)的位置排列成一個(gè)序列，以文章總詞數(shù)為總長(zhǎng)度，以1為單元刻度，取序列最中間的位置為原始坐標(biāo)，計(jì)算其他詞距離原始坐標(biāo)的距離，距離越遠(yuǎn)，給予權(quán)重越大，說(shuō)明該詞對(duì)分類的影響越大。定義位置影響因子(location factor)如下：

(8)

其中，ε為要增加的權(quán)重值倍數(shù)，δ的范圍在(0,D/2)之間，其中D為序列總長(zhǎng)度。

將去中心化詞頻因子和特征詞位置信息加入到傳統(tǒng)的TF-IDF公式中，最終改進(jìn)的TF-IDF公式(TF-IDF-DL)如下：

wdt=TF*IDF*DIF*LF

(9)

最后將該公式與樸素貝葉斯算法相結(jié)合[14]，改進(jìn)后的樸素貝葉斯公式為：

(10)

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

3.1 數(shù)據(jù)處理

該實(shí)驗(yàn)采用搜狗實(shí)驗(yàn)室的搜狗新聞精簡(jiǎn)數(shù)據(jù)集(SogouCS,2012版http://www.sogou.com/labs/resource/cs.php)，共698 M，128個(gè)新聞文檔，完整新聞條數(shù)共429 818條，數(shù)據(jù)樣式如下所示:

從上述樣式的標(biāo)簽得出此條信息的新聞?lì)悇e為sports類，以此方式進(jìn)行所有文檔新聞?lì)悇e的提取，并提取對(duì)應(yīng)的標(biāo)簽中的新聞內(nèi)容信息。

同時(shí)，還需對(duì)得到的數(shù)據(jù)集進(jìn)行進(jìn)一步的處理。首先，將常用的停用詞(的，并不，而且等)進(jìn)行過(guò)濾，其次將新聞內(nèi)容短于50字符的新聞視為垃圾新聞并進(jìn)行剔除。最終數(shù)據(jù)集將分為12類，該實(shí)驗(yàn)選擇其中5類進(jìn)行分析，分別為：women，entertainment，travel，health，sports。為保證數(shù)據(jù)均勻分布，各類新聞各取5 000條作為訓(xùn)練集，取1 000條作為測(cè)試集，如表1所示。

表1 數(shù)據(jù)集

3.2 實(shí)驗(yàn)步驟

文中分別采用傳統(tǒng)的TF-IDF算法、文獻(xiàn)[2]中的TF-IDF-dist算法以及TF-IDF-DL算法進(jìn)行特征權(quán)重計(jì)算并將其應(yīng)用于樸素貝葉斯分類器中進(jìn)行文本分類，對(duì)比實(shí)驗(yàn)結(jié)果并進(jìn)行分析，具體實(shí)驗(yàn)步驟如下：

(1)輸入文檔轉(zhuǎn)化為特征詞后的詞頻向量；

(2)進(jìn)行文本的特征詞提取，并使用卡方檢驗(yàn)(CHI-Squre)方法計(jì)算特征值的卡方，并按照卡方值從大到小進(jìn)行排序，選取Top N的特征詞；

(3)分別使用TF-IDF算法，TF-IDF-dist算法及TF-IDF-DL算法計(jì)算各特征詞的權(quán)重值；

(4)將各個(gè)特征詞的權(quán)重值加入到樸素貝葉斯算法中，計(jì)算得出文檔屬于各分類的概率，選擇分類概率中的最大值作為最終類別，輸出對(duì)應(yīng)分類信息；

(5)對(duì)比分析實(shí)驗(yàn)結(jié)果。

3.3 實(shí)驗(yàn)評(píng)估指標(biāo)

文中使用準(zhǔn)確率、召回率、F1值三個(gè)指標(biāo)來(lái)評(píng)估算法效果。

(1)分類準(zhǔn)確率precision。

對(duì)于類別Ci的分類準(zhǔn)確率定義為：分類結(jié)果中正確分類為Ci的樣本數(shù)占分類結(jié)果中所有分為Ci類別的樣本數(shù)(包含正確結(jié)果和錯(cuò)誤結(jié)果)的比例。

(11)

(2)召回率recall。

對(duì)于類別Ci的召回率定義為：分類結(jié)果中正確分類為Ci的樣本數(shù)占實(shí)際情形中分類為Ci的比例。

(12)

(3)F1值

F1值其實(shí)是準(zhǔn)確率和召回率的調(diào)和平均值，它的最大值是1，最小值是0。

(13)

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

在文本分類中少量的特征詞不能對(duì)文本進(jìn)行準(zhǔn)確的分類預(yù)測(cè)，但特征詞數(shù)量過(guò)大也會(huì)對(duì)實(shí)驗(yàn)有一定的消極影響。因此需要在分類前，找出最合適的特征詞數(shù)量，由于特征詞個(gè)數(shù)對(duì)所有權(quán)重值算法均適用，所以選擇以TF-IDF算法為基準(zhǔn)進(jìn)行分類實(shí)驗(yàn)。由圖1可得，隨著特征詞數(shù)量增加，precision值逐漸提高，但當(dāng)特征詞數(shù)量過(guò)大時(shí)，文本分類時(shí)間將會(huì)大幅增加。針對(duì)選取的數(shù)據(jù)集，在選擇特征詞數(shù)量為125左右時(shí)，precision增加速度開(kāi)始減緩，且特征詞數(shù)量在160左右時(shí)，分類時(shí)間開(kāi)始變長(zhǎng)。為了兼顧準(zhǔn)確率和效率，該實(shí)驗(yàn)選取中間值143作為分類的特征詞數(shù)量。

圖1 特征詞個(gè)數(shù)對(duì)precision和時(shí)間的影響

在采用TF-IDF-DL算法計(jì)算貝葉斯特征權(quán)重時(shí)，需要計(jì)算出位置信息的影響因子：ε和δ。當(dāng)δ值一定時(shí)，在初始范圍內(nèi)分類的準(zhǔn)確率隨詞頻位置影響度的增加而提高，但當(dāng)詞頻位置影響力度達(dá)到一定程度時(shí)，會(huì)超出該詞頻實(shí)際的作用效果，從而夸大其影響力，對(duì)分類效果產(chǎn)生負(fù)面影響，因此詞頻位置信息的影響度會(huì)存在一個(gè)準(zhǔn)確率峰值，當(dāng)ε值小于這個(gè)峰值時(shí)，分類準(zhǔn)確率會(huì)隨著ε值的增大而提高，當(dāng)ε值大于該峰值時(shí)，準(zhǔn)確率會(huì)隨之下降。同理，當(dāng)ε值一定時(shí)，對(duì)分類影響大的詞頻會(huì)分布在近首尾處，但是與中心位置坐標(biāo)距離太小和太大都會(huì)對(duì)準(zhǔn)確率造成一定的不良影響，因此最優(yōu)的δ值也存在一個(gè)準(zhǔn)確率峰值。通過(guò)圖2(多個(gè)不同的δ值進(jìn)行測(cè)試取得準(zhǔn)確率的平均值)和圖3(多個(gè)不同的ε值進(jìn)行測(cè)試取得準(zhǔn)確率的平均值)可知，對(duì)于該數(shù)據(jù)集的ε和δ的最優(yōu)取值分別為1.5和D/6。

圖2 不同ε對(duì)precision值的影響

圖3 不同ε對(duì)precision值的影響

在對(duì)上述未知參數(shù)進(jìn)行最優(yōu)值求解后，進(jìn)行TD-IDF，TD-IDF-dist以及TF-IDF-DL的權(quán)重值求解，并分別將求解權(quán)重值應(yīng)用到貝葉斯文本分類中，得出相應(yīng)的樸素貝葉斯分類器。并對(duì)選取的五種數(shù)據(jù)類別進(jìn)行測(cè)試，記錄每個(gè)類別對(duì)應(yīng)測(cè)試結(jié)果的precision、recall、F1值[15]，如圖4～圖6所示。

圖4 在不同新聞種類下不同算法對(duì)P的影響

圖5 在不同新聞種類下不同算法對(duì)R的影響

圖6 在不同新聞種類下不同算法對(duì)F1的影響

通過(guò)結(jié)果可以看出，在特征詞詞頻差異不明顯且特征詞位置沒(méi)有明顯規(guī)律的women類別上，應(yīng)用TF-IDF-DL算法的樸素貝葉斯分類準(zhǔn)確率沒(méi)有特別明顯的提高。

在特征詞詞頻差異性和特征詞位置規(guī)律性明顯的類別上，基于TF-IDF-DL的貝葉斯文本分類表現(xiàn)出明顯的優(yōu)勢(shì)。以travel類別為例(travel類別文本中近首尾處多出現(xiàn)“游客”、“景點(diǎn)”等詞匯)，應(yīng)用傳統(tǒng)TF-IDF和TF-IDF-dist算法的樸素貝葉斯分類效果表現(xiàn)都不是很好，而應(yīng)用TF-IDF-DL算法進(jìn)行貝葉斯分類時(shí)在travel分類上表現(xiàn)依然良好。在研究以TF-IDF-dist計(jì)算權(quán)重的分類結(jié)果后，發(fā)現(xiàn)平均有近10%的travel新聞被分類到entertainment類別中，有3.46%的travel新聞被分類到health中。統(tǒng)計(jì)分類錯(cuò)誤的新聞特征詞發(fā)現(xiàn)，其中明顯為entertainment分類的特征詞占統(tǒng)計(jì)特征詞的31.67%，明顯為health分類的特征詞占統(tǒng)計(jì)特征詞的9.82%。這是由于TF-IDF-dist算法僅僅考慮了特征詞在類內(nèi)和類間的分布關(guān)系，卻忽略了特征詞在詞頻上的差異性和特征詞位置信息規(guī)律這兩個(gè)因素。而TF-IDF-DL算法在去除了此類文章中entertainment和health類別所屬特征詞的中心詞頻，且加入了特征詞頻的位置信息影響因子。

通過(guò)實(shí)驗(yàn)對(duì)比，基于TF-IDF-DL的貝葉斯算法在分類準(zhǔn)確率、召回率和F1值這三方面最高可比基于TF-IDF-dis的貝葉斯分類提高8.6%、11.7%和7.4%。說(shuō)明文中提出的基于TF-IDF-DL的貝葉斯分類算法在特征詞詞頻有差異、特征詞位置信息有規(guī)律的數(shù)據(jù)集上分類效果較好，是一種良好的分類算法。

4 結(jié)束語(yǔ)

通過(guò)研究詞頻出現(xiàn)規(guī)律以及文檔中特征詞的出現(xiàn)位置，提出加入去中心化詞頻因子和特征詞距離因子來(lái)改進(jìn)TF-IDF算法，并將改進(jìn)后的TF-IDF-DL算法應(yīng)用到樸素貝葉斯算法中。該算法能夠解決在文本分類過(guò)程中存在特征屬性權(quán)重一致及考慮指標(biāo)單一的問(wèn)題。通過(guò)使用搜狗實(shí)驗(yàn)室新聞數(shù)據(jù)作為數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。結(jié)果表明，該算法能夠較好地提高分類性能，并對(duì)于不易區(qū)分的類別也能達(dá)到良好的分類效果，與國(guó)內(nèi)最新研究的TF-IDF-dis相比，在分類準(zhǔn)確率、召回率和F1值這三方面最高可比其高8.6%、11.7%和7.4%。但是該算法也存在一定的局限性，對(duì)于特征詞詞頻差異小且詞頻位置不規(guī)律的數(shù)據(jù)分類效果沒(méi)有明顯提高，還需進(jìn)一步完善。