李航老师《统计学习方法》第五章阅读笔记

决策树（decision tree）是一种基本的分类与回归方法。本章主要讨论用于分类的决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。

以下是关于分类决策树的一些基本概念和特点：

1. 树形结构：决策树模型呈现为一种树状结构，其中包括根节点、内部节点和叶子节点。每个节点表示一个特征或属性，每个边表示一个特征值或属性值的判断条件。从根节点开始，通过遵循不同的条件路径，最终到达叶子节点，叶子节点代表了一个类别标签或回归值。
2. if-then规则：决策树可以看作是一组if-then规则的集合，每个规则表示一个从根节点到叶子节点的路径，其中包括特征条件和对应的类别标签。当新样本进入决策树时，它会根据特征的条件依次遵循路径，最终确定样本所属的类别。
3. 条件概率分布：决策树也可以看作是定义在特征空间与类别空间上的条件概率分布。每个内部节点表示一个特征条件，每个叶子节点表示一个类别，并且沿着路径的条件概率决定了样本被分类到不同的类别。
4. 学习过程：决策树的学习过程通常包括以下步骤：
   • 特征选择：选择最佳的特征作为根节点，以最大化分类效果。
   • 分裂节点：将数据集根据选定的特征进行分割，生成子节点。
   • 递归学习：对每个子节点递归应用上述步骤，直到达到停止条件（例如，达到最大深度、样本数量小于阈值等）。
   • 剪枝（可选）：在生成决策树后，可以应用剪枝算法来减小过拟合风险。
5. 优点：决策树具有易于理解和解释的特点，可以生成清晰的分类规则。它们适用于离散和连续特征，对缺失值具有一定的容忍性，且在某些情况下表现良好。
6. 缺点：决策树容易过拟合训练数据，因此需要进行剪枝等正则化方法。它们可能在处理复杂问题时产生过多的规则，导致模型过于复杂。此外，决策树对数据中的噪声和不稳定性敏感。

决策树是一种强大的机器学习工具，适用于各种分类和回归任务。通过合适的参数调整和正则化方法，可以改善其性能并减小过拟合的风险。在实际应用中，决策树通常与集成学习方法（如随机森林和梯度提升树）相结合，以进一步提高模型的性能。

它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

特征空间（Feature Space）和类空间（Class Space）是机器学习中常用的两个概念，它们用于描述模型和数据的属性。

1. 特征空间（Feature Space）：
   • 特征空间是指用来描述样本（数据点）的属性或特征的空间。每个样本可以在特征空间中表示为一个向量，其中每个维度对应一个特征。
   • 在特征空间中，每个维度表示一个特征，而每个样本由这些特征的值组成。例如，在文本分类任务中，特征空间可能包括词汇表中的单词，每个维度表示一个单词在文本中的出现次数或TF-IDF值。
   • 特征空间的维度取决于数据集中的特征数量，可以是高维的（包含许多特征）或低维的（包含较少的特征）。
2. 类空间（Class Space）：
   • 类空间是指用来描述样本所属类别或标签的空间。每个样本都被分配到类空间中的一个类别。
   • 在分类问题中，类空间包括所有可能的类别或标签。每个样本在类空间中被分配到一个类别，以表示其所属类别。
   • 类空间通常是离散的，每个类别由一个唯一的标识符表示。例如，二元分类问题中的类空间可能包括 “正类” 和 “负类” 两个类别。

在机器学习任务中，特征空间和类空间之间的映射关系是模型的关键。机器学习模型的目标是学习如何从特征空间中的数据映射到类空间中的类别。决策树、支持向量机、神经网络等各种模型都是用来建立特征空间到类空间的映射关系，并用于分类或回归任务。
总之，特征空间描述了数据的特征属性，而类空间描述了数据的类别或标签，它们在机器学习中是重要的概念，用于建模和解决各种问题。

其主要优点：1.模型具有可读性；2.分类速度快

阶段	操作
学习时	利用训练数据，根据损失函数最小化的原则建立决策树模型
预测时	对新的数据，利用决策树模型进行分类

决策树学习通常包括3个步骤：特征选择->决策树的生成->决策树的修剪

5.1决策树模型与学习

5.1.1决策树模型

定义5.1(决策树)：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型:内部结点(internalnode)和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。

5.1.2决策树与if-then规则

5.1.3决策树与条件概率分布

5.1.4决策树学习

决策树学习用损失函数表示这一目标。如下所述，决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。
当损失函数确定后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题，这样得到的决策树是次最优(sub-optimal)的。

1. 从所有可能的决策树中选择最优决策树是一个非常复杂的问题，它属于NP完全问题，这意味着在现实世界中，找到确切的最优解可能需要大量时间，甚至是不可行的。
2. 为了解决这个问题，决策树学习算法通常采用一种称为启发式方法的策略。这就像在迷宫中找到出口，你可能不会尝试每个可能的路径，而是根据一些规则或经验选择下一步，希望最终找到出口。在决策树学习中，这些规则和经验可以是分裂节点的标准、剪枝策略、节点的排序等。
3. 使用这些启发式方法，我们可以获得一个次最优（sub-optimal）的决策树，这意味着它可能不是全局最优解，但在实践中性能仍然很好。次最优的决策树通常能够很好地拟合训练数据，并且具有较好的泛化性能，可以用于对未见数据的分类或回归。

简而言之，决策树学习算法面临一个非常复杂的优化问题，通常无法找到全局最优解。因此，它使用一些经验法则和启发式方法来近似求解这个问题，最终得到一个次最优的决策树，以在实际应用中表现良好。这类似于在实际问题中使用经验和直觉来做出决策，而不是尝试每种可能的选择。

决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。

决策学习常用的算法有ID3、C4.5与CART，下面结合这些算法分别叙述决策树学习的特征选择、决策树的生成和剪枝过程。

5.2特征选择

5.2.1特征选择问题

通常特征选择的准则是信息增益或信息增益比

5.2.2信息增益

为了便于说明，先给出熵与条件熵的定义
在信息论与概率统计中，熵（entropy）是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为
$$P(X=x_i)=p_i,i=1,2,...,n$$
则随机变量X的熵定义为（若$p_i=0$，则定义$0log0=0$）
$$H(X)=-\sum _{i=1}^n{p}_{i}log{p}_i$$
由于熵只依赖于X的分布，而与X的取值无关，所以也可将X的熵记作H§，即
$$H(p)=-\sum _{i=1}^n{p}_{i}log{p}_i$$
熵越大，随机变量的不确定性就越大。从定义可验证
$$0\le H(p)\le logn$$

它是信息熵的基本性质之一。这是信息熵 $H(p)$ 的性质，不需要再次证明。

设有随机变量$(X,Y)$，其联合概率分布为
$$P(X=x_i,Y=y_j)=p_{ij},i=1,2,...,n;j=1,2,...,m$$
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵（conditional entropy）H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望
$$H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x_i)$$
这里，$p_i=P(X=x_i),i=1,2,...,n$

让我们通过一个简单的例子来计算条件熵。
假设我们有两个随机变量X和Y，它们的联合分布如下：

X/Y	Y=1	Y=2
X=1	0.2	0.1
X=2	0.3	0.4
X=3	0.1	0.2

首先，我们需要计算条件概率分布 $P(Y|X)$，然后根据这个分布计算条件熵 $H(Y|X)$。让我们按照步骤进行计算：
步骤 1：计算边际概率分布 $P(X)$
首先，我们计算随机变量X的边际概率分布 $P(X)$，即X取每个可能值的概率。
$P(X=1)=0.2+0.1+0.1=0.4$
$P(X=2)=0.3+0.4+0.2=0.9$
$P(X=3)=0.1+0.2=0.3$
步骤 2：计算条件概率分布 $P(Y|X)$
接下来，我们计算条件概率分布 $P(Y|X)$，即在给定X的条件下Y的概率分布。我们可以使用条件概率的定义来计算它：
$P(Y=1|X=1)=\frac{P(X=1,Y=1)}{P(X=1)}=\frac{0.2}{0.4}=0.5$
$P(Y=2|X=1)=\frac{P(X=1,Y=2)}{P(X=1)}=\frac{0.1}{0.4}=0.25$
$P(Y=1|X=2)=\frac{P(X=2,Y=1)}{P(X=2)}=\frac{0.3}{0.9}=\frac{1}{3}$
$P(Y=2|X=2)=\frac{P(X=2,Y=2)}{P(X=2)}=\frac{0.4}{0.9}\approx 0.4444$
$P(Y=1|X=3)=\frac{P(X=3,Y=1)}{P(X=3)}=\frac{0.1}{0.3}\approx 0.3333$
$P(Y=2|X=3)=\frac{P(X=3,Y=2)}{P(X=3)}=\frac{0.2}{0.3}\approx 0.6667$
步骤 3：计算条件熵 $H(Y|X)$
现在我们可以使用条件熵的定义来计算 $H(Y|X)$，根据公式：
$$H(Y|X)=\sum _{i=1}^{n}P(X=x_i)H(Y|X=x_i)$$
代入我们计算得到的条件概率值：
$$H(Y|X)=P(X=1)\cdot [-(0.5{\log }_2(0.5)+0.25{\log }_2(0.25))]+P(X=2)\cdot [-(\frac{1}{3}{\log }_2(\frac{1}{3})+0.4444{\log }_2(0.4444))]+P(X=3)\cdot [-(0.3333{\log }_2(0.3333)+0.6667{\log }_2(0.6667))]$$
计算每个部分的值并求和：
$$H(Y|X)\approx 0.8464+0.6492+0.6365\approx 2.1321$$
所以，在给定随机变量X的条件下，随机变量Y的条件熵 $H(Y|X)$ 约为2.1321。

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。此时，若有0概率，令0log0=0

经验熵和经验条件熵是信息论中的概念，它们涉及到基于实际观测数据来估计随机变量的熵和条件熵。

1. 经验熵（Empirical Entropy）：
   经验熵是指根据实际观测数据来估计一个随机变量的熵。通常情况下，我们没有完全的先验知识，无法直接知道随机变量的概率分布。因此，我们可以使用观测到的数据来估计这个分布，最常见的估计方法之一是极大似然估计。通过统计数据中每个事件（或取值）的频率，我们可以估计随机变量的概率分布，然后计算熵。这个估计得到的熵被称为经验熵。
2. 经验条件熵（Empirical Conditional Entropy）：
   经验条件熵是在已知另一个随机变量的条件下，根据实际观测数据估计另一个随机变量的条件熵。与经验熵类似，我们可以使用观测到的数据来估计条件概率分布，然后计算条件熵。这个估计得到的条件熵被称为经验条件熵。

这两个概念的核心思想是，当我们不知道真实的概率分布，但有一些观测数据时，我们可以基于数据来估计信息熵和条件熵，以便在实际问题中应用信息论的概念。这对于机器学习、数据分析和模型建立等领域非常有用，因为通常我们只能获得有限的数据，而无法获得完整的概率分布信息。所以，经验熵和经验条件熵允许我们在缺乏完整信息的情况下进行信息论分析。

信息增益（information gain）表示得知特征X的信息而使得类Y的信息不确定性减少的程度
定义5.2（信息增益）特征A对训练数据集D的信息增益$g(D,A)$，定义为集合D的经验熵$H(D)$与特征A给定条件下D的经验条件熵$H(D|A)$之差，即
$$g(D,A)=H(D)-H(D|A)$$
一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息（mutual information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

5.2.3信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。

以信息增益作为划分训练数据集的特征存在偏向于选择取值较多的特征的问题，这是因为信息增益的计算方式使得在有更多取值的特征上产生更多的子分支，从而可能导致信息增益偏向于选择取值较多的特征。让我更详细地解释这个问题。

信息增益的计算方式涉及到条件熵（Conditional Entropy），其计算公式为：

$$H(D|A)=\sum _{i=1}^n\frac{|D_i|}{|D|}\cdot H(D_i)$$

其中，$H(D|A)$ 是在特征 $A$ 条件下数据集 $D$ 的条件熵，$D_i$ 是特征 $A$ 的每个取值对应的子数据集，$|D_i|$ 表示子数据集的大小，$|D|$ 表示总数据集的大小。

注意到在计算条件熵时，分母 $|D|$ 是不变的，但分子 $|D_i|$ 取决于特征 $A$ 的取值个数。如果特征 $A$ 的取值较多，那么就会有更多的 $|D_i|$ 需要相加，这会导致条件熵的计算中有更多的项。

这个问题的关键在于，条件熵的值越低，信息增益越高。因此，如果特征 $A$ 具有更多的取值，它可能会导致更多的子分支，每个子分支对应一个取值，而每个子分支的条件熵通常较低，因为数据更容易在这个子分支中进行分类。这会使得信息增益在计算时受到特征取值数量的影响，偏向于选择取值较多的特征。

为了克服这个问题，可以考虑使用一些改进的特征选择准则，例如信息增益比（Information Gain Ratio）或基尼不纯度（Gini impurity）。这些准则在计算中会考虑到特征取值的数量，以减轻信息增益对取值较多特征的偏向，使得特征选择更加平衡。

5.3决策树的生成

5.3.1 ID3算法

5.3.2 C4.5的生成算法

5.4决策树的剪枝

5.5 CART算法

5.5.1 CART生成

5.5.2 CART剪枝