随机森林

森林由若干棵树组成。

随机森林由若干棵决策树组成，每棵决策树之间互不相关。

随机体现在：

• 通过 随机 抽取得到不同的样本，来构建每棵决策树。
• 决策树每个节点的最佳分叉属性从由 随机 得到的特征属性集合中选取。

预测时，预测样本作用于所有决策树。

• 对于分类问题，利用投票方式得到分类。
• 对于回归问题，取所有决策树结果的平均值。

随机过程

Bootstrap 过程

Bootstrap过程：生成每棵决策树时，使用的参数相同，但使用的训练集不同。

• 随机得到的子集称为 bootstrap 集合。

在 Bootstrap 集合的基础上聚集得到学习模型的过程称为 Bagging（Bootstrap aggregating）。

不在 Bootstrap 集合中的样本称为 OOB（Out Of Bag）。

Bootstrap 过程：从全部 $N$ 个样本中，有放回的随机抽取 $S$ 次（OpenCV中，$S=N$），其中存在 OOB。计算 OOB 样本所占比率：

• 每个样本被抽取的概率为 $1/N$，未被抽取的概率为 $1-1/N$，$S$ 次仍未被抽到的概率为 $(1-1/n)^S$，$\lim_{N=S\rightarrow \infty}(1-\frac{1}{N})^S=e^{-1}$。

随机森林中每棵决策树的 bootstrap 集合是不完全相同的，每棵决策树的 OOB 集合也不完全相同。

即每棵生成决策树之前，进行 Bootstrap 过程。

• 保证 bootstrap 集合不同，保证了每棵决策树不相关以及不相同。

随机特征属性过程

随机森林的决策树的最佳分叉属性是在一个特征属性随机子集内计算得到。

• 全部的 $p$ 个特征属性中，随机选择 $q$ 个特征属性。
  • 对于分类问题，$q$ 可以为 $p$ 的平方根。
  • 对于回归问题，$q$ 可以为 $p$ 的三分之一。

随机子集内特征属性的数量 $q$ 是固定的，但不同决策树之间这 $q$ 个特征属性不同。

• 由于 $q$ 远小于 $p$，构建决策树时无需剪枝。

OOB误差

评估机器学习算法的预测误差的常用方法时交叉验证法，但 Bagging 方法不需要交叉验证。

OOB 误差可以代替 bootstrap 集合误差，结果近似于交叉验证。

• OOB 误差是利用那 $e^{-1}$ 的 OOB 样本来评估预测误差。

OOB 误差计算是在训练过程同步得到。每得到一棵决策树，就可以根据该决策树来调整前面决策树得到的 OOB 误差。

对于分类问题， OOB 误差计算：

• 构建生成决策树 $T_k,k=1,2,...,K$。

1. 用 $T_k$ 预测 $T_k$ 的 OOB 样本的分类结果。
2. 更新所有训练样本的 OOB 预测分类结果次数（如果样本 $\mathbf{x}$ 是 $T_1$ 的 OOB 样本，则它有一个预测结果，而它是 $T_2$ 的 bootstrap 集合内的样本，则此时它没有预测结果）。
3. 对所有样本，把每个样本的预测次数最多的分类作为该样本在 $T_k$ 时的预测结果。
4. 统计所有训练样本中预测错误的数量。
5. 该数量除以 $T_k$ 的 OOB 样本的数量作为 $T_k$ 的 OOB 误差。

对于回归问题， OOB 误差计算：

• 构建生成决策树 $T_k,k=1,2,...,K$。

1. 用 $T_k$ 预测 $T_k$ 的 OOB 样本的回归值。
2. 累加所有训练样本中的 OOB 样本的预测值。
3. 对所有样本，计算 $T_k$ 时每个样本的平均预测值（预测累加值除以被预测的次数）。
4. 累加每个训练样本平均预测值与真实响应值之差的平方。
5. 该平方累加和除以 $T_k$ 的 OOB 样本的数量作为 $T_k$ 的 OOB 误差。

OOB 误差会逐渐缩小，设置精度 $\varepsilon$，当误差小于 $\varepsilon$ 时，提前终止迭代。

计算特征属性的重要性

特征属性的重要性：样本哪个特征属性对预测起决定作用。

Gini 法和置换法常用于计算特征属性的重要性。

Gini 法依据不纯度减小的原则。

置换法依据原则为：样本某个特征属性越重要，那么改变该特征属性值，则样本预测值就越容易出错。

• 通过置换两个样本的相同特征属性的值来改变特征属性。

具体方法：

在决策树 $T_k$ 的 OOB 集合中随机选择两个样本 $\mathbf{x}_i=(x_{i,1},x_{i,2},\ldots,x_{i,p})$ 和 $\mathbf{x}_j=(x_{j,1},x_{j,2},\ldots,x_{j,p})$，这两个样本响应值分别为 $y_i$ 和 $y_j$，用 $T_k$ 的预测值分别为 $\hat{y}_i^{(k)}$ 和 $\hat{y}_j^{(k)}$。

设该 OOB 集合有 $m_k$ 个样本。衡量第 $q$ 个特征属性的重要性，置换 $\mathbf{x}_i$ 和 $\mathbf{x}_j$ 中的 $x_{i,q}$ 和 $x_{j,q}$，置换后为：$\mathbf{x}_{i,jq}=(x_{i,1},\ldots,x_{j,q},\ldots,x_{i,p})$ 和 $\mathbf{x}_{j,iq}=(x_{j,1},\ldots,x_{i,q},\ldots,x_{j,p})$

根据这个方法，对 OOB 集合共置换 $m_k$ 次，最终置换结果为：$\mathbf{x}_{i,mq}=(x_{i,1},\ldots,x_{mi,q},\ldots,x_{i,p})$。

使用 $T_k$ 对 $\mathbf{x}_{i,mq}$ 的预测值为 $\hat{y}_{i,mq}^{(k)}$。

对于分类问题：

• 如果 $\hat{y}_{i,mq}^{(k)}=y_i$，说明改变第 $q$ 个特征属性的值，并不改变最终的响应值。
• 如果 $\hat{y}_{i,mq}^{(k)}\neq y_i$，说明第 $q$ 个特征属性很重要。

重要程度量化为：

$\mathbf{VI}_q^{(k)}=\frac{\sum_{i\in m_k}I(y_i=\hat{y}_i^{(k)})-\sum_{i\in m_k}I(y_i=\hat{y}_{i,mq}^{(k)})}{m_k}$

• 分子第一项表示对 OOB 中，预测正确的样本数量。
• 分子第二项表示置换后正确的样本数量。

对于回归问题，重要程度量化为：

$\mathbf{VI}_q^{(k)}=\frac{\sum_{i\in m_k}e^{-\left(\frac{y_i-\hat{y}_i^{(k)}}{A}\right)^2}-\sum_{i\in m_k}e^{-\left(\frac{y_i-\hat{y}_{i,mq}^{(k)}}{A}\right)^2}}{m_k}$

其中，

$A=\max_{i\in N}\vert y_i\vert$

如果第 $q$ 个特征属性不属于 $T_k$，则 $\mathbf{VI}_q^{(k)}=0$。

对随机森林的所有决策树都计算第 $q$ 个特征属性的重要性，取平均得到整个随机森林对第 $q$ 个特征属性的重要程度量化为：

$\mathbf{VI}_q=\frac{\sum_{i=1}^K\mathbf{VI}_q^{(i)}}{K}$

归一化处理：

$\mathbf{VI}_{q^{(1)}}=\frac{\mathbf{VI}_q}{\sum_{i=1}^p\mathbf{VI}_i}$

OpenCV 提供的随机森林

OpenCV 提供了一个 继承自 DTree 的 RTree 类，可用于设计随机森林。

• DTree 指决策树。

部分参数如下：

• CalculateVarImportance：表示是否计算特征属性的重要程度。函数接口：

1
2
3
4

bool getCalculateVarImportance();
void setCalculateVarImportance(bool val); // 默认值为false

// 可以通过RTrees::getVarImportance检索。

• ActiveVarCount：在每棵树结点处随机选择的特征子集的大小，以及所使用的找到最佳分割点。如果将其设置为0，则大小将设置为特征总数的平方根。函数接口：

1
2

int getActiveVarCount() ;
void setActiveVarCount(int val); // 默认值为0

• TermCriteria：迭代终止条件。

还有些参数通过 DTree 的函数设置。

例子-单词难度预测(RTrees)

该数据集在决策树中也使用过，故不多介绍。

数据集属性有：

• Word：单词
• Length：长度
• Freq_HAL：频率_HAL
• Log_Freq_HAL：对数频率HAL
• I_Mean_RT
• I_Zscore：确定单词的难度。对于一个单词，此值在0和1之间波动，其中0为简单，1为困难
• I_SD
• Obs
• I_Mean_Accuracy：准确性，为响应值

使用决策树和随机森林的效果如下：

1
2
3
4
5
6
7
8
9
10
11

Train Data imported: 30457
Test Data imported: 9992
决策树算法(基于OpenCV实现)：
计算花费时长：186ms
平均误差：0.0239817

Train Data imported: 30457
Test Data imported: 9992
随机森林算法(基于OpenCV实现)：
计算花费时长：17378ms
平均误差：0.0212776

代码地址：Gitee - Random Trees