决策树（机器学习）_决策树 csdn

系列文章目录

3.1 决策树的构造

3.1.1 信息增益
  3.1.2 编写代码计算经验熵
  3.1.3利用代码计算信息增益

3.2 决策树的生成和修剪

 3.2.1 决策树的构建
     1. ID3算法
     2. 决策树的剪枝
  3.2.2 决策树可视化
  3.2.3 ID3、C4.5、CART的区别
3.3 使用决策树进行分类
3.4 决策树的存储
3.5 sklearn——使用决策树预测隐形眼镜类型
  3.5.1 使用sklearn构建决策树
  3.5.2 使用Graphviz可视化决策树
3.6 总结
 

---

---

前言

决策树是一种常见的机器学习算法，它被广泛用于分类和回归问题。决策树模型的主要思想是通过对特征进行递归分割，构建一棵树状的结构来对数据进行预测。在决策树中，每个内部节点表示对一个特征的判断，每个叶子节点表示一个类别或一个回归值。

决策树的构建过程主要包括特征选择、节点划分和剪枝三个主要步骤。特征选择决定了在每个节点上选择哪个特征来进行划分，常用的特征选择指标包括信息增益、信息增益比、基尼系数等。节点划分是通过选择一个划分点将数据划分为更纯的子节点，常见的划分方法有ID3、C4.5、CART等。剪枝是为了防止过拟合，通过去掉一些节点或子树来简化决策树。

决策树的优点包括易于理解、可解释性强、能够处理分类和回归问题等。然而，决策树也有一些局限性，例如对于连续性特征处理较为困难、容易产生过拟合等。因此，在实际应用中，通常会采用集成学习方法如随机森林、提升树等来提升决策树的性能。

总的来说，决策树是一种简单但有效的机器学习算法，具有广泛的应用领域，包括医疗诊断、金融风险评估、推荐系统等。

---

决策树是什么？

决策树是一种常见的机器学习算法，也是一种数据挖掘技术。它基于对输入数据进行递归分割的方式构建一棵树状结构，用于解决分类和回归问题。在决策树模型中，每个内部节点表示对一个特征的判断，每个叶子节点表示一个类别或一个回归值。

决策树的三个主要步骤分别是特征选择、节点划分和剪枝，下面分别介绍：

1. 特征选择：在每个节点上选择最优特征，以便于将数据更好地进行划分。常用的特征选择指标包括信息增益、信息增益比、基尼系数等。

2. 节点划分：根据选择的最优特征进行节点划分，将数据集分割成更纯的子集。常用的划分方法有ID3、C4.5、CART等。

3. 剪枝：为了防止过拟合，可以通过去掉一些节点或子树来简化决策树。常用的剪枝方法包括预剪枝和后剪枝两种。

4. 决策树模型

3.1 决策树的构造

构造决策树的一般步骤如下：

1. 选择特征：从所有特征中选择对样本分类最具有判别力的特征。可以根据信息增益、信息增益比、基尼指数等指标进行特征选择。

2. 划分数据集：根据选择的特征将数据集划分为不同的子集，每个子集对应于特征的一个取值。

3. 构建子树：对于每个子集，递归地应用上述步骤构建子树，直到子集中的所有样本属于同一类别或达到预设停止条件。

4. 剪枝处理：对于已构建的决策树，可以使用预剪枝或后剪枝等剪枝策略进行优化，以避免过拟合。

5. 预测分类：使用构建好的决策树对新样本进行分类预测。

需要注意的是，决策树的构建和剪枝过程与具体的算法和问题有关，不同的算法和策略可能会产生不同的决策树。在应用中需要根据具体问题和数据特征选择合适的决策树算法和优化策略。

决策树特点

优点：

1. 可解释性强，决策树的结构直观，可直接理解和解释。

2. 适用性广泛，决策树可以用于处理分类和回归问题。

3. 非参数方法，决策树对数据的分布和特征之间的关系没有做任何假设，具有较强的适应性。

4. 能够处理混合型特征和缺失数据。

5. 可以自动选择重要的特征，进行特征选择。

6. 模型可解释性强，可以对模型进行可视化展示。

缺点：

1. 容易发生过拟合，特别是在处理高维数据时。

2. 对噪声敏感，可能会导致不稳定的决策树模型。

3. 数据中特征之间的相关性可能会影响决策树模型的性能。

4. 在处理连续型数据时需要进行离散化，造成信息损失。

5. 决策树的分类结果对样本分布的变化比较敏感。

3.1.1 信息增益

信息增益是评估在决策树算法中选择某个特征作为节点划分标准的指标之一。它衡量了使用该特征进行划分后，能够对数据集带来多少信息的增益。

在决策树算法中，选择合适的特征来进行节点划分是非常重要的。信息增益的计算基于信息熵的概念。信息熵用于测量数据的不确定性或者混乱程度。

对于给定的数据集，假设目标变量有不同的取值，计算其信息熵可以表示为：

l(xi​)=−log2​p(xi​)

其中，p1, p2, …, pn 表示每个目标变量取值的概率。

当选择某个特征作为节点划分标准时，该特征会将数据集划分为多个子集。信息增益衡量的是使用该特征进行划分后，对数据集整体信息熵的减少程度。信息增益的计算公式如下：

H(D)=−Σ∣D∣∣ck​∣​log2​∣D∣∣ck​∣​

其中，S表示原始的数据集，A表示特征，Sv表示特征A取值为v时的子集，|S|表示数据集S的大小，|Sv|表示子集Sv的大小。

信息增益越大，表示使用特征A进行划分后，能够对数据集的不确定性带来更多的减少，即有更多的信息增益。

在构建决策树时，一般会选择具有最大信息增益的特征作为当前节点的划分标准，以此构建决策树的分支。

在理解信息增益之前，要明确——条件熵

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

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

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

信息增益：信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)-H(D|A)
g(D,A)=H(D)−H(D∣A)

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

信息增益值的大小相对于训练数据集而言的，并没有绝对意义，在分类问题困难时，也就是说在训练数据集经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小，使用信息增益比可以对这个问题进行校正，这是特征选择的另一个标准。

信息增益比：特征A AA对训练数据集D的信息增益比g R ( D , A ) g_R(D,A)g 
R
​
 (D,A)定义为其信息增益g ( D , A ) g(D,A)g(D,A)与训练数据集D DD的经验熵之比：

gR​(D,A)=H(D)g(D,A)​
​

3.1.2 编写代码计算经验熵

经验熵是表示特征集合的无序程度的量，可以用下面的公式进行计算：

H(D) = - Σ (Ck/D) * log2(Ck/D)

其中 H(D) 是经验熵，Ck 是数据集 D 中属于类别 k 的样本数，D 是数据集。

以下是一个 Python 代码示例，用于计算经验熵：

这个函数接受一个数据集作为输入，并返回经验熵的值。数据集中的每个样本都表示为一个数组，其中最后一个元素是该样本的类别标签。

  3.1.3利用代码计算信息增益

3.2 决策树的生成和修剪

工作原理

得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。

第一次划分之后，数据集被向下传递到树的分支的下一个结点。在这个结点上，我们可以再次划分数据。

因此我们可以采用递归的原则处理数据集。

构建决策树的算法有很多，比如C4.5、ID3和CART，这些算法在运行时并不总是在每次划分数据分组时都会消耗特征。

由于特征数目并不是每次划分数据分组时都减少，因此这些算法在实际使用时可能引起一定的问题。

目前我们并不需要考虑这个问题，只需要在算法开始运行前计算列的数目，查看算法是否使用了所有属性即可。

决策树生成算法递归地产生决策树，直到不能继续下去未为止。这样产生的树往往对训练数据的分类很准确，但对未知的测试数据的分类却没有那么准确，即出现过拟合现象。

过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。
 

3.2.1 决策树的构建

1.ID3算法

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

具体方法是：

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

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

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

下面是使用ID3算法构建决策树的步骤：

1. 计算根节点的信息熵：
   首先计算整个数据集的样本个数，共6个。然后计算正样本（感冒）和负样本（健康）的比例，感冒为3个，健康为3个。根据这些信息可以计算根节点的信息熵。

   • 正样本的概率：P(感冒) = 3/6
   • 负样本的概率：P(健康) = 3/6

   根节点的信息熵为：- P(感冒) * log2(P(感冒)) - P(健康) * log2(P(健康)) = - (3/6) * log2(3/6) - (3/6) * log2(3/6) ≈ 1

2. 计算各个候选特征的信息增益：
   对于每个可能的划分特征，计算其相应子节点的信息熵，并计算信息增益。假设有三个属性 A、B 和 C，我们需要计算每个属性对应的信息增益。

   • 算法首先计算属性 A 的信息增益：首先计算 A 为 “是” 的情况下的子数据集，其中有3个样本，全部属于感冒类别，信息熵为0。然后计算 A 为 “否” 的情况下的子数据集，其中有3个样本，2个属于健康类别，1个属于感冒类别，信息熵为 - (2/3) * log2(2/3) - (1/3) * log2(1/3)。根据这些信息可以计算属性 A 的信息增益。

   • 同样的方式计算属性 B 和 C 的信息增益。

   最后，将每个属性的信息增益与根节点的信息熵相减，得到每个属性的信息增益。

3. 选择最大信息增益的特征作为当前节点的划分标准：
   根据上一步的计算结果，选择信息增益最大的特征作为当前节点的划分标准。在这个例子中，我们假设属性 B 的信息增益最大，因此我们将属性 B 作为根节点的划分标准。

4. 生成子节点：
   对于划分标准为属性 B 的根节点，我们需要将数据集根据属性 B 的不同取值划分为不同的子数据集。在这个例子中，属性 B 的取值有高、中和低，对应着三个子数据集。我们在每个子数据集上递归地重复上述步骤，直到满足终止条件。

5. 编写ID3算法的代码

6. 

2.决策树的剪枝

决策树的剪枝是一种防止过拟合的技术，在构建决策树时去掉一些节点或子树，以降低模型复杂度，提高泛化能力。剪枝可以分为预剪枝（pre-pruning）和后剪枝（post-pruning）。

预剪枝是在树的构建过程中，在每个节点进行划分前先进行评估，并决定是否继续划分。一些常见的预剪枝方法有：

1. 最大深度限制：限制树的最大深度，防止树过深导致过拟合。
2. 叶子节点数量限制：限制叶子节点的最小样本数量，防止每个叶子节点只包含极少量的样本。
3. 不纯度减少阈值：限制不纯度的减少量，如果划分后的不纯度减少量低于阈值，则停止划分。

后剪枝是在树构建完成后，从底向上对决策树剪枝。一些常见的后剪枝方法有：

1. 错误率降低剪枝（Reduced Error Pruning）：对每个非叶子节点都尝试剪枝，并计算剪枝后在验证集上的错误率，选择错误率降低的剪枝方式。
2. 悲观剪枝（Pessimistic Pruning）：为每个非叶子节点引入一个置信区间，以统计学方法计算节点剪枝后在测试集上的错误率估计，选择错误率最小的剪枝方式。

   实例：

假设我们有一个分类问题，要通过决策树对花朵进行分类。

首先，我们使用训练数据构建一个决策树模型。根据花朵的特征如花瓣长度、花瓣宽度等，我们创建一个深度为3的决策树。

然后，我们可以使用预剪枝来避免过拟合。比如，我们设置最大深度为2和叶子节点最小样本数量为5。如果在构建过程中遇到一个节点，它的深度已经达到了2或者样本数量少于5，我们停止继续划分并将该节点作为叶子节点。

接下来，我们可以使用后剪枝来进一步优化决策树。我们用验证集评估决策树的性能，并对决策树进行剪枝。这里使用错误率降低剪枝。我们从底向上，对每个非叶子节点尝试剪枝。对于每个非叶子节点，我们剪枝后得到一个新的决策树，在验证集上计算错误率。如果剪枝后的错误率比不剪枝小，那么就进行剪枝，将该节点变为叶子节点。

最后，我们使用剪枝后的决策树进行测试，并评估模型的泛化能力。

以上就是一个决策树的剪枝实例。在实际应用中，可以根据具体问题和数据集的特点选择合适的剪枝策略进行模型优化。

3.2.2 决策树可视化

决策树的可视化是一个直观、易于理解的方法，可以帮助我们了解决策树的结构和决策过程。下面是一些常用的决策树可视化方法：

1. 文本表示法：用文本形式表示决策树，即将决策过程用一系列的if-else语句表示出来。这种方法虽然简单易用，但缺乏直观性。

2. 图形表示法：用树形图来展示决策树，将每个节点视为一个圆圈，节点之间用箭头连接，箭头上标明判断条件。这种方法直观易懂，可以快速理解决策树的结构和决策过程。常见的图形表示法有Graphviz和TreePlot等。

3. 规则集表示法：将决策树表示为一组规则，每条规则包含一个前提条件和一个结论。这种方法可以用于比较复杂的决策树，帮助我们从规则的角度理解决策树的决策过程。

4. 动态可视化法：通过动态呈现决策树的决策过程，可以帮助我们更深入地理解决策树的工作原理。例如，可以将决策过程用动画的形式展示出来，或者将决策树与实时数据集结合，演示决策树如何分类对应的实例。

以下是一个决策树可视化的示例：

假设我们有一个二分类问题，要用决策树来对数据进行分类。数据集包含两个特征，分别是X1和X2。我们使用sklearn库中的DecisionTreeClassifier进行决策树的训练，并采用Graphviz将决策树可视化展示出来。

from sklearn.datasets import make_classification
from sklearn.tree import DecisionTreeClassifier, export_graphviz
import graphviz
 
# 生成训练数据
X, y = make_classification(n_samples=100, n_features=2, n_classes=2, random_state=1)
 
# 构建决策树
dt = DecisionTreeClassifier(random_state=1)
dt.fit(X, y)
 
# 输出决策树可视化结果
dot_data = export_graphviz(dt, out_file=None, feature_names=['X1', 'X2'], class_names=['Class_0', 'Class_1'], filled=True, rounded=True, special_characters=True)
graph = graphviz.Source(dot_data)
graph

通过 above 代码中的export_graphviz()方法，我们可以将决策树以Graphviz格式输出，再通过graphviz库将其可视化。输出的决策树如下所示：

在可视化的决策树中，每个节点表示一个特定数据分裂的标准，包括特征名称、分裂阈值和分裂依据，叶子结点表示数据被划分到的类别（如Class 0和Class1）。通过深入分析决策树，我们可以了解模型对数据如何进行判断和分类。

3.2.3 ID3、C4.5、CART的区别

ID3、C4.5和CART是常见的决策树算法，它们在构建决策树和选择分裂节点的方法上有一些区别。

1. ID3 (Iterative Dichotomiser 3)：ID3算法使用信息增益作为选择分裂节点的准则。信息增益衡量了在选定特征后，样本集合的不确定性减少的程度。ID3算法要求特征必须是离散的，且可以有多个取值。ID3算法在处理离散值时表现良好，但在处理连续值时需要进行离散化处理。

2. C4.5：C4.5算法是ID3算法的改进版本，它引入了信息增益比来解决ID3算法的倾向性问题。信息增益比考虑了特征取值的数目对信息增益的影响，避免了对取值较多的特征的偏向性。C4.5算法在处理离散值和连续值时都不需要对离散化处理，可以直接处理多种类型的特征。此外，C4.5算法还支持对缺失值的处理。

3. CART (Classification and Regression Trees)：CART算法既可以用于分类问题，也可以用于回归问题。CART算法选择分裂节点的准则是基尼不纯度（Gini Impurity）或均方差（Mean Squared Error）。基尼不纯度衡量了从样本集合中随机选取两个样本，其类别不同的概率，基尼指数越小表示样本集合的纯度越高。在回归问题中，CART算法通过最小化均方差来选择最优分裂。

总结：

• ID3算法使用信息增益作为分裂节点的选择准则，适用于离散特征，需要离散化处理连续特征。
• C4.5算法在ID3的基础上改进，引入信息增益比来解决倾向性问题，可以处理离散特征和连续特征，支持处理缺失值。
• CART算法可以用于分类和回归问题，使用基尼不纯度或均方差作为分裂节点的选择准则。

3.3 使用决策树进行分类

1. 准备训练数据集：首先，你需要准备一个包含已知类别的训练数据集。每个样本应包含一组特征值以及对应的分类或标签。

2. 选择决策树算法：根据你的需求和数据特征的类型，选择适合的决策树算法，如ID3、C4.5或CART。

3. 训练决策树模型：使用选定的算法，将训练数据集输入模型进行训练。模型将学习数据中的模式和规律，并生成一个决策树模型。

4. 特征选择：决策树构建过程中需要选择最佳的特征来进行分裂节点。根据所选算法的不同，可以使用不同的特征选择准则，如信息增益、信息增益比、基尼不纯度等。

5. 构建决策树：根据选定的特征选择准则，逐步分裂数据集，构建决策树。直到满足停止条件（如达到最大深度或无法继续分裂）为止。

6. 进行预测：使用训练好的决策树模型进行分类预测。将待分类的样本输入决策树，按照分裂节点的条件逐步向下遍历，直到到达叶子节点，并将样本分到相应的类别。

下面是一个使用sklearn库中的DecisionTreeClassifier的示例代码，演示了如何使用决策树进行分类：

在上述示例中，我们从sklearn库中加载了一个经典的鸢尾花数据集。然后，我们将数据集划分为训练集和测试集，并使用DecisionTreeClassifier构建决策树模型。接下来，我们使用训练好的模型对测试集进行预测，并计算预测结果的准确率。

3.4 决策树的存储

1. 序列化存储：将训练好的决策树模型序列化，保存成本地文件或数据库中。这种方式可以方便地进行模型的存储和传输，但由于决策树模型通常比较庞大，因此可能会占用较多的存储空间。
2. 另一种存储方式是将决策树模型转换成一组可解释的规则（rule），比如"Age>=30 and Age<40 => Yes"，并将这些规则存储到数据库中。这种方式可以方便地进行模型的解释和调试，但由于决策树模型本身可能较为复杂，因此生成的规则也可能较为复杂，不方便人工解释。

3.5 sklearn——使用决策树预测隐形眼镜类型

步骤：

收集数据：使用书中提供的小型数据集

准备数据：对文本中的数据进行预处理，如解析数据行

分析数据：快速检查数据，并使用createPlot()函数绘制最终的树形图

训练决策树：使用createTree()函数训练

测试决策树：编写简单的测试函数验证决策树的输出结果&绘图结果

使用决策树：这部分可选择将训练好的决策树进行存储，以便随时使用

3.5.1 使用sklearn构建决策树

在使用scikit-learn（sklearn）构建决策树时，可以按照以下步骤进行：

1. 导入需要的库和模块：
```python
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
```

2. 加载数据集：
```python
iris = load_iris()
X = iris.data
y = iris.target
```

3. 划分数据集为训练集和测试集：
```python
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
```
这里使用了train_test_split函数将数据集分成训练集和测试集，其中test_size表示测试集所占的比例，random_state是一个随机种子，用于确保每次运行时划分结果一致。

4. 构建和训练决策树模型：
```python
dt = DecisionTreeClassifier()
dt.fit(X_train, y_train)
```
在这里，我们创建了一个DecisionTreeClassifier对象，并使用fit方法将训练数据和标签传递给模型进行训练。

5. 使用模型进行预测：
```python
y_pred = dt.predict(X_test)
```
使用predict方法对测试集数据进行预测。

6. 评估模型性能：
```python
accuracy = accuracy_score(y_test, y_pred)
print("准确率: ", accuracy)
```
使用accuracy_score函数计算预测结果的准确率，并输出结果。

以上是使用scikit-learn库构建决策树的基本步骤。根据实际需求，可能还需要对模型进行参数调优、使用交叉验证等进一步优化模型性能。

3.5.2 使用Graphviz可视化决策树
（1）pydotplus安装

直接在anaconda prompt下输入：

pip install pydotplus
1
2）Graphviz下载

安装步骤安装，之后win+R->sysdm.cpl

在“环境变量”中的“系统变量”中找到“PATH”，之后将路径

C:\Anaconda\pkgs\graphviz-2.38.0-4\Library\bin添加到后面，重启 Pycharm 即可。
 

---

总结

优点：

易于理解和解释，决策树可以可视化。
几乎不需要数据预处理。其他方法经常需要数据标准化，创建虚拟变量和删除缺失值。决策树还不支持缺失值。
使用树的花费（例如预测数据）是训练数据点(data points)数量的对数。
可以同时处理数值变量和分类变量。其他方法大都适用于分析一种变量的集合。
可以处理多值输出变量问题。
使用白盒模型。如果一个情况被观察到，使用逻辑判断容易表示这种规则。相反，如果是黑盒模型（例如人工神经网络），结果会非常难解释。
即使对真实模型来说，假设无效的情况下，也可以较好的适用。
缺点：

决策树学习可能创建一个过于复杂的树，并不能很好的预测数据。也就是过拟合。修剪机制（现在不支持），设置一个叶子节点需要的最小样本数量，或者数的最大深度，可以避免过拟合。
决策树可能是不稳定的，因为即使非常小的变异，可能会产生一颗完全不同的树。这个问题通过decision trees with an ensemble来缓解。
学习一颗最优的决策树是一个NP-完全问题under several aspects of optimality and even for simple concepts。因此，传统决策树算法基于启发式算法，例如贪婪算法，即每个节点创建最优决策。这些算法不能产生一个全家最优的决策树。对样本和特征随机抽样可以降低整体效果偏差。
概念难以学习，因为决策树没有很好的解释他们，例如，XOR, parity or multiplexer problems.
如果某些分类占优势，决策树将会创建一棵有偏差的树。因此，建议在训练之前，先抽样使样本均衡。
决策树算法主要包括三个部分：特征选择、树的生成、树的剪枝。常用算法有 ID3、C4.5、CART。

特征选择。特征选择的目的是选取能够对训练集分类的特征。特征选择的关键是准则：信息增益、信息增益比、Gini 指数；

决策树的生成。通常是利用信息增益最大、信息增益比最大、Gini 指数最小作为特征选择的准则。从根节点开始，递归的生成决策树。相当于是不断选取局部最优特征，或将训练集分割为基本能够正确分类的子集；

决策树的剪枝。决策树的剪枝是为了防止树的过拟合，增强其泛化能力。包括预剪枝和后剪枝。