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

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

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

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

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

4、6.8%,被抽取到的樣本為 63.2% 。 隨機(jī)森林中的每棵決策樹的 bootstrap 集合是不完全相同的， 因此每棵決策樹的 OOB 集合也是不完全相同的，所以對于訓(xùn)練集合中的某個樣本來說，它可能屬于決策樹 Ti 的 bootstrap 集合，而屬于決策樹 Tj 的 OOB 集合。 因?yàn)樵谏擅靠脹Q策樹之前，都要進(jìn)行 bootstrap 過程，而每次 bootstrap 過程所得到的 bootstrap 集合都會不同，所以保證了每棵決策樹的不相關(guān)以及不相同。 為了進(jìn)一步保證決策樹的多樣性， Breiman 又提出了第二個隨機(jī)性。一般的決策樹是在全部 特征屬性中進(jìn)行計(jì)算， 從而

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

6、基本相同， 預(yù)測樣本作用于所有的決策樹，對于分類問題，利用投票的方式， 最多得票 數(shù)的分類結(jié)果即為預(yù)測樣本的分類，對于回歸問題，所有決策樹結(jié)果的平均值即為預(yù)測值。 再回到前面的訓(xùn)練過程中， 為什么我們要使用 Bagging 方法？這是因?yàn)槭褂?Bagging 方法可 以減小訓(xùn)練過程中的噪聲和偏差， 并且更重要的是， 它還可以評估預(yù)測的誤差和衡量特征屬 性的重要程度。 常用的評估機(jī)器學(xué)習(xí)算法的預(yù)測誤差方法是交叉驗(yàn)證法， 但該方法費(fèi)時。 而 Bagging 方法不 需要交叉驗(yàn)證法，我們可以計(jì)算 OOB 誤差，即利用那些 36.8% 的 OOB 樣本來評估預(yù)測誤 差。已經(jīng)得到證明， OO

7、B 誤差是可以代替 bootstrap 集合誤差的，并且其結(jié)果近似于交叉驗(yàn) 證。 OOB 誤差的另一個特點(diǎn)是它的計(jì)算是在訓(xùn)練的過程中同步得到的，即每得到一棵決策 樹，我們就可以根據(jù)該決策樹來調(diào)整由前面的決策樹得到的 OOB 誤差。對于分類問題，它 的 OOB 誤差計(jì)算的方法和步驟為： ?構(gòu)建生成了決策樹 Tk, k=1,2,…，K ①用 Tk 預(yù)測 Tk 的 OOB 樣本的分類結(jié)果 ②更新所有訓(xùn)練樣本的 OOB 預(yù)測分類結(jié)果的次數(shù)（如樣本 xi 是 T1 的 OOB 樣本，則 它有一個預(yù)測結(jié)果，而它是 T2 的 bootstrap 集合內(nèi)的樣本，則此時它沒有預(yù)測結(jié)果） ③對所有樣

8、本，把每個樣本的預(yù)測次數(shù)最多的分類作為該樣本在 Tk時的預(yù)測結(jié)果 ④統(tǒng)計(jì)所有訓(xùn)練樣本中預(yù)測錯誤的數(shù)量 ⑤該數(shù)量除以 Tk 的 OOB 樣本的數(shù)量作為 Tk 時的 OOB 誤差 對于回歸問題，它的 OOB 誤差計(jì)算的方法和步驟為： ?構(gòu)建生成了決策樹 Tk, k=1,2,…，K ①用 Tk 預(yù)測 Tk 的 OOB 樣本的回歸值 ②累加所有訓(xùn)練樣本中的 OOB 樣本的預(yù)測值 ③對所有樣本，計(jì)算 Tk時的每個樣本的平均預(yù)測值，即預(yù)測累加值除以被預(yù)測的次數(shù) ④累加每個訓(xùn)練樣本平均預(yù)測值與真實(shí)響應(yīng)值之差的平方 ⑤該平方累加和除以 Tk 的 OOB 樣本的數(shù)量作為 Tk 時的 OOB 誤

9、差 很顯然，隨著決策樹的增多， OOB誤差會趨于縮小，因此我們可以設(shè)置一個精度 e ,當(dāng)Tk 的OOB誤差小于時，我們可以提前終止迭代過程，即不必再生成 Tk+1及以后的決策樹 了。 即特征屬性 不僅能夠預(yù)測樣本， 而且還能夠得到樣本的哪個特征屬性對預(yù)測起到?jīng)Q定作用， Bagging方法在 的重要性，也是機(jī)器學(xué)習(xí)的一項(xiàng)主要任務(wù)，并且在實(shí)際應(yīng)用中越來越重要。 隨機(jī)森林中的另一個作用就是可以計(jì)算特征屬性的重要程度。 目前有兩種主要的方法用于計(jì) 算特征屬性的重要性： Gini法和置換法。Gini法依據(jù)的是不純度減小的原則，在這里我們 重點(diǎn)介紹置換法。 置換法依據(jù)的原則是；樣本的某

10、個特征屬性越重要.那么改變該特征屬性的值，則該樣本 的預(yù)測值就越容易出現(xiàn)錯誤,置換法是通過置檢兩個樣本的相同特征屬性的值來改變特征 屬性的』它的具體方法是：在決策樹7X的。。日集合中隨機(jī)選擇兩個樣本K產(chǎn)(現(xiàn)1周2 …西加和X尸的1.刃2…的每個樣本具有戶個特征屬性』這兩個樣本的響應(yīng)值A(chǔ)別為并 和歲,而用丁的這兩個樣本的預(yù)硼值分別為門 ,，設(shè)逮。0日集含中一共有m*個樣 本.我們衡量第價特征屬性的重要性」則置換翼茶々中的町萍與q.置頓后的樣本 為口q=M,1「為…題灑算妒邂1…題中…葺G?依據(jù)該方法J為006集合共置 換m3文,則最終*換的結(jié)果為x荷,1,…潑血中…jX/p)o用T對國的預(yù)惻

11、值為 八小 對于分類問題，如果北取工修，說明改變第q個特征屬性的值，并不改變最簿的響 應(yīng)值，也就是第仆特征屬性對“來說不是很重要，而如果以秒為小說明改變第什特征 屬性的值餞改變最繆的響應(yīng)值，因此謖特征屬性重要,下式則為這種重要程度的量化能 式： 工皿/儀=5產(chǎn))二工證加"止=渣) 用上 (1) 式中,分子中的第一項(xiàng)表示對00日中」預(yù)測正確的樣本的數(shù)量,而分子中的第二項(xiàng)表示置 摭后預(yù)測正確的樣本數(shù)量-而對于回歸問題 > 它的重要程度的量化花式為： 式中， A = rnax| y( | iGN * 如果第（TT■特征屬性不屬于不，V!q^= 0,對隨機(jī)森林中的所有決策樹都應(yīng)用

12、式1或式2 計(jì)算第H■特征雇性的重要性』則取平均得到整個隨機(jī)森林對第M特征屬性的重要程度的 量化毯式為 3哨 (4) 最后,我們對所有的特征厘性的重要程度進(jìn)行歸一化處理，則第M■特征屬性的歸一化 為： 至從隨機(jī)森林提出以來，該篁法已成為一種流行的被廣泛使用的非參數(shù)回歸應(yīng)用的工具, 日向E日口對該苴法總結(jié)了以下一些特點(diǎn)： ?在目前所有的機(jī)藉學(xué)習(xí)笠法中?具有無法比擬的預(yù)測楮度 ?能妙有效的處理大型數(shù)患庫 ?不需要任何的特征雇性的刪瀛-就能解處理具有上千種特征屬性的樣本 ?能雄給出特征屬性的重要程度 ?在隨機(jī)森林的構(gòu)建過程中 ＞就可以得到匿化誤差的內(nèi)部無偏估計(jì) ?即使包含一定比例

13、的缺失特征屬性的樣本j也能夠得到睢確的預(yù)棚 ?在樣本種群不均衡的數(shù)據(jù)庫中，也能蜉平衡這種情況 ?構(gòu)建好的隨機(jī)森林可以破保存下來.用于以后的其他數(shù)據(jù)的使用 二、源碼分析 我們先給出表示隨機(jī)森林參數(shù)的類的一個構(gòu)造函數(shù): bool [cpp] view plain copy 在CODE上查看代碼片派生到我的代碼片 CvRTParams::CvRTParams( int _max_depth, int _min_sample_count, float _regression_accuracy, bool _use_surrogates, int _max_categories, const

14、 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 ), calc_var_importance(_calc_var_

15、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)建回歸樹的一個條件， 回歸樹的響應(yīng)值的精度如果達(dá)到了該

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

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

18、es_in_the_forest 為 終 止 條 件 ； 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_va

19、rs(0) term_crit = cvTermCriteria( CV_TERMCRIT_ITER+CV_TERMCRIT_EPS, 50, 0.1 ); } 下面為隨機(jī)森林模型的類 CvRTrees,它的構(gòu)造函數(shù)為： [cpp] view plain copy 在 CODE 上查看代碼片派生到我的代碼片 CvRTrees::CvRTrees() { nclasses oob_error ntrees trees data active_var_mask var_importance = 0; = 0; = 0; = NULL; = NULL; = NU

20、LL; = NULL; //表示分類類別數(shù)量 //表示 OOB 誤差 //表示決策樹的數(shù)量 //表示決策樹 ; // 表示用于構(gòu)建決策樹的樣本數(shù)據(jù) //表示隨機(jī)特征屬性的掩碼 //表示特征屬性的重要性 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,

21、int _tflag, const CvMat* _responses, const CvMat* _var_idx, const CvMat* _sample_idx, const CvMat* _var_type, const CvMat* _missing_mask, CvRTParams params ) //_train_data 訓(xùn)練樣本數(shù)據(jù)，必須為 32FC1 類型的矩陣形式 //_tflag 訓(xùn)練數(shù)據(jù)的特征屬性類型，如果為 CV_ROW_SAMPLE ，表示樣本是以行的形式儲 存的，即 _train_data 矩陣的每一行為一個樣本；如果為 CV_COL_SAMPL

22、E ，表示樣本是以 列的形式儲存的 //_responses 樣本的結(jié)果， 即響應(yīng)值， 該值必須是 32SC1 或 32FC1 類型的一維矩陣 （即矢量） 的形式，并且元素的數(shù)量必須與訓(xùn)練樣本數(shù)據(jù) _train_data 的樣本數(shù)一致 //_var_idx 標(biāo)識感興趣的特征屬性，即真正用于訓(xùn)練的那些特征屬性，該值的形式與 _sample_idx 變量相似 //_sample_idx 標(biāo)識感興趣的樣本， 即真正用于訓(xùn)練的樣本， 該值必須是一維矩陣的形式， 即 矢量的形式，并且類型必須是 8UC1、8SU1或者32SC1。如果為8UC1或8SU1 ,則該值的 含義是用掩碼的形式表示

23、對應(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 特征屬性的形式， 是類的形式還是數(shù)值的形式， 用掩碼的形式表現(xiàn)對應(yīng)特征屬性 的形式， 0 表示為數(shù)值的形式， 1 表示為類的形式。該值必須是一維矩陣，并且元素的數(shù)量 必須是真正用于訓(xùn)練的那些特征屬性的數(shù)量加 1，多余的一個元素表示的是響應(yīng)值的形式，

24、 即是分類樹還是回歸樹 //_missing_mask 缺失的特征屬性，用掩碼的形式表現(xiàn)對應(yīng)的特征屬性， 0 表示沒有缺失，而 且必須與 _train_data 的矩陣尺寸大小一致 //params 為構(gòu)建隨機(jī)森林的參數(shù) clear(); // 清空一些全局變量 //得到用于構(gòu)建決策樹的參數(shù) CvDTreeParams tree_params( params.max_depth, params.min_sample_count, params.regression_accuracy, params.use_surrogates, params.max_categories, par

25、ams.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, _missing_mask, tree_params, true); int var_count = data->var_count; // 表示特征屬性的數(shù)量 //隨機(jī)特征屬性的數(shù)量

26、nactive_vars 一定不能大于全部特征屬性的數(shù)量 var_count if( 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 = (int)sqrt((double)var_count); else if( params.nactive_vars < 0 ) //如

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

28、rtance ) { var_importance = cvCreateMat( 1, var_count, CV_32FC1 ); cvZero(var_importance); //初始化為 0 } { // initialize active variables mask CvMat submask1, submask2; //確保全部特征屬性的數(shù)量不能小于 1 ，隨機(jī)特征屬性的數(shù)量不能小于 0，并且前 者不能小于后者 CV_Assert( (active_var_mask->cols >= 1) && (params.nactive_vars > 0) && (par

29、ams.nactive_vars <= active_var_mask->cols) ); //對于 active_var_mask 矩陣，前 nactive_vars 列的所有元素賦值為 1 ，其余的賦值 為0 cvGetCols( active_var_mask, &submask1, 0, params.nactive_vars ); cvSet( &submask1, cvScalar(1) ); if( params.nactive_vars < active_var_mask->cols ) { cvGetCols( active_var_mask, &submask

30、2, params.nactive_vars, var_count ); cvZero( &submask2 ); } //調(diào)用 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ī)樣本的掩碼，抽取到的樣本

31、掩碼為 0xFF ，否則為 0 CvMat* sample_idx_mask_for_tree = 0; //表示用于構(gòu)建單棵決策樹的隨機(jī)樣本，該矩陣存儲的是這些樣本在全部樣本中的索引 值 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ù)量 fl

32、oat maximal_response = 0; //表示最大的響應(yīng)值，即式 3 中的參數(shù) A //表示 OOB 樣本的響應(yīng)值的投票結(jié)果，用于分類問題 CvMat* oob_sample_votes = 0; CvMat* oob_responses = 0; //OOB 樣本的響應(yīng)值，用于回歸問題 = 0; = 0; = 0; OOB //表示樣本矩陣的首地址指針 //表示缺失特征屬性矩陣的首地址指針 //表示樣本響應(yīng)值矩陣的首地址指針 誤差精度或需要計(jì)算特征屬性重要程度 float* oob_samples_perm_ptr= 0; //OOB 樣本的置換指針

33、float* samples_ptr uchar* missing_ptr float* true_resp_ptr //該標(biāo)識變量表示應(yīng)用 bool is_oob_or_vimportance = (max_oob_err > 0 && term_crit.type != CV_TERMCRIT_ITER) || var_importance; // oob_predictions_sum[i] = sum of predicted values for the i-th sample // oob_num_of_predictions[i] = number of summands

34、 // (number of predictions for the i-th sample) // initialize these variable to avoid warning C4701 // oob_predictions_sum 表示某個訓(xùn)練樣本在所有決策樹 OOB 集合中的預(yù)測值累加和 CvMat oob_predictions_sum = cvMat( 1, 1, CV_32FC1 ); // oob_num_of_predictions 表示某個訓(xùn)練樣本在所有決策樹 OOB 集合中的被預(yù)測數(shù)量 CvMat oob_num_of_predictions = cv

35、Mat( 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_votes變量，矩陣大小為樣本總數(shù)x分類類別數(shù) oob_sample_votes = cvCreateMat( nsamples, nclasses, CV_32S

36、C1 ); cvZero(oob_sample_votes); // 初始化為 0 } else // 回歸問題 { // oob_responses[0,i] = oob_predictions_sum[i] // = sum of predicted values for the i-th sample // oob_responses[1,i] = oob_num_of_predictions[i] // = number of summands (number of predictions for the i-th sample) //創(chuàng)建oob_responses變

37、量，矩陣大小為 2 x樣本總數(shù)，其中oob_responses[0,i]= oob_predictions_sum[i] ， oob_responses[1,i] = oob_num_of_predictions[i] oob_responses = cvCreateMat( 2, nsamples, CV_32FC1 ); cvZero(oob_responses); //初始化為 0 // oob_predictions_sum 指向矩陣 oob_responses 的第 0 行 cvGetRow( oob_responses, &oob_predictions_sum, 0 )

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

39、ms ); = (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, tru

40、e_resp_ptr); //得到響應(yīng)值中的最大值 maxval 和最小值 minval ， minval 有可能是負(fù)數(shù) cvMinMaxLoc( &responses, &minval, &maxval ); //式 3 maximal_response = (float)MAX( MAX( fabs(minval), fabs(maxval) ), 0 ); } 〃為trees分配內(nèi)存空間 trees = (CvForestTree**)cvAlloc( sizeof(trees[0])*max_ntrees ); memset( trees, 0, sizeof(tree

41、s[0])*max_ntrees ); 〃決策樹 trees 初始化為 0 //創(chuàng)建下面兩個變量 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ù)時，結(jié)束迭代 { // oob_samples_count 用于

42、OOB 樣本計(jì)數(shù) int i, oob_samples_count = 0; //分類問題，該值表示式 1 中分子的第一項(xiàng)；回歸問題，為式 2 中的分子第一項(xiàng) double ncorrect_responses = 0; // used for estimation of variable importance CvForestTree* tree = 0; //實(shí)例化 CvForestTree 類，表示當(dāng)前要構(gòu)建的決策樹 cvZero( sample_idx_mask_for_tree ); //初始化 0 //遍歷所有樣本，得到用于構(gòu)建決策樹的樣本 for(i = 0; i

43、< nsamples; i++ ) //form sample for creation one tree { //在全體樣本中，有放回的隨機(jī)抽取一個樣本，一共抽取 nsamples次 //idx 為一個不大于 nsamples 的隨機(jī)整數(shù)， 該語句的含義是隨機(jī)抽取某個樣本， idx 表示該樣本的索引值 int idx = (*rng)(nsamples); sample_idx_for_tree->data.i[i] = idx; //賦值樣本的索引值 sample_idx_mask_for_tree->data.ptr[idx] = 0xFF; //該樣本的掩碼 } tr

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

45、; if ( is_oob_or_vimportance ) //如果該變量為 true { // 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; //初始化為 0 for

46、( i = 0; i < nsamples; i++, //遍歷所有樣本 sample.data.fl += dims, missing.data.ptr += dims ) CvDTreeNode* predicted_node = 0; //表示預(yù)測結(jié)果的葉節(jié)點(diǎn) // check if the sample is OOB //判斷當(dāng)前的樣本是否用于構(gòu)建當(dāng)前決策樹，如果是則遍歷下一個樣本 if( sample_idx_mask_for_tree->data.ptr[i] ) continue; // predict oob samples //得到當(dāng)前 OOB 樣本的預(yù)測結(jié)果

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

48、_num_of_predictions.data.fl[i] += 1; //第 i 個樣本被預(yù)測的次數(shù) // compute oob error // OOB誤差步驟的第③步，計(jì)算平均預(yù)測值 avg_resp oob_predictions_sum.data.fl[i]/oob_num_of_predictions.data.fl[i]; //樣本平均預(yù)測值與真實(shí)響應(yīng)值之差 avg_resp -= true_resp_ptr[i]; // OOB 誤差步驟的第④步 oob_error += avg_resp*avg_resp; //式 2 中分子第一項(xiàng)中的 e 的指數(shù)部分

49、 resp = (resp - true_resp_ptr[i])/maximal_response; //式 2 中分子第一項(xiàng)內(nèi)容 ncorrect_responses += exp( -resp*resp ); } else //classification 分類問題 { double prdct_resp; //表示預(yù)測結(jié)果 CvPoint max_loc; //表示最多得票值的位置 CvMat votes; //表示投票結(jié)果 //votes為oob_sample_votes矩陣白勺第i行，即當(dāng)前樣本的分類 cvGetRow(oob_sample_votes, &votes

50、, i); //OOB誤差步驟的第②步，統(tǒng)計(jì) OOB預(yù)測分類結(jié)果的次數(shù) votes.data.i[predicted_node->class_idx]++; // compute oob error // max_loc 表示當(dāng)前樣本預(yù)測次數(shù)最多的分類的位置 cvMinMaxLoc( &votes, 0, 0, 0, &max_loc ); //得到當(dāng)前樣本預(yù)測分類結(jié)果的映射值， OOB 誤差步驟的第③步 prdct_resp = data->cat_map->data.i[max_loc.x]; // OOB誤差步驟的第④步，統(tǒng)計(jì)預(yù)測錯誤的數(shù)量 oob_error += (

51、fabs(prdct_resp - true_resp_ptr[i]) < FLT_EPSILON) ? 0 : 1; //統(tǒng)計(jì)當(dāng)前決策樹的 OOB 樣本預(yù)測正確的樣本數(shù)，式 1 中分子的第 一項(xiàng)內(nèi)容 ncorrect_responses += cvRound(predicted_node->value true_resp_ptr[i]) == 0; } oob_samples_count++; //OOB 樣本計(jì)數(shù) } // 遍歷所有樣本結(jié)束 // OOB 誤差步驟的第⑤步 if( oob_samples_count > 0 ) oob_error /= (double)o

52、ob_samples_count; // estimate variable importance //評估特征屬性的重要程度 if( var_importance && oob_samples_count > 0 ) { int m; //用于特征屬性的循環(huán)索引 //賦值樣本數(shù)據(jù) samples_ptr 給 oob_samples_perm_ptr memcpy( oob_samples_perm_ptr, samples_ptr, dims*nsamples*sizeof(float)); for( m = 0; m < dims; m++ ) //遍歷所有的特征屬性 {

53、 //該值表示式 1 或式 2 中分子的第二項(xiàng)內(nèi)容 double ncorrect_responses_permuted = 0; // randomly permute values of the m-th variable in the oob samples //指向第 m 個特征屬性 float* mth_var_ptr = oob_samples_perm_ptr + m; //所有 OOB 樣本的第 m 個特征屬性都要隨機(jī)置換 for( i = 0; i < nsamples; i++ ) //遍歷所有樣本 { int i1, i2; float temp;

54、//當(dāng)前樣本不是 OOB ，則繼續(xù)遍歷下個樣本 if( sample_idx_mask_for_tree->data.ptr[i] ) //the sample is not OOB continue; //在全體樣本中，隨機(jī)得到兩個樣本 i1 和 i2 i1 = (*rng)(nsamples); i2 = (*rng)(nsamples); //置換這兩個樣本在第 m 個特征屬性的值 CV_SWAP( mth_var_ptr[i1*dims], mth_var_ptr[i2*dims], temp ); // turn values of (m-1)-th variable,

55、 that were permuted // at the previous iteration, untouched //下面語句的作用是保持第 m-1 個特征屬性(上一次的迭代)不 置換，也就是每次只置換一個特征屬性 if( m > 1 ) oob_samples_perm_ptr[i*dims+m-1] samples_ptr[i*dims+m-1]; } // predict "permuted" cases and calculate the number of votes for the // correct ss in the variable-m-permute

56、d oob data //重新賦值置換以后的樣本 sample = cvMat( 1, dims, CV_32FC1, oob_samples_perm_ptr ); missing = cvMat( 1, dims, CV_8UC1, missing_ptr ); for( i = 0; i < nsamples; i++, //遍歷所有樣本 sample.data.fl += dims, missing.data.ptr += dims ) { double predct_resp, true_resp; //當(dāng)前樣本不是 OOB ，則繼續(xù)遍歷下個樣本 if( sample

57、_idx_mask_for_tree->data.ptr[i] ) //the sample is not OOB continue; //得到當(dāng)前置換后樣本的預(yù)測值 predct_resp = tree->predict(&sample, &missing, true)->value; true_resp = true_resp_ptr[i]; //置換前樣本的響應(yīng)值 if( data->is_classifier ) //分類問題 // 統(tǒng)計(jì)置換后預(yù)測正確的樣本數(shù)量，式 1 分子的第二項(xiàng)內(nèi)容 ncorrect_responses_permuted += cvRound(true

58、_resp predct_resp) == 0; else // 回歸問題 { //式 2 分子的第二項(xiàng)中 e 的指數(shù)部分 true_resp = (true_resp - predct_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.fl[m] += (float)(ncorrect_responses

59、 - ncorrect_responses_permuted); } ntrees++; //迭代次數(shù)加 1 ，即決策樹的數(shù)量加 1 //如果滿足 OOB 誤差的精度要求，則提前退出迭代，即結(jié)束 while 循環(huán) if( term_crit.type != CV_TERMCRIT_ITER && oob_error < max_oob_err ) break; } //while 循環(huán)結(jié)束 //歸一化 var_importance ，即歸一化各個特征屬性的重要性程度 if( var_importance ) { for ( int vi = 0; vi < var_impor

60、tance->cols; vi++ ) var_importance->data.fl[vi] = ( var_importance->data.fl[vi] > 0 ) ? var_importance->data.fl[vi] : 0; cvNormalize( var_importance, var_importance, 1., 0, CV_L1 ); } //清空一些變量 cvFree( &oob_samples_perm_ptr ); cvFree( &samples_ptr ); cvFree( &missing_ptr ); cvFree( &true_resp

61、_ptr ); cvReleaseMat( &sample_idx_mask_for_tree ); cvReleaseMat( &sample_idx_for_tree ); cvReleaseMat( &oob_sample_votes ); cvReleaseMat( &oob_responses ); return true; } 隨機(jī)森林算法中，在每棵決策樹構(gòu)建過程中，最佳分叉屬性不是從全體特征屬性中得到的， 而是從隨機(jī)選取的一部分特征屬性中得到的，因此這部分程序不能應(yīng)用通用的決策樹程序， 而是需要改寫這部分內(nèi)容，以下就是專用于隨機(jī)森林算法中最佳分叉屬性選取的函數(shù)：

62、 [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 ) 還是高斯正態(tài)分布 ( NORMAL ) CvRNG* rng = forest->get_rng();

63、 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 個特征屬性，在 active_var_mask 向 量中，前 nactive_vars 項(xiàng)為 1 ，其余為 0，下面的語句通過隨機(jī)調(diào)整向量元素的位置，實(shí)現(xiàn) 了打亂那些值為 1 的

64、元素的位置，從而達(dá)到了隨機(jī)得到 nactive_vars 個特征屬性的目的 for( int vi = 0; vi < var_count; vi++ ) { uchar temp; // 隨機(jī)得到兩個不大于 var_count 的值，用于表示隨機(jī)得到的特征屬性 int i1 = cvRandInt(rng) % var_count; int i2 = cvRandInt(rng) % var_count; //交換這兩個特征屬性的位置 CV_SW AP( active_var_mask->data.ptr[i1], active_var_mask->data.ptr[i2],

65、 temp ); } } //實(shí)例化 ForestTreeBestSplitFinder 類 cv::ForestTreeBestSplitFinder finder( this, node ); //并行處理，調(diào)用 ForestTreeBestSplitFinder 類的重載 ( )運(yùn)算符，見后面的介紹 cv::parallel_reduce(cv::BlockedRange(0, data->var_count), finder); CvDTreeSplit *bestSplit = 0; //表示最佳分叉屬性 if( finder.bestSplit->quality >

66、 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