python程序实现rep后剪枝算法

背景

在使用决策树模型时&＃xff0c;如果训练集中的样本数很多&＃xff0c;则会使得生成的决策树过于庞大&＃xff0c;即分化出了很多的枝节。这时会产生过拟合问题&＃xff0c;也就是在模型在训练集上的表现效果良好&＃xff0c;而在测试集的效果却很差。因此在生成一棵决策树之后&＃xff0c;需要对它进行必要的剪枝&＃xff0c;从而提高它的泛化能力。本文将讲述后剪枝算法——REP方法。

原理

剪枝是指将决策树的一些枝节去掉&＃xff0c;将中间节点变成叶子节点&＃xff0c;该叶子节点的预测值便是该分组训练样本$y$值的均值。剪枝算法分为预剪枝和后剪枝&＃xff0c;预剪枝是在决策树生成的过程中同步进行&＃xff0c;而后剪枝是在决策树生成完之后再剪枝。

REP方法也称为错误率降低剪枝&＃xff0c;它是一类最基础、最简单的后剪枝算法&＃xff0c;是其他剪枝算法的基础。主要过程是将训练集分为两个集合N1N_1N1​和N2N_2N2​&＃xff0c;可以称为训练集中的训练集和训练集中的验证集。N1N_1N1​用来生成决策树&＃xff0c;N2N_2N2​用来验证剪枝前后的模型效果。具体是先用N1N_1N1​来生成决策树&＃xff0c;然后自底向上遍历所有中间节点&＃xff0c;对于每个中间节点&＃xff0c;比较剪枝前后的两棵决策树在验证集N2N_2N2​上的效果&＃xff0c;这个效果体现在N2N_2N2​通过两棵决策树得到的预测值与原始实际值的误差平方和&＃xff0c;若剪枝后的误差平方和更小&＃xff0c;则对决策树进行剪枝&＃xff0c;反之则不进行剪枝。

例子

假设通过对数据集N1N_1N1​进行训练&＃xff0c;得到了如下的决策树

现在要自底向上进行剪枝&＃xff0c;对象是中间节点&＃xff0c;对应到图中依次是节点5、2、3。对于节点5&＃xff0c;先将它的左右枝8和9剪掉&＃xff0c;得到剪枝前和剪枝后的两棵树

将数据集N2N_2N2​的特征$x$分别代入这两棵树&＃xff0c;得到两组预测值&＃xff0c;然后通过比较两组数据的误差平方和来决策是否进行剪枝。之后再考虑节点2&＃xff0c;最后考虑节点3。

程序实现

重新定义树结构

为了方便处理不同节点间的调用&＃xff0c;CART回归树的树模型不再用字典进行存储&＃xff0c;而改用自定义的类对象&＃xff08;参考leetcode中的树节点&＃xff09;&＃xff0c;每个节点可以通过成员变量来调用分裂出来的左右节点。

class TreeNode:def __init__(self, val, fea_name&＃61;None, fea_c&＃61;None):self.left &＃61; Noneself.right &＃61; Noneself.val &＃61; round(val,2)self.fea_name &＃61; fea_name self.fea_c &＃61; fea_c if fea_c is None else round(fea_c,2)


变量$val$是指当前节点数据集的$y$值的均值&＃xff0c;若当前节点是叶子节点&＃xff0c;则该变量代表这种分支的预测值&＃xff0c;若是中间节点&＃xff0c;则可以表示为对该节点进行剪枝后的节点预测值。

生成剪枝后的子树

def sub_tree(tree, num): # 返回后序剪枝得到的子树stack &＃61; [(False, tree)]while stack:flag, t &＃61; stack.pop()if not t:continueif flag:if t.left or t.right:if num&＃61;&＃61;0:t.left &＃61; Nonet.right &＃61; Nonereturn treeelse:num -&＃61; 1else:stack.append((True, t))stack.append((False, t.right))stack.append((False, t.left))return tree


采用后序遍历的方式来搜索中间节点&＃xff0c;参数$num$是为了控制对应序号的中间节点&＃xff0c;因为并不是剪去每个中间节点都能提高性能&＃xff0c;通过$num$可以避开不想剪去的中间节点。

计算中间节点的个数

def mid_leaf_num(tree): if not tree or (not tree.left and not tree.right):return 0return 1 &＃43; mid_leaf_num(tree.left) &＃43; mid_leaf_num(tree.right)


效果比较函数

def ifmore(self, temp_tree, test_x, test_y):orig_ &＃61; []temp_ &＃61; []for i in range(len(test_x)):orig_.append(self.check(self.tree, test_x[i]))temp_.append(self.check(temp_tree, test_x[i]))orig_sum &＃61; sum(np.power(np.array(orig_)-test_y, 2))temp_sum &＃61; sum(np.power(np.array(temp_)-test_y, 2))if orig_sum>temp_sum: # and (orig_sum-temp_sum)/orig_sum>0.0001:self.tree &＃61; temp_treereturn Trueelse:return False


REP剪枝函数

def prune_tree(self, test_x, test_y):mid_num &＃61; mid_leaf_num(self.tree)i &＃61; 0while i<mid_num: temp_tree &＃61; sub_tree(self.tree, i)if self.ifmore(temp_tree, test_x, test_y):i &＃61; 0mid_num -&＃61; 1else:i &＃43;&＃61; 1


实例化演示

X,y &＃61; make_regression(n_samples&＃61;1000, n_features&＃61;4, noise&＃61;0.1)
X_name &＃61; np.array(list(&＃39;abcd&＃39;))
clf &＃61; Tree_Regress()
train_x, test_x, train_y, test_y &＃61; train_test_split(X, y, test_size&＃61;0.30)
train_size &＃61; len(train_x)//4
train_test_x, train_test_y &＃61; train_x[:train_size], train_y[:train_size]
train_train_x, train_train_y &＃61; train_x[train_size:], train_y[train_size:]
print(&＃39;不剪枝&＃39;)
clf.fit(train_x, train_y, X_name)
predict_y &＃61; clf.predict(test_x)
pre_error &＃61; sum(np.power(test_y-predict_y,2))
print(&＃39;误差为&＃xff1a;&＃39;, pre_error,&＃39; 节点数&＃xff1a;&＃39;, clf.node_num())print(&＃39;有剪枝&＃39;)
clf.fit(train_train_x, train_train_y, X_name)
clf.prune_tree(train_test_x, train_test_y)
predict_y &＃61; clf.predict(test_x)
pre_error &＃61; sum(np.power(test_y-predict_y,2))
print(&＃39;误差为&＃xff1a;&＃39;, pre_error,&＃39; 节点数&＃xff1a;&＃39;, clf.node_num())# 不剪枝
# 误差为&＃xff1a; 9860.41223121167 节点数&＃xff1a; 249
# 有剪枝
# 误差为&＃xff1a; 6892.04066950184 节点数&＃xff1a; 33


在对模型进行后剪枝之后&＃xff0c;模型的泛化能力有所提升。

不足

REP方法虽然在一定程度上简化了决策树&＃xff0c;提高了模型的性能&＃xff0c;但在有些情况下反而会造成相反的结果&＃xff0c;使得模型表现更差。我试了几个不同的数据集&＃xff0c;发现效果其实不是很好&＃xff0c;可能是这个方法考虑到的东西比较少&＃xff0c;它单单考虑到了模型拟合的误差平方和&＃xff0c;却没考虑生成的节点个数&＃xff0c;粗暴地将影响模型性能的枝节都剪去&＃xff0c;使得模型太过简单。另外&＃xff0c;该方法的计算开销是很大的&＃xff0c;需要遍历搜索两次中间节点。