Random Forest 简单的实现

前言

本文仅记录Random Forest python代码实现。关于Random Forest 算法模型不做深入讨论。单颗树使用的是二叉搜索树。

代码地址

代码简单流程示意图：

核心思路说明：

1、数据加载和预处理

2、决策树一类算法，重要点在于树停止生长的条件，如下：(当不满足树停止生长的条件时，就可以生长，二者是互斥的)

      a>当前的结点的左或右子树不能为空

      b>当前结点中实例的个数不能小于初始化时结点实例个数的最小值(假设不做限制，取极限值为0时，自然得出矛盾点)

      c>当前树的深度不能超过初始化树的深度(防止过拟合，这是算法自身的精髓)

     (此处没有对每棵树使用的特征个数，树的个数做限制)

3、最优特征选择的指标是: 基尼指数(Gini_index)

核心代码说明：

  split()函数说明：

校验停止生长条件：

    是否属于同一个类(即只有一个结点)，

    当前树的深度，

    当前左右子树实例个数是否满足生长的条件。

如果上述条件没有一个满足则生长，调用get_split()函数，选取最优特征划分出左右子树，递归调用split()函数

def split(node, max_depth, min_size, n_features, depth):
    '''
    参数：结点，最大深度，结点个数的容忍度，特征的个数，深度
    '''
    left, right = node['groups']#获取左右子树
    del (node['groups'])

    if not left or not right:#如果左或右子树为空，则构造为叶子结点，返回是实例数最大的标记作为该结点所有实例的类，且停止生长
        node['left'] = node['right'] = to_terminal(left + right)
        return
    if depth >= max_depth:#如果当前深度大于最大深度则当前左右子树分别构造叶子结点，返回结点中实例最多的类作为该结点所有实例的类，且停止生长
        node['left'], node['right'] = to_terminal(left), to_terminal(right)
        return
    #分别判定左子树右子树实例个数是否小于结点的容忍度，如果小于则构造为叶子结点，停止生长，否则通过递归进行生长
    if len(left) <= min_size:
        node['left'] = to_terminal(left)
    else:
        node['left'] = get_split(left, n_features)
        split(node['left'], max_depth, min_size, n_features, depth + 1)
    if len(right) <= min_size:
        node['right'] = to_terminal(right)
    else:
        node['right'] = get_split(right, n_features)
        split(node['right'], max_depth, min_size, n_features, depth + 1)

get_split()函数说明：

    根据gini指数选取最优切分点。

    遍历训练当前树的所有特征的特征值(此处的特征非全量)，与数据集中所有样本对应的特征值进行比较划分左右子树

def get_split(dataset, n_features):
    '''

    :param dataset: 当前的数据集
    :param n_features: 特征的个数
    :return: 返回最优切分点的特征下标，特征值，左右子树
    '''
    class_values = list(set(row[-1] for row in dataset))
    b_index, b_value, b_score, b_groups = 999, 999, 999, None
    features = list()
    while len(features) < n_features:#随机选取特征
        index = randrange(len(dataset[0]) - 1)
        if index not in features:
            features.append(index)
    #遍历每个特征，遍历所有特征的特征值，计算以该特征值划分数据数据集下的基尼指数取并取gini最小的特征的特征值，作为最优切分点。
    for index in features:
        for row in dataset:
            groups = test_split(index, row[index], dataset)
            gini = gini_index(groups, class_values)
            if gini < b_score:
                b_index, b_value, b_score, b_groups = index, row[index], gini, groups
    #返回最优切分特征的下标，特征值，左右子树
    return {'index': b_index, 'value': b_value, 'groups': b_groups}

gini_index()函数说明：

基尼指数的计算。计算公式为：

                         

def gini_index(groups, class_values):
    gini = 0.0
    for class_value in class_values:
        for group in groups:
            size = len(group)
            if size == 0:
                continue
            proportion = [row[-1] for row in group].count(class_value) / float(size)
            gini += (proportion * (1.0 - proportion))
    return gini

bagging_predict()函数说明：

    遍历测试集中的样本，返回每个树的预测结果，最终选择预测结果列表中类别个数最多的类作为预测结果。

def bagging_predict(trees, row):
    '''
    :param trees: 使用训练数据集构造出来的所有的树
    :param row: 当前的样本
    :return: 返回最终的投票结果
    '''
    predictions = [print('predict  ',predict(tree, row)) for tree in trees]
    return max(set(predictions), key=predictions.count)

predict()函数说明：

    完成单个样本的预测。通过递归实现

def predict(node, row):
    '''
    :param node:当前单颗树的根结点
    :param row: 当前的样本
    :return: 该树的预测结果
    '''
    if row[node['index']] < node['value']:#取出当前样本下标为当前node存储idx的特征值并与当前node存储的idx的特征值进行比较，然后递归判断左右子树所属的类别
        if isinstance(node['left'], dict):
            return predict(node['left'], row)
        else:
            return node['left']
    else:
        if isinstance(node['right'], dict):#若右子树存在则为字典类型，否则为叶子结点，直接返回该结点
            return predict(node['right'], row)
        else:
            return node['right']

random_forest()函数说明：

    初始化训练、测试数据集，单个树的最大深度，单个结点可分裂最小实例数，最终模型中树的最大个数，特征个数。

def random_forest(train, test, max_depth, min_size, sample_size, n_trees, n_features):
    trees = list()
    for i in range(n_trees):
        sample = subsample(train, sample_size)
        tree = build_tree(sample, max_depth, min_size, n_features)
        trees.append(tree)
    predictions = [bagging_predict(trees, row) for row in test]
    return (predictions)

to_terminal() 函数说明：

    当不满足生长条件时，该结点即为叶子结点，该函数返回叶子结点的类别。

def to_terminal(group):
    '''
    当前子树为叶子结点，以实例的个数作为准则返回其所属类型。
    :param group: 
    :return: 
    '''
    outcomes = [row[-1] for row in group]
    return max(set(outcomes), key=outcomes.count)

总结：

      在实现RF之前我实现过决策树模型两者对比之下， 从基础模型的角度来看，决策树模型应当还是RF的核心，只是在单颗树中增加了“森林”中树的个数，参与训练的特征的个数，最终的类别的判定是由多个“专家”来决定。