劉 云，黃榮乘

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明 650050)

0 引 言

隨著網(wǎng)絡(luò)信息技術(shù)迅速發(fā)展，對(duì)新聞文本進(jìn)行有效快捷的自動(dòng)分類可以幫助人們提高信息檢索的效率[1-2]。通?？梢允褂弥С窒蛄繖C(jī)(support vector machine ，SVM)[3-4]、k近鄰(k-nearest-neighbor，KNN)[5]和樸素貝葉斯(naive Bayes，NB)[6]等分類算法對(duì)文本進(jìn)行分類，其中，分類算法的性能直接影響到了文本分類的時(shí)間和準(zhǔn)確率，所以尋找一個(gè)高效的分類算法成為了本文研究的重點(diǎn)。

Cui Limeng等[7]提出了一種基于文檔主題生成模型和支持向量機(jī)(latent dirichlet allocation-support vector machine，LDA-SVM)算法，該算法首先構(gòu)建每個(gè)類的LDA模型和待分類文檔的LDA模型，然后計(jì)算每個(gè)類和要分類的文檔之間的相似度并降序排列，最后使用SVM模型將文檔分為M個(gè)類中的一個(gè)特定類。胡吉明等[8]提出一種改進(jìn)的超球支持向量機(jī)(improved hyper-sphere support vector machine，IHS-SVM)文本分類算法，該算法基于增量學(xué)習(xí)和密度決策函數(shù)對(duì)原始 HS-SVM 進(jìn)行改進(jìn), 實(shí)現(xiàn)超球類支持向量的動(dòng)態(tài)改變, 準(zhǔn)確計(jì)算構(gòu)造超球支持向量機(jī)的決策函數(shù), 從而達(dá)到提高文本分類效果的目的。Nedungadi Prema等[9]提出了一種基于主成份分析和k最近鄰(principal component analysis-k-nearest-neighbor，PCA-KNN)混合分類算法相比，該算法首先計(jì)算訓(xùn)練數(shù)據(jù)的主要組成部分，將訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)按每個(gè)主要部分進(jìn)行投影，然后在每個(gè)投影空間執(zhí)行二進(jìn)制搜索并找到最近的L個(gè)鄰域，計(jì)算投影空間中測(cè)試數(shù)據(jù)與其鄰域之間的相似度，選擇最相似的k個(gè)鄰域，最后根據(jù)選定的鄰域預(yù)測(cè)測(cè)試數(shù)據(jù)的類別。其中，PCA-KNN分類算法在對(duì)文本進(jìn)行分類時(shí)能獲得較高的分類準(zhǔn)確率，但這個(gè)過程需要遍歷所有訓(xùn)練示例以找到其最近的鄰居，計(jì)算量較大，需要消耗大量時(shí)間。

IHS-SVM分類算法在對(duì)文本進(jìn)行分類時(shí)，只需要計(jì)算待分類文本與每一個(gè)超球心的距離就可得知該文本的所屬類別，故分類時(shí)間消耗少，但是分類精度不理想。LDA-SVM分類算法對(duì)文本進(jìn)行分類時(shí)消耗時(shí)間較少，但是在面對(duì)多分類的問題時(shí)分類準(zhǔn)確率相對(duì)較低。

1 相關(guān)工作

1.1 文本表示

由N個(gè)類的數(shù)據(jù)集，生成一個(gè)有著D個(gè)不同特征詞的字典，根據(jù)詞袋將每個(gè)文本x轉(zhuǎn)化特征向量的形式d=[x1,x2,…,xD]T，xi中的第i項(xiàng)對(duì)應(yīng)于字典中第i個(gè)特征詞在文本中出現(xiàn)的次數(shù)，它也被稱為詞語頻率(term frequency,TF)，每個(gè)類的TF分布通常可以用特定的多項(xiàng)分布模型來建模。

1.2 多項(xiàng)式樸素貝葉斯分類器

在樸素貝葉斯分類器中，在N個(gè)類別下對(duì)一個(gè)文本x進(jìn)行分類時(shí)，其中，文本x∈RD是有D個(gè)原始特征的R集合，根據(jù)最大后驗(yàn)概率規(guī)則，將x歸為后驗(yàn)概率最大的類別

(1)

(1)式中：p(x|ci)是樣本在第N類下的原始PDF；p(ci)是類的先驗(yàn)概率。通常p(x|ci)是未知的，需要從訓(xùn)練集中估計(jì)，但是對(duì)于高維數(shù)據(jù)，當(dāng)訓(xùn)練集有限的時(shí)，很難準(zhǔn)確估計(jì)出p(x|ci)，所以對(duì)樣本x進(jìn)行特征選擇：z=f(x)，其中，z∈RK是有K個(gè)特征的R集合，且K?D，這樣就可以用特征子集中的特征PDFp(z|ci)來簡(jiǎn)化原始PDFp(x|ci)的估計(jì)，根據(jù)最大后驗(yàn)概率規(guī)則有

(2)

由(2)式知，對(duì)數(shù)據(jù)特征降維后，所估計(jì)出的類的PDF的精度直接影響到了貝葉斯分類器的分類性能，所以需要通過提高PDF的精度來提高該分類器的分類準(zhǔn)確率。

多項(xiàng)式樸素貝葉斯分類器是用詞語頻率來表示文本的最著名分類方法之一，根據(jù)多項(xiàng)式分布，在每個(gè)類ci=1,2,…,N下都得到一個(gè)帶有D個(gè)特征詞的多項(xiàng)式分布p(x|ci):[pi,1,…,pi,D]，第N個(gè)類的原始PDF為

(3)

本文所提的分類算法基于指數(shù)分布族，通過將參考類別的PDF和第N個(gè)類的PDF用參數(shù)向量θ嵌入到一個(gè)原始PDF估計(jì)表達(dá)式中來構(gòu)建出每個(gè)類的PDF，這就需要構(gòu)建出一個(gè)參考分布。

通過給定的訓(xùn)練集，構(gòu)造出一個(gè)參考類別c0由N個(gè)類組成，參考類別的原始PDF為p(x|c0)滿足(3)式中具有D個(gè)特征詞的多項(xiàng)式分布，[p0,1,…,p0,D]中的第D個(gè)特征詞的概率為

(4)

所構(gòu)造的參考分布由所有類組成，包含了N類中所有數(shù)據(jù)的分布，由于該算法構(gòu)造的PDF運(yùn)用了這個(gè)參考分布，所以它成為了提高分類器分類性能的關(guān)鍵。

1.3 類特定的特征選擇算法

對(duì)于高維數(shù)據(jù)，需對(duì)樣本進(jìn)行特征選擇以減少計(jì)算負(fù)擔(dān)，其中，信息增益是一種有效的特征選擇算法，其通過某個(gè)特征項(xiàng)t在類別C中出現(xiàn)與否的文檔數(shù)來統(tǒng)計(jì)計(jì)算特征項(xiàng)t對(duì)類別C貢獻(xiàn)的信息量，即特征項(xiàng)t的信息增益，其定義為考慮出現(xiàn)前后的信息熵之差，其計(jì)算公式定義為

(5)

傳統(tǒng)特征選擇算法和類特定特征選擇算法的對(duì)比如圖1。由圖1a知，對(duì)于給定的N個(gè)類的訓(xùn)練數(shù)據(jù)集，首先通過字典用詞袋將每個(gè)文本轉(zhuǎn)換成向量d的形式，傳統(tǒng)特征選擇算法使用信息增益(IG)計(jì)算出每個(gè)單獨(dú)類的特征重要性，然后應(yīng)用全局函數(shù)(例如總和或加權(quán)平均)對(duì)所有類下的特征進(jìn)行處理后，將特征進(jìn)行排名后得到了一個(gè)所有類共用的特征子集。它只考察了特征對(duì)整個(gè)系統(tǒng)的貢獻(xiàn)，而沒有具體到某個(gè)類別上，且每個(gè)類別有自己的特征集合，有的特征詞對(duì)這個(gè)類別很有區(qū)分度，對(duì)另一個(gè)類別則無足輕重，所以這就降低了分類器的分類性能。

圖1 傳統(tǒng)特征選擇算法和類特定特征選擇算法的對(duì)比圖Fig.1 Comparison of traditional feature selection algorithm and class-specific feature selection algorithm

為了解決上述傳統(tǒng)特征選擇算法中使用一個(gè)共同特征子集，而忽略了在不同類別中特征詞區(qū)分度不同的問題，本文提出類特定分類算法，由圖1b知，首先基于信息增益(information gain,IG)計(jì)算出第N類訓(xùn)練文檔中每個(gè)特征詞的信息增益，并將特征詞排名后構(gòu)成一個(gè)新的第N個(gè)類的特征向量zN，針對(duì)N個(gè)類得到了N個(gè)不同的特征向量。因?yàn)閼?yīng)用了類特定的特征進(jìn)行分類，直接針對(duì)了類間的可分離性，使得分類器的分類性能得到提高。

由(5)式得，每個(gè)類其特征向量d中第t個(gè)特征詞在第N類下的信息增益為

(6)

為了將構(gòu)造的參考分布的特征PDF和類的特征PDF相結(jié)合，本文使用指數(shù)分布族，將這2個(gè)PDF通過參數(shù)θ嵌入到所構(gòu)造的PDF中。

2 基于指數(shù)分布族的貝葉斯類特定分類算法

2.1 基于指數(shù)分布族的PDF構(gòu)建

根據(jù)指數(shù)分布族定義有

p(x;θ)=b(x)exp(θT(x)-K(θ))

(7)

(7)式中：θ是自然參數(shù)；T(x)是充分統(tǒng)計(jì)量；K(θ)是對(duì)數(shù)配分函數(shù)，起歸一化作用，使得PDF滿足積分為1的條件。

通過(3)式和(4)式構(gòu)造了2個(gè)PDF分別為p(x|ci)和p(x|c0)，通過(7)式的指數(shù)分布族將參考類別的PDF和N個(gè)類的PDF用參數(shù)向量θ嵌入到一個(gè)PDF表達(dá)式中

p(x|ci;θ)=exp(θT(x)-K0(θ)+lnp(x|c0))

(8)

(8)式中：θ為指數(shù)分布族嵌入?yún)?shù)向量，θi=[θ1,θ2,…,θD],i=1,…,N，0<θ<1，由于訓(xùn)練集有限，不能準(zhǔn)確估計(jì)出類的原始p(x|ci)，所以通過特征降維后使用類的特征p(z|ci)來估計(jì)出類的原始PDF。其中，T(x)是參數(shù)θ的充分統(tǒng)計(jì)量，它可衡量出第N個(gè)類的原始PDF和參考類別的原始PDF之間的差異，其等于第N個(gè)類的特征PDF和參考類別的特征PDF之間的差異

(9)

通過(6)式得到了N個(gè)類的特征PDF后，如果在參考類別c0下已知p(z|ci)和p(z|c0)，就可以使用p(z|ci)估計(jì)出p(x|ci)。這些PDF都使用相同的參考類別進(jìn)行構(gòu)建，參考類別c0由N個(gè)類構(gòu)成，其潛在的概率空間是相同的，即使類的特征數(shù)量或類型發(fā)生變化，仍然可以對(duì)N個(gè)類的PDF進(jìn)行估計(jì)和比較。

(7)式中的對(duì)數(shù)配分函數(shù)K(θ)為

(10)

K(θ)可對(duì)估計(jì)的PDF進(jìn)行歸一化處理，使得PDF在0<β<1范圍內(nèi)積分為1，由(10)式得到

(11)

因?yàn)镸0(0)=M0(1)=1，根據(jù)赫爾德不等式[15]證明了M0(θ)是一個(gè)凹函數(shù)。

將(9)式代入(8)式中，通過使用第N類的特征PDF構(gòu)造出了第N類的原始PDF估計(jì)表達(dá)式

p(x|ci;θ)=

(12)

(12)式中：θ是個(gè)未知值，且θ的值決定了所估計(jì)的PDF的精度。根據(jù)KL散度知，類的原始PDF和估計(jì)的PDF之間的KL散度為

(13)

假設(shè)所估計(jì)出的類的PDF和原始PDF對(duì)統(tǒng)計(jì)量T(x)有相同的期望即EPθ[T(x)]=Ept[T(x)]，那么(13)式為

D(pt‖pθ)=D(pt‖pθ)-(θEpθ[T(x)]-K0(θ))=

D(pt‖p0)-D(pθ‖p0)

(14)

因?yàn)镈(pt‖p0)是固定的，要使原始的PDF和估計(jì)的PDF之間的KL散度D(pt‖pθ)最小，那么就使D(pβ‖p0)最大，因?yàn)?/p>

(15)

由(11)式知K0(θ)是凹函數(shù)，則θT(x)-K0(θ)是凸函數(shù)，根據(jù)凸優(yōu)化，可找到一個(gè)θ使得下列式子成立

(16)

(17)

(18)

對(duì)于一個(gè)N分類問題，最終通過用類的特征PDF估計(jì)出了原始的PDF，根據(jù)貝葉斯定理，制定以下分類規(guī)則

(19)

通過(19)式構(gòu)造的分類器，使用第N個(gè)類的特征PDF估計(jì)出了對(duì)應(yīng)類下的最優(yōu)PDF。

2.2 算法應(yīng)用分析

采用一個(gè)案例說明，由(14)式構(gòu)造出了第N個(gè)類的PDF優(yōu)化估計(jì)表達(dá)式為

p(x|ci,l;θi)=

(20)

(20)式中，充分統(tǒng)計(jì)量βi,k為

(21)

統(tǒng)計(jì)量的累計(jì)量生成函數(shù)為

(22)

通過N個(gè)類的訓(xùn)練集，由(6)式得到第N個(gè)類的特征PDF為p(zi|ci)和參考類別的特征PDF為p(zi|c0)。對(duì)于N個(gè)類，通過(17)式估計(jì)出了最佳的嵌入?yún)?shù)為

(23)

i=1,2,…,N

(24)

根據(jù)估計(jì)出的N個(gè)類的最優(yōu)PDF，由貝葉斯定理制定了以下分類規(guī)則

(25)

因?yàn)闃颖緮?shù)據(jù)維度高且訓(xùn)練集有限，不能準(zhǔn)確估計(jì)出類的原始PDF，從而基于指數(shù)分布族，用第N個(gè)類的特征PDF估計(jì)出了對(duì)應(yīng)類的最優(yōu)PDF。因?yàn)椴挥脤?shí)際測(cè)量類的原始PDF，且構(gòu)造的參考類別包含了所有類別，其利用了整個(gè)訓(xùn)練集的分布信息，所以這就成為了提高分類性能的關(guān)鍵。

對(duì)于一個(gè)N分類問題，基于指數(shù)分布族的類特定文本分類算法如下。

輸入：數(shù)據(jù)集；

fori=1:Ndo

1)通過(6)式計(jì)算出個(gè)第i個(gè)類下所有特征的IG分?jǐn)?shù)并降序排列后得到類特定的特征向量Zi；

2)通過參考分布和指數(shù)分布族，構(gòu)造出第i個(gè)類的原始PDF估計(jì)表達(dá)式(12)；

end

輸出：根據(jù)貝葉斯定理，通過(18)式，制定(19)式所示的分類規(guī)則。

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

在對(duì)文本進(jìn)行分類時(shí)，通常用準(zhǔn)確率[16]作為評(píng)估系統(tǒng)的指標(biāo)，定義為

(26)

(26)式中：TP表示正確判定屬于此類的文檔數(shù)；FP表示錯(cuò)誤判屬此類的文檔數(shù)；FN表示錯(cuò)誤判定不屬于此類的文檔數(shù)；TN表示正確判定不屬于此類的文檔數(shù)。

3 仿真分析

本文采用了路透社(REUTERS)的ModApte數(shù)據(jù)集[17]，包括各類新聞和金融數(shù)據(jù)。REUTERS中的ModApte數(shù)據(jù)集，由8 293個(gè)包含65個(gè)類(主題)的文檔組成，隨機(jī)選擇了4 994個(gè)文本作為訓(xùn)練集，3 299個(gè)文本作為測(cè)試集，REUTERS-10代表取數(shù)據(jù)集前10個(gè)類別，REUTERS-20代表取數(shù)據(jù)集前20個(gè)類別，在這2個(gè)數(shù)據(jù)集中，有18 933個(gè)原始特征尺寸。

為了驗(yàn)證本文所提分類算法的性能，本文將EF-MNB分類算法與PCA-KNN分類算法(參數(shù)K=5)，IHS-SVM文本分類算法(參數(shù)q=5，C=10，v=0.01)和LDA-SVM分類算法(參數(shù)M=3，α=0.5，β=0.05)進(jìn)行對(duì)比，在分類準(zhǔn)確率和分類耗時(shí)上評(píng)估3種特征選擇算法的性能，其中，特征詞數(shù)量從100—2 000個(gè)。

圖2和圖3是在REUTERS-10數(shù)據(jù)集和REUTERS-20數(shù)據(jù)集上分類結(jié)果，由圖2看出，對(duì)于REUTERS-10數(shù)據(jù)集，EF-MNB分類算法的分類準(zhǔn)確率始終高于PCA-KNN分類算法、IHS-SVM分類算法和LDA-SVM分類算法，且在特征數(shù)量為1 000時(shí)準(zhǔn)確率接近最大值，達(dá)到95.46%。由圖3看出，對(duì)于REUTERS-20數(shù)據(jù)集，特征數(shù)量在100—1 200內(nèi)，EF-MNB分類算法的分類準(zhǔn)確率大幅領(lǐng)先于其余2種分類算法，且在特征數(shù)量為200—400內(nèi)分類準(zhǔn)確率提升最大，當(dāng)特征數(shù)量為400時(shí)，分類準(zhǔn)確率高達(dá)90.51%，即該算法在相對(duì)較少的特征數(shù)量情況下，就能得到高分類準(zhǔn)確率。

圖2 在REUTERS-10數(shù)據(jù)集中的分類結(jié)果Fig.2 Classification results on REUTERS-10

圖3 在REUTERS-20數(shù)據(jù)集中的分類結(jié)果Fig.3 Classification results on REUTERS-20

表1和表2是在REUTERS-10數(shù)據(jù)集和REUTERS-20數(shù)據(jù)集上分類所消耗的時(shí)間。從表1看出，對(duì)于REUTERS-10數(shù)據(jù)集，在特征數(shù)量較少時(shí)，EF-MNB分類算法分類所需時(shí)間與其余3種分類算法比較接近，隨著特征數(shù)量的增加，分類效率差距逐漸變大。從表2看出，對(duì)于REUTERS-20數(shù)據(jù)集，EF-MNB分類算法的分類效率始終大幅領(lǐng)先與其余2種分類算法。

表1 在REUTERS-10數(shù)據(jù)集中的分類耗時(shí)

在REUTERS-10和REUTERS-20數(shù)據(jù)集中的比較得知，相比于在REUTERS-10數(shù)據(jù)集中4種分類算法的對(duì)比情況，在REUTERS-20數(shù)據(jù)集中，EF-MNB分類算法性能的優(yōu)化程度更高，即處理更多類的分類問題時(shí)，EF-MNB分類算法的分類性能更加突出。

表2 在REUTERS-20數(shù)據(jù)集中的分類耗時(shí)

4 結(jié) 論

對(duì)文本進(jìn)行有效快捷的分類可為人們提供更高質(zhì)量和智能化的信息服務(wù)，為了在較少的時(shí)間對(duì)文本進(jìn)行精準(zhǔn)分類，本文提出一種EF-MNB算法。給定N個(gè)類的訓(xùn)練集，首先基于信息增益，用類特定特征算法得到第N個(gè)類的特征子集,從中選出K個(gè)特征得到了第N個(gè)類的特征PDF和參考類別的特征PDF，然后根據(jù)指數(shù)分布族通過訓(xùn)練集估計(jì)出了第N個(gè)類下的最優(yōu)PDF，最后根據(jù)貝葉斯定理制定了分類規(guī)則。

仿真結(jié)果表明，對(duì)比LDA-SVM分類算法、IHS-SVM分類算法和PCA-KNN分類算法，EF-MNB分類算法運(yùn)用了類特定的特征PDF和參考類別的特征PDF來構(gòu)建出類的最優(yōu)PDF，在2個(gè)方面對(duì)PDF進(jìn)行了優(yōu)化：①該P(yáng)DF運(yùn)用了類特定的特征PDF直接針對(duì)了類間的可分離性；②該P(yáng)DF運(yùn)用了參考類別的PDF，其包含了所有類下全部數(shù)據(jù)的分布。通過這兩方面優(yōu)化，使得本文所構(gòu)造的分類器在使用少量特征數(shù)量進(jìn)行分類時(shí)，在較少的時(shí)間內(nèi)就可獲得高分類準(zhǔn)確率，特別是在處理更多類的分類問題時(shí)，相比于其他2種算法，該算法的分類性能將更加顯著。下一步將找出一種更高效的特征選擇框架，選擇出具有最大判別能力的特征進(jìn)行文本分類。