构造决策树 基本过程 ·满足如下条件之一时,划分操作停止 ·所有落入某一节点的样本均属于同一类别 该节点成为叶节点,标记为该类别 ·没有特征能够进一步用于划分样本集 该节点成为叶节点,类别标签为落入该节点的多数样本所属的类别 没有任何样本落入某一节点 该节点成为叶节点,类别标签为落入父节点的多数样本所属的类别
构造决策树 • 基本过程 • 满足如下条件之一时，划分操作停止 • 所有落入某一节点的样本均属于同一类别 该节点成为叶节点，标记为该类别 • 没有特征能够进一步用于划分样本集 该节点成为叶节点，类别标签为落入该节点的多数样本所属的类别 • 没有任何样本落入某一节点 该节点成为叶节点，类别标签为落入父节点的多数样本所属的类别
CART 分类和回归树( Classification And Regression Tree, CART CART为通用的树生长算法框架,涉及如下问题: ·属性的值是二值的还是多值的?即节点可以有几个分支? 如何确定某节点处应该测试哪个属性? 何时令某个节点为叶节点? ·如果树生长的过大,如何使其变小变简单,即如何剪枝? ·如果落入叶节点的样本不都属于同一类,如何给该叶节点赋类别 标记?
CART • 分类和回归树（Classification And Regression Tree, CART) • CART为通用的树生长算法框架，涉及如下问题： • 属性的值是二值的还是多值的？即节点可以有几个分支？ • 如何确定某节点处应该测试哪个属性？ • 何时令某个节点为叶节点？ • 如果树生长的过大，如何使其变小变简单，即如何剪枝？ • 如果落入叶节点的样本不都属于同一类，如何给该叶节点赋类别 标记？
分支数目 同一个节点分出去的分支的数目称为分支系数或 分支率( branching ratio ·任意决策树都可以用分支系数为2的决策树(即二 叉树)来表示 二叉树是最常用的决策树形式
分支数目 • 同一个节点分出去的分支的数目称为分支系数或 分支率（branching ratio） • 任意决策树都可以用分支系数为2的决策树（即二 叉树）来表示 • 二叉树是最常用的决策树形式
分支数目 root。1or2 level o green vellow Size? hape S level big roun d thin medium mall Watermelon Apple grape Size?) Banana Apple (Taste? level 2 b small sweet SOuI Grapefruit Lemon Cherry Grape level 3
分支数目
分支数目 color Green size big? color yellow? no no Watermelon (size medium shape round? sIze sma11? es no Apple Grape sIze big?) Banana (taste= sweet? Apple yes n Grapefruit(Lemon Cherry Grape
分支数目