QBC主動采樣學習在垃圾郵件在線過濾中的應用

陳念，唐振民

1.池州學院數學與計算機科學系，安徽池州 247000

2.南京理工大學計算機科學與工程學院，南京 210094

QBC主動采樣學習在垃圾郵件在線過濾中的應用

陳念1，2，唐振民2

1.池州學院數學與計算機科學系，安徽池州 247000

2.南京理工大學計算機科學與工程學院，南京 210094

垃圾郵件指的是通過群發方式，未經許可強行向用戶發送的電子郵件，其承載的信息多為商業廣告，但也充斥著相當數量的詐騙、色情信息，嚴重干擾了人們的日常生活，甚至會造成一定的經濟損失。提供郵件服務的網站都有一些垃圾郵件在線過濾的方法，其實質都是解決二值文本的在線分類問題[1]，但由于垃圾郵件本身的格式、內容等都在不斷地發生變化，因此分類器也需要獲取相應的樣本進行更新。網絡上存在著一些已被標注的郵件樣本，但更多的是未經用戶標注的樣本。當前研究方向是：以較小的標注成本獲取高價值的樣本，快速地建立訓練集，使得垃圾郵件在線過濾既能滿足低計算量的要求，又能兼顧高識別率的期望。

主動學習是近年來機器學習研究的熱點，它改變了原先分類器被動接受訓練樣本的學習方式[2]，在已有帶標簽樣本數量不足，分類器充分訓練得不到保證的條件下，在無標簽樣本池中通過一定的采樣策略主動選擇樣本，經專家或用戶標注類別后，加入訓練集。現有的采樣策略主要分三種[3]：一是基于不確定性的采樣策略，文獻[4]中提出的邊界采樣（Margin Sampling）是目前廣泛被使用的一種方法，它在SVM超平面附近采集類別歸屬不確定性大的樣本進行機器訓練，并在各種實際應用中取得很好分類效果。Huang等人提出的最小—最大視圖方法[5]（QUIRE）由于充分考慮了樣本的分布信息，因此能很好地克服噪音帶來的干擾，是該策略下采樣效果較好的方法。二是基于版本空間縮減的采樣策略，它將所有可能成為目標參數的模型假設集中在一起，構成版本空間（Version Space），在某種算法思想下，逐步淘汰錯誤的假設，使版本空間最終收斂于目標假設。委員會投票算法QBC就是這種策略下最具代表性的采樣方法，由此衍生出的Boosting_QBC[6]和Bagging_QBC[7]，都能很好地適應多種分類器模型。三是基于誤差縮減的采樣策略，它采集的訓練樣本可以最大程度地縮減泛化誤差，如Fisher Information方法。

本文根據垃圾郵件在線過濾應用的特點，在分析縮減版本空間采樣策略的思想基礎上，采用投票熵度量樣本類別歸屬的不確定性，將熵值超過閾值θ的樣本進行標注學習。文中提出一種基于QBC的快速采樣方法，即在算法執行過程中，隨著分類器預測能力的增強，以Δθ的幅度逐步調高閾值，這樣可以減少采樣次數，降低樣本采集帶來的標注成本和學習時間成本，同時對分類精度不會產生大的影響。

1 縮減版本空間采樣策略

設樣本空間χ={xi|i=1,2,…,n},類標識空間C= {ck|k=1,2,…,m},對xi∈χ,存在ωj={ωj1,ωj2,…,ωjs}使得表達式f(ωjp,xi)=ck成立，其中f為分類器模型，ωj為模型參數集合，p=1,2,…,s。χ中任一樣本都對應有ωj,可以將它映射到空間C中，那么由所有ωj構成的集合稱為f參數的版本空間（Version Space），表示為：

VS={ωj|j=1,2,…,t}（1）

圖1（a）中顯示了樣本x1可被4個超平面劃歸到Class1中（可能的分類面遠不止4個），每個分類面對應的模型參數ωj構成了x1的版本空間。縮減版本空間的做法在于：對新采集的樣本，版本空間中現有的參數預測其類別，在與專家標注的真實類別比對后，預測錯誤的參數將被淘汰出去。該過程迭代若干次，版本空間最終將收斂于目標參數ω0。

如圖1（b）中所示，新樣本x2被plane1、plane2錯誤地劃分到Class1中，那么這兩個分類面對應的參數被淘汰之后，版本空間的規模將縮減一半，而新樣本x3對版本空間的縮減則沒有產生貢獻。

從上例可以看，版本空間收斂的速度取決于采集樣本的質量。平分版本空間是縮減策略的理想化實踐，它假設VS中的t個元素服從平均概率分布，即每個元素成為目標參數的概率都是相同的，有P(ω0|ωj)=,則第i次采樣后，樣本空間規模的數學期望是：

圖1 版本空間概念與縮減過程圖解

當然，這種獲取分類器參數的方法，和其他很多方法一樣，不能避免噪音樣本的干擾。設想如果采集到的新樣本是野值點，那么依此訓練得出的目標參數可能就是錯誤的。

2 委員會投票算法

2.1 算法思想與實現步驟

Seung和Freund提出的委員會投票算法QBC[9-10]，是基于版本空間縮減策略中最具代表性的采樣學習方法。它依據采集樣本的歸類不確定性的高低，來決定該樣本是否用于機器訓練，圖2簡單表達了QBC的算法思想。

圖2 委員會投票算法的一般步驟

設有帶標簽樣本集L={＜xi,ck＞},無標簽樣本集UL={xj},分類器模型f。從L中分離出若干個子集SL分別訓練f獲取分類器當前版本空間VS,從VS中選擇r個元素組成委員會com。對采集的樣本xi∈UL,com中的每個成員對其類別歸屬有一票的表決權，計算xi的歸類不確定性值，如果超出了設定門檻θ,則需經專家標注獲取其真實類別ci。調整L,UL集合的組成：L+xi→L,UL-xi→UL,用L訓練模型f,并在測試集上檢驗其泛化精度。

投票熵是度量樣本歸類不確定性的一種方式[11]，由于它沒有考慮樣本的概率分布情況，因此在采樣時不會遺漏有價值的訓練樣本，公式為：

樣本存在屬于或不屬于某類兩種情況，式中V(c,xi)是委員會判斷樣本xi屬于c類的票數，|C|是類別數，ε是為防止某類得票數為0，而出現lb 0這種情況的微調常量，可取非常小的值。

QBC算法可描述如下：

輸入條件：有標簽樣本集L,無標簽樣本集UL,標注閾值θ

輸出：訓練樣本集L及對應目標參數ω0

算法將UL中的無標簽樣本逐一取出判斷其歸類不確定性，然后將其熵值超過門檻θ與否，作為是否進行標注且作為訓練數據的依據。θ∈[0,1]對算法的執行效果影響很大。θ偏大時，由于門檻過高，很多高價值樣本得不到作為訓練數據的機會，分類器的精度會降低；而其值偏小時，大量信息量近似的樣本會被冗余標注和訓練，增加了學習過程的時間成本。

實際問題處理中，Boosting和Bagging方法有效結合了投票查詢的過程，使分類模型適應復雜數據環境的能力更強。Boosting_QBC中每個委員會成員被賦予不同的動態權重wj,其投票結果wj×f(ωj,xi)對熵值的影響也相應存在差異。一次采樣投票后，預測誤差e被作為權值調整的依據，wj=ln((1-e)/e),低預測誤差的成員將被賦予更高的權重參與下一次投票。Bagging_QBC算法則每次在有標簽池L中隨機選擇由n個樣本構成的子集Li,迭代i次訓練分類模型f,由此獲得委員會成員。Bagging方法對諸如判定樹、神經網絡等受訓練規模影響較大的不穩定模型，具有較強的預測能力。

2.2 快速訓練樣本采樣方法

對于一些在線應用，如垃圾郵件的在線過濾，由于時效性要求較高，因此應選擇高信息量樣本進行針對性訓練，使分類器在較短的時間內獲得強的泛化能力。分類器學習效率η與識別準確率facc及所需訓練樣本數量nosam之間的關系顯然滿足：

訓練樣本規模nosam由兩部分組成：初始訓練樣本數量|L|和標注后加入訓練集的樣本數量labelsam。初始樣本是機器學習開始之前就已具備的，可以給分類器提供前期經驗，后續的學習樣本則是訓練過程中主動選擇的。labelsam與熵值votentropy及標注門檻θ的關系是：

隨著機器學習過程的推進，版本空間中錯誤的模型參數被逐步淘汰，保留下的參數成為目標參數的概率也在增加。分類器應傾向于選擇具有更高熵值，即信息量更豐富的樣本來加快版本空間的收斂，而樣本標注依據的閾值θ卻是靜態的。本文在主動采樣學習的過程中，以相同的幅度Δθ逐步增加θ的值，以達到分類器訓練效果不變的前提下，削減訓練樣本數量，提高學習速度的目的。

機器的學習目的是用最小的訓練代價獲得最高的識別準確率，即maxη，假定分類器訓練后可達到的準確率facc=δ,δ為常量，由式（5）得：

因此，閾值增加幅度Δθ應滿足條件：

與θ的取值一樣，過大的Δθ值雖然能使采樣的過程快速地結束，但也會遺漏樣本集中有價值的數據，分類器由于得不到充分訓練而泛化精度不高；Δθ偏小的取值，同樣會造成冗余采樣，出現獲取樣本對版本空間的縮減貢獻較低的現象。

一般的做法是，在分類器學習的初始階段，設置的門檻θ值較低，讓更多的樣本能獲得訓練分類器的機會。隨著學習過程的推進，分類器預測能力的提升，逐步提高采樣標注門檻，以求獲取更高價值的樣本，更快地結束分類器的學習過程。

3 實驗與分析

UCI的Spambase是從實際e-mail應用中收集出的郵件集合，可用于郵件過濾器的訓練。它包含有4 601個樣本，分成Non-Spam（正常郵件2 788個）和Spam（垃圾郵件1 813個）兩個類別，每個樣本由58個屬性描述，其中包含1個類別屬性。認定垃圾郵件的依據有：特定的單詞或字符在e-mail中出現的頻率，及不間斷的大寫字母長度信息等。表1給出了Spambase集中各樣本的屬性描述。

實驗在Spambase數據集上進行，采用SVM二分類模型，分別用隨機采樣（Random Sampling），委員會投票采樣（QBC Sampling），衍生的投票采樣（Boosting_ QBC Sampling和Bagging_QBC Sampling）及本文提出的快速QBC采樣（Fast QBC Sampling）五種方法在無標簽樣本池中采集訓練樣本。通過實驗，比較這些方法的工作效率，并分析θ,Δθ不同取值下，快速QBC采樣算法表現出的性能。

3.1 不同采樣方法分析與比較

將Spambase按4∶1的比例隨機劃分成訓練集和測試集，做交叉驗證。設算法中各相關量初始化為|L|=90,θ=0.2,Δθ=0.002,計算在測試集上進行不同規模的采樣，分類器訓練所能達到的精度，表2給出了5次實驗的平均值。

表2的對比主要是展現同等采樣規模下泛化精度的變化，可以看出，隨著由采樣獲得的訓練樣本不斷加入，用不同方法獲得樣本訓練分類器，獲得的精度都是逐步上升的。隨機采樣方法在選擇樣本時，由于帶有一定盲目性，因此在不同采樣次數下，其所能達到的精度在85%～86%之間，低于表中其他方法。QBC采樣選擇類別不確定性大的樣本加入訓練集，相比較于隨機采樣，同等規模下能提升泛化精度2%左右。Boosting_QBC和Bagging_QBC采樣優勢在這個數據集上并沒有體現出來，相同數量的采樣獲得的泛化精度與QBC采樣相近，最大差值只有0.6%。這是因為前者的加權投票策略更適用于難區分樣本數量較多的情形，而后者則在受訓練規模影響偏大的不穩定分類模型上更能體現其針對性，可以推斷，郵件分類數據集Spambase和當前模型并不滿足充分發揮它們預測優勢的條件。Fast QBC方法則在采樣過程，不斷尋找更高價值訓練樣本，因而能獲得優于其他方法的效率，實驗結果證實了這點，例如在采樣規模為130時，精度較常規QBC方法有1.4%的提升，比Boosting_QBC也增加了1%。

圖3給出了相同θ前提下，幾種QBC方法在無標簽樣本池中采樣次數的對比，其中Fast QBC采用Δθ=0.005。

由圖3可見，四種投票采樣方法隨著采樣閾值θ的遞增，在無標簽池中采樣的次數呈現明顯的下降趨勢。QBC、Boosting_QBC及Bagging_QBC由于使用固定值的采樣標注門檻，相同閾值下的采樣次數差別并不明顯。而Fast QBC以Δθ的步長動態提升門檻設置，因此能更為快速地結束采樣過程，建立訓練樣本集。

3.2 參數設置對Fast QBC的影響

在2.2節中提到，參數θ和Δθ的取值是影響Fast QBC采樣數量與質量的重要因素，而引入調整幅度Δθ是該方法區別與其他投票算法的最主要特點。表3記錄了不同參數設置時，Fast QBC的采樣次數情況，其中|L|=90,表中數據為5次實驗均值。

表1 Spambase數據集樣本屬性情況

表2 不同算法在不同采樣規模時獲得的泛化精度對比

圖3 幾種QBC算法采樣次數對比

表3結果與理論分析一致，隨著采樣門檻θ和調整幅度Δθ的增加，算法在數據集上的采樣次數呈現遞減趨勢，且調高Δθ可以更快地降低采樣數量。由于初始訓練樣本L是從訓練集中隨機產生的，它的組成也會影響到后續的采樣，因此從表中看出，遞減的過程并不是單調的。

表3 不同參數對應的Fast QBC采樣數量情況

θ和Δθ值增加時，能夠快速地從樣本池中收集訓練樣本，使機器學習的過程盡快結束，但過大的值設置同樣會帶來識別率的下降。

圖4顯示，θ在0.25附近取值時，Δθ用不同值采樣訓練后得到的分類器識別精度能夠保持在90%附近。隨著參數值設置得增大，訓練獲得的分類器泛化精度會呈現下降的趨勢。在兩個參數都有較大取值時（如圖θ=0.5,Δθ=0.008），識別率僅有86%，這是由于相鄰的兩次采樣間門檻跨度過大，一些信息量大，但熵值未超過門檻設置的樣本沒有獲得訓練分類模型的機會，而導致識別率不高。因此θ和Δθ值的選擇要綜合考慮采樣數量和泛化精度兩個方面的因素，以達到用較小的訓練代價獲得相對較高識別準確率的目標。

4 結束語

圖4 Fast QBC識別精度隨參數變化情況

本文針對垃圾郵件在線過濾的實際應用，在委員會投票QBC算法的基礎上，通過逐步提高采樣門檻的做法，在無標簽樣本池中選擇高信息量的樣本用于分類器的訓練。根據應用的時效性要求，需要在盡可能短的時間內建立最有學習價值的訓練集，QBC采樣算法是一種高效的主動學習方法，它通過計算樣本的熵值高低，來評價其訓練價值。本文充分考慮了機器學習過程中，分類器識別能力逐步增強這一特點，用動態提升采樣閾值的方法，梯度增加采集樣本的質量，進一步壓縮樣本標注和學習所需的時間成本，提高學習的效率。

[1]劉伍穎，王挺.結構化集成學習垃圾郵件過濾[J].計算機研究與發展，2012，49（3）：628-635.

[2]陳榮.基于主動學習和半監督學習的多類圖像分類[J].自動化學報，2011，37（8）：954-962.

[3]吳偉寧.基于采樣策略的主動學習算法研究進展[J].計算機研究與發展，2012，49（6）：1162-1173.

[4]Tong S，Koller D.Support vector machine active learning with applications to text classification[J].The Journal of Machine Learning Research，2002（2）：45-66.

[5]Huang Shengjun，Jin Rong，Zhou Zhihua.Active learning by querying informative and representative examples[C]// Proc of NIPS 2010.Cambridge，MA：MIT Press，2010：892-900.

[6]Freund Y，Schapire R E.A decision-theoretic generalization of on-line learning and an application to boosting[J]. Journal of Computer and System Sciences，1997，55（1）：119-139.

[7]Breiman L.Bagging predictors[J].Machine Learning，1996，24（2）：123-140.

[8]龍軍.選取最大可能預測錯誤樣例的主動學習算法[J].計算機研究與發展，2008，45（3）：472-478.

[9]Seung H S，Opper M，Sompolinsky H.Query by committee[C]//Proceedings of the 15th Annual ACM Workshop on Computational Learning Theory，California，1992：287-294.

[10]Freund Y，Seung H S，Samir E，et al.Selective sampling usingthequerybycommitteealgorithm[J].Machine Learning，1997，28（23）：133-168.

[11]Argamon E S，Dagan I.Committee-based sample selection for probabilistic classifiers[J].Journal of Artificial Intelligence Research，1999，11：335-360.

CHEN Nian1，2,TANG Zhenmin2

1.Department of Mathematics and Computer Science,Chizhou College,Chizhou,Anhui 247000,China
2.College of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China

A method is put forward in the paper which can get informative samples from unlabeled-sample pool with stepped way.The method which is based on query-by-committee algorithm increases the sampling threshold dynamically and it is in order to solve the problem of spam filtering online.Through the new method,the number of samples which is used for labeling and training is further reduced and the accuracy of classifier can remain stable.By experiments on Spambase datasets,the effectiveness which can improve efficiency of machine learning is certificated.

spam filtering;version space;active learning;vote entropy;query-by-committee algorithm

針對垃圾郵件在線過濾的實際應用，在委員會投票算法采樣學習的基礎上，提出動態提升采樣門檻，在無標簽樣本池中階梯式獲取高信息量訓練樣本的方法。該方法能夠在穩定識別精度的前提下，進一步降低用于標注和學習的樣本數量，壓縮由此帶來的時間成本。通過在UCI的Spambase數據集上仿真，證明了該方法在改善學習效率方面的有效性。

垃圾郵件過濾；版本空間；主動學習；投票熵；委員會投票算法

A

TP393

10.3778/j.issn.1002-8331.1211-0016

CHEN Nian,TANG Zhenmin.Method of spam filtering online based on QBC active sampling learning algorithm. Computer Engineering and Applications,2014,50（22）：170-174.

安徽省教育廳自然重點項目（No.KJ2012A211）。

陳念（1978—），男，副教授，主研方向：機器學習與人工智能；唐振民，教授，博導。E-mail：njustchennian@gmail.com

2012-11-01

2013-01-23

1002-8331（2014）22-0170-05

CNKI網絡優先出版：2013-02-28,http://www.cnki.net/kcms/detail/11.2127.TP.20130228.1148.012.html

◎圖形圖像處理◎