模式识别实验报告9.pdf

深圳大学研究生课程：模式识别理论与方法 课程作业实验报告 实验名称: 分类回归决策树CART 的研究与实现 实验编号：Proj08-0 1 签 名： 姓 名：罗升 学 号：2140130418 截止提交日期：2015 年6 月29 日 摘要：分类回归决策树算法：CART 算法采用一种二分递归分割的技术，将当前的样本 集分为两个子样本集，使得生成的每个非叶子节点都有两个分支。 使用课本表中的数据来训练二叉分类树，训练过程中使用熵不纯度进行分支，并 用训练好的非剪枝完全树对{A,E,I,L,N},{D,E,J,K,N},{B,F,J,K,M}, {C,D,J,L,N}四个模式 进行分类，其分类结果与剪枝完全树对四个模式的分类结果相同。 1 / 10 一、 基本原理 分类回归决策树算法：CART(Classification And Regression Tree)算法采用一 种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的每个非 叶子节点都有两个分支。 分类树两个基本思想：第一个是将训练样本进行递归地划分自变量空间进行 建树的想法，第二个想法是用验证数据进行剪枝。 1. 决策树的生成 决策树采用自顶向下的递归方式：从根节点开始在每个节点上按照给定标准 选择测试属性，然后按照相应属性的所有可能取值向下建立分支，划分训练样本， 直到一个节点上的所有样本都被划分到同一个类，或者某一节点中的样本数量低 于给定值时为止。这一阶段最关键的操作是在树的节点上选择最佳测试属性，该 属性可以将训练样本进行最好的划分。 最流行的测量时所谓的“熵不纯度”(亦称为信息量不纯度)： i(N ) P( )log P( ) (1) j 2 j j P( )  这里 是节点 N 处属于 类模式样本数占总样本数的频度。根据众做周知 j j 的熵的特性，如果所有模式的样本都来自同一类别，则不纯度为零，否则是大于 零的正值，当所有类别以等概率出现时，熵值取最大值。 另一种不纯度的定义在两类分类问题中特别有用。根据当节点样本均来自单 一类别时不纯度为0 的思想，可用如下多项式形式定义不纯度： i(N) P( )P( ) (2) 1 2 一种推广了的可用于多类分类问题的方差不纯度，称为“Gini不纯度”： 2 (3) i(N ) P( )P( ) 1P ( ) i j j i j j 这也正是当节点 N 的类别标记任意选取时对应的误差率。当类别标记等概率时 “Gini不纯度”指标的峰度特性比“熵不纯度”要好。 “误分类不纯度”可以定义为： i(N ) 1max P( ) (4)