决策树算法总结.docx

《决策树算法总结.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、决策树决策树研发二部武汉中原电子信息有限公司决策树文件状态：[]草稿[]正式发布[]正在修改文件标识：当前版本：1.0作者：张宏超完成日期：2019年3月8日II决策树目录1.算法介绍11.1.分支节点选取11.2.构建树31.3.剪枝102.sk-learn中的使用123.sk-learn中源码分析13II决策树1.算法介绍决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算

2、法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对ID3优化出现的，既可以做分类，可以做回归。决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。决策树算法主要分为以下3个步骤：1.分支节点选取2.构建树3.剪枝1.1.分支节点选取分支节点选取，也就是寻找分

3、支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。基尼系数：同上，也可以作为信息混乱程度的衡量指标。武汉中原电子信息有限公司15决策树有了量化指标后，就可以衡量使用某个分支条件前后，信息混乱程度的收敛效果了。使用分支前的混乱程度，减去分支后的混乱程度，结果越大，表示效果越好。#计算熵值def

4、entropy(dataSet):tNum=len(dataSet)print(tNum)#用来保存标签对应的个数的，比如,男：6，女：5labels={}fornodeindataSet:curL=node[-1]#获取标签ifcurLnotinlabels.keys():labels[curL]=0#如果没有记录过该种标签，就记录并初始化为0labels[curL]+=1#将标签记录个数加1#此时labels中保存了所有标签和对应的个数res=0#计算公式为-p*logp，p为标签出现概率fornodeinlabels:

5、p=float(labels[node])/tNumres-=p*log(p,2)returnres#计算基尼系数defgini(dataSet):tNum=len(dataSet)print(tNum)#用来保存标签对应的个数的，比如,男：6，女：5labels={}fornodeindataSet:curL=node[-1]#获取标签ifcurLnotinlabels.keys():labels[curL]=0#如果没有记录过该种标签，就记录并初始化为0labels[curL]+=1#将标签记录个数加1#此时labels

6、中保存了所有标签和对应的个数res=1武汉中原电子信息有限公司15决策树#计算公式为-p*logp，p为标签出现概率fornodeinlabels:p=float(labels[node])/tNumres-=p*preturnres1.1.构建树ID3算法：利用信息熵增益，决定选取哪个特征作为分支节点。分支前的总样本熵值-分支后的熵值总和=信息熵增益。A：10个B：10个特征T1A：5个B：8个A：5个B：2个A：10个B：10个特征T2A：3个B：9个A：7个B：1个T1的信息熵增益：1–13/20*0.961-7/20

7、*0.863=0.073T2的信息熵增益：1–12/20*0.812-8/20*0.544=0.295所以使用T2作为分支特征更优。ID3算法建树：依据前面的逻辑，递归寻找最优分支节点，直到下面情况结束1.叶节点已经属于同一标签2.虽然叶节点不属于同一标签，但是特征已经用完了3.熵小于预先设置的阈值4.树的深度达到了预先设置的阈值武汉中原电子信息有限公司15决策树ID3算法的不足：1.取值多的特征比取值少的特征更容易被选取。2.不包含剪枝操作，过拟合严重3.特征取值必须是离散的，或者有限的区间的。于是有了改进算法C4.5C4

8、.5算法：基于ID3算法进行了改进，首先，针对ID3的不足1，采用信息增益率取代ID3中使用信息增益而造成的偏向于选取取值较多的特征作为分裂点的问题。针对ID3的不足2，采用剪枝操作，缓解过拟合问题。针对ID3的不足3，采用将连续值先排列，然后逐个尝试分裂，找到连续值中的最佳分裂点。信息增