决策树算法总结讲课教案.doc
《决策树算法总结讲课教案.doc》由会员分享,可在线阅读,更多相关《决策树算法总结讲课教案.doc(19页珍藏版)》请在咨信网上搜索。
1、决策树算法总结精品文档决策树研发二部收集于网络,如有侵权请联系管理员删除 文件状态: 草稿 正式发布 正在修改文件标识:当前版本:1.0作者:张宏超完成日期:2019年3月8日目录1.算法介绍11.1.分支节点选取11.2.构建树31.3.剪枝102.sk-learn中的使用123.sk-learn中源码分析13 1. 算法介绍决策树算法是机器学习中的经典算法之一,既可以作为分类算法,也可以作为回归算法。决策树算法又被发展出很多不同的版本,按照时间上分,目前主要包括,ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的,可以用来做分类算法。C4.5是针对ID3的不足出现的
2、优化版本,也用来做分类。CART也是针对ID3优化出现的,既可以做分类,可以做回归。决策树算法的本质其实很类似我们的if-elseif-else语句,通过条件作为分支依据,最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由,以及谁先判断谁后判断,包括最后对过拟合的处理,也就是剪枝。这是我们之前写if语句时不会考虑的问题。决策树算法主要分为以下3个步骤:1. 分支节点选取2. 构建树3. 剪枝1.1. 分支节点选取分支节点选取,也就是寻找分支节点的最优解。既然要寻找最优,那么必须要有一个衡量标准,也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。熵:熵用来表示信
3、息的混乱程度,值越大表示越混乱,包含的信息量也就越多。比如,A班有10个男生1个女生,B班有5个男生5个女生,那么B班的熵值就比A班大,也就是B班信息越混乱。基尼系数:同上,也可以作为信息混乱程度的衡量指标。有了量化指标后,就可以衡量使用某个分支条件前后,信息混乱程度的收敛效果了。使用分支前的混乱程度,减去分支后的混乱程度,结果越大,表示效果越好。#计算熵值def entropy(dataSet): tNum = len(dataSet) print(tNum) #用来保存标签对应的个数的,比如,男:6,女:5 labels = for node in dataSet: curL = node
4、-1 #获取标签 if curL not in labels.keys(): labelscurL = 0 #如果没有记录过该种标签,就记录并初始化为0 labelscurL += 1 #将标签记录个数加1 #此时labels中保存了所有标签和对应的个数 res = 0 #计算公式为-p*logp,p为标签出现概率 for node in labels: p = float(labelsnode) / tNum res -= p * log(p, 2) return res#计算基尼系数def gini(dataSet): tNum = len(dataSet) print(tNum) # 用
5、来保存标签对应的个数的,比如,男:6,女:5 labels = for node in dataSet: curL = node-1 # 获取标签 if curL not in labels.keys(): labelscurL = 0 # 如果没有记录过该种标签,就记录并初始化为0 labelscurL += 1 # 将标签记录个数加1 # 此时labels中保存了所有标签和对应的个数 res = 1 # 计算公式为-p*logp,p为标签出现概率 for node in labels: p = float(labelsnode) / tNum res -= p * p return res
6、1.2. 构建树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*0.863 = 0.073T2的信息熵增益:1 12/20*0.812 - 8/20*0.544 = 0.295所以使用T2作为分支特征更优。ID3算法建树:依据前面的逻辑,递归寻找最优分支节点,直到下面情况结束1. 叶节点已经属于同一标签2. 虽然叶节点不属于同一标签,但是特征已经用完了3.
7、熵小于预先设置的阈值4. 树的深度达到了预先设置的阈值ID3算法的不足:1. 取值多的特征比取值少的特征更容易被选取。2. 不包含剪枝操作,过拟合严重3. 特征取值必须是离散的,或者有限的区间的。于是有了改进算法C4.5C4.5算法:基于ID3算法进行了改进,首先,针对ID3的不足1,采用信息增益率取代ID3中使用信息增益而造成的偏向于选取取值较多的特征作为分裂点的问题。针对ID3的不足2,采用剪枝操作,缓解过拟合问题。针对ID3的不足3,采用将连续值先排列,然后逐个尝试分裂,找到连续值中的最佳分裂点。信息增益率的计算:先计算信息增益,然后除以spliteInfo。spliteInfo为分裂后
8、的子集合的函数,假设分裂后的子集合个数为sub1和sub2,total为分裂前的个数。spliteInfo = -sub1 / total * log(sub1 / total) sub2 / total * log(sub2 / total)#index:特征序号#value:特征值#该方法表示将index对应特征的值为value的集合返回,返回集合中不包含index对应的特征def spliteDataSet(dataSet, index, value): newDataSet = for node in dataSet: if nodeindex = value: #0,index)列的
9、数据 newData = node:index #index+1,最后列的数据 newData.extend(nodeindex + 1:) newDataSet.append(newData) return newDataSet;#选择最优分裂项def chooseBestFeature(dataSet): #特征个数 featureNum = len(dataSet0) - 1 #计算整体样本的熵值 baseEntropy = entropy(dataSet) print(baseEntropy = %f%(baseEntropy) #保存最大的信息增益率 maxInfoGainRatio
10、 = 0.0 bestFeatureId = -1 for i in range(featureNum): #获取特征所有可能的值 featureValues = for node in dataSet: featureValues.append(nodei) print(featureValues) #将特征值去除重复 uniqueFeatureValues = set(featureValues) print(uniqueFeatureValues) #按照i特征分裂之后的熵值 newEntropy = 0.0 #分裂信息 spliteInfo = 0.0 #按照i所表示的特征,开始分裂数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 决策树 算法 总结 讲课 教案
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。