机器学习5

1.1 决策树的定义

决策树是用于分类和回归的机器学习算法。它通过一系列的“是或否”的决策来分类数据。每个决策是基于数据的某个属性进行的，如“色泽是青绿吗？”。
决策树的核心是通过树状结构，将一个复杂的问题逐步拆解为多个简单的二元问题，最终通过一系列决策得出结果。

示例：假设我们要判断一个水果是否是苹果。可能的决策过程包括：

颜色是红色吗？如果是，继续判断；
形状是圆的吗？如果是，继续判断；
它的味道是甜的吗？如果都是，那么我们可以说它是苹果。

1.2 决策树的基本元素

根节点：根节点是决策树的起点，它包含了所有数据。在决策树中，所有的分类判断从根节点开始。
内部节点：每个内部节点代表对某个属性的判断。例如，“颜色是否为红色”可以是一个内部节点。
叶节点：叶节点代表最终的分类结果。例如，经过一系列判断后，叶节点会告诉我们“是苹果”或“不是苹果”。

示例：

       颜色
      /    \
  红色    其他
   /         \
 形状       不是苹果
 /   \
圆     其他
  |
味道
  |
甜 -> 苹果

在这个例子中，我们通过颜色、形状和味道的逐步判断，最终得出是否是苹果的结论。

1.3 决策树的生成步骤

决策树生成过程基于“分而治之”的策略，通过不断地划分数据集，逐步建立决策规则。

输入：给定一个训练数据集 (D = {(X_1, Y_1), (X_2, Y_2), \dots, (X_m, Y_m)}) 和属性集 (A = {a_1, a_2, \dots, a_n})。
- 训练数据集包含特征和标签，如 (X_1) 是样本的属性，(Y_1) 是它的分类结果。
- 属性集是可用来划分样本的特征，比如色泽、根蒂等。
生成节点：从根节点开始，递归创建决策树。如果节点包含的样本都属于同一类别（如都是“好瓜”），那么将该节点标记为叶节点，并终止进一步划分。
选择划分属性：当节点中的样本不属于同一类别时，需要选择一个最优的属性来划分样本。例如，如果属性“色泽”对样本的分类效果最好，选择它来划分数据。
递归生成子节点：对于每个子节点，重复步骤2和3，直到所有节点都成为叶节点或无法继续划分为止。

1.4 决策树递归返回的三种情形

样本同类：如果当前节点中所有样本属于同一类（如全部是好瓜），则该节点直接标记为叶节点，无需继续划分。
属性无法再划分：如果样本在当前所有属性上的取值相同，则无法继续划分。这种情况下，将该节点标记为样本数最多的类。
样本集为空：如果某个节点没有样本，则标记为其父节点样本数最多的类别。

示例：假设我们在划分过程中遇到一个节点，包含的所有样本都是“好瓜”，那么这个节点会被标记为“好瓜”，不再进行进一步划分。

递归过程：决策树的生成是一个递归的过程，树会不断地被细化，直到所有节点都无法再进行划分。每次划分时都选择当前最优的属性来进行，这保证了决策树能够尽量准确地分类数据。

1.5 总结与示例

为了更好地理解决策树的流程，我们可以看以下的例子：

问题：判断一个水果是否是苹果。
属性：
1. 颜色：红色、绿色、黄色；
2. 形状：圆形、椭圆形；
3. 味道：甜、酸。
决策过程如下：

       颜色
      /    \
  红色    其他
   /         \
 形状       不是苹果
 /   \
圆     其他
  |
味道
  |
甜 -> 苹果

在这个决策树中，首先判断颜色，如果是红色则继续判断形状；如果形状是圆的，再判断味道；最终，如果味道是甜的，可以判断为苹果。

2. 划分选择

2.1 信息增益

首先，信息增益的目标是通过某个属性对数据集进行划分，使得划分后的数据集更加“纯净”，即每个子集尽可能只包含同一类别的样本。

我们首先来看 信息熵 的定义：
[
Ent(D) = - \sum_{k=1}^{|Y|} p_k \log_2 p_k
]
这个公式的每一个符号解释如下：

(Ent(D))：表示数据集 (D) 的 信息熵，是衡量数据集纯度的一个指标。
(\sum_{k=1}^{|Y|})：这是一个求和符号，表示对 (k) 从 1 到 (|Y|) 进行求和。 (|Y|) 表示数据集中类别的数量。例如，西瓜数据集中有两类（好瓜和坏瓜），所以 (|Y| = 2)。
(p_k)：这是数据集中第 (k) 类样本的比例。例如，如果在数据集中好瓜占 60%，坏瓜占 40%，那么 (p_1 = 0.6)，(p_2 = 0.4)。
(\log_2 p_k)：这是 (p_k) 在以 2 为底的对数，表示第 (k) 类的熵值。

公式含义：信息熵是通过计算各个类别在数据集中的占比 (p_k)，然后将这些占比进行加权求和，用来衡量整个数据集的不确定性。熵值越大，表示数据集越混乱，类别分布越分散；熵值越小，表示数据集越纯净，样本集中在某一类别。

示例：假设在一个西瓜数据集中，有 60% 是好瓜，40% 是坏瓜，则信息熵计算如下：
[
Ent(D) = -(0.6 \log_2 0.6 + 0.4 \log_2 0.4) \approx 0.971
]
这个值表示当前数据集中的不确定性程度。

信息增益 的公式为：
[
Gain(D, A) = Ent(D) - \sum_{v \in Values(A)} \frac{|D_v|}{|D|} Ent(D_v)
]
每个符号的解释如下：

(Gain(D, A))：表示使用属性 (A) 对数据集 (D) 进行划分后，所获得的 信息增益。信息增益是指划分后数据集的熵值减少量。
(Ent(D))：表示划分之前整个数据集 (D) 的信息熵。
(\sum_{v \in Values(A)})：表示对属性 (A) 的每个可能取值 (v) 进行求和。 (Values(A)) 表示属性 (A) 的所有可能取值，例如“色泽”属性可能有“青绿”、“乌黑”、“浅白”等取值。
(\frac{|D_v|}{|D|})：表示子集 (D_v) 的样本数占总样本数 (D) 的比例。即在划分后，每个子集的大小对总信息增益的贡献权重。
(Ent(D_v))：表示子集 (D_v) 的信息熵。划分后，每个子集中的样本越“纯净”，这个值就越小。

公式含义：信息增益是衡量使用某个属性 (A) 对数据集 (D) 进行划分时，数据集的纯度提升了多少。信息增益越大，说明使用该属性进行划分能够更有效地减少数据集的不确定性，从而使得子集更加纯净。

示例：如果我们使用“色泽”作为划分属性，将数据集 (D) 分为三个子集 (D_1)（青绿），(D_2)（乌黑），和 (D_3)（浅白）。分别计算每个子集的信息熵和它们在总数据集中的比例，然后计算出信息增益。

2.2 增益率

增益率用于避免信息增益对可取值较多的属性（如编号）产生偏好。它的公式为：
[
Gain_ratio(D, A) = \frac{Gain(D, A)}{IV(A)}
]
其中：

(Gain(D, A))：表示属性 (A) 的信息增益。
(IV(A))：表示属性 (A) 的 固有值，用于调整信息增益的偏好。

固有值 的计算公式为：
[
IV(A) = - \sum_{v \in Values(A)} \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|}
]
每个符号的解释如下：

(\sum_{v \in Values(A)})：对属性 (A) 的每个取值 (v) 进行求和。
(\frac{|D_v|}{|D|})：子集 (D_v) 的样本占总样本数的比例。
(\log_2 \frac{|D_v|}{|D|})：子集占比的对数。

公式含义：固有值衡量的是属性 (A) 的取值的分布情况。如果一个属性的取值越多，固有值 (IV(A)) 就会越大。这是为了减少信息增益对取值较多属性的偏好。

示例：例如，编号属性虽然对每个样本的分类都能得到高的信息增益，但它并没有实际意义。增益率通过使用固有值来调整这种偏好，使得划分更加合理。

2.3 基尼指数

基尼指数 是另一种衡量数据集纯度的指标，常用于 CART 决策树。它的公式为：
[
Gini(D) = 1 - \sum_{k=1}^{|Y|} p_k^2
]
每个符号的解释如下：

(Gini(D))：表示数据集 (D) 的基尼指数。
(\sum_{k=1}^{|Y|})：对类别 (k) 从 1 到 (|Y|) 进行求和，(|Y|) 是类别的总数。
(p_k)：表示第 (k) 类样本的比例。

公式含义：基尼指数衡量的是从数据集中随机抽取两个样本，它们属于不同类别的概率。基尼指数越小，表示数据集的纯度越高。

示例：假设一个数据集有60%的好瓜和40%的坏瓜，那么基尼指数为：
[
Gini(D) = 1 - (0.6^2 + 0.4^2) = 0.48
]
这个值表示数据集中样本的混合程度。

通过这些公式，我们可以根据数据的特征选择最优属性来划分决策树，从而提高模型的分类效果。

3. 剪枝处理

剪枝是决策树学习中的一个重要步骤，用来防止过拟合。过拟合是指模型对训练数据过度拟合，导致对新数据的泛化能力下降。剪枝可以减少模型的复杂度，从而提高模型的泛化能力。

剪枝策略通常分为两种：

预剪枝：在生成决策树的过程中，提前停止分裂，避免生成过多分支。
后剪枝：先生成一棵完整的决策树，然后从叶节点开始向上回溯，去掉一些分支。

3.1 预剪枝

预剪枝在每次划分前，通过评估划分是否能提高模型的泛化性能，决定是否进行划分。
如果划分不能带来显著的性能提升，算法会停止划分，并将当前节点标记为叶节点。

示例：假设我们正在生成一棵决策树，当前节点的样本集已经通过某个属性划分，但继续划分带来的性能提升很小，甚至可能对新数据的预测准确率下降。在这种情况下，预剪枝策略会停止继续划分，将当前节点标记为叶节点。

3.2 后剪枝

后剪枝是在生成一棵完整的决策树之后，通过逐步删除一些分支来减少过拟合。
后剪枝的基本步骤是：从树的叶节点开始向上回溯，逐一评估是否可以将当前节点的子树替换为一个叶节点。如果替换能提高泛化性能，则进行剪枝。

示例：假设我们有一棵完整的决策树，其中某个分支只对训练数据有作用，但对新数据预测时效果很差。在这种情况下，后剪枝策略会删除这个分支，将其父节点直接标记为叶节点。

总结：剪枝的目的在于减少决策树的复杂度，避免过拟合，从而提高模型的泛化能力。预剪枝和后剪枝各有优缺点，前者可以减少生成树的时间，但可能错过某些有效的划分；后者能够保留更多的信息，但需要更多的计算资源。

4. 连续与缺失值

在现实中的数据集里，很多属性是 连续值，例如一个水果的密度或含糖量。此外，数据集中还可能存在 缺失值，例如某些样本在某个属性上没有取值。决策树算法需要处理这些情况，以确保模型的可靠性。

4.1 连续值处理

对于离散属性，决策树可以直接根据取值划分数据集，但连续属性的取值范围很大，不能简单地枚举所有可能值。因此，决策树通过 二分法 来处理连续属性。

公式：在划分数据集时，决策树选择一个划分点 (t)，将数据集分为两部分：
[
Gain(D, A, t) = Ent(D) - \left( \frac{|D_{\leq t}|}{|D|} Ent(D_{\leq t}) + \frac{|D_{> t}|}{|D|} Ent(D_{> t}) \right)
]
解释如下：

(Gain(D, A, t))：表示在划分点 (t) 下，使用属性 (A) 进行划分所获得的信息增益。
(Ent(D))：划分前数据集 (D) 的信息熵。
(\frac{|D_{\leq t}|}{|D|})：表示取值不大于 (t) 的样本在整个数据集中的比例。
(Ent(D_{\leq t}))：表示取值不大于 (t) 的样本子集的信息熵。
(\frac{|D_{> t}|}{|D|})：表示取值大于 (t) 的样本在整个数据集中的比例。
(Ent(D_{> t}))：表示取值大于 (t) 的样本子集的信息熵。

公式含义：通过选取不同的划分点 (t)，决策树可以将连续属性分为两部分，计算划分后的信息增益。最终选择信息增益最大的划分点作为最佳划分。

示例：假设我们有一个水果数据集，属性“密度”的取值范围是 0.1 到 0.9。决策树可以通过划分点 (t = 0.5) 将数据集分为两部分：密度小于等于 0.5 和密度大于 0.5。然后计算每个部分的信息增益，选择最优的划分点。

4.2 缺失值处理

在现实数据集中，常常会遇到某些属性的值缺失，决策树需要处理这些不完整的样本，而不是简单地舍弃它们。处理缺失值的常见方法包括：

属性值缺失：当某个样本在某个属性上的取值缺失时，可以通过样本权重的调整来处理。具体方法是将样本按比例分配到不同的子节点，并根据样本的权重调整划分结果。
分类结果缺失：在分类过程中，如果某个样本的某个属性取值缺失，决策树可以同时将样本分配到所有可能的子节点，并根据样本的权重调整最终的分类结果。

公式：处理缺失值时，信息增益的计算公式被修改为：
[
Gain(D, A) = p \times Gain(D, A)
]
其中，(p) 表示没有缺失值样本的比例。

公式含义：在计算信息增益时，仅对没有缺失值的样本集进行计算，同时根据样本集的比例调整最终的信息增益结果。

示例：假设我们有一个数据集，其中某些样本的“色泽”属性缺失。我们可以根据样本权重，将缺失的样本分配到不同的子节点，计算这些子节点的信息增益。

5. 多变量决策树

多变量决策树 是决策树的扩展版本，它允许使用多个属性的线性组合来进行划分，而不仅仅是单个属性。这种方法能够处理复杂的分类问题，特别是当数据的决策边界不是简单的轴平行时。

5.1 多变量决策树的定义

在普通的决策树中，非叶节点对单个属性进行测试（如“色泽是否为青绿？”）。
而在多变量决策树中，每个非叶节点测试的是多个属性的线性组合。也就是说，决策树的节点不是对某个单独的属性进行划分，而是对多个属性组合后的结果进行划分。

线性分类器 的公式为：
[
w_1 x_1 + w_2 x_2 + \dots + w_d x_d \leq t
]
解释如下：

(w_1, w_2, \dots, w_d)：表示属性 (x_1, x_2, \dots, x_d) 对应的权重。每个权重 (w_i) 代表属性 (x_i) 对分类的重要性。
(x_1, x_2, \dots, x_d)：表示样本的属性值。例如，样本的密度、含糖量等。
(t)：是一个阈值，表示通过这个阈值来决定样本属于哪个类别。

公式含义：通过多个属性的线性组合，决策树能够在数据空间中形成一个斜的划分边界，而不是像传统决策树那样形成轴平行的划分边界。