基于改進(jìn)的加權(quán)補(bǔ)集樸素貝葉斯物流新聞分類

許英姿，任俊玲

(北京信息科技大學(xué) 信息管理學(xué)院，北京 100192)

0 引 言

常用文本分類算法主要有樸素貝葉斯[1](Naive Bayes，NB)、支持向量機(jī)[2](support vector machine，SVM)和K近鄰[3](k nearest neighbor，KNN)等。NB算法以其計算效率高、精確度高且穩(wěn)定性強(qiáng)的特點，成為常用的文本分類算法之一。縱觀國內(nèi)外學(xué)者使用NB算法對專業(yè)領(lǐng)域的文本進(jìn)行分類的研究，趙燕等[4]建立了適用于農(nóng)業(yè)文本分類的NB模型；孫宇[5]構(gòu)建NB模型，挖掘稻米產(chǎn)品物流因素與顧客滿意度間的關(guān)系。在物流領(lǐng)域，現(xiàn)有工作大多集中于對物流數(shù)據(jù)的挖掘與分析[6,7]或?qū)υu論文本的情感分析[8,9]，物流新聞文本相關(guān)研究較少。

根據(jù)各大官方物流新聞網(wǎng)站調(diào)研結(jié)果，不同類別物流新聞總數(shù)差距較大，物流新聞具有類間分布不均衡的特點，較大程度影響了分類器的實際分類效果。針對分類數(shù)據(jù)集不均衡的特點，王占偉[10]對樣本空間進(jìn)行改進(jìn)，提出基于重采樣技術(shù)的非平衡分類算法；Naderalvojou等[11]對分類加權(quán)算法進(jìn)行改進(jìn)，提出一種正負(fù)項和類別相關(guān)度的概率特征加權(quán)算法。以上方法均未考慮改進(jìn)算法對分類時間的影響。本文針對物流新聞文本專業(yè)性強(qiáng)且類別分布不均衡的特點，構(gòu)建物流新聞?wù)Z料庫，使用在中文數(shù)據(jù)集中表現(xiàn)最好的卡方檢驗[12,13](chi-square test，CHI)進(jìn)行特征選擇，考慮局部、全局和類內(nèi)、類間的特征加權(quán)算法進(jìn)行特征加權(quán)，實現(xiàn)基于加權(quán)補(bǔ)集樸素貝葉斯(weighted complement Naive Bayes，WCNB)的物流文本分類模型，通過不均衡的物流新聞文本分類實驗驗證模型的有效性與性能。

1 基于補(bǔ)集的樸素貝葉斯模型

1.1 樸素貝葉斯原理

樸素貝葉斯[14]是一種基于貝葉斯定理和特征條件獨(dú)立假設(shè)的概率統(tǒng)計方法。根據(jù)貝葉斯定理，假設(shè)有v個類別集合C={c1,c2,…,cv}；T={t1,t2,…,tm} 表示m篇文本，每個文本由n維特征詞向量X={x1,x2,…,xn} 表示，其中xi∈T(1≤i≤n)。 則對任何滿足P(tk)>0的tk都有公式

(1)

由于在給定的輸入中P(cl)是一個常量，且取最大后驗概率作為樣本所屬類別

(2)

式中：c(tk) 為該文本所屬類別對應(yīng)的數(shù)值。

1.2 補(bǔ)集樸素貝葉斯模型

傳統(tǒng)分類算法都假設(shè)類的樣本數(shù)量大致相同，面對不均衡樣本時，由于少數(shù)類信息表達(dá)不充分，而多數(shù)類信息提取更充分，分類模型易將少數(shù)類樣本分到多數(shù)類，導(dǎo)致分類性能大大降低。補(bǔ)集樸素貝葉斯[15](complement Naive Bayes，CNB)模型的基本思想是在估計文本屬于某一類別的概率時，通過估計文本不屬于該類別的概率，即利用補(bǔ)集的特征來表示當(dāng)前類別的特征，進(jìn)而預(yù)測待分類文本的類別,以解決分類模型容易傾向大類別而忽略小類別的問題。

(3)

用CNB模型對文本tk進(jìn)行分類，得該文本的類別最大值cCNB(tk)

(4)

2 特征選擇與權(quán)重計算

2.1 基于卡方檢驗的特征選擇

基于特征獨(dú)立性的NB算法假設(shè)所有特征詞對文本分類的貢獻(xiàn)相同，但實際上，向量化后文本的特征維數(shù)高達(dá)上萬維，每個特征詞的重要性也不相同的。若一個特征詞在某一類別中多次出現(xiàn)，而在其它類別中很少出現(xiàn)，則認(rèn)為該特征詞具有較高的類別區(qū)分度[16]。

常用的特征選擇方法有基于詞頻、方差、信息增益、互信息、卡方檢驗等[17]。常規(guī)的特征選擇方法對小類別的特征提取不足，卡方檢驗度量了特征詞與類別的關(guān)聯(lián)程度[18]，能通過計算關(guān)聯(lián)度來進(jìn)行特征選擇。特征詞xi相對于類別cl的卡方值χ2(xi,cl) 計算公式如下

(5)

式中：fa表示類別cl中出現(xiàn)特征詞xi的文本數(shù)；fb表示除類別cl的其它類別中出現(xiàn)特征詞xi的文本數(shù)；fc表示類別cl中未出現(xiàn)特征詞xi的文本數(shù)；fd表示除類別cl的其它類別中未出現(xiàn)特征詞xi的文本數(shù)。

利用最大值思想計算特征詞xi對于訓(xùn)練集文本的卡方值，公式為

(6)

對特征全集的卡方值進(jìn)行降序排列，并選取前z個特征詞以構(gòu)成特征子集。

2.2 基于TF-IDF特征加權(quán)算法的改進(jìn)

2.2.1 TF-IDF加權(quán)算法分析

詞頻-逆文檔頻率[19](term frequency-inverse document frequency，TF-IDF)為應(yīng)用最廣泛的特征詞權(quán)重計算方法之一。TF是局部加權(quán)因子，反映特征詞xi相對于文本tk的重要度，默認(rèn)出現(xiàn)次數(shù)越多越重要；IDF是全局加權(quán)因子，反映特征詞xi相對于整個訓(xùn)練集的重要度，即包含特征詞的文本越少，特征詞越重要。

第i個特征詞權(quán)重計算公式如下

(7)

(8)

TFIDF(xi,tk)=TF(xi,tk)·IDF(xi)

(9)

式中：N表示訓(xùn)練集的文本總數(shù)；df(xi) 表示包含特征詞xi的訓(xùn)練集文本數(shù)；TFIDF(xi,tk) 為特征詞xi的TF-IDF 值。

在特定的分類任務(wù)中，N是一個常數(shù)。因此，IDF(xi) 隨著df(xi) 的增大而減小，即特征詞xi的IDF(xi) 值與出現(xiàn)該詞的文本數(shù)成反比。故IDF能使TF的敏感性降低。

IDF主要有兩個缺陷，第一，僅有極少數(shù)文本出現(xiàn)某一特征詞時，其IDF值趨近無窮大；第二，若某一特征詞出現(xiàn)在很多文本中，則IDF約等于零[20]。此外，IDF忽略了特征詞在類內(nèi)和類間的分布，當(dāng)特征詞在某一類內(nèi)頻繁出現(xiàn)，而在其它類中出現(xiàn)較少，則認(rèn)為該詞具有良好的類別區(qū)分能力，但由于包含該詞的文本數(shù)較多，其權(quán)重可能并不高。

2.2.2 TF-IECF與TF-RIECF

為減小具有高TF、增強(qiáng)具有低DF與高類別區(qū)分度的特征詞對權(quán)值的影響，本文用具有以下屬性的新全局加權(quán)因子替換IDF因子：

(1)當(dāng)DF值增加時，全局加權(quán)因子具有較大的衰減率；

(2)為避免被零除，df(xi) 不能當(dāng)作分母；

(3)函數(shù)是有界函數(shù)。

(10)

(11)

觀察式(10)和式(11)，IEF與RIEF因子仍未解決特征詞在類內(nèi)和類間的分布問題，本文引入類內(nèi)及類間加權(quán)因子。類內(nèi)加權(quán)因子I(xi)反映所有類別中包含特征詞xi文本數(shù)最多的那一類的分布情況，值越大代表該詞在某類中分布越廣；類間加權(quán)因子B(xi)反映特征詞xi在各類間的分散程度，值越大代表該詞出現(xiàn)的類別越集中。類內(nèi)加權(quán)因子I(xi)和類間加權(quán)因子B(xi)的公式如下

(12)

(13)

綜上，本文將改進(jìn)的特征加權(quán)算法命名為詞頻-類別逆(根)指數(shù)頻率(term frequency-(radial) inverse exponential class frequency，TF-(R)IECF)，其公式如下

(14)

(15)

3 TF(R)IECF-WCNB模型

TF(R)IECF-WCNB模型分別使用TF-(R)IECF特征加權(quán)算法計算文本中經(jīng)過CHI特征選擇后的特征詞權(quán)重。假設(shè)特征詞xi在文本tk中歸一化后的權(quán)重為wik，并用wik修改式(3)

(16)

特征詞xi對類別cl的權(quán)重Wil計算公式如下

(17)

將式(17)標(biāo)準(zhǔn)化

(18)

根據(jù)式(18)修改式(4)，得出待分類文本D的最大后驗概率cWCNB(D) 為

(19)

文本D的所屬類別即為cWCNB(D)所對應(yīng)的類別。

4 物流新聞分類方法

4.1 物流新聞?wù)Z料庫構(gòu)建

文本分類已經(jīng)涉及多個領(lǐng)域，但迄今為止，尚沒有公開的物流新聞分類語料庫。因此，本文爬取中國物流信息中心網(wǎng)、中國貿(mào)易金融網(wǎng)等多家官方物流信息網(wǎng)站共4856條物流新聞，新聞文本具有真實性與一定的權(quán)威性。從物流領(lǐng)域的角度出發(fā)，結(jié)合當(dāng)下物流熱點，在各網(wǎng)站物流新聞劃分的基礎(chǔ)上，將物流新聞?wù)Z料庫劃分為6個類別[21]：采購、倉儲、運(yùn)輸、冷鏈、電子商務(wù)和快遞配送。物流新聞?wù)Z料庫類別分布情況如圖1所示。

圖1 物流新聞文本分布

根據(jù)圖1所示，實驗使用的新聞文本類間數(shù)量有一定差距，倉儲類與運(yùn)輸類占總數(shù)據(jù)集的51%，其余4類共占49%，體現(xiàn)物流新聞的不均衡性。

4.2 物流新聞分類流程

物流新聞分類流程分為三大模塊：構(gòu)建物流新聞?wù)Z料庫、TF(R)IECF-WCNB分類器分類和輸出分類結(jié)果。本文通過獲取已發(fā)布的物流新聞來構(gòu)建物流新聞?wù)Z料庫，將原始語料庫劃分為訓(xùn)練集和測試集，對分類器進(jìn)行訓(xùn)練和測試，最終輸出分類結(jié)果。全流程用Python語言實現(xiàn)。物流新聞分類流程如圖2所示。

圖2 物流新聞分類流程

TF(R)IECF-WCNB分類器分類分為兩大過程：訓(xùn)練過程和測試過程。訓(xùn)練過程利用劃分的訓(xùn)練集訓(xùn)練分類模型。主要步驟為：

步驟1 文本預(yù)處理。實現(xiàn)所有文本的分詞、剔除停用詞和去標(biāo)點符號等操作。根據(jù)物流領(lǐng)域?qū)I(yè)文本詞匯特征，在原有jieba分詞詞庫的基礎(chǔ)上，人工構(gòu)建并添加物流專業(yè)詞庫，防止物流專業(yè)詞匯在分詞階段被誤切，如：“冷鏈”被誤切為“冷”和“鏈”。依據(jù)物流新聞文本特點，修改中文停用詞表，作為本文的停用詞表。使用正則表達(dá)式匹配并刪除無關(guān)的英文及標(biāo)點符號；

步驟2 文本向量化。將分詞后的文本轉(zhuǎn)化為向量空間模型(vector space model，VSM)中的向量，生成文本-詞語矩陣，矩陣元素a[i][j] 表示第j個詞語在第i個文本下的詞頻；

步驟3 CHI特征選擇。原始文本-詞語矩陣特征維度過大，進(jìn)行特征選擇不僅可以篩選出正確分類有貢獻(xiàn)的特征詞，還能大大縮短分類時間。計算每個向量的CHI值，將計算結(jié)果按照降序進(jìn)行排序，選擇前z個特征詞，構(gòu)成特征子集；

步驟4 特征加權(quán)。對特征子集中的特征詞用TF-IECF或TF-RIECF特征加權(quán)算法計算每個特征詞的權(quán)重，并以權(quán)重更新文本-詞語矩陣；

步驟5 構(gòu)建并訓(xùn)練模型。構(gòu)建加權(quán)補(bǔ)集樸素貝葉斯模型，以特征加權(quán)后的文本-詞語矩陣作為輸入，訓(xùn)練模型。

測試過程中的測試集經(jīng)過相同的預(yù)處理、向量化和特征選擇后，利用已訓(xùn)練的加權(quán)補(bǔ)集樸素貝葉斯模型對物流新聞測試集進(jìn)行分類，最終輸出分類結(jié)果。

5 實驗與分析

5.1 評價指標(biāo)

文本分類的評價指標(biāo)分為局部指標(biāo)和全局指標(biāo)。局部指標(biāo)主要有準(zhǔn)確率P和召回率R。準(zhǔn)確率描述當(dāng)前類別分類正確的文本占分類至當(dāng)前類別文本總數(shù)的比例；召回率描述當(dāng)前類別分類正確的文本占當(dāng)前類別文本總數(shù)的比例。全局指標(biāo)有精確度和Kappa系數(shù)[22]。相較于精確度，Kappa 系數(shù)更適合應(yīng)用于多分類模型評價。本文使用兩種局部指標(biāo)與全局指標(biāo)Kappa系數(shù)來評價模型。

兩種局部指標(biāo)公式如下

(20)

(21)

式中：TP表示正確分類至當(dāng)前類別的文本數(shù)；FP表示其它類別文本錯分類至當(dāng)前類別的文本數(shù)；FN表示當(dāng)前類別文本錯分類至其它類別的文本數(shù)

(22)

(23)

Kappa系數(shù)公式中，ai表示第i類文本的實際樣本數(shù)量；bi為預(yù)測出的第i類文本樣本數(shù)量；M表示樣本總數(shù)；Kappa取值范圍[0,1]，數(shù)值越大代表模型分類效果越好。

除局部、總體指標(biāo)外，本文定義模型分類時間，特指文本向量化至輸出最終分類結(jié)果的時間間隔，也用于評價模型性能。

5.2 結(jié)果與分析

本文分別使用基于NB模型、MNB模型、CNB模型、TFIDF-WCNB模型、TFIECF-WCNB模型和TFRIECF-WCNB模型的6種分類器，進(jìn)行兩組實驗。

實驗1：為了達(dá)到最優(yōu)模型性能，對原始特征詞用CHI進(jìn)行特征選擇時，實驗對特征詞維度z的取值從0開始以間隔400為單位逐漸遞增。z=0代表不進(jìn)行特征選擇。特征詞維度z的取值對CNB模型的全局指標(biāo)Kappa系數(shù)的影響如圖3所示。

圖3 特征詞維度取值對Kappa系數(shù)的影響

從圖3的折線圖可以看出，特征詞維度z從0以400為單位遞增到2000的過程中，隨著特征子集增大，所選特征詞對各類別特性表述的完整性提高，描述的類別信息增多，CNB模型分類的Kappa系數(shù)也不斷增加；當(dāng)z取值大于2000時，特征子集所表述的類別信息臨近飽和，特征詞維度的增加并不能增多其對各類別信息表述，反而導(dǎo)致模型出現(xiàn)輕微過擬合現(xiàn)象，故Kappa系數(shù)隨著z值的增加而緩慢減小，直至平穩(wěn)。當(dāng)z=2000時，模型分類性能最優(yōu)。

實驗2：在特征詞維度z=2000的條件下，比較各模型在物流新聞?wù)Z料庫的6個不同類別內(nèi)的分類性能。實驗采用Laplace平滑方法，即先驗平滑因子α=1。各模型不同類別下的準(zhǔn)確率P和召回率R對比如圖4所示。

圖4 z=2000時各模型局部指標(biāo)對比

由圖4可以看出，各模型不同類別的分類效果不同，運(yùn)輸類、冷鏈類和電子商務(wù)類分類效果較好；快遞配送類分類效果最差。傳統(tǒng)NB模型在6種模型中，其準(zhǔn)確率和召回率皆為最低，分類性能最差。在NB模型的基礎(chǔ)上，形成的服從多項分布的MNB模型其局部指標(biāo)較NB模型有較大提升。適用于不均衡數(shù)據(jù)集的CNB模型與適用于均衡數(shù)據(jù)集的MNB模型相比，無論大類別還是小類別，其兩種局部指標(biāo)大都有所提高，且小類別表現(xiàn)更好，驗證了CNB模型能有效利用補(bǔ)集的思想彌補(bǔ)傳統(tǒng)模型小類別信息提取不充分的缺陷。運(yùn)用傳統(tǒng)特征加權(quán)思想的TFIDF-WCNB模型，由于其IDF因子原有的缺陷且忽略了特征詞在類內(nèi)、類間的分布，分類準(zhǔn)確率較CNB模型并無較明顯提升，相反，在運(yùn)輸類、冷鏈類、電子商務(wù)類中其準(zhǔn)確率不升反降，表明對不均衡數(shù)據(jù)集的特征詞用傳統(tǒng)算法進(jìn)行加權(quán)，不一定能取得理想的效果。本文對CNB模型進(jìn)行改進(jìn)，提出的TFIECF-WCNB模型和TFRIECF-WCNB模型與TFIDF-WCNB模型相比，局部指標(biāo)都有一定程度的提高，且小類別較大類別提升更明顯。從總體上看，TFRIECF-WCNB模型的在各類別的分類效果最好，TFIECF-WCNB模型次之，實驗結(jié)果驗證了基于TF(R)IECF-WCNB模型的分類器對類別分布不均衡物流新聞分類的有用性。

各模型全局指標(biāo)Kappa系數(shù)與模型分類時間見表1。

根據(jù)表1的分類結(jié)果，傳統(tǒng)NB模型分類效果最差，雖然MNB、CNB模型相對于NB模型在Kappa系數(shù)上有很大提升，但也大幅增加了其時間復(fù)雜度。對特征詞進(jìn)行加權(quán)處理，在小幅提升Kappa系數(shù)的同時，能大幅縮短分類時間。本文提出的TFIECF-WCNB模型和TFRIECF-WCNB 模型在Kappa系數(shù)和分類時間這兩個指標(biāo)上，都是最佳的。其中，TFRIECF-WCNB模型分類性能最優(yōu)，其全局指標(biāo)高達(dá)0.8945，且分類時間最短為50.5 s。

表1 z=2000時各模型Kappa系數(shù)與分類時間

綜合對局部、全局指標(biāo)和分類時間的分析，本文提出的基于TF(R)IECF-WCNB模型的分類器能快速、準(zhǔn)確地對物流新聞進(jìn)行分類，并驗證了TF(R)IECF-WCNB模型在類別分布不均衡的物流新聞文本分類上的優(yōu)勢和可行性。

6 結(jié)束語

本文采了一種改進(jìn)的樸素貝葉斯模型即加權(quán)補(bǔ)集樸素貝葉斯模型，用以實現(xiàn)對不均衡物流新聞文本進(jìn)行分類，并取得了較好的分類效果。NB算法是一個穩(wěn)定的算法，基于NB算法改進(jìn)的模型，在保證分類模型的強(qiáng)穩(wěn)定性同時，還具有較高的計算效率與分類精度。

通過構(gòu)建物流新聞?wù)Z料庫，并針對語料庫中各類別文本數(shù)量分布不均衡與專業(yè)性強(qiáng)的特點，對文本進(jìn)行預(yù)處理，使用卡方檢驗進(jìn)行特征選擇，對傳統(tǒng)TF-IDF算法進(jìn)行分析，提出、改進(jìn)并形成了TF-(R)IECF特征加權(quán)算法，解決了傳統(tǒng)加權(quán)算法對特征詞在各類別間分布情況重視不足的問題。實驗結(jié)果表明，基于TF(R)IECF-WCNB模型的分類器，解決了傳統(tǒng)分類器容易傾向大類別而忽略小類別的問題，面對類別分布不均衡的物流新聞數(shù)據(jù)集，表現(xiàn)出良好的分類性能。

國民經(jīng)濟(jì)快速發(fā)展的今天，物流業(yè)已成為助力經(jīng)濟(jì)發(fā)展不可或缺的一部分。在物流業(yè)快速發(fā)展的背景下，快速而準(zhǔn)確對物流新聞進(jìn)行分類，以滿足新聞時效性、準(zhǔn)確性和真實性三大特性，對相關(guān)物流機(jī)構(gòu)及用戶來說具有重要的意義。