发布时间 : 星期二 文章完整word版,决策树算法总结,推荐文档更新完毕开始阅读
决策树
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