autoauto- [1. 决策树算法](#1-决策树算法)auto - [1.1. 分支处理](#11-分支处理)auto - [1.2. 基本流程](#12-基本流程)auto - [1.3. 划分选择](#13-划分选择)auto - [1.3.1. 信息增益](#131-信息增益)auto - [1.4. ID3 算法](#14-id3-算法)autoauto

决策树算法

分类算法是利用训练样本集获得分类函数即分类模型（分类器），从而实现将数据集中的样本划分到各个类中。分类模型通过学习训练样本中的属性集与类别之间的潜在关系，并以此为依据对新样本属于哪一类进行预测。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-302GlXLq-1593705732576)(./决策树/分类示意图.png)]

决策树通过把数据样本分配到某个叶子结点来确定数据集中样本所属的分类决策树由结点、分支和叶子结点组成 决策结点表示在样本的一个属性上进行的划分分支表示对于决策结点进行划分的输出叶结点代表经过分支到达的类 从决策树根结点出发，自顶向下移动，在每个决策结点都会进行次划分，通过划分的结果将样本进行分类，导致不同的分支，最后到达叶子结点，这个过程就是利用决策树进行分类的过程

分支处理

往往使用启发式算法来进行决策树的构造，例如，使用贪婪算法对每个结点构造部分最优决策树对于一个决策树的构建，最重要的部分就在于其分支处理，即确定在每个决策结点处的分支属性分支属性的选取即对决策节点上选择哪一个属性来对数据集进行划分，要求每个分支中样本的类别纯度尽可能高，而且不要产生样本数量太少的分支

基本流程

决策树的一般流程 （1）收集数据：可以用任何方法 （2）准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化 （3）分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期 （4）训练算法：构造树的数据结构 （5）测试算法：使用经验树计算错误率 （6）使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。下面给出西瓜书的基本流程算法 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FTUMdX6M-1593705732579)(./决策树/决策树学习基本算法.png)]

划分选择

决策树学习的关键是，如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)

西瓜数据集，如下图所示： [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2YfKeEFv-1593705732580)(./决策树/西瓜数据集2.0.png)]

信息增益

“信息熵”(information entropy)是度量样本集合纯度最常用的一种指标。假定当前样本集合$D$中的第$k$类样本所占的比例为$p_k(k=1,2,...,|y|$)，则$D$的信息熵定义为$$Ent(D)=-\sum _1^{|y|}{p}_k\ast lo{g}_2{p}_k$$ $Ent(D)$的值越小，则$D$的纯度越高。

假定离散属性$a$有$V$个可能的取值$\{a^1,a^2,...,a^V\}$,若使用$a$来对样本集$D$进行划分，则会产生$V$个分支结点，其中第$v$个分支结点包含了$D$中所有在属性$a$上取值为$a^v$的样本，记为$D^v$。根据上述公式计算出$D$的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重$|D^v|/|D|$，即样本数越多的分支结点的影响越大，于是可以计算出用属性$a$对样本集$D$进行划分所获得的“信息增益”(information gain) $$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$ 一般而言，信息增益越大，则意味着使用属性$a$来划分所获得的“纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择，即在算法流程的第8行选择属性$a_{\ast }=arg{\max }_{a\in A}Gain(D,a)$。著名的ID3决策树学习算法$[Quinlan,1986]$就是以信息增益为准则来选择划分属性。

下面给出对根结点信息熵的计算ID3.py

整个数据集的原始香农熵 0.998 各个属性的信息增益 色泽 = 0.108 根蒂 = 0.143 敲声 = 0.141 纹理 = 0.381 脐部 = 0.289 触感 = 0.006 纹理 的信息增益最大= 0.381

增益率

但是当每个分支结点仅包含一个样本时，这些分支结点的纯度已达到最大（如，编号列）。然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效的预测。

实际上，信息增益准则对可能取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的$C4.5$决策树算法$[Quinlan,1993]$不直接使用信息增益，而是使用“增益率”(gain ratio)来选择最优的划分属性，增益率定义为: $$GainRation(D,a)=\frac{Gain(D,a)}{IV(a)}$$ 其中 $$IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$$ 称为$a$的“固有值”$(intrinsicvalue)[Quinlan,1993].$ 属性$a$的可能取值数目越多(即$V$越大)，则$IV(a)$的值通常会很大。

需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，$C4.5$算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式$[Quinlan,1993]:$ 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

大的候选划分属性，而是使用了一个启发式$[Quinlan,1993]:$ 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。