基于Ａｄａｂｏｏｓｔ的選擇性樣本權重更新算法

收稿日期：2007-10-16；修回日期：2008-01-17

基金項目：國家自然科學基金重點資助項目（60634030）；高等學校博士學科點專項科研基金資助項目（20060699032）

作者簡介：趙春暉(1973-)，男，陜西西安人，博士研究生，主要研究方向為人工智能、信息融合、圖像處理(zhaochunhui@nwpu.edu.cn); 張洪才（1938-），男，江蘇人，教授，博導，主要研究方向為估計與控制、圖像處理、信息融合; 陸朝霞(1981-)，女，陜西人，碩士研究生，主要研究方向為視頻圖像處理、智能監控、目標跟蹤.*

（西北工業大學 自動化學院，西安 710072）

摘 要：提出一種選擇性樣本權重更新算法，把FNR和FPR引入樣本權重更新過程，將分類效果反饋給分類器，實現對分類器結構的有效控制，在樣本權重更新時合理選擇更新方法，使得分類器的FNR或FPR達到理想狀態。實驗表明，該算法能有效改善整個分類器的FNR和FPR。

關鍵詞：權重更新；Adaboost；分類器

中圖分類號：TP391.6

文獻標志碼：A

文章編號：1001-3695(2008)10-2943-03

Method for selecting sample weight renew in Adaboost

ZHAO Chun-hui， ZHANG Hong-cai， LU Chao-xia

（College of Automation， Northwestern Polytechnical University， Xi’an710072， China）

Abstract:This paper proposed a new method for renewing sample weight in Adaboost. Took FNR and FPR into the step of sample weight renewing， which feedbacked the result of classifier into itself in order to control the classifier structure efficiently. This method could make the FNR and FPR of classifier to ideal status. Many experiments illuminate that new method can improve the performance of classifier.

Key words：weight renewing; Adaboost; classifier

Adaboost算法廣泛應用于人臉識別[1]、行人檢測[2，3]、文本分類[4]等方面的分類器設計中。在Adaboost分類器的訓練過程中，每一輪循環訓練集的樣本權重如何分布是Adaboost算法要解決的基本問題[5，6]。樣本權重處理過程一般包括更新和歸一化兩個部分。Viola等人[7，8]提出的樣本權重更新方法認為樣本被正確分類后其權重將按設定的比例減小，被錯誤分類的樣本權重不變，并對樣本權重采用全局歸一化法，提升了被錯誤分類樣本的權重。下一輪訓練時，分類器會更加重視本輪錯分的樣本。文獻[9]利用目標模型在目標觀測上的匹配度來表明當前的目標模型能否合理解釋目標觀測的變化，查看目標模型的匹配程度，從而選擇性地更新目標模型。文獻[10]采用動態更新訓練樣本權值的方法，對不同訓練階段的訓練樣本賦予不同的訓練權值。在產生某一層的最佳弱分類器后，通過該層弱分類器判定結果更新當前樣本權值概率分布，加入訓練權值因子。文獻[11]中將FPR（被錯分為正樣本的負樣本數目與全部負樣本數目之比，表示負樣本的錯分率）引入權重更新過程，這種權重更新方法使得那些被前一輪弱分類器錯誤分類的樣本權重擴張幅度減小。因為那些被錯分的樣本權重的擴張幅度將會對FPR敏感，其限制程度將由FPR來控制。FPR越大，則被錯分的樣本權重的受限程度越大，從而在一定程度上均衡了各個弱分類器的權重。但是在實際應用中，FNR（被錯分為負樣本的正樣本數目與全部正樣本數目之比，表示正樣本的錯分率）比FPR更值得重視。

如何使用適當的樣本權重更新和歸一化方法，是Adaboost分類器設計的關鍵。本文提出一種選擇性樣本權重更新方法，通過引入FNR和FPR，將樣本權重更新和分類器的分類效果聯系起來。分類器首先將FNR快速降低至期望值，然后再降低FPR，同時保持FNR值不變。該方法用數量較少的弱分類器便可使得強分類器在保持較高檢測率的同時，將誤檢率降低到可接受的范圍內。

1 傳統權重更新方法

Viola提出的權重更新方法包含兩個步驟：ωt+1，i=ωt，iβ¹-εtt(1)

ωt，i=ωt，i/∑ni=1ωt，i(2)其中:i=1，2，…，N;更新因子βt=ηt/(1-ηt)， ηt=∑iωt，i|ht(xi)-yi|; ht為分類器; yi為樣本類別;ωt，i為第i個樣本在第t輪訓練時的權重。

傳統Adaboost算法中的單個樣本權重更新過程（式(2)）會使得被前一輪弱分類器ht錯誤分類的那些樣本權重不斷增大。如果這些樣本被錯分多次，那么它們的權重將不斷擴張，導致每輪產生的弱分類器ht的錯誤率ηt相對增大，使弱分類器在最后加權投票中所占的權重變得很小。文獻[11]中將式(2)的權重更新過程修改為ωt+1，i=ωt，i(β¹-εtt)¹-FPR(3)

這種權重更新的改進方法使得那些被前一輪弱分類器錯誤分類的樣本權重擴張幅度減小。當ηt＜0.5，即錯分率較低時，則0＜βt＜1，并且由于1-FPR≤1：(β¹-εtt)¹-FPR≥β¹-εtt(4)

式（4）說明那些被錯分的樣本權重擴張幅度將會對FPR敏感，其限制程度將由FPR來控制。FPR越大，則被錯分的樣本權重的受限程度越大，從而在一定程度上均衡了各個弱分類器的權重。

2 閾值選擇權重更新方法

雖然該樣本權重更新方法可以使樣本權重更新過程受到FPR的影響，在降低FNR的同時，限制樣本整體誤差率的提高，但并不能控制FNR被降低的程度。因為在大部分實際應用中，對FNR的要求比FPR高，如行人檢測。

本文提出一種選擇性樣本權重更新方法。該方法可以根據實際情況，將FNR或FPR的值限制在需要的范圍內。在Adaboost訓練過程中，首先關注正樣本的分類正確率，當FNR降低到足夠小后，再注重整體的誤差率，盡量降低負樣本的錯分率FPR。算法步驟如下：

a)初始化。樣本權重初始值為1/N，N為樣本總數。

b)如果FNR＞f1，則

ωt+1，i=ωt，i(β¹-εtt)(1-FPR)k(5)

否則，如果FPR＞f2，則

ωt+1，i=ωt，i(β¹-εtt)(1-FNR)k(6)

否則

ωt+1，i=ωt，i(β¹-εtt)（7）

c)全局歸一化樣本集，進入下一輪訓練。

其中: f1、 f2為錯分率閾值且f1＜f2，它們根據實際使用中對正負樣本錯分率的具體要求來規定；k是調節因子，用于調節樣本權重擴張受制于FPR或FNR的程度。

21 FNR和FPR對新的樣本權重更新方法的影響

為了分析FNR和FPR對樣本權重的影響，保持k=1不變，采用本文中第3章的實驗數據集進行比較分析，結果如圖1、2所示。其中，Viola提出的權重更新方法是樣本權重未受FPR和FNR制約的算法。

分析實驗結果可以看到：不管是對于正負樣本分布比較均勻的點集1，還是正樣本緊湊負樣本分散的點集2，當用FPR對樣本權重進行修正時，FNR降低，但同時FPR提高；當用FNR對樣本權重進行修正時，FPR降低，但同時FNR提高。

對于點集1，三種方法的誤差曲線基本一致，但是采用兩種權重更新制約方法的FPR和FNR曲線的收斂速度都較Viola算法快速且振蕩小、穩定度高。

對于點集2，使用FNR限制樣本權重時，其分類器性能與Viola算法的效果相當。但是當FPR限制樣本權重時，雖然分類器的FNR降低，但整體誤差率提高。這是因為對于點集2，正樣本分布比較緊湊，負樣本比較分散，正樣本相對于負樣本更容易被正確分類，即FNR較低，FPR較高。此時，更加需要提高對負樣本的重視度，用FNR限制權重的更新速度，從而降低分類器的FPR。如果用FPR來修正樣本權重，則算法對正負樣本的偏見更加嚴重，將導致樣本整體錯分率提高。

22 調節因子k對新的樣本權重更新方法的影響

對于正負樣本分布均勻的樣本集，即正負樣本很容易被正確分類的樣本集（點集1），權重更新方法的改變對其影響不大，所以只在點集2上進行實驗。圖3為使用FNR時的error、FPR、FNR曲線。圖4為使用FPR時的error、FPR、FNR曲線。

從圖3、4中可以看出：當k＜1時，可以加速權重更新算法的修正程度，各項指標收斂速度加快;當k＞1時，可用降低權重更新算法的修正程度，各項指標收斂速度趨緩。

使用FPR進行調節時，k＜1比k=1時的error、FNR和FPR曲線獲得了更好的效果。這是因為，當正樣本分布比較集中而負樣本分布分散時，算法對負樣本的重視度不夠，FNR較高。使用FPR修正樣本權重來平衡FNR，這樣使得FNR和FPR的值比較平均，穩定了分類器的性能。

3 仿真分析

31 點集訓練仿真實驗

仿真實驗數據為圖5所示的二維平面內的兩個點集。圖中實心點表示正樣本，空心點表示負樣本。這些數據是在MATLAB下由rand函數隨機生成。每個點集均包含1 000個數據。點集1中正負樣本的分布比較均勻，正樣本750個，負樣本250個；點集2中正樣本分布比較緊湊，負樣本分布比較分散，正樣本496個，負樣本504個。這兩個點集可以測試不同樣本模式下，權重更新規則變化對分類器性能的影響。

在Adaboost訓練過程中，用樣本點的坐標(x，y)作為簡單特征。

實驗中取f1=0.02， f2=0.1，即對正樣本的錯分率要求較高為2%，對負樣本的錯分率要求較低，為10%；k取1/3。

用傳統的Viola權重更新方法和選擇性樣本權重更新方法在訓練集1和2上仿真的實驗結果如圖6、7所示。

從圖7中可以看出，選擇性樣本權重更新方法可以在保證整體誤差率一定的情況下，在更少的訓練輪數內迅速降低FNR的值。

32 UCI數據仿真實驗

本文還采用Wisconsin大學和加州大學Irvine分校的機器學習數據庫(machine learning repository)UCI中的數據來檢驗選擇性樣本權重更新算法的有效性。實驗中選用UCI數據庫中的Diabetes糖尿病樣本集。此樣本集中共含有正樣本268個，負樣本500個。Diabetes數據集中兩種方法的err、FPR、FNR曲線如圖8所示。

從圖8可以看出，閾值選擇方法在保證整體錯分率一定的情況下，降低了FNR的值，證明了閾值選擇方法的普遍有效性。使用這種樣本權重更新方法，分類器先按期望要求將FNR快速降低；當獲得筆者期望值之后，再注重FPR的值，同時保持FNR的值不變。較少的弱分類器便可保證強分類器在保持較高檢測率的同時，將誤檢率降低到可接受的范圍內。

4 結束語

本文提出了一種選擇性樣本權重更新方法。該算法將FNR和FPR引入樣本權重更新過程，使分類器結構與其分類效果聯系起來，將分類效果反饋給分類器，從而實現對分類器結構的有效控制，可以在保證整體錯分率一定的情況下，根據實際需要限定正樣本或負樣本的錯分率在期望的范圍之內。

參考文獻：

[1]MITA T， KANEKO T， HORI O. Joint Haar-like features for face detection[C]//Proc of the 10th IEEE International Conference on Computer Vision. Washington DC: IEEE Computer Society， 2005:1619-1626.

[2]朱誼強， 張洪才， 程詠梅，等. 基于Adaboost算法的實時行人檢測系統[J]. 計算機測量與控制， 2006， 14(11):1462-1465.

[3]CUTLER R， DAVISL S. Robust real-time periodic motion detection: analysis and applications[J]. IEEE Pattern Analysis and Machine Intelligence， 2000， 22(8):781-796.

[4]蘇金樹， 張博鋒， 徐昕. 基于機器學習的文本分類技術研究進展[J]. 軟件學報， 2006， 17(9):1848-1859.

[5]SCHAPIRE R E. The boosting approach to machine learning: an overview[C]//Proc of MSRI Workshop on Nonlinear Estimation and Classification. Berkeley， CA: Springer-Verlag， 2002:149-172.

[6]QUINLAN J R. Bagging， boosting， and C4.5[C]//Proc of the 13th National Conference on Artificial Intelligence. Portland: [s.n.]， 1996:725-730.

[7]VIOLA P， PLATT J C. ZHANG Cha. Multiple instance boosting for object detection[C]//Proc of HZPS .Cambridge， MA: MIT Press， 2006:1419-1426.

[8]VIOLA P， JONES M. Rapid object detection using a boosted cascade of simple features[C]//Proc of IEEE Conference on Computer Vision and Pattern Recognition. Washington DC: IEEE Computer Society， 2001:511-518.

[9]王建宇， 陳熙， 高文，等. 背景變化魯棒的自適應視覺跟蹤目標模型[J]. 軟件學報，2006， 17(5):1001-1008.

[10]武妍，項恩寧. 動態權值預劃分實值Adaboost人臉檢測算法[J]. 計算機工程，2007， 33(3):208-209.

[11]蔡忠志. 使用新特征的人臉偵測系統[D].臺北:臺灣清華大學，2005.