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

張子祥,陳優廣

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

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

張子祥,陳優廣

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

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

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

1 引言

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

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

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

2 AdaBoost算法介紹

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

2.1 算法流程

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

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

3 改進的算法及其分析

3.1 原算法分析

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

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

3.2 樣本噪聲處理

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

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

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

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

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

3.3 NAdaBoost算法流程

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

4 實驗

4.1 實驗方法

本文主要是針對二分類問題進行研究,因此使用著名的加州大學歐文分校提出的數據庫UCI,從其中選出部分二分類數據集來進行實驗. UCI數據庫是行業內經常被用于數據挖掘,機器學習的標準測試數據庫. 本文隨機從中選取了9組數據集,如表1所示.

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

表1 數據集信息

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

4.2 本文算法與其他算法比較結果

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

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

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

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

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

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

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

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

圖2 ionosphere數據集下各個算法分類準確率對比

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

圖3 mushroom數據集下各個算法分類準確率對比

圖4 sonar數據集下各個算法分類準確率對比

5 總結

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

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李航. 統計學習方法. 北京: 清華大學出版社,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付忠良. 關于AdaBoost有效性的分析. 計算機研究與發展,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周志華. 機器學習. 北京: 清華大學出版社,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胡金海,駱廣琦,李應紅,等. 一種基于指數損失函數的多類分類 AdaBoost算法及其應用. 航空學報,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

張子祥,陳優廣.基于樣本噪聲檢測的 AdaBoost算法改進.計算機系統應用,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