張穎江，庫凱琳

一種用于微信信息分類的改進(jìn)貝葉斯算法

張穎江，庫凱琳

（湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，湖北武漢430068）

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

貝葉斯；微信信息；特征提?。惶卣骷訖?quán)；信息分類

隨著微信已成為人們?nèi)粘＝涣骱蜏贤ǖ囊环N重要方式，微信平臺(tái)的信息安全問題急需解決。目前對(duì)微信信息的監(jiān)管主要是通過設(shè)置黑名單的形式，即大量收集傳播垃圾信息的微信用戶ID，并將其加入黑名單來阻斷信息的傳播。但由于微信用戶量大，增長速度快等特點(diǎn)，傳統(tǒng)的設(shè)置黑名單的方式很難從源頭上杜絕垃圾信息的產(chǎn)生。并且實(shí)施周期長，工作量大，效果顯微。

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

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

1 樸素貝葉斯分類

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

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

則a∈bk。根據(jù)貝葉斯定理：

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

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

計(jì)算過程中由于p（ai｜bj）、p（bi）的值都很小，兩者相乘的結(jié)果偏小會(huì)導(dǎo)致精度下降，常用的做法是取對(duì)數(shù)進(jìn)行運(yùn)算，可減少計(jì)算開銷并提高了計(jì)算結(jié)果的精度。

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

2 改進(jìn)的貝葉斯算法

2.1 特征提取

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

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

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

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

若存在m個(gè)類別，則特征項(xiàng)a與m個(gè)類別分別有m個(gè)互信息，常用的方法是求平均互信息，平均互信息的計(jì)算公式為：

傳統(tǒng)互信息在特征提取時(shí)，有兩個(gè)突出的缺陷：（1）不考慮詞頻，更趨向于低頻詞匯；（2）忽略負(fù)相關(guān)特征，特征與類別的負(fù)相關(guān)部分會(huì)導(dǎo)致該特征的權(quán)值降低［8］。針對(duì)以上兩個(gè)缺陷帶來的分類性能較低的問題，本文采用改進(jìn)的互信息進(jìn)行特征提取。

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

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

通過限定閾值，就可以對(duì)互信息選取特征的缺陷進(jìn)行很好地補(bǔ)充。

2.2 特征加權(quán)

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

其中，wik表示文檔i中第K維的向量值，tfik表示文檔i中第K個(gè)特征值的TF值，N表示文本集的文檔數(shù)，nk表示文本集中出現(xiàn)該特征項(xiàng)的文本數(shù)。將TFIDF歸一化后得

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

該函數(shù)考慮詞條i在某一具體類中的文檔出現(xiàn)的概率。改進(jìn)的TFIDF＊函數(shù)定義如下：

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

3 實(shí)驗(yàn)結(jié)果與分析

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

表1 數(shù)據(jù)集

本文采用查全率R和查準(zhǔn)率P作為評(píng)測(cè)指標(biāo)，計(jì)算公式如下：

查全率和查準(zhǔn)率從兩個(gè)不同方面反映了分類器的性能。

圖2 查準(zhǔn)率

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

為驗(yàn)證本文提出的改進(jìn)貝葉斯算法的穩(wěn)健性，采用不同數(shù)量的訓(xùn)練集作為樣本進(jìn)行訓(xùn)練，觀察訓(xùn)練樣本數(shù)量對(duì)分類準(zhǔn)確性的影響，實(shí)驗(yàn)結(jié)果見圖3。

圖3 樣本數(shù)量對(duì)分類結(jié)果的影響

從圖3可以看出，隨著訓(xùn)練樣本的不斷增加，改進(jìn)的貝葉斯分類器趨于穩(wěn)定，并保持較高的分類性能。而樸素貝葉斯分類器在訓(xùn)練樣本增加之后性能也得到提高，但整體分類性能沒有改進(jìn)貝葉斯分類性能高?？梢钥闯?，樸素貝葉斯在大樣本訓(xùn)練集中具有較好的分類性能。而改進(jìn)貝葉斯在小樣本區(qū)間也具有較好的分類性能。

4 結(jié)語與展望

采用改進(jìn)的貝葉斯分類器對(duì)微信信息進(jìn)行分類，使用改進(jìn)的互信息提取特征，然后使用改進(jìn)的TFIDF對(duì)特征進(jìn)行加權(quán)，最終較樸素貝葉斯取得了更好的分類效果。改進(jìn)的貝葉斯算法在小樣本區(qū)間也表現(xiàn)出較好的分類性能，可以將本方法及后續(xù)改進(jìn)方法用于垃圾郵件檢測(cè)和入侵檢測(cè)系統(tǒng)中。

［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］ 鄧桂騫，趙躍龍.一種優(yōu)化的貝葉斯分類算法［J］.計(jì)算機(jī)測(cè)量與控制，2012，20（1）：199－202.

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

［6］ 趙文濤，孟令軍.樸素貝葉斯算法的改進(jìn)與應(yīng)用［J］.測(cè)控技術(shù)，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文本特征加權(quán)方法的改進(jìn)研究［J］.計(jì)算機(jī)應(yīng)用軟件，2011，28（2）：17－20.

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

［11］魯松，李曉黎，白碩.文檔中詞語權(quán)重計(jì)算方法的改進(jìn)［J］.中文信息學(xué)報(bào)，2000，14（6）：8－20.

［12］施聰鶯，徐朝軍，楊曉江.TFIDF算法研究綜述［J］.計(jì)算機(jī)應(yīng)用，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

［責(zé)任編校：張巖芳］

1003－4684（2017）04－0051－04

2016－06－06

張穎江（1959－），男，北京人，湖北工業(yè)大學(xué)教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)安全

庫凱琳（1991－），男，湖北黃岡人，湖北工業(yè)大學(xué)碩士研究生，研究方向?yàn)樾畔⑻幚砼c網(wǎng)絡(luò)安全