。

它通过一系列的“是或否”的决策来分类数据。

每个决策是基于数据的某个属性进行的#xff0c;如“色泽是青绿吗#xff1f;”。

决策树的核心是通过树状结构#xff0c;将一个复杂的问题逐步拆解为多个简单的二元问…1.1

决策树是用于分类和回归的机器学习算法。

它通过一系列的“是或否”的决策来分类数据。

每个决策是基于数据的某个属性进行的如“色泽是青绿吗”。

决策树的核心是通过树状结构将一个复杂的问题逐步拆解为多个简单的二元问题最终通过一系列决策得出结果。

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

1.2

根节点根节点是决策树的起点它包含了所有数据。

在决策树中所有的分类判断从根节点开始。

内部节点每个内部节点代表对某个属性的判断。

例如“颜色是否为红色”可以是一个内部节点。

叶节点叶节点代表最终的分类结果。

例如经过一系列判断后叶节点会告诉我们“是苹果”或“不是苹果”。

颜色/

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

1.3

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

输入给定一个训练数据集

是它的分类结果。

属性集是可用来划分样本的特征比如色泽、根蒂等。

生成节点从根节点开始递归创建决策树。

如果节点包含的样本都属于同一类别如都是“好瓜”那么将该节点标记为叶节点并终止进一步划分。

选择划分属性当节点中的样本不属于同一类别时需要选择一个最优的属性来划分样本。

例如如果属性“色泽”对样本的分类效果最好选择它来划分数据。

递归生成子节点对于每个子节点重复步骤2和3直到所有节点都成为叶节点或无法继续划分为止。

1.4

样本同类如果当前节点中所有样本属于同一类如全部是好瓜则该节点直接标记为叶节点无需继续划分。

属性无法再划分如果样本在当前所有属性上的取值相同则无法继续划分。

这种情况下将该节点标记为样本数最多的类。

样本集为空如果某个节点没有样本则标记为其父节点样本数最多的类别。

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

递归过程决策树的生成是一个递归的过程树会不断地被细化直到所有节点都无法再进行划分。

每次划分时都选择当前最优的属性来进行这保证了决策树能够尽量准确地分类数据。

1.5

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

划分选择

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

我们首先来看

信息熵是衡量数据集纯度的一个指标。

(\sum_{k1}^{|Y|})这是一个求和符号表示对

(k)

(p_k)然后将这些占比进行加权求和用来衡量整个数据集的不确定性。

熵值越大表示数据集越混乱类别分布越分散熵值越小表示数据集越纯净样本集中在某一类别。

示例假设在一个西瓜数据集中有

信息增益。

信息增益是指划分后数据集的熵值减少量。

(Ent(D))表示划分之前整个数据集

(D)

的所有可能取值例如“色泽”属性可能有“青绿”、“乌黑”、“浅白”等取值。

(\frac{|D_v|}{|D|})表示子集

(D_v)

的比例。

即在划分后每个子集的大小对总信息增益的贡献权重。

(Ent(D_v))表示子集

(D_v)

进行划分时数据集的纯度提升了多少。

信息增益越大说明使用该属性进行划分能够更有效地减少数据集的不确定性从而使得子集更加纯净。

(D)

(D_3)浅白。

分别计算每个子集的信息熵和它们在总数据集中的比例然后计算出信息增益。

2.2

增益率用于避免信息增益对可取值较多的属性如编号产生偏好。

它的公式为

Gain_ratio(D,

示例例如编号属性虽然对每个样本的分类都能得到高的信息增益但它并没有实际意义。

增益率通过使用固有值来调整这种偏好使得划分更加合理。

2.3

公式含义基尼指数衡量的是从数据集中随机抽取两个样本它们属于不同类别的概率。

基尼指数越小表示数据集的纯度越高。

Gini(D)

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

剪枝处理

剪枝是决策树学习中的一个重要步骤用来防止过拟合。

过拟合是指模型对训练数据过度拟合导致对新数据的泛化能力下降。

剪枝可以减少模型的复杂度从而提高模型的泛化能力。

预剪枝在生成决策树的过程中提前停止分裂避免生成过多分支。

后剪枝先生成一棵完整的决策树然后从叶节点开始向上回溯去掉一些分支。

3.1

预剪枝在每次划分前通过评估划分是否能提高模型的泛化性能决定是否进行划分。

如果划分不能带来显著的性能提升算法会停止划分并将当前节点标记为叶节点。

示例假设我们正在生成一棵决策树当前节点的样本集已经通过某个属性划分但继续划分带来的性能提升很小甚至可能对新数据的预测准确率下降。

在这种情况下预剪枝策略会停止继续划分将当前节点标记为叶节点。

3.2

后剪枝是在生成一棵完整的决策树之后通过逐步删除一些分支来减少过拟合。

后剪枝的基本步骤是从树的叶节点开始向上回溯逐一评估是否可以将当前节点的子树替换为一个叶节点。

如果替换能提高泛化性能则进行剪枝。

示例假设我们有一棵完整的决策树其中某个分支只对训练数据有作用但对新数据预测时效果很差。

在这种情况下后剪枝策略会删除这个分支将其父节点直接标记为叶节点。

总结剪枝的目的在于减少决策树的复杂度避免过拟合从而提高模型的泛化能力。

预剪枝和后剪枝各有优缺点前者可以减少生成树的时间但可能错过某些有效的划分后者能够保留更多的信息但需要更多的计算资源。

连续与缺失值

缺失值例如某些样本在某个属性上没有取值。

决策树算法需要处理这些情况以确保模型的可靠性。

4.1

对于离散属性决策树可以直接根据取值划分数据集但连续属性的取值范围很大不能简单地枚举所有可能值。

因此决策树通过

二分法

(t)决策树可以将连续属性分为两部分计算划分后的信息增益。

最终选择信息增益最大的划分点作为最佳划分。

0.1

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

处理缺失值的常见方法包括

属性值缺失当某个样本在某个属性上的取值缺失时可以通过样本权重的调整来处理。

具体方法是将样本按比例分配到不同的子节点并根据样本的权重调整划分结果。

分类结果缺失在分类过程中如果某个样本的某个属性取值缺失决策树可以同时将样本分配到所有可能的子节点并根据样本的权重调整最终的分类结果。

Gain(D,

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

示例假设我们有一个数据集其中某些样本的“色泽”属性缺失。

我们可以根据样本权重将缺失的样本分配到不同的子节点计算这些子节点的信息增益。

多变量决策树

是决策树的扩展版本它允许使用多个属性的线性组合来进行划分而不仅仅是单个属性。

这种方法能够处理复杂的分类问题特别是当数据的决策边界不是简单的轴平行时。

5.1

在普通的决策树中非叶节点对单个属性进行测试如“色泽是否为青绿”。

而在多变量决策树中每个非叶节点测试的是多个属性的线性组合。

也就是说决策树的节点不是对某个单独的属性进行划分而是对多个属性组合后的结果进行划分。

线性分类器

x_d)表示样本的属性值。

例如样本的密度、含糖量等。

(t)是一个阈值表示通过这个阈值来决定样本属于哪个类别。

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

5.2

多变量决策树允许节点使用多个属性的组合进行划分因此它可以生成“斜决策边界”。

这种划分方式能够更好地处理复杂数据例如当数据的决策边界是斜的而不是平行于坐标轴时。

示例在普通决策树中如果我们使用属性“密度”和“含糖量”分别对数据进行划分得到的决策边界是平行于这些属性轴的。

但在多变量决策树中我们可以对这两个属性的线性组合进行划分例如“0.5

0.3

在西瓜数据集上传统决策树的划分可能会形成直角形的决策区域而多变量决策树可以通过线性组合形成斜线划分更加灵活。

阅读材料

这一部分列出了与决策树相关的经典算法和文献它们对决策树的研究和发展起到了重要的作用。

6.1

ID3最早的决策树算法之一它使用信息增益作为划分标准来选择最优属性。

C4.5ID3的改进版本使用增益率来避免对取值较多的属性产生偏好并且能够处理连续值和缺失值。

CART分类与回归树Classification

and

1998]提供了决策树相关文献的综述和研究指南。

[Quinlan,

1993]C4.5决策树算法的原始论文介绍了增益率和剪枝处理等技术。

[Breiman

al.,

1984]CART算法的提出者之一介绍了基于基尼指数的决策树算法。

6.3

剪枝对决策树的泛化性能有显著影响。

过多的分支会导致决策树过拟合剪枝能够减少过拟合的风险提高模型对新数据的泛化能力。

实验表明通过剪枝可以将决策树的泛化性能提高约25%特别是在数据带有噪声时。

6.4

的一系列算法通过贪心搜索和线性分类器来改进多变量决策树的学习过程。

其他算法则结合神经网络的思想将感知机或神经网络嵌入到决策树的叶节点中形成混合模型从而提高学习能力。

6.5

增量学习即能够在接收到新的样本后对已有的决策树模型进行部分更新而不是重新训练整个模型。

代表性算法有

ID4、ID5R

ITI它们通过对分支路径的调整来进行局部更新降低了每次接收新样本时的训练时间开销。