新聞中心

EEPW首頁 > 手機(jī)與無線通信 > 設(shè)計(jì)應(yīng)用 > 基于改進(jìn)平衡Winnow算法的短信過濾系統(tǒng)

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

作者: 時(shí)間:2011-01-20 來源:網(wǎng)絡(luò) 收藏


2 構(gòu)造分類器

訓(xùn)練分類器是研究的重點(diǎn),采用Balanced Winnow 算法并對(duì)其進(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 算法是錯(cuò)誤型的分類算法, 即當(dāng)出現(xiàn)錯(cuò)分的實(shí)例時(shí)才更新權(quán)值向量。設(shè)定兩個(gè)學(xué)習(xí)系數(shù)α 和β(其中α>1,β<1) , 通過將權(quán)值乘以參數(shù)α( 或β) 來分別修改權(quán)值。

2.2 Balanced Winnow 分類算法

標(biāo)準(zhǔn)的Winnow 算法不允許有負(fù)的權(quán)值, 于是就有了另一個(gè)稱為平衡的Winnow 版本, 允許使用負(fù)的權(quán)值。

對(duì)Winnow 算法的基本形式, 權(quán)重向量的每一維都是正數(shù)。Balanced Winnow 是用w+-w-代替w, 當(dāng)則將實(shí)例歸為該類。Balanced Winnow 的權(quán)重更新策略為:

(1) 如果, 但文本不屬于該類, 則要降低權(quán)重:  對(duì)j=1,,…,d,如果xj≠0 , 則xj≠0 , w+j =βw+j ,w-j =αw-j ,α>1,0<β<1。

(2) 如果但文本應(yīng)屬于該類, 則要提高權(quán)重:  對(duì)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)一α 和β 為一個(gè)參數(shù)的方法, 令β=1/α, 沒有影響分類效果, 但有效簡化了參數(shù)的選擇??梢詾椴煌念悇e確定不同的θ 值, 但實(shí)驗(yàn)表明: 對(duì)于不同的類別選擇同樣的θ 值, 結(jié)果幾乎是一樣的, 所以在每次獨(dú)立的實(shí)驗(yàn)中都取相同的θ 值, 大小是訓(xùn)練文本所含的平均特征數(shù), 而初始的w+和w-分別取全2 和全1 向量。

在平衡Winnow 算法中, 一旦參數(shù)α、β 和閾值θ 確定下來后, 將在訓(xùn)練過程中不斷更新權(quán)重向量w+和w-至最適合這組參數(shù)。因此對(duì)參數(shù)的依賴較小, 需要手工調(diào)整的參數(shù)不多。

2.3 去除野點(diǎn)

在短信過濾中,短信樣本是由手動(dòng)或自動(dòng)方式收集的, 收集的過程中難免會(huì)出錯(cuò), 因此短信樣本集中可能存在一些被人為錯(cuò)分的樣本點(diǎn), 即野點(diǎn)。這些野點(diǎn)在訓(xùn)練時(shí), 會(huì)使得分類器產(chǎn)生嚴(yán)重的抖動(dòng)現(xiàn)象, 降低分類器的性能。因此,好的分類器應(yīng)具有識(shí)別野點(diǎn)的能力。

對(duì)于Winnow 算法,若樣本中存在野點(diǎn), 則野點(diǎn)在訓(xùn)練時(shí)以較大的概率出現(xiàn)在兩分類線之外, 且分類錯(cuò)誤。

這些野點(diǎn)對(duì)分類器的訓(xùn)練過程產(chǎn)生很大的影響, 可能會(huì)造成分類器的“ 過度學(xué)習(xí)” 。因此引入損失函數(shù), 按照損失函數(shù)的定義, 這些野點(diǎn)損失較大, 因此可以通過給損失函數(shù)設(shè)置一個(gè)上界函數(shù)來處理線性分類器中的野點(diǎn)問題, 如圖1 所示。


圖1 所示為兩類線性可分情況, 圖中實(shí)心點(diǎn)和空心點(diǎn)分別表示兩類訓(xùn)練樣本,H 為兩類樣本沒有被錯(cuò)誤地分開的分類線,H1 和H2 分別為平行于分類線H 且與分類線H 的距離為單位距離的兩條直線。直線G(t)為平衡Winnow 算法中第t 輪迭代后損失函數(shù)的上界線。該上界線是關(guān)于迭代次數(shù)t 的函數(shù), 因此可以將該上界線G(t)對(duì)應(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ù)既不能太大, 也不能太小。太大會(huì)降低判斷野點(diǎn)的能力, 太小則會(huì)誤判正常樣本為野點(diǎn)。

根據(jù)上界函數(shù)的這些特性, 可以考慮一個(gè)平行于分類線H 的線性函數(shù)作為損失函數(shù)的上界函數(shù)。即g(t)=其中:ε 為常數(shù)值; 直線G(t) 平行于分類線H;η 為損失因子, 也稱為學(xué)習(xí)率, 可以在訓(xùn)練分類器的時(shí)候指定其值。

在每一輪訓(xùn)練中, 若該樣本的G(t) 值大于分類線的值, 并且超過一定的閾值, 且不屬于該類, 則判定該樣本具有野點(diǎn)的性質(zhì), 應(yīng)當(dāng)在訓(xùn)練集中將該樣本去除, 以便提高下一輪訓(xùn)練的準(zhǔn)確性。這樣不僅有效削弱了分類器的抖動(dòng)現(xiàn)象, 而且提高了分類器的性能。


關(guān)鍵詞: 驅(qū)動(dòng)

評(píng)論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉