分類器算法資料

關于adaboost的一些說明上學期拿出一部分時間來做adaboost，做的時候做了一些筆記。論壇上也有一些正在讀程序研究算法的人。我就把這份粗糙的筆記拿出來與大家分享一下吧?？隙ㄓ绣e誤的地方，也有不妥當的地方，大家不要太相信我

還有這個地方不能貼公式，不能貼圖片，還有我很懶，就挑了幾幅重要的貼了，其他的大家去看文章吧

排版不好看，也許寫得也不明白，大家多包涵，希望大家可以完善這個文檔。讓后來者少走些彎路。

不用發(fā)論壇消息問我，發(fā)在這里讓更多人看見，更多人解答，然后也可以讓更多的人知道，更好些

第一部分:算法的產生

1996年YoavFreund在ExperimentswithaNewBoostingAlgorithm中提出了AdaBoost.M1和AdaBoost.M2兩種算法.其中,AdaBoost.M1是我們通常所說的DiscreteAdaBoost;而AdaBoost.M2是M1的泛化形式.該文的一個結論是:當弱分類器算法使用簡單的分類方法時,boosting的效果明顯地統(tǒng)一地比bagging要好.當弱分類器算法使用C4.5時,boosting比bagging較好,但是沒有前者的比較來得明顯.

文獻中記錄的.M1算法

初始

1.獲得一組樣本(X)和它的分類(Y)和一個分類器(weaklearn).

2.賦予平均的權值分布D(i)

進入循環(huán):T次

1.賦予弱分類器權值D(i),使用弱分類器獲得樣本(X)到分類(Y)上的一個映射.(就是把某個X歸到某個Y類中去)

2.計算這個映射的誤差e.e=各個歸類錯誤的樣本權值之和.如果e>1/2那么弱分類器訓練失敗,挑出循環(huán),訓練結束(這在二值檢測中是不會發(fā)生的,而多值的情況就要看分類器夠不夠強健了)

3.設B=e/(1-e).用于調整權值.因為e<1/2.因此0<B<1

4.如果某樣本分類正確,該樣本的權值就乘以B讓權值變小;如果分類錯誤,就讓該樣本的權值乘以B^-1或者不變,這樣就讓分類正確的樣本權值降低,分類錯誤的樣本權值升高,加強了對較難分類樣本的分類能力

5.權值均衡化

循環(huán)結束

1.最終的分類器是,當一個X進入時,遍歷所有Y,尋找使(h(x)=y的情況下,log(1/B)之和)最大者即是輸出分類y

M2相比于M1的改進是允許弱分類器輸出多個分類結果,并輸出這幾個分類結果的可能性(注意,這里不是概率)

.M2的流程是

1.獲得一組樣本(X)和它的分類(Y)和一個分類器(weaklearn).

2.對于某個樣本Xi將它的分類歸為一個正確分類Yi和其他不正確分類Yb

3.樣本權值進行如下分布首先每個樣本分到1/m的權值,然后每個不正確分類分到(1/m)/Yb的個數.也就是說樣本權值是分到了每個不正確的分類上

進入循環(huán)

1.求每個樣本的權值,即每個樣本所有不正確的分類的權值和,再求每個樣本錯誤分類的權值,即不正確分類的權值除以該樣本的權值.最后將每個樣本的權值歸一化

2.將樣本權值和某樣本的不正確分類的權值輸入到weaklearn,獲得弱分類器的輸出為各個分類的可能值

3.計算偽錯誤率:公式見上

4.更新權值

退出循環(huán)

最終的強分類器:圖貼不出來了...

1999年,ROBERTE.SCHAPIRE和YORAMSINGER,于MachineLearning發(fā)表論文:ImprovedBoostingAlgorithmsUsingConfidence-ratedPredictions.提出了更具一般性的AdaBoost形式.提出了自信率以改善AdaBoost的性能.并提出了解決多標簽問題的AdaBoost.MH和AdaBoost.MR算法,其中AdaBoost.MH算法的一種形式又被稱為RealBoost算法.

事實上:DiscreteAdaBoost是指,弱分類器的輸出值限定在{-1,+1}，和與之相應的權值調整，強分類器生成的AdaBoost算法；RealAdaBoost是指，弱分類器輸出一個可能度，該值的范圍是整個R,和與之相應的權值調整，強分類器生成的AdaBoost算法。事實上，Discrete到Real的轉變體現(xiàn)了古典集合到模糊集合轉變的思想

至于GentleAdaBoost.考慮到(AdaBoost對”不像”的正樣本權值調整很高,而導致了分類器的效率下降),而產生的變種算法.它較少地強調難以分類的樣本.

RainerLienhart,AlexanderKuranov,VadimPisarevsky在論文EmpiricalAnalysisofDetectionCascadesofBoostedClassifiersforRapidObjectDetection中提出在stump弱分類器(即每個弱分類器使用一個特征進行分類)上進行的對比試驗中,Gentle的結果明顯好于Real和Discrete.大牛已經做出試驗了,我就不懷疑它了.

和上篇論文流程大體相同.作者還討論了alpha(t)的取法:

算法去看文章吧...這里不能直接貼圖

文獻中記錄的AdaBoost.MH算法

算法的運算流程:

1.得到一組樣本(m個)和樣本相應的分類,這個分類是由K個是和否的標簽組成.某一個樣本可以有多個是標簽.

*****************還有一篇巨大量負樣本的速度提高方法找不到了……

第三部分,OpenCv中AdaBoost訓練程序略解

這里只介紹一個大概的情況,具體的都寫在代碼的注釋里了.

1.結構:

程序的總體結構是一棵多叉樹,每個節(jié)點多少個叉由初始設定的maxtreesplits決定

樹節(jié)點結構:

typedefstructCvTreeCascadeNode

{

CvStageHaarClassifier*stage;//指向該節(jié)點stage強分類器的指針

structCvTreeCascadeNode*next;//指向同層下一個節(jié)點的指針

structCvTreeCascadeNode*child;//指向子節(jié)點的指針

structCvTreeCascadeNode*parent;//指向父節(jié)點的指針

structCvTreeCascadeNode*next_same_level;//最后一層葉節(jié)點之間的連接

structCvTreeCascadeNode*child_eval;//用于連接最終分類的葉節(jié)點和根節(jié)點

intidx;//表示該節(jié)點是第幾個節(jié)點

intleaf;//從來沒有用到過的參數

}CvTreeCascadeNode;

這里需要說明的是child_eval這個指針，雖說人臉檢測是一個單分類問題，程序中的maxtreesplits的設置值為0，沒有分叉，但是樹本身是解決多分類問題的，它有多個葉節(jié)點，也就有多個最終的分類結果。但是我們使用的時候，雖然是一個多分類的樹，也可能我們只需要判斷是或者不是某一類。于是我們就用root_eval和child_eval把這個分類上的節(jié)點索引出來，更方便地使用樹結構。當然，這一點在本程序中是沒有體現(xiàn)的。

分類器結構：

每個樹節(jié)點中都包含了一個CvStageHaarClassifier強分類器，而每個CvStageHaarClassifier包含了多個CvIntHaarClassifier弱分類器。當CvIntHaarClassifier被使用的時候，被轉化為CvCARTHaarClassifier，也就是分類樹與衰減數分類器作為一個弱分類器。

typedefstructCvCARTHaarClassifier

{

CV_INT_HAAR_CLASSIFIER_FIELDS()

intcount;/*在決策樹中的節(jié)點數numberofnodesinthedecisiontree*/

int*compidx;//特征序號

CvTHaarFeature*feature;//選出的特征。數組

CvFastHaarFeature*fastfeature;

float*threshold;/*arrayofdecisionthresholds*/

int*left;/*arrayofleft-branchindices*/

int*right;/*arrayofright-branchindices*/

float*val;/*arrayofoutputvalues*/

}CvCARTHaarClassifier;

CvCARTHaarClassifier結構中包含了弱分類器的左值右值閾值等數組，在我們的程序中CART只選用了一個特征進行分類，即退化成了stump。這里的數組里面就只存有一個元了

那么這里為什么要使用一個如此復雜的結構呢。大體來說有兩個好處：

1、方便弱分類器之間的切換，當我們不選用CART而是其他的弱分類器結構的時候，就可以調用CvIntHaarClassifier時轉換成其他的指針

2、這樣方便了Haar訓練的過程和Boost過程的銜接。

特征的結構：

2.OpenCV的HaarTraining程序中一種常用的編程方法：

在這個程序中，函數指針是一種很常用的手法。函數指針的轉換使讀程序的人更難把握程序的脈絡，在這里舉一個最極端的例子，來說明程序中這種手法的應用。

我們在cvBoost.cpp文件中的cvCreateMTStumpClassifier函數（這是一個生成多閾值(Multi-threshold)stump分類器的函數）下看到了一個這樣的調用：

findStumpThreshold_16s[stumperror]（……….）

這里對應的stumperror值是2

在cvboost.cpp中我們找到了一個這樣的數組

CvFindThresholdFuncfindStumpThreshold_16s[4]={

icvFindStumpThreshold_misc_16s,

icvFindStumpThreshold_gini_16s,

icvFindStumpThreshold_entropy_16s,

icvFindStumpThreshold_sq_16s

};

這個數組的類型是一個類型定義過的函數指針typedefint(*CvFindThresholdFunc)（…..）

因此這個數組中的四項就是四個指針，我們在cvCreateMTStumpClassifier中調用的也就是其中的第三項icvFindStumpThreshold_entropy_16s。

然后我們發(fā)現(xiàn)這個函數指針沒有直接的顯性的實現(xiàn)。那么問題出在哪里呢？

它是通過宏實現(xiàn)的：

程序中定義了一個這樣的宏：

#defineICV_DEF_FIND_STUMP_THRESHOLD_SQ(suffix,type)

ICV_DEF_FIND_STUMP_THRESHOLD(sq_##suffix,type,

/*calculateerror(sumofsquares)*/

/*err=sum(w*(y-left(rigt)Val)^2)*/

curlerror=wyyl+curleft*curleft*wl-2.0F*curleft*wyl;

currerror=(*sumwyy)-wyyl+curright*curright*wr-2.0F*curright*wyr;

)

和一個這樣的宏：

#defineICV_DEF_FIND_STUMP_THRESHOLD(suffix,type,error)

CV_BOOST_IMPLinticvFindStumpThreshold_##suffix(…..)

{

……..

}

這兩個宏中，后者是函數的主體部分，而函數的定義通過前者完成。即：

ICV_DEF_FIND_STUMP_THRESHOLD_ENTROPY(16s,short)，這樣的形式完成。這相當于給前者的宏傳遞了兩個參數，前者的宏將第一個參數轉換成sq_16s后和第二個參數一起傳到后者的宏。（##是把前后兩個string連接到一起，string是可變的兩，在這里suffix就放入了16s和sq_結合成了sq_16s）

后者的宏接收到參數以后就進行了函數的定義：

CV_BOOST_IMPLinticvFindStumpThreshold_sq_16s

這樣icvFindStumpThreshold_sq_16s就被定義了。這樣做的好處是，12個非常相似的函數可以通過兩個宏和12個宏的調用來實現(xiàn)，而不需要直接定義12個函數。

3.訓練結果中數據的含義：

-<feature>

-<rects>

<_>64129-1.</_>

//矩陣。前四個數值是矩陣四個點的位置，最后一個數值是矩陣像素和的權值

<_>671233.</_>

//矩陣。前四個數值是矩陣四個點的位置，最后一個是像素和的權值，這樣兩個矩陣就形成了一個Haar特征

</rects>

<tilted>0</tilted>//是否是傾斜的Haar特征

</feature>

<threshold>-0.0315119996666908</threshold>//閾值

<left_val>2.0875380039215088</left_val>//小于閾值時取左值

<right_val>-2.2172100543975830</right_val>//大于閾值時取右值

4.訓練過程中使用的算法

這里主要講弱分類器算法

?矩形特征值：Value[i][j],1≤i≤n代表所有的Haar特征，1≤j≤m代表所有的樣本

?FAULT=(curlerror+currerror)表示當前分類器的錯誤率的最小值，初始設置：curlerrorcurrerror=1000000000000000000000000000000000000000000000000(反正給個暴力大的數值就對了)

幾種adaboos算法的區(qū)別事實上:DiscreteAdaBoost是指,弱分類器的輸出值限定在{-1,+1}，和與之相應的權值調整，強分類器生成的AdaBoost算法；RealAdaBoost是指，弱分類器輸出一個可能度，該值的范圍是整個R,和與之相應的權值調整，強分類器生成的AdaBoost算法。事實上，Discrete到Real的轉變體現(xiàn)了古典集合到模糊集合轉變的思想

Logit和Gentle算法是由同一個人提出的，他認為adaboost實際上是一個尋優(yōu)過程，然后用運籌學里的兩種不同的尋優(yōu)方法提出了logit和gentle，logit是自適應的牛頓法，gentle是用的牛頓步長法。作者認為，logitAdaBoost在每一輪中都使目標最優(yōu),會使訓練樣本的代表性下降。然后這位作者的這篇文章被幾位大牛批了一遍...具體見DiscussionofthePaperAdditiveLogisticRegressionAStatisticalViewofBoostingbyJeromeFriedman,TrevorHastieandRobertTibshirani

另外，值得一提的是

1、2004年,BoWU&HaizhouAI&ChangHUANG&ShihongLAO在ComputerSociety上發(fā)表文章FastRotationInvariantMulti-ViewFaceDetectionBasedonRealAdaBoost.提出了使用RealBoost檢測旋轉人臉，獲得了很好的效果

2、2002年,RainerLienhart&AlexanderKuranov&VadimPisarevsky在MRLTechnicalReport上發(fā)表EmpiricalAnalysisofDetectionCascadesofBoostedClassifiersforRapidObjectDetection.通過試驗得出結論,在人臉檢測上GentleAdaBoost的效果要好于Discrete和Real。這也是Opencv里為什么要用Gentle的原因吧Gentleboost算法的人物檢測方法,利用人物的身體碎片以及這些碎片相對于身體中心的相對位置作為特征,用Gentleboost算法訓練的分類器來對人體進行分類。為了提高分類器的學習效率,解決復雜場景中人體檢測的難題,提出了一種利用線性回歸末端作為弱分類器的方法,從正、負兩個方面對預測模型進行加權,改變了原來的僅從正預測進行加權的方法1.2Gentleboost算法及其操作步驟本文采用的Gentleboost算法是AdaBoosting算法的進一步改進,它比AdaBoost收斂的要快而且對于物體檢測執(zhí)行的也比較好[1],針對人體比較復雜,有關節(jié)相連,容易發(fā)生變形,而且所處的環(huán)境復雜多變,檢測困難的特點,對原來的Gentleboost算法作了進一步的改進。假如X表示樣本集,Rn表示樣本空間,Y表示類別標識集合,由于人物檢測是二值分類問題,此時Y={1,-1},分別對應樣本的正和負。對于N個被標注的樣例數列[(x1,y1),?,(xN,yN)],這里xi∈Rn,yi∈Y±1。(1)首先,初始化權值w=1,而不是以前的wi=1/N,這樣使執(zhí)行起來比較方