培训资料决策树算法及应用拓展(41页)-管理培训(编辑修改稿)

培训资料决策树算法及应用拓展(41页)-管理培训(编辑修改稿)内容摘要：

)2/(l o g2l o g21l o g*)( 2/knknniniSC ki Γπ Cost of Encoding Tree  编码树结构本身的代价  编码每个分裂节点的代价  确定分类属性的代价  确定分类属性值的代价 amp。 其中， v是该节点上不同属性值的个数  编码每个树叶上的记录分类的代价 )22lo g ( v)1log ( v剪枝算法  设 N为欲计算其最小代价的节点  两种情形：  N是叶结点 ——C(S)+1 ——Cost1  N是内部节点，有两个子节点 N N2 已剪去 N N2， N成为叶子节点 ——Cost1 计算 N节点及其子树的代价，使用递归过程 Csplit(N)+1+minCost1+minCost2 ——Cost2 比较 Cost1和 Cost2，选取 代价较小者 作为返回值 计算最小子树代价的伪代码 Procedure ComputeCostamp。 Prune(Node N) if N 是叶子节点， return (C(S)+1) minCost1= Computeamp。 Prune(Node N1) minCost2= Computeamp。 Prune(Node N2) minCostN=min{C(S)+1,Csplit(N)+1+minCost1 +minCost2} if minCostN=C(S)+1 Prune child nodes N1 and N2 return minCostN 引入 Public算法  一般做法：先建树，后剪枝  Public算法：建树的同时进行剪枝  思想：在一定量 (用户定义参数 )的节点分裂后 /周期性的进行部分树的剪枝  存在的问题：可能高估 (OverEstimate)被剪节点的值  改进：采纳低估 (UnderEstimate)节点代价的策略 具体思路  三种叶节点：  有待扩展：需计算子树代价下界  不能扩展 (纯节点 )  剪枝后的结点 C(S)+1 改进算法的伪代码 Procedure ComputCosteamp。 Prune(Node N) If N是仍待扩展的结点， return N节点的代价下界 If N是纯节点或不可扩展的叶节点 ， return (C(S)+1) 两个子节点 N N2 minCost1= Computeamp。 Prune(Node N1) minCost2= Computeamp。 Prune(Node N2) minCostN=min{C(S)+1,Csplit(N)+1+minCost1 +minCost2} if minCostN=C(S)+1 Prune child nodes N1 and N2 return minCostN 计算子树代价下界  Public(1)  假设节点 N的代价至少是 1  Public(S) S —— split  计算以 N为根且包含 S个分裂点的子树代价的下界 (包括确定分裂节点属性的代价 )  Public(V) V ——split value  同上，还包括确定分裂节点值的代价 Public(S)算法 (一 )  相关概念 Public(S)算法 (二 )  定理：  任何以 N为根结点且有 S个分裂点的子树的代价至少是 2*S+1+S*log a+∑ ni i=s+2..k  证明： 编码树结构代价 2*S+。