基于改進平衡Winnow算法的短信過濾系統(tǒng)
加入技術(shù)交流群
2 構(gòu)造分類器
訓(xùn)練分類器是研究的重點，采用Balanced Winnow 算法并對其進行改進。
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)錯分的實例時才更新權(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)
則將實例歸為該類。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。在實驗中， 采用文獻[7] 中統(tǒng)一α 和β 為一個參數(shù)的方法， 令β=1/α， 沒有影響分類效果， 但有效簡化了參數(shù)的選擇?？梢詾椴煌念悇e確定不同的θ 值， 但實驗表明： 對于不同的類別選擇同樣的θ 值， 結(jié)果幾乎是一樣的， 所以在每次獨立的實驗中都取相同的θ 值， 大小是訓(xùn)練文本所含的平均特征數(shù)， 而初始的w+和w-分別取全2 和全1 向量。
在平衡Winnow 算法中， 一旦參數(shù)α、β 和閾值θ 確定下來后， 將在訓(xùn)練過程中不斷更新權(quán)重向量w+和w-至最適合這組參數(shù)。因此對參數(shù)的依賴較小， 需要手工調(diào)整的參數(shù)不多。
2.3 去除野點
在短信過濾中，短信樣本是由手動或自動方式收集的， 收集的過程中難免會出錯， 因此短信樣本集中可能存在一些被人為錯分的樣本點， 即野點。這些野點在訓(xùn)練時， 會使得分類器產(chǎn)生嚴(yán)重的抖動現(xiàn)象， 降低分類器的性能。因此，好的分類器應(yīng)具有識別野點的能力。
對于Winnow 算法，若樣本中存在野點， 則野點在訓(xùn)練時以較大的概率出現(xiàn)在兩分類線之外， 且分類錯誤。
這些野點對分類器的訓(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 可知， 在直線G(t)左下側(cè)誤分樣本的損失較少， 可以認(rèn)為這些誤分樣本是由于當(dāng)前分類器的性能較低而誤分的； 在直線G(t) 右上側(cè)誤分的樣本由于在第t 輪迭代后損失仍較大， 則可以認(rèn)為這些誤分的樣本是野點。根據(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ù)作為損失函數(shù)的上界函數(shù)。即g(t)=
其中：ε 為常數(shù)值； 直線G(t) 平行于分類線H；η 為損失因子， 也稱為學(xué)習(xí)率， 可以在訓(xùn)練分類器的時候指定其值。在每一輪訓(xùn)練中， 若該樣本的G(t) 值大于分類線的值， 并且超過一定的閾值， 且不屬于該類， 則判定該樣本具有野點的性質(zhì)， 應(yīng)當(dāng)在訓(xùn)練集中將該樣本去除， 以便提高下一輪訓(xùn)練的準(zhǔn)確性。這樣不僅有效削弱了分類器的抖動現(xiàn)象， 而且提高了分類器的性能。
評論