基于改進(jìn)平衡Winnow算法的短信過濾系統(tǒng)

1、    基于改進(jìn)平衡Winnow算法的短信過濾系統(tǒng)    基于改進(jìn)平衡Winnow算法的短信過濾系統(tǒng)    類別：嵌入式系統(tǒng)      摘要： 將黑白名單技術(shù)與Balanced Winnow 算法相結(jié)合，實(shí)現(xiàn)對垃圾短信的過濾。采用CHI 特征提取算法并對權(quán)重計算方法進(jìn)行改進(jìn)， 同時提出了去除訓(xùn)練樣本中野點(diǎn)的想法， 通過判定去除野點(diǎn)， 減緩在訓(xùn)練過程中出現(xiàn)的抖動現(xiàn)象。實(shí)驗表明這種改進(jìn)對于提高訓(xùn)練速度及提高短信過濾的性能

2、均有很好的作用。 手機(jī)短信以其短小、迅速、簡便、價格低廉等優(yōu)點(diǎn)成為一種重要的通信和交流方式， 受到眾多人士的青睞。然而， 手機(jī)短信與郵件一樣存在著垃圾信息問題。 目前， 垃圾短信過濾主要有黑名單過濾、關(guān)鍵詞過濾和基于文本分類的內(nèi)容過濾等方式。黑名單過濾和關(guān)鍵詞過濾方式能快速過濾垃圾短信， 但這兩種過濾方式實(shí)質(zhì)是基于規(guī)則的過濾， 雖然在一定程度上阻擋了一些垃圾短信， 但規(guī)則的方法需要更多的用戶自定義設(shè)置，很容易被反過濾?；谖谋痉诸惖亩绦胚^濾采用常見的分類算法， 如樸素貝葉斯、SVM、神經(jīng)網(wǎng)絡(luò)等。黎路 等人將貝葉斯分類應(yīng)用到J2ME 模擬環(huán)境中成功地過濾了中獎短信和祝福短信。浙江大學(xué)的金展、范晶

3、等 將樸素貝葉斯和支持向量機(jī)結(jié)合， 解決了傳統(tǒng)垃圾短信過濾系統(tǒng)短信特征和內(nèi)容未能得到及時更新而導(dǎo)致過濾性能降低的問題。王忠軍將基于樸素貝葉斯短信過濾算法與基于最小風(fēng)險貝葉斯算法進(jìn)行了實(shí)驗分析和比較，結(jié)論是基于最小風(fēng)險的短信過濾算法具有較好的性能。 然而， 短信過濾的準(zhǔn)確率依賴于其訓(xùn)練樣本的數(shù)量及質(zhì)量， 這些分類算法需要經(jīng)過訓(xùn)練學(xué)習(xí)建立分類器模型，因此在速度上不能很好地滿足短信過濾實(shí)時性的要求。 從現(xiàn)有技術(shù)上來說， 垃圾短信的過濾在準(zhǔn)確率和效率方面仍然不能滿足現(xiàn)實(shí)需要。 本文針對現(xiàn)有短信過濾技術(shù)的不足， 設(shè)計了在手機(jī)終端的短信過濾系統(tǒng)， 根據(jù)垃圾短信的特點(diǎn)將黑白名單和基于內(nèi)容過濾相結(jié)合。這種過濾

4、方式要求能夠快速地對短信進(jìn)行分類， 并且能夠?qū)崿F(xiàn)用戶對短信過濾的個性化要求， 使垃圾短信過濾系統(tǒng)具有更好的過濾性能。 Winnow 算法是在1987 年由Nick LittleSTONe 提出并對可行性做了嚴(yán)格證明的線性分類算法。當(dāng)時的目標(biāo)是想找到一種時空復(fù)雜度僅僅與分類對象相關(guān)屬性相關(guān)的數(shù)量呈線性相關(guān)的算法。平衡Winnow 算法是對基本W(wǎng)innow 算法的一種改進(jìn)， 該算法具有過濾速度快、性能好、支持反饋更新的優(yōu)點(diǎn)， 在信息過濾領(lǐng)域有很好的應(yīng)用前景， 尤其適合于對實(shí)時性要求較高的短信過濾系統(tǒng)。 本文設(shè)計并實(shí)現(xiàn)了一個基于平衡Winnow 算法的短信內(nèi)容過濾系統(tǒng)， 對該算法在短信過濾系統(tǒng)上的應(yīng)

5、用進(jìn)行了詳細(xì)分析。分類器的訓(xùn)練過程分成預(yù)處理、訓(xùn)練、分類和反饋四個部分。 1 預(yù)處理模塊 預(yù)處理模塊包括中文分詞、特征提取以及短信的向量表示子模塊。 1.1 中文分詞 中文分詞是漢語所特有的研究課題。英語、法語等印歐語種詞與詞之間存在著自然的分割， 一般不存在分詞的問題。本系統(tǒng)采用了目前國內(nèi)較多使用的中科院計算所開發(fā)的漢語詞法分析系統(tǒng)ICTCLAS ( Institute Technology ，Chinese Lexical Analysis System) 。 ICTCLAS 3.0 分詞速度單機(jī)996 Kb/s，分詞精度98.45%，API 不超過200 KB， 各種詞典數(shù)據(jù)壓縮后不到3

6、 MB， 是當(dāng)前相對較好的漢語詞法分析器。 1.2 特征提取 特征提取的方法目前也有很多， 常用的特征選取方法有： 文檔頻率DF(Document Frequency) 、信息增益IG(Information Gain) 、互信息MI(Mutual Information) 、2統(tǒng)計等。 本文將分詞后的詞作為候選特征， 然后使用特征提取算法從中提取出對分類最有用的一些特征， 去除對分類貢獻(xiàn)不大的候選特征， 以降低特征的維數(shù)。其中2分布。2 是一個歸一化的值， 該方法比其他方法能減少50左右的詞匯， 具有分類效果好的優(yōu)點(diǎn)。本文中采用2統(tǒng)計進(jìn)行特征提取。 但不是簡單地令特征項的權(quán)重xi=1 或0

7、， 而是令xi=f(2 特指特征對應(yīng)的(n 是一個正整數(shù)， 取n=4) 。實(shí)驗表明比用布爾權(quán)重表示效果要好。 1.3 文本向量表示目前應(yīng)用較多的是向量空間模型VSM (VectorSpace Model) ， 文中用VSM 將一條短信表示為(W1，W2，Wk，Wn)的向量形式。其中：Wk(k=1 ，2 ，n)為第k 個特征的權(quán)重，n 為選定的特征數(shù)。 2 構(gòu)造分類器 訓(xùn)練分類器是研究的重點(diǎn)，采用Balanced Winnow 算法并對其進(jìn)行改進(jìn)。 2.1 Winnow 分類算法 Winnow 算法是二值屬性數(shù)據(jù)集上的線性分類算法。線性分類問題中表示分類界限的超平面等式如下： w00+w11+w

8、22+wkk=0 ， 其中：0，1，k分別是屬性的值；w0，w1， ，wk是超平面的權(quán)值。如果其值大于0 ， 則預(yù)測為第一類否則為第二類。 Winnow 算法是錯誤驅(qū)動型的分類算法， 即當(dāng)出現(xiàn)錯分的實(shí)例時才更新權(quán)值向量。設(shè)定兩個學(xué)習(xí)系數(shù) 和(其中1，1) ， 通過將權(quán)值乘以參數(shù)( 或) 來分別修改權(quán)值。 2.2 Balanced Winnow 分類算法 標(biāo)準(zhǔn)的Winnow 算法不允許有負(fù)的權(quán)值， 于是就有了另一個稱為平衡的Winnow 版本， 允許使用負(fù)的權(quán)值。 對Winnow 算法的基本形式， 權(quán)重向量的每一維都是正數(shù)。Balanced Winnow 是用w+-w-代替w， 當(dāng)則將實(shí)例歸為該

9、類。Balanced Winnow 的權(quán)重更新策略為： (1) 如果， 但文本不屬于該類， 則要降低權(quán)重：對j=1，d，如果xj0 ， 則xj0 ， w+j =w+j ，w-j =w-j ，1，01。 (2) 如果但文本應(yīng)屬于該類， 則要提高權(quán)重：對j=1，2，d，如果xj0， 則w+j =w+j ，w-j =w-j ，1，01。 在實(shí)驗中， 采用文獻(xiàn)7 中統(tǒng)一 和 為一個參數(shù)的方法， 令=1/， 沒有影響分類效果， 但有效簡化了參數(shù)的選擇。可以為不同的類別確定不同的 值， 但實(shí)驗表明： 對于不同的類別選擇同樣的 值， 結(jié)果幾乎是一樣的， 所以在每次獨(dú)立的實(shí)驗中都取相同的 值， 大小是訓(xùn)練文本

10、所含的平均特征數(shù)， 而初始的w+和w-分別取全2 和全1 向量。 在平衡Winnow 算法中， 一旦參數(shù)、 和閾值 確定下來后， 將在訓(xùn)練過程中不斷更新權(quán)重向量w+和w-至最適合這組參數(shù)。因此對參數(shù)的依賴較小， 需要手工調(diào)整的參數(shù)不多。 2.3 去除野點(diǎn) 在短信過濾中，短信樣本是由手動或自動方式收集的， 收集的過程中難免會出錯， 因此短信樣本集中可能存在一些被人為錯分的樣本點(diǎn)， 即野點(diǎn)。這些野點(diǎn)在訓(xùn)練時， 會使得分類器產(chǎn)生嚴(yán)重的抖動現(xiàn)象， 降低分類器的性能。因此，好的分類器應(yīng)具有識別野點(diǎn)的能力。 對于Winnow 算法，若樣本中存在野點(diǎn)， 則野點(diǎn)在訓(xùn)練時以較大的概率出現(xiàn)在兩分類線之外， 且分類

11、錯誤。 這些野點(diǎn)對分類器的訓(xùn)練過程產(chǎn)生很大的影響， 可能會造成分類器的“ 過度學(xué)習(xí)” 。因此引入損失函數(shù)， 按照損失函數(shù)的定義， 這些野點(diǎn)損失較大， 因此可以通過給損失函數(shù)設(shè)置一個上界函數(shù)來處理線性分類器中的野點(diǎn)問題， 如圖1 所示。 圖1 所示為兩類線性可分情況， 圖中實(shí)心點(diǎn)和空心點(diǎn)分別表示兩類訓(xùn)練樣本，H 為兩類樣本沒有被錯誤地分開的分類線，H1 和H2 分別為平行于分類線H 且與分類線H 的距離為單位距離的兩條直線。直線G(t)為平衡Winnow 算法中第t 輪迭代后損失函數(shù)的上界線。該上界線是關(guān)于迭代次數(shù)t 的函數(shù)， 因此可以將該上界線G(t)對應(yīng)的上界函數(shù)記為g(t)。從圖1 可知，

12、 在直線G(t)左下側(cè)誤分樣本的損失較少， 可以認(rèn)為這些誤分樣本是由于當(dāng)前分類器的性能較低而誤分的； 在直線G(t) 右上側(cè)誤分的樣本由于在第t 輪迭代后損失仍較大， 則可以認(rèn)為這些誤分的樣本是野點(diǎn)。根據(jù)線性分類器和野點(diǎn)的性質(zhì)可知，上界函數(shù)g(t)具有以下性質(zhì)： (1) 隨著Winnow 算法中迭代次數(shù)t 的增加， 上界函數(shù)g(t) 單調(diào)遞減， 并且遞減的速率也隨著t 的增加而遞減， 即上界函數(shù)的導(dǎo)數(shù)g(t)為單調(diào)遞減函數(shù)；(2) 上界函數(shù)既不能太大， 也不能太小。太大會降低判斷野點(diǎn)的能力， 太小則會誤判正常樣本為野點(diǎn)。 根據(jù)上界函數(shù)的這些特性， 可以考慮一個平行于分類線H 的線性函數(shù)作為損失

13、函數(shù)的上界函數(shù)。即g(t)=其中： 為常數(shù)值； 直線G(t) 平行于分類線H； 為損失因子， 也稱為學(xué)習(xí)率， 可以在訓(xùn)練分類器的時候指定其值。 在每一輪訓(xùn)練中， 若該樣本的G(t) 值大于分類線的值， 并且超過一定的閾值， 且不屬于該類， 則判定該樣本具有野點(diǎn)的性質(zhì)， 應(yīng)當(dāng)在訓(xùn)練集中將該樣本去除， 以便提高下一輪訓(xùn)練的準(zhǔn)確性。這樣不僅有效削弱了分類器的抖動現(xiàn)象， 而且提高了分類器的性能。 3 系統(tǒng)反饋 Winnow 是一種在線學(xué)習(xí)的、以錯誤為驅(qū)動的分類器， 適于結(jié)合增量式學(xué)習(xí)來解決自適應(yīng)問題， 實(shí)現(xiàn)用戶的個性化要求。平衡Winnow 算法是基本W(wǎng)innow 算法的另外一種形式， 同樣具有在線更

14、新能力。在分類器訓(xùn)練過程中， 對錯分的短信通過 和 更新類別權(quán)重向量，實(shí)現(xiàn)對分類器的更新， 平衡Winnow 算法中w+和w-的雙向調(diào)節(jié)， 使算法的訓(xùn)練速度更快， 適合于對分類實(shí)時性要求較高的短信過濾系統(tǒng)。 4 實(shí)驗資源及分析與價 本文在自建短信語料庫的基礎(chǔ)上完成對比實(shí)驗， 其中正常短信1 892 條， 垃圾短信270 條， 將短信語料庫隨機(jī)分成5 等份， 其中4 份用于訓(xùn)練樣本，1 份作為測試樣本。 4.1 價指標(biāo) 分類系統(tǒng)價指標(biāo)如下， 包括兩類短信各自的準(zhǔn)確率(precision) 和召回率(recall) ， 由于系統(tǒng)目標(biāo)是垃圾短信過濾， 于是增加了針對垃圾短信的綜合價指標(biāo)(F1): F

15、1=(2×準(zhǔn)確率×召回率)/( 準(zhǔn)確率+召回率)。 4.2 實(shí)驗結(jié)果分析 (1) 實(shí)驗1： 探討改進(jìn)的特征權(quán)重計算方法對實(shí)驗結(jié)果的影響。實(shí)驗結(jié)果如表1 所示。 表1 特征權(quán)重計算方法對實(shí)驗結(jié)果的影響。 其中測試樣本中正常短信被誤分為垃圾短信條數(shù)為22 條， 正常短信召回率為94.2%； 垃圾短信被誤分為正常短信8 條， 準(zhǔn)確率僅為67.7%。 (2) 實(shí)驗2： 統(tǒng)一參數(shù)和取固定的閾值 之后對實(shí)驗結(jié)果的影響。該實(shí)驗中?。?1.5 、=1/1.5 、=15 。實(shí)驗結(jié)果如表2 所示。 表2 選定參數(shù)對實(shí)驗結(jié)果的影響 其中測試樣本中正常短信被誤分為垃圾短信條數(shù)為18 條， 正常短信召回率為96.1%； 而測試用的垃圾短信正確識別了44 條， 準(zhǔn)確率為71.0%。由此可見， 參數(shù)對實(shí)驗結(jié)果的影響不大。 (3) 實(shí)驗3： 去除野點(diǎn)對實(shí)驗結(jié)果的影響。實(shí)驗結(jié)果如表3 所示。 表3 去除野點(diǎn)對實(shí)驗結(jié)果的影響。 從實(shí)驗結(jié)果分析， 僅有12 條正