分类技术-决策树算法ppt课件.ppt

《分类技术-决策树算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、决策树教师：***学生：***分类技术电子科技大学●What’sthat?●初印象(简例)●基本步骤●量化纯度●信息增益●停止条件电子科技大学●过度拟合●过度拟合修正●实例详解●准确率估计What’sthat?●决策树（DecisionTree）是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。●决策树两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。电子科技大学What

2、’sthat?●决策树（DecisionTree）是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。●决策树两大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。电子科技大学电子科技大学ID拥有房产（是/否）婚姻情况（单身，已婚，离婚）年收入（单位：千元）无法偿还债务（是/否）1是单身125否2否已婚100否3否单身70否4是已婚120否5否离婚95是6否已婚60否7是离婚2

3、20否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，那么根据上面的决策树，可以预测他无法偿还债务

4、（蓝色虚线路径）。电子科技大学基本步骤●决策树构建的基本步骤如下：1.开始，所有记录看作一个节点2.遍历每个变量的每一种分割方式，找到最好的分割点3.分割成两个节点N1和N24.对N1和N2分别继续执行2-3步，直到每个节点足够“纯”为止●决策树的变量可以有两种：1）数字型（Numeric）：变量类型是整数或浮点数，如前面例子中的“年收入”。用“>=”，“>”,“<”或“<=”作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。2）名称型（Nominal）：类似编程语言中的枚举类型，变量

5、只能重有限的选项中选取，比如前面例子中的“婚姻情况”，只能是“单身”，“已婚”或“离婚”。使用“=”来分割。电子科技大学量化纯度Gini纯度：熵（Entropy）：误分类差错：上面的三个公式均是值越大，表示越“不纯”，越小表示越“纯”。三种公式只需要取一种即可，实践证明三种公式的选择对最终分类准确率的影响并不大，一般使用熵公式。转至示例电子科技大学信息增益信息增益（InformationGain）：I(.)是给定节点的不纯性度量，N是父节点上的记录总数，k是属性值的个数，N(Vj)是与子女节点Vj相关联的记录

6、个数。转至示例电子科技大学停止条件决策树的构建过程是一个递归的过程，所以需要确定停止条件，否则过程将不会结束。一种最直观的方式是当每个子节点只有一种类型的记录时停止，但是这样往往会使得树的节点过多，导致过拟合问题（Overfitting）。另一种可行的方法是当前节点中的记录数低于一个最小的阀值，那么就停止分割，将max(P(i))对应的分类作为当前叶节点的分类。电子科技大学过度拟合某决策树对训练数据可以得到很低的错误率，但是运用到测试数据上却得到非常高的错误率。过渡拟合的原因有以下几点：•噪音数据：训练数据中

7、存在噪音数据，决策树的某些节点有噪音数据作为分割标准，导致决策树无法代表真实数据。•缺少代表性数据：训练数据没有包含所有具有代表性的数据，导致某一类数据无法很好的匹配，这一点可以通过观察混淆矩阵（ConfusionMatrix）分析得出。•多重比较（MulitpleComparition）：电子科技大学过度拟合修正优化方案1：修剪枝叶前置裁剪：在构建决策树的过程时，提前停止。那么，会将切分节点的条件设置的很苛刻，导致决策树很短小。结果就是决策树无法达到最优。实践证明这中策略无法得到较好的结果。后置裁剪：决策树

8、构建好后，才开始裁剪。采用两种方法：1）用单一叶节点代替整个子树，叶节点的分类采用子树中最主要的分类；2）将一个字数完全替代另外一颗子树。后置裁剪有个问题就是计算效率，有些节点计算后就被裁剪了，导致有点浪费。电子科技大学过度拟合修正优化方案2：K-FoldCrossValidation首先计算出整体的决策树T，叶节点个数记作N，设i属于[1,N]。对每个i，使用K-FoldValidataion方法