决策树一、前言二、决策树学习三、CART（Classification And Regression Tree）知识点：

81 阅读 0 评论 54 点赞

我是靠谱客的博主欢呼大地，最近开发中收集的这篇文章主要介绍决策树一、前言二、决策树学习三、CART（Classification And Regression Tree）知识点：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、前言

1.决策树学习存在三个过程：特征选择，决策树生成，决策树剪枝。

2.决策树的节点有两种类型：内部节点和叶节点，内部节点表示一个特征，叶子节点代表一个类别。

二、决策树学习

1.特征选择

特征选择就是要优先选取对于训练数据具有良好分类能力的特征进行特征空间的划分，其准则就是信息增益或信息增益比。

根据信息增益准则的特征选择方法是：对训练数据集或数据子集D，计算每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

ID3算法：以信息增益为准则选择信息增益最大的属性。
缺点：1）信息增益对可取值数目较多的属性有所偏好，比如通过ID号可将每个样本分成一类，但是没有意义。

2）ID3只能对离散属性的数据集构造决策树。
鉴于以上缺点，后来出现了C4.5算法。

C4.5算法：以信息增益率为准则选择属性；在信息增益的基础上对属性有一个惩罚，抑制可取值较多的属性，增强泛化性能。
优点：1）在树的构造过程中可以进行剪枝，缓解过拟合；

2）能够对连续属性进行离散化处理（二分法)；

3）能够对缺失值进行处理；
缺点：构造树的过程需要对数据集进行多次顺序扫描和排序，导致算法低效；
刚才我们提到信息增益对可取值数目较多的属性有所偏好；而信息增益率对可取值数目较少的属性有所偏好！两者结合：先从候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。而不是大家常说的直接选择信息增益率最高的属性！

1.1 信息增益（information gain) （ID3算法）

信息增益表示得知特征X的信息而使得类Y(这个类只各个类别，而不一定是某一个类别)的信息的不确定性减少的程度。

定义：

集合D的经验熵H(D)与特征A给定条件下，D的经验条件熵H(D|A)之差，即：

$g(D,A)=H(D)-H(D|A)$

1.2 信息增益比（C4.5算法）

$g_{R}(D,A) = g(D,A)/H(D)$

熵（entropy）:表示随机变量不确定性的度量。

设 $textup{x}$ 表示一个取有限个值的离散随机变量，其概率分布:

$P(X=x_{i})=p_{i}$ $i=1,2,3...,n$

则随机变量 $textup{x}$ 的熵定义为：

$H(X)=-sum_{i=1}^{n}p_{i} log p_{i}$

熵只依赖于随机变量的分布，而与随机变量的取值无关。

条件熵（conditional entropy）:表示在已知随机变量x的条件下，随机变量Y的不确定性，定义为X给定条件下，Y的条件概率分布的熵对x的数学期望。

$H(Y|X)=sum_{i=1}^{n}p_{i}H(Y|X=x_{i})$

其中：

$p_{i}=P(X=x_{i})$

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵

tips:（关于熵的详细信息参考https://blog.csdn.net/am290333566/article/details/81187124）

作为一个不确定性函数，需要满足三个条件：

单调性，发生概率越高的事件，其携带的信息量越低；
非负性，信息熵可以看作为一种广度量，非负性是一种合理的必然；
累加性，即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和，这也是广度量的一种体现。

能同时满足上述3个条件的函数是对数函数： ${color{Blue}log p }$

在信源中，考虑的不是某一单个符号发生的不确定性，而是要考虑这个信源所有可能发生情况的平均不确定性。这时，信源的平均不确定性应当为单个符号不确定性 $-log p_{i}$ 的统计平均值，也就是求期望值，即：

$H(textup{x})=-sum_{i=1}^{n}p_{i} log p_{i}$

çµä¸æ¦ççå³ç³»

2.决策树剪枝

通常，决策树容易产生过拟合，因为决策树的生成过程只考虑了最大化信息增益，以实现对训练数据的最佳拟合。因此，需要对树进行剪枝处理，通过极小化决策树整体损失函数，降低模型的复杂度，以增加泛化能力。决策树的生成学习局部模型，决策树的剪枝学习整体模型。

所谓剪枝，就是去掉已生成的树的一些内部节点，并将相应的根节点作为新的叶节点，从而简化树模型。决策树剪枝的基本策略有：预剪枝 和 后剪枝
预剪枝：是指在决策树的生成过程中，对每个结点在划分前后进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶结点。

后剪枝：先从训练集生成一颗完整的决策树，然后自底向上的对非叶子结点考察，若将该结点对应的子树替换成叶子结点能决策树泛化性能的提升，则将该子树替换成叶结点。

如何判断决策树泛化性能是否提升呢？这就要用到我们上述的决策树的损失函数了。

预剪枝：要对划分前后的泛化性能进行比较来决定是不是继续划分，从预剪枝的定义可以看出，预剪枝操作可以使决策树的很多分支都没有展开。

优点：不仅降低了过拟合的风险，还显著的减少了决策树训练时间的开销和测试时间的开销

缺点： 有些分支的当前划分不会提升泛化性能、甚至可能导致返回性能的暂时降低，但在其基础上进行的后序划分却又可能导致性能的显著提高。产生这种问题的原因是，预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

后剪枝：是先从训练集生成一颗完整的决策树，然后从底而上进行修剪。
优点： 相对于预剪枝来说：后剪枝通常比预剪枝决策树保留了更多的分支。一般情况下后剪枝决策树的欠拟合风险较小，泛化性能往往优于预剪枝决策树。

缺点： 因为是在完全生成决策树的以后，再从低到上的对树中的所有非叶子结点进行逐一考察，因此其训练时间开销比未剪枝和预剪枝决策树大很多。

设树T的叶子节点个数为|T|，t是树T的叶子节点，该叶节点有 $N_{t}$ 个样本点，其中k类的样本点有 $N_{tk}$ 个， $H_{t}(T)$ 是叶节点t的经验熵， $alpha geq 0$ 为参数，则定义决策树学习的损失函数：

$C_{alpha }(T)=C(T)+alpha |T|=sum_{t=1}^{|T|}N_{t}H_{t}(T)+alpha |T|$

$C(T)$ 表示模型对训练数据的拟合度， $|T|$ 表示模型的复杂度， $alpha$ 调和二者，较小的 $alpha$ 促使选择较复杂的模型。

三、CART（Classification And Regression Tree）

CART假设决策树是二叉树，内部特征节点左分支取值为 “是”，右分支为 “否”，这样，等价于决策树递归地二分每个特征。可以进行分类和回归，可以处理离散属性，也可以处理连续的。CART 与ID3,C4.5的一个重要区别在于CART是二叉树，因此，在某个特征的所有特征值没用尽之前，可以多次以该特征进行数据集的划分。CART建树的过程在于遍历所有特征以及特征值，以寻得最有特征与特征值组合，使得数据集被划分后，对于回归问题，平方误差最小，对于分类问题，基尼指数最小。

1 回归树

一个回归树对应输入空间的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为M个单元 $R_{1},R_{2}...R_{M}$ ,并且每个单元有一个相应的输出值 $c_{m}$ ,于是回归树模型可以表示为：

$f(x)=sum_{m=1}^{M}c_{m}I(xin R_{m})$

1.1回归树的生成

（1）利用平方误差最小准则（最小二乘）递归地遍历所有变量 j 所有切分点 s，选择最优（j,s）对：

$underset{j, s}{min}[underset{c_{1}}{min}sum_{x_{i}in R_{1(j, s)}}(y_{i}-c_{1})^{2}+underset{c_{2}}{min}sum_{x_{i}in R_{2(j, s)}}(y_{i}-c_{2})^{2}]$

（2）用选定的最优（j,s）对划分新的区域，并计算输出值，输出值就是本区域内所有因变量的平均值。

（3）递归执行（1）（2），直到满足停止条件为止。

1.2 分类树的生成

分类树使用基尼指数表示样本集合的不确定性，定义如下：

假设有K个分类，样本点属于k类的概率为 $P_{k}$ ，则概率分布的基尼指数定义为：

$Gini(p)=sum_{k=1}^{K}p_{k}(1-p_{k})$

如果样本集合D根据特征A是否取某一可能值a被分割成 $D_{1}$ 和 $D_{2}$ 两个部分，则在特征A的条件下，集合D的基尼指数为：

$Gini(D,A)=frac{|D_{1}|}{|D|}Gini(D_{1})+frac{|D_{2}|}{|D|}Gini(D_{2})$

Gini(D,A)表示经A分割后，集合D的不确定性。

基尼指数是信息熵中﹣logP在P=1处一阶泰勒展开后的结果！所以两者都可以用来度量数据集的纯度，用于描述决策树节点的纯度！(详见：https://blog.csdn.net/YE1215172385/article/details/79470926)

1.3 CART剪枝

未完待续。。。。

知识点：

1.决策树与逻辑回归的区别：决策树针对每个特征单独处理，可以进行非线性划分。逻辑回归对于每个特征赋予一定的权重而得到一个新值，并根据Sigmoid函数把该值变换为概率，随后通过设置阈值的方式进行分类，逻辑回归只能找到线性划分。

2.决策树学习：采用自顶向下的递归的方法，基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处熵值为0（叶节点中的实例都属于一类）无论是在ID3还是C4.5决策树的生成算法中，都是递归的生成决策树，直到不能继续下去为止。这样产生的决策树存在一些问题：过拟合即对训练数据的分类很准确，对未知的测试数据的分类却没有那么准确。过拟合的原因在于学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。

3.决策树要达到寻找最纯净划分的目标要干两件事，建树和剪枝

参考：

李航. 统计学习方法[M]. 清华大学出版社, 2012.