决策树.pdf

下载

下载

16积分

20积分

下载

20积分

VIP价：16积分

回顾•随机优化方法•依赖随机性所起的关键作用，使搜索朝着预期最优解的区域前进，同时允许一定程度的随机扰动，以利于发现最优解•模拟退火•基于统计力学的概念和技术•遗传算法•基于生物学概念，尤其是进化论的数学描述 回顾•模拟退火•随机状态转移•Metropolis准则1ifE(x)E(x)p(x,x)E(x)E(x)expifE(x)E(x)T(k) 回顾•遗传算法•三种基本操作•复制（replication）•交叉（crossover）•变异（mutation）•基本过程•编码•生成种群•计算适应度•选择•交叉•变异 Ch 10. 决策树 特征类型•数值数据（numerical data）•例：{, , }•模式间可以计算距离度量•基于度量的模式分类方法•标称数据（nominal data）•例：{红色，有光泽，甜，小}•模式间没有距离的概念•非度量方法 决策树•什么是决策树？•决策树是一种类似流程图的树形结构，每个内部节点表示一个测试（查询），该节点的每个分支表示该测试的一个结果，每个叶节点表示一个类别•决策树的构成•根节点（root）•分支（branch）•叶节点（leaf） 决策树 决策树•决策树分类过程•从根节点开始，首先对某一属性的取值提问•Color?•与根节点相连的不同分支，对应这个属性的不同取值•green; yellow; red;•根据不同的回答，转向相应的分支•green•在新到达的节点处做同样的分支判断•Size? –big.•这一过程持续，直到到达某个叶节点，输出该叶节点的类别标记•Watermelon 决策树•决策树的判决面 决策树•决策树的优势•语义可表示性•从根节点到叶节点表示为合取式•（颜色=黄）AND（形状=细长）香蕉•利用合取式和析取式获得某个类别的明确描述•苹果=（绿色AND 中等大小）OR（红色AND 中等大小）•分类速度快•只需一系列简单查询即可对模式的类别做出判断•可以很自然的嵌入专家的先验知识 决策树学习算法•决策树研究历史•第一个决策树算法称为CLS(Concept Learning System)[E. B. Hunt, J. Marin, and P. T. Stone’s book “Experiments in Induction”published by Academic Press in 1966]•真正引发决策树研究热潮的算法是ID3[J. R. Quinlan’s paper in a book “Expert Systems in the Micro Electronic Age”edited by D. Michie, published by Edinburgh University Press in 1979]•最流行的决策树算法[J. R. Quinlan’s book “: Programs for Machine Learning”published by Morgan Kaufmann in 1993] 决策树学习算法•通用的决策树算法CART (Classification and Regression Tree)[L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone’s book “Classification and Regression Trees”published by Wadsworth in 1984]•基于决策树的较强学习算法为一种称为随机森林(RandomForests)的集成算法[L. Breiman’s MLJ’01 paper “Random Forests”] 构造决策树•基本过程•从上到下，分而治之（divide-and-conquer），递归生长•最初，所有的样本都在根节点•所有属性都是标称型的（如果是连续数值型的，则需要预先离散化）•所有样本根据每次选择出的属性递归的逐渐划分开来选择出来的属性称为一个划分（split）或测试（test）或查询（query）•查询的选择基于启发式或者统计特征 构造决策树•基本过程•满足如下条件之一时，划分操作停止•所有落入某一节点的样本均属于同一类别该节点成为叶节点，标记为该类别•没有特征能够进一步用于划分样本集该节点成为叶节点，类别标签为落入该节点的多数样本所属的类别•没有任何样本落入某一节点该节点成为叶节点，类别标签为落入父节点的多数样本所属的类别 CART•分类和回归树（Classification And Regression Tree, CART)•CART为通用的树生长算法框架，涉及如下问题：•属性的值是二值的还是多值的？即节点可以有几个分支？•如何确定某节点处应该测试哪个属性？•何时令某个节点为叶节点？•如果树生长的过大，如何使其变小变简单，即如何剪枝？•如果落入叶节点的样本不都属于同一类，如何给该叶节点赋类别标记？ 分支数目•同一个节点分出去的分支的数目称为分支系数或分支率（branching ratio）•任意决策树都可以用分支系数为2的决策树（即二叉树）来表示•二叉树是最常用的决策树形式 分支数目 分支数目 测试的选取•决策树设计的核心问题之一•基本思想：使后继结点的数据尽可能的“纯”•节点N的不纯度（impurity）i(N)•当N节点上的所有模式都来自同一类时，i(N)=0；•当N节点上的模式类别分布均匀时，i(N)应很大 测试的选取•常用不纯度度量•熵不纯度（entropy impurity）属于的样本个数jP()j样本总个数•方差不纯度——对两类问题•Gini不纯度•误分类不纯度 测试的选取•常用不纯度度量 测试的选取•对N节点如何选择查询？使不纯度下降最快的那个查询！•和分别为左、右子节点•和分别为左、右子节点的不纯度•是N节点的模式划分到的比例•如果采用熵不纯度，则不纯度下降差就是本次查询所能提供的信息增益（information gain） 信息增益•信息增益（information gain）•：节点N上样本总个数•：其中属于类的样本个数（i=1,2, …, m）i•：属性A的第j个取值（j=1,2, …, v）•该节点处的熵不纯度mSSiiE(S)log2SSi1•属性A将S划分为v个子集•中属于类的样本个数为i 信息增益•信息增益（information gain）•以A作为查询，生长出v个分支的信息熵vmSSSSjjijijE(A)E(S)logj2111jj•以A为查询的信息增益Gain(A)E(S)E(A)•选择信息增益最大的属性作为N节点的查询 信息增益•例子S1: buys_computer= “yes”, •训练集S2: buys_computer= “no” 信息增益•根节点上的熵不纯度9955E(root)loglog2214141414•age作为查询的信息熵2233E(root)loglog225555E(root)023322E(root)loglog22555554E(age)i(root)i(root)i(root) 信息增益•age作为查询的信息增益Gain(age)E(root)E(age)•类似可以计算出所有属性的信息增益Gain(income)(student)(credit_rating)•age的信息增益最大，所以选择age作为根节点的查询，对训练集进行首次划分 信息增益率•信息增益作为查询选择标准的缺点：偏向有较多不同取值的属性•为克服这一缺点，J. R. Quinlan在其著名的算法中采用信息增益率（gain ratio）作为选择标准Gain(A)Gain_ratio(A)IV(A)vSSjjIV(A)log2SSj1 信息增益率554455•例子IV(age)logloglog22214141414141466IV(income)logloglogIV(student)loglog22141414148866IV(credit_rating)loglog(age)Gain_ratio(age)(age)Gain(income)Gain_ratio(income)(income)Gain(student)Gain_ratio(student)(student)Gain(credit_rating)Gain_ratio(credit_rating)(credit_rating) Gini不纯度•：节点N上样本总个数•：其中属于类的样本个数（i=1,2, …, m）i•：属性A的第j个取值（j=1,2, …, v）•该节点处的Gini不纯度2mSiGini(S)1Si1•属性A将S划分为v个子集•中属于类的样本个数为i Gini不纯度•以A作为查询，生长出v个分支的Gini不纯度2vmSSSjjjGini(A)Gini(S)1j111j•选择Gini不纯度差最大（即Gini(A)最小）的属性作为N节点的查询 Gini不纯度•例子222253440Gini(age)111455144422531455Gini(income)?Gini(student)?Gini(credit_rating)? 分支停止准则•如果决策树持续生长，直到所有叶节点都达到最小不纯度为止，那么一般将出现“过拟合”•极端情况：所有叶节点仅对应一个训练样本，这时，决策树退化为查找表•如果分支停止过早，则对训练样本的拟合较差，导致分类性能较差•常用分支停止准则•交叉验证•预设一个不纯度下降差的阈值•监测每个节点代表的样本数目是否小于某个阈值 分支停止准则•最小化如下指标正则项•不纯度下降的统计显著分析•如果一个划分不能显著降低不纯度，则停止分支 剪枝•剪枝（pruning）•用于消除过拟合•预剪枝（prepruning）和后剪枝（postpruning）•预剪枝即前面提到的分支停止技术，也就是在树生长到一定条件时停止继续划分•后剪枝指首先让树充分生长，直到叶节点具有最小不纯度为止，然后对树进行剪枝•可用交叉验证技术来确定剪掉哪些分支•剪掉使不纯度增长最小的分支•一般来讲，后剪枝性能较好，但需要更多计算量 叶节点的标记•如果叶节点对应的样本都来自同一类，则用该类别标记该叶节点•一般情况下，叶节点都具有正的不纯度，此时用占优势的样本类别标记该叶节点 例子•根据二维空间n=16个点构成的训练集构造二叉CART决策树 例子•根节点的熵不纯度•查询形式：•的选择：排序，取相邻两点的中点作为xx共可生成15个和15个2s1s 例子•根据最大不纯度下降逐步划分训练集剪枝 例子•不稳定性 ID3•ID3: Interactive Dichotomizer-3（交互式二分法第三版）•仅仅适用于标称（无序）数据如果涉及实值数据，则需离散化，然后当做标称数据处理•每个划分的分支因子等于查询属性的取值个数•采用信息增益率作为选择查询的依据•算法直到所有叶节点的不纯度最小，或者没有可用于划分的属性时停止•标准版中无剪枝步骤 •: ID3算法的后继和改进•可以处理实值数据•每个划分的分支因子等于查询属性的取值个数•采用信息增益率作为选择查询的依据•首先让树充分生长，然后利用分支的统计显著性来实现剪枝•为目前最为流行的决策树算法 小结•特征类型•数值数据（numerical data）基于度量的模式分类方法•标称数据（nominal data）非度量方法•决策树•根节点（root）•分支（branch）•叶节点（leaf） 小结•构造决策树•分支数目•测试的选取•信息增益•信息增益率•Gini不纯度•剪枝•预剪枝•后剪枝