决策树python源码_python决策树scikit_python决策树剪枝(2)

4.8试将决策树生成的深度优先搜索过程修改为广度优先搜索，以参数MaxNode控制树的最大结点数，将题4.7中基于队列的决策树算法进行改写。对比题4.7中的算法，试分析哪种方式更易于控制决策树所需储存不超过内存。答：在4.7中写的基于队列的算法本身就是广度优先搜索的。若要写成深度优先搜索的方式应该将队列换成堆栈即可。以下对4.7中的代码进行改写，用队列MaxNode控制——————————————————————————————————————————————————————输入：训练集 D={(x1,y1),(x2,y2),...,(xm,ym)}; 属性集 A={a1,a2,...,ad} 最大节点数MaxNode过程：函数TreeGenerate(D,A,MaxNode)1:生成节点root2:if D中样本全部属于同一类别C then3: 将root标记为C类叶节点;return4:end if5:if A=空集 or D中样本在A上取相同 then6: 将root标记为叶节点，其类别标记为D中样本数最多的类；return7:end if8:从A中选择最优划分属性a*;9:将root标记为分支节点，属性为属性a*;10:将root放入NodeQueue;11:将D放入DataQueue;12:将A\{a*}放入AQueue;13:初始化节点数numNode=1;14:while NodeQueue 非空:15: 取出NodeQueue队尾的节点rNode，其对应的属性是ra*;16: 取出DataQueue队尾的数据集rD; #此处r均指队尾rear17: 取出AQueue队尾的属性集rA;18: if numNode==MaxNode:19: 将rNode标记为叶节点，类别标记为rD中样本最多的类;20: continue; #跳过本次循环，即不再对这个节点做展开。

对于下一个节点，由于条件任然成立，故任然不展开21: for ra*的每一个取ra*v do:22: 为rNode生成一个分支节点，令rDv表示rD在ra*上取为ra*v的样本子集;23: if rDv为空 then：24: 将分支节点标记为叶节点，其类别标记为rD中样本最多的类;25: else if rD中样本全部属于同一类别C then26: 将分支节点标记为C类叶节点;27: else if rA=空集 orrD中样本在A上取相同 then28: 将分支节点标记为叶节点，其类别标记为rD中样本数最多的类;29: else：30: 从rA中选择最优划分属性a*v;31: 将分支节点的属性记为a*v;32: 将分支节点放入NodeQueue的队头;33: 将rDv放入DataQueue的队头;34: 将rA\{a*v}放入AQueue的队头;35: 将(rDepth1)放入DepthQueue的队头;36: end if37： numNode=138: end for39:end while输入：以root为根节点的一棵决策树——————————————————————————————————————————————————————讨论：4.7中与4.8中用队列的话均为广度优先搜索，我觉得是出题的时候的疏忽。

。应该是广度优先搜索（队列）MaxNode控制与 深度优先搜索（堆栈）MaxDepth控制 两种方法之间的比较。个人认为，广度优先搜索（队列）MaxNode 的方法更容易控制决策树所需内存不溢出。因为最大节点数目是固定的。队列中储存的是当前深度未处理的节点以及当前深度以处理节点的下一级节点，其数目是可控的，总小于最大节点数。而深度优先搜索在堆栈中储存的是当前节点的兄弟节点、当前节点的父节点、当前节点的父节点的兄弟节点.....若一些分支节点的分支数很多，那么堆栈的深度就会比较深，虽然有MaxDepth控制最大深度，但还是可能出现栈溢出的情况。

4.9试将4.4.2节对缺失的处理机制推广到基指数的计算中去。答：

4.10从网上下载或自己编程实现任意一种多变量决策树算法，并观察其在西瓜数据集3.0上产生的结果。答：此处要求实现一种多变量决策树算法。实际上4.3与4.4题就是多变量决策树算法。其在西瓜数据集3.0上产生的结果如下

与P85的图4.8一致。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-28592-2.html