python决策树之CART分类回归树详解

决策树之CART(分类回归树)详解,具体内容如下

1、CART分类回归树简介

  CART分类回归树是一种典型的二叉决策树,可以处理连续型变量和离散型变量。如果待预测分类是离散型数据,则CART生成分类决策树;如果待预测分类是连续型数据,则CART生成回归决策树。数据对象的条件属性为离散型或连续型,并不是区别分类树与回归树的标准,例如表1中,数据对象xi的属性A、B为离散型或连续型,并是不区别分类树与回归树的标准。

表1

2、CART分类回归树分裂属性的选择

  2.1 CART分类树——待预测分类为离散型数据

  选择具有最小Gain_GINI的属性及其属性值,作为最优分裂属性以及最优分裂属性值。Gain_GINI值越小,说明二分之后的子样本的“纯净度”越高,即说明选择该属性(值)作为分裂属性(值)的效果越好。
  对于样本集S,GINI计算如下:

其中,在样本集S中,Pk表示分类结果中第k个类别出现的频率。

  对于含有N个样本的样本集S,根据属性A的第i个属性值,将数据集S划分成两部分,则划分成两部分之后,Gain_GINI计算如下:

其中,n1、n2分别为样本子集S1、S2的样本个数。

  对于属性A,分别计算任意属性值将数据集划分成两部分之后的Gain_GINI,选取其中的最小值,作为属性A得到的最优二分方案:

对于样本集S,计算所有属性的最优二分方案,选取其中的最小值,作为样本集S的最优二分方案:

所得到的属性A及其第i属性值,即为样本集S的最优分裂属性以及最优分裂属性值。

  2.2 CART回归树——待预测分类为连续型数据

  区别于分类树,回归树的待预测分类为连续型数据。同时,区别于分类树选取Gain_GINI为评价分裂属性的指标,回归树选取Gain_σ为评价分裂属性的指标。选择具有最小Gain_σ的属性及其属性值,作为最优分裂属性以及最优分裂属性值。Gain_σ值越小,说明二分之后的子样本的“差异性”越小,说明选择该属性(值)作为分裂属性(值)的效果越好。

  针对含有连续型分类结果的样本集S,总方差计算如下:

其中,μ表示样本集S中分类结果的均值,Ck表示第k个分类结果。

  对于含有N个样本的样本集S,根据属性A的第i个属性值,将数据集S划分成两部分,则划分成两部分之后,Gain_σ计算如下:

  对于属性A,分别计算任意属性值将数据集划分成两部分之后的Gain_σ,选取其中的最小值,作为属性A得到的最优二分方案:

  对于样本集S,计算所有属性的最优二分方案,选取其中的最小值,作为样本集S的最优二分方案:

所得到的属性A及其第i属性值,即为样本集S的最优分裂属性以及最优分裂属性值。

3、CART分类回归树的剪枝

  由于决策树的建立完全是依赖于训练样本,因此该决策树对训练样本能够产生完美的拟合效果。但这样的决策树对于测试样本来说过于庞大而复杂,可能产生较高的分类错误率。这种现象就称为过拟合。因此需要将复杂的决策树进行简化,即去掉一些节点解决过拟合问题,这个过程称为剪枝。

  剪枝方法分为预剪枝和后剪枝两大类。预剪枝是在构建决策树的过程中,提前终止决策树的生长,从而避免过多的节点产生。预剪枝方法虽然简单但实用性不强,因为很难精确的判断何时终止树的生长。后剪枝是在决策树构建完成之后,对那些置信度不达标的节点子树用叶子结点代替,该叶子结点的类标号用该节点子树中频率最高的类标记。后剪枝方法又分为两种,一类是把训练数据集分成树的生长集和剪枝集;另一类算法则是使用同一数据集进行决策树生长和剪枝。常见的后剪枝方法有CCP(Cost Complexity Pruning)、REP(Reduced Error Pruning)、PEP(Pessimistic Error Pruning)、MEP(Minimum Error Pruning)。其中,悲观错误剪枝法PEP(Pessimistic Error Pruning)在“决策树之C4.5算法详解”中有详细介绍,感兴趣的小童鞋可以了解学习。这里我们详细介绍CART分类回归树中应用最广泛的剪枝算法——代价复杂性剪枝法CCP(Cost Complexity Pruning)。

  代价复杂性剪枝法CCP(Cost Complexity Pruning)主要包含两个步骤:(1)从原始决策树T0开始生成一个子树序列{T0,T1,...,Tn},其中,Ti+1从Ti产生,Tn为根节点。(2)从第1步产生的子树序列中,根据树的真实误差估计选择最佳决策树。

  CCP剪枝法步骤(1)

  生成子树序列{T0,T1,...,Tn}的基本思想是从T0开始,裁剪Ti中关于训练数据集误差增加最小的分枝来得到Ti+1。实际上,当1棵树T在节点t处剪枝时,它的误差增加直观上认为是R(t)−R(Tt),其中,R(t)为在节点t的子树被裁剪后节点t的误差,R(Tt)为在节点t的子树没被裁剪时子树Tt的误差。然而,剪枝后,T的叶子数减少了L(Tt)−1,其中, L(Tt)为子树Tt的叶子数,也就是说,T的复杂性减少了。因此,考虑树的复杂性因素,树分枝被裁剪后误差增加率由下式决定:

其中,R(t)表示节点t的子树被裁剪后节点t的误差,R(t)=r(t)∗p(t),r(t)是节点t的误差率,p(t)是节点t上的样本个数与训练集中样本个数的比例。R(Tt)表示节点t的子树没被裁剪时子树Tt的误差,即子树Tt上所有叶子节点的误差之和。

  Ti+1就是选择Ti中具有最小α值所对应的剪枝树。

  例如:图1中ti表示决策树中第i个节点,A、B表示训练集中的两个类别,A、B之后的数据表示落入该节点分别属于A类、B类的样本个数。

  图1,决策树中训练样本总个数为80。对于节点t4,其中,A类样本46个,B类样本4个,根据大多数原则,则节点t4中样本为A类,故节点t4的子树(t8、t9)被裁剪之后t4的误差为:450∗5080=480。节点t4的子树(t8、t9)被裁剪之前t4的误差为:145∗4580+25∗580=380。故α(t4)=480−3802−1=0.0125。类似过程,依次得到所有节点的误差增加率,如表2:

表2

  从表2可以看出,在原始树T0行,4个非叶节点中t4的α值最小,因此,裁剪T0的t4节点的分枝得到T1;在T1行,虽然t2和t3的α值相同,但裁剪t2的分枝可以得到更小的决策树,因此,T2是裁剪T1中的t2分枝得到的。

  CCP剪枝法步骤(2)

  如何根据第1步产生的子树序列{T0,T1,...,Tn},选择出1棵最佳决策树是CCP剪枝法步骤(2)的关键。通常采用的方法有两种,一种是V番交叉验证(V-fold cross-validation),另一种是基于独立剪枝数据集。此处不在过分赘述,感兴趣的小童鞋,可以阅读参考文献[1][2][3]等。

参考文献

[1] 魏红宁. 决策树剪枝方法的比较[J]. 西南交通大学学报, 2005, 40(1):44-48.
[2] 张宇. 决策树分类及剪枝算法研究[D]. 哈尔滨理工大学, 2009.
[3] Breiman L, Friedman J H, Olshen R, et al. Classification and Regression Trees[J]. Biometrics, 1984, 40(3):358.

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2017-12-19

Python机器学习之决策树算法实例详解

本文实例讲述了Python机器学习之决策树算法.分享给大家供大家参考,具体如下: 决策树学习是应用最广泛的归纳推理算法之一,是一种逼近离散值目标函数的方法,在这种方法中学习到的函数被表示为一棵决策树.决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,机器学习算法最终将使用这些从数据集中创造的规则.决策树的优点为:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据.缺点为:可能产生过度匹配的问题.决策树适于处理离散型和连续型的数据. 在决策树中最重要的就是如何选取

机器学习python实战之决策树

决策树原理:从数据集中找出决定性的特征对数据集进行迭代划分,直到某个分支下的数据都属于同一类型,或者已经遍历了所有划分数据集的特征,停止决策树算法. 每次划分数据集的特征都有很多,那么我们怎么来选择到底根据哪一个特征划分数据集呢?这里我们需要引入信息增益和信息熵的概念. 一.信息增益 划分数据集的原则是:将无序的数据变的有序.在划分数据集之前之后信息发生的变化称为信息增益.知道如何计算信息增益,我们就可以计算根据每个特征划分数据集获得的信息增益,选择信息增益最高的特征就是最好的选择.首先我们先来

基于ID3决策树算法的实现(Python版)

实例如下: # -*- coding:utf-8 -*- from numpy import * import numpy as np import pandas as pd from math import log import operator #计算数据集的香农熵 def calcShannonEnt(dataSet): numEntries=len(dataSet) labelCounts={} #给所有可能分类创建字典 for featVec in dataSet: currentLa

python决策树之C4.5算法详解

本文为大家分享了决策树之C4.5算法,供大家参考,具体内容如下 1. C4.5算法简介   C4.5算法是用于生成决策树的一种经典算法,是ID3算法的一种延伸和优化.C4.5算法对ID3算法主要做了一下几点改进:   (1)通过信息增益率选择分裂属性,克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足:   (2)能够处理离散型和连续型的属性类型,即将连续型的属性进行离散化处理:   (3)构造决策树之后进行剪枝操作:   (4)能够处理具有缺失属性值的训练数据. 2

python编写分类决策树的代码

决策树通常在机器学习中用于分类. 优点:计算复杂度不高,输出结果易于理解,对中间值缺失不敏感,可以处理不相关特征数据. 缺点:可能会产生过度匹配问题. 适用数据类型:数值型和标称型. 1.信息增益 划分数据集的目的是:将无序的数据变得更加有序.组织杂乱无章数据的一种方法就是使用信息论度量信息.通常采用信息增益,信息增益是指数据划分前后信息熵的减少值.信息越无序信息熵越大,获得信息增益最高的特征就是最好的选择. 熵定义为信息的期望,符号xi的信息定义为: 其中p(xi)为该分类的概率. 熵,即信息

python实现决策树C4.5算法详解(在ID3基础上改进)

一.概论 C4.5主要是在ID3的基础上改进,ID3选择(属性)树节点是选择信息增益值最大的属性作为节点.而C4.5引入了新概念"信息增益率",C4.5是选择信息增益率最大的属性作为树节点. 二.信息增益 以上公式是求信息增益率(ID3的知识点) 三.信息增益率 信息增益率是在求出信息增益值在除以. 例如下面公式为求属性为"outlook"的值: 四.C4.5的完整代码 from numpy import * from scipy import * from mat

决策树的python实现方法

本文实例讲述了决策树的python实现方法.分享给大家供大家参考.具体实现方法如下: 决策树算法优缺点: 优点:计算复杂度不高,输出结果易于理解,对中间值缺失不敏感,可以处理不相关的特征数据 缺点:可能会产生过度匹配的问题 适用数据类型:数值型和标称型 算法思想: 1.决策树构造的整体思想: 决策树说白了就好像是if-else结构一样,它的结果就是你要生成这个一个可以从根开始不断判断选择到叶子节点的树,但是呢这里的if-else必然不会是让我们认为去设置的,我们要做的是提供一种方法,计算机可以根

python代码实现ID3决策树算法

本文实例为大家分享了python实现ID3决策树算法的具体代码,供大家参考,具体内容如下 ''''' Created on Jan 30, 2015 @author: 史帅 ''' from math import log import operator import re def fileToDataSet(fileName): ''''' 此方法功能是:从文件中读取样本集数据,样本数据的格式为:数据以空白字符分割,最后一列为类标签 参数: fileName:存放样本集数据的文件路径 返回值:

python机器学习之决策树分类详解

决策树分类与上一篇博客k近邻分类的最大的区别就在于,k近邻是没有训练过程的,而决策树是通过对训练数据进行分析,从而构造决策树,通过决策树来对测试数据进行分类,同样是属于监督学习的范畴.决策树的结果类似如下图: 图中方形方框代表叶节点,带圆边的方框代表决策节点,决策节点与叶节点的不同之处就是决策节点还需要通过判断该节点的状态来进一步分类. 那么如何通过训练数据来得到这样的决策树呢? 这里涉及要信息论中一个很重要的信息度量方式,香农熵.通过香农熵可以计算信息增益. 香农熵的计算公式如下: p(xi)

python模块之re正则表达式详解

一.简单介绍 正则表达式是一种小型的.高度专业化的编程语言,并不是python中特有的,是许多编程语言中基础而又重要的一部分.在python中,主要通过re模块来实现. 正则表达式模式被编译成一系列的字节码,然后由用c编写的匹配引擎执行.那么正则表达式通常有哪些使用场景呢? 比如为想要匹配的相应字符串集指定规则: 该字符串集可以是包含e-mail地址.Internet地址.电话号码,或是根据需求自定义的一些字符串集: 当然也可以去判断一个字符串集是否符合我们定义的匹配规则: 找到字符串中匹配该规

Python探索之ModelForm代码详解

这是一个神奇的组件,通过名字我们可以看出来,这个组件的功能就是把model和form组合起来,对,你没猜错,相信自己的英语水平. 先来一个简单的例子来看一下这个东西怎么用: 比如我们的数据库中有这样一张学生表,字段有姓名,年龄,爱好,邮箱,电话,住址,注册时间等等一大堆信息,现在让你写一个创建学生的页面,你的后台应该怎么写呢? 首先我们会在前端一个一个罗列出这些字段,让用户去填写,然后我们从后天一个一个接收用户的输入,创建一个新的学生对象,保存 其实,重点不是这些,而是合法性验证,我们需要在前端

python装饰器实例大详解

一.作用域 在python中,作用域分为两种:全局作用域和局部作用域. 全局作用域是定义在文件级别的变量,函数名.而局部作用域,则是定义函数内部. 关于作用域,我们要理解两点: a.在全局不能访问到局部定义的变量 b.在局部能够访问到全局定义的变量,但是不能修改全局定义的变量(当然有方法可以修改) 下面我们来看看下面实例: x = 1 def funx(): x = 10 print(x) # 打印出10 funx() print(x) # 打印出1 如果局部没有定义变量x,那么函数内部会从内往

python中 logging的使用详解

日志是用来记录程序在运行过程中发生的状况,在程序开发过程中添加日志模块能够帮助我们了解程序运行过程中发生了哪些事件,这些事件也有轻重之分. 根据事件的轻重可分为以下几个级别: DEBUG: 详细信息,通常仅在诊断问题时才受到关注.整数level=10 INFO: 确认程序按预期工作.整数level=20 WARNING:出现了异常,但是不影响正常工作.整数level=30 ERROR:由于某些原因,程序 不能执行某些功能.整数level=40 CRITICAL:严重的错误,导致程序不能运行.整数

python的mysqldb安装步骤详解

python的mysqldb安装步骤详解 安装MySQLdb: 一. 什么是MySQLdb? 解释:MySQLdb是Python操作MySQL的一个接口包.这里要理解一个概念,python操作数据库,都是需要一个类似MySQLdb这样的中间层,这些中间层抽象了具体的实现,提供了统一的API供开发者使用. 二. 如何安装MySQLdb? python2环境下: sudo pip install MySQL-python. MySQL-python目前暂时还不支持python3,有些小问题,可以安装

python魔法方法-自定义序列详解

自定义序列的相关魔法方法允许我们自己创建的类拥有序列的特性,让其使用起来就像 python 的内置序列(dict,tuple,list,string等). 如果要实现这个功能,就要遵循 python 的相关的协议.所谓的协议就是一些约定内容.例如,如果要将一个类要实现迭代,就必须实现两个魔法方法:__iter__.next(python3.x中为__new__).__iter__应该返回一个对象,这个对象必须实现 next 方法,通常返回的是 self 本身.而 next 方法必须在每次调用的时

python logging日志模块的详解

python logging日志模块的详解 日志级别 日志一共分成5个等级,从低到高分别是:DEBUG INFO WARNING ERROR CRITICAL. DEBUG:详细的信息,通常只出现在诊断问题上 INFO:确认一切按预期运行 WARNING:一个迹象表明,一些意想不到的事情发生了,或表明一些问题在不久的将来(例如.磁盘空间低").这个软件还能按预期工作. ERROR:更严重的问题,软件没能执行一些功能 CRITICAL:一个严重的错误,这表明程序本身可能无法继续运行 这5个等级,也

python实现rsa加密实例详解

python实现rsa加密实例详解 一 代码 import rsa key = rsa.newkeys(3000)#生成随机秘钥 privateKey = key[1]#私钥 publicKey = key[0]#公钥 message ='sanxi Now is better than never.' print('Before encrypted:',message) message = message.encode() cryptedMessage = rsa.encrypt(messag

python生成式的send()方法(详解)

随便在网上找了找,感觉都是讲半天讲不清楚,这里写一下. def generator(): while True: receive=yield 1 print('extra'+str(receive)) g=generator() print(next(g)) print(g.send(111)) print(next(g)) 输出: 1 extra111 1 extraNone 1 为什么会这样呢,点进send就能看到一句话 send:Resumes the generator and "sen