手册AI red teamer （人工智能红队）系列 05 – 人工智能基础 – 决策树

决策树是一种流行的 监督学习算法，适用于 分类和 回归任务。决策树以其直观的树状结构而著称，这使得它们易于理解和解释。从本质上讲，决策树创建了一个模型，通过学习从数据特征中推断出的简单决策规则来预测目标变量的值。

想象一下，你正试图根据天气决定是否打网球。决策树会把这个决定分解成一系列简单的问题：天气晴朗吗？有风吗？是否潮湿？根据这些问题的答案，决策树会引导你做出最终决定：打网球还是不打网球。

决策树由三个主要部分组成：

• 根节点： 它代表树的起点，包含整个数据集。
• 内部节点： 这些节点表示数据的特征或属性。每个内部节点根据不同的决策规则分为两个或多个子节点。
• 叶节点： 这些是树的终端节点，代表最终结果或预测。

建立决策树

构建决策树需要在每个节点上选择最佳特征来分割数据。这种选择基于 吉尼不纯度、熵或 信息增益等度量，它们量化了拆分后产生的子集的同质性。我们的目标是创建能产生越来越纯的子集的拆分，其中每个子集中的数据点主要属于同一类别。

基尼不纯度/基尼指数

基尼不纯度测量从集合中随机选择一个元素的错误分类概率。基尼不纯度越低，表示集合越纯粹。基尼不纯度的计算公式为

Gini(S) = 1 - Σ (pi)^2

Python

• S 是数据集。
• pi 是属于 i 类别的元素在集合中所占的比例。

考虑一个包含两个类别：A和B的数据集S。假设数据集中有30个属于类别A的实例和20个属于类别B的实例。

• A 类的比例：pA = 30 / (30 + 20) = 0.6。
• B 类的比例：pB = 20 / (30 + 20) = 0.4。

该数据集的基尼不纯度为

Gini(S) = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 1 - 0.52 = 0.48

Python

熵

熵表示集合的无序性或不确定性。熵越小，表示集合越均匀。熵的计算公式为

Entropy(S) = - Σ pi * log2(pi)

Python

• S 是数据集。
• pi 是属于 i 类别的元素在集合中所占的比例。

使用相同的数据集 S，其中包含30个属于类别A的实例和20个属于类别B的实例：

• A 类的比例：pA = 0.6。
• B 类的比例：pB = 0.4。

该数据集的熵值为

Entropy(S) = - (0.6 * log2(0.6) + 0.4 * log2(0.4))
           = - (0.6 * (-0.73697) + 0.4 * (-1.32193))
           = - (-0.442182 - 0.528772)
           = 0.970954

Python

信息增益

信息增益用于度量根据特定特征拆分数据集所实现的熵减。分割时会选择信息增益最大的特征。信息增益的计算公式为

Information Gain(S, A) = Entropy(S) - Σ ((|Sv| / |S|) * Entropy(Sv))

Python

• S 是数据集。
• A 是用于分割的特征。
• Sv 是特征 A 具有值 v 的 S 的子集。

考虑一个包含50个实例的数据集S，其中有两个类别：A和B。假设我们考虑的特征 F 可以有两个值：1 和 2 。数据集的分布如下：

• 对于 F = 1：30 个实例，20 个 A 类，10 个 B 类
• 对于 F = 2：20 个实例，10 个 A 类，10 个 B 类

首先，计算整个数据集 S 的熵：

Entropy(S) = - (30/50 * log2(30/50) + 20/50 * log2(20/50))
           = - (0.6 * log2(0.6) + 0.4 * log2(0.4))
           = - (0.6 * (-0.73697) + 0.4 * (-1.32193))
           = 0.970954

Python

接下来，计算每个子集 Sv 的熵：

• 对于 F = 1：
  • A 类的比例：pA = 20/30 = 0.6667。
  • B 类的比例：pB = 10/30 = 0.3333。
  • Entropy(S1) = - (0.6667 * log2(0.6667) + 0.3333 * log2(0.3333)) = 0.9183
• 对于 F = 2：
  • A 类的比例：pA = 10/20 = 0.5。
  • B 类的比例：pB = 10/20 = 0.5。
  • Entropy(S2) = - (0.5 * log2(0.5) + 0.5 * log2(0.5)) = 1.0

现在，计算子集的加权平均熵：

Weighted Entropy = (|S1| / |S|) * Entropy(S1) + (|S2| / |S|) * Entropy(S2)
                 = (30/50) * 0.9183 + (20/50) * 1.0
                 = 0.55098 + 0.4
                 = 0.95098

Python

最后，计算信息增益：

Information Gain(S, F) = Entropy(S) - Weighted Entropy
                       = 0.970954 - 0.95098
                       = 0.019974

Python

构建树

树从根节点开始，根据其中一个标准（基尼不纯度、熵或信息增益）选择最能分割数据的特征。该特征成为内部节点，并为该特征的每个可能值或值范围创建分支。然后根据这些分支将数据划分为子集。这个过程会对每个子集进行递归，直到满足停止标准为止。

当满足以下条件之一时，树就会停止延申：

• 最大深度：树达到指定的最大深度，防止树变得过于复杂和可能过度拟合数据。
• 最小数据点数：节点中的数据点数低于指定阈值，以确保分割是有意义的，而不是基于很小的子集。
• 纯节点：节点中的所有数据点都属于同一类别，表明进一步分割不会提高子集的纯度。

举例：打网球

让我们仔细研究一下 "打网球 "的例子，以说明决策树在实际中是如何工作的。

想象一下，你有一个数据集，其中包含历史天气状况以及您是否在这些日子里打网球。例如

数据集包括以下特征：

• 天气: Sunny, Overcast, Rainy
• 温度: Hot, Mild, Cool
• 湿度: High, Normal
• 风: Weak, Strong

目标变量是 打网球： Yes or No。

决策树算法将对该数据集进行分析，以确定最能将 "是 "实例与 "否 "实例区分开来的特征。首先，它将计算每个特征的 信息增益或 吉尼杂质，以确定哪个特征能提供最有信息量的分割。

决策树算法将分析这个数据集以识别最佳特征，这些特征可以将“是”与“否”分开。它将首先计算每个特征的信息增益或基尼不纯度，以确定哪个特征能提供最有信息量的分割。

例如，算法可能会发现 天气 特征可提供最高的信息增益。这意味着根据晴天、阴天或雨天对数据进行拆分，可以最显著地减少熵或杂质。

决策树的根节点将是 天气 特征，并有三个分支：晴天、阴天和雨天。根据这些分支，数据集将分为三个子集。

接下来，算法将分析每个子集，以确定下一次拆分的最佳特征。例如，在 "晴天 "子集中，湿度可能会提供最高的信息增益。这将导致另一个具有 "高 "和 "正常 "分支的内部节点。

这一过程一直递归进行，直到满足停止标准，如达到最大深度或节点中数据点的最小数量。最终结果是一个树状结构，每个内部节点都有决策规则，叶节点则有预测结果（打网球： Yes or No）。

数据假设

决策树的优势之一是对数据的假设最少：

• 无线性假设： 决策树可以处理特征与目标变量之间的线性和非线性关系。这使得决策树比线性回归等假设线性关系的算法更加灵活。
• 无正态性假设： 数据不需要呈正态分布。这与某些需要正态性才能做出有效推论的统计方法形成了鲜明对比。
• 处理异常值： 决策树对异常值的处理相对稳健。由于决策树是根据特征值对数据进行分区，而不是依赖于基于距离的计算，因此异常值不太可能对决策树结构产生重大影响。

这些最低限度的假设有助于决策树的多功能性，使其无需大量预处理或转换即可应用于各种数据集和问题。