随机森林的训练过程

    随机森林顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。

     在建立每一棵决策树的过程中，有两点需要注意 – 采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M 个feature中，选择m个(m << M)。推荐m的值为M的平方根。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 – 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。随机森林的核心是随机选取样本特征和随机选取样本,每次在选取的训练集上训练决策树。

       随机森林由决策树组成，决策树实际上是将空间用超平面进行划分的一种方法，每次分割的时候，都将当前的空间一分为二，比如说下面的决策树（其属性的值都是连续的实数）：

随机深林的优点：比较适合做多分类问题；训练和预测速度快；对训练数据的容错能力，是一种有效地估计缺失数据的一种方法，当数据集中有大比例的数据缺失时仍然可以保持精度不变；能够有效地处理大的数据集；可以处理没有删减的成千上万的变量；能够在分类的过程中可以生成一个泛化误差的内部无偏估计；能够检测到特征之间的相互影响以及重要性程度；不过出现过度拟合；实现简单容易并行化。

下面是随机森林的构造过程：

1. 假如有N个样本，则有放回的随机选择N个样本(每次随机选择一个样本，然后返回继续选择)。这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。

2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。

3. 决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。

4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了。

从上面的步骤可以看出，随机森林的随机性体现在每颗数的训练样本是随机的，树中每个节点的分类属性也是随机选择的。有了这2个随机的保证，随机森林就不会产生过拟合的现象了。

随机森林有2个参数需要人为控制，一个是森林中树的数量，一般建议取很大。另一个是m的大小，推荐m的值为M的均方根。

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* _missing_mask, CvRTParams params )

{

   。。。。

  // Create mask of active variables at the tree nodes

   active_var_mask = cvCreateMat( 1, var_count, CV_8UC1 );

   if( params.calc_var_importance )

   {

       var_importance  = cvCreateMat( 1, var_count, CV_32FC1 );

       cvZero(var_importance);

   }

{ // initialize active variables mask

//active_var_mask保存是选取的哪些特征，选中的特征对应1，未选中的对应0

//active_var_mask初始化为前面的m个特征

//即将active_var_mask前m个值置为1，后面的值置为0

       CvMat submask1, submask2;

       CV_Assert( (active_var_mask->cols >= 1) && (params.nactive_vars > 0) && (params.nactive_vars <= active_var_mask->cols) );

       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, &submask2, params.nactive_vars, var_count );

           cvZero( &submask2 );

       }

   }

   return grow_forest( params.term_crit );

}

随机森林中决策树增长的终止条件：

1.训练得到的决策树的数目达到森林里树的最大数目。最大数目由term_crit.max_iter指定。（term_crit.type == CV_TERMCRIT_ITER）

2. OOB错误小于term_crit.epsilon时，树停止增长。

（term_crit.type ！= CV_TERMCRIT_ITER）

grow_forest函数的流程：

1.  随机生成创建决策树的训练样本标识，决定哪些样本参加决策树的训练

2.  选择的子样本进行训练，生成一颗决策树

3.  判断决策树的终止类型，如果决策树的类型不是数目限制，则计算OOB错误，并判断该错误是否小于指定的精度，小于则退出，不小于则继续

4.  将已有决策树的棵树加1，并判断其数目是否达到随机森林的最大数目，小于则返回1继续，不小于则退出。

bool CvRTrees::grow_forest( const CvTermCriteria term_crit )

{

。。。。。。

const int max_ntrees = term_crit.max_iter;//最多树的的个数

   trees = (CvForestTree**)cvAlloc( sizeof(trees[0])*max_ntrees );

   memset( trees, 0, sizeof(trees[0])*max_ntrees );

   sample_idx_mask_for_tree = cvCreateMat( 1, nsamples, CV_8UC1 );

   sample_idx_for_tree      = cvCreateMat( 1, nsamples, CV_32SC1 );

   ntrees = 0;

   while( ntrees < max_ntrees )

   {

       int i, oob_samples_count = 0;

       double ncorrect_responses = 0; // used for estimation of variable importance

       CvForestTree* tree = 0;

       cvZero( sample_idx_mask_for_tree );

       for(i = 0; i < nsamples; i++ ) //form sample for creation one tree

       {

//随机生成创建决策树的训练样本标识，决定哪些样本参加决策树的训练

           int idx = (*rng)(nsamples);

           sample_idx_for_tree->data.i[i] = idx;//创建决策树的训练样本标识

           sample_idx_mask_for_tree->data.ptr[idx] = 0xFF;

       }

       //trees是CvRTrees的成员变量，指向随机森林的所有树

       trees[ntrees] = new CvForestTree();      

tree = trees[ntrees];

       tree->train( data, sample_idx_for_tree, this );//训练随机森林中的一棵树

       if ( is_oob_or_vimportance )

       {

// 计算OOB错误率

           。。。。。。

       }

       ntrees++;

       if( term_crit.type != CV_TERMCRIT_ITER && oob_error < max_oob_err )

           break;

   }

   if( var_importance )

   {

       for ( int vi = 0; vi < var_importance->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 );

   }

   。。。//

   return true;

}

bool CvForestTree::train( CvDTreeTrainData* _data,

                         const CvMat* _subsample_idx,

                         CvRTrees* _forest )

{

   clear();

   forest = _forest;

   data = _data;

   data->shared = true;

   return do_train(_subsample_idx);

}

grow_forest函数不断调用上面的train函数,随机森林中每棵树都是CvForestTree，这个类继承于CvDTree。CvForestTree重载了train函数，find_best_split函数，因此会调用了CvDTree类中的do_train函数后，do_train函数依旧调用CvDTree类中的try_split_node函数，try_split_node函数就会调用CvForestTree的find_best_split函数。下面介绍CvForestTree的find_best_split函数。

CvDTreeSplit* CvForestTree::find_best_split( CvDTreeNode* node )

{

   CvMat* active_var_mask = 0;

   if( forest )

   {

       int var_count;

       CvRNG* rng = forest->get_rng();

       active_var_mask = forest->get_active_var_mask();

       var_count = active_var_mask->cols;

       CV_Assert( var_count == data->var_count );

       //随机交换active_var_mask中不同位置的值，即可达到随机选择m个特征的目的

       for( int vi = 0; vi < var_count; vi++ )

       {

           uchar temp;

           int i1 = cvRandInt(rng) % var_count;

           int i2 = cvRandInt(rng) % var_count;

           CV_SWAP( active_var_mask->data.ptr[i1],

               active_var_mask->data.ptr[i2], temp );

       }

   }

   cv::ForestTreeBestSplitFinder finder( this, node );

   cv::parallel_reduce(cv::BlockedRange(0, data->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;

}

和决策树的find_best_split函数不同的是上面的标黄部分，该部分实现了随机选择样本特征的作用。即只有随机选中的那些才参与后面的最优特征分裂的选择中。（active_var_mask矩阵代表选取的那些特征，选中的特征对应1，未选中的对应0）

【注】active_var_mask在最初训练函数中（CvRTrees::train）已经初始化。该矩阵初始化为：前m个值置为1，后面的值置为0。（m是指定的特征个数，一般为总特征个数的平方根）。

find_best_split函数通过下面这句命令，实现此过程。

cv::parallel_reduce(cv::BlockedRange(0, data->var_count), finder);

实际上，parallel_reduce是调用body函数，其中重载了操作符（）。即实际上是执行下面的函数。

void ForestTreeBestSplitFinder::operator()(const BlockedRange& range)

{

。。。。。。

   CvForestTree* ftree = (CvForestTree*)tree;

   const CvMat* active_var_mask = ftree->forest->get_active_var_mask();

   for( vi = vi1; vi < vi2; vi++ )

   {

       CvDTreeSplit *res;

       int ci = data->var_type->data.i[vi];

       if( node->num_valid[vi] <= 1

           || (active_var_mask && !active_var_mask->data.ptr[vi]))

           continue;

       if( data->is_classifier )

       {

           if( ci >= 0 )

               res = ftree->find_split_cat_class( node, vi, bestSplit->quality, split, (uchar*)inn_buf );

           else

               res = ftree->find_split_ord_class( node, vi, bestSplit->quality, split, (uchar*)inn_buf );

       }

          。。。。。。

       if( res && bestSplit->quality < split->quality )

               memcpy( (CvDTreeSplit*)bestSplit, (CvDTreeSplit*)split, splitSize );

   }

}

该操作符重载函数和决策树中的函数的区别是标黄的部分，该部分判断当前的特征是否在active_var_mask中为0,如果为0,代表不选用该特征，则循环继续。也就是当前特征不参与最优分裂的选择。

find_split_cat_class函数并没有重载，依旧使用决策树中的该函数。