面试题详解

什么是决策树？

决策树是一种用于分类和回归任务的非参数监督学习算法。目标是构建一个模型，使用从数据属性派生的基本决策规则来预测目标变量的值。

它是由根节点、分支、内部节点和叶节点组成的分层树结构。

与决策树相关的术语

image-20231026111032080

  1. 根节点： 它代表整个总体或样本，并进一步分为两个或多个同质集。
  2. 分裂： 是将一个节点划分为两个或多个子节点的过程。
  3. 决策节点： 当一个子节点分裂为更多子节点时，则称为决策节点。
  4. 叶子/终端节点： 不分裂的节点称为叶子或终端节点。
  5. 剪枝： 当我们删除一个决策节点的子节点时，这个过程称为剪枝。你可以说分裂的相反过程。
  6. 分支/子树： 整个树的一个子部分称为分支或子树。
  7. 父节点：任意两个相连的节点中，层次较高的一个为父节点。
  8. 子节点：任意两个相连的节点中，层级较低的一个为子节点。
一个案例

让我们通过一个例子来进行说明。

我们有如下一个数据集，该数据集仅包含四个变量：“日”、“温度”、“风” 和 “玩耍？”。

根据任意一天的气温和风向，结果是二元的，要么出去玩，要么呆在家里。

让我们使用这些数据构建决策树：

image-20231026105336817

image-20231026105434220

从上面的可视化中，请注意决策树首先在变量“温度”上分裂。当温度达到极限时它也会停止分裂，并表示我们不应该出去玩。

只有当温度温和时，它才会开始在第二个变量上分裂。

这些观察引出了以下问题：

  1. 决策树如何决定第一个要分割的变量？
  2. 如何决定何时停止分裂？
  3. 构建决策树的顺序是什么？

aaa

如何构建一个决策树？

如何从表格数据构建决策树？该选择哪个特征作为根节点？节点分裂的依据是什么？

属性选择

如果数据集由 N 个 属性组成，那么决定将哪个属性放置在根或树的内部节点是一个复杂的步骤。

仅随机选择任意节点作为根并不能解决问题。如果我们采用随机方法，可能会产生精度较低的不良结果。

为了解决这个属性选择问题，研究人员努力并设计了一些解决方案。他们建议使用一些标准，例如：熵、信息增益、基尼指数、增益比、方差减少。

这些标准将计算每个属性的值。对值进行排序，并按顺序将属性放置在树中，即具有高值的属性（在信息增益的情况下）放置在根处。

在使用信息增益作为标准时，我们假设属性是分类的，而对于基尼指数，假设属性是连续的。

熵

熵是我们数据集中的不确定性或无序度的度量，熵越高，从该信息中得出任何结论就越困难。

熵值的范围为 0 到 1。值为 0 表示纯分裂，值为 1 表示不纯分裂。

image-20231026114512481

从上图可以很明显地看出，当概率为 0 或 1 时，熵 H(X) 为零。当概率为 0.5 时，熵最大，因为它在数据中投射了完美的随机性。

计算熵的公式如下所示： $$ H(S) = \sum_{i=1}^{c} -p_i \log_2 p_i $$ image-20231026115057663

aaa

信息增益

信息增益是熵的减少。它根据给定的属性值计算数据集分割前的熵与分割后的平均熵之间的差异。

决策树算法 ID3 就是使用信息增益。 $$ g(Y,X) = H(Y) - H(Y|X) $$ 为了更好地理解这一点，让我们考虑一个例子：

假设我们的整个群体总共有 30 个实例。该数据集用于预测该人是否会去健身房。假设有 16 人去健身房，14 人不去。

现在我们有两个特征来预测他/她是否会去健身房。

  • 特征1是 “能量”，它有两个值 “高”和 “低”。
  • 特征2是 “动机”，有“无动机”、“中立” 和 “高度动机” 3个值。

让我们看看如何使用这两个功能来制作我们的决策树。

我们将使用信息增益来决定哪个特征应该是根节点以及哪个特征应该放置在分割之后。

image-20231026135557378

我们来计算一下熵： $$ E(Parent) = - \left( \frac{16}{30} \right) \log_2 \left( \frac{16}{30} \right) - \left( \frac{14}{30} \right) \log_2 \left( \frac{14}{30} \right) \approx 0.99 \

E(Parent|Energy = "high") = - \left( \frac{12}{13} \right) \log_2 \left( \frac{12}{13} \right) - \left( \frac{1}{13} \right) \log_2 \left( \frac{1}{13} \right) \approx 0.39 \

E(Parent|Energy = "low") = - \left( \frac{4}{17} \right) \log_2 \left( \frac{4}{17} \right) - \left( \frac{13}{17} \right) \log_2 \left( \frac{13}{17} \right) \approx 0.79 $$ 要查看每个节点的加权平均熵，我们将执行以下操作： $$ E(Parent|Energy) = \frac{13}{30} \times 0.39 + \frac{17}{30} \times 0.79 = 0.62 $$ 现在我们有了 E(Parent) 和 E(Parent|Energy) 的值，信息增益将是： $$ Information Gain = E(parent) - E(parent|energy)

= 0.99 - 0.62

= 0.37 $$ 如果我们将 “Energy” 作为根节点，数据集的熵将减少 0.37。

同样，我们将对另一个特征 “动机” 执行此操作并计算其信息增益。

image-20231026135529259

我们来计算一下这里的熵： $$ E(Parent) = 0.99 \

E(Parent|Motivation='No motivation') = -(\frac{7}{8}) \log_2(\frac{7}{8}) - (\frac{1}{8}) \log_2(\frac{1}{8}) = 0.54 \

E(Parent|Motivation='Neutral') = -(\frac{4}{10}) \log_2(\frac{4}{10}) - (\frac{6}{10}) \log_2(\frac{6}{10}) = 0.97 \

E(Parent|Motivation='Highly motivated') = -(\frac{5}{12}) \log_2(\frac{5}{12}) - (\frac{7}{12}) \log_2(\frac{7}{12}) = 0.98 $$ 要查看每个节点的加权平均熵，我们将执行以下操作： $$ E(Parent|Motivation) = \frac{8}{30} \times 0.54 + \frac{10}{30} \times 0.97 + \frac{12}{30} \times 0.98 = 0.86 $$ 现在我们有了 E(Parent) 和 E(Parent|Motivation) 的值，信息增益将是： $$ Information Gain = E(Parent) - E(Parent|Motivation)

= 0.99 - 0.86

= 0.13 $$ 我们将选择具有最高信息增益的特征，然后根据该特征分割节点。

在此示例中，“Energy” 将是我们的根节点，我们将对子节点执行相同的操作。

信息增益的算法

输入：训练数据集D和特征A；

输出：特征A对训练集D的信息增益g(D,A)。

（1）计算数据集D的经验熵H(D) $$ H(D) = - \sum_{k=1}^{K} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|} $$ （2）计算特征A对数据集D的经验条件熵H(D|A) $$ H(D|A) = \sum_{i=1}^{n} \frac{|D_i|}{|D|} H(D_i) = \sum_{i=1}^{n} \frac{|D_i|}{|D|} \sum_{k=1}^{K} \frac{|D_{ik}|}{|D_i|} \log_2 \frac{|D_{ik}|}{|D_i|} $$ （3）计算信息增益 $$ g(D, A) = H(D) - H(D|A) $$

信息增益比

信息增益偏向于选择取值较多的属性作为根节点。这意味着它更喜欢具有大量不同值的属性。

C4.5 是 ID3 的改进，使用增益比，它是信息增益的修改，可以减少其偏差，通常是最佳选择。

增益比通过考虑分裂之前产生的分支数量来克服信息增益的问题。它通过考虑分裂的内在信息来校正信息增益。

信息增益比的定义

特征 A 对训练数据D的信息增益比定义为其信息增益g(D,A)与其训练数据集D关于特征A的熵之比，即 $$ gR(D, A) = \frac{g(D, A)}{H_A(D)} $$ 其中，\(\(H_A(D) = - \sum_{i=1}^{n} \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}\)\)，n 是特征A取值的个数。

上式表明，一个特征的取值越多，则其本身的熵越大。

C4.5 算法使用信息增益比。

基尼指数

CART 决策树使用 “基尼指数”（Gini index）来选择划分属性。

数据集 D 的纯度可以用基尼指数来度量：

分类问题中，假设有 K 个类，样本点属于第 k 类的概率为 \(p_k\)，则概率分布的基尼指数定义为 $$ \text{Gini}(D) = \sum_{k=1}^{K} \sum_{k' \neq k} p_k p_{k'} \

= \sum_{k=1}^{K} p_k (1 - p_k) \

= 1 - \sum_{k=1}^{K} p_k^2 $$ 直观的来说，Gini(D) 反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。

因此，Gini(D)越小，则数据集D的纯度越高。

对于给定的样本集合D，其基尼指数为： $$ \text{Gini}(D) = 1 - \sum_{k=1}^{K} \left( \frac{|C_k|}{|D|} \right)^2 $$ 这里，Ck 是 D 中属于第 k 类的样本子集，K 是类的个数。

如果样本集合 D 根据特征 A 是否取某一可能值 a 被分割成 \(D_1\) 和 \(D_2\) 两部分，则在特征 A 的条件下，集合 D 的基尼指数定义为: $$ \text{Gini}(D, A) = \frac{|D_1|}{|D|} \text{Gini}(D_1) + \frac{|D_2|}{|D|} \text{Gini}(D_2) $$ 基尼指数 Gini(D) 表示集合 D 的不确定性，基尼指数 Gini(D,A) 表示经 A=a 分割后，集合的不确定性。

尼基指数越大，样本的集合不确定性越大，这一点与熵类似。

简单描述一下决策树的生成算法 ID3、 C4.5、CART

决策树使用多种算法来决定将一个节点拆分为两个或多个子节点。子节点的创建增加了所有子节点的同质性。换句话说，我们可以说节点的纯度相对于目标变量有所增加。

决策树中常用的算法有

  • ID3 →（D3 的扩展）
  • C4.5 →（ID3 的后继）
  • CART →（分类和回归树）
ID3

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

具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或者没有特征可以选择为止。最后得到一颗决策树。

ID3算法

输入：训练数据集 D，特征集 A，阈值 ε；

输出：决策树 T。

（1）若 D 中所有实例属于同一类 \(C_k\)，则 T 为单结点树，并将类 \(C_k\) 作为该结点的类标记，返回 T；

（2）若 A=Ø，则 T 为单结点树，并将 D 中实例数最大的类 \(C_k\) 作为该结点的类标记，返回 T；

（3）否则，计算A中每个特征对 D 的信息增益，选择信息增益最大的特征 \(A_g\)；

（4）如果特征 \(A_g\) 的信息增益小于阈值 ε，则置 T 为单结点树，并将 D 中实例数最大的类 \(C_k\) 作为该结点的类标记，返回 T；

（5）否则，对 \(A_g\) 的每一可能值 \(a_i\)，依 \(A_g=a_i\) 将 D 分割为若干非空子集 \(D_i\)，将 \(D_i\) 中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树 T，返回 T；

（6）对第 i 个子结点，以 \(D_i\) 为训练集，以 \(A - A_g\) 为特征集，递归地调用步（1）到步（5），得到子树 \(T_i\)，返回 \(T_i\)

ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。

C 4.5

C 4.5 算法与 ID3 算法相似，C4.5 算法对 ID3 算法进行了改进。

C4.5 在生成过程中，使用信息增益比来选择特征。

CART 算法

分类与回归树（CART）即可用于分类，也可用于回归。

CART 假设决策树是二叉树，内部结点特征的取值是 “是” 和 “否”，左分支是取值为 “是” 的分支，右分支是取值为 “否” 的分支，这样的决策树等价于递归地二分每个特征，将特征空间划分为有限个单元。

CART 算法由以下两步组成：

（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；

（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

CART 生成

决策树的生成就是递归地构建二叉决策树的过程。

对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

回归树的生成

最小二乘回归树生成算法

输入：训练数据集 D；

输出：回归树 f(x)。

在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。

（1）选择最优切分变量 j 与切分点 s，求解 $$ \min_{j,s} \left[ \min_{c1} \sum_{x_i \in R1(j,s)} (y_i - c1)^2 + \min_{c2} \sum_{x_i \in R2(j,s)} (y_i - c2)^2 \right] $$ 遍历变量 j，对固定的切分变量 j 扫描切分点 s，选择使上式达到最小值的对 (j,s)。

（2）用选定的对 (j,s) 划分区域并决定相应的输出值： $$ R1(j, s) = {x | x^{(j)} \leq s} , R2(j, s) = {x | x^{(j)} > s} \ \hat{c}m = \frac{1}{N_m} \sum{x_i \in R_m(j,s)} y_i, \quad x \in R_m, \quad m = 1,2 $$ (3) 继续对两个子区域调用步骤（1）,（2），直到满足停止条件。

(4) 将输入空间划分为 M 个区域 R1，R2，...，RM，生成决策树。

分类树的生成

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

CART 生成算法

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

输出：CART 决策树。

从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树。

（1）设训练数据集为 D，计算现有特征对该数据集的基尼指数。即，对每一个特征 A，对其可能取的每一个值 a，根据样本点对 A=a 的测试为 “是” 或者 “否” 将 D 分割成 \(D_1\) 和 \(D_2\) 两部分，计算 A=a 时的基尼指数。

（2）在所有可能的特征 A 以及它们所有可能的切分点 a 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。

（3）对两个子结点递归地调用（1）、（2），直到满足停止条件。

（4）生成 CART 决策树。

算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多的特征。

简单解释一下预剪枝和后剪枝

在决策树算法中，剪枝是一种防止过拟合的重要技术。过拟合发生在模型过于复杂，以至于它不仅学习了数据的一般趋势，还学习了训练数据中的噪声。为了避免这种情况，剪枝技术被用来简化决策树。剪枝有两种主要形式：预剪枝和后剪枝。

预剪枝

预剪枝是在决策树完全生成之前进行的。在树的每个节点，在决策树进一步分支之前，会先评估分支是否真的有助于提升模型的性能。如果分支预计不会显著提升性能，则停止进一步分支，并将当前节点标记为叶节点。

预剪枝的关键点包括：

  • 停止标准：可以是达到预定的树的深度、节点中的样本数量少于某个阈值、分割后的信息增益低于某个阈值等。
  • 优点：可以显著减少计算成本，同时，预剪枝生成的树往往更小，更易于理解。
  • 缺点：可能过早停止树的生长，导致模型欠拟合。
后剪枝

后剪枝是在决策树完全生成之后进行的。它首先构建完整的决策树，然后自底向上检查每个节点，评估移除或替换某些子树是否能提高验证集上的性能。

后剪枝的关键点包括：

  • 优点：通常能找到更优的树结构，因为它在全局范围内评估树的性能。
  • 缺点：计算成本较高，因为需要首先构建完整的树，然后进行评估和剪枝。

决策树是如何处理缺失值？

决策树处理缺失值要考虑以下三个问题

1、当开始选择哪个属性来划分数据集时，样本在某几个属性上有缺失怎么处理？

（1）忽略这些缺失的样本。

（2）填充缺失值，例如给属性 A 填充一个均值或者用其他方法将缺失值补全。

（3）计算信息增益比时根据缺失率的大小对信息增益比进行打折，例如计算属性 A 的信息增益比，若属性 A 的缺失率为 0.9，则将信息增益比乘以 0.9 作为最终的信息增益比。

2、一个属性已经被选择，那么在决定分割点时，有些样本在这个属性上有缺失怎么处理？

（1）忽略这些缺失的样本。

（2）填充缺失值，例如填充一个均值或者用其他方法将缺失值补全。

（3）把缺失的样本分配给所有的子集，也就是每个子集都有缺失的样本。

（4）单独将缺失的样本归为一个分支。

3、决策树模型构建好后，测试集上的某些属性是缺失的，这些属性该怎么处理？

（1）如果有单独的缺失值分支，依据此分支。

（2）把待分类的样本的属性 A 分配一个最常出现的值，然后进行分支预测。

（3）待分类的样本在到达属性 A 结点时就终止分类，然后根据此时 A 结点所覆盖的叶子节点类别状况为其分配一个发生概率最高的类。

决策树的优缺点是什么？

优点

  • 决策树简单且易于解释。
  • 可处理混合类型特征
  • 具体伸缩不变性（不用归一化特征）
  • 有特征组合的作用
  • 可自然地处理缺失值
  • 对异常点鲁棒
  • 有特征选择作用
  • 可扩展性强， 容易并行
  • 它们可用于分类和回归问题。
  • 它们可以对不可线性分离的数据进行分区。

缺点

  • 缺乏平滑性
  • 不适合处理高维稀疏数据
  • 决策树很容易出现过度拟合。
  • 即使训练数据集发生很小的变化，也会对决策树的逻辑产生巨大的影响。

如何使用 Scikit-learn 实现决策树？

下面我们使用 Scikit-learn 构建决策树分类器。

这里我们使用的数据集是超市数据。

import numpy as np
import matplotlib.pyplot as plt 
import pandas as pd
data = pd.read_csv('Social_Network_Ads.csv')
data.head()

image-20231026162521963

它由 5 个特征组成：UserID、Gender、Age、EstimatedSalary 和 Purchased。

我们只将 Age 和 EstimatedSalary 作为自变量，Purchased 作为因变量。

feature_cols = ['Age','EstimatedSalary' ]
X = data.iloc[:,[2,3]].values
y = data.iloc[:,4].values

下一步是将数据集分为训练和测试。

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test =  train_test_split(X,y,test_size = 0.25, random_state= 0)

训练模型。

from sklearn.tree import DecisionTreeClassifier
classifier = DecisionTreeClassifier()
classifier = classifier.fit(X_train,y_train)

做出预测并检查准确性。

#prediction
y_pred = classifier.predict(X_test)#Accuracy
from sklearn import metrics
print('Accuracy Score:', metrics.accuracy_score(y_test,y_pred))
#Accuracy Score: 0.9

决策树分类器的准确率为 91%。

混淆矩阵

from sklearn.metrics import confusion_matrix
cm = confusion_matrix(y_test, y_pred)
cm

#输出
#array([[62,  6],
#       [ 4, 28]])

这意味着 6 个观察结果被归类为错误。

让我们首先可视化模型预测结果。

from matplotlib.colors import ListedColormap
X_set, y_set = X_test, y_test
X1, X2 = np.meshgrid(np.arange(start = X_set[:,0].min()-1, stop= X_set[:,0].max()+1, step = 0.01),np.arange(start = X_set[:,1].min()-1, stop= X_set[:,1].max()+1, step = 0.01))
plt.contourf(X1,X2, classifier.predict(np.array([X1.ravel(), X2.ravel()]).T).reshape(X1.shape), alpha=0.75, cmap = ListedColormap(("red","green")))
plt.xlim(X1.min(), X1.max())
plt.ylim(X2.min(), X2.max())
for i,j in enumerate(np.unique(y_set)):
  plt.scatter(X_set[y_set==j,0],X_set[y_set==j,1], c = ListedColormap(("red","green"))(i),label = j)
plt.title("Decision Tree(Test set)")
plt.xlabel("Age")
plt.ylabel("Estimated Salary")
plt.legend()
plt.show()

image-20231026163218971

可视化生成的树。

为了绘制树，你还需要安装 Graphviz 和 pydotplus。

pip install pydotplus
pip install graphviz
pip install six

from sklearn.tree import export_graphviz
from six import StringIO  
from IPython.display import Image  
import pydotplus
dot_data = StringIO()
feature_cols = ['Age','EstimatedSalary']
export_graphviz(classifier, out_file=dot_data,  
                filled=True, rounded=True,
                special_characters=True,
                feature_names = feature_cols,class_names=['0','1'])
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())  
Image(graph.create_png())

image-20231026163614460

在决策树图中，每个内部节点都有一个分割数据的决策规则。

在这里，生成的树没有被修剪。这棵未经修剪的树是无法解释的，也不容易理解。下面我们通过剪枝来进行处理。

优化决策树分类器

criteria：此参数指定了用于分割每个节点的准则，可以选择 “gini”（基尼指数） 和 “entropy”（信息增益）。

max_depth：树的最大深度。如果没有，则扩展节点，直到所有叶子包含少于 min_samples_split 样本。最大深度值较高会导致过拟合，较小值会导致欠拟合。

在 Scikit-learn 中，决策树分类器的优化仅通过预剪枝来执行。树的最大深度可以作为预剪枝的控制变量。

# Create Decision Tree classifer object
# Train Decision Tree Classifer
classifier = DecisionTreeClassifier(criterion="entropy", max_depth=3) 
#Predict the response for test dataset
classifier = classifier.fit(X_train,y_train) 
y_pred = classifier.predict(X_test)
# Model Accuracy, how often is the classifier correct?
print("Accuracy:",metrics.accuracy_score(y_test, y_pred))
# Accuracy: 0.94

此时分类率提高到了 94%，比之前的模型准确率更高。

现在让我们再次可视化修剪后的决策树。

dot_data = StringIO()
export_graphviz(classifier, out_file=dot_data,  
                filled=True, rounded=True,
                special_characters=True, feature_names = feature_cols,class_names=['0','1'])
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())  
Image(graph.create_png())

image-20231026164303693

与之前的决策树模型图相比，该剪枝模型不太复杂、可解释且易于理解。

aaa