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

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

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

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

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

5、用進行了詳細分析。分類器的訓(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 分詞速度單機996 Kb/s，分詞精度98.45%，API 不超過200 KB， 各種詞典數(shù)據(jù)壓縮后不到3

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

7、， 而是令xi=f(2 特指特征對應(yīng)的(n 是一個正整數(shù)， 取n=4) 。實驗表明比用布爾權(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)練分類器是研究的重點，采用Balanced Winnow 算法并對其進行改進。 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ū)動型的分類算法， 即當出現(xiàn)錯分的實例時才更新權(quán)值向量。設(shè)定兩個學(xué)習(xí)系數(shù) 和(其中1，1) ， 通過將權(quán)值乘以參數(shù)( 或) 來分別修改權(quán)值。 2.2 Balanced Winnow 分類算法 標準的Winnow 算法不允許有負的權(quán)值， 于是就有了另一個稱為平衡的Winnow 版本， 允許使用負的權(quán)值。 對Winnow 算法的基本形式， 權(quán)重向量的每一維都是正數(shù)。Balanced Winnow 是用w+-w-代替w， 當則將實例歸為該

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。 在實驗中， 采用文獻7 中統(tǒng)一 和 為一個參數(shù)的方法， 令=1/， 沒有影響分類效果， 但有效簡化了參數(shù)的選擇。可以為不同的類別確定不同的 值， 但實驗表明： 對于不同的類別選擇同樣的 值， 結(jié)果幾乎是一樣的， 所以在每次獨立的實驗中都取相同的 值， 大小是訓(xùn)練文本

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

11、錯誤。 這些野點對分類器的訓(xùn)練過程產(chǎn)生很大的影響， 可能會造成分類器的“ 過度學(xué)習(xí)” 。因此引入損失函數(shù)， 按照損失函數(shù)的定義， 這些野點損失較大， 因此可以通過給損失函數(shù)設(shè)置一個上界函數(shù)來處理線性分類器中的野點問題， 如圖1 所示。 圖1 所示為兩類線性可分情況， 圖中實心點和空心點分別表示兩類訓(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è)誤分樣本的損失較少， 可以認為這些誤分樣本是由于當前分類器的性能較低而誤分的； 在直線G(t) 右上側(cè)誤分的樣本由于在第t 輪迭代后損失仍較大， 則可以認為這些誤分的樣本是野點。根據(jù)線性分類器和野點的性質(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ù)既不能太大， 也不能太小。太大會降低判斷野點的能力， 太小則會誤判正常樣本為野點。 根據(jù)上界函數(shù)的這些特性， 可以考慮一個平行于分類線H 的線性函數(shù)作為損失

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

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

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