一種用于微信信息分類的改進貝葉斯算法

張穎江，庫凱琳

一種用于微信信息分類的改進貝葉斯算法

張穎江，庫凱琳

（湖北工業大學計算機學院，湖北武漢430068）

微信的快速普及加快了信息的傳播，隨之而來的廣告、詐騙等信息嚴重困擾人們的生活。針對樸素貝葉斯對信息分類時考慮所有特征并將特征賦予相同權值兩方面的缺陷，提出一種用于微信信息分類的改進貝葉斯算法。采用改進的互信息進行特征選擇，提取關鍵特征，通過改進TFIDF對特征加權，優化樸素貝葉斯的分類性能。實驗結果表明，改進的貝葉斯算法能有效選擇關鍵特征屬性，提高微信信息分類的精準度。

貝葉斯；微信信息；特征提取；特征加權；信息分類

隨著微信已成為人們日常交流和溝通的一種重要方式，微信平臺的信息安全問題急需解決。目前對微信信息的監管主要是通過設置黑名單的形式，即大量收集傳播垃圾信息的微信用戶ID，并將其加入黑名單來阻斷信息的傳播。但由于微信用戶量大，增長速度快等特點，傳統的設置黑名單的方式很難從源頭上杜絕垃圾信息的產生。并且實施周期長，工作量大，效果顯微。

微信信息的處理本質上是對文本信息的處理。常見的文本分類器包括決策樹（Decision Tree）［1］分類器、樸素貝葉斯（Naive Bayesian）［2］分類器、支持向量機（Support Vector Machine）［3］等。樸素貝葉斯分類器具有訓練和分類速度快的特點，許多學者對其進行深入研究并提出了一些改進方法。鄧桂騫提出一種條件屬性相對于決策屬性的相關性和重要性的屬性權值計算方法［4］；李靜梅提出一種通過EM算法（期望值最大算法），自動增加訓練量，得到較為完備的訓練庫，提高樸素貝葉斯的分類精度［5］；趙文濤，孟令軍等人針對樸素貝葉斯算法下溢問題，對算法基本公式進行優化改進，提出一種新的CITNB算法并通過實驗驗證其分類性能遠優于樸素貝葉斯分類器［6］，以上改進方法都是針對樸素貝葉斯屬性權值相同進行的改進。

針對樸素貝葉斯屬性選擇和屬性加權兩方面的缺陷，提出采用互信息對文本特征屬性進行選擇，并針對傳統互信息的缺陷提出改進措施，對選取的特征屬性采用改進的TF－IDF加權［7］，將改進后的貝葉斯算法用于微信信息分類。與傳統貝葉斯算法、基于TF－IDF的樸素貝葉斯算法相比，該算法在查準率和查全率方面都有顯著提升。

1 樸素貝葉斯分類

樸素貝葉斯（NB）分類是一種十分簡單的分類算法，其基本思想可概括為：對給出的待分類項，求解出在該分類項出現的情況下各類別出現的概率，并認為該分類項屬于類別中概率最大的類，樸素貝葉斯有如下定義：

設A＝｛a1，a2，a3，…，am｝為一個待分類樣本，每個ai為A的一個特征屬性。有類別集合B＝｛b1，b2，b3，…，bn｝，計算p（b1｜a），p（b2｜a），p（b3｜a），p（b4｜a），如果

則a∈bk。根據貝葉斯定理：

p（a）對所有類均為常數，最大化后驗概率p（bi｜a）可轉化為最大化先驗概率p（a｜bi）P（bi）。若訓練數據集有許多屬性和元組，假設各屬性相對類別條件獨立，即：為避免（3）式中出現乘積為0的結果，需要對公式進行平滑處理，常用的方法是對式（3）進行拉普拉斯平滑：

其中：N（bi）表示bi的文檔個數，∑kN（bk）表示集中文檔總個數，Nij表示特征屬性ai在類別bj的文檔中出現的次數，M表示特征詞個數，∑kN（ckj）表示bj類中所有詞出現的次數。

計算過程中由于p（ai｜bj）、p（bi）的值都很小，兩者相乘的結果偏小會導致精度下降，常用的做法是取對數進行運算，可減少計算開銷并提高了計算結果的精度。

樸素貝葉斯在分類時有兩個條件較為苛刻：（1）條件獨立性假設：NB分類假設樣本各特征之間相互獨立，該假設在實際應用中往往是不成立的，從而影響了分類的正確性。（2）各屬性權值都設為1：NB分類算法認為樣本各屬性具有相同的權值，但是在實際分類中，不同類別的樣本屬性出現的概率并不相同，將所有屬性的權值設為1，影響NB算法的精準性。本文針對以上NB算法的局限性提出一種改進的貝葉斯算法用于微信信息的分類，并將實驗結果進行對比，給出結論。

2 改進的貝葉斯算法

2.1 特征提取

微信信息可看作為文本特征向量，原始的特征向量空間由出現在微信信息中的所有詞組成，如果將出現的所有詞都作為特征向量的話，那么特征向量空間通常會維度過高，若直接對這種高維度的樣本空間進行訓練和分類，需要很大的計算開銷，且無用的特征信息參與計算會導致分類不精準。通常在對樣本進行訓練前，在不影響分類精準性的前提下盡可能剔除無用的特征屬性，這個過程稱為降維。在特征提取前，首先對特征向量空間人工降維，去掉一些常用的數詞、量詞、語氣詞等，這類詞對分類結果沒有影響，但是會造成很大的計算開銷。

本文采用MI互信息（Mutual Information）［8］進行特征提取，MI計算詞元ai與類別bi之間的相關度作為特征提取的標準，定義如下：

其中p（a）為單詞出現的概率，p（bi）為類別bi出現的概率，p（a∩bi）為兩者同時出現的概率。式（6）可簡化為：

N表示訓練集中樣本總數，A表示詞元a與類別bi同時出現的次數，B為詞元a出現類bi不出現的次數，C為類bi出現但詞元a不出現的次數，式（7）表示的詞a與各類別bi之間的互信息。

若存在m個類別，則特征項a與m個類別分別有m個互信息，常用的方法是求平均互信息，平均互信息的計算公式為：

傳統互信息在特征提取時，有兩個突出的缺陷：（1）不考慮詞頻，更趨向于低頻詞匯；（2）忽略負相關特征，特征與類別的負相關部分會導致該特征的權值降低［8］。針對以上兩個缺陷帶來的分類性能較低的問題，本文采用改進的互信息進行特征提取。

首先，在特征提取時考慮詞頻信息。一般認為：詞頻越高、集中度越強的詞對文本分類作用越大，而傳統互信息在進行特征選擇時通常是詞頻較小的詞獲得較大的互信息，與實際預期的情況不符，因此將詞頻、集中度等因素考慮進去采用改進的互信息進行特征提取。為此引入特征詞a對于類別bi的先驗概率p（a｜bi），表示特征詞a在bi中出現的頻度，其參數公式表示為X＝p（a｜bi），同時引入后驗概率p（bi｜a），表示特征詞a出現同時又屬于類別bi的概率來表示其集中度，其參數公式表示為：

其次，在計算互信息時會出現負數的情況，特征項a與類別b不相關時，互信息為0，當特征項a在類別b中很少出現時，互信息為負值，這稱為特征項a與類別b負相關。在計算中負相關會降低分類效果，但在實際情況中，一個特征若出現在少數類別中，這對分類具有較大的區分性。分析式（6）可知，在p（a∩bi）較小而p（a）較大時，MI（a）取值為負，且MI（a）的值隨p（a）變大及p（a∩bi）變小而變小，但在實際情況中，特征a的區分性隨著p（a）變大及p（a∩bi）變小而變大。針對此情況，本文對互信息取絕對值進行計算，該做法相對更為合理。綜合傳統互信息提取特征的缺陷來考慮，本文提出一種改進的互信息方案來提取特征，新的互信息計算公式可以表示為：

通過限定閾值，就可以對互信息選取特征的缺陷進行很好地補充。

2.2 特征加權

傳統貝葉斯算法中認為所有的特征屬性具有相同的權值（即將所有的屬性權值設為1），但在實際應用中，應賦予特征屬性不同的權值。如果某個特征在某個文本中重復出現，而在別的文本中很少出現，就可以認為該特征具有較好的區分性，應賦予其較大的權值。特征權值的計算方法有很多，詞頻權值、布爾權值、TFIDF都是常用的計算權值的方法［9］。TFIDF［10］用詞頻乘以逆文檔來表示特征項的權值。TF表示特征項t在文檔d中出現的頻率，IDF表示特征項t在整個文檔集中的分布量化［11］。TFIDF公式：

其中，wik表示文檔i中第K維的向量值，tfik表示文檔i中第K個特征值的TF值，N表示文本集的文檔數，nk表示文本集中出現該特征項的文本數。將TFIDF歸一化后得

TFIDF的局限性表現在：若某一特征在某一類別文檔中大量出現，而在其他類別文檔中很少出現，或者某個特征只在某一類別的少量文檔中大量出現而在別的文檔中很少出現，這樣的特征應該具有很好的區分性，應該賦予較大的權值，但實際上在式（11）中卻不能體現出來，相反IDF更趨向于賦予少量出現的特征較大的權值，這與實際情況并不相符。TFIDF考慮特征與文檔之間的信息，而忽略特征與類別的關系。為此，本文將特征的類別信息考慮進TFIDF進行特征加權，提出一種信息特征加權函數TFIDF＊。改進的TFIDF＊函數引入特征類函數K，其中

該函數考慮詞條i在某一具體類中的文檔出現的概率。改進的TFIDF＊函數定義如下：

式中，nk表示包含詞條i的文檔總數，cmax表示包含特征i最多的類中文檔數量。特征類函數設計的思想就是將特征與文本類別結合考慮，彌補TFIDF只考慮文本特征與數量的不足。如果特征在某一類文本中出現的次數較多，那該特征就可以很好地代表該類別，該類加權的結果值就大，因此，特征i在某一類中越重要，特征類函數權值也就越大。

3 實驗結果與分析

為驗證改進算法的可行性和有效性，設計實驗采用本文改進的互信息對特征屬性進行選擇，并對選擇后的特征采用改進TF－IDF賦予不同權值，通過貝葉斯公式計算概率得到最終的分類結果。實驗數據集主要采用python網絡爬蟲和人工搜索的方式收集。數據來源是一些微信公眾號推送的消息，共收集測試信息包含體育、健康、教育、科技、軍事、文化等6類信息共2264條，采用其中的1509條作為訓練集，其余的755條作為測試集用于測試。各信息分布情況見表1。

表1 數據集

本文采用查全率R和查準率P作為評測指標，計算公式如下：

查全率和查準率從兩個不同方面反映了分類器的性能。

圖2 查準率

從圖1和圖2的測試結果中可以看出：采用樸素貝葉斯對樣本進行分類，其分類效果明顯低于改進后的貝葉斯的性能。分析可知其原因主要有以下幾個方面：本文在樸素貝葉斯分類的時候采用的是未改進的互信息方法挑選特征值，同時采用樸素貝葉斯的思想，認為所有的屬性權值相同，全部設為1，導致其分類結果不盡人意，而本文提出的改進的貝葉斯采用改進的互信息提取特征，考慮互信息的負相關影響，將詞頻因素考慮進特征提取，同時使用改進的TFIDF對提取出的特征加權，從測試結果可以看出分類性能高于改進之前。

為驗證本文提出的改進貝葉斯算法的穩健性，采用不同數量的訓練集作為樣本進行訓練，觀察訓練樣本數量對分類準確性的影響，實驗結果見圖3。

圖3 樣本數量對分類結果的影響

從圖3可以看出，隨著訓練樣本的不斷增加，改進的貝葉斯分類器趨于穩定，并保持較高的分類性能。而樸素貝葉斯分類器在訓練樣本增加之后性能也得到提高，但整體分類性能沒有改進貝葉斯分類性能高。可以看出，樸素貝葉斯在大樣本訓練集中具有較好的分類性能。而改進貝葉斯在小樣本區間也具有較好的分類性能。

4 結語與展望

采用改進的貝葉斯分類器對微信信息進行分類，使用改進的互信息提取特征，然后使用改進的TFIDF對特征進行加權，最終較樸素貝葉斯取得了更好的分類效果。改進的貝葉斯算法在小樣本區間也表現出較好的分類性能，可以將本方法及后續改進方法用于垃圾郵件檢測和入侵檢測系統中。

［1］ Carreras X，Marquez L.Boosting trees for anti－spam email filtering［J］.2001，3（4）：1306－1311.

［2］ Androutsopoulos I，Koutsias J，Chandrinos K V，et al.An evaluation of naive bayesian anti－spam filtering［J］.Tetsu－to－Hagane，2000，cs.cl／0006013（2）：9－17.

［3］ Cortes C，Vapnik V.Support vector networks［J］.Machine Learning.1995，20（1）：273－329.

［4］ 鄧桂騫，趙躍龍.一種優化的貝葉斯分類算法［J］.計算機測量與控制，2012，20（1）：199－202.

［5］ 李靜梅，孫麗華.一種文本處理中的樸素貝葉斯分類器［J］.哈爾濱工程大學學報，2003，24（1）：71－74.

［6］ 趙文濤，孟令軍.樸素貝葉斯算法的改進與應用［J］.測控技術，2016，35（2）：143－147.

［7］ Salton G，Yu C T.On the construction of effective vocabularies for information retrieval［J］.Acm Sigplan Notices，1973，10（1）：48－60.

［8］ Zheng Z，Wu X，Srihari R.Feature selection for text categorization on imbalanced data.［C］／／Acm Sigkdd Explorations Newsletter，1931：80－89.

［9］ 張保富，施化吉，馬素琴.基于TFIDF文本特征加權方法的改進研究［J］.計算機應用軟件，2011，28（2）：17－20.

［10］Salton G，Introduction to Modern Information Retriveval［M］.New York：McGraw Hill Book Company，1983.

［11］魯松，李曉黎，白碩.文檔中詞語權重計算方法的改進［J］.中文信息學報，2000，14（6）：8－20.

［12］施聰鶯，徐朝軍，楊曉江.TFIDF算法研究綜述［J］.計算機應用，2009（29）：167－180.

An Optimized Bayesian Classification Algorithm for WeChat Information

ZHANG Yingjiang，KU Kailin
（School of Computer Science，Hubei Univ.of Tech.，Wuhan 430000，China）

The prevalence and development of WeChat has facilitated the dissemination of information.However，it also comes with advertising and fraudulent information，which brings a lot of troubles to people’s lives.For the two important factors that naive bayes considering all the features and characteristics are given the same weight.We put forward an improved bayes algorithm.Selecting features by improved mutual information and weighting by improved TFIDF to optimize the bayesian classification performance.Experimental results show that the improved bayes algorithm can effectively select key features and improved classification precision

bayes；WeChat information；feature extraction；feature weighting；information classification

TP391.1

A

［責任編校：張巖芳］

1003－4684（2017）04－0051－04

2016－06－06

張穎江（1959－），男，北京人，湖北工業大學教授，研究方向為計算機網絡安全

庫凱琳（1991－），男，湖北黃岡人，湖北工業大學碩士研究生，研究方向為信息處理與網絡安全