完整word版,决策树算法总结

1、决策树研发二部武汉中原电子信息有限公司文件状态：草稿正式发布正在修改文件标识：当前版本：1.0作者：张宏超完成日期：2019年3月8日目录 TOC o 1-5 h z HYPERLINK l bookmark13 o Current Document 算法介绍1 HYPERLINK l bookmark19 o Current Document 分支节点选取1 HYPERLINK l bookmark25 o Current Document 构建树3剪枝10 HYPERLINK l bookmark55 o Current Document sk-learn 中的使用12sk-learn中源

2、码分析131.算法介绍决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作 为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要 包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的， 可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。 CART也是针对ID3优化出现的，既可以做分类，可以做回归。决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依 据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分 支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理

3、，也就是剪枝。 这是我们之前写if语句时不会考虑的问题。决策树算法主要分为以下3个步骤：分支节点选取构建树剪枝1.1.分支节点选取分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须 要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系 数。熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越 多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵 值就比A班大，也就是B班信息越混乱。Entropy = -V p. - logtp)基尼系数：同上，也可以作为信息混乱程度的衡量指标。IGini = 1 - P.1有了量化指标后，就可

4、以衡量使用某个分支条件前后，信息混乱程 度的收敛效果了。使用分支前的混乱程度，减去分支后的混乱程度， 结果越大，表示效果越好 圻计算熵值def entropy(dataSet):tNum = len(dataSet)print(tNum)#用来保存标签对应的个数的，比如男：6,女：5labels = for node in dataSet:curL = node-1 #获取标签if curL not in labels.keys():labelscurL = 0#如果没有记录过该种标签，就记录并初始化为labelscurL += 1#将标签记录个数加1毗时labels中保存了所有标签和对应的个

5、数res = 0圻计算公式为p*logp p为标签出现概率for node in labels:p = float(labelsnode) / tNumres -= p * log(p, 2)return res圻计算基尼系数def gini(dataSet):tNum = len(dataSet)print(tNum)#用来保存标签对应的个数的，比如男：6,女：5labels = for node in dataSet:curL = node-1 # 获取标签if curL not in labels.keys():labelscurL = 0 #如果没有记录过该种标签，就记录并初始化为 l

6、abelscurL += 1 #将标签记录个数加1#此时labels中保存了所有标签和对应的个数res = 1#计算公式为p*logp p为标签出现概率for node in labels:p = float(labelsnode) / tNumres -= p * preturn res1.2.构建树ID3算法：利用信息熵增益，决定选取哪个特征作为分支节点。分支前的总样本 熵值-分支后的熵值总和=信息熵增益。T1 的信息熵增益：1 - 13/20*0.961 - 7/20*0.863 = 0.073T2 的信息熵增益：1 - 12/20*0.812 - 8/20*0.544 = 0.295所

7、以使用T2作为分支特征更优。ID3算法建树：依据前面的逻辑，递归寻找最优分支节点，直到下面情况结束叶节点已经属于同一标签虽然叶节点不属于同一标签，但是特征已经用完了熵小于预先设置的阈值树的深度达到了预先设置的阈值ID3算法的不足:取值多的特征比取值少的特征更容易被选取。不包含剪枝操作，过拟合严重特征取值必须是离散的，或者有限的区间的。于是有了改进算法C4.5C4.5算法：基于ID3算法进行了改进，首先，针对ID3的不足1，采用信息增益 率取代ID3中使用信息增益而造成的偏向于选取取值较多的特征作为分裂点的问 题。针对ID3的不足2,采用剪枝操作，缓解过拟合问题。针对ID3的不足3,采 用将连续

8、值先排列，然后逐个尝试分裂，找到连续值中的最佳分裂点。信息增益率的计算：先计算信息增益，然后除以spliteInfo。spliteInfo为分裂后的 子集合的函数，假设分裂后的子集合个数为subl和sub2, total为分裂前的个数。spliteInfo = -subl / total * log(sub1 / total) - sub2 / total * log(sub2 / total)#index:特征序号#value:特征值#该方法表示将index对应特征的值为value的集合返回，返回集合中不包含index对应 的特征def spliteDataSet(dataSet, inde

9、x, value):newDataSet =for node in dataSet:if nodeindex = value:#0,index)列 的数据newData = node:index#index+1,最后列的数据newData.extend(nodeindex + 1:) newDataSet.append(newData) return newDataSet;#选择最优分裂项def chooseBestFeature(dataSet):#特征个数featureNum = len(dataSet0) - 1#计算整体样本的熵值baseEntropy = entropy(dataSe

10、t)武汉中原电子信息有限公司4print(baseEntropy = %f”%(baseEntropy) #保存最大的信息增益率 maxInfoGainRatio =0.0 bestFeatureId = -1for i in range(featureNum):#获取特征所有可能的值 featureValues = for node in dataSet:featureValues.append(nodei) print(featureValues) #将特征值去除重复 uniqueFeatureValues = set (featureValues) print(uniqueFeature

11、Values) #按照1特征分裂之后的熵值 newEntropy =0.0 #分裂信息 spliteInfo =0.0#按照1所表示的特征，开始分裂数据集 for value in uniqueFeatureValues: #当i属性等于value时的分裂结果 subDataSet = spliteDataSet(dataSet, i, value) print(subDataSet) 圻计算占比p = float(len(subDataSet) / float(len(dataSet) newEntropy += p * entropy(subDataSet) spliteInfo += -

12、p * log(p, 2)#计算信息增益infoGain = baseEntropy - newEntropy 圻计算信息增益率 if spliteInfo = 0:continueinfoGainRatio = infoGain / spliteInfo if infoGainRatio maxInfoGainRatio: maxInfoGainRatio = infoGainRatio bestFeatureId = ireturn bestFeatureIdC4.5算法的不足：如果存在连续值的特征需要做排序等处理，计算比较耗时只能用于分类使用于是有了 CART算法CART算法：也是基于I

13、D3算法优化而来，支持分类和回归，使用基尼系数（分类 树）或者均方差（回归树）替代熵的作用，减少运算难度。使用二叉树代替多叉 树建模，降低复杂度。基尼系数的计算：均方差的计算:计算举例，假设有如下数据源看电视 时间婚姻情 况3未婚4未婚2已婚5已婚2.5已婚3.5未婚职业年龄学生12学生18老师26上班族47上班族36老师294已婚学生21如果将婚否作为标签，该问题是一个分类问题，所以使用基尼系数 假设使用职业作为特征分支，对于看电视和年龄，都是连续数据，需要按照C4.5的算法排序后处理，这里先分析简单的按照职业开始划分。又因为，CART算法的建模是二叉树，所以针对职业来说，有以下组合，学生|

14、非学生，老师|非老师，上班族|非上班族到底怎么划分，就要通过基尼系数来判断了。&就汨:一耻粮畚牲畚牲1S4*学生，胜瞬,是皿拙16-上腿虾2.5-是，1SS-J&gini = 3 / 7 * (1 - 2 / 3 * 2 /3 - 1 / 3 * 1 / 3) + 4 / 7 * (1-3 / 4 * 3 / 4 - 1 / 4 * 1 / 4) = 0.4酒酣Eft藉璇靴告酬3S 注是杏己抢*私n-牲A思上瓠弟r 2r上曜.1r jfr 14gini = 2 / 7 *(1 - 1 / 2 * 1 / 2 - 1 / 2 * 1 / 2) + 5 / 7 *(1 - 2 / 5 * 2 /

15、5 - 3 / 5 * 3 / 5)= 0.49年蜘学18-是C圭1低g是gini = 2 / 7 * (1 - 1 * 1) + 5 / 7 * (1 - 3 / 5 * 3 / 5 - 2 /5 * 2 / 5) = 0.34所以，如果选择职业来划分，那么首先应该按照上班族|非上班族划分如果将年龄作为标签，该问题是一个回归问题，所以使用均方差 同样，先考虑使用职业来划分我是否己临辙尊牲111-*去学生慎醐1A施一是上册套各折4恚学生；21- 1我岫12-学生-18牝学客是皿.bIA是4A2S-gIS私Sff.母mean =开方(12 * 12 + 18 * 18 + 21 * 21 - 3

16、 * 17 * 17) + 开方(26 * 26 + 47 * 47 + 36* 36 + 29 * 29 - 5 * 32.5 * 32.5) = 34.71其他情况略。可以看到选择分裂属性这一步骤会比较麻烦，首先要遍历所有特征， 找到每一个特征的最优分裂方法，然后在选择最优的分裂特征。功能树结构特征选取连续值处理缺失值处理剪枝ID3分类多叉信息增益不支持不支持不支持C4.5分类多叉信息增益率支持支持支持CART分类/回归二叉基尼系数（分 类），均方差（回 归）支持支持支持1.3.剪枝CCP (Cost Complexity Pruning)代价复杂性剪枝法(CART 常用)REP (Red

17、uced Error Pruning)错误降低剪枝法PEP (Pessimistic Error Pruning)悲观错误剪枝法(C4.5 使用)MEP (Minimum Error Pruning)最小错误剪枝法这里以CCP为例讲解其原理CCP选择节点表面误差率增益值最小的非叶子节点，删除该节点的子节点。若多 个非叶子节点的表面误差率增益值相同，则选择子节点最多的非叶子节点进行裁 剪。表面误差率增益值计算：|厂质)-叫)-1R(t)表示非叶子节点的错误率，比如，总样本20，在A节点上a类5个，b类2 个，所以可以认为A节点代表的是a类，那么错误率就是2 / 7 * 7 / 20R(T )表示

18、叶子节点的错误率累积和N(T)表示叶子节点的个数剪枝步骤：1.构建子树序列2.找到最优子树，作为我们的决策树(交叉验证等)举例: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.0125t5: (4/10 * 10/80 - 0 - 0) / (2 - 1) = 0.05t2: (10/60 * 60/80 - 1/45 * 45/80 - 2/5 * 5/80 - 0 -

19、0) / (4 - 1) = 0.0292t3: 0.0375因此得到第 1 颗子树：T0 = t4（0.0125），t5（0.05），t2（0.0292），t3（0.0375）比较发现可以将t4裁剪掉得到第2颗子树t5: 0.05 t3: 0.0375 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 l

20、oad_irisfrom sklearn import treeimport pydotplusimport graphviziris = 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(iris.pdf)主要分析tree的相关函数代码，使用pycharm下载skl

21、earn包中tree文件， 引用了_tree.pxd，pxd相当于头文件，其实现在tree.pyd中，pyd是加密文件，无 法查看。从github上下载源码中有_tree.pyx相当于c文件，因此可以查看。.pxd:相当于.h.pyx:相当于.c.pyd:相当于dlltree.DecisionTreeClassifier()创建分类决策树对象DecisionTreeClassifier 继承 BaseDecisionTreeclf.fit(iris.data, iris.target) 建树DecisionTreeClassifier 直接使用了父类 BaseDecisionTree 的方法

22、super().fit(X, y,sample_weight=sample_weight,check_input=check_input,X_idx_sorted=X_idx_sorted)查看DecisionTreeClassifier的fit，学习建树过程代码前面是对参数的校验之类的工作4 Build tree criterion = self . criterion, if not isirstance(criterion, Criterion): i ff Lest ion : _(fcriterion = CRITERIA_3LFlelz . criterion. (self .n_ou.tpiu.ts_, J 一 -self .r. classes )else:cr