随机森林算法（RF）原理及Python实现（超详细）

随机森林（Random Forest，RF）算法是一种重要的基于 Bagging 的集成学习方法，加州大学伯克利分校的 Breiman Leo 和 Adele Cutler 在 2001 年发表的论文中提到了 Random Forest 算法，随机森林算法可以用来做分类、回归等问题，在本章节中主要介绍随机森林在分类问题中的应用。

随机森林算法是由一系列的决策树组成，它通过自助法（Bootstrap）重采样技术，从原始训练样本集中有放回地重复随机抽取 m 个样本，生成新的训练样本集合，然后根据自助样本集生成 k 个分类树组成随机森林，新数据的分类结果按分类树投票多少形成的分数而定。

该算法实质是对决策树算法的一种改进，将多个决策树合并在一起，每棵树的建立依赖于一个独立抽取的样品，森林中的每棵树具有相同的分布，分类误差取决于每一棵树的分类能力和它们之间的相关性。特征选择采用随机的方法去分裂每一个节点，然后比较不同情况下产生的误差。能够检测到的内在估计误差、分类能力和相关性决定选择特征的数目。单棵树的分类能力可能很小，但在随机产生大量的决策树后，一个测试样品可以通过统计每一棵树的分类结果，从面选择最可能的分类。

随机森林算法流程

随机森林算法是通过训练多个决策树，生成模型，然后综合利用多个决策树进行分类。随机森林算法只需要两个参数：构建的决策树的个数 ntree ，在决策树的每个节点进行分裂时需要考虑的输入特征的个数 k，通常 k 可以取为 log2n，其中 n 表示的是原数据集中特征的个数。

对于单棵决策树的构建，可以分为如下的步骤：

• 假设训练样本的个数为 m，则对于每一棵决策树的输入样本的个数都为 m，且这 m 个样本是通过从训练集中有放回地随机抽取得到的。
• 假设训练样本特征的个数为 n，对于每一棵决策树的样本特征是从该 n 个特征中随机挑选 k 个，然后从这 k 个输入特征里选择一个最好的进行分裂。
• 每棵树都一直这样分裂下去，直到该节点的所有训练样例都属于同一类。在决策树分裂过程中不需要剪枝。

根据上述的过程，我们利用 Python 实现随机森林的训练过程，在实现随机森林的训练过程时，需要使用到 numpy 中的函数，因此需要导入 numpy 模块：

import numpy as np

随机森林的构建过程如下代码所示。

def random_forest_training(data_train, trees_num):
    '''构建随机森林
    input:  data_train(list):训练数据
            trees_num(int):分类树的个数
    output: trees_result(list):每一棵树的最好划分
            trees_feature(list):每一棵树中对原始特征的选择
    '''
    trees_result = []  # 构建好每一棵树的最好划分
    trees_feature = []
    n = np.shape(data_train)[1]  # 样本的维数
    if n > 2:
        k = int(log(n - 1, 2)) + 1 # 设置特征的个数
    else:
        k = 1
    # 开始构建每一棵树
    for i in xrange(trees_num):
        # 1、随机选择m个样本, k个特征
        data_samples, feature = choose_samples(data_train, k)
        # 2、构建每一棵分类树
        tree = build_tree(data_samples)
        # 3、保存训练好的分类树
        trees_result.append(tree)
        # 4、保存好该分类树使用到的特征
        trees_feature.append(feature)
   
    return trees_result, trees_feature

程序中，函数 random_forest_training 用于构建具有多棵树的随机森林，其中函数的输入 data_train 表示的是训练数据，trees_num 表示的是在随机森林中分类树的数量。在随机森林算法中，随机选择的特征的个数通常为 k=log2n，其中 n 表示的是原数据集中特征的个数；在程序代码中，使用到了 math 模块中的 log 函数，因此，需要导入 log 函数：

from math import log

当随机森林中分类树的数量 trees_num 和每一棵树的特征的个数 k 设置完成后，便可以利用训练样本训练随机森林中的每一棵树。在训练每一棵树的过程中，主要有如下几步：

1) 从样本集中随机选择 m 个样本中的 k 个特征，其中，m 为原始数据集中的样本个数，函数 choose_sample 的具体实现为：

def choose_samples(data, k):
    '''
    input:  data(list):原始数据集
            k(int):选择特征的个数
    output: data_samples(list):被选择出来的样本
            feature(list):被选择的特征index
    '''
    m, n = np.shape(data)  # 样本的个数和样本特征的个数
    # 1、选择出k个特征的index
    feature = []
    for j in xrange(k):
        feature.append(rd.randint(0, n - 2))  # n-1列是标签
    # 2、选择出m个样本的index
    index = []
    for i in xrange(m):
        index.append(rd.randint(0, m - 1))
    # 3、从data中选择出m个样本的k个特征，组成数据集data_samples
    data_samples = []
    for i in xrange(m):
        data_tmp = []
        for fea in feature:
            data_tmp.append(data[index[i]][fea])
        data_tmp.append(data[index[i]][-1])
        data_samples.append(data_tmp)
    return data_samples, feature

choose_samples 函数的功能是从原始的训练样本 data 中随机选择出 m 个样本，这里的随机选择是指有放回地选择，样本之间是可以重复的，同时这 m 个样本中只保留k维特征，用来组成新的样本 data_sample，同时为了能够还原选择出的样本特征，需要保存选择出的特征 feature。

在随机选择的过程中，使用到了 random 模块中的 randint 函数，因此需要导入 random 模块：

import random as rd

2) 利用选择好的只包含部分特征的数据集 data_sample 构建分类树模型，函数 build_tree 的具体实现为下所示：

def build_tree(data):
    '''构建树
    input:  data(list):训练样本
    output: node:树的根结点
    '''
    # 构建决策树，函数返回该决策树的根节点
    if len(data) == 0:
        return node()
   
    # 1、计算当前的Gini指数
    currentGini = cal_gini_index(data)
   
    bestGain = 0.0
    bestCriteria = None  # 存储最佳切分属性以及最佳切分点
    bestSets = None  # 存储切分后的两个数据集
   
    feature_num = len(data[0]) - 1  # 样本中特征的个数
    # 2、找到最好的划分
    for fea in range(0, feature_num):
        # 2.1、取得fea特征处所有可能的取值
        feature_values = {}  # 在fea位置处可能的取值
        for sample in data:  # 对每一个样本
            feature_values[sample[fea]] = 1  # 存储特征fea处所有可能的取值
       
        # 2.2、针对每一个可能的取值，尝试将数据集划分，并计算Gini指数
        for value in feature_values.keys():  # 遍历该属性的所有切分点
            # 2.2.1、 根据fea特征中的值value将数据集划分成左右子树
            (set_1, set_2) = split_tree(data, fea, value)
            # 2.2.2、计算当前的Gini指数
            nowGini = float(len(set_1) * cal_gini_index(set_1) + 
                             len(set_2) * cal_gini_index(set_2)) / len(data)
            # 2.2.3、计算Gini指数的增加量
            gain = currentGini - nowGini
            # 2.2.4、判断此划分是否比当前的划分更好
            if gain > bestGain and len(set_1) > 0 and len(set_2) > 0:
                bestGain = gain
                bestCriteria = (fea, value)
                bestSets = (set_1, set_2)
   
    # 3、判断划分是否结束
    if bestGain > 0:
        right = build_tree(bestSets[0])
        left = build_tree(bestSets[1])
        return node(fea=bestCriteria[0], value=bestCriteria[1], 
                    right=right, left=left)
    else:
        return node(results=label_uniq_cnt(data))  # 返回当前的类别标签作为最终的类别标签

3) 当训练好 CART 树后，保存训练好的分类树模型。

4) 保存在该分类树下选择的特征 feature，这一步主要是保证对新的数据集进行预测时，能够从中选择出特征。