文档介绍：决策树教师: ***学生: ***分类技术电子科技大学● What ’ s that? ●初印象(简例)●基本步骤●量化纯度●信息增益●停止条件电子科技大学●过度拟合●过度拟合修正●实例详解●准确率估计 What ’ s that? ●决策树( Decision Tree )是一种简单但是广泛使用的分类器。通过训练数据构建决策树,可以高效的对未知的数据进行分类。●决策树两大优点: 1)决策树模型可以读性好,具有描述性,有助于人工分析; 2)效率高,决策树只需要一次构建,反复使用,每一次预测的最大计算次数不超过决策树的深度。电子科技大学 What ’ s that? ●决策树( Decision Tree )是一种简单但是广泛使用的分类器。通过训练数据构建决策树,可以高效的对未知的数据进行分类。●决策树两大优点: 1)决策树模型可以读性好,具有描述性,有助于人工分析; 2)效率高,决策树只需要一次构建,反复使用,每一次预测的最大计算次数不超过决策树的深度。电子科技大学电子科技大学 ID 拥有房产(是/否) 婚姻情况(单身,已婚,离婚) 年收入(单位:千元) 无法偿还债务(是/否) 1 是单身 125 否 2 否已婚 100 否 3 否单身 70 否 4 是已婚 120 否 5 否离婚 95 是 6 否已婚 60 否 7 是离婚 220 否 8 否单身 85 是 9 否已婚 75 否 10 否单身 90 是初印象电子科技大学 ID 拥有房产(是/否) 婚姻情况(单身,已婚,离婚) 年收入(单位:千元) 无法偿还债务(是/否) 1 是单身 125 否 2 否已婚 100 否 3 否单身 70 否 4 是已婚 120 否 5 否离婚 95 是 6 否已婚 60 否 7 是离婚 220 否 8 否单身 85 是 9 否已婚 75 否 10 否单身 90 是初印象上表根据历史数据,记录已有的用户是否可以偿还债务,以及相关的信息。通过该数据,构建的决策树如下: 电子科技大学比如新来一个用户:无房产,单身,年收入 55K ,那么根据上面的决策树, 可以预测他无法偿还债务(蓝色虚线路径)。电子科技大学基本步骤●决策树构建的基本步骤如下: 1. 开始,所有记录看作一个节点 2. 遍历每个变量的每一种分割方式,找到最好的分割点 3. 分割成两个节点 N1 和 N2 4. 对 N1 和 N2 分别继续执行 2-3 步,直到每个节点足够“纯”为止●决策树的变量可以有两种: 1)数字型( Numeric ):变量类型是整数或浮点数,如前面例子中的“年收入”。用“>= ”,“>”,“<”或“<= ”作为分割条件(排序后,利用已有的分割情况,可以优化分割算法的时间复杂度)。 2)名称型( Nominal ):类似编程语言中的枚举类型,变量只能重有限的选项中选取,比如前面例子中的“婚姻情况”,只能是“单身”,“已婚”或“离婚”。使用“=”来分割。电子科技大学量化纯度 Gini 纯度: 熵( Entropy ): 误分类差错: 上面的三个公式均是值越大,表示越“不纯”,越小表示越“纯”。三种公式只需要取一种即可,实践证明三种公式的选择对最终分类准确率的影响并不大,一般使用熵公式。转至示例电子科技大学信息增益信息增益( Information Gain ): I(.) 是给定节点的不纯性度量, N是父节点上的记录总数, k是属性值的个数, N(Vj) 是与子女节点 Vj相关联的记录个数。转至示例