[人工智能]Random Forests C++实现：细节，使用与实验

代码已同步到github randomforests
欢迎讨论

1. 随机森林简介

1.1 算法简介

????????随机森林（Random Forest, RF）算法是一类集成学习算法，它由统计学习界的大师级人物 Leo Breiman(1928–2005) 提出^[1]。它是若干随机树（Randomized Tree）的组合，这些随机树彼此互相独立，而且在训练样本的选择和树的生长过程中引入随机性以降低树结构分类器较高的方差。随机森林在很多应用场景下具有不错的准确性，它具备一些优良特性，比如，较少的超参，高效的训练与预测，多分类和对噪声不敏感等。这些特性使它广泛应用于不同领域，比如计算机视觉，遥感，生物信息学等。特别在计算机视觉领域，随机森林在图像分割、特征点识别、目标检测和人体部件识别等方面都有比较成功的应用。
????????本文并不是随机森林算法的入门，需要对RF算法具有一定的认识甚至实践经验。若想对RF有详细甚至进一步的深入了解，推荐阅读微软的技术报告^[3]，这份报告对分类森林、随机回归森林、概率密度森林等从算法和实现角度进行了介绍。

1.2 随机特性

????????针对不同问题随机森林学习算法包括分类和回归两类。随机森林是一组随机树的组合，它们彼此独立且有较大差异。其中的随机树按传统分类回归树(Classification and Regression Tree, CART) 的训练方式生长到最大深度，但是不进行剪枝（pruning）。随机性主要体现在两个方面：（1）训练样本的随机选择，即使用自举重采样法（Bootstrap Sampling）为森林中每棵树生成有差异的训练样本，其本质上是 Bagging 集成学习思想。Bagging 能够提高不稳定学习算法分类和预测的准确性，即降低学习算法的方差（Variance）。因此，引入 Bagging方法可降低树结构学习算法较高的方差^[4]。（2）另一方面，随机性也体现在树中节点的分裂方式中。每个节点进行分裂时仅从参数空间中随机选择一个子集，在其中选出“最优”的分裂参数。在树的生长过程中加入随机性可以降低它们彼此之间的相关度，从而降低集成学习算法的泛化误差的上限^[1]。

2. C++实现和使用

2.1 动机

????????目前Random Forest的实现大多是python、R语言，C++实现存在但比较少，我所知的且好用的仅有opencv, ALGLIB。此外，上述实现一般作为一个机器学习库的一部分，或者需要科学上网才能下载，使用成本稍高。下图总结了各类RF实现。

上图来自论文：
Anne-Laure Boulesteix, Silke Janitza. Overview of random forest methodology and practical guidance with emphasis on computational biology and bioinformatics. WIREs Data Mining and Knowledge Discovery 2012, 2: 493–507.
此外，还有微软的decision forest(C++)；刚刚开源的tensorflow决策森林 (TF-DF); 基于NumPy实现的机器学习库 numpy-ml;
高度优化，并且在开源社区中速度最快的scikit-learn中的sklearn.ensemble模块，提供了许多可选参数。
… …

????????本文RF实现的主体代码其实在2012年就已经完成，当时还写了篇博文《肤色检测（分割）via Random Forest》，效果还不错。今年3月以来对部分算法和交互的代码做了优化，跑了十几个数据集，并与论文中结果进行了比对，验证了算法的正确性。这版程序尽力做到实现的准确，注重代码质量提高运行性能，兼顾简洁、对用户友好。以下是本RF实现的特点：

1. 适用于分类和回归, 支持回归的多维输出
2. off-the-shelf，即插即用
3. 提供两种使用方式：命令行与嵌入代码(C风格的C++)
4. 提供python接口（未完待续）
5. 支持3种随机性
6. 可保存训练完成的模型至本地 (XML格式，可读性强)，也可读取本地模型进行预测^*
   使用tinyxml2库支持xml文件的读写

2.2 细节

2.2.1 算法的参数（Hyperparameters）

1. MaxDepth: 树最大的深度，若传入负值则使用默认值40
2. TreesNum: 森林中树的数量，若传入负值则使用默认值200
3. SplitVariables: 用于分裂的候选特征数量，如果传入负值则使用默认值，对于分类问题设置为$\sqrt{n\_features}$，对于回归问题设置为$\frac{n\_features}{3}$
4. MinSamplesSplit: 节点还能往下分裂的最小样本数
5. Randomness: 1或2或3，随数字增大在节点分类的随机性增加，1为经典RF（默认），3为Etra-Trees^[4]

2.2.2 关于节点分裂方式

????????对于随机森林中的每棵树，在每个节点要寻找“最优”的分裂参数，使训练样本分裂后的信息增益（Information Gain, IG, 式1）最大化。IG衡量了分裂前后节点上样本不纯度（impurity）的下降幅度。对于分类森林，采用了Gini系数来计算节点不纯度；对于回归森林，采用了方差（或协方差）来描述节点不纯度。为了方便实现和控制计算量，采用了“轴平行”（axis aligned）的分裂方式（即经典RF），其他分裂方式可见微软的技术报告^[3]。
$$IG=H\left(S\right)?\sum _{i=l,r}\frac{|S^i|}{|S|}H\left(S^i\right)\text{\hspace{1em}(1)}$$
????????上一小节中提到的参数“Randomness”用来控制节点分裂时的随机性，实际上是控制了节点分裂时参数空间的大小，参数空间越小随机性越大。“Randomness”可选参数值为{1，2，3}，对应含义为：

"1": Breiman的经典RF，在寻找节点分裂特征和分裂值时采用基于快排（quick sort）+“积分”的加速方法，使时间复杂度从$O(n^2)$降低到$O(n\log n)$，$n$为达到节点样本数（实测在elevators数据集上加速370倍，参数为[200, 40, 6, 5]）；
"2": 从候选特征的最大值与最小值之间均匀得到$K$（默认为50）个候选的分裂值，再从中选择较优的特征和对应的分裂值，当$K\to \infty$，即为经典RF；
"3": 采用论文“Extremely randomized trees”^[4]的方法，从候选特征的最大值与最小值之间随机选择一个值作为候选，然后再选择较优的特征和对应的分裂值。

2.2.3 关于终止条件

当到达节点的样本不可分或者不必再分时，停止树的生长。具体来说，满足以下条件之一时，停止生长，RF不对树进行剪枝。

1. 达到最大深度MaxDepth；
2. 到达节点的样本的不纯度低于阈值：节点上样本的类别相同（适用于分类）或者样本目标值的方差为0（适用于分类回归）；
3. 到达节点的样本数小于等于MinSamplesSplit。
   以上三个条件满足其一，即终止继续生长。
   注：对于分类问题，如果只满足第三个条件，但是最多和第二多类别的样本数相同，那么还需要继续往下生长。

存在特殊情况，当不满足上述“终止条件”，但从候选的SplitVariables个特征中无法获得分裂值，此时尝试从所有特征中随机选择可能的分裂值的方式。这有可能出现在达到节点样本数较少，且SplitVariables较小的场景，恰巧候选特征的值都相同。若还是不可分则停止树的生长。

2.2.4 关于预测

Final predictions are obtained by aggregating over the ensemble. — Gérard Biau

1. 对于分类问题，可用hard descion或者soft decsion两种方式。先介绍后者，随机森林训练结束后，测试样本$x$经过每棵树到达叶子节点，那么样本$x$属于类别$c$的概率为：
   $$p\left(c\mid x\right)=\frac{1}{T}\sum _{t=1}^T{p}_t\left(c\mid x\right)$$
   其中，$T$为森林中随机树的数量，$p_t\left(c\mid x\right)$为叶子节点的类别分布。那么对$x$类别的决策为：
   c ^ = arg ? max ? c ∈ { 1 , ? ? , N c } p ( c ∣ x ) \hat{c}=\mathop{\arg\max}_{c\in \left \{ 1,\cdots,N_{c} \right \}}p\left ( c\mid x \right ) c^=argmaxc∈{1,?,Nc?}?p(c∣x)
   以上是soft decision。对于Hard decision，每颗树输出对应的类别，然后统计出现最多的类别即为$x$的类别，也就是多数投票。

2. 对于回归问题，使用所有树输出的平均值。

2.3 使用

源码可以从github上下载：gxf1027/randomforests

2.3.1 命令行方式

可执行文件在bin目录下，也可以自行编译（linux）

git clone https://github.com/gxf1027/randomforests.git
cd randomforests
# g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
# train
g++ -fpermissive -std=c++11 -O2  src/RandomCLoquatForests.cpp src/RandomRLoquatForests.cpp src/UserInteraction2.cpp src/SharedRoutines.cpp src/tinyxml2/tinyxml2.cpp demo/rf_train.cpp  -o rf_train
# test
g++ -fpermissive -std=c++11 -O2 src/RandomCLoquatForests.cpp src/RandomRLoquatForests.cpp src/UserInteraction2.cpp  src/SharedRoutines.cpp src/tinyxml2/tinyxml2.cpp demo/rf_test.cpp  -o rf_test

如果是windows下，包含 src和demo目录，通过IDE编译即可。
示例1：训练

分类：./rf_train -p 0 -c RF_config.xml -d dataset.data -o ClassificationForest.xml
回归：./rf_train -p 1 -c RF_config.xml -d dataset.data -o RegressionForest.xml

• -p: '0’表示分类问题，'1’表示回归问题
• -c: RF的参数，通过xml文件指定
  以下为参数文件的示例

<?xml version="1.0" ?>
<RandomForestConfig>
	<MaxDepth>40</MaxDepth>
	<TreesNum>200</TreesNum>
	<SplitVariables>4</SplitVariables>
	<MinSamplesSplit>5</MinSamplesSplit>
	<Randomness>1</Randomness>
</RandomForestConfig>

如果不提供参数文件，则使用默认参数

• -d: 训练集数据文件，需要遵循以下格式

用于分类的数据集文件：
开头三行为样本数(totoal_sample_num), 特征数(variable_num), 类别数(class_num)
接下来每一行为一个训练样本，数字用空格分隔，其中首列为类别序号（从0开始，如对于二分类问题为0, 1）

@totoal_sample_num=19020
@variable_num=10
@class_num=2
1 86.088 36.259 3.4839 0.2359 0.1337 -12.893 -56.746 -4.0291 4.158 372.98
1 76.099 18.755 2.8639 0.3461 0.2209 -90.721 -52.015 -19.577 3.46 271.43
1 62.989 22.083 3.1191 0.2258 0.1167 -85.779 48.038 19.251 7.652 246
1 19.55 10.763 2.3201 0.6077 0.3421 8.3626 -17.38 -10.092 17.368 173.39
0 67.609 26.678 2.632 0.3851 0.2462 -56.63 -57.963 19.806 79.666 227.19
1 24.909 17.432 2.632 0.3944 0.2229 7.1171 -2.3838 -8.6055 37.114 204.79

用于回归的数据集文件：
开头三行为样本数(totoal_sample_num), 特征数(variable_num_x), 目标维度(variable_num_y)
接下来每一行为一个训练样本，数字用空格分隔，其中前’variable_num_y’列为目标值

@totoal_sample_num=4177
@variable_num_x=8
@variable_num_y=1
15 1 0.455 0.365 0.095 0.514 0.2245 0.101 0.15 
7 1 0.35 0.265 0.09 0.2255 0.0995 0.0485 0.07 
9 2 0.53 0.42 0.135 0.677 0.2565 0.1415 0.21 
10 1 0.44 0.365 0.125 0.516 0.2155 0.114 0.155 
7 3 0.33 0.255 0.08 0.205 0.0895 0.0395 0.055 
8 3 0.425 0.3 0.095 0.3515 0.141 0.0775 0.12 

• -o: （可选）输出RF模型到本地路径（以xml文件格式，下图为部分片段）
  

训练过程(以分类为例，pendigits数据集）

示例2：测试

./rf_test -p 0 -c rf_pendigits.xml -d ./DataSet/Classification/pendigits.tes -o test-pendigits.out

• -c: RF模型文件，即rf_train输出到本地的模型文件
• -d: 测试数据集，格式与训练集相同
• -o: 输出结果至文件
  

2.3.2 代码嵌入方式（推荐）

包含src目录下源文件，编写训练或者预测代码。各函数及其参数在头文件中有详细说明，容易上手。以下给出训练和预测的代码片段。

训练
从本地数据文件读入数据集进行训练，计算oob-error(oob-mse)，并保存forest到本地。
（1）分类森林

#include <cmath>
using namespace std;

#include "RandomCLoquatForests.h"
#include "UserInteraction2.h"

int main()
{
	// read training samples if necessary
	char filename[500] = "./DataSet/Classification/pendigits.tra";
	float** data = NULL;
	int* label = NULL;
	Dataset_info_C datainfo;
	InitalClassificationDataMatrixFormFile2(filename, data/*OUT*/, label/*OUT*/, datainfo/*OUT*/);
	// setting random forests parameters
	RandomCForests_info rfinfo;
	rfinfo.datainfo = datainfo;
	rfinfo.maxdepth = 40;
	rfinfo.ntrees = 500;
	rfinfo.mvariables = (int)sqrtf(datainfo.variables_num);
	rfinfo.minsamplessplit = 5;
	rfinfo.randomness = 1;
	// train forest
	LoquatCForest* loquatCForest = NULL;
	TrainRandomForestClassifier(data, label, rfinfo, loquatCForest /*OUT*/, 50);
	float error_rate = 1.f;
	OOBErrorEstimate(data, label, loquatCForest, error_rate /*OUT*/);
	// save RF model
	SaveRandomClassificationForestModelToXML2("Modelfile.xml", loquatCForest);
	// clear the memory allocated for the entire forest
	ReleaseClassificationForest(&loquatCForest);
	// release money: data, label
	for (int i = 0; i < datainfo.samples_num; i++)
   		delete[] data[i];
	delete[] data;
	delete[] label;
	return 0;
}

（2）回归森林

#include "RandomRLoquatForests.h"
#include "UserInteraction2.h"
using namespace std;

int main()
{
	// read training samples if necessary 
    char filename[500] = "./DataSet/Regression/Housing_Data_Set-R.txt"; 
	float** data = NULL;
	float** target = NULL;
	Dataset_info_R datainfo;
	InitalRegressionDataMatrixFormFile2(filename, data /*OUT*/, target /*OUT*/, datainfo /*OUT*/);
	// setting random forests parameters
	RandomRForests_info rfinfo;
	rfinfo.datainfo = datainfo;
	rfinfo.maxdepth = 40;
	rfinfo.ntrees = 200;
	rfinfo.mvariables = (int)(datainfo.variables_num_x / 3.0 + 0.5); 
	rfinfo.minsamplessplit = 5;
	rfinfo.randomness = 1; 
	// train forest
	LoquatRForest* loquatRForest = NULL;
	TrainRandomForestRegressor(data, target, rfinfo, loquatRForest /*OUT*/, false, 20);
	float* mean_squared_error = NULL;
	MSEOnOutOfBagSamples(data, target, loquatRForest, mean_squared_error /*OUT*/);
	delete[] mean_squared_error;
	// save RF model
	SaveRandomRegressionForestModelToXML2("Modelfile-R.xml", loquatRForest);
	// clear the memory
	ReleaseRegressionForest(&loquatRForest);
	// release money: data, target
	for (int i = 0; i < datainfo.samples_num; i++)
   	{
		   delete[] data[i];
		   delete[] target[i];
	}	
	delete[] data;
	delete[] target;
}

说明

• 以上代码仅为主干，实际使用需对函数返回值进行判断。
• RF结构体对象loquatForest的内存由TrainRandomForestClassifier /TrainRandomForestRegressor 负责分配，由ReleaseClassificationForest /ReleaseRegressionForest 释放内存，用户无需对其分配或者释放
• OOBErrorEstimate 计算out-of-bag分类错误率，输入参数data, label必须与训练时相同,MSEOnOutOfBagSamples类同
• InitalClassificationDataMatrixFormFile2/InitalRegressionDataMatrixFormFile2 从本地文件读取数据集，文件格式与“命令行方式”中相同。也可以自行准备训练数据，就可以不调用上述函数。

预测

// 分类森林：label_index用于返回预测的类别
EvaluateOneSample(data, loquatForest, label_index /*OUT*/, 1);
// 回归森林：target_predicted用于返回预测的目标值
EvaluateOneSample(data, loquatForest, target_predicted /*OUT*/);

• 提供单个样本的分类/回归接口，对整个数据集可以循环解决。
• 分类森林的最后一个参数表示预测方式，1：hard，0：soft decision。

3. Python接口

未完待续

4. 实验

4.1 数据集

1. Bike-Sharing: 原数据集去掉第1、2列
2. Parkinsons_Telemonitoring: 预测输出(output)是2维的。将原数据集第1列（subject number）去掉，UCI网站上记录“Number of Attributes：26”但根据下载的数据集只有22维（包括2维output)

4.2 参数

????????使用2.2中参数，下一小节表格中“参数”列为 [TreesNum, SplitVariables, MaxDepth, MinSamplesSplit] （randomness均为1，即经典RF）。实验并没有对参数进行调优，而是根据经验选取了个人认为比较合理的参数组合。实验目的一方面是为了验证算法实现的正确性，另一方面也想说明RF对参数敏感度较低（相比SVM）。

Clearly, some algorithms such as glmnet and svm are much more tunable than the others,
while ranger(random forest) is the algorithm with the smallest tunability.^[6]

4.3 结果

????????如果没有特殊说明，分类和回归问题的实验结果分别通过out-of-bag分类错误率（%）和out-of-bag 均方误差(Mean Square Error (MSE))来统计，结果运行10次取平均和标准差。可以看到，大多数数据集都采用了默认的参数，也能达到较理想效果。

The out-of-bag (oob) error estimate
…This has proven to be unbiased in many tests^[2].

*: 表示使用分类森林默认的$\sqrt{variable\_num}$作为SplitVariables参数;
#:表示使用回归森林默认的??$\frac{variable\_num\_x}{3}$作为SplitVariables参数
3: Parkinsons_Telemonitoring的预测输出是2维的，本算法并不是把它分解为两个独立回归问题，而是直接使用多维输出数据进行训练。

5. 分析

5.1 参数影响

????????通常RF在默认参数设定下也能取得较理想的效果，通过对参数（见2.2节）调优可以获得更佳的分类/回归效果。一般可以对TreesNum和SplitVariables进行调优。通常认为增加TreesNum会使泛化误差下降（当然也有特例）。如下图，展示了随着树增加，oob error呈现下降的趋势。

????????SplitVariables是控制RF随机性的主要参数，当它增加时树之间的关联性也随之增加，而关联性增加会导致分类/回归误差提高^[2]。从可调性(Tunability)角度考虑，调节SplitVariables对性能提升的贡献是最大的。而SplitVariables选择默认设定时，通常也能取得不错的效果。

The correlation between any two trees in the forest. Increasing the correlation increases the forest error rate.^[2]
In ranger(random forest) mtry is the most tunable parameter which is already common knowledge and is implemented in software packages such as caret.^[6]

下图为pendigits数据集上，不同SplitVariables（样本为16维，TreesNum=500）参数下的分类oob error。

5.2 特征重要性

????????特征重要性(variable importance)的评估是RF“自带”的一个特性。采用oob数据的特征随机交换的方法来估计特征重要性。对于数据集"waveform"，结果如下图所示，可见后一半特征的重要性几乎为0，这是因为waveform的后19维特征是随机噪声，因此variable importance计算结果符合上述情况。

参考文献

[1]. Breiman, L. Random Forests . Machine Learning 45, 5–32, 2001.

[2]. Leo Breiman, Adele Cutler. Random Forest Homepage on berkeley website.

[3]. Antonio Criminisi, Ender Konukoglu, Jamie Shotton. Decision Forests for Classification, Regression, Density Estimation, Manifold Learning and Semi-Supervised Learning. MSR-TR-2011-114, 2011.

[4]. P. Geurts, D. Ernst, and L. Wehenkel. Extremely randomized trees . Machine Learning, 63(1), 2006: 3-42.

[5]. Manuel Fernández-Delgado, Eva Cernadas, Senén Barro, Dinani Amorim. Do we Need Hundreds of Classifiers to Solve Real World Classification Problems? Journal of Machine Learning Research, 15(90):3133?3181, 2014.

[6]. Philipp Probst, Anne-Laure Boulesteix, Bernd Bischl. Tunability: Importance of Hyperparameters of Machine Learning Algorithms. Journal of Machine Learning Research, 20(53):1?32, 2019.