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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金重點(diǎn)資助項(xiàng)目（60634030）；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目（20060699032）

作者簡(jiǎn)介：趙春暉(1973-)，男，陜西西安人，博士研究生，主要研究方向?yàn)槿斯ぶ悄堋⑿畔⑷诤稀D像處理(zhaochunhui@nwpu.edu.cn); 張洪才（1938-），男，江蘇人，教授，博導(dǎo)，主要研究方向?yàn)楣烙?jì)與控制、圖像處理、信息融合; 陸朝霞(1981-)，女，陜西人，碩士研究生，主要研究方向?yàn)橐曨l圖像處理、智能監(jiān)控、目標(biāo)跟蹤.*

（西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，西安 710072）

摘 要：提出一種選擇性樣本權(quán)重更新算法，把FNR和FPR引入樣本權(quán)重更新過(guò)程，將分類效果反饋給分類器，實(shí)現(xiàn)對(duì)分類器結(jié)構(gòu)的有效控制，在樣本權(quán)重更新時(shí)合理選擇更新方法，使得分類器的FNR或FPR達(dá)到理想狀態(tài)。實(shí)驗(yàn)表明，該算法能有效改善整個(gè)分類器的FNR和FPR。

關(guān)鍵詞：權(quán)重更新；Adaboost；分類器

中圖分類號(hào)：TP391.6

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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算法廣泛應(yīng)用于人臉識(shí)別[1]、行人檢測(cè)[2，3]、文本分類[4]等方面的分類器設(shè)計(jì)中。在Adaboost分類器的訓(xùn)練過(guò)程中，每一輪循環(huán)訓(xùn)練集的樣本權(quán)重如何分布是Adaboost算法要解決的基本問(wèn)題[5，6]。樣本權(quán)重處理過(guò)程一般包括更新和歸一化兩個(gè)部分。Viola等人[7，8]提出的樣本權(quán)重更新方法認(rèn)為樣本被正確分類后其權(quán)重將按設(shè)定的比例減小，被錯(cuò)誤分類的樣本權(quán)重不變，并對(duì)樣本權(quán)重采用全局歸一化法，提升了被錯(cuò)誤分類樣本的權(quán)重。下一輪訓(xùn)練時(shí)，分類器會(huì)更加重視本輪錯(cuò)分的樣本。文獻(xiàn)[9]利用目標(biāo)模型在目標(biāo)觀測(cè)上的匹配度來(lái)表明當(dāng)前的目標(biāo)模型能否合理解釋目標(biāo)觀測(cè)的變化，查看目標(biāo)模型的匹配程度，從而選擇性地更新目標(biāo)模型。文獻(xiàn)[10]采用動(dòng)態(tài)更新訓(xùn)練樣本權(quán)值的方法，對(duì)不同訓(xùn)練階段的訓(xùn)練樣本賦予不同的訓(xùn)練權(quán)值。在產(chǎn)生某一層的最佳弱分類器后，通過(guò)該層弱分類器判定結(jié)果更新當(dāng)前樣本權(quán)值概率分布，加入訓(xùn)練權(quán)值因子。文獻(xiàn)[11]中將FPR（被錯(cuò)分為正樣本的負(fù)樣本數(shù)目與全部負(fù)樣本數(shù)目之比，表示負(fù)樣本的錯(cuò)分率）引入權(quán)重更新過(guò)程，這種權(quán)重更新方法使得那些被前一輪弱分類器錯(cuò)誤分類的樣本權(quán)重?cái)U(kuò)張幅度減小。因?yàn)槟切┍诲e(cuò)分的樣本權(quán)重的擴(kuò)張幅度將會(huì)對(duì)FPR敏感，其限制程度將由FPR來(lái)控制。FPR越大，則被錯(cuò)分的樣本權(quán)重的受限程度越大，從而在一定程度上均衡了各個(gè)弱分類器的權(quán)重。但是在實(shí)際應(yīng)用中，F(xiàn)NR（被錯(cuò)分為負(fù)樣本的正樣本數(shù)目與全部正樣本數(shù)目之比，表示正樣本的錯(cuò)分率）比FPR更值得重視。

如何使用適當(dāng)?shù)臉颖緳?quán)重更新和歸一化方法，是Adaboost分類器設(shè)計(jì)的關(guān)鍵。本文提出一種選擇性樣本權(quán)重更新方法，通過(guò)引入FNR和FPR，將樣本權(quán)重更新和分類器的分類效果聯(lián)系起來(lái)。分類器首先將FNR快速降低至期望值，然后再降低FPR，同時(shí)保持FNR值不變。該方法用數(shù)量較少的弱分類器便可使得強(qiáng)分類器在保持較高檢測(cè)率的同時(shí)，將誤檢率降低到可接受的范圍內(nèi)。

1 傳統(tǒng)權(quán)重更新方法

Viola提出的權(quán)重更新方法包含兩個(gè)步驟：ω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個(gè)樣本在第t輪訓(xùn)練時(shí)的權(quán)重。

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

這種權(quán)重更新的改進(jìn)方法使得那些被前一輪弱分類器錯(cuò)誤分類的樣本權(quán)重?cái)U(kuò)張幅度減小。當(dāng)ηt＜0.5，即錯(cuò)分率較低時(shí)，則0＜βt＜1，并且由于1-FPR≤1：(β¹-εtt)¹-FPR≥β¹-εtt(4)

式（4）說(shuō)明那些被錯(cuò)分的樣本權(quán)重?cái)U(kuò)張幅度將會(huì)對(duì)FPR敏感，其限制程度將由FPR來(lái)控制。FPR越大，則被錯(cuò)分的樣本權(quán)重的受限程度越大，從而在一定程度上均衡了各個(gè)弱分類器的權(quán)重。

2 閾值選擇權(quán)重更新方法

雖然該樣本權(quán)重更新方法可以使樣本權(quán)重更新過(guò)程受到FPR的影響，在降低FNR的同時(shí)，限制樣本整體誤差率的提高，但并不能控制FNR被降低的程度。因?yàn)樵诖蟛糠謱?shí)際應(yīng)用中，對(duì)FNR的要求比FPR高，如行人檢測(cè)。

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

a)初始化。樣本權(quán)重初始值為1/N，N為樣本總數(shù)。

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)全局歸一化樣本集，進(jìn)入下一輪訓(xùn)練。

其中: f1、 f2為錯(cuò)分率閾值且f1＜f2，它們根據(jù)實(shí)際使用中對(duì)正負(fù)樣本錯(cuò)分率的具體要求來(lái)規(guī)定；k是調(diào)節(jié)因子，用于調(diào)節(jié)樣本權(quán)重?cái)U(kuò)張受制于FPR或FNR的程度。

21 FNR和FPR對(duì)新的樣本權(quán)重更新方法的影響

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

分析實(shí)驗(yàn)結(jié)果可以看到：不管是對(duì)于正負(fù)樣本分布比較均勻的點(diǎn)集1，還是正樣本緊湊負(fù)樣本分散的點(diǎn)集2，當(dāng)用FPR對(duì)樣本權(quán)重進(jìn)行修正時(shí)，F(xiàn)NR降低，但同時(shí)FPR提高；當(dāng)用FNR對(duì)樣本權(quán)重進(jìn)行修正時(shí)，F(xiàn)PR降低，但同時(shí)FNR提高。

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

對(duì)于點(diǎn)集2，使用FNR限制樣本權(quán)重時(shí)，其分類器性能與Viola算法的效果相當(dāng)。但是當(dāng)FPR限制樣本權(quán)重時(shí)，雖然分類器的FNR降低，但整體誤差率提高。這是因?yàn)閷?duì)于點(diǎn)集2，正樣本分布比較緊湊，負(fù)樣本比較分散，正樣本相對(duì)于負(fù)樣本更容易被正確分類，即FNR較低，F(xiàn)PR較高。此時(shí)，更加需要提高對(duì)負(fù)樣本的重視度，用FNR限制權(quán)重的更新速度，從而降低分類器的FPR。如果用FPR來(lái)修正樣本權(quán)重，則算法對(duì)正負(fù)樣本的偏見(jiàn)更加嚴(yán)重，將導(dǎo)致樣本整體錯(cuò)分率提高。

22 調(diào)節(jié)因子k對(duì)新的樣本權(quán)重更新方法的影響

對(duì)于正負(fù)樣本分布均勻的樣本集，即正負(fù)樣本很容易被正確分類的樣本集（點(diǎn)集1），權(quán)重更新方法的改變對(duì)其影響不大，所以只在點(diǎn)集2上進(jìn)行實(shí)驗(yàn)。圖3為使用FNR時(shí)的error、FPR、FNR曲線。圖4為使用FPR時(shí)的error、FPR、FNR曲線。

從圖3、4中可以看出：當(dāng)k＜1時(shí)，可以加速權(quán)重更新算法的修正程度，各項(xiàng)指標(biāo)收斂速度加快;當(dāng)k＞1時(shí)，可用降低權(quán)重更新算法的修正程度，各項(xiàng)指標(biāo)收斂速度趨緩。

使用FPR進(jìn)行調(diào)節(jié)時(shí)，k＜1比k=1時(shí)的error、FNR和FPR曲線獲得了更好的效果。這是因?yàn)椋?dāng)正樣本分布比較集中而負(fù)樣本分布分散時(shí)，算法對(duì)負(fù)樣本的重視度不夠，F(xiàn)NR較高。使用FPR修正樣本權(quán)重來(lái)平衡FNR，這樣使得FNR和FPR的值比較平均，穩(wěn)定了分類器的性能。

3 仿真分析

31 點(diǎn)集訓(xùn)練仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)數(shù)據(jù)為圖5所示的二維平面內(nèi)的兩個(gè)點(diǎn)集。圖中實(shí)心點(diǎn)表示正樣本，空心點(diǎn)表示負(fù)樣本。這些數(shù)據(jù)是在MATLAB下由rand函數(shù)隨機(jī)生成。每個(gè)點(diǎn)集均包含1 000個(gè)數(shù)據(jù)。點(diǎn)集1中正負(fù)樣本的分布比較均勻，正樣本750個(gè)，負(fù)樣本250個(gè)；點(diǎn)集2中正樣本分布比較緊湊，負(fù)樣本分布比較分散，正樣本496個(gè)，負(fù)樣本504個(gè)。這兩個(gè)點(diǎn)集可以測(cè)試不同樣本模式下，權(quán)重更新規(guī)則變化對(duì)分類器性能的影響。

在Adaboost訓(xùn)練過(guò)程中，用樣本點(diǎn)的坐標(biāo)(x，y)作為簡(jiǎn)單特征。

實(shí)驗(yàn)中取f1=0.02， f2=0.1，即對(duì)正樣本的錯(cuò)分率要求較高為2%，對(duì)負(fù)樣本的錯(cuò)分率要求較低，為10%；k取1/3。

用傳統(tǒng)的Viola權(quán)重更新方法和選擇性樣本權(quán)重更新方法在訓(xùn)練集1和2上仿真的實(shí)驗(yàn)結(jié)果如圖6、7所示。

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

32 UCI數(shù)據(jù)仿真實(shí)驗(yàn)

本文還采用Wisconsin大學(xué)和加州大學(xué)Irvine分校的機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)(machine learning repository)UCI中的數(shù)據(jù)來(lái)檢驗(yàn)選擇性樣本權(quán)重更新算法的有效性。實(shí)驗(yàn)中選用UCI數(shù)據(jù)庫(kù)中的Diabetes糖尿病樣本集。此樣本集中共含有正樣本268個(gè)，負(fù)樣本500個(gè)。Diabetes數(shù)據(jù)集中兩種方法的err、FPR、FNR曲線如圖8所示。

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

4 結(jié)束語(yǔ)

本文提出了一種選擇性樣本權(quán)重更新方法。該算法將FNR和FPR引入樣本權(quán)重更新過(guò)程，使分類器結(jié)構(gòu)與其分類效果聯(lián)系起來(lái)，將分類效果反饋給分類器，從而實(shí)現(xiàn)對(duì)分類器結(jié)構(gòu)的有效控制，可以在保證整體錯(cuò)分率一定的情況下，根據(jù)實(shí)際需要限定正樣本或負(fù)樣本的錯(cuò)分率在期望的范圍之內(nèi)。

參考文獻(xiàn)：

[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]朱誼強(qiáng)， 張洪才， 程詠梅，等. 基于Adaboost算法的實(shí)時(shí)行人檢測(cè)系統(tǒng)[J]. 計(jì)算機(jī)測(cè)量與控制， 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]蘇金樹(shù)， 張博鋒， 徐昕. 基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J]. 軟件學(xué)報(bào)， 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]王建宇， 陳熙， 高文，等. 背景變化魯棒的自適應(yīng)視覺(jué)跟蹤目標(biāo)模型[J]. 軟件學(xué)報(bào)，2006， 17(5):1001-1008.

[10]武妍，項(xiàng)恩寧. 動(dòng)態(tài)權(quán)值預(yù)劃分實(shí)值A(chǔ)daboost人臉檢測(cè)算法[J]. 計(jì)算機(jī)工程，2007， 33(3):208-209.

[11]蔡忠志. 使用新特征的人臉偵測(cè)系統(tǒng)[D].臺(tái)北:臺(tái)灣清華大學(xué)，2005.