Opencv2.4.9源碼分析——RandomTrees要點(diǎn)

《Opencv2.4.9源碼分析——RandomTrees要點(diǎn)》由會(huì)員分享，可在線閱讀，更多相關(guān)《Opencv2.4.9源碼分析——RandomTrees要點(diǎn)（19頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、Opencv2.4.9 源碼分析RandomTrees一、原理隨機(jī)森林（Random Forest）的思想最早是由 Ho于1995年首次提出，后來 Breiman完整系統(tǒng)的發(fā)展了該算法，并命名為隨機(jī)森林，而且他和他的博士學(xué)生兼同事Cutler 把 RandomForest注冊(cè)成了商標(biāo)，這可能也是 OpenCV把該算法命名為 Random Trees的原因吧。一片森林是由許多棵樹木組成， 森林中的每棵樹可以說是彼此不相關(guān)， 也就是說每棵樹木的生長(zhǎng)完全是由自身?xiàng)l件決定的， 只有保持森林的多樣性， 森林才能更好的生長(zhǎng)下去。 隨機(jī)森林算法與真實(shí)的森林相類似， 它是由許多決策樹組成， 每棵決策樹之間是不

2、相關(guān)的。 而隨機(jī)森林算法的獨(dú)特性就體現(xiàn)在 “隨機(jī)” 這兩個(gè)字上： 通過隨機(jī)抽取得到不同的樣本來構(gòu)建每棵決策樹； 決策樹每個(gè)節(jié)點(diǎn)的最佳分叉屬性是從由隨機(jī)得到的特征屬性集合中選取。 下面就詳 細(xì)介紹這兩次隨機(jī)過程。雖然在生成每棵決策樹的時(shí)候， 使用的是相同的參數(shù)， 但使用的是不同的訓(xùn)練集合， 這些訓(xùn)練集合是從全體訓(xùn)練樣本中隨機(jī)得到的，這一過程稱之為 bootstrap 過程，得到的隨機(jī)子集稱之為 bootstrap 集合，而在bootstrap 集合的基礎(chǔ)上聚集得到的學(xué)習(xí)模型的過程稱之為Bagging （Bootstrap aggregating） ， 那些不在bootstrap 集合中的樣本稱之

3、為 OOB（ Out Of Bag ） 。Bootstrap 過程為：從全部N 個(gè)樣本中，有放回的隨機(jī)抽取S 次（在 Opencv 中， S=N ） ，由于是有放回的抽取，所以肯定會(huì)出現(xiàn)同一個(gè)樣本被抽取多次的現(xiàn)象，因此即使S=N ，也會(huì)存在OOB。我們可以計(jì)算 OOB樣本所占比率：每個(gè)樣本被抽取的概率為1/N,未被抽取的概率為（1 1/N）,抽取S次仍然沒有被抽到的概率就為 （1 1/N）S ,如果S和N都趨于無窮 大，則（1 1/N）Se1 = 0.368,即OOB樣本所占全部樣本約為 36.8%,被抽取到的樣本為63.2% 。 隨機(jī)森林中的每棵決策樹的bootstrap 集合是不完全相同的

4、， 因此每棵決策樹的 OOB集合也是不完全相同的，所以對(duì)于訓(xùn)練集合中的某個(gè)樣本來說，它可能屬于決策樹Ti 的bootstrap 集合，而屬于決策樹Tj 的 OOB 集合。因?yàn)樵谏擅靠脹Q策樹之前，都要進(jìn)行bootstrap 過程，而每次bootstrap 過程所得到的bootstrap 集合都會(huì)不同，所以保證了每棵決策樹的不相關(guān)以及不相同。為了進(jìn)一步保證決策樹的多樣性， Breiman 又提出了第二個(gè)隨機(jī)性。一般的決策樹是在全部特征屬性中進(jìn)行計(jì)算， 從而得到最佳分叉屬性， 決策樹的節(jié)點(diǎn)依據(jù)該屬性進(jìn)行分叉。 而隨機(jī)森林的決策樹的最佳分叉屬性是在一個(gè)特征屬性隨機(jī)子集內(nèi)進(jìn)行計(jì)算得到的。 在全部 p

5、個(gè)特征屬性中，隨機(jī)選擇q 個(gè)特征屬性，對(duì)于分類問題， q 可以為 p 的平方根，對(duì)于回歸問題，q 可以為 p 的三分之一。對(duì)于隨機(jī)森林中的所有決策樹，隨機(jī)子集內(nèi)的特征屬性的數(shù)量 q 是 固定不變的，但不同的決策樹， 這 q 個(gè)特征屬性是不同， 而對(duì)于同一棵決策樹，它的全部節(jié)點(diǎn)應(yīng)用的是同一個(gè)隨機(jī)子集。另外由于q遠(yuǎn)小于p,所以構(gòu)建決策樹時(shí)無需剪枝。以上內(nèi)容是在訓(xùn)練過程中，隨機(jī)森林與其他基于決策樹算法的不同之處。而在預(yù)測(cè)過程中，方法基本相同， 預(yù)測(cè)樣本作用于所有的決策樹，對(duì)于分類問題，利用投票的方式， 最多得票數(shù)的分類結(jié)果即為預(yù)測(cè)樣本的分類，對(duì)于回歸問題，所有決策樹結(jié)果的平均值即為預(yù)測(cè)值。再回到前面

6、的訓(xùn)練過程中， 為什么我們要使用 Bagging 方法？這是因?yàn)槭褂?Bagging 方法可以減小訓(xùn)練過程中的噪聲和偏差， 并且更重要的是， 它還可以評(píng)估預(yù)測(cè)的誤差和衡量特征屬 性的重要程度。常用的評(píng)估機(jī)器學(xué)習(xí)算法的預(yù)測(cè)誤差方法是交叉驗(yàn)證法， 但該方法費(fèi)時(shí)。 而 Bagging 方法不需要交叉驗(yàn)證法，我們可以計(jì)算OOB 誤差，即利用那些36.8% 的 OOB 樣本來評(píng)估預(yù)測(cè)誤差。已經(jīng)得到證明， OOB 誤差是可以代替bootstrap 集合誤差的，并且其結(jié)果近似于交叉驗(yàn)證。 OOB 誤差的另一個(gè)特點(diǎn)是它的計(jì)算是在訓(xùn)練的過程中同步得到的，即每得到一棵決策樹，我們就可以根據(jù)該決策樹來調(diào)整由前面的決

7、策樹得到的 OOB 誤差。對(duì)于分類問題，它 的 OOB 誤差計(jì)算的方法和步驟為：構(gòu)建生成了決策樹Tk, k=1,2,，K用 Tk 預(yù)測(cè) Tk 的 OOB 樣本的分類結(jié)果更新所有訓(xùn)練樣本的 OOB 預(yù)測(cè)分類結(jié)果的次數(shù)（如樣本xi 是 T1 的 OOB 樣本，則它有一個(gè)預(yù)測(cè)結(jié)果，而它是T2 的 bootstrap 集合內(nèi)的樣本，則此時(shí)它沒有預(yù)測(cè)結(jié)果）對(duì)所有樣本，把每個(gè)樣本的預(yù)測(cè)次數(shù)最多的分類作為該樣本在Tk時(shí)的預(yù)測(cè)結(jié)果統(tǒng)計(jì)所有訓(xùn)練樣本中預(yù)測(cè)錯(cuò)誤的數(shù)量該數(shù)量除以 Tk 的 OOB 樣本的數(shù)量作為 Tk 時(shí)的 OOB 誤差對(duì)于回歸問題，它的 OOB 誤差計(jì)算的方法和步驟為：構(gòu)建生成了決策樹Tk, k=

8、1,2,，K用 Tk 預(yù)測(cè) Tk 的 OOB 樣本的回歸值累加所有訓(xùn)練樣本中的 OOB 樣本的預(yù)測(cè)值對(duì)所有樣本，計(jì)算 Tk時(shí)的每個(gè)樣本的平均預(yù)測(cè)值，即預(yù)測(cè)累加值除以被預(yù)測(cè)的次數(shù)累加每個(gè)訓(xùn)練樣本平均預(yù)測(cè)值與真實(shí)響應(yīng)值之差的平方該平方累加和除以 Tk 的 OOB 樣本的數(shù)量作為 Tk 時(shí)的 OOB 誤差很顯然，隨著決策樹的增多，OOB誤差會(huì)趨于縮小，因此我們可以設(shè)置一個(gè)精度e ,當(dāng)Tk的OOB誤差小于時(shí)，我們可以提前終止迭代過程，即不必再生成 Tk+1及以后的決策樹 了。即特征屬性不僅能夠預(yù)測(cè)樣本， 而且還能夠得到樣本的哪個(gè)特征屬性對(duì)預(yù)測(cè)起到?jīng)Q定作用，Bagging方法在的重要性，也是機(jī)器學(xué)習(xí)的一

9、項(xiàng)主要任務(wù)，并且在實(shí)際應(yīng)用中越來越重要。隨機(jī)森林中的另一個(gè)作用就是可以計(jì)算特征屬性的重要程度。目前有兩種主要的方法用于計(jì)算特征屬性的重要性：Gini法和置換法。Gini法依據(jù)的是不純度減小的原則，在這里我們重點(diǎn)介紹置換法。置換法依據(jù)的原則是；樣本的某個(gè)特征屬性越重要.那么改變?cè)撎卣鲗傩缘闹担瑒t該樣本 的預(yù)測(cè)值就越容易出現(xiàn)錯(cuò)誤,置換法是通過置檢兩個(gè)樣本的相同特征屬性的值來改變特征 屬性的它的具體方法是：在決策樹7X的。日集合中隨機(jī)選擇兩個(gè)樣本K產(chǎn)(現(xiàn)1周2 西加和X尸的1.刃2的每個(gè)樣本具有戶個(gè)特征屬性這兩個(gè)樣本的響應(yīng)值A(chǔ)別為并和歲,而用丁的這兩個(gè)樣本的預(yù)硼值分別為門,，設(shè)逮。0日集含中一共有m

10、*個(gè)樣本.我們衡量第價(jià)特征屬性的重要性則置換翼茶中的町萍與q.置頓后的樣本 為口q=M,1為題灑算妒邂1題中葺G依據(jù)該方法J為006集合共置 換m3文,則最終*換的結(jié)果為x荷,1,潑血中jX/p)o用T對(duì)國(guó)的預(yù)惻值為 八小 對(duì)于分類問題，如果北取工修，說明改變第q個(gè)特征屬性的值，并不改變最簿的響應(yīng)值，也就是第仆特征屬性對(duì)“來說不是很重要，而如果以秒為小說明改變第什特征 屬性的值餞改變最繆的響應(yīng)值，因此謖特征屬性重要,下式則為這種重要程度的量化能 式：工皿/儀=5產(chǎn))二工證加止=渣)用上(1)式中,分子中的第一項(xiàng)表示對(duì)00日中預(yù)測(cè)正確的樣本的數(shù)量,而分子中的第二項(xiàng)表示置 摭后預(yù)測(cè)正確的樣本數(shù)量-

11、而對(duì)于回歸問題 它的重要程度的量化花式為：式中，A = rnax| y( | iGN *如果第（TT特征屬性不屬于不，V!q= 0,對(duì)隨機(jī)森林中的所有決策樹都應(yīng)用式1或式2 計(jì)算第H特征雇性的重要性則取平均得到整個(gè)隨機(jī)森林對(duì)第M特征屬性的重要程度的 量化毯式為3哨(4)最后,我們對(duì)所有的特征厘性的重要程度進(jìn)行歸一化處理，則第M特征屬性的歸一化 為：至從隨機(jī)森林提出以來，該篁法已成為一種流行的被廣泛使用的非參數(shù)回歸應(yīng)用的工具, 日向E日口對(duì)該苴法總結(jié)了以下一些特點(diǎn)：在目前所有的機(jī)藉學(xué)習(xí)笠法中具有無法比擬的預(yù)測(cè)楮度能妙有效的處理大型數(shù)患庫(kù)不需要任何的特征雇性的刪瀛-就能解處理具有上千種特征屬性的樣

12、本能雄給出特征屬性的重要程度在隨機(jī)森林的構(gòu)建過程中 就可以得到匿化誤差的內(nèi)部無偏估計(jì)即使包含一定比例的缺失特征屬性的樣本j也能夠得到睢確的預(yù)棚在樣本種群不均衡的數(shù)據(jù)庫(kù)中，也能蜉平衡這種情況構(gòu)建好的隨機(jī)森林可以破保存下來.用于以后的其他數(shù)據(jù)的使用二、源碼分析我們先給出表示隨機(jī)森林參數(shù)的類的一個(gè)構(gòu)造函數(shù):boolcpp view plain copy 在CODE上查看代碼片派生到我的代碼片 CvRTParams:CvRTParams( int _max_depth, int _min_sample_count, float _regression_accuracy, bool _use_surro

13、gates, int _max_categories, const float* _priors, _calc_var_importance,int _nactive_vars, int max_num_of_trees_in_the_forest, float forest_accuracy, int termcrit_type ):CvDTreeParams( _max_depth, _min_sample_count, _regression_accuracy, _use_surrogates, _max_categories, 0, false, false, _priors ), c

14、alc_var_importance(_calc_var_importance), nactive_vars(_nactive_vars)term_crit = cvTermCriteria(termcrit_type,max_num_of_trees_in_the_forest, forest_accuracy);_max_depth 表示決策樹的深度，該值的大小嚴(yán)重影響擬合的效果_min_sample_count 表示決策樹節(jié)點(diǎn)的最小樣本數(shù)，如果節(jié)點(diǎn)的樣本數(shù)小于該值，則該節(jié)點(diǎn)不再分叉，一般該值為樣本總數(shù)的1%_regression_accuracy 表示終止構(gòu)建回歸樹的一個(gè)條件， 回歸樹的

15、響應(yīng)值的精度如果達(dá)到了該值，則無需再分叉。該值不能小于0，否則報(bào)錯(cuò)_use_surrogates表示是否使用 替代分叉節(jié)點(diǎn)_max_categories 表示特征屬性為類的形式的最大的類的數(shù)量_priors 表示決策樹的特征屬性的先驗(yàn)概率以上幾個(gè)參數(shù)是用于構(gòu)建決策樹時(shí)的參數(shù)CvDTreeParams ， 其中 0 表示不使用交叉驗(yàn)證方法，兩個(gè)false分別表示不應(yīng)用1SE規(guī)則和不移除被剪掉的節(jié)點(diǎn)。_calc_var_importance 表示是否計(jì)算特征屬性的重要程度_nactive_vars 表示用于尋找最佳分叉屬性的每個(gè)節(jié)點(diǎn)的隨機(jī)特征屬性的數(shù)量， 如果該值設(shè)置 為 0，則表示該值為樣本的全

16、部特征屬性的平方根 max_num_of_trees_in_the_forest 表示森林中決策樹的最大數(shù)量，也就是最大迭代次數(shù)，因?yàn)槊康淮尉蜁?huì)得到一棵決策樹。通常來說， 決策樹越多，預(yù)測(cè)越準(zhǔn)確，但決策樹的數(shù)量達(dá)到一定程度后， 準(zhǔn)確度的增長(zhǎng)會(huì)減小甚至趨于不變， 另一方面， 預(yù)測(cè)時(shí)間是與決策樹的數(shù)量呈線性關(guān)系的以決策樹達(dá)到以精度到達(dá)為任一條件達(dá)到forest_accuracy 表示 OOB 誤差的精度要求termcrit_type 表 示 隨 機(jī) 森 林 構(gòu) 建 的 終 止 準(zhǔn) 則 ， CV_TERMCRIT_ITER max_num_of_trees_in_the_forest 為 終 止

17、 條 件 ； CV_TERMCRIT_EPS forest_accuracy 為終止條件； CV_TERMCRIT_ITER | CV_TERMCRIT_EPS 即終止缺省的 CvRTParams 構(gòu)造函數(shù)為：cpp view plain copy 在 CODE 上查看代碼片派生到我的代碼片CvRTParams:CvRTParams() : CvDTreeParams( 5, 10, 0, false, 10, 0, false, false, 0 ),calc_var_importance(false), nactive_vars(0)term_crit = cvTermCriteria(

18、CV_TERMCRIT_ITER+CV_TERMCRIT_EPS, 50, 0.1 );下面為隨機(jī)森林模型的類CvRTrees,它的構(gòu)造函數(shù)為：cpp view plain copy 在 CODE 上查看代碼片派生到我的代碼片CvRTrees:CvRTrees() nclassesoob_errorntreestreesdataactive_var_maskvar_importance= 0;= 0;= 0;= NULL;= NULL;= NULL;= NULL;/表示分類類別數(shù)量/表示OOB 誤差/表示決策樹的數(shù)量/表示決策樹;/ 表示用于構(gòu)建決策樹的樣本數(shù)據(jù)/表示隨機(jī)特征屬性的掩碼/表示特

19、征屬性的重要性rng = &cv:theRNG();實(shí)例化rng,表示隨機(jī)數(shù)default_model_name = my_random_trees;下面是訓(xùn)練隨機(jī)森林的函數(shù)：cpp view plain copy 在 CODE 上查看代碼片派生到我的代碼片bool CvRTrees:train( const CvMat* _train_data, int _tflag,const CvMat* _responses, const CvMat* _var_idx,const CvMat* _sample_idx, const CvMat* _var_type,const CvMat* _mis

20、sing_mask, CvRTParams params )/_train_data 訓(xùn)練樣本數(shù)據(jù)，必須為 32FC1 類型的矩陣形式/_tflag 訓(xùn)練數(shù)據(jù)的特征屬性類型，如果為 CV_ROW_SAMPLE ，表示樣本是以行的形式儲(chǔ)存的，即 _train_data 矩陣的每一行為一個(gè)樣本；如果為 CV_COL_SAMPLE ，表示樣本是以列的形式儲(chǔ)存的/_responses 樣本的結(jié)果，即響應(yīng)值， 該值必須是32SC1 或 32FC1 類型的一維矩陣 （即矢量）的形式，并且元素的數(shù)量必須與訓(xùn)練樣本數(shù)據(jù)_train_data 的樣本數(shù)一致/_var_idx 標(biāo)識(shí)感興趣的特征屬性，即真正用于訓(xùn)練

21、的那些特征屬性，該值的形式與_sample_idx 變量相似/_sample_idx 標(biāo)識(shí)感興趣的樣本， 即真正用于訓(xùn)練的樣本， 該值必須是一維矩陣的形式， 即矢量的形式，并且類型必須是8UC1、8SU1或者32SC1。如果為8UC1或8SU1 ,則該值的含義是用掩碼的形式表示對(duì)應(yīng)的樣本，即 0 表示不感興趣的樣本，其他數(shù)為感興趣的樣本，因此矢量的元素?cái)?shù)量必須與訓(xùn)練樣本數(shù)據(jù)_train_data的樣本數(shù)一致；如果為 32SC1,則該值的含義是那些感興趣的樣本的索引， 而不感興趣的樣本的索引不在該矢量中出現(xiàn)， 因此該矢量的元素?cái)?shù)量可以小于或等于_train_data 的樣本數(shù)/_var_type

22、 特征屬性的形式， 是類的形式還是數(shù)值的形式， 用掩碼的形式表現(xiàn)對(duì)應(yīng)特征屬性的形式， 0 表示為數(shù)值的形式， 1 表示為類的形式。該值必須是一維矩陣，并且元素的數(shù)量必須是真正用于訓(xùn)練的那些特征屬性的數(shù)量加1，多余的一個(gè)元素表示的是響應(yīng)值的形式，即是分類樹還是回歸樹/_missing_mask 缺失的特征屬性，用掩碼的形式表現(xiàn)對(duì)應(yīng)的特征屬性， 0 表示沒有缺失，而且必須與 _train_data 的矩陣尺寸大小一致/params 為構(gòu)建隨機(jī)森林的參數(shù)clear();/ 清空一些全局變量/得到用于構(gòu)建決策樹的參數(shù)CvDTreeParams tree_params( params.max_depth

23、, params.min_sample_count, params.regression_accuracy, params.use_surrogates, params.max_categories, params.cv_folds, params.use_1se_rule, false, params.priors );data = new CvDTreeTrainData(); / 實(shí)例化 data/得到用于構(gòu)建決策樹的樣本數(shù)據(jù)data-set_data( _train_data, _tflag, _responses, _var_idx, _sample_idx, _var_type,

24、_missing_mask, tree_params, true);int var_count = data-var_count; / 表示特征屬性的數(shù)量/隨機(jī)特征屬性的數(shù)量nactive_vars 一定不能大于全部特征屬性的數(shù)量var_countif( params.nactive_vars var_count ) params.nactive_vars = var_count;/如果nactive_vars 為 0 ，則nactive_vars 重新賦值為 var_count 的平方根else if( params.nactive_vars = 0 )params.nactive_vars

25、 = (int)sqrt(double)var_count);else if( params.nactive_vars 0 )/如果nactive_vars 小于0 ，則報(bào)錯(cuò)CV_Error( CV_StsBadArg, must be non-negative );/ Create mask of active variables at the tree nodes/創(chuàng)建一個(gè)用于特征屬性掩碼的變量active_var_mask = cvCreateMat( 1, var_count, CV_8UC1 );/如果calc_var_importance 為 true ，則創(chuàng)建一個(gè)用于表示特征屬性

26、重要性的變量if( params.calc_var_importance )var_importance = cvCreateMat( 1, var_count, CV_32FC1 );cvZero(var_importance);/初始化為0 / initialize active variables maskCvMat submask1, submask2;/確保全部特征屬性的數(shù)量不能小于1 ，隨機(jī)特征屬性的數(shù)量不能小于0，并且前者不能小于后者CV_Assert( (active_var_mask-cols = 1) & (params.nactive_vars 0) & (params.

27、nactive_vars cols) );/對(duì)于active_var_mask 矩陣，前 nactive_vars 列的所有元素賦值為 1 ，其余的賦值為0cvGetCols( active_var_mask, &submask1, 0, params.nactive_vars );cvSet( &submask1, cvScalar(1) );if( params.nactive_vars cols )cvGetCols( active_var_mask, &submask2, params.nactive_vars, var_count );cvZero( &submask2 );/調(diào)用

28、grow_forest 函數(shù)，由決策樹構(gòu)建森林return grow_forest( params.term_crit );生成隨機(jī)森林的函數(shù)grow_forest ：cpp view plain copy 在 CODE 上查看代碼片派生到我的代碼片bool CvRTrees:grow_forest( const CvTermCriteria term_crit ) /表示用于構(gòu)建單棵決策樹的隨機(jī)樣本的掩碼，抽取到的樣本掩碼為0xFF ，否則為0CvMat* sample_idx_mask_for_tree = 0;/表示用于構(gòu)建單棵決策樹的隨機(jī)樣本，該矩陣存儲(chǔ)的是這些樣本在全部樣本中的索引值

29、CvMat* sample_idx_for_tree = 0;const int max_ntrees = term_crit.max_iter; /得到最大迭代次數(shù)const double max_oob_err = term_crit.epsilon;/得到OOB 誤差精度const int dims = data-var_count;/得到樣本的特征屬性的數(shù)量float maximal_response = 0;/表示最大的響應(yīng)值，即式3 中的參數(shù) A/表示OOB 樣本的響應(yīng)值的投票結(jié)果，用于分類問題CvMat* oob_sample_votes= 0;CvMat* oob_respon

30、ses= 0;/OOB 樣本的響應(yīng)值，用于回歸問題= 0;= 0;= 0;OOB/表示樣本矩陣的首地址指針/表示缺失特征屬性矩陣的首地址指針/表示樣本響應(yīng)值矩陣的首地址指針誤差精度或需要計(jì)算特征屬性重要程度float* oob_samples_perm_ptr= 0; /OOB 樣本的置換指針float* samples_ptr uchar* missing_ptr float* true_resp_ptr /該標(biāo)識(shí)變量表示應(yīng)用bool is_oob_or_vimportance = (max_oob_err 0& term_crit.type !=CV_TERMCRIT_ITER) | va

31、r_importance;/ oob_predictions_sumi = sum of predicted values for the i-th sample/ oob_num_of_predictionsi = number of summands/(number of predictions for the i-th sample)/ initialize these variable to avoid warning C4701/ oob_predictions_sum 表示某個(gè)訓(xùn)練樣本在所有決策樹OOB 集合中的預(yù)測(cè)值累加和CvMat oob_predictions_sum = c

32、vMat( 1, 1, CV_32FC1 );/ oob_num_of_predictions 表示某個(gè)訓(xùn)練樣本在所有決策樹OOB 集合中的被預(yù)測(cè)數(shù)量CvMat oob_num_of_predictions = cvMat( 1, 1, CV_32FC1 );nsamples = data-sample_count;/表示樣本的全體數(shù)量nclasses = data-get_num_classes();/表示分類問題的樣本分類類別數(shù)量if ( is_oob_or_vimportance )/該變量為真if( data-is_classifier )/分類問題/創(chuàng)建oob_sample_vote

33、s變量，矩陣大小為樣本總數(shù)x分類類別數(shù)oob_sample_votes = cvCreateMat( nsamples, nclasses, CV_32SC1 );cvZero(oob_sample_votes); / 初始化為 0else/ 回歸問題/ oob_responses0,i = oob_predictions_sumi/= sum of predicted values for the i-th sample/ oob_responses1,i = oob_num_of_predictionsi/= number of summands (number of prediction

34、s for the i-th sample)/創(chuàng)建oob_responses變量，矩陣大小為 2 x樣本總數(shù)，其中oob_responses0,i=oob_predictions_sumi ， oob_responses1,i = oob_num_of_predictionsioob_responses = cvCreateMat( 2, nsamples, CV_32FC1 );cvZero(oob_responses);/初始化為0/ oob_predictions_sum 指向矩陣 oob_responses 的第 0 行cvGetRow( oob_responses, &oob_pre

35、dictions_sum, 0 );/ oob_num_of_predictions 指向矩陣 oob_responses 的第 1 行 cvGetRow( oob_responses, &oob_num_of_predictions, 1 );/分配空間給下面4 個(gè)變量oob_samples_perm_ptr samples_ptr missing_ptr true_resp_ptr/從樣本數(shù)據(jù)中得到指針= (float*)cvAlloc( sizeof(float)*nsamples*dims );= (float*)cvAlloc( sizeof(float)*nsamples*dims

36、 );= (uchar*)cvAlloc( sizeof(uchar)*nsamples*dims );= (float*)cvAlloc( sizeof(float)*nsamples );samples_ptr、 missing_ptr 和 true_resp_ptr data-get_vectors( 0, samples_ptr, missing_ptr, true_resp_ptr );double minval, maxval;/定義并得到樣本的響應(yīng)值CvMat responses = cvMat(1, nsamples, CV_32FC1, true_resp_ptr);/得到響

37、應(yīng)值中的最大值maxval 和最小值 minval ， minval 有可能是負(fù)數(shù)cvMinMaxLoc( &responses, &minval, &maxval );/式 3maximal_response = (float)MAX( MAX( fabs(minval), fabs(maxval) ), 0 );為trees分配內(nèi)存空間trees = (CvForestTree*)cvAlloc( sizeof(trees0)*max_ntrees );memset( trees, 0, sizeof(trees0)*max_ntrees );決策樹 trees 初始化為 0/創(chuàng)建下面兩個(gè)

38、變量sample_idx_mask_for_tree = cvCreateMat( 1, nsamples, CV_8UC1 );sample_idx_for_tree = cvCreateMat( 1, nsamples, CV_32SC1 );ntrees = 0;/決策樹的索引值，先初始化為 0/進(jìn)入構(gòu)建隨機(jī)森林的循環(huán)體中while( ntrees max_ntrees )/ 滿足最大迭代次數(shù)時(shí)，結(jié)束迭代/ oob_samples_count 用于 OOB 樣本計(jì)數(shù)int i, oob_samples_count = 0;/分類問題，該值表示式1 中分子的第一項(xiàng)；回歸問題，為式2 中的分

39、子第一項(xiàng)double ncorrect_responses = 0; / used for estimation of variable importanceCvForestTree* tree = 0;/實(shí)例化 CvForestTree 類，表示當(dāng)前要構(gòu)建的決策樹cvZero( sample_idx_mask_for_tree );/初始化0/遍歷所有樣本，得到用于構(gòu)建決策樹的樣本for(i = 0; i data.ii = idx;/賦值樣本的索引值sample_idx_mask_for_tree-data.ptridx = 0xFF;/該樣本的掩碼treesntrees = new Cv

40、ForestTree();/實(shí)例化隨機(jī)森林tree = treesntrees; /決策樹賦值/訓(xùn)練單棵決策樹，它首先調(diào)用 CvForestTree 類中的 train 虛函數(shù)， 而最終調(diào)用的是CvDTree 類的 do_train 函數(shù)，該函數(shù)的詳細(xì)講解請(qǐng)看我的關(guān)于決策樹那篇文章。但這里在執(zhí)行 do_train 函數(shù)時(shí)，會(huì)調(diào)用 CvForestTree 類中的 find_best_split 函數(shù)，該函數(shù)在后面給此詳細(xì)的介紹tree-train( data, sample_idx_for_tree, this );if ( is_oob_or_vimportance )/如果該變量為true

41、/ sample 表示當(dāng)前樣本， missing 表示缺失的特征屬性CvMat sample, missing;/ form array of OOB samples indices and get these samples sample= cvMat( 1, dims, CV_32FC1, samples_ptr );missing= cvMat( 1, dims, CV_8UC1, missing_ptr );oob_error = 0;/初始化為 0for( i = 0; i data.ptri ) continue;/ predict oob samples/得到當(dāng)前OOB 樣本的預(yù)

42、測(cè)結(jié)果的葉節(jié)點(diǎn)if( !predicted_node ) predicted_node = tree-predict(&sample, &missing, true);if( !data-is_classifier ) /regression 回歸問題/resp 為當(dāng)前樣本的預(yù)測(cè)值， avg_resp 為響應(yīng)值的平均值 double avg_resp, resp = predicted_node-value;/ OOB誤差步驟的第步，第 i個(gè)樣本的預(yù)測(cè)值的累加和 oob_predictions_sum.data.fli += (float)resp;oob_num_of_predictions

43、.data.fli += 1;/第 i 個(gè)樣本被預(yù)測(cè)的次數(shù)/ compute oob error/ OOB誤差步驟的第步，計(jì)算平均預(yù)測(cè)值avg_respoob_predictions_sum.data.fli/oob_num_of_predictions.data.fli;/樣本平均預(yù)測(cè)值與真實(shí)響應(yīng)值之差avg_resp -= true_resp_ptri;/ OOB 誤差步驟的第步oob_error += avg_resp*avg_resp;/式 2 中分子第一項(xiàng)中的 e 的指數(shù)部分resp = (resp - true_resp_ptri)/maximal_response;/式 2 中分

44、子第一項(xiàng)內(nèi)容 ncorrect_responses += exp( -resp*resp );else /classification 分類問題double prdct_resp;/表示預(yù)測(cè)結(jié)果CvPoint max_loc;/表示最多得票值的位置CvMat votes; /表示投票結(jié)果 /votes為oob_sample_votes矩陣白勺第i行，即當(dāng)前樣本的分類 cvGetRow(oob_sample_votes, &votes, i);/OOB誤差步驟的第步，統(tǒng)計(jì) OOB預(yù)測(cè)分類結(jié)果的次數(shù)votes.data.ipredicted_node-class_idx+;/ compute oo

45、b error/ max_loc 表示當(dāng)前樣本預(yù)測(cè)次數(shù)最多的分類的位置cvMinMaxLoc( &votes, 0, 0, 0, &max_loc );/得到當(dāng)前樣本預(yù)測(cè)分類結(jié)果的映射值，OOB 誤差步驟的第步prdct_resp = data-cat_map-data.imax_loc.x;/ OOB誤差步驟的第步，統(tǒng)計(jì)預(yù)測(cè)錯(cuò)誤的數(shù)量oob_error += (fabs(prdct_resp - true_resp_ptri) value true_resp_ptri) = 0;oob_samples_count+; /OOB 樣本計(jì)數(shù)/ 遍歷所有樣本結(jié)束/ OOB 誤差步驟的第步if( o

46、ob_samples_count 0 )oob_error /= (double)oob_samples_count;/ estimate variable importance/評(píng)估特征屬性的重要程度if( var_importance & oob_samples_count 0 )int m; /用于特征屬性的循環(huán)索引/賦值樣本數(shù)據(jù)samples_ptr 給 oob_samples_perm_ptrmemcpy( oob_samples_perm_ptr, samples_ptr, dims*nsamples*sizeof(float);for( m = 0; m dims; m+ )/遍

47、歷所有的特征屬性/該值表示式1 或式 2 中分子的第二項(xiàng)內(nèi)容double ncorrect_responses_permuted = 0;/ randomly permute values of the m-th variable in the oob samples/指向第m 個(gè)特征屬性float* mth_var_ptr = oob_samples_perm_ptr + m;/所有OOB 樣本的第 m 個(gè)特征屬性都要隨機(jī)置換for( i = 0; i data.ptri ) /the sample is not OOB continue;/在全體樣本中，隨機(jī)得到兩個(gè)樣本i1 和 i2i1

48、= (*rng)(nsamples);i2 = (*rng)(nsamples);/置換這兩個(gè)樣本在第m 個(gè)特征屬性的值CV_SWAP( mth_var_ptri1*dims, mth_var_ptri2*dims, temp );/ turn values of (m-1)-th variable, that were permuted/ at the previous iteration, untouched/下面語句的作用是保持第m-1 個(gè)特征屬性(上一次的迭代)不置換，也就是每次只置換一個(gè)特征屬性if( m 1 )oob_samples_perm_ptri*dims+m-1 sampl

49、es_ptri*dims+m-1;/ predict permuted cases and calculate the number of votes for the/ correct ss in the variable-m-permuted oob data /重新賦值置換以后的樣本sample = cvMat( 1, dims, CV_32FC1, oob_samples_perm_ptr );missing = cvMat( 1, dims, CV_8UC1, missing_ptr );for( i = 0; i data.ptri ) /the sample is not OOB

50、continue;/得到當(dāng)前置換后樣本的預(yù)測(cè)值predct_resp = tree-predict(&sample, &missing, true)-value;true_resp = true_resp_ptri;/置換前樣本的響應(yīng)值if( data-is_classifier )/分類問題/ 統(tǒng)計(jì)置換后預(yù)測(cè)正確的樣本數(shù)量，式1 分子的第二項(xiàng)內(nèi)容ncorrect_responses_permuted += cvRound(true_resp predct_resp) = 0;else/ 回歸問題/式 2 分子的第二項(xiàng)中e 的指數(shù)部分true_resp = (true_resp - predc

51、t_resp)/maximal_response;/ 式 2 分子的第二項(xiàng)內(nèi)容ncorrect_responses_permuted += exp( -true_resp*true_resp ); /式 1 或式 2 ，以及式4，因?yàn)楹竺嬉M(jìn)行歸一化，所以無需除法var_importance-data.flm += (float)(ncorrect_responses- ncorrect_responses_permuted);ntrees+;/迭代次數(shù)加1 ，即決策樹的數(shù)量加 1/如果滿足OOB 誤差的精度要求，則提前退出迭代，即結(jié)束while 循環(huán)if( term_crit.type !=

52、 CV_TERMCRIT_ITER & oob_error max_oob_err ) break; /while 循環(huán)結(jié)束/歸一化var_importance ，即歸一化各個(gè)特征屬性的重要性程度if( var_importance )for ( int vi = 0; vi cols; vi+ )var_importance-data.flvi = ( var_importance-data.flvi 0 ) ? var_importance-data.flvi : 0;cvNormalize( var_importance, var_importance, 1., 0, CV_L1 );/

53、清空一些變量cvFree( &oob_samples_perm_ptr );cvFree( &samples_ptr );cvFree( &missing_ptr );cvFree( &true_resp_ptr );cvReleaseMat( &sample_idx_mask_for_tree );cvReleaseMat( &sample_idx_for_tree );cvReleaseMat( &oob_sample_votes );cvReleaseMat( &oob_responses );return true;隨機(jī)森林算法中，在每棵決策樹構(gòu)建過程中，最佳分叉屬性不是從全體特征屬性

54、中得到的，而是從隨機(jī)選取的一部分特征屬性中得到的，因此這部分程序不能應(yīng)用通用的決策樹程序，而是需要改寫這部分內(nèi)容，以下就是專用于隨機(jī)森林算法中最佳分叉屬性選取的函數(shù)：cpp view plain copy 在 CODE 上查看代碼片派生到我的代碼片CvDTreeSplit* CvForestTree:find_best_split( CvDTreeNode* node )CvMat* active_var_mask = 0;/表示隨機(jī)特征屬性的掩碼if( forest )/已構(gòu)建了隨機(jī)森林int var_count;/全部特征屬性的數(shù)量/得到隨機(jī)數(shù)的分布類型，是均勻分布( UNIFORM )

55、還是高斯正態(tài)分布( NORMAL )CvRNG* rng = forest-get_rng();active_var_mask = forest-get_active_var_mask();/得到隨機(jī)特征屬性的掩碼var_count = active_var_mask-cols; /得到全部特征屬性的數(shù)量CV_Assert( var_count = data-var_count );/ 確保 var_count 的正確/遍歷所有的特征屬性，隨機(jī)得到nactive_vars 個(gè)特征屬性，在active_var_mask 向量中，前 nactive_vars 項(xiàng)為 1 ，其余為0，下面的語句通過隨

56、機(jī)調(diào)整向量元素的位置，實(shí)現(xiàn)了打亂那些值為 1 的元素的位置，從而達(dá)到了隨機(jī)得到 nactive_vars 個(gè)特征屬性的目的for( int vi = 0; vi data.ptri1, active_var_mask-data.ptri2, temp );/實(shí)例化ForestTreeBestSplitFinder 類cv:ForestTreeBestSplitFinder finder( this, node );/并行處理，調(diào)用ForestTreeBestSplitFinder 類的重載 ( )運(yùn)算符，見后面的介紹cv:parallel_reduce(cv:BlockedRange(0, d

57、ata-var_count), finder);CvDTreeSplit *bestSplit = 0;/表示最佳分叉屬性if( finder.bestSplit-quality 0 )/得到了最佳分叉屬性bestSplit = data-new_split_cat( 0, -1.0f );memcpy( bestSplit, finder.bestSplit, finder.splitSize );return bestSplit;/返回最佳分叉屬性重載 ForestTreeBestSplitFinder 類的 ( )運(yùn)算符：cpp view plain copy 在 CODE 上查看代碼片派生到我的代碼片void ForestTreeBestSplitFinder:operator()(const BlockedRange& range)int vi, vi1 = range.begin(), vi2 = range.end();/作用范圍為全部特征屬性int n = node-sample_count; / 該節(jié)點(diǎn)的樣本數(shù)量CvDTreeTrainData* data = tree-get_data();/得到樣本數(shù)據(jù)Au