用家里网络做网站,广州seo团队,雷军做的网站,电子商务网站建设下载1.1 决策树的定义
决策树是用于分类和回归的机器学习算法。它通过一系列的“是或否”的决策来分类数据。每个决策是基于数据的某个属性进行的#xff0c;如“色泽是青绿吗#xff1f;”。决策树的核心是通过树状结构#xff0c;将一个复杂的问题逐步拆解为多个简单的二元问…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 总结与示例
为了更好地理解决策树的流程我们可以看以下的例子 问题判断一个水果是否是苹果。 属性 颜色红色、绿色、黄色形状圆形、椭圆形味道甜、酸。 决策过程如下 颜色/ \红色 其他/ \形状 不是苹果/ \
圆 其他|
味道|
甜 - 苹果在这个决策树中首先判断颜色如果是红色则继续判断形状如果形状是圆的再判断味道最终如果味道是甜的可以判断为苹果。 2. 划分选择
2.1 信息增益
首先信息增益的目标是通过某个属性对数据集进行划分使得划分后的数据集更加“纯净”即每个子集尽可能只包含同一类别的样本。
我们首先来看 信息熵 的定义 [ Ent(D) - \sum_{k1}^{|Y|} p_k \log_2 p_k ] 这个公式的每一个符号解释如下
(Ent(D))表示数据集 (D) 的 信息熵是衡量数据集纯度的一个指标。(\sum_{k1}^{|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_{k1}^{|Y|} p_k^2 ] 每个符号的解释如下
(Gini(D))表示数据集 (D) 的基尼指数。(\sum_{k1}^{|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)是一个阈值表示通过这个阈值来决定样本属于哪个类别。
公式含义通过多个属性的线性组合决策树能够在数据空间中形成一个斜的划分边界而不是像传统决策树那样形成轴平行的划分边界。
5.2 多变量决策树的划分方式
多变量决策树允许节点使用多个属性的组合进行划分因此它可以生成“斜决策边界”。这种划分方式能够更好地处理复杂数据例如当数据的决策边界是斜的而不是平行于坐标轴时。
示例在普通决策树中如果我们使用属性“密度”和“含糖量”分别对数据进行划分得到的决策边界是平行于这些属性轴的。但在多变量决策树中我们可以对这两个属性的线性组合进行划分例如“0.5 * 密度 0.3 * 含糖量 \leq 0.7”从而得到一个斜的决策边界。
图示 在西瓜数据集上传统决策树的划分可能会形成直角形的决策区域而多变量决策树可以通过线性组合形成斜线划分更加灵活。 6. 阅读材料
这一部分列出了与决策树相关的经典算法和文献它们对决策树的研究和发展起到了重要的作用。
6.1 经典算法
ID3最早的决策树算法之一它使用信息增益作为划分标准来选择最优属性。C4.5ID3的改进版本使用增益率来避免对取值较多的属性产生偏好并且能够处理连续值和缺失值。CART分类与回归树Classification and Regression Tree它使用基尼指数作为划分标准适用于分类和回归任务。
6.2 其他相关文献
[Murthy, 1998]提供了决策树相关文献的综述和研究指南。[Quinlan, 1993]C4.5决策树算法的原始论文介绍了增益率和剪枝处理等技术。[Breiman et al., 1984]CART算法的提出者之一介绍了基于基尼指数的决策树算法。
6.3 决策树的泛化性能
剪枝对决策树的泛化性能有显著影响。过多的分支会导致决策树过拟合剪枝能够减少过拟合的风险提高模型对新数据的泛化能力。实验表明通过剪枝可以将决策树的泛化性能提高约25%特别是在数据带有噪声时。
6.4 多变量决策树的研究
OC1 和 Brodley and Utgoff 的一系列算法通过贪心搜索和线性分类器来改进多变量决策树的学习过程。其他算法则结合神经网络的思想将感知机或神经网络嵌入到决策树的叶节点中形成混合模型从而提高学习能力。
6.5 增量学习
决策树学习的另一个方向是 增量学习即能够在接收到新的样本后对已有的决策树模型进行部分更新而不是重新训练整个模型。代表性算法有 ID4、ID5R 和 ITI它们通过对分支路径的调整来进行局部更新降低了每次接收新样本时的训练时间开销。
