随机森林算法是一种精度较高，又不用过多操心过拟合问题的模型。

然而，随机森林是一种决策树模型，初学者往往难以理解决策树模型是如何实现回归功能的。

本文将利用numpy，从头开始搭建一个回归树。

• 评价标准

  回归树与分类树同样采取数据分割的方式进行拟合，分类树的常用指标有信息增益、信息增益率和基尼系数等；

  回归树常使用绝对平均方差（MSE）和绝对平均误差（MAE），本文中将使用MAE。

def MAE(set):
    y = set['y'].values
    return np.mean([abs(yi-np.mean(y)) for yi in y])

• 定义树节点

  对于决策树中的叶节点，包含如下属性：

  1. 该叶节点中包含的数据集合；
  2. 该叶节点的平均预测值（Label）；
  3. 该叶节点的mae

  而在非子节点中，包含如下属性：

  1. 分割特征；
  2. 分割特征值；
  3. 真子树（满足条件的数据进入真子树）；
  4. 假子树（不满足条件的数据进入假子树）。
  5. mae

所有节点都带有mae是为了方便剪枝（后剪枝），但是随机森林算法因为本身就有防止过拟合的能力，所以一般都会选择让树自由生长。

class tree_node(object):
    def __init__(self,set = None,mae = None, col = None,value = None, result = None,tb = None, fb = None):
        self.set = set
        self.mae = mae
        self.col = col
        self.value = value
        self.result = result
        self.tb = tb
        self.fb = fb

• 建立树

依次遍历所有的特征及其取值，寻找使得分割后的加权mae最小的分割方式，将数据分割。

然后再对分割出来的两个子树分别执行同样的操作，直到数据集无法再分割。

def build_tree(data):
    cols = data.drop('y',axis = 1).columns
    t = tree_node()
    #数据集
    t.set = data
    #该节点的mae，同样只适用于叶节点，如果节点被划分则归零
    t.mae = MAE(data)
    delta_mae = 0
    for col in cols:#遍历特征
        for value in data[col]:#遍历所有特征取值，对于大的数据集可以使用set()或者转换为字典来去重
            set1 = data[data[col]>=value]
            set2 = data[data[col]<value]
            if len(set1)>0 and len(set2)>0:
                new_mae = (MAE(set1)*len(set1) + MAE(set2)*len(set2))/len(data)
                new_delta_mae = t.mae - new_mae
                if delta_mae < new_delta_mae:
                    delta_mae = new_delta_mae
                    t.mae = new_mae
                    t.col = col
                    t.value = value
    #判断是否能够进行划分
    if t.col != None:
        t_tree = build_tree(data[data[t.col]>=t.value])
        f_tree = build_tree(data[data[t.col]<t.value])
        return tree_node(col = t.col,value = t.value,tb = t_tree,fb = f_tree)
    else:
        #该节点的平均值，只适用于叶节点    
        t.result = data['y'].mean()
        return tree_node(result = t.result,set = t.set)

• 预测数据

预测过程较为简单，只需要从根节点开始，依次判断数据是否满足各节点的条件便可。

def classify(row,tree):
    #样本单个单个地通过决策树
    #如果是叶节点
    if tree.result != None:
        return tree.result
    else:
        if row[tree.col] >= tree.value:
            branch = tree.tb
        elif row[tree.col] < tree.value:
            branch = tree.fb
        return classify(row,branch)

• 生成测试数据

data = pd.DataFrame({'x1':[1,2,3,4],'x2':[2,3,4,3],'y':[1,3,5,3]})

test_data = pd.DataFrame({
    'x1':[1,2],
    'x2':[2,2],
    'y':[1,3]
})

• 训练+ 预测

tree = build_tree(data)
print(tree)
for i,row in test_data.drop('y',axis=1).iterrows():
    print(classify(row,tree))

参考：
https://zhuanlan.zhihu.com/p/20794583