完整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