随机森林

一、随机森林的定义

     作为新兴起的、高度灵活的一种机器学习算法,随机森林(Random Forest,简称RF)拥有广泛的应用前景,从市场营销到医疗保健保险,既可以用来做市场营销模拟的建模,统计客户来源,保留和流失,也可用来预测疾病的风险和病患者的易感性。如果接触过决策树(Decision Tree)的话,那么会很容易理解什么是随机森林。随机森林就是通过集成学习的思想将多棵树集成的一种算法,它的基本单元是决策树,而它的本质属于机器学习的一大分支——集成学习(Ensemble Learning)方法。随机森林的名称中有两个关键词,一个是“随机”,一个就是“森林”。“森林”我们很好理解,一棵叫做树,那么成百上千棵就可以叫做森林了,这样的比喻还是很贴切的,其实这也是随机森林的主要思想--集成思想的体现。“随机”的含义我们会在下边部分讲到。其实从直观角度来解释,每棵决策树都是一个分类器(假设现在针对的是分类问题),那么对于一个输入样本,N棵树会有N个分类结果。而随机森林集成了所有的分类投票结果,将投票次数最多的类别指定为最终的输出,这就是一种最简单的 Bagging 思想。

二、随机森岭的基础要点

  随机森林看起来是很好理解,但是要完全搞明白它的工作原理,需要很多机器学习方面相关的基础知识。在本文中,我们简单谈一下,而不逐一进行赘述,如果有同学不太了解相关的知识,可以参阅其他博友的一些相关博文或者文献。

1)信息、熵以及信息增益的概念

  这三个基本概念是决策树的根本,是决策树利用特征来分类时,确定特征选取顺序的依据。理解了它们,决策树你也就了解了大概。

  引用香农的话来说,信息是用来消除随机不确定性的东西。当然这句话虽然经典,但是还是很难去搞明白这种东西到底是个什么样,可能在不同的地方来说,指的东西又不一样。对于机器学习中的决策树而言,如果带分类的事物集合可以划分为多个类别当中,则某个类(xi)的信息可以定义如下:

I(x)用来表示随机变量的信息,p(xi)指是当xi发生时的概率。

  熵是用来度量不确定性的,当熵越大,X=xi的不确定性越大,反之越小。对于机器学习中的分类问题而言,熵越大即这个类别的不确定性更大,反之越小。

  信息增益在决策树算法中是用来选择特征的指标,信息增益越大,则这个特征的选择性越好。往往在决策树中的层数也越靠前。

2)决策树

  决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。常见的决策树算法有C4.5、ID3和CART。3种算法的模型构建思想都十分类似,只是采用了不同的指标。决策树模型的构建过程大致如下:

ID3,C4.5决策树的生成

输入:训练集D,特征集A,阈值eps 输出:决策树T

  1. 若D中所有样本属于同一类Ck,则T为单节点树,将类Ck作为该结点的类标记,返回T
  2. 若A为空集,即没有特征作为划分依据,则T为单节点树,并将D中实例数最大的类Ck作为该结点的类标记,返回T
  3. 否则,计算A中各特征对D的信息增益(ID3)/信息增益比(C4.5),选择信息增益最大的特征Ag
  4. 若Ag的信息增益(比)小于阈值eps,则置T为单节点树,并将D中实例数最大的类Ck作为该结点的类标记,返回T
  5. 否则,依照特征Ag将D划分为若干非空子集Di,将Di中实例数最大的类作为标记,构建子节点,由结点及其子节点构成树T,返回T
  6. 对第i个子节点,以Di为训练集,以A-{Ag}为特征集,递归地调用1~5,得到子树Ti,返回Ti

CART决策树的生成

对回归树:用平方误差最小化准则,进行特征选择,生成二叉树

对分类树:用基尼指数最小化准则,进行特征选择,生成二叉树

         PS:基尼指数(Gini)代表了某一集合的不确定性,Gini越大,样本集合的不确定性就越大,这点和熵相似。


3)集成学习

  集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是生成多个分类器/模型,各自独立地学习和作出预测。这些预测最后结合成单预测,因此优于任何一个单分类的做出预测。随机森林是集成学习的一个子类,它依靠于决策树的投票选择来决定最后的分类结果。

三、随机森林的生成

  前面提到,随机森林中有许多的分类树。我们要将一个输入样本进行分类,我们需要将输入样本输入到每棵树中进行分类。打个形象的比喻:森林中召开会议,讨论某个动物到底是老鼠还是松鼠,每棵树都要独立地发表自己对这个问题的看法,也就是每棵树都要投票。该动物到底是老鼠还是松鼠,要依据投票情况来确定,获得票数最多的类别就是森林的分类结果。森林中的每棵树都是独立的,99.9%不相关的树做出的预测结果涵盖所有的情况,这些预测结果将会彼此抵消。少数优秀的树的预测结果将会超脱于芸芸“噪音”,做出一个好的预测。将若干个弱分类器的分类结果进行投票选择,从而组成一个强分类器,这就是随机森林bagging的思想(关于bagging的一个有必要提及的问题:bagging的代价是不用单棵决策树来做预测,具体哪个变量起到重要作用变得未知,所以bagging改进了预测准确率但损失了解释性。)。下图可以形象地描述这个情况:


有了树我们就可以分类了,但是森林中的每棵树是怎么生成的呢?

  每棵树的按照如下规则生成:

  1)如果训练集大小为N,对于每棵树而言,随机且有放回地从训练集中的抽取N个训练样本(这种采样方式称为bootstrap sample方法),作为该树的训练集;

  从这里我们可以知道:每棵树的训练集都是不同的,而且里面包含重复的训练样本(理解这点很重要)。

  为什么要随机抽样训练集?

  如果不进行随机抽样,每棵树的训练集都一样,那么最终训练出的树分类结果也是完全一样的,这样的话完全没有bagging的必要;

  为什么要有放回地抽样?

  我理解的是这样的:如果不是有放回的抽样,那么每棵树的训练样本都是不同的,都是没有交集的,这样每棵树都是"有偏的",都是绝对"片面的"(当然这样说可能不对),也就是说每棵树训练出来都是有很大的差异的;而随机森林最后分类取决于多棵树(弱分类器)的投票表决,这种表决应该是"求同",因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的,这样无异于是"盲人摸象"。

  2)如果每个样本的特征维度为M,指定一个常数m<<M随机地从M个特征中选取m个特征子集,每次树进行分裂时,从这m个特征中选择最优的;

  3)每棵树都尽最大程度的生长,并且没有剪枝过程

  一开始我们提到的随机森林中的“随机”就是指的这里的两个随机性。两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入,使得随机森林不容易陷入过拟合,并且具有很好得抗噪能力(比如:对缺省值不敏感)。

  随机森林分类效果(错误率)与两个因素有关:

  • 森林中任意两棵树的相关性:相关性越大,错误率越大;
  • 森林中每棵树的分类能力:每棵树的分类能力越强,整个森林的错误率越低。

  减小特征选择个数m,树的相关性和分类能力也会相应的降低;增大m,两者也会随之增大。所以关键问题是如何选择最优的m(或者是范围),这也是随机森林唯一的一个参数。

四、袋外错误率

上面我们提到,构建随机森林的关键问题就是如何选择最优的m,要解决这个问题主要依据计算袋外错误率oob error(out-of-bag error)。

  随机森林有一个重要的优点就是,没有必要对它进行交叉验证或者用一个独立的测试集来获得误差的一个无偏估计。它可以在内部进行评估,也就是说在生成的过程中就可以对误差建立一个无偏估计。

  我们知道,在构建每棵树时,我们对训练集使用了不同的bootstrap sample(随机且有放回地抽取)。所以对于每棵树而言(假设对于第k棵树),大约有1/3的训练实例没有参与第k棵树的生成,它们称为第k棵树的oob样本。

  而这样的采样特点就允许我们进行oob估计,它的计算方式如下:

  (note:以样本为单位)

  1)对每个样本,计算它作为oob样本的树对它的分类情况(约1/3的树);

  2)然后以简单多数投票作为该样本的分类结果;

  3)最后用误分个数占样本总数的比率作为随机森林的oob误分率。

五、opencv实现随机森林算法

本次实现的是OCR进行分类,具体代码如下:  

bool read_num_class_data(const string& filename, int var_count, Mat* _data, Mat* _responses)
 {
	   const int M = 1024;
	   char buf[M + 2];
	   Mat el_ptr(1, var_count, CV_32F);
	   int i;
	   vector<int> responses;
	   _data->release();
	   _responses->release();
	   FILE *f;
	   fopen_s(&f, filename.c_str(), "rt");
	   if (!f)
	   {
		   cout << "Could not read the database " << filename << endl;
		   return false;
	   }
	
	   for (;;)
	   {
		   char* ptr;
		   if (!fgets(buf, M, f) || !strchr(buf, ','))
			   break;
		   responses.push_back((int)buf[0]);
		   ptr = buf + 2;
		   for (i = 0; i < var_count; i++)
		   {
			   int n = 0;
			   sscanf_s(ptr, "%f%n", &el_ptr.at<float>(i), &n);
			   ptr += n + 1;
		   }
		   if (i < var_count)
			   break;
		   _data->push_back(el_ptr);
		 }
	     fclose(f);
	     Mat(responses).copyTo(*_responses);
	     return true;
	 }

Ptr<TrainData> prepare_train_data(const Mat& data, const Mat& responses, int ntrain_samples)
{
	     Mat sample_idx = Mat::zeros(1, data.rows, CV_8U);
	     Mat train_samples = sample_idx.colRange(0, ntrain_samples);
	     train_samples.setTo(Scalar::all(1));
		 int nvars = data.cols;
	     Mat var_type(nvars + 1, 1, CV_8U);
	     var_type.setTo(Scalar::all(VAR_ORDERED));
	     var_type.at<uchar>(nvars) = VAR_CATEGORICAL;
		 return TrainData::create(data, ROW_SAMPLE, responses,noArray(), sample_idx, noArray(), var_type);
}

inline TermCriteria TC(int iters, double eps)
{
     return TermCriteria(TermCriteria::MAX_ITER + (eps > 0 ? TermCriteria::EPS : 0), iters, eps);
}

void test_and_save_classifier(const Ptr<StatModel>& model, const Mat& data, const Mat& responses,
	     int ntrain_samples, int rdelta)
	 {
	     int i, nsamples_all = data.rows;
		 double train_hr = 0, test_hr = 0;
		 for (i = 0; i < nsamples_all; i++)
		 {
		         Mat sample = data.row(i);
			     float r = model->predict(sample);
		         r = std::abs(r + rdelta - responses.at<int>(i)) <= FLT_EPSILON ? 1.f : 0.f;
			     if (i < ntrain_samples)
			            train_hr += r;
		         else
			            test_hr += r;
		 }
		 test_hr /= nsamples_all - ntrain_samples;
	     train_hr = ntrain_samples > 0 ? train_hr / ntrain_samples : 1.;
		 printf("Recognition rate: train = %.1f%%, test = %.1f%%\n",
			         train_hr*100., test_hr*100.);
	 }


bool build_rtrees_classifier(const string& data_filename)
{
	    Mat data;
	    Mat responses;
	    read_num_class_data(data_filename, 16, &data, &responses);
		int nsamples_all = data.rows;
	    int ntrain_samples = (int)(nsamples_all*0.8);
		Ptr<RTrees> model;
	    Ptr<TrainData> tdata = prepare_train_data(data, responses, ntrain_samples);
        model = RTrees::create();
	    model->setMaxDepth(10);
	    model->setMinSampleCount(10);
	    model->setRegressionAccuracy(0);
	    model->setUseSurrogates(false);
	    model->setMaxCategories(15);
	    model->setPriors(Mat());
	    model->setCalculateVarImportance(true);
	    model->setActiveVarCount(4);
	    model->setTermCriteria(TC(100, 0.01f));
	    model->train(tdata);
	    test_and_save_classifier(model, data, responses, ntrain_samples, 0);
	    cout << "Number of trees: " << model->getRoots().size() << endl;
		Mat var_importance = model->getVarImportance();
		if (!var_importance.empty())
		{
			double rt_imp_sum = sum(var_importance)[0];
			printf("var#\timportance (in %%):\n");
			int i, n = (int)var_importance.total();
			for (i = 0; i < n; i++)
				printf("%-2d\t%-4.1f\n", i, 100.f*var_importance.at<float>(i) / rt_imp_sum);
		}
	    return true;
	 }

int main()
{
	string data_filename = "D:\\cv_study\\Machine learning\\Random_forest\\letter-recognition.data";
    build_rtrees_classifier(data_filename);
    return 0;
}

由上图看出,分类效果不是太好。以后有时间我会尝试DNN的效果。




版权声明:本文为zhangjunp3原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zhangjunp3/article/details/80895821