基于改進(jìn)平衡Winnow算法的短信過濾系統(tǒng)
加入技術(shù)交流群
2 構(gòu)造分類器
訓(xùn)練分類器是研究的重點(diǎn)，采用Balanced Winnow 算法并對其進(jìn)行改進(jìn)。
2.1 Winnow 分類算法
Winnow 算法是二值屬性數(shù)據(jù)集上的線性分類算法。線性分類問題中表示分類界限的超平面等式如下：
w0α0+w1α1+w2α2+…+wkαk=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í)例歸為該類。Balanced Winnow 的權(quán)重更新策略為：(1) 如果
， 但文本不屬于該類， 則要降低權(quán)重： 對j=1，，…，d，如果xj≠0 ， 則xj≠0 ， w+j =βw+j ，w-j =αw-j ，α＞1，0＜β＜1。(2) 如果
但文本應(yīng)屬于該類， 則要提高權(quán)重： 對j=1，2，…，d，如果xj≠0， 則w+j =αw+j ，w-j =βw-j ，α＞1，0＜β＜1。在實(shí)驗(yàn)中， 采用文獻(xiàn)[7] 中統(tǒng)一α 和β 為一個參數(shù)的方法， 令β=1/α， 沒有影響分類效果， 但有效簡化了參數(shù)的選擇?？梢詾椴煌念悇e確定不同的θ 值， 但實(shí)驗(yàn)表明： 對于不同的類別選擇同樣的θ 值， 結(jié)果幾乎是一樣的， 所以在每次獨(dú)立的實(shí)驗(yàn)中都取相同的θ 值， 大小是訓(xùn)練文本所含的平均特征數(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)在兩分類線之外， 且分類錯誤。
這些野點(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 可知， 在直線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ù)作為損失函數(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)象， 而且提高了分類器的性能。
評論