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

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

3、ating） ， 那些不在 bootstrap 集合中的樣本稱之為 OOB（ Out Of Bag ） 。 Bootstrap 過(guò)程為：從全部 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次仍然沒(méi)有被抽到的概率就為 （1 — 1/N）S ,如果S和N都趨于無(wú)窮 大，則（1 — 1/N）S^e—1 = 0.368,即OOB樣本所占全部樣本約為 3

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

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

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

7、B 誤差是可以代替 bootstrap 集合誤差的，并且其結(jié)果近似于交叉驗(yàn) 證。 OOB 誤差的另一個(gè)特點(diǎn)是它的計(jì)算是在訓(xùn)練的過(guò)程中同步得到的，即每得到一棵決策 樹(shù)，我們就可以根據(jù)該決策樹(shù)來(lái)調(diào)整由前面的決策樹(shù)得到的 OOB 誤差。對(duì)于分類問(wèn)題，它 的 OOB 誤差計(jì)算的方法和步驟為： ?構(gòu)建生成了決策樹(shù) 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í)它沒(méi)有預(yù)測(cè)結(jié)果） ③對(duì)所有樣

8、本，把每個(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ì)于回歸問(wèn)題，它的 OOB 誤差計(jì)算的方法和步驟為： ?構(gòu)建生成了決策樹(shù) Tk, k=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 誤

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

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

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

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

13、的缺失特征屬性的樣本j也能夠得到睢確的預(yù)棚 ?在樣本種群不均衡的數(shù)據(jù)庫(kù)中，也能蜉平衡這種情況 ?構(gòu)建好的隨機(jī)森林可以破保存下來(lái).用于以后的其他數(shù)據(jù)的使用 二、源碼分析 我們先給出表示隨機(jī)森林參數(shù)的類的一個(gè)構(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 表示決策樹(shù)的深度，該值的大小嚴(yán)重影響擬合的效果 _min_sample_count 表示決策樹(shù)節(jié)點(diǎn)的最小樣本數(shù)，如果節(jié)點(diǎn)的樣本數(shù)小于該值，則該節(jié)點(diǎn) 不再分叉，一般該值為樣本總數(shù)的 1% _regression_accuracy 表示終止構(gòu)建回歸樹(shù)的一個(gè)條件， 回歸樹(shù)的響應(yīng)值的精度如果達(dá)到了該

16、 值，則無(wú)需再分叉。該值不能小于 0，否則報(bào)錯(cuò) _use_surrogates表示是否使用 替代分叉節(jié)點(diǎn) _max_categories 表示特征屬性為類的形式的最大的類的數(shù)量 _priors 表示決策樹(shù)的特征屬性的先驗(yàn)概率 以上幾個(gè)參數(shù)是用于構(gòu)建決策樹(shù)時(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，則表示該

17、值為樣本的全部特征屬性的平方根 max_num_of_trees_in_the_forest 表示森林中決策樹(shù)的最大數(shù)量，也就是最大迭代次數(shù)，因?yàn)? 每迭代一次就會(huì)得到一棵決策樹(shù)。通常來(lái)說(shuō)， 決策樹(shù)越多，預(yù)測(cè)越準(zhǔn)確，但決策樹(shù)的數(shù)量達(dá) 到一定程度后， 準(zhǔn)確度的增長(zhǎng)會(huì)減小甚至趨于不變， 另一方面， 預(yù)測(cè)時(shí)間是與決策樹(shù)的數(shù)量 呈線性關(guān)系的 以決策樹(shù)達(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ù)的數(shù)量 //表示決策樹(shù) ; // 表示用于構(gòu)建決策樹(shù)的樣本數(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 ，表示樣本是以行的形式儲(chǔ) 存的，即 _train_data 矩陣的每一行為一個(gè)樣本；如果為 CV_COL_SAMPL

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

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

24、 即是分類樹(shù)還是回歸樹(shù) //_missing_mask 缺失的特征屬性，用掩碼的形式表現(xiàn)對(duì)應(yīng)的特征屬性， 0 表示沒(méi)有缺失，而 且必須與 _train_data 的矩陣尺寸大小一致 //params 為構(gòu)建隨機(jī)森林的參數(shù) clear(); // 清空一些全局變量 //得到用于構(gòu)建決策樹(shù)的參數(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ù)的樣本數(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)錯(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è)用于表示特征屬性重要性的變量 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) ); //對(duì)于 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ù)，由決策樹(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)建單棵決策樹(shù)的隨機(jī)樣本的掩碼，抽取到的樣本

31、掩碼為 0xFF ，否則為 0 CvMat* sample_idx_mask_for_tree = 0; //表示用于構(gòu)建單棵決策樹(shù)的隨機(jī)樣本，該矩陣存儲(chǔ)的是這些樣本在全部樣本中的索引 值 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é)果，用于分類問(wèn)題 CvMat* oob_sample_votes = 0; CvMat* oob_responses = 0; //OOB 樣本的響應(yīng)值，用于回歸問(wèn)題 = 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)識(shí)變量表示應(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 表示某個(gè)訓(xùn)練樣本在所有決策樹(shù) OOB 集合中的預(yù)測(cè)值累加和 CvMat oob_predictions_sum = cvMat( 1, 1, CV_32FC1 ); // oob_num_of_predictions 表示某個(gè)訓(xùn)練樣本在所有決策樹(shù) OOB 集合中的被預(yù)測(cè)數(shù)量 CvMat oob_num_of_predictions = cv

35、Mat( 1, 1, CV_32FC1 ); nsamples = data->sample_count; //表示樣本的全體數(shù)量 nclasses = data->get_num_classes(); //表示分類問(wèn)題的樣本分類類別數(shù)量 if ( is_oob_or_vimportance ) //該變量為真 { if( data->is_classifier ) //分類問(wèn)題 { //創(chuàng)建oob_sample_votes變量，矩陣大小為樣本總數(shù)x分類類別數(shù) oob_sample_votes = cvCreateMat( nsamples, nclasses, CV_32S

36、C1 ); cvZero(oob_sample_votes); // 初始化為 0 } else // 回歸問(wèn)題 { // 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 個(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*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 ); 〃決策樹(shù) trees 初始化為 0 //創(chuàng)建下面兩個(gè)變量 sample_idx_mask_for_tree = cvCreateMat( 1, nsamples, CV_8UC1 ); sample_idx_for_tree = cvCreateMat( 1, nsamples, CV_32SC1 ); ntrees = 0; //決策樹(shù)的索引值，先初始化為 0 //進(jìn)入構(gòu)建隨機(jī)森林的循環(huán)體中 while( ntrees < max_ntrees ) // 滿足最大迭代次數(shù)時(shí)，結(jié)束迭代 { // oob_samples_count 用于

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

43、< nsamples; i++ ) //form sample for creation one tree { //在全體樣本中，有放回的隨機(jī)抽取一個(gè)樣本，一共抽取 nsamples次 //idx 為一個(gè)不大于 nsamples 的隨機(jī)整數(shù)， 該語(yǔ)句的含義是隨機(jī)抽取某個(gè)樣本， 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]; //決策樹(shù)賦值 //訓(xùn)練單棵決策樹(shù)， 它首先調(diào)用 CvForestTree 類中的 train 虛函數(shù)， 而最終調(diào)用的是 CvDTree 類的 do_train 函數(shù)，該函數(shù)的詳細(xì)講解請(qǐng)看我的關(guān)于決策樹(shù)那篇文章。但這里在執(zhí) 行 do_train 函數(shù)時(shí)，會(huì)調(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ù)測(cè)結(jié)果的葉節(jié)點(diǎn) // check if the sample is OOB //判斷當(dāng)前的樣本是否用于構(gòu)建當(dāng)前決策樹(shù)，如果是則遍歷下一個(gè)樣本 if( sample_idx_mask_for_tree->data.ptr[i] ) continue; // predict oob samples //得到當(dāng)前 OOB 樣本的預(yù)測(cè)結(jié)果

47、的葉節(jié)點(diǎn) if( !predicted_node ) predicted_node = tree->predict(&sample, &missing, true); if( !data->is_classifier ) //regression 回歸問(wèn)題 { //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.fl[i] += (float)resp; oob

48、_num_of_predictions.data.fl[i] += 1; //第 i 個(gè)樣本被預(yù)測(cè)的次數(shù) // compute oob error // OOB誤差步驟的第③步，計(jì)算平均預(yù)測(cè)值 avg_resp oob_predictions_sum.data.fl[i]/oob_num_of_predictions.data.fl[i]; //樣本平均預(yù)測(cè)值與真實(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 分類問(wèn)題 { double prdct_resp; //表示預(yù)測(cè)結(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ù)測(cè)分類結(jié)果的次數(shù) votes.data.i[predicted_node->class_idx]++; // compute oob 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.i[max_loc.x]; // OOB誤差步驟的第④步，統(tǒng)計(jì)預(yù)測(cè)錯(cuò)誤的數(shù)量 oob_error += (

51、fabs(prdct_resp - true_resp_ptr[i]) < FLT_EPSILON) ? 0 : 1; //統(tǒng)計(jì)當(dāng)前決策樹(shù)的 OOB 樣本預(yù)測(cè)正確的樣本數(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 //評(píng)估特征屬性的重要程度 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 個(gè)特征屬性 float* mth_var_ptr = oob_samples_perm_ptr + m; //所有 OOB 樣本的第 m 個(gè)特征屬性都要隨機(jī)置換 for( i = 0; i < nsamples; i++ ) //遍歷所有樣本 { int i1, i2; float temp;

54、//當(dāng)前樣本不是 OOB ，則繼續(xù)遍歷下個(gè)樣本 if( sample_idx_mask_for_tree->data.ptr[i] ) //the sample is not OOB continue; //在全體樣本中，隨機(jī)得到兩個(gè)樣本 i1 和 i2 i1 = (*rng)(nsamples); i2 = (*rng)(nsamples); //置換這兩個(gè)樣本在第 m 個(gè)特征屬性的值 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 //下面語(yǔ)句的作用是保持第 m-1 個(gè)特征屬性(上一次的迭代)不 置換，也就是每次只置換一個(gè)特征屬性 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ù)遍歷下個(gè)樣本 if( sample

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

58、_resp predct_resp) == 0; else // 回歸問(wèn)題 { //式 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)行歸一化，所以無(wú)需除法 var_importance->data.fl[m] += (float)(ncorrect_responses

59、 - ncorrect_responses_permuted); } ntrees++; //迭代次數(shù)加 1 ，即決策樹(shù)的數(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 ，即歸一化各個(gè)特征屬性的重要性程度 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ī)森林算法中，在每棵決策樹(shù)構(gòu)建過(guò)程中，最佳分叉屬性不是從全體特征屬性中得到的， 而是從隨機(jī)選取的一部分特征屬性中得到的，因此這部分程序不能應(yīng)用通用的決策樹(shù)程序， 而是需要改寫(xiě)這部分內(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 個(gè)特征屬性，在 active_var_mask 向 量中，前 nactive_vars 項(xiàng)為 1 ，其余為 0，下面的語(yǔ)句通過(guò)隨機(jī)調(diào)整向量元素的位置，實(shí)現(xiàn) 了打亂那些值為 1 的

64、元素的位置，從而達(dá)到了隨機(jī)得到 nactive_vars 個(gè)特征屬性的目的 for( int vi = 0; vi < var_count; vi++ ) { uchar temp; // 隨機(jī)得到兩個(gè)不大于 var_count 的值，用于表示隨機(jī)得到的特征屬性 int i1 = cvRandInt(rng) % var_count; int i2 = cvRandInt(rng) % var_count; //交換這兩個(gè)特征屬性的位置 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)算符，見(jià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