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

决策树

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

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

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

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

建立决策树

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

基尼不纯度/基尼指数

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

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

• 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

熵

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

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

• 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

信息增益

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

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

• 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

接下来，计算每个子集 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

最后，计算信息增益：

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

构建树

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

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

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

举例：打网球

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

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

PlayTennis	Outlook_Overcast	Outlook_Rainy	Outlook_Sunny	Temperature_Cool	Temperature_Hot	Temperature_Mild	Humidity_High	Humidity_Normal	Wind_Strong	Wind_Weak
No	False	True	False	True	False	False	False	True	False	True
Yes	False	False	True	False	True	False	False	True	False	True
No	False	True	False	True	False	False	True	False	True	False
No	False	True	False	False	True	False	True	False	False	True
Yes	False	False	True	False	False	True	False	True	False	True
Yes	False	False	True	False	True	False	False	True	False	True
No	False	True	False	False	True	False	True	False	True	False
Yes	True	False	False	True	False	False	True	False	False	True
No	False	True	False	False	True	False	False	True	True	False
No	False	True	False	False	True	False	True	False	True	False

数据集包括以下特征：

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

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

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

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

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

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

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

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

数据假设

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

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

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