极小泛化函数python,实变函数与泛函数分析基础

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

决策树、随机森林

在了解树模型之前，自然想到树模型和线性模型，他们有什么区别呢？

决策树与逻辑回归的分类区别也在于此。

树形模型更加接近人的思维方式，可以产生可视化的分类规则，产生的模型具有可解释性。树模型拟合出来的函数其实是分区间的阶梯函数。

决策树（decision tree）是一种基本的分类与回归方法，此处主要讨论分类的决策树。决策树是一种十分常用的分类方法，属于有监督学习（Supervised Learning）。所谓有监督学习，就是给出一堆样本，每个样本都有一组属性和一个分类结果，也就是分类结果已知，那么通过学习这些样本得到一个决策树，这个决策树能够对新的数据给出正确的分类。

决策树是一种树形结构，它主要有三种不同的节点：

决策树算法主要包括三个部分：特征选择、树的生成、树的剪枝。

比较常用的决策树算法有ID3，C4.5和CART（Classification And Regression Tree），CART的分类效果一般优于其他决策树。

样本数量，特征数量上面，一开始需要注意的：

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵 (empirical entropy)。

什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。

训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类Ck，k = 1,2,3,···,K，|Ck|为属于类Ck的样本个数，这经验熵公式可以写为：

信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。

条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望：

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令0log0=0。

信息增益

一般地，熵H(D)与条件熵H(D|A)之差成为互信息(mutual information) 。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益比

Gini 指数

举例计算Gini指数（不纯度）

这个分类结果明显并不是很好，因为它没有将见面与不见面完全的分开，在算法中，当然不能凭我们的“感觉”去评价分类结果的好坏。我们需要用一个数去表示。（具体数值代入上面的基尼指数计算公式）

信息增益 vs 信息增益比

Gini 指数 vs 熵

ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征，递归地构建决策树。

具体方法是：

1）从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。

2）由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；

3）最后得到一个决策树。

ID3相当于用极大似然法进行概率模型的选择。

与ID3算法相似，但是做了改进，将信息增益比作为选择特征的标准。

CART 的全称是分类与回归树。从这个名字中就应该知道，CART 既可以用于分类问题，也可以用于回归问题。

回归树中，使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。

要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。

ID3

熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。

信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说，用属性 a 来划分训练集，得到的结果中纯度比较高。

ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。

C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵选择信息增益比最大的作为最优特征。

C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。

CART 与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点只能根据属性值进行二分。

决策树生成算法递归的产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知测试数据的分类缺没有那么精确，即会出现过拟合现象。过拟合产生的原因在于在学习时过多的考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树，解决方法是考虑决策树的复杂度，对已经生成的树进行简化。

剪枝（pruning）：从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型。

实现方式：极小化决策树整体的损失函数或代价函数来实现

决策树学习的损失函数定义为：

鉴于决策树容易过拟合的缺点，随机森林采用多个决策树的投票机制来改善决策树，我们假设随机森林使用了m棵决策树，那么就需要产生m个一定数量的样本集来训练每一棵树，如果用全样本去训练m棵决策树显然是不可取的，全样本训练忽视了局部样本的规律，对于模型的泛化能力是有害的。

产生n个样本的方法采用Bootstraping法，这是一种有放回的抽样方法，产生n个样本。

而最终结果采用Bagging的策略来获得，即多数投票机制。

随机森林的生成方法：

1.从样本集中通过重采样的方式产生n个样本

2.假设样本特征数目为a，对n个样本选择a中的k个特征，用建立决策树的方式获得最佳分割点

3.重复m次，产生m棵决策树

4.多数投票机制来进行预测

（需要注意的一点是，这里m是指循环的次数，n是指样本的数目，n个样本构成训练的样本集，而m次循环中又会产生m个这样的样本集）

随机森林是一个比较优秀的模型，在我的项目的使用效果上来看，它对于多维特征的数据集分类有很高的效率，还可以做特征重要性的选择。运行效率和准确率较高，实现起来也比较简单。但是在数据噪音比较大的情况下会过拟合，过拟合的缺点对于随机森林来说还是较为致命的。

机器学习实战（三）——决策树

相关问答

Q1: 从零开始用Python构建神经网络

从零开始用Python构建神经网络

动机：为了更加深入的理解深度学习，我们将使用 python 语言从头搭建一个神经网络，而不是使用像 Tensorflow 那样的封装好的框架。我认为理解神经网络的内部工作原理，对数据科学家来说至关重要。

这篇文章的内容是我的所学，希望也能对你有所帮助。

神经网络是什么?

介绍神经网络的文章大多数都会将它和大脑进行类比。如果你没有深入研究过大脑与神经网络的类比，那么将神经网络解释为一种将给定输入映射为期望输出的数学关系会更容易理解。

神经网络包括以下组成部分

? 一个输入层，x

? 任意数量的隐藏层

? 一个输出层，?

? 每层之间有一组权值和偏置，W and b

? 为隐藏层选择一种激活函数，σ。在教程中我们使用 Sigmoid 激活函数

下图展示了 2 层神经网络的结构(注意：我们在计算网络层数时通常排除输入层)

2 层神经网络的结构

用 Python 可以很容易的构建神经网络类

训练神经网络

这个网络的输出 ? 为：

你可能会注意到，在上面的等式中，输出 ? 是 W 和 b 函数。

因此 W 和 b 的值影响预测的准确率. 所以根据输入数据对 W 和 b 调优的过程就被成为训练神经网络。

每步训练迭代包含以下两个部分:

? 计算预测结果 ?，这一步称为前向传播

? 更新 W 和 b,，这一步成为反向传播

下面的顺序图展示了这个过程：

前向传播

正如我们在上图中看到的，前向传播只是简单的计算。对于一个基本的 2 层网络来说，它的输出是这样的：

我们在 NeuralNetwork 类中增加一个计算前向传播的函数。为了简单起见我们假设偏置 b 为0：

但是我们还需要一个方法来评估预测结果的好坏(即预测值和真实值的误差)。这就要用到损失函数。

损失函数

常用的损失函数有很多种，根据模型的需求来选择。在本教程中，我们使用误差平方和作为损失函数。

误差平方和是求每个预测值和真实值之间的误差再求和，这个误差是他们的差值求平方以便我们观察误差的绝对值。

训练的目标是找到一组 W 和 b，使得损失函数最好小，也即预测值和真实值之间的距离最小。

反向传播

我们已经度量出了预测的误差(损失)，现在需要找到一种方法来传播误差，并以此更新权值和偏置。

为了知道如何适当的调整权值和偏置，我们需要知道损失函数对权值 W 和偏置 b 的导数。

回想微积分中的概念，函数的导数就是函数的斜率。

梯度下降法

如果我们已经求出了导数，我们就可以通过增加或减少导数值来更新权值 W 和偏置 b(参考上图)。这种方式被称为梯度下降法。

但是我们不能直接计算损失函数对权值和偏置的导数，因为在损失函数的等式中并没有显式的包含他们。因此，我们需要运用链式求导发在来帮助计算导数。

链式法则用于计算损失函数对 W 和 b 的导数。注意，为了简单起见。我们只展示了假设网络只有 1 层的偏导数。

这虽然很简陋，但是我们依然能得到想要的结果—损失函数对权值 W 的导数(斜率)，因此我们可以相应的调整权值。

现在我们将反向传播算法的函数添加到 Python 代码中

为了更深入的理解微积分原理和反向传播中的链式求导法则，我强烈推荐 3Blue1Brown 的如下教程：

Youtube：

整合并完成一个实例

既然我们已经有了包括前向传播和反向传播的完整 Python 代码，那么就将其应用到一个例子上看看它是如何工作的吧。

神经网络可以通过学习得到函数的权重。而我们仅靠观察是不太可能得到函数的权重的。

让我们训练神经网络进行 1500 次迭代，看看会发生什么。注意观察下面每次迭代的损失函数，我们可以清楚地看到损失函数单调递减到最小值。这与我们之前介绍的梯度下降法一致。

让我们看看经过 1500 次迭代后的神经网络的最终预测结果：

经过 1500 次迭代训练后的预测结果

我们成功了!我们应用前向和方向传播算法成功的训练了神经网络并且预测结果收敛于真实值。

注意预测值和真实值之间存在细微的误差是允许的。这样可以防止模型过拟合并且使得神经网络对于未知数据有着更强的泛化能力。

下一步是什么?

幸运的是我们的学习之旅还没有结束，仍然有很多关于神经网络和深度学习的内容需要学习。例如：

? 除了 Sigmoid 以外，还可以用哪些激活函数

? 在训练网络的时候应用学习率

? 在面对图像分类任务的时候使用卷积神经网络

我很快会写更多关于这个主题的内容，敬请期待!

最后的想法

我自己也从零开始写了很多神经网络的代码

虽然可以使用诸如 Tensorflow 和 Keras 这样的深度学习框架方便的搭建深层网络而不需要完全理解其内部工作原理。但是我觉得对于有追求的数据科学家来说，理解内部原理是非常有益的。

这种练习对我自己来说已成成为重要的时间投入，希望也能对你有所帮助

Q2: 如何利用 Python 实现 SVM 模型

我先直观地阐述我对SVM的理解，这其中不会涉及数学公式，然后给出Python代码。

SVM是一种二分类模型，处理的数据可以分为三类：

线性可分，通过硬间隔最大化，学习线性分类器

近似线性可分，通过软间隔最大化，学习线性分类器

线性不可分，通过核函数以及软间隔最大化，学习非线性分类器

线性分类器，在平面上对应直线；非线性分类器，在平面上对应曲线。

硬间隔对应于线性可分数据集，可以将所有样本正确分类，也正因为如此，受噪声样本影响很大，不推荐。

软间隔对应于通常情况下的数据集（近似线性可分或线性不可分），允许一些超平面附近的样本被错误分类，从而提升了泛化性能。

如下图：

实线是由硬间隔最大化得到的，预测能力显然不及由软间隔最大化得到的虚线。

对于线性不可分的数据集，如下图：

我们直观上觉得这时线性分类器，也就是直线，不能很好的分开红点和蓝点。

但是可以用一个介于红点与蓝点之间的类似圆的曲线将二者分开，如下图：

我们假设这个黄色的曲线就是圆，不妨设其方程为x^2+y^2=1，那么核函数是干什么的呢？

我们将x^2映射为X，y^2映射为Y，那么超平面变成了X+Y=1。

那么原空间的线性不可分问题，就变成了新空间的（近似）线性可分问题。

此时就可以运用处理（近似）线性可分问题的方法去解决线性不可分数据集的分类问题。

---------------------------------------------------------------------------------------------------------------------------

以上我用最简单的语言粗略地解释了SVM，没有用到任何数学知识。但是没有数学，就体会不到SVM的精髓。因此接下来我会用尽量简洁的语言叙述SVM的数学思想，如果没有看过SVM推导过程的朋友完全可以跳过下面这段。

对于求解（近似）线性可分问题：

由最大间隔法，得到凸二次规划问题，这类问题是有最优解的（理论上可以直接调用二次规划计算包，得出最优解）

我们得到以上凸优化问题的对偶问题，一是因为对偶问题更容易求解，二是引入核函数，推广到非线性问题。

求解对偶问题得到原始问题的解，进而确定分离超平面和分类决策函数。由于对偶问题里目标函数和分类决策函数只涉及实例与实例之间的内积，即xi,xj。我们引入核函数的概念。

拓展到求解线性不可分问题：

如之前的例子，对于线性不可分的数据集的任意两个实例：xi,xj。当我们取某个特定映射f之后，f(xi)与f(xj)在高维空间中线性可分，运用上述的求解（近似）线性可分问题的方法，我们看到目标函数和分类决策函数只涉及内积f(xi),f(xj)。由于高维空间中的内积计算非常复杂，我们可以引入核函数K(xi,xj)=f(xi),f(xj)，因此内积问题变成了求函数值问题。最有趣的是，我们根本不需要知道映射f。精彩！

我不准备在这里放推导过程，因为已经有很多非常好的学习资料，如果有兴趣，可以看：CS229 Lecture notes

最后就是SMO算法求解SVM问题，有兴趣的话直接看作者论文：Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines

我直接给出代码：SMO+SVM

在线性可分数据集上运行结果：

图中标出了支持向量这个非常完美，支持向量都在超平面附近。

在线性不可分数据集上运行结果（200个样本）：

核函数用了高斯核，取了不同的sigma

sigma=1，有189个支持向量，相当于用整个数据集进行分类。

sigma=10，有20个支持向量，边界曲线能较好的拟合数据集特点。

我们可以看到，当支持向量太少，可能会得到很差的决策边界。如果支持向量太多，就相当于每次都利用整个数据集进行分类，类似KNN。

Q3: 2019-03-02

集成学习：构建并结合多个学习器来完成学习任务。

同质：集成中只包含同种类型的个体学习器（基学习器）；

异质：集成中的个体学习器（组件学习器）由不同学习算法生成。

个体学习器的“准确性”和“多样性”很重要，且相互冲突。

分类：个体学习器间存在强依赖关系，必须串行生成的序列化方法，eg，Boosting；个体学习器间不存在强依赖关系，可同时生成的并行化方法，eg，Bagging和随机森林。

工作机制：先从初始训练集训练出一个基学习器1，根据基学习器误差率表现更新训练样本权重，使弱学习器1学习误差率高的训练样本权重变高，让这些点在弱学习器2中得到更多的重视，然后基于调整权重后的训练集训练学习器2,...重复进行，直至弱学习器数目达到指定的值T，最终将这T个基学习器进行加权结合。

Boosting族算法最著名的代表是AdaBoost，是“Adaptive Boosting（自适应增强）”的缩写。它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

算法过程

优点：作为分类器时精度很高；在AdaBoost框架下，可使用各种回归分类模型来构建学习器；不易发生过拟合（会加入正则化项）。

缺点：对异常样本点敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。

两者均是0/1误差的平滑近似：

梯度提升算法首先给定一个目标损失函数，它的定义域是所有可行的基函数集合，提升算法通过迭代的选择一个负梯度方向上的基函数来逐渐逼近局部最小值。

GB每一次建立模型是在之前建立模型损失函数的梯度下降方向。一般认为损失函数越小，性能越好，因此最好是使损失函数沿着梯度方向下降，模型得以不断改进提升性能。

GBDT是GB和DT的结合，是以决策树为基学习器的gb算法，此处的决策树是回归树。GBDT中的决策树深度一般不超过5，叶子结点数不超过10。GBDT核心在于：每一棵树学得是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学习。

xgboost是在GBDT基本思路上改善而来，主要改变有

1）在损失函数中加入防止过拟合的惩罚函数

T是叶子的个数，w是预测函数的参数，也就是决策树算法下叶子节点的权重值。可以控制γ和λ这两个超参数来调整正则化的惩罚力度。其实这里的惩罚函数也就定义了模型复杂度，比如γ越大，λ越大，复杂度越小越不易过拟合。

2）用二阶泰勒展式将损失函数展开，同时用到了一阶和二阶导数

第t次的loss：

对上式做二阶泰勒展开：g为一阶导数，h为二阶导数

3)CART回归树中寻找最佳分割点的衡量标准是最小化均方差，xgboost 寻找分割点的标准是最大化，lamda，gama与正则化项相关

xgboost算法的步骤和GB基本相同，都是首先初始化为一个常数，gb是根据一阶导数ri，xgboost是根据一阶导数gi和二阶导数hi，迭代生成基学习器，相加更新学习器。

为得到泛化性能强的集成，集成中的个体学习器应尽可能相互独立，考虑使用相互有交叠的采样子集。

并行式集成学习的最著名代表，基于自助采样法，算法流程如下：

优点：训练一个Bagging集成与直接使用基学习算法训练一个学习器的复杂度同阶；与标准AdaBoost只适用于二分类任务不同，Bagging能不经修改的用于多分类、回归任务；初始训练集63.2%用于训练，36.8%用作验证集对泛化性能做“包外估计”。

但从偏差-方差分解角度看，Bagging主要关注降低方差。

随机森林是Bagging的一个扩展变体，在以决策树为基学习器构建Bagging集成的基础上，在决策树训练过程中引入了随机属性选择。即对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k（kd，d为所有属性个数）个属性的子集，然后从中选一个最优属性用于划分。若k=d，则为传统决策树；k=1，则随机选择一个属性划分。一般推荐。

RF起始性能相对较差，但随着学习器数目的增加，会收敛到更低的泛化误差。另外RF的训练效率常优于Bagging，因为Bagging使用“确定型”决策树，选择划分属性时要对结点所有属性进行考察，而RF使用“随机型”决策树，只需考虑一个属性子集。

学习器结合可能会从三个方面带来好处：

1）统计方面：当多个假设达到同等性能时，可减小因误选单学习器导致泛化性能不佳的风险；

2）计算方面：降低陷入糟糕局部极小点的风险；

3）表示方面：扩大相应假设空间，学习更好的近似。

对数值型输出，最常见的结合策略是平均法。

简单平均：

(特殊的加权平均法，宜在个体学习器性能相近时使用)

加权平均法：

其中是个体学习器的权重，一般从训练数据中学习而得，通常要求，宜在个体学习器相差较大时使用。

对分类任务，学习器从类别标记集合中预测出一个标记，最常见的结合策略是投票法。

绝大多数投票法：

相对多数投票法：

预测为得票最多的标记，若同时有多个标记获得最高票，则从中随机选取一个。

加权投票法：

与加权平均法类似，是的权重，通常。

个体学习器的输出类型：

类标记：硬投票。，若将样本x预测为类别则取值为1，否则为0。

类概率：软投票。，相当于对后验概率的一个估计。

不同类型的值不能混用；对一些能在预测出类别标记的同时产生分类置信度的学习器，其分类置信度可转化为类概率使用；分类置信度应规范化后使用；基于类概率进行结合优于直接基于类标记进行结合；若基学习器类型不同，不能直接比较类概率值，应先将其转化为类标记输出（eg类概率输出最大的设为1，其他为0）再投票。

当训练数据很多时，常使用通过另一个学习器来进行结合的“学习法”，代表算法Stacking

第一阶段获得各个模型对样本x1的预测标签值；第二阶段将各个模型的预测标签值作为一个新的特征（x1的真实标签值还是标签值），再用某个算法进行训练，获得一个融合模型，用这个融合模型进行测试集的预测。

周志华《机器学习》

Q4: 大数据经典算法解析（1）一C4.5算法

姓名：崔升学号：14020120005

【嵌牛导读】：

C4.5作为一种经典的处理大数据的算法，是我们在学习互联网大数据时不得不去了解的一种常用算法

【嵌牛鼻子】：经典大数据算法之C4.5简单介绍

【嵌牛提问】：C4.5是一种怎么的算法，其决策机制靠什么实现？

【嵌牛正文】：

决策树模型：

决策树是一种通过对特征属性的分类对样本进行分类的树形结构，包括有向边与三类节点：

根节点（root node），表示第一个特征属性，只有出边没有入边；

内部节点（internal node），表示特征属性，有一条入边至少两条出边

叶子节点（leaf node），表示类别，只有一条入边没有出边。

上图给出了（二叉）决策树的示例。决策树具有以下特点：

对于二叉决策树而言，可以看作是if-then规则集合，由决策树的根节点到叶子节点对应于一条分类规则;

分类规则是互斥并且完备的，所谓互斥即每一条样本记录不会同时匹配上两条分类规则，所谓完备即每条样本记录都在决策树中都能匹配上一条规则。

分类的本质是对特征空间的划分，如下图所示，

决策树学习：

决策树学习的本质是从训练数据集中归纳出一组分类规则[2]。但随着分裂属性次序的不同，所得到的决策树也会不同。如何得到一棵决策树既对训练数据有较好的拟合，又对未知数据有很好的预测呢？

首先，我们要解决两个问题：

如何选择较优的特征属性进行分裂？每一次特征属性的分裂，相当于对训练数据集进行再划分，对应于一次决策树的生长。ID3算法定义了目标函数来进行特征选择。

什么时候应该停止分裂？有两种自然情况应该停止分裂，一是该节点对应的所有样本记录均属于同一类别，二是该节点对应的所有样本的特征属性值均相等。但除此之外，是不是还应该其他情况停止分裂呢？

2. 决策树算法

特征选择

特征选择指选择最大化所定义目标函数的特征。下面给出如下三种特征（Gender, Car Type, Customer ID）分裂的例子：

图中有两类类别（C0, C1），C0: 6是对C0类别的计数。直观上，应选择Car Type特征进行分裂，因为其类别的分布概率具有更大的倾斜程度，类别不确定程度更小。

为了衡量类别分布概率的倾斜程度，定义决策树节点tt的不纯度（impurity），其满足：不纯度越小，则类别的分布概率越倾斜；下面给出不纯度的的三种度量：

其中，p(ck|t)p(ck|t)表示对于决策树节点tt类别ckck的概率。这三种不纯度的度量是等价的，在等概率分布是达到最大值。

为了判断分裂前后节点不纯度的变化情况，目标函数定义为信息增益（information gain）：

I(⋅)I(⋅)对应于决策树节点的不纯度，parentparent表示分裂前的父节点，NN表示父节点所包含的样本记录数，aiai表示父节点分裂后的某子节点，N(ai)N(ai)为其计数，nn为分裂后的子节点数。

特别地，ID3算法选取熵值作为不纯度I(⋅)I(⋅)的度量，则

cc指父节点对应所有样本记录的类别；AA表示选择的特征属性，即aiai的集合。那么，决策树学习中的信息增益ΔΔ等价于训练数据集中类与特征的互信息，表示由于得知特征AA的信息训练数据集cc不确定性减少的程度。

在特征分裂后，有些子节点的记录数可能偏少，以至于影响分类结果。为了解决这个问题，CART算法提出了只进行特征的二元分裂，即决策树是一棵二叉树；C4.5算法改进分裂目标函数，用信息增益比（information gain ratio）来选择特征：

因而，特征选择的过程等同于计算每个特征的信息增益，选择最大信息增益的特征进行分裂。此即回答前面所提出的第一个问题（选择较优特征）。ID3算法设定一阈值，当最大信息增益小于阈值时，认为没有找到有较优分类能力的特征，没有往下继续分裂的必要。根据最大表决原则，将最多计数的类别作为此叶子节点。即回答前面所提出的第二个问题（停止分裂条件）。

决策树生成：

ID3算法的核心是根据信息增益最大的准则，递归地构造决策树；算法流程如下：

如果节点满足停止分裂条件（所有记录属同一类别 or 最大信息增益小于阈值），将其置为叶子节点；

选择信息增益最大的特征进行分裂；

重复步骤1-2，直至分类完成。

C4.5算法流程与ID3相类似，只不过将信息增益改为信息增益比。

3. 决策树剪枝

过拟合

生成的决策树对训练数据会有很好的分类效果，却可能对未知数据的预测不准确，即决策树模型发生过拟合（overfitting）——训练误差（training error）很小、泛化误差（generalization error，亦可看作为test error）较大。下图给出训练误差、测试误差（test error）随决策树节点数的变化情况：

可以观察到，当节点数较小时，训练误差与测试误差均较大，即发生了欠拟合（underfitting）。当节点数较大时，训练误差较小，测试误差却很大，即发生了过拟合。只有当节点数适中是，训练误差居中，测试误差较小；对训练数据有较好的拟合，同时对未知数据有很好的分类准确率。

发生过拟合的根本原因是分类模型过于复杂，可能的原因如下：

训练数据集中有噪音样本点，对训练数据拟合的同时也对噪音进行拟合，从而影响了分类的效果；

决策树的叶子节点中缺乏有分类价值的样本记录，也就是说此叶子节点应被剪掉。

剪枝策略

为了解决过拟合，C4.5通过剪枝以减少模型的复杂度。[2]中提出一种简单剪枝策略，通过极小化决策树的整体损失函数（loss function）或代价函数（cost function）来实现，决策树TT的损失函数为：

其中，C(T)C(T)表示决策树的训练误差，αα为调节参数，|T||T|为模型的复杂度。当模型越复杂时，训练的误差就越小。上述定义的损失正好做了两者之间的权衡。

如果剪枝后损失函数减少了，即说明这是有效剪枝。具体剪枝算法可以由动态规划等来实现。

4. 参考资料

[1] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introduction to Data Mining .

[2] 李航，《统计学习方法》.

[3] Naren Ramakrishnan, The Top Ten Algorithms in Data Mining.