决策树

1.3. 剪枝

CCP（Cost Complexity Pruning）代价复杂性剪枝法（CART常用） REP（Reduced Error Pruning）错误降低剪枝法

PEP（Pessimistic Error Pruning）悲观错误剪枝法（C4.5使用） MEP（Minimum Error Pruning）最小错误剪枝法 这里以CCP为例讲解其原理

CCP选择节点表面误差率增益值最小的非叶子节点，删除该节点的子节点。若多个非叶子节点的表面误差率增益值相同，则选择子节点最多的非叶子节点进行裁剪。

表面误差率增益值计算：

R(t)表示非叶子节点的错误率，比如，总样本20，在A节点上a类5个，b类2个，所以可以认为A节点代表的是a类，那么错误率就是2 / 7 * 7 / 20 R(T)表示叶子节点的错误率累积和 N(T)表示叶子节点的个数 剪枝步骤： 1． 构建子树序列

2． 找到最优子树，作为我们的决策树（交叉验证等）

武汉中原电子信息有限公司

10

决策树

举例：

t1是根节点

t2，t3，t4，t5是非叶子节点 t6，t7，t8，t9，t10，t11是叶子节点 首先我们计算所有非叶子节点误差率增益值

t4: (4/50 * 50/80 – 1/45 * 45/80 – 2/5 * 5/80) / (2 – 1) = 0.0125 t5: (4/10 * 10/80 – 0 - 0) / (2 - 1) = 0.05

t2: (10/60 * 60/80 – 1/45 * 45/80 – 2/5 * 5/80 – 0 - 0) / (4 - 1) = 0.0292 t3: 0.0375

因此得到第1颗子树：T0 = t4（0.0125），t5（0.05），t2（0.0292），t3（0.0375） 比较发现可以将t4裁剪掉 得到第2颗子树

t5: 0.05 t3: 0.0375

武汉中原电子信息有限公司

11

决策树

t2: (10/60 * 60/80 – 4/50 * 50/80 – 0 - 0) / (3 -1) = 0.0375 此时t2与t3相同，那么裁剪叶子节点较多的，因此t2被裁剪 得到第3颗树

然后对上面3颗子树进行验证，找到效果最后的作为剪枝之后的决策树。

2. sk-learn中的使用

from sklearn.datasets import load_iris from sklearn import tree import pydotplus import graphviz

iris = load_iris()

clf = tree.DecisionTreeClassifier() clf.fit(iris.data, iris.target)

dot_data = tree.export_graphviz(clf, out_file=None) graph = pydotplus.graph_from_dot_data(dot_data) graph.write_pdf(\)

武汉中原电子信息有限公司

12

决策树

3. sk-learn中源码分析

主要分析tree的相关函数代码，使用pycharm下载sklearn包中tree文件，引用了_tree.pxd，pxd相当于头文件，其实现在_tree.pyd中，pyd是加密文件，无法查看。从github上下载源码中有_tree.pyx相当于c文件，因此可以查看。 .pxd:相当于.h .pyx:相当于.c .pyd:相当于dll

tree.DecisionTreeClassifier() 创建分类决策树对象

DecisionTreeClassifier继承BaseDecisionTree

clf.fit(iris.data, iris.target) 建树

DecisionTreeClassifier直接使用了父类BaseDecisionTree的方法 super().fit( X, y,

武汉中原电子信息有限公司

13