張子祥,陳優(yōu)廣

(華東師范大學(xué) 計算機科學(xué)與軟件工程學(xué)院,上海 200333)

基于樣本噪聲檢測的AdaBoost算法改進①

張子祥,陳優(yōu)廣

(華東師范大學(xué) 計算機科學(xué)與軟件工程學(xué)院,上海 200333)

針對傳統(tǒng)的AdaBoost算法中,存在的噪聲樣本造成的過擬合問題,提出了一種基于噪聲檢測的AdaBoost改進算法,本文稱為NAdaBoost(nois-detection AdaBoost). NAdaBoost算法創(chuàng)新點在于針對傳統(tǒng)的AdaBoost算法在錯誤分類的樣本中,噪聲樣本在某些屬性上存在很大差異,根據(jù)這一特性來確定噪聲樣本,再重新使用算法對兩類樣本進行分類,最終達(dá)到提高分類準(zhǔn)確率的目的. 本文對二分類問題進行實驗結(jié)果表明,本文提出的算法和傳統(tǒng)的AdaBoost算法,以及相關(guān)改進的算法相比,有較高的分類準(zhǔn)確率.

過擬合; 噪聲檢測; AdaBoost算法; 二分類

1 引言

歷史上,Kearns 和 Valiant[1,2]首先提出“強可學(xué)習(xí)(Strong learnable)”和“弱可學(xué)習(xí) (Weakly learnable)”的概念,指出在概率近似正確 (Probably approximately correct,PAC)的學(xué)習(xí)框架中,“弱可學(xué)習(xí)”可以轉(zhuǎn)化為“強可學(xué)習(xí)”. Schapire 后來證明在該框架下[3],一個概念是強可學(xué)習(xí)的充分必要條件是這個概念是弱可學(xué)習(xí)的. 1995 年 AdaBoost (Adaptive Boosting)算法被提出,在機器學(xué)習(xí)中得到了廣泛的運用,其中在文本分類[4]和人臉檢測[5]上取得比較成功的應(yīng)用,并且它是第一個實現(xiàn)實時人臉檢測的算法,與以前的很多算法相比,它在速度上有很大的突破,因此研究該算法不論是在機器學(xué)習(xí)還是圖像處理方面都具有非常廣闊的前景.

AdaBoost算法跟大多數(shù)其它學(xué)習(xí)算法相比,不會很容易出現(xiàn)過擬合現(xiàn)象,但AdaBoost算法對噪聲和異常數(shù)據(jù)很敏感,在有噪聲的情況下會出現(xiàn)過擬合[6],這是由于噪聲樣本在不斷迭代的情況下,權(quán)值不斷增加,進而分類器的準(zhǔn)確率會有所下降. 目前提出了一些方法來減弱噪聲的影響,一類方法是修改損失函數(shù),在不斷的迭代過程中噪聲點權(quán)重下降[7],相對比較好的算法是LogitBoost. 這類方法在一定程度上取得了效果,但也對正常訓(xùn)練樣本的權(quán)重產(chǎn)生影響. Yunlong提出了EAdaBoost算法[8],處理樣本中存在的噪聲樣本,以此來提高算法的準(zhǔn)確率,此外還有學(xué)者將多個算法結(jié)合起來如MutiboostingAB[9]等. 可見在噪聲數(shù)據(jù)方向的研究對于AdaBoost算法的改進還有很大的空間,同樣算法的改進對于文本分類和人臉檢測等問題的解決,具有重大意義,本文將針對AdaBoost算法對噪聲和異常數(shù)據(jù)很敏感這一問題進行深入的研究.

綜上所述本文的創(chuàng)新點是從處理樣本噪聲來對AdaBoost算法進行研究和改進. 首先在第一節(jié)介紹AdaBoost算法和相關(guān)分析,第二節(jié)對提出的新算法進行詳細(xì)的介紹和分析,第三、四節(jié)是實驗總結(jié)部分.

2 AdaBoost算法介紹

AdaBoost算法的主要目的就是把弱分類器組合形成一個強分類器.

2.1 算法流程

算法1. AdaBoost算法輸入: 訓(xùn)練數(shù)據(jù)集(二分類); 弱學(xué)習(xí)算法輸出: 最終分類器G(x)1. 初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布. 所有的訓(xùn)練樣本開始時都賦值一樣的權(quán)重: 1/N2. 進行多輪迭代(1,2,….,M)a) 使用上一步得到的Dm訓(xùn)練數(shù)據(jù)集進行學(xué)習(xí),可以得到一個基本分類器:b) 計算Gm分類的誤差率:c) 計算的系數(shù),表示在最終分類器中起的重要程度.d) 更新訓(xùn)練數(shù)據(jù)集的權(quán)值分布如果em>1/2,結(jié)束迭代. 其中,3. 構(gòu)建基本分類器的線性組: 得到最終的分類器: ()

AdaBoost算法主要是以迭代的方式不斷增大被錯誤判斷樣本的權(quán)值的原則,來進行樣本權(quán)值的更新,分類器在下一次分類中把重心放在那些被錯誤判斷的樣本上,從而達(dá)到正確分類所有樣本的目的,多個這樣的分類器會被算法訓(xùn)練出來,以級聯(lián)的方式組合所有的分類器,一個比較強的分類器就能被組成起來.

3 改進的算法及其分析

3.1 原算法分析

算法主要性質(zhì)是不斷減少學(xué)習(xí)過程中的訓(xùn)練誤差,如何確定最終誤差下界,對于這個問題有如下的定理[10]:

這一定理說明,在每一次迭代過程中選擇合適的Gm使得Zm最小,訓(xùn)練的誤差會下降的最快. 對于二分類問題有如下結(jié)果[11]:

3.2 樣本噪聲處理

噪聲數(shù)據(jù)對分類結(jié)果有很大的影響,只要在這些類中存在少量的噪聲數(shù)據(jù),就會影響這些類的分類效果. 在AdaBoost算法中只有被分類為錯誤樣本的權(quán)值才會被擴大,在下一次分類中分類器會把重心放在權(quán)值大的樣本上,然而噪聲樣本很難被分類正確,這類樣本的權(quán)值就會變得越來越大,分類器也會趨向于過擬合,可以看出算法本身就忽略了噪聲樣本的存在. 另一方面噪聲樣本確實很難被分類正確,然而在真實環(huán)境中,噪聲樣本對于效果不是很好的弱分類器,噪聲樣本也有可能被分類正確,該樣本的權(quán)值會下降,又進一步降低了被分類錯誤的可能,那么最終分類器的準(zhǔn)確率必定會受影響.

為了確定樣本中的噪聲樣本,本文提出在AdaBoost算法的一次迭代過程中會產(chǎn)生一些分類為錯誤的樣本,這些樣本中可以分為兩部分,一類是好的樣本能夠在下一次分類中被分類正確,另外一類是噪聲樣本這類樣本很難被分類正確,而且它與同一分類中的樣本在某些屬性上存在很大差異.

其中,β?是規(guī)范化因子,目的使得f(x)是概論分布,保證每輪的樣本權(quán)值之和為1,由于經(jīng)過訓(xùn)練,AdaBoost在訓(xùn)練集上誤差率已經(jīng)很低了,所以他越接近于-1,可以發(fā)現(xiàn)被分類錯誤的樣本的ε(x)在[-1,10]之間,如果P是噪聲點,那么它的ε(x)就會越接近-1. 為了進一步確定P 樣本是否是噪聲數(shù)據(jù),對于兩個樣本點x1,x2,使用歐幾里得距離思想來定義它們之間的距離:

圖1中折線之內(nèi)為模糊地帶樣本,折線之外為正常樣本,其中含有兩個強噪聲樣本,本文以此來確定噪聲樣本并進行分類處理. 3.3節(jié)將詳細(xì)講述算法流程.

圖1 噪聲樣本和非噪聲樣本分布示意圖

3.3 NAdaBoost算法流程

算法2. NAdaBoost算法輸入: 訓(xùn)練數(shù)據(jù)集(二分類); 弱學(xué)習(xí)算法(本文的弱分類器是單層決策樹).輸出: 最終分類器G(x).1. 用傳統(tǒng)的AdaBoost算法得到初次分類器: .) (2. 對于每個樣本計算,.3. 根據(jù)上一步的計算,將 的樣本點集合記為Ususpect.4.a) 對于上述集合Ususpect根據(jù)給定的距離公式 在集合中找出與當(dāng)前樣本點P最臨近的K個點,記為Nk(p).b) 在Nk(p)中根據(jù)分類決策規(guī)則決定P點的類別y: 根據(jù)這兩個步驟得到極大可能性的噪聲點集合Unoise,和不是噪聲的集合Ugood=(Uall-Unoise).∑5. 分別對上述兩個集合Unoise,Ugood重復(fù)進行上述步驟1分別得到分類器和,即最終的))((分類器為 .G(x)=Gn(x)x∈Unoise Gg(x)x∈Ugood

4 實驗

4.1 實驗方法

本文主要是針對二分類問題進行研究,因此使用著名的加州大學(xué)歐文分校提出的數(shù)據(jù)庫UCI,從其中選出部分二分類數(shù)據(jù)集來進行實驗. UCI數(shù)據(jù)庫是行業(yè)內(nèi)經(jīng)常被用于數(shù)據(jù)挖掘,機器學(xué)習(xí)的標(biāo)準(zhǔn)測試數(shù)據(jù)庫. 本文隨機從中選取了9組數(shù)據(jù)集,如表1所示.

實驗中本文所提出的算法將和傳統(tǒng)的AdaBoost算法在相同的情況下進行對比,并且與上文提到的其他比較著名的改進算法LogitBoost,MutiboostAB,最終得出結(jié)論. 為了保證結(jié)果的準(zhǔn)確性,本文先將各個算法在沒有噪聲的情況下比較分類結(jié)果,然后對各個數(shù)據(jù)集添加一定比例的噪聲,再使用各個算法測試數(shù)據(jù)進行分類,比較實驗結(jié)果,最終得出結(jié)論. 在本次實驗中,采用的是java編程語言,結(jié)合WEKA提供的開源代碼進行實驗.

表1 數(shù)據(jù)集信息

本文算法使用的弱分類器是單層決策樹,迭代次數(shù)根據(jù)原始的算法為10次(默認(rèn)都是10次),k值也是根據(jù)經(jīng)驗取樣本總數(shù)的5.6%.

4.2 本文算法與其他算法比較結(jié)果

表2至表6依次列出了在數(shù)據(jù)沒有添加噪聲的情況下,和添加數(shù)據(jù)數(shù)量10%的噪聲,20%的噪聲的情況下,各個算法的預(yù)測結(jié)果的正確率對比.

表2 沒添加噪聲時各個算法的預(yù)測結(jié)果對比 (單位: %)

表2的實驗結(jié)果中加粗的部分是每組數(shù)據(jù)集中預(yù)測正確最高的,加下劃線的是正確率最低的,因此可以清楚看出不管在有沒有加噪聲的情況下,本文提出的NAdaBoost算法在大多數(shù)數(shù)據(jù)集中都有很高的正確率,而且沒有出現(xiàn)最低的正確率情況. 為了進一步體現(xiàn)本文算法在噪聲數(shù)據(jù)干擾情況的健壯性,選擇特征最多的三組數(shù)據(jù)集 (ionosphere,sonar,mushroom)分別隨機添加10%,20%的噪聲,測定不同噪聲下各個算法的準(zhǔn)確率,如表3至表6所示,分別記錄了不同噪聲下各個算法的準(zhǔn)確率.

表3 NAdaBoost在不同噪聲比例下的準(zhǔn)確率 (單位: %)

表4 LogitBoost在不同噪聲比例下的準(zhǔn)確率 (單位: %)

表5 MutiboostAB 在不同噪聲比例下的準(zhǔn)確率 (單位: %)

表6 AdaBoost在不同噪聲比例下的準(zhǔn)確率 (單位: %)

從表3至表6的比較可以發(fā)現(xiàn)NAdaBoost算法在不同的噪聲比例下依然保持很高的分類準(zhǔn)確率,并且在相同的噪聲條件下,分類結(jié)果會優(yōu)于其他算法. 為了便于觀察分別繪制了在三個數(shù)據(jù)集上的各種算法比較的折線圖,如圖2所示.

圖2 ionosphere數(shù)據(jù)集下各個算法分類準(zhǔn)確率對比

可以發(fā)現(xiàn)在隨著噪聲比例的增大各個算法的正確率都有所下降,但本文提出的NAdaBoost算法正確率下降緩慢,并且相比于其他算法依然保持最高的正確率.

圖3 mushroom數(shù)據(jù)集下各個算法分類準(zhǔn)確率對比

圖4 sonar數(shù)據(jù)集下各個算法分類準(zhǔn)確率對比

5 總結(jié)

本文是以AdaBoost算法為基礎(chǔ),針對噪聲樣本造成的“過擬合問題”,對臨界樣本在計算權(quán)值時進行抑制,對于噪聲樣本采用k近鄰思想檢測噪聲樣本,對重新劃分的樣本進行分類. 本文使用UCI數(shù)據(jù)集來實驗,從多個方面來考察實驗結(jié)果,表明本文提出的算法都有較好的分類準(zhǔn)確率. 然而,在判斷噪聲樣本時k值的選擇是取樣本總數(shù)的5.6%,雖然這是多次實驗最終選擇的取值,在大多數(shù)情況下是有效的,但也有可能會碰到極端的情況,可能樣本點本身是噪聲點在5.6%的范圍內(nèi)存在多數(shù)噪聲點,算法會錯誤的把該樣本點判斷為非樣本點,最終影響分類的準(zhǔn)確率,因此k值的選擇有待進一步研究. 此外本文只是針對的二分類問題,不適用于多分類問題,因為AdaBoost算法要求每個弱分類器的準(zhǔn)確率大于1/2,但是在多分類問題中找到這種弱分類器很困難,需要從數(shù)學(xué)的角度重新創(chuàng)建模型,有學(xué)者提出多類指數(shù)損失函數(shù)的逐步添加模型[14],把分類器要求的準(zhǔn)確率降到1/n(n為類別數(shù)),但這無法保證有效性,因此提升到多分類問題還需要進一步研究尋找合適的模型.

1Freund Y,Schapire RE. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences,1997,55(1): 119–139. [doi:10.1006/jcss.1997.1504]

2Freund Y,Schapire RE. Experiments with a new boosting algorithm. Proc. of the 13th International Conference on International Conference on Machine Learning. Bari,Italy.1996. 148–156.

3李航. 統(tǒng)計學(xué)習(xí)方法. 北京: 清華大學(xué)出版社,2012: 3.

4Schapire RE,Singer Y. BoosTexter: A boosting-based system for text categorization. Machine Learning,2000,39(2-3): 135–168.

5Viola P,Jones MJ. Robust real-time face detection. International Journal of Computer Vision,2004,57(2): 137–154.[doi: 10.1023/B:VISI.0000013087.49260.fb]

6Jiang WX. Does boosting overfit: Views from an exact solution. Technical Report 00-03,Evanston,IL: Northwestern University,2000.

7Servedio RA. Smooth boosting and learning with malicious noise. Proc. of the 14th Annual Conference on Computational Learning Theory,COLT 2001 and 5th European Conference on Computational Learning Theory. Amsterdam,The Netherlands. 2003. 473–489.

8Gao YL,Gao F. Edited AdaBoost by weighted kNN.Neurocomputing,2010,73(16-18): 3079–3088. [doi: 10.1016/j.neucom.2010.06.024]

9Webb GI. MultiBoosting: A technique for combining boosting and wagging. Machine Learning,2000,40(2):159–196. [doi: 10.1023/A:1007659514849]

10付忠良. 關(guān)于AdaBoost有效性的分析. 計算機研究與發(fā)展,2008,45(10): 1747–1755.

11Freund Y,Schapire RE. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences,1997,55(1): 119–139. [doi:10.1006/jcss.1997.1504]

12周志華. 機器學(xué)習(xí). 北京: 清華大學(xué)出版社,2016: 1.

13R?tsch G,Onoda T,Müller KR. Regularizing AdaBoost.Proc. of the 1998 Conference on Advances in Neural Information Processing Systems II. Cambridge,MA,USA.1999. 564–570.

14胡金海,駱廣琦,李應(yīng)紅,等. 一種基于指數(shù)損失函數(shù)的多類分類 AdaBoost算法及其應(yīng)用. 航空學(xué)報,2008,29(4):811–816.

Improvement of AdaBoost Algorithm Based on Sample Noise Detection

ZHANG Zi-Xiang,CHEN You-Guang
(School of Computer Science and Software Engineering,East China Normal University,Shanghai 200333,China)

In the traditional AdaBoost algorithm,there are over-fitting problems caused by noise samples. In this paper,an improved AdaBoost algorithm based on noise detection is proposed,called NAdaBoost. According to the traditional AdaBoost algorithm,in the misclassified samples,noise samples vary widely in some attributes. NAdaBoost can,instead,determine the noise samples based on this,and then reuse the algorithm to classify the two types of samples,and ultimately achieve the purpose of improving the accuracy of classification. The experiment on the binary classification shows that the proposed algorithm has a higher classification accuracy compared with the traditional AdaBoost algorithm,as well as relative improvement of algorithms.

over-fitting; noise detection; AdaBoost algorithm; binary classification

張子祥,陳優(yōu)廣.基于樣本噪聲檢測的 AdaBoost算法改進.計算機系統(tǒng)應(yīng)用,2017,26(12):186–190. http://www.c-s-a.org.cn/1003-3254/6081.html

2017-03-03; 修改時間: 2017-03-20; 采用時間: 2017-03-29