融合語義特征的加權樸素貝葉斯分類算法

邱寧佳，賀金彪，薛麗嬌，王 鵬，趙建平

(長春理工大學 計算機科學技術學院，吉林 長春 130022)

0 引 言

數據分析和挖掘已成為文本分類領域內研究的重點。樸素貝葉斯算法進行分類既簡單又高效，但由于算法本身的屬性條件獨立性假設回避了關聯關系，使得算法的分類效果有所降低，因此在提高樸素貝葉斯的分類性能問題上大多數學者做了廣泛的研究和改進。目前特征處理方面的改進主要有選出最優特征集[1-3]、結合特征選擇方法修改權重[4-6]等方法，以提高算法的分類精確度；羅慧欽等在隱樸素貝葉斯模型中加入文本屬性的依賴性和獨立性約束條件，從而提高了文本情感分類的準確性[7]。此外，針對提取的不同關鍵特征重要程度的判定問題，一些學者通過構建相應的加權函數計算各特征的不同權值[8-10]，用于區分不同特征類別的貢獻度來改善樸素貝葉斯模型的性能。Jiang等提出根據不同類中屬性分配特定權重的細粒度加權方法，使模型在分類性能上具有一定優勢[11]；Yu和Lee分別使用屬性值之間差異計算和KL測度方法，對特征項的權值分配相應權重，顯著提高了樸素貝葉斯的性能[12，13]。

上述研究均在不同程度上提高了樸素貝葉斯算法的分類性能，但缺少語義關聯性研究方面的探討，在此基礎上本文綜合考慮特征處理和屬性加權，提出一種融合語義特征的加權樸素貝葉斯分類算法。首先在傳統TextRank算法(圖模型排序算法)的基礎上，將特征間的語義相關性引入到圖模型中，通過Google距離求解節點的初始權重。然后使用特征加權的方法來降低獨立性假設的影響，最后利用改進的加權樸素貝葉斯模型進行分類。

1 特征提取

基于圖模型的TextRank算法在計算時單純的設定所有分詞初始權值均等，忽略了分詞本身的屬性，直接影響分類的效果。本文利用詞語間語義相關性重新計算節點權值，實現TextRank算法的改進工作。

1.1 TextRank算法原理

傳統的TextRank算法是由PageRank改進而來，將每個詞語作為網頁節點根據重要程度進行連接構造帶權網絡圖模型，并利用投票機制對節點進行排序，最終選擇TOP-K個詞語作為候選關鍵詞。TextRank是一種有向帶權圖模型，表示為G=(V,E)， 其中V是圖模型構成的節點集合，E是圖模型構成的邊集合，具體的圖模型如圖1所示。

圖1 TextRank關鍵詞圖模型

圖中wji為任意兩節點Vi與Vj之間邊的權重，對于給定的任意節點Vi，In(Vi) 表示Vi節點的所有入度節點集合，Out(Vj) 表示Vi節點的所有出度節點集合，δ為阻尼系數，表示當前節點能夠跳轉到其它任意節點的概率，節點S(Vi) 的權重計算公式為

(1)

1.2 NGD-TextRank特征提取算法

在TextRank算法中認為任意兩個節點之間的聯系是相同的，設定初始權重均等，忽略了節點間語義關聯性對節點自身產生的影響。針對上述問題本文采用節點間的語義相關性來表示節點間的權重，Google距離通過衡量語義相關性，應用于搜索引擎的結果匹配程度上具有較高的精確度，在處理分析文本概念間相關性和語義標注領域能取得較好的效果。本文使用Google距離計算節點間語義相關性作為節點間的初始權值，通過TextRank模型迭代訓練至收斂得到各節點的最終權重值，再根據最終結果進行TOP-K排序提取關鍵特征。

設定存在文檔集合D={d1,d2…,dn}， 第n個文檔內特征集合V={v1,v2,…,vi,…,vj}， 利用Google距離計算詞語vi，vj在當前文檔中出現頻率的高低來測量概念間的語義距離，分析語義層面上的聯系程度。詞語間的語義距離越小，表明相關聯系越緊密，反之越疏遠。因此，使用Google距離計算兩個不同特征間的語義相關性來表示權重wji， 其任意兩個特征的語義相關性可表示為

(2)

式中：df(vi) 代表包含了詞語vi的文檔數量，df(vj) 代表包含了詞語vj的文檔數量，df(vi,vj) 代表同時包含了詞語vi和詞語vj的文檔數量，N代表文檔集的總數。

最終的權重計算公式為

wji=(wNGD(vi,vj)+1)-1

(3)

與傳統算法相比，上述wNGD計算方法從語義層面上反映了詞語之間的聯系程度，引入語義聯系計算節間點的權值不僅能彌補設定初始權值相等的不足，還能在一定程度上減少不相關冗余特征的出現，而具有高相關性的詞語能夠獲得更高的權值。使用改進的NGD-TextRank算法得到的關鍵特征相較于原算法質量更高，更適用于分類。下面給出特征提取的算法流程：

算法1： NGD-TextRank算法

輸入： 數據文檔集合D={d1,d2…,dn}， 關鍵特征集合T， 關鍵特征個數K

輸出： 更新后的關鍵特征詞集合T={t1,t2…,ti}

(1) 預處理得到詞語集合V={v1,v2,…,vi,…,vj}

(2) setT=? //設定初始關鍵特征詞集合為空

(3) setK//設定取前K個關鍵特征詞

(4) for eachD

(5) for eachvi,vjinV

(6) 通過式(2)計算詞語間語義相關性wNGD(i,j)

(7) end for

(8) end for

(9) 根據式(3)計算初始權重wji

(10) for eachviinV

(11) 計算S(Vi)

(12) end for

(13) 對vi按S(Vi) 值降序排序

(14) 取TOP-K特征加入特征集合T

(15) 輸出更新后的關鍵特征詞集合T={t1,t2…,ti}

2 特征加權樸素貝葉斯算法

2.1 樸素貝葉斯算法

樸素貝葉斯算法是假設各特征相互獨立的分類方法，求解特征項ti在相互獨立出現的條件下屬于各個類別cj的概率P(cj|ti)， 則將歸屬類別的最大概率結果作為待分類文檔的真正類別，具體的樸素貝葉斯公式為

(4)

然而，樸素貝葉斯公式在分類過程中屬性之間相互獨立在現實生活中往往很難滿足。在文本分類中，各特征項之間必然會存在一定的聯系，忽視樸素貝葉斯算法特征獨立的假設會降低算法的分類性能。

2.2 加權樸素貝葉斯算法

Hellinger距離具有對稱性可以衡量兩個概率之間的距離，因此能夠作為兩個分布之間差異的適當度量函數。本文采用該距離函數對某個特征項在分類過程中所含信息量的多少進行度量，表示為文本類別在某個特征詞出現前后時概率之間的差異，具體的計算公式為

(5)

式中：p(cj|ti) 表示含有特征詞ti的cj類文本在整個文本集中的概率，p(cj) 表示cj類文本在整個文本集中的概率，n表示類別總數。

上述Ht衡量了同一特征在不同類別間的影響程度，其值越大代表該特征攜帶的信息量越大，越具有類別代表性，說明該特征在劃分類別能力上的貢獻度越大。然而上述加權過程忽略了特征詞在某一類別內的集中情況，即詞頻集中度對特征權重的影響；同時沒有體現該類包含特征項的文檔分布，以及文檔空間內不同特征個數對特征詞類別代表性的影響，因此應該從文檔差分度上考慮特征詞在分類過程中的重要性。

本文考慮詞頻集中程度對特征詞權重的影響去構建加權函數，以類別cj中特征詞ti的數量占總特征詞的比例表示特征詞ti在類別cj中出現的可能性，并根據特征詞ti在待分類文本中的詞頻，定義了詞頻集中度加權函數，具體公式表示為

(6)

式中：cj_tf(ti) 表示在類別cj中特征詞ti的詞頻，cj_tf表示類別cj中的特征詞總數，d_tf(ti) 表示在當前文檔中特征詞ti的詞頻。從詞頻集中度可以量化該特征詞在某一類中的分布情況，如果特征詞的詞頻集中度較高，說明此特征詞具有較均勻的類內分布，就越能代表該類別。

在某個給定的類別中，包含特征項的文檔出現頻率以及文檔中含有的不同特征詞數量的差異，在很大程度上體現特征詞分類能力的高低。在考慮類內文檔分布情況時，本文關注了含有特征詞ti的文檔空間內不同特征的個數，即文檔特征空間大小，以此為依據定義了文檔差分度加權函數，具體公式表示為

(7)

式中：cj_df(ti) 表示在類別cj中含有特征詞ti的文檔數，cj_df表示類別cj中的文檔總數，cj_d(tfavg) 表示類別cj的各文檔中不同特征詞的平均數，即文檔特征空間的大小。分類能力強的特征詞應該分布在該類的多數文檔中，也就是該類中包含特征詞ti的文檔占文檔總數的比例越高，特征詞越具有類別代表性；同時該類各文檔中不同特征詞的數量越少，說明該類文檔的特征空間越小，此時特征詞分類的貢獻程度越強。

結合上述思想，本文提出特征加權樸素貝葉斯公式，考慮特征詞在類別間的信息量大小，并分析詞頻集中度和文檔差分度對特征詞重要性的影響，綜合計算特征項的權重值，最終得到改進的加權樸素貝葉斯公式和權重計算公式如下

(8)

w(i,j)=Ht×TCF×TDS

(9)

其中，w(i,j) 值越大，特征詞獲得的權重越高，對分類的貢獻程度越大；反之，w(i,j) 值越小，特征詞獲得的權重越低，對分類的貢獻程度越小。使用上述特征加權方法是對每個特征項約束條件的放寬處理，通過對每個特征項重新估量分配不同的權值，能夠彌補傳統樸素貝葉斯算法在分類過程中各屬性相互獨立假設的不足，以提高分類器性能。

3 NTWNB算法

屬性獨立性假設一直是樸素貝葉斯分類算法面臨的問題，解決屬性獨立假設問題對最終的分類結果影響較大。本文提出一種融合語義特征的加權樸素貝葉斯分類算法(NTWNB)，首先對分類文本進行數據預處理，并使用Google距離重新計算詞語間相互關聯程度來代替原始權重改進TextRank算法進行特征提取，然后以提取的關鍵特征詞集合構建向量模型，并從特征詞信息量、詞頻集中度和文檔差分度3個方面分析特征詞的綜合權重，使用改進的加權樸素貝葉斯分類算法進行分類，整體解決方案如下：

(1)數據預處理。將訓練文本經過數據解析、進行分詞、過濾停用詞等操作后得到初始詞語集合。

(2)關鍵特征選取。依次對初始集合中詞語使用Google距離計算語義相關性得到新的權重，將新的權重值帶入到TextRank中重新計算，根據計算結果進行排序選取前TOP-K作為關鍵特征集合。

(3)向量模型構建。使用(2)中的NGD-TextRank算法提取出的關鍵特征進行向量化表示，構建特征向量模型。

(4)綜合權重計算。分別使用Ht，TCF和TDS表示特征信息量、詞頻集中度、文檔差分度，綜合分析得到特征項的權重表示w(i,j)， 并計算每個特征項的權重值。

(5)特征加權改進。根據(4)中的計算權重方法改進傳統樸素貝葉斯公式，得到加權樸素貝葉斯算法。

(6)文本類別輸出。對待分類文本使用(5)中分類器模型進行類別預測。以輸出結果作為該文本類別。

完整的算法結構如圖2所示。

圖2 算法結構

4 實驗及結果分析

4.1 實驗環境和數據

實驗在Pycharm平臺上使用Python3.6語言開發，實驗配置為IntelCore i5-7500 @3.40 GHz四核，16 GB內存，windows10操作系統。為了驗證本文提出的算法可行性，本研究采用的熱線咨詢數據來自于某運營商客服熱線平臺數據庫，該平臺每月統計的用戶咨詢文本數量在 5-10 萬條不等，便于研究選取訓練集30 000條文本、測試集6000條文本作為數據集對象，每條文本中記錄了用戶整個通話過程的全部內容。設計實驗時具體的數據集特征見表1。

表1 數據集特征內容

4.2 評價指標

本文使用上述實驗數據進行二分類，為了對上述算法的優劣性進行評估，選取ROC(receive operating characte-ristic)曲線及曲線下面積AUC(area under curve)值作為本文提出的算法評估標準，由式(10)、式(11)可以看出使用偽正率(FPR)和真正率(TPR)分別作為橫縱坐標繪制曲線并計算AUC值，可以得出數值越大算法分類性能越好。

以用戶查號意向監測為例，設TP表示用戶意向為查號且被分類為查號的情況，FP表示為用戶意向為非查號但被分類為查號的情況，FN表示為用戶意向為查號但被分類為非查號的情況，TN表示為用戶意向為非查號且被分類為非查號的情況。則偽正率表示為在所有實際意向為非查號的樣本中被錯誤地預測為查號的比例，公式為

(10)

真正率表示為在所有實際意向為查號的樣本中被正確預測為查號的比例，公式為

(11)

4.3 改進算法實驗驗證

實驗1：特征提取效果對比分析。

本文分別使用改進前后的特征提取算法對同一數據集30 000文檔數據做特征提取分析，表2列出了兩種算法選用特征詞數量50為間隔進行對比，分析特征數量變化時因提取的特征詞不同造成的覆蓋文檔數和準確率變化對比。

表2 2種特征提取算法對比

通過表2可以發現兩種算法都能夠有效地利用詞之間的關聯性取得較好的效果，而在相同維度下改進的NGD-TextRank算法與傳統算法相比提取到的關鍵特征文檔覆蓋率更高，這是因為基于語義距離計算的特征權重充分體現詞之間在文檔中相關聯系的重要性，引入語義距離對相關特征節點圖邊權重進行重新計算能夠獲得更重要關鍵特征，表明在特征提取時融入語義相關性具有更好的特征提取效果。從不同特征維度分析，可以看出改進后的算法隨著特征詞數量的增加整體呈現上升的趨勢，而原始算法則隨著特征詞的增加準確率上升到某一最高點后逐漸開始下降，這種現象是因為特征詞中含有部分關聯性弱、代表性差的冗余特征造成。當特征詞維度為400時傳統算法準確率達到最高值，而改進后的算法在特征維度為250時已經實現原始實驗的分類效果并在后期持續上升，說明改進后的算法可以篩選出具有高分類能力的代表特征，剔除冗余屬性。上述對比可以看出改進后的算法具有降維的作用，用更少的語義特征可以得到更準確的分類效果。

實驗2：加權效果驗證。

為了驗證權重前后變化的合理性，表3展示了部分特征詞以及它們在權重計算前后的對比結果。同時考慮本文改進算法的有效性，設計實驗使用傳統TextRank-NB算法以及其加權形式和融合形式進行ROC曲線分析和AUC值比較結果如圖3所示。

表3 加權前后特征權重對比

圖3 改進算法ROC曲線和AUC值對比

由表3可以看出選取的特征詞通過使用Hellinger距離衡量了特征詞的信息量大小，信息量越大說明其分類貢獻度越大，并根據特征詞在某一類別中集中度的提高來提升類別代表能力，以及分類貢獻度高的特征詞其文檔差分度越高來體現特征詞分類貢獻程度的差異。綜合考慮上述因素共同作用下得到的最終權重可以看出改進后的“想查”、“查下”等權重提升較大，更能反映出類別的代表能力，反之“電話”、“醫院”等權值相應降低，由此可以看出對類別代表能力弱的特征詞經過重新計算后權重都有相應下降變化，說明了特征詞權重變化的合理性。通過圖3可以看出，在使用NB或WNB相同分類模型時，結合改進的NGD-TextRank特征提取算法得到的ROC曲線要優于傳統TextRank算法，對應的AUC值也提高了2%，這主要是因為改進算法考慮語義重新計算后提取的特征詞更能發揮分類作用，明顯提高算法的分類性能。在使用TextRank或NGD-TextRank相同特征提取算法時，使用改進的加權樸素貝葉斯分類器要比傳統的分類器ROC曲線效果更突出，改進分類器的AUC值相應提高了7%，說明了傳統樸素貝葉斯算法由于其條件獨立假設限制了特征詞的作用而影響了分類的性能，通過特征詞的信息量、特征分布情況和文檔特征數量的加權實現了分類器綜合考慮特征的權重，增強了分類過程中特征詞之間的差異性以提高分類性能。NGD-TextRank-WNB算法的ROC曲線和AUC值均高于其它算法表現，表明本文算法能夠保證提取特征詞的優越性時，同樣也解決了傳統樸素貝葉斯方法沒有根據不同特征詞其重要程度進行衡量影響分類準確率的問題，因此在進行分類時具有優勢，是一種較好的分類算法。

實驗3：多數據集普適性驗證。

為了更好地體現本文提出的NTWNB算法的分類效果，通過對比各算法在不同數據集上的實驗結果進一步分析。實驗選取了表1中4個具有代表性的數據集，其中前兩個數據集為二分類不平衡數據集；選取的數據集3和數據集4分別是二分類和多分類平衡數據集，同時數據集的樣本存在明顯差異。在各類型數據集上設計實驗與文獻中提到的LAWNB[14]和TWNB[15]以及傳統NB算法進行對比，表4記錄了算法在各數據集上的分類性能對比結果，4種算法的F值綜合評價指標如圖4所示。

表4 4種分類算法性能對比

圖4 不同數據集各算法F值對比

通過表4可以看出，4種算法在不同數據集上的分類性能具有明顯的不同，這主要因為數據集分布情況對分類結果具有較大影響，但是本文改進的NTWNB算法在各數據集上表現最優，使用特征詞的信息量、特征分布情況和文檔特征數量的加權改進處理相應數據集得到的準確率、召回率都高于其它算法，說明本文提出的特征加權算法是提高樸素貝葉斯分類性能的一種有效方法。由圖4可以看出，在4個不同數據集中傳統的樸素貝葉斯算法F值皆為最低，經過相應改進的算法均有所提高。在不平衡數據集上，其它改進的算法性能提升到85%，而本文提出的分類算法性能提升更為明顯達到了92%，充分驗證了針對數據集樣本差異考慮詞頻集中度和文本差分度進行特征加權的重要性。在二分類和多分類平衡數據集中，本文改進的算法在分類表現上提升幅度相近，從而體現出本文提出的算法既適用于二分類又適用于多分類。綜合對比本文提出的算法具有更好的分類效果。

5 結束語

本文針對傳統特征提取算法忽略語義相關性以及傳統樸素貝葉斯算法的條件獨立假設性而引起的分類準確率降低問題，提出一種改進的NTWNB算法。首先融入詞語間語義相關性對TextRank算法節點初始權重進行重新計算，提取出具有相關代表性的關鍵特征；然后在分類過程中以特征詞的Hellinger信息量作為初始權重，結合特征和文檔分布情況求解最優的加權函數組合；最后使用加權函數改進樸素貝葉斯分類模型。采用ROC和AUC作為本文算法的評價指標，通過與其它算法在不同數據集上的實驗對比，最終得到本文改進的算法具有更高的分類效果。但是本文的方法在多分類數據集上的表現仍有待提升，下一步將針對多分類問題進一步研究，擴大本文算法的普適性。