一：决策树概述

决策树（Decision Tree）：是一种机器学习算法，广泛应用于分类和预测分析等领域。它基于树形结构进行决策，通过向下遍历该树实现对数据的分类或预测。在决策树中，每个节点表示一个特征或属性，每个分支表示该特征的一个取值，而叶子节点则表示最终的分类或者预测结果

例如在判断好瓜和坏瓜这个二分类问题上，通常会进行一系列的决策，我们可以认为色泽、根蒂、敲声是一个西瓜的三个特征，每次我们做出抉择都是基于这三个特征来把一个节点分成好几个新的节点

从上面的决策过程中我们可以看出下面几点

• 决策过程的最终结论对应了我们所希望的判定结果
• 决策过程中提出的每个判定问题都是对某个属性的测试
  • 色泽=？
  • 根蒂=？
• 每个测试的结果或是导出最终结论、或是导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内

因此，一棵决策树包含了一个根结点、若干个内部结点和若干个叶结点这三个部分，树中每个内部节点表示在一个属性特征上的测试，每个分支代表一个测试输出，每个叶节点表示一种类别

• 每个结点包含的样本集合根据属性测试结果被划分到子结点中
• 根结点包含样本全集，从根结点到每个叶结点的路径对应了一个判定预测序列

给定一个数据实例，其构造的决策树如下图

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子结点处的熵值为0，此时每个叶子结点中的实例都属于同一类。对于上面构建那一颗决策树，信息熵计算如下

• 第一层：被分为17份，8是9否；故$H_0=-[(8/17)\log 8/17+(9/17)\log 9/17]=0.998$
• 第二层：其加权信息熵为$H^{\prime }=9/17H_1+5/17H_2+3/17H_3=0.617$
  • 清晰：被分为9份，7是2否；$H_1=-[(7/9)\log 7/9+(2/9)\log 2/9]=0.764$
  • 稍糊：被分为5份，1是4否；$H_2=-[(1/5)\log 1/5+(4/5)\log 4/5]=0.722$
  • 模糊：被分为3份，0是3否；$H_3=0$

可见信息熵由0.998降低为了0.617，所以决策树状态会由不确定转变为确定

二：决策树学习基本算法

决策树学习基本算法：如下图，可见决策树的生成是一个递归过程。在该算法中，有三种情形会导致递归返回

• 当前结点包含的样本全部属于同一类别，无需划分
• 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分：此时把当前结点标记叶结点，并将其类别设定为该结点所含样本最多的类别（利用当前结点的后验分布）
• 当前结点包含的样本集合为空，不能划分：此时把当前结点标记叶结点，但将其类别设定为其父结点所含样本最多的类别（把父结点的样本分布作为当前结点的先验分布）

三：划分选择和决策树算法

由上面的算法流程图可以看出，决策树算法关键在于第8行，也即如何选择最优划分属性，常见划分准则主要有以下三种

• 信息增益（ID3算法）
• 信息增益率（C4.5算法）
• 基尼指数（CART算法）

（1）信息增益（ID3算法）

A：信息熵和信息增益

信息熵：是信息论中的一个重要概念，用于描述随机变量某种特定取值出现的不确定性程度。在信息论中，越不确定的事件，其信息熵就越高，反之则越低。 单位通常由比特（bit）来表示，而这个单位被定义为处理在随机事件中的两个等可能发生的结果所需的信息量。简单来说，信息熵可以帮助我们衡量一段文本或信号中含有多少重要和不重要的信息

假定当前样本集合$D$中第$k$类样本所占比例为$p_k(k=1,2,..,|y|)$，则$D$的信息熵定义为

$$Ent(D)=-\sum _{k=1}^{|y|}{p}_k{\log }_2{p}_k$$

$Ent(D)$的值越小，则$D$的纯度越高

---

信息增益：假定离散属性$a$有$V$个可能的取值 { a 1 , a 2 , . . , a V } \{a^{1},a^{2},..,a^{V}\} {a1,a2,..,aV}，若使用$a$来对样本集合$D$进行划分，则会产生$V$个分支结点，其中第$v$个分支结点包含了$D$中所有在属性$a$上取值为$a^v$的样本，记为$D^v$。根据上面的式子计算出$D^v$的信息熵，再考虑到不同的分支结点所包含的样本数，给分支结点赋予权重$\frac{|D^v|}{D}$，也即样本数越多的分支结点的影响越大，于是可计算出用属性$a$对样本集$D$进行划分所得的信息增益

$$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{D}Ent(D^v)$$

简单来说，信息增益=信息熵-条件熵

$$Gain(D,A)=H(D|A)$$

一般而言，信息增益越大则意味着使用属性$a$来进行划分所得到的纯度提升越大。因此我们可以用信息增益来进行决策树的画风属性选择，也即

$$a_{\ast }=\underset{a\in A}{\mathrm{argmax}}Gain(D,a)$$

著名的ID3决策树学习算法正是以信息增益为准则来划分属性的

B：例子说明

• 此部分内容借助《周志华·机器学习》内容

C：ID3算法

①：简介

ID3算法：ID3算法以信息增益为准则来选择特征，递归的构建决策树。具体来说，它会从根结点开始，对结点计算所有可能的属性的信息增益，选择信息增益最大的属性作为划分属性，由该属性的不同取值建立子结点，再对子结点递归地调用上面步骤，直到所有属性的信息增益均很小或没有属性可选择为止。流程如下

• 找到最优特征（信息增益值最高）
• 最优特征、特征值作为有向边，判断子数据集
  • 全部是同一类：输出叶子结点
  • 如果有多类
    • 如果子数据集中还有特征，那么再次寻找最优特征
    • 如果子数据集中只剩下最后的分类结果了，那么输出最多的一类作为叶子节点
• 直到叶子节点全部输出，或者无数据可遍历

②：例子

如下，有过去几天天气状况的记录，我们需要根据这些记录，利用ID3算法习得一棵决策树，用于预测在特定天气状况下是否应该打球

首先计算分类结果Play（yes/no）的熵

$$H(play)=-(\frac{9}{14}\ast {\log }_2\frac{9}{14}+\frac{5}{14}\ast {\log }_2\frac{5}{14})\approx 0.93$$

接着，我们要计算出当前属性集合{Outlook、Temp、Humidity、Wind}中每个属性的信息增益，这里以Outlook为例。它有3个可能的取值：{sunny, overcast, rain}

计算如下

$$H(play|Outlook=sunny)=-(\frac{2}{5}\ast {\log }_2\frac{2}{5}+\frac{3}{5}\ast {\log }_2\frac{3}{5})\approx 0.97$$

$$H(play|Outlook=overcast)=-(1\ast {\log }_{2}1)=0$$

$$H(play|Outlook=rain)=-(\frac{3}{5}\ast {\log }_2\frac{3}{5}+\frac{2}{5}\ast {\log }_2\frac{2}{5})\approx 0.97$$

据此，可计算出属性Outlook的信息增益为

$$G(Play,Outlook)=0.93-(\frac{5}{14}\ast 0.97+\frac{4}{14}\ast 0+\frac{5}{14}\ast 0.97)=0.93-0.69=0.24$$

同理，其他属性的信息增益为

• $G(Play,Temp)=0.93-0.91=0.02$
• $G(Play,Humidity)=0.93-0.79=0.14$
• $G(Play,Wind)=0.93-0.89=0.04$

现在，我们已经找到第一个判断的条件了，其中

• 当outlook是sunny的时候，还无法下结论
• 当outlook是overcast的时候，因为此时属性只有一个取值，所以可以下结论去打球
• 当outlook是rain的时候，还无法下结论

现在，我们需要在sunny条件下（去掉sunny这条属性），再次进行计算

• $G(Play,Temp)=H(Play)-H(Play|Temp)=0.97-0.95=0.02$
• $G(Play,Humidity)=H(Play)-H(Play|Humidity)=0.97-0=0.97$
• $G(Play,Wind)=H(Play)-H(Play|Wind)=0.97-0.95=0.02$

同理，在rain条件下（去掉rain这条属性），再次进行计算

• $G(Play,Humidity)=H(Play)-H(Play|Humidity)=0.97-0.95=0.02$
• $G(Play,Temp)=H(Play)-H(Play|Temp)=0.97-0.95=0.02$
• $G(Play,Wind)=H(Play)-H(Play|Wind)=0.97-0=0.97$

于是，最终构建如下决策树

③：缺点

缺点：

• ID3算法只能处理离散的特征值，无法处理连续的特征值
• uID3算法构建的决策树，会有过拟合问题（Overfitting）

（2）信息增益率（C4.5算法）

A：信息增益的缺点

ID3算法所采用的划分准则为信息增益，但其存在以下缺点

• 对取值数目较多的属性有偏好：信息增益会偏好于取值数目较多的属性，因为它们可以更细致地划分数据集。但是这些属性可能并不是最优划分属性，因为它们过于具体和细节化，而忽略了属性间的相关性
• 忽略属性的相互作用：信息增益只考虑每个属性对类别标签的贡献，并忽略了多个属性之间的相互作用。例如，在某些情况下，两个看似无关的属性可能会共同对结果产生重大影响，但是信息增益无法识别这种相互作用

假设有一个二元分类问题，其中有两个特征$X_1$和$X_2$​，其取值如下表所示

样本编号	$X_1$	$X_2$​	类别
1	0	0	1
2	0	1	1
3	0	1	1
4	1	0	0
5	1	1	0

如果使用信息增益作为划分准则，会发现$X_2$​是最优划分属性。但是实际上，如果考虑$X_1$​和$X_2$​之间的相互作用，可以发现它们对结果都有一定的贡献，因此应该选择将它们同时考虑作为划分条件

B：信息增益率

信息增益率：定义如下

$$\text{GainRatio}(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$的固有值。属性$a$的可能取值数目越多（也即$V$越大），则$IV(a)$通常会越大，例如西瓜数据集中

• $IV(\text{触感})=0.874$，其中$V=2$
• $IV(\text{色泽})=1.580$，其中$V=3$
• $IV(\text{编号})=4.088$，其中$V=17$

C：C4.5算法

①：简介

C4.5算法：与ID3算法相比，C4.5算法增加了处理连续型特征、缺失值等问题的能力，同时在生成决策树时使用信息增益率来选择最佳分裂属性，避免了ID3算法对可取值数目较多的特征偏好的问题。需要注意的是，信息增益率准则可能又会对取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的作为候选划分属性，而是使用了一个启发式规则：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

C4.5算法流程如下

②：例子

仍以下表数据为例说明C4.5算法构建决策树

首先我们需要计算各个属性的信息增益，这里不再重复，数据如下

• $G(Play,Outlook)=0.93-0.69=0.24$
• $G(Play,Temp)=0.93-0.91=0.02$
• $G(Play,Humidity)=0.93-0.79=0.14$
• $G(Play,Wind)=0.93-0.89=0.04$

然后计算属性固有值

• $IV(Outlook)=-(\frac{5}{14}{\log }_2\frac{5}{14}+\frac{4}{14}{\log }_2\frac{4}{14})+\frac{5}{14}{\log }_2\frac{5}{14})=1.58$
• $IV(Temp)=1.56$
• $IV(Humidity)=1.0$
• $IV(Wind)=0.99$

接着计算信息增益率

• $GainRatio(Outlook)=\frac{0.24}{1.58}=0.15$
• $GainRatio(Temp)=\frac{0.02}{1.56}=0.01$
• $GainRatio(Humidity)=\frac{0.14}{1.0}=0.14$
• $GainRatio(Wind)=\frac{0.04}{0.99}=0.04$

可以看到，"Outlook"信息增益率最大，所以将其作为决策树的根节点

重复上述过程即可

③：连续值处理

什么是连续值和离散值

• 离散值：Hot、Cool
• 连续值：27.2、26.8、21.5

由于连续属性的可取值数目不再有限，因此不能直接根据连续属性的可取值来对结点进行划分。C4.5算法会采用如下两种方法对连续属性进行处理

• 二分离散化：首先将数据集按照属性值从小到大排序，然后遍历每个属性值，找到它中间的值作为阈值，同时在当前位置新建一个划分或分裂节点，左子树包含值小于等于阈值的样本数据，右子树则包含大于阈值的样本数据。如此递归下去，构建出一个包含多个节点的决策树
• 基于信息增益的离散化：C4.5算法采用信息增益来评估每个划分点的好坏程度。其基本思路是将连续变量V映射到区间{[a1, b1], [a2, b2], … [ak, bk]}上，其中ai < bi，再计算每个候选区间的信息增益，选择增益最大的区间，以该区间边界处的值作为分裂点进行离散化

这里我们对二分离散化进行说明：给定样本集$D$和连续属性$a$，假定$a$在$D$上出现了$n$个不同的取值，将这些值从小到大进行排序，记为 { a 1 , . . . , a n } \{a^{1},...,a^{n}\} {a1,...,an}。基于划分点$t$可将$D$分为子集$D_t^{-}$和$D_t^{+}$，其中$D_t^{-}$包含那些在属性$a$上取值不大于$t$的样本、而$D_t^{+}$则包含那些在属性$a$上取值大于$t$的样本。显然，对相邻的属性取值$a^i$与$a^{i+1}$来说，$t$在区间$[a^i,a^{i+1}]$中取任意值所产生的划分结果相同。因此，对连续属性$a$，我们可考察包含$n-1$个元素的候选划分点集合

T a = { a i + a i + 1 2 ∣ 1 ≤ i ≤ n − 1 } T_{a}=\{\frac{a^{i}+a^{i+1}}{2}|1\leq i\leq n-1\} Ta​={2ai+ai+1​∣1≤i≤n−1}

即把区间$[a^i,a^{i+1}]$的中位点$a^i+\frac{a^{i+1}}{2}$作为候选划分点。然后，我们可像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分

这里我们借用西瓜书的例子

④：缺失值处理

在现实任务中，我们可能经常会遇到属性值缺失这种情形。如果简单放弃不完整样本，仅仅使用无缺失值的样本来进行学习，显然是不太可取的，一方面会造成信息的极大浪费，一方面少数数据不足以代表整体情况

ID3算法不能处理缺失值，而C4.5算法可以处理缺失值（常用概率权重方法），主要有三种情况

• 在有缺失值的特征上如何计算信息增益率？
  • 计算某属性的信息増益率时忽略掉缺失了此属性的样本
  • 通过此属性的样本中出现频率最高的属性值，赋值给缺失了此属性的样本
• 选定了划分属性，若样本在该属性上的值是缺失的，那么如何对这个样本进行划分？
  • 不处理那些属性未知的样本，即简单的忽略它们
  • 根据属性的其他样本的取值，来对未知样本进行赋值
  • 为缺失属性的样本单独创建一个分支，不过这种方式得到的决策树模型结点数显然要増加，使模型更加复杂了
• 对新的样本进行分类时，如果测试样本特性有缺失值如何判断其类别？
  • 待分类样本在到达属性的分支结点时即可结束分类过程，此样本所属类别为属性的子树中概率最大的类别
  • 把待分类样本的属性赋予一个最常见的值，然后继续分类过程

⑤：缺点

缺点：

• 过拟合：C4.5 可能会过度拟合训练数据，导致对新数据的泛化能力较差。 当算法构建的决策树过于复杂且特定于训练数据，而不是捕获数据中的潜在模式和关系时，就会发生过度拟合。于追求信息增益最大，可能会将一些无用的分支加入树中，导致模型复杂度过高，容易发生过拟合
• 对噪声数据的敏感性：C4.5 对噪声数据敏感，这可能导致次优分割和错误决策。 噪声数据是指包含错误、异常值或不一致值的数据，它们会扭曲数据中的模式和关系
• 计算密集型：C4.5 需要大量的计算资源，并且在大型数据集上进行训练可能非常耗时

（3）基尼指数（CART算法）

A：基尼指数

基尼指数：无论是ID3还是C4.5，都是基于信息论的熵模型的，其中会涉及大量的对数运算，并且信息增益和信息增益率更容易受数据集中样本分布不均或者其中某个类别占据主导地位的影响，可能会导致生成的决策树偏向于该类别。CART算法采用基尼指数来选择划分属性，对于数据集$D$，其基尼指数定义如下

• $\mathcal{Y}$表示数据集中所有类别
• $p_k$表示第$k$个类别在数据集$D$中所占比例

$$\begin{array}{rl}\mathrm{Gini}(D)& =\sum _{k=1}^{|\mathcal{Y}|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}=1-\sum _{k=1}^{|\mathcal{Y}|}{p}_k^2\end{array}$$
基尼指数可以理解为：从数据集$D$中随机选择两个样本，它们属于不同类别的概率，因此基尼指数越小说明数据集纯度越高

在属性$a$的条件下，数据集$D$基尼指数定义为

$$\text{Gini\_index(D,a)}=\sum _{v=1}^V\frac{D^v}{D}\text{Gini}(D^v)$$

因此，我们在候选属性集合$A$中，应选择那个使得划分后基尼指数最小的属性作为最优划分属性，也即

$$a_{\ast }=\underset{a\in A}{\mathrm{argmin}}\text{Gini\_index(D,a)}$$

B：CART算法

①：简介

CART算法：CART是Classification and Regression Trees（分类回归树）的缩写，它采用基尼系数或均方误差来选择划分属性。同时注意，为了进一步简化，CART分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树

输入：训练数据集$D$，停止计算的条件为

• 结点中的样本个数小于预定阈值
• 样本集的基尼指数小于预定阈值（样本基本属于同一类）
• 没有更多特征
  输出：CART决策树
  根据训练数据集，从根节点开始，递归地对每个结点进行以下操作，构建决策树

1. 设结点的训练数据集为$D$，计算现有特征对该数据集的基尼指数。此时，对每一个特征$A$，对其每个可能取值$a$，根据样本点对$A=a$的测试为“是”或“否”，将$D$分割为$D_1$和$D_2$两部分，然后计算基尼指数
2. 在所有可能的特征$A$以及它们所有可能的切分点$a$中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中
3. 对两个子结点递归调用1和2，直至满足停止条件
4. 生成CART决策树

②：例子

如下数据，样本特征有三个分别为“是否有房”、“婚姻状况”和“年收入”，“是否拖欠贷款”是分类结果

序号	是否有房	婚姻状况	年收入	是否拖欠贷款
1	是	单身	125K	否
2	否	已婚	100K	否
3	否	单身	70K	否
4	是	已婚	120K	否
5	否	离婚	95K	是
6	否	已婚	60K	否
7	是	离婚	220K	否
8	否	单身	85K	是
9	否	已婚	75K	否
10	否	单身	90K	是

对于“是否有房”这个特征，他是一个二分类离散数据，其基尼系数为

$$Gini=\frac{3}{10}Gini(有房)+\frac{7}{10}Gini(无房)=\frac{3}{10}(1-((\frac{3}{3}{)}^2+(\frac{0}{3}{)}^2)+\frac{7}{10}(1-((\frac{4}{7}{)}^2+(\frac{3}{7}{)}^2)=0.343$$

对于“婚姻状况”这个有三个取值的离散型特征，它有三种分类情况

• $Gini=\frac{2}{10}Gini(离婚)+\frac{8}{10}Gini(单身或已婚)=0.4$
• $Gini=\frac{4}{10}Gini(离婚)+\frac{6}{10}Gini(单身或离婚)=0.3$
• $Gini=\frac{4}{10}Gini(单身)+\frac{6}{10}Gini(已婚或离婚)=0.3677$

对于“收入”这个连续型数据，需要进行处理，转换为离散型才可以计算，其处理方法和C4.5基本一致。如下，通过计算我们得知当以97K作为分类点时其基尼系数最小，所以选择它作为该特征的二元分类点

通过比较得知，发现“离婚”作为婚姻状况的分类点和97K作为收入的分类点基尼系数一样，所以我们任选其一作为最优特征的最优切分点。如下图，这里选择“婚姻状况”作为最优特征，“离婚”作为最优切分点，构造决策树，然后递归处理

③：回归树

CART回归树和分类树的建立过程大致相似，区别在于样本输出，如果输出的是离散值，那么这是一棵分类树，如果输出的是连续值，那么这是一棵回归树。回归树对于连续性数据采用了均方误差来度量，其度量目标是：对于任意划分特征$A$，对应的任意划分点$s$两边划分成的数据集$D_1$和$D_2$，求出使$D_1$和$D_2$各自集合的均方误差最小，同时$D_1$和$D_2$的均方误差之和最小所对应的特征和特征值划分点

$$\underset{A,s}{\underbrace{\min }}[\underset{c1}{\underbrace{\min }}\sum _{x_i\in D_1(A,s)}{\left(y_i-c_1\right)}^2+\underset{c2}{\underbrace{\min }}\sum _{x_i\in D_2(A,s)}{\left(y_i-c_2\right)}^2]$$

四：代码示例-鸢尾花分类

• 这里我们以构建CART树为例来展示鸢尾花分类这个案例

鸢尾花数据集，这是一个常用的机器学习数据集，其中包含150个样本和4个特征（花萼长度、花萼宽度、花瓣长度和花瓣宽度），以及每个样本对应的类别（Setosa、Versicolor或Virginica）

决策树实现如下

import numpy as np
from sklearn.datasets import load_iris

iris = load_iris()
X = iris.data
y = iris.target

# 计算基尼系数
def calculate_gini(y):
    n = len(y)
    _, counts = np.unique(y, return_counts=True)
    p = counts / n
    gini = 1 - np.sum(p**2)
    return gini

# 利用基尼系数找寻最优分裂点
def find_split(X, y):
    best_feature = None
    best_value = None
    best_gini = 1.0
    
    for feature in range(X.shape[1]):
        # 将特征值从小到大排序
        values = np.sort(X[:, feature])
        for i in range(1, len(values)):
            # 计算分裂点
            value = (values[i-1] + values[i]) / 2
            # 分裂数据集
            left = y[X[:, feature] < value]
            right = y[X[:, feature] >= value]
            # 计算Gini指数
            gini = (len(left) * calculate_gini(left) + len(right) * calculate_gini(right)) / len(y)
            # 更新最优分裂点
            if gini < best_gini:
                best_feature = feature
                best_value = value
                best_gini = gini
                
    return best_feature, best_value

# 决策树节点定义
class Node:
    def __init__(self, X, y):
        self.X = X
        self.y = y
        self.feature = None
        self.value = None
        self.left = None
        self.right = None

"""
决策树递归构建：对于每个节点，我们都会寻找最优分裂点并将数据集分成两个子集
如果子集中的样本全部属于同一类别，则将该节点标记为叶节点，并将其类别标记为该类别
否则，我们将递归地对子集进行划分，直到达到预定的停止条件为止
"""
def build_tree(node, max_depth, min_samples_split):
    X, y = node.X, node.y
    
    # 停止条件：达到最大深度或样本数量小于最小分裂样本数
    if max_depth <= 0 or len(y) < min_samples_split:
        node.feature = None
        node.value = np.argmax(np.bincount(y))
        return
    
    # 停止条件：所有样本属于同一类别
    if np.all(y == y[0]):
        node.feature = None
        node.value = y[0]
        return
    
    # 寻找最优分裂点
    feature, value = find_split(X, y)
    if feature is None or value is None:
        node.feature = None
        node.value = np.argmax(np.bincount(y))
        return
    
    # 分裂数据集
    left_X, left_y = X[X[:, feature] < value], y[X[:, feature] < value]
    right_X, right_y = X[X[:, feature] >= value], y[X[:, feature] >= value]
    
    # 停止条件：分裂后的子集中有一个为空
    if len(left_y) == 0 or len(right_y) == 0:
        node.feature = None
        node.value = np.argmax(np.bincount(y))
        return
    
    # 递归构建左子树和右子树
    node.feature = feature
    node.value = value
    node.left = Node(left_X, left_y)
    node.right = Node(right_X, right_y)
    build_tree(node.left, max_depth-1, min_samples_split)
    build_tree(node.right, max_depth-1, min_samples_split)

# 训练和预测
def fit(X, y, max_depth=3, min_samples_split=2):
    """训练决策树"""
    root = Node(X, y)
    build_tree(root, max_depth, min_samples_split)
    return root

def predict(node, x):
    """对新样本进行分类"""
    if node.left is None and node.right is None:
        return node.value
    if x[node.feature] < node.value:
        return predict(node.left, x)
    else:
        return predict(node.right, x)

训练和预测

# 将数据集划分为训练集和测试集
np.random.seed(42)
indices = np.random.permutation(len(X))
train_indices, test_indices = indices[:100], indices[100:]

X_train, y_train = X[train_indices], y[train_indices]
X_test, y_test = X[test_indices], y[test_indices]

# 训练决策树
tree = fit(X_train, y_train)

# 对测试集进行预测
y_pred = [predict(tree, x) for x in X_test]

# 计算准确率
accuracy = np.mean(y_pred == y_test)
print("Accuracy:", accuracy)

效果可视化

import matplotlib.pyplot as plt

# 绘制训练集和测试集
plt.scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap="rainbow", edgecolor="k", alpha=0.7)
plt.scatter(X_test[:, 0], X_test[:, 1], c=y_test, cmap="rainbow", marker="x", edgecolor="k")

# 绘制分类正确和分类错误的样本
correct_indices = np.where(y_pred == y_test)[0]
incorrect_indices = np.where(y_pred != y_test)[0]
plt.scatter(X_test[correct_indices, 0], X_test[correct_indices, 1], marker="o", s=100, edgecolor="k", facecolor="none")
plt.scatter(X_test[incorrect_indices, 0], X_test[incorrect_indices, 1], marker="x", s=100, edgecolor="k", facecolor="none")

# 绘制决策边界
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.1),
                     np.arange(y_min, y_max, 0.1))
Z = np.array([predict(tree, np.array([x1, x2])) for x1, x2 in np.c_[xx.ravel(), yy.ravel()]])
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, alpha=0.3, cmap="rainbow")

plt.xlabel("Feature 1")
plt.ylabel("Feature 2")
plt.title("Decision Tree Visualization")
plt.show()

五：剪枝处理

剪枝：剪枝是决策树学习算法应对过拟合的手段。具体来说，在决策树学习中将已生成的树进行简化的过程称为剪枝，剪枝会从从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。决策树剪枝有以下两种策略

• 预剪枝： 在构建决策树时就开始进行剪枝，具体实现方式为设定一个阈值，当决策树生长到一定层数或某个节点的样本数量小于阈值时，就停止分裂，将该节点转化为叶子节点并进行剪枝
• 后剪枝： 决策树构建完成后，对已有叶子节点进行剪枝，具体实现方式为对每个叶子节点进行剪枝，并对剪枝前后的性能进行比较，若剪枝后性能有所提升，则保留剪枝结果

（1）预剪枝

预剪枝：预剪枝是一种在构建决策树时就开始对其进行剪枝的方法，它在构建决策树阶段之前，通过预先设定一个阈值或某个判断条件，停止树的分裂。具体来说，预剪枝会在每个节点处考虑是否将该节点转化为叶子节点，从而使得整个决策树更加精简且避免过度拟合。常用的预剪枝技术包括

• 最大深度限制：在构建决策树时规定其最大深度，到达该深度后即停止继续分裂并转换为叶子节点。
• 最小样本数限制：当某个节点的样本数小于预设阈值时，停止对该节点分裂，将其转化为叶子节点。
• 信息增益/增益比阈值限制：计算每个节点的信息增益或信息增益比，如果小于设定的阈值则停止分裂。
• 错误率限制：计算每个节点的预测错误率，如果该节点的错误率高于设定的阈值，则停止分裂

这里借用周志华机器学习的例子来说明预剪枝

预剪枝优缺点如下

• 优点
  • 预剪枝易于实现，计算速度快
  • 预剪枝可以在构建决策树的过程中尽早地停止无效的分裂操作，避免生成过于复杂的决策树
  • 预剪枝通常更容易提高模型泛化性能
• 缺点
  • 预剪枝在决策树构建时进行特征选择，可能没有利用所有可用的数据信息，导致欠拟合
  • 预剪枝中节点划分所依赖的信息增益、基尼指数等指标容易受到样本不平衡的影响，容易导致决策树过度依赖某些特征或者产生偏差
  • 预剪枝需要根据经验或者调参来设置阈值，设置不当可能导致模型过于简单或者过于复杂

（2）后剪枝

后剪枝：后剪枝是指在生成决策树之后，通过对决策树进行修剪来防止其过拟合的一种方法。后剪枝的基本思想是先构建一棵完整的决策树，然后从下往上考虑每一个节点，计算剪枝该节点会对验证集准确率的影响。如果剪枝后的决策树性能没有损失，那么就剪枝该节点，将其转化为叶子节点。常用的后剪枝方法包括

• 错误率降低剪枝：对于每个非叶节点，计算对应子树上的验证集分类错误率，与剪枝后的错误率比较，如果剪枝后错误率更小，则进行剪枝操作
• Chi-squared剪枝：计算每个节点的卡方值，向上遍历树，如果父节点可以被替代成当前节点，并且替换后决策树效果不差，则进行替换操作
• Minimum Description Length（MDL）剪枝：先计算出生成的决策树的编码长度，然后再计算出以叶节点表示样本的编码长度，若二者大小相近，则认为当前子树可被剪枝

这里借用周志华机器学习的例子来说明后剪枝

后剪枝优缺点如下

• 优点
  • 后剪枝相对于预剪枝更加灵活，在构造完整决策树之后再进行修剪，可以综合考虑全局信息，避免过拟合
  • 后剪枝可以利用全部数据集的信息，避免预剪枝中由于样本不平衡导致的偏差
  • 后剪枝通常可以提升模型泛化性能
• 缺点
  • 后剪枝计算时间较长，需要跑完整个决策树之后再进行修剪
  • 如果样本数量过少，可能并不是很有用，因为有效的分裂节点可能非常少

六：总结

决策树是一种常用的机器学习方法，可用于分类和回归问题。它将数据集递归分解成规模越来越小的子集，并且每个子集都通过应用某些规则进行重新分解，直到每个子集都只包含具有相同标签或输出值的样本点

• 决策树优点
  • 易于理解和解释：对人类而言，决策树是一种很自然的表示，容易可视化
  • 可处理多类型属性：决策树可以在多种形式的数据上进行操作
  • 能够处理缺失值：决策树不会被缺失数据点所困扰
  • 具有非线性可分离特点：决策树可以处理非线性特征之间的相互影响关系
• 决策树缺点
  • 容易出现过拟合：决策树构建时可能会生成过于复杂的树，导致模型出现过拟合现象
  • 欠拟合：模型过于简单时，无法捕捉数据的真实分布和特征之间的复杂关系
  • 不稳定性：对于相似的数据，可能因为少量信息的变化产生完全不同的树形结构
  • 不能处理高维数据：当特征数量非常大时，决策树的性能可能会降低

决策树应用

• 医学领域：使用决策树分类算法可以预测疾病风险、制定治疗计划等
• 金融领域：使用决策树分类算法可以识别风险客户，制定风险管理措施
• 销售和营销领域：使用决策树分类算法可以识别最有可能购买产品的潜在客户，从而对客户进行更好的定位和营销
• 工业生产领域：使用决策树回归算法可以预测工业生产的产量和产品质量
• 自然语言处理领域：使用决策树分类算法可以对文本进行分类、情感分析等
• 图像识别领域：使用决策树分类算法可以对图像进行分类、物体识别等