随机森林算法

由前文讨论可知，我们在实现 RF 算法之前，需要先在决策树模型的生成过程中加一个参数、使得我们能够对特征选取加入随机性。这个过程相当平凡，下给出代码片段以进行粗略的说明。首先在CvDBase的fit方法中加入一个参数feature_bound：

def fit(self, x, y, sample_weight=None, alpha=None, eps=1e-8,
    cv_rate=0.2, train_only=False, feature_bound=None):

然后在同一个方法里面、把这个参数传给CvDNode的fit方法：

self.root.fit(x_train, y_train, _train_weights, feature_bound, eps)

在CvDNode的fit方法中，原始代码中有一个对可选特征空间的遍历：

for feat in self.feats:

根据参数feature_bound对它加入随机性：

feat_len = len(self.feats)
# 默认没有随机性
if feature_bound is None:
    indices = range(0, feat_len)
elif feature_bound == "log":
    # np.random.permutation(n)：将数组打乱后返回
    indices = np.random.permutation(feat_len)[:max(1, int(log2(feat_len)))]
else:
    indices = np.random.permutation(feat_len)[:feature_bound]
tmp_feats = [self.feats[i] for i in indices]
for feat in tmp_feats:

然后要在同一个方法里面、把feature_bound传给_gen_children方法，而在_gen_children中、再把feature_bound传给子节点的fit方法即可

以上所有实现细节可参见这里中的 Tree.py 和 Node.py

有了这些准备，我们就可以来看看 RF 的算法陈述了（以分类问题为例）：

1. 输入：训练数据集（包含 N 个数据）、决策树模型、迭代次数 M
2. 过程：
   1. 对$j=1,2,...,M$：
      1. 通过 Bootstrap 生成包含 N 个数据的数据集$D_k$
      2. 利用$D_j$和输入的决策树模型进行训练，注意不用对训练好的决策树模型$g_j$进行剪枝。同时需要注意的是，在训练决策树的过程中、每一步的生成都要对特征的选取加入随机性
   2. 对个体决策树进行简单组合。不妨用符号$\text{freq}(c_{k})$表示类别$c_{k}$在 M 个决策树模型的决策中出现的频率，那么： $$g\left( x \right) = \arg{\max_{c_k}{\text{freq}(c_{k})}}$$
3. 输出：最终分类器$g(x)$

从算法即可看出随机森林算法的实现（在实现好决策树模型后）是相当平凡的，需要额外做的工作只有定义一个能够计算上述算法第 2.2 步中$\arg{\max_{c_k}{freq(c_{k})}}$的函数而已：

# 导入我们自己实现的决策树模型
from c_CvDTree.Tree import *

class RandomForest(ClassifierBase):
    # 建立一个决策树字典，以便调用
    _cvd_trees = {
        "id3": ID3Tree,
        "c45": C45Tree,
        "cart": CartTree
    }

    def __init__(self):
        super(RandomForest, self).__init__()
        self._trees = []

    # 实现计算的函数
    @staticmethod
    def most_appearance(arr):
        u, c = np.unique(arr, return_counts=True)
        return u[np.argmax(c)]

    # 默认使用 10 棵 CART 树、默认 k = log(d)
    def fit(self, x, y, sample_weight=None, tree="cart", epoch=10, feature_bound="log",
            *args, **kwargs):
        x, y = np.atleast_2d(x), np.array(y)
        n_sample = len(y)
        for _ in range(epoch):
            tmp_tree = RandomForest._cvd_trees[tree](*args, **kwargs)
            _indices = np.random.randint(n_sample, size=n_sample)
            if sample_weight is None:
                _local_weight = None
            else:
                _local_weight = sample_weight[_indices]
                _local_weight /= _local_weight.sum()
            tmp_tree.fit(x[_indices], y[_indices],
                sample_weight=_local_weight, feature_bound=feature_bound)
            self._trees.append(deepcopy(tmp_tree))

    # 对个体决策树进行简单组合
    def predict(self, x):
        _matrix = np.array([_tree.predict(x) for _tree in self._trees]).T
        return np.array([RandomForest.most_appearance(rs) for rs in _matrix])

需要指出的是，most_appearance函数用到了 Numpy 中的unique方法、它和标准库collections中的Counter具有差不多的用法。举个小栗子：

x = np.array([i for i in "dcbabcd"])
np.unique(x, return_counts=True)

这两行代码会返回：

(
    array(['a', 'b', 'c', 'd'], dtype='<U1'),
    array([1, 2, 2, 2], dtype=int64)
)

换句话说，unique方法能够提取出一个 Numpy 数组中出现过的元素并对它们计数、同时输出的 Numpy 数组是经过排序的

以上就完成了一个简易可行的随机森林模型的实现，我们可以把对随机森林模型的评估与对 AdaBoost 的评估放在一起进行以便于对比、这里就先按下不表