基于指數(shù)分布族的類特定文本分類算法

劉 云，黃榮乘

(昆明理工大學 信息工程與自動化學院，昆明 650050)

0 引 言

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

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

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

1 相關工作

1.1 文本表示

由N個類的數(shù)據(jù)集，生成一個有著D個不同特征詞的字典，根據(jù)詞袋將每個文本x轉化特征向量的形式d=[x1,x2,…,xD]T，xi中的第i項對應于字典中第i個特征詞在文本中出現(xiàn)的次數(shù)，它也被稱為詞語頻率(term frequency,TF)，每個類的TF分布通?？梢杂锰囟ǖ亩囗椃植寄Ｐ蛠斫！?/p>

1.2 多項式樸素貝葉斯分類器

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

(1)

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

(2)

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

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

(3)

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

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

(4)

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

1.3 類特定的特征選擇算法

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

(5)

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

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

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

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

(6)

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

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

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

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

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

(7)

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

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

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，由于訓練集有限，不能準確估計出類的原始p(x|ci)，所以通過特征降維后使用類的特征p(z|ci)來估計出類的原始PDF。其中，T(x)是參數(shù)θ的充分統(tǒng)計量，它可衡量出第N個類的原始PDF和參考類別的原始PDF之間的差異，其等于第N個類的特征PDF和參考類別的特征PDF之間的差異

(9)

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

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

(10)

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

(11)

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

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

p(x|ci;θ)=

(12)

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

(13)

假設所估計出的類的PDF和原始PDF對統(tǒng)計量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)

因為D(pt‖p0)是固定的，要使原始的PDF和估計的PDF之間的KL散度D(pt‖pθ)最小，那么就使D(pβ‖p0)最大，因為

(15)

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

(16)

(17)

(18)

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

(19)

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

2.2 算法應用分析

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

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

(20)

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

(21)

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

(22)

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

(23)

i=1,2,…,N

(24)

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

(25)

因為樣本數(shù)據(jù)維度高且訓練集有限，不能準確估計出類的原始PDF，從而基于指數(shù)分布族，用第N個類的特征PDF估計出了對應類的最優(yōu)PDF。因為不用實際測量類的原始PDF，且構造的參考類別包含了所有類別，其利用了整個訓練集的分布信息，所以這就成為了提高分類性能的關鍵。

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

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

fori=1:Ndo

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

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

end

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

2.3 評價指標

在對文本進行分類時，通常用準確率[16]作為評估系統(tǒng)的指標，定義為

(26)

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

3 仿真分析

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

為了驗證本文所提分類算法的性能，本文將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)進行對比，在分類準確率和分類耗時上評估3種特征選擇算法的性能，其中，特征詞數(shù)量從100—2 000個。

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

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

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

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

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

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

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

4 結 論

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

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