企业网站设计目的和意义,ci框架建设网站案例,网站建设的展望 视频,凡科可以做视频网站吗目录 一、回忆1、*机器学习的三要素#xff1a;1#xff09;*函数族2#xff09;*目标函数2.1#xff09;*模型的其他复杂度参数 3#xff09;*优化算法 2、*前处理/后处理1#xff09;前处理#xff1a;特征工程2#xff09;后处理#xff1a;模型选择和模型评估 3、… 目录 一、回忆1、*机器学习的三要素1*函数族2*目标函数2.1*模型的其他复杂度参数 3*优化算法 2、*前处理/后处理1前处理特征工程2后处理模型选择和模型评估 3、*机器学习开发流程1数据收集2特征探索分析3特征工程4模型训练5性能评估 二、决策树Decision Treea、基本概念b、决策树的构建1初始化2选择一个合适的树结构3确定在每个非叶子节点上要使用的特征4在每个非叶子节点上选择合适的决策规则5停止划分条件6剪枝 *拓展知识熵 信息增益1、熵系统不确定的度量2、数据集的经验熵3、条件熵4、经验条件熵5、信息增益1信息增益的定义2ID3算法3多叉树4图示说明 6、信息增益与决策树分裂1数据集概览2总体数据集的信息熵 H ( D ) H(\mathcal{D}) H(D)3根据特征划分后的信息熵3.1日志密度L 4信息增益计算5决策树分裂 7、信息增益率1ID3算法的局限性3C4.5算法信息增益率4总结 c、决策树的损失函数1Gini指数2为什么不使用错误率3Gini指数的优势4图示说明 2错误率 vs. Gini指数2.1示例说明2.2决策树分裂效果2.3左子结点分析左子结点分裂效果 2.4右子结点分析右子结点分裂效果 3分裂后的平均效果3.1分裂后的平均错误率和熵3.2分裂前的情况 三、分类回归树Classification And Regression Tree CART 1、基本概念2、例离散型特征3、例连续型特征3.1根据特征width的取值对所有样本进行排序得到可能的阈值为6.25, 6.55, 6.75, 6.95。3.2根据特征height的取值对所有样本进行排序得到可能的阈值为6.3, 8.05, 9.55。 4、划分停止条件5、剪枝1剪枝过程2剪枝策略3验证集4Scikit-Learn中对剪枝的支持 四、决策树的优缺点1、决策树模型的优点2、决策树模型的缺点 五、DecisionTreeClassifier类1、DecisionTreeClassifier的参数2、DecisionTreeClassifier的属性3、DecisionTreeClassifier的方法 目录中带*注解的内容为通用部分非本章节特定内容。 一、回忆
1、*机器学习的三要素 - 函数族 F \mathcal{F} F这是一个函数的集合其中的每个函数 f f f 都属于这个集合即 f ∈ F f \in \mathcal{F} f∈F。 - 目标函数 J ( f ) J(f) J(f)这个函数用来衡量函数 f f f 的性能或质量。它是一个评价标准帮助我们了解函数的好坏。 - 优化算法我们的目标是找到一个函数 f ∗ f^* f∗它在函数族 F \mathcal{F} F 中使得目标函数 J ( f ) J(f) J(f) 的值最小。用数学表达式表示就是 f ∗ arg min f J ( f ) f^* \arg\min_f J(f) f∗argminfJ(f)。这意味着我们正在寻找一个函数它在所有可能的函数中目标函数的值是最小的。 这些概念是优化问题的基础也是在优化问题中我们通常会遇到以下几个关键概念。无论是在机器学习、工程优化还是其他领域理解和应用这些概念都是至关重要的。
1*函数族 在机器学习和统计学中函数族是指一组具有相似形式或结构的函数。以下是一些常见的函数族 - 线性模型 f ( x ) w T x f(x) \mathbf{w}^T x f(x)wTx其中 w \mathbf{w} w 是权重向量 x x x 是输入向量。这种模型假设输出是输入的线性组合。 - 多项式一种扩展的线性模型可以捕捉输入变量之间的非线性关系。 - 核方法由核函数决定这种方法可以在高维空间中有效地处理数据而不需要显式地计算高维特征。 - 决策树分段常数函数通过一系列的决策规则将输入空间分割成不同的区域并为每个区域分配一个常数值。 - 神经网络由网络结构决定这是一种模仿人脑神经元连接方式的模型能够学习和表示复杂的函数关系。 - 集成学习多棵决策树的加权平均这种方法通过结合多个模型的预测来提高整体的预测性能。 随机森林一种集成学习方法通过构建多棵决策树并进行投票或平均来提高预测的准确性和鲁棒性。GBDT梯度提升决策树另一种集成学习方法通过逐步构建决策树来纠正前一个模型的错误。 - 概率图模型利用条件独立假设简化概率计算这种模型可以有效地表示和推理变量之间的概率关系。 函数族可以根据是否需要调整参数来分为两类 参数模型包括线性模型、多项式、神经网络、概率图模型。这些模型需要通过训练数据来调整模型参数。非参数模型包括核方法、决策树、集成学习。这些模型不依赖于固定的参数数量而是根据数据的复杂性来调整模型的复杂度。 2*目标函数 在机器学习中目标函数是用来评估模型性能的函数它通常由两部分组成损失函数和正则项。目标函数的一般形式为 J ( f ) L ( f ) λ R ( f ) J(f) L(f) \lambda R(f) J(f)L(f)λR(f) 其中 J ( f ) J(f) J(f) 是目标函数 L ( f ) L(f) L(f) 是损失函数 R ( f ) R(f) R(f) 是正则项 λ \lambda λ 是正则参数用于平衡损失函数和正则项的影响。 - 损失函数 L ( f ) L(f) L(f)衡量函数 f f f 与训练数据的拟合程度。常见的损失函数包括 负对数似然损失如 L2/L1 损失、交叉熵损失。合页损失SVM、 ε \varepsilon ε 不敏感损失SVR。聚类损失如 K均值、谱聚类。降维损失如结构保持、重构。 - 正则项 R ( f ) R(f) R(f)衡量函数 f f f 自身的复杂程度以防止过拟合。常见的正则项包括 L2 正则、L1 正则。K-Lipschitz 连续WGAN。 - 正则参数 λ \lambda λ控制模型复杂度的参数。 当 λ \lambda λ 越小模型可以更复杂训练误差越小但可能导致偏差小、方差大。当 λ \lambda λ 越大模型更简单训练误差可能增大但偏差大、方差小。 通过调整正则参数 λ \lambda λ我们可以在模型的偏差和方差之间找到一个平衡点以获得最佳的泛化能力。 2.1*模型的其他复杂度参数 在机器学习中模型的复杂度不仅由其基本结构决定还受到一些关键参数的影响。以下是一些常见模型的复杂度参数 - 线性模型特征的数目。特征越多模型的表达能力越强但也可能增加过拟合的风险。 - 多项式多项式阶数。阶数越高模型能够捕捉的非线性关系越复杂但同样可能导致过拟合。 - 核方法核函数超参数如 RBF 核的核函数宽度。这些参数决定了模型在特征空间中的映射方式影响模型的复杂度和泛化能力。 - 决策树 树的最大深度控制树的复杂度防止过拟合。叶子结点数目影响模型的精细程度。叶子结点代表的训练样本数目决定每个叶子结点需要多少样本来分裂。 - 神经网络 网络的连接方式全连接、局部连接等影响信息的流动和模型的学习能力。网络的层数层数越多模型的学习能力越强但计算成本和过拟合风险也增加。每层的神经元数目影响模型的表达能力和计算复杂度。 这些参数的选择对于模型的性能至关重要需要根据具体问题和数据集进行调整和优化。 3*优化算法 优化算法是机器学习中用于寻找模型参数最优值的方法。目标是找到一个函数 f ∗ f^* f∗使得目标函数 J ( f ) J(f) J(f) 最小化 f ∗ arg min f J ( f ) f^* \arg\min_f J(f) f∗argfminJ(f) 以下是一些常见的优化算法 - 梯度下降/上升 梯度计算损失函数的梯度指导参数更新的方向。 批处理梯度下降使用所有数据计算梯度。随机梯度下降每次使用一个样本计算梯度。小批量梯度下降每次使用一小部分样本计算梯度。动量法加速梯度下降减少震荡。 学习率控制每次更新的步长。 学习率的影响学习率过大可能导致不收敛过小则收敛速度慢。自适应学习率根据训练过程动态调整学习率。 - 坐标下降/上升每次选择一个或一部分参数进行更新。 K均值聚类一种常用的聚类算法。EM期望最大化一种迭代算法用于含有隐变量的概率模型。Lasso、SMO用于解决正则化问题的优化算法。 这些算法各有优缺点选择合适的优化算法可以显著提高模型的训练效率和性能。 2、*前处理/后处理
1前处理特征工程 *特征工程的具体细节会在单独章节讲到 大致流如下 - 数据探索性分析 -特征编码 - 特征预处理 - 特征选择 - 特征工程与机器学习模型一起考虑 - 天下没有免费的午餐原则 表明没有任何单一的机器学习算法能够在所有问题上都表现最好。这个原则强调了算法选择的相对性和问题依赖性。“没有免费的午餐”No Free Lunch,NFL原则是机器学习领域中的一个重要概念它表明没有任何单一的机器学习算法能够在所有问题上都表现最好。这个原则强调了算法选择的相对性和问题依赖性 理解“没有免费的午餐”原则 1.算法的局限性不同的算法对不同类型的数据和问题有不同的适应性。例如线性回归可能在线性可分的数据上表现良好但在非线性问题上可能就不够有效。 2.问题的特性问题的复杂性、数据的分布、特征的数量和类型等都会影响算法的性能。一个算法可能在某些特定类型的问题上表现优异但在其他问题上可能表现平平。 3.算法的权衡在选择算法时通常需要在准确性、效率、可解释性等方面做出权衡。没有一种算法能在所有方面都做到最优。 4.经验的重要性在实际应用中选择最适合特定问题的算法往往需要基于经验和实验。这意味着需要对数据和问题有足够的理解以及对不同算法的性能有足够的了解。 5.组合方法由于单一算法可能无法解决所有问题研究者和实践者可能会采用集成学习等方法将多个算法结合起来以提高整体性能。 6. 持续学习随着数据和问题的不断变化算法也需要不断更新和调整。这意味着机器学习是一个持续学习和适应的过程。 总之“没有免费的午餐”原则提醒我们在机器学习中没有一种万能的解决方案。我们需要根据具体问题的特点和需求选择合适的算法并可能需要结合多种方法来达到最佳效果。 2后处理模型选择和模型评估 *详细内容会在单独章节展开讲解 - 训练集、验证集、测试集划分 - 训练集和验证集 - 留出法 - 交叉验证 - 训练误差、验证误差、测试误差 - 统计学习理论 - 奥卡姆剃刀原理 在模型选择和评估过程中我们将数据集划分为训练集、验证集和测试集。训练集用于训练模型验证集用于调整模型参数和选择最佳模型测试集则用于评估模型的最终性能。训练误差是我们在训练数据上得到的误差验证误差是在验证数据上得到的误差而测试误差则是在未见过的数据上得到的误差它更能反映模型在实际应用中的表现。 统计学习理论为我们提供了理解模型性能的理论基础其中奥卡姆剃刀原理强调在模型选择时应该倾向于更简单的模型除非有充分的理由选择更复杂的模型。这是因为更简单的模型更不容易过拟合同时也更容易理解和解释。 3、*机器学习开发流程 机器学习项目的开发过程可以概括为以下几个关键步骤 1数据收集 给定任务分析可能的相关特征收集数据。 2特征探索分析 对收集到的数据进行分析以发现有用的特征。 3特征工程 将原始数据转换成算法制定的输入。 4模型训练 确定机器学习算法函数集合 F \mathcal{F} F。模型训练在给定超参数的情况下确定模型参数。模型选择在验证集上评估模型预测性能。 5性能评估 模型测试和评估。模型应用。 在整个过程中我们的目标是找到一个能够从输入数据 x x x 预测输出结果 y y y 的模型即 y f ( x ) y f(x) yf(x)。这需要我们不断地调整模型参数和特征以提高模型的预测准确性和泛化能力。 以上就是对机器学习基础知识的回顾和复习接下来我们将进入本章的正题由分段常数函数族定义的决策树模型。
二、决策树Decision Tree
a、基本概念 决策树是一种多级分类器特别适用于多类分类任务和多峰分布数据。 分级是指将一个复杂问题转化为若干个简单的分类问题来解决。
从根结点到叶子结点的有向边代表了 一条决策路径 一条决策路径 一条决策路径。每个叶子结点对应一个分类器判别结果为样本占比最高的类别。决策树的路径是互斥并且完备的。 决策树可视化工具 - dtreeviz 介绍 - dtreeviz GitHub 在决策树中从根节点开始根据特征的不同取值数据被分配到不同的路径上。每个中间节点代表一个特征的测试而叶子节点则代表最终的分类结果。例如在图中根据花萼长度sepal length和花萼宽度sepal width的不同数据被分配到不同的路径上最终在叶子节点上得到分类结果。
b、决策树的构建 决策树的构建过程是一个递归的划分过程通过不断地将数据集划分为更小的子集直到满足停止条件。以下是构建决策树的详细步骤
1初始化 构建根节点将所有训练数据放在根节点并根节点加入叶子节点列表 若叶子节点列表为空算法结束返回生成的决策树 否则从叶子节点列表中挑选1个叶子节点
2.1若该叶子节点的样本集合已足够纯净计算该叶子节点的预测值并将其从叶子节点列表中删除不再划分2.2否则对该叶子节点进行进一步划分 1对每个特征的每个可能的划分方式尝试将该节点的样本集合进行划分计算划分后数据的纯净度和划分的分数2从第1步所有的划分中选择一个最优划分分数最高将训练数据划分成若干子集每个子集为当前节点的子节点并将这些子节点加入叶子节点列表同时将当前节点从叶子节点列表中删除
2选择一个合适的树结构
二叉树、多叉树
3确定在每个非叶子节点上要使用的特征
所有特征训练性能更好、随机选择特征子集更快测试性能可能也不差
4在每个非叶子节点上选择合适的决策规则
划分点的选择精确搜索/穷举所有可能的划分点训练性能更好、近似搜索/直方图更快测试性能可能也不差划分点的评价准则信息熵增益、信息熵增益率、Gini指数、带正则的Gini指数
5停止划分条件
足够纯净、最大深度、最大叶子节点数目、节点的最小样本数目、…
6剪枝
*拓展知识熵 信息增益
1、熵系统不确定的度量 熵是衡量系统不确定性的一种度量。对于一个随机变量 Y Y Y其可能的取值为 { 1 , 2 , . . . , C } \{1, 2, ..., C\} {1,2,...,C}熵的定义为 H ( Y ) − ∑ c 1 C P ( Y c ) log 2 ( P ( Y c ) ) H(Y) -\sum_{c1}^{C} P(Y c) \log_2(P(Y c)) H(Y)−c1∑CP(Yc)log2(P(Yc))
2、数据集的经验熵 数据集 D \mathcal{D} D的经验熵表示数据的不确定性或不纯净度的度量定义为 H ( D ) − ∑ c 1 C N c N log 2 ( N c N ) H(\mathcal{D}) -\sum_{c1}^{C} \frac{N_c}{N} \log_2 \left(\frac{N_c}{N}\right) H(D)−c1∑CNNclog2(NNc) 其中 N N N是数据集 D \mathcal{D} D中的样本数目 N c ∑ i 1 N I ( y i c ) N_c \sum_{i1}^{N} \mathbb{I}(y_i c) Nc∑i1NI(yic)是第 c c c个类别的样本数目。 用样本的比例估计概率分布相当于 P ( Y c ) π ^ c N c N ∑ i 1 N I ( y i c ) N P(Y c) \hat{\pi}_c \frac{N_c}{N} \frac{\sum_{i1}^{N} \mathbb{I}(y_i c)}{N} P(Yc)π^cNNcN∑i1NI(yic)。
3、条件熵 条件熵是衡量在已知特征 X X X的取值后随机变量 Y Y Y的不确定性。特征 X X X的取值为 { 1 , 2 , . . . , M } \{1, 2, ..., M\} {1,2,...,M}知道 X X X后 Y Y Y还有多少不确定条件熵定义为 H ( Y ∣ X ) ∑ m 1 M P ( X m ) H ( Y ∣ X m ) ∑ m 1 M P ( X m ) ∑ c 1 C P ( Y c ∣ X m ) log 2 ( P ( Y c ∣ X m ) ) H(Y|X) \sum_{m1}^{M} P(X m) H(Y|X m) \sum_{m1}^{M} P(X m) \sum_{c1}^{C} P(Y c|X m) \log_2(P(Y c|X m)) H(Y∣X)m1∑MP(Xm)H(Y∣Xm)m1∑MP(Xm)c1∑CP(Yc∣Xm)log2(P(Yc∣Xm))
4、经验条件熵 经验条件熵是根据特征 X X X的取值将数据划分为 M M M个子集 D m \mathcal{D}_m Dm。经验条件熵定义为 H ( D ∣ X ) ∑ m 1 M ∣ D m ∣ ∣ D ∣ H ( D m ) H(\mathcal{D}|X) \sum_{m1}^{M} \frac{|\mathcal{D}_m|}{|\mathcal{D}|} H(\mathcal{D}_m) H(D∣X)m1∑M∣D∣∣Dm∣H(Dm) 其中 N m ∣ D m ∣ ∑ i 1 N I ( x i m ) N_m |\mathcal{D}_m| \sum_{i1}^{N} \mathbb{I}(x_i m) Nm∣Dm∣∑i1NI(xim)表示第 m m m个子集的样本数目 N m , c ∑ i 1 N I ( x i m , y i c ) N_{m,c} \sum_{i1}^{N} \mathbb{I}(x_i m, y_i c) Nm,c∑i1NI(xim,yic)表示第 m m m个子集中第 c c c个类别的样本数目。 进一步展开经验条件熵的计算公式 H ( D ∣ X ) ∑ m 1 M N m N ∑ c 1 C − N m , c N m log 2 ( N m , c N m ) H(\mathcal{D}|X) \sum_{m1}^{M} \frac{N_m}{N} \sum_{c1}^{C} -\frac{N_{m,c}}{N_m} \log_2 \left(\frac{N_{m,c}}{N_m}\right) H(D∣X)m1∑MNNmc1∑C−NmNm,clog2(NmNm,c) 将数据集 D \mathcal{D} D按照特征 X X X取值分为 M M M个子集后各子集的平均不纯净程度。
5、信息增益
1信息增益的定义 特征 X X X对训练数据集 D \mathcal{D} D的信息增益 g ( D , X ) g(\mathcal{D}, X) g(D,X)定义为 g ( D , X ) H ( D ) − H ( D ∣ X ) g(\mathcal{D}, X) H(\mathcal{D}) - H(\mathcal{D}|X) g(D,X)H(D)−H(D∣X) 这表示将数据集 D \mathcal{D} D根据特征 X X X的取值划分为 M M M个子集后各子集的平均不确定性减少量。
2ID3算法 ID3算法选择信息增益最大的特征进行分裂即对标签 Y Y Y提供信息最多的特征倾向于选择取值多的特征进行分裂。
3多叉树 在决策树中多叉树是指每个节点可以有多于两个子节点的树结构。
4图示说明 下图展示了在知道某特征前后数据集的经验信息熵的变化
划分前经验信息熵为1划分后经验信息熵为0 图中 x 1 x_1 x1和 x 2 x_2 x2表示特征通过特征 x 1 x_1 x1的取值将数据集划分为两个子集显著减少了不确定性从而提高了模型的纯净度。
6、信息增益与决策树分裂
1数据集概览 下表展示了一个包含日志密度L、好友密度F、是否使用真实头像H和账号是否真实R的数据集
日志密度L好友密度F是否使用真实头像H账号是否真实Rssnonoslyesyeslmyesyesmmyesyeslmyesyesmlnoyesmsnonolmnoyesmsnoyesssyesno
2总体数据集的信息熵 H ( D ) H(\mathcal{D}) H(D) 计算得到数据集 D \mathcal{D} D的信息熵为 H ( D ) − 7 10 log 2 7 10 − 3 10 log 2 3 10 0.879 H(\mathcal{D}) -\frac{7}{10}\log_2\frac{7}{10} - \frac{3}{10}\log_2\frac{3}{10} 0.879 H(D)−107log2107−103log21030.879
3根据特征划分后的信息熵
3.1日志密度L 根据日志密度L划分后的信息熵 H ( D ∣ L ) H(\mathcal{D}|L) H(D∣L)计算如下 H ( D ∣ L ) 3 10 × H ( D s ) 4 10 × H ( D m ) 3 10 × H ( D l ) H(\mathcal{D}|L) \frac{3}{10} \times H(\mathcal{D}_s) \frac{4}{10} \times H(\mathcal{D}_m) \frac{3}{10} \times H(\mathcal{D}_l) H(D∣L)103×H(Ds)104×H(Dm)103×H(Dl) 具体计算为 3 10 × ( − 1 3 log 2 1 3 − 2 3 log 2 2 3 ) 4 10 × ( − 3 4 log 2 3 4 − 1 4 log 2 1 4 ) 3 10 × ( − 3 3 log 2 3 3 − 0 3 log 2 0 3 ) \frac{3}{10} \times \left(-\frac{1}{3}\log_2\frac{1}{3} - \frac{2}{3}\log_2\frac{2}{3}\right) \frac{4}{10} \times \left(-\frac{3}{4}\log_2\frac{3}{4} - \frac{1}{4}\log_2\frac{1}{4}\right) \frac{3}{10} \times \left(-\frac{3}{3}\log_2\frac{3}{3} - \frac{0}{3}\log_2\frac{0}{3}\right) 103×(−31log231−32log232)104×(−43log243−41log241)103×(−33log233−30log230) 0.603 0.603 0.603
4信息增益计算
根据日志密度L的信息增益 g ( D , L ) g(\mathcal{D}, L) g(D,L) g ( D , L ) H ( D ) − H ( D ∣ L ) 0.276 g(\mathcal{D}, L) H(\mathcal{D}) - H(\mathcal{D}|L) 0.276 g(D,L)H(D)−H(D∣L)0.276根据好友密度F的信息增益 g ( D , F ) g(\mathcal{D}, F) g(D,F) g ( D , F ) 0.553 g(\mathcal{D}, F) 0.553 g(D,F)0.553根据是否使用真实头像H的信息增益 g ( D , H ) g(\mathcal{D}, H) g(D,H) g ( D , H ) 0.033 g(\mathcal{D}, H) 0.033 g(D,H)0.033
5决策树分裂 因为好友密度F具有最大的信息增益或最小熵所以第一次分裂选择F为分裂属性。分裂后的结果如下表所示
日志密度L是否使用真实头像H账号是否真实Rsnonomnonomnoyessyesno 对应的决策树结构图如下 #mermaid-svg-gCwyK4LCVt9pwh7t {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-gCwyK4LCVt9pwh7t .error-icon{fill:#552222;}#mermaid-svg-gCwyK4LCVt9pwh7t .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-gCwyK4LCVt9pwh7t .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-gCwyK4LCVt9pwh7t .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-gCwyK4LCVt9pwh7t .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-gCwyK4LCVt9pwh7t .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-gCwyK4LCVt9pwh7t .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-gCwyK4LCVt9pwh7t .marker{fill:#333333;stroke:#333333;}#mermaid-svg-gCwyK4LCVt9pwh7t .marker.cross{stroke:#333333;}#mermaid-svg-gCwyK4LCVt9pwh7t svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-gCwyK4LCVt9pwh7t .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-gCwyK4LCVt9pwh7t .cluster-label text{fill:#333;}#mermaid-svg-gCwyK4LCVt9pwh7t .cluster-label span{color:#333;}#mermaid-svg-gCwyK4LCVt9pwh7t .label text,#mermaid-svg-gCwyK4LCVt9pwh7t span{fill:#333;color:#333;}#mermaid-svg-gCwyK4LCVt9pwh7t .node rect,#mermaid-svg-gCwyK4LCVt9pwh7t .node circle,#mermaid-svg-gCwyK4LCVt9pwh7t .node ellipse,#mermaid-svg-gCwyK4LCVt9pwh7t .node polygon,#mermaid-svg-gCwyK4LCVt9pwh7t .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-gCwyK4LCVt9pwh7t .node .label{text-align:center;}#mermaid-svg-gCwyK4LCVt9pwh7t .node.clickable{cursor:pointer;}#mermaid-svg-gCwyK4LCVt9pwh7t .arrowheadPath{fill:#333333;}#mermaid-svg-gCwyK4LCVt9pwh7t .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-gCwyK4LCVt9pwh7t .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-gCwyK4LCVt9pwh7t .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-gCwyK4LCVt9pwh7t .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-gCwyK4LCVt9pwh7t .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-gCwyK4LCVt9pwh7t .cluster text{fill:#333;}#mermaid-svg-gCwyK4LCVt9pwh7t .cluster span{color:#333;}#mermaid-svg-gCwyK4LCVt9pwh7t div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-gCwyK4LCVt9pwh7t :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} l s m l m s F yes s yes yes yes no 7、信息增益率
1ID3算法的局限性 ID3算法选择信息增益最大的特征进行分裂倾向于选择取值多的特征。例如如果一个特征如ID号取值非常多ID3算法可能会分裂出很多子节点但这些分裂对分类可能没有实际意义。
3C4.5算法信息增益率 C4.5算法改进了ID3算法选择信息增益率最大的特征进行分裂。特征 X X X对训练集 D \mathcal{D} D的信息增益比 g R ( D , X ) g_R(\mathcal{D}, X) gR(D,X)定义为 g R ( D , X ) g ( D , X ) H X ( D ) g_R(\mathcal{D}, X) \frac{g(\mathcal{D}, X)}{H_X(\mathcal{D})} gR(D,X)HX(D)g(D,X) 其中 g ( D , X ) g(\mathcal{D}, X) g(D,X)是特征 X X X的信息增益 H X ( D ) H_X(\mathcal{D}) HX(D)是特征 X X X的熵。通过计算信息增益率C4.5算法对信息增益乘以一个加权系数希望在增加信息的同时不要以分割太细为代价。
4总结 信息增益率是C4.5算法中用于选择分裂特征的关键指标它平衡了信息增益和特征取值的数量从而避免了ID3算法中可能出现的过分裂问题。
c、决策树的损失函数 决策树中使用的损失函数取决于任务的类型 分类任务通常使用Gini指数作为损失函数。Gini指数衡量的是数据集的不纯度值越小表示数据集越纯。 回归任务通常使用L2损失平方损失作为损失函数。L2损失衡量的是预测值与真实值之间差的平方和值越小表示模型的预测越准确。 L2正则在线性回归模型章节已经讲过下面我们主要来讲应用在分类任务中的Gini指数。
1Gini指数 Gini指数是一种衡量数据集不纯度的指标它无需使用对数函数因此计算速度更快。对于一个数据集 D \mathcal{D} D其Gini指数定义为 H ( D ) ∑ c 1 C π ^ c ( 1 − π ^ c ) H(\mathcal{D}) \sum_{c1}^{C} \hat{\pi}_c (1 - \hat{\pi}_c) H(D)c1∑Cπ^c(1−π^c) 其中 π ^ c N c N ∑ i 1 N I ( y i c ) N \hat{\pi}_c \frac{N_c}{N} \frac{\sum_{i1}^{N} \mathbb{I}(y_i c)}{N} π^cNNcN∑i1NI(yic)是第 c c c类样本在数据集中的比例。
2为什么不使用错误率 错误率定义为 Err ( D ) 1 − max c { π ^ c } \text{Err}(\mathcal{D}) 1 - \max_{c} \{\hat{\pi}_c\} Err(D)1−cmax{π^c} 错误率曲线将数据集分为两个区间在每个区间内是直线。如果划分后的子节点和父节点在同一条直线上则划分后错误率不会下降从而无法进一步分裂节点。
3Gini指数的优势 与错误率曲线不同Gini指数的曲线也分为两个区间但在每个区间内是向上凸起的。这样划分后子节点的熵的平均值会比分裂前的熵小从而可以继续分裂节点直到达到分裂停止标准。
4图示说明 下图展示了两类分类的不纯度度量包括Gini指数、熵和错误率随类别概率变化的曲线 #mermaid-svg-AUSjEHChv3EcfErZ {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-AUSjEHChv3EcfErZ .error-icon{fill:#552222;}#mermaid-svg-AUSjEHChv3EcfErZ .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-AUSjEHChv3EcfErZ .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-AUSjEHChv3EcfErZ .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-AUSjEHChv3EcfErZ .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-AUSjEHChv3EcfErZ .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-AUSjEHChv3EcfErZ .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-AUSjEHChv3EcfErZ .marker{fill:#333333;stroke:#333333;}#mermaid-svg-AUSjEHChv3EcfErZ .marker.cross{stroke:#333333;}#mermaid-svg-AUSjEHChv3EcfErZ svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-AUSjEHChv3EcfErZ .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-AUSjEHChv3EcfErZ .cluster-label text{fill:#333;}#mermaid-svg-AUSjEHChv3EcfErZ .cluster-label span{color:#333;}#mermaid-svg-AUSjEHChv3EcfErZ .label text,#mermaid-svg-AUSjEHChv3EcfErZ span{fill:#333;color:#333;}#mermaid-svg-AUSjEHChv3EcfErZ .node rect,#mermaid-svg-AUSjEHChv3EcfErZ .node circle,#mermaid-svg-AUSjEHChv3EcfErZ .node ellipse,#mermaid-svg-AUSjEHChv3EcfErZ .node polygon,#mermaid-svg-AUSjEHChv3EcfErZ .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-AUSjEHChv3EcfErZ .node .label{text-align:center;}#mermaid-svg-AUSjEHChv3EcfErZ .node.clickable{cursor:pointer;}#mermaid-svg-AUSjEHChv3EcfErZ .arrowheadPath{fill:#333333;}#mermaid-svg-AUSjEHChv3EcfErZ .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-AUSjEHChv3EcfErZ .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-AUSjEHChv3EcfErZ .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-AUSjEHChv3EcfErZ .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-AUSjEHChv3EcfErZ .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-AUSjEHChv3EcfErZ .cluster text{fill:#333;}#mermaid-svg-AUSjEHChv3EcfErZ .cluster span{color:#333;}#mermaid-svg-AUSjEHChv3EcfErZ div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-AUSjEHChv3EcfErZ :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 划分 划分 父结点 左子结点 右子结点 Gini Index Entropy Error Rate 2错误率 vs. Gini指数
2.1示例说明 假设父节点包含10个样本其中正样本有7个负样本有3个。我们可以计算错误率和Gini指数如下 样本中正类( c 1 c1 c1)和负类( c 0 c0 c0)的比例分别为 π ^ 1 0.3 \hat{\pi}_1 0.3 π^10.3和 π ^ 0 0.7 \hat{\pi}_0 0.7 π^00.7。 错误率Error Rate计算为 Err ( D ) 1 − max { π ^ c } 1 − 0.7 0.3 \text{Err}(\mathcal{D}) 1 - \max\{\hat{\pi}_c\} 1 - 0.7 0.3 Err(D)1−max{π^c}1−0.70.3 Gini指数Gini Index计算为 H ( D ) ∑ c 1 C π ^ c ( 1 − π ^ c ) 0.7 × 0.3 × 2 0.41 H(\mathcal{D}) \sum_{c1}^{C} \hat{\pi}_c (1 - \hat{\pi}_c) 0.7 \times 0.3 \times 2 0.41 H(D)c1∑Cπ^c(1−π^c)0.7×0.3×20.41
2.2决策树分裂效果 如果我们根据特征 H H H的值将数据集分裂为两个子集我们可以计算每个子集的不纯度度量 子集1 H no H \text{no} Hno 错误率 E ( D no ) 2 5 E(\mathcal{D}_{\text{no}}) \frac{2}{5} E(Dno)52样本数5类别分布 [ 3 / 5 , 2 / 5 ] [3/5, 2/5] [3/5,2/5]Gini指数 H ( D no ) 0.48 H(\mathcal{D}_{\text{no}}) 0.48 H(Dno)0.48 子集2 H yes H \text{yes} Hyes 错误率 E ( D yes ) 1 5 E(\mathcal{D}_{\text{yes}}) \frac{1}{5} E(Dyes)51样本数5类别分布 [ 4 / 5 , 1 / 5 ] [4/5, 1/5] [4/5,1/5]Gini指数 H ( D yes ) 0.32 H(\mathcal{D}_{\text{yes}}) 0.32 H(Dyes)0.32 通过比较错误率和Gini指数我们可以看到Gini指数在决策树分裂中提供了一个更加平滑的度量有助于更好地评估分裂效果。在本例中尽管子集2的错误率较低但子集1的Gini指数较低表明子集1的不纯度较低。因此Gini指数可以帮助我们更全面地评估决策树的分裂效果。
2.3左子结点分析 左子结点包含5个样本其中正样本3个负样本2个。计算如下
正负样本比例分别为 π ^ 0 3 / 5 \hat{\pi}_0 3/5 π^03/5 和 π ^ 1 2 / 5 \hat{\pi}_1 2/5 π^12/5。错误率计算为 Err L ( D ) 1 − max { π ^ c } 1 − 3 / 5 2 / 5 \text{Err}_L(\mathcal{D}) 1 - \max\{\hat{\pi}_c\} 1 - 3/5 2/5 ErrL(D)1−max{π^c}1−3/52/5。Gini指数计算为 H L ( D ) ∑ c 1 C π ^ c ( 1 − π ^ c ) 3 / 5 × 2 / 5 × 2 12 / 25 H_L(\mathcal{D}) \sum_{c1}^{C} \hat{\pi}_c (1 - \hat{\pi}_c) 3/5 \times 2/5 \times 2 12/25 HL(D)∑c1Cπ^c(1−π^c)3/5×2/5×212/25。
左子结点分裂效果
初始错误率 E ( D ) 3 / 10 E(\mathcal{D}) 3/10 E(D)3/10样本数10分布 [ 0.7 , 0.3 ] [0.7, 0.3] [0.7,0.3]。分裂后 子集1 H no H \text{no} Hno错误率 E ( D no ) 2 / 5 E(\mathcal{D}_{\text{no}}) 2/5 E(Dno)2/5样本数5分布 [ 3 / 5 , 2 / 5 ] [3/5, 2/5] [3/5,2/5]Gini指数 H ( D no ) 0.48 H(\mathcal{D}_{\text{no}}) 0.48 H(Dno)0.48。子集2 H yes H \text{yes} Hyes错误率 E ( D yes ) 1 / 5 E(\mathcal{D}_{\text{yes}}) 1/5 E(Dyes)1/5样本数5分布 [ 4 / 5 , 1 / 5 ] [4/5, 1/5] [4/5,1/5]Gini指数 H ( D yes ) 0.32 H(\mathcal{D}_{\text{yes}}) 0.32 H(Dyes)0.32。
2.4右子结点分析 右子结点包含5个样本其中正样本4个负样本1个。计算如下
正负样本比例分别为 π ^ 0 4 / 5 \hat{\pi}_0 4/5 π^04/5 和 π ^ 1 1 / 5 \hat{\pi}_1 1/5 π^11/5。错误率计算为 Err R ( D ) 1 − max { π ^ c } 1 − 4 / 5 1 / 5 \text{Err}_R(\mathcal{D}) 1 - \max\{\hat{\pi}_c\} 1 - 4/5 1/5 ErrR(D)1−max{π^c}1−4/51/5。Gini指数计算为 H R ( D ) ∑ c 1 C π ^ c ( 1 − π ^ c ) 4 / 5 × 1 / 5 × 2 8 / 25 H_R(\mathcal{D}) \sum_{c1}^{C} \hat{\pi}_c (1 - \hat{\pi}_c) 4/5 \times 1/5 \times 2 8/25 HR(D)∑c1Cπ^c(1−π^c)4/5×1/5×28/25。
右子结点分裂效果
初始Gini指数 H ( D ) 0.41 H(\mathcal{D}) 0.41 H(D)0.41样本数10分布 [ 0.7 , 0.3 ] [0.7, 0.3] [0.7,0.3]。分裂后 子集1 H no H \text{no} HnoGini指数 H ( D no ) 0.48 H(\mathcal{D}_{\text{no}}) 0.48 H(Dno)0.48样本数5分布 [ 3 / 5 , 2 / 5 ] [3/5, 2/5] [3/5,2/5]。子集2 H yes H \text{yes} HyesGini指数 H ( D yes ) 0.32 H(\mathcal{D}_{\text{yes}}) 0.32 H(Dyes)0.32样本数5分布 [ 4 / 5 , 1 / 5 ] [4/5, 1/5] [4/5,1/5]。 通过比较左子结点和右子结点的分裂效果我们可以看到Gini指数在评估分裂质量时提供了一个更细致的视角。尽管错误率在右子结点上更低但Gini指数在两个子结点上都显示出较低的不纯度表明Gini指数是一个有效的分裂评估指标。
3分裂后的平均效果
3.1分裂后的平均错误率和熵 在进行数据集分裂后我们可以计算平均错误率和平均熵来评估分裂的效果 平均错误率 Err ( D ∣ X ) 5 10 Err L ( D ) 5 10 Err R ( D ) 0.3 \text{Err}(\mathcal{D}|X) \frac{5}{10} \text{Err}_L(\mathcal{D}) \frac{5}{10} \text{Err}_R(\mathcal{D}) 0.3 Err(D∣X)105ErrL(D)105ErrR(D)0.3 平均熵 H ( D ∣ X ) 5 10 H L ( D ) 5 10 H R ( D ) 0.4 H(\mathcal{D}|X) \frac{5}{10} H_L(\mathcal{D}) \frac{5}{10} H_R(\mathcal{D}) 0.4 H(D∣X)105HL(D)105HR(D)0.4
3.2分裂前的情况 错误率 Err ( D ) 1 − max c { π ^ c } 1 − 0.7 0.3 \text{Err}(\mathcal{D}) 1 - \max_{c}\{\hat{\pi}_c\} 1 - 0.7 0.3 Err(D)1−cmax{π^c}1−0.70.3 熵 H ( D ) ∑ c 1 C π ^ c ( 1 − π ^ c ) 0.7 × 0.3 × 2 0.41 H(\mathcal{D}) \sum_{c1}^{C} \hat{\pi}_c (1 - \hat{\pi}_c) 0.7 \times 0.3 \times 2 0.41 H(D)c1∑Cπ^c(1−π^c)0.7×0.3×20.41 从上面的计算可以看出虽然分裂前后的错误率没有变化但熵有所减少。这意味着尽管分类错误的比例没有改变数据集的不纯度或不确定性有所降低这是决策树分裂的一个积极效果。
三、分类回归树Classification And Regression Tree CART
1、基本概念 ID3和C4.5根据特征取值生成的树为多叉树。 CARTClassification And Regression Tree采用二分递归划分的方法将当前样本集合划分为两个子集分别为左右两个子节点使得生成的每个非叶子节点都有两个分支从而形成二叉树。 离散型特征左右分支的组合较多亦可将离散型特征编码成连续型特征。 连续型特征设特征 X X X在 D \mathcal{D} D中出现了 M M M个不同的取值将这些值从小到大排序记作 a 1 , a 2 , . . . , a M a_1, a_2, ..., a_M a1,a2,...,aM则共有 M − 1 M - 1 M−1个候选划分点依次为 a 1 a 2 2 , a 2 a 3 2 , . . . , a M − 1 a M 2 \frac{a_1 a_2}{2}, \frac{a_2 a_3}{2}, ..., \frac{a_{M-1} a_M}{2} 2a1a2,2a2a3,...,2aM−1aM 对于大数据集训练数据中特征的取值数目 M M M可能会很多要考虑所有 M − 1 M - 1 M−1个候选点开销太大可考虑将特征分成多个区间采用直方图方式快速寻找近似的最佳划分点XGBoost、LightGBM。
2、例离散型特征 根据日志密度 L L L候选分裂方式有3种左右分支可交换为6种8种减去空集和全集
日志密度 L L L好友密度 F F F是否使用真实头像 H H H账号是否真实 R R Rssnonollyesyeslmyesyesmmyesyeslmyesyesmlnoyesmsnonolmnoyesmsnoyesssyesno 1. 左侧分支 L s L s Ls右侧分支 R { l , m } R \{l, m\} R{l,m} N L 3 N_L 3 NL3 N R 7 N_R 7 NR7 H ( D L ) 4 9 H(\mathcal{D}_L) \frac{4}{9} H(DL)94 H ( D R ) 12 49 H(\mathcal{D}_R) \frac{12}{49} H(DR)4912 H ( D ) 3 10 × 4 9 7 10 × 12 49 64 210 H(\mathcal{D}) \frac{3}{10} \times \frac{4}{9} \frac{7}{10} \times \frac{12}{49} \frac{64}{210} H(D)103×94107×491221064 2. 左侧分支 L l L l Ll右侧分支 R { s , m } R \{s, m\} R{s,m} N L 3 N_L 3 NL3 N R 7 N_R 7 NR7 H ( D L ) 0 H(\mathcal{D}_L) 0 H(DL)0 H ( D R ) 24 49 H(\mathcal{D}_R) \frac{24}{49} H(DR)4924 H ( D ) 3 10 × 0 7 10 × 24 35 12 210 H(\mathcal{D}) \frac{3}{10} \times 0 \frac{7}{10} \times \frac{24}{35} \frac{12}{210} H(D)103×0107×352421012 3. 左侧分支 L m L m Lm右侧分支 R { s , l } R \{s, l\} R{s,l} N L 4 N_L 4 NL4 N R 6 N_R 6 NR6 H ( D L ) 3 8 H(\mathcal{D}_L) \frac{3}{8} H(DL)83 H ( D R ) 4 9 H(\mathcal{D}_R) \frac{4}{9} H(DR)94 H ( D ) 4 10 × 3 8 6 10 × 4 9 5 12 H(\mathcal{D}) \frac{4}{10} \times \frac{3}{8} \frac{6}{10} \times \frac{4}{9} \frac{5}{12} H(D)104×83106×94125
3、例连续型特征
3.1根据特征width的取值对所有样本进行排序得到可能的阈值为6.25, 6.55, 6.75, 6.95。
widthheightClass7.09.5Orange6.96.0Orange6.66.6Orange6.56.6Lemon6.06.6Lemon6.99.6Lemon 对每个可能的阈值计算划分后的Gini指数 H width 6.25 ( D ) H width 6.95 ( D ) 1 6 × ( 0 ) 5 6 × ( 2 5 × 3 5 × 2 ) 2 5 H_{\text{width}6.25}(\mathcal{D}) H_{\text{width}6.95}(\mathcal{D}) \frac{1}{6} \times (0) \frac{5}{6} \times \left(\frac{2}{5} \times \frac{3}{5} \times 2\right) \frac{2}{5} Hwidth6.25(D)Hwidth6.95(D)61×(0)65×(52×53×2)52 H width 6.55 ( D ) 2 6 × ( 0 ) 4 6 × ( 1 4 × 3 4 × 2 ) 1 4 H_{\text{width}6.55}(\mathcal{D}) \frac{2}{6} \times (0) \frac{4}{6} \times \left(\frac{1}{4} \times \frac{3}{4} \times 2\right) \frac{1}{4} Hwidth6.55(D)62×(0)64×(41×43×2)41 H width 6.75 ( D ) 3 6 × ( 1 3 × 2 3 × 2 ) 3 6 × ( 2 3 × 1 3 × 2 ) 4 9 H_{\text{width}6.75}(\mathcal{D}) \frac{3}{6} \times \left(\frac{1}{3} \times \frac{2}{3} \times 2\right) \frac{3}{6} \times \left(\frac{2}{3} \times \frac{1}{3} \times 2\right) \frac{4}{9} Hwidth6.75(D)63×(31×32×2)63×(32×31×2)94 通过计算不同阈值下的Gini指数我们可以选择Gini指数最小的阈值作为最佳划分点从而实现样本的最优分类。
3.2根据特征height的取值对所有样本进行排序得到可能的阈值为6.3, 8.05, 9.55。
widthheightClass6.96.0Orange6.06.6Lemon6.56.6Lemon6.66.6Orange7.09.5Orange6.99.6Lemon 对每个可能的阈值计算划分后的Gini指数 H height 9.55 ( D ) H height 6.3 ( D ) 1 6 × ( 0 ) 5 6 × ( 2 5 × 3 5 × 2 ) 2 5 H_{\text{height}9.55}(\mathcal{D}) H_{\text{height}6.3}(\mathcal{D}) \frac{1}{6} \times (0) \frac{5}{6} \times \left(\frac{2}{5} \times \frac{3}{5} \times 2\right) \frac{2}{5} Hheight9.55(D)Hheight6.3(D)61×(0)65×(52×53×2)52 H height 8.05 ( D ) 4 6 × ( 2 4 × 2 4 × 2 ) 2 6 × ( 1 2 × 1 2 × 2 ) 1 2 H_{\text{height}8.05}(\mathcal{D}) \frac{4}{6} \times \left(\frac{2}{4} \times \frac{2}{4} \times 2\right) \frac{2}{6} \times \left(\frac{1}{2} \times \frac{1}{2} \times 2\right) \frac{1}{2} Hheight8.05(D)64×(42×42×2)62×(21×21×2)21 最佳决策规则为width 6.55划分后的Gini指数为 1 4 \frac{1}{4} 41。 根据这个规则我们可以得到以下分类结果
左侧分支width ≤ 6.552个Lemons右侧分支width 6.551个Lemon, 3个Oranges
4、划分停止条件 建树过程是一个自顶向下的递归过程。在递归过程中我们需要设定一些停止条件来避免过拟合和提高模型的泛化能力。 递归的停止条件包括
划分带来的损失的减小太小当进一步划分不能显著提高模型的性能时停止划分。树的深度超过了最大深度限制树的最大深度防止树过于复杂。叶子结点数目超过了最大数目限制叶子结点的最大数量控制模型复杂度。左/右分支的样本分布足够纯净当分支中的样本已经足够纯净即大部分样本属于同一类别时停止划分。左/右分支中样本数目足够少当分支中的样本数量少于某个阈值时停止划分以避免模型过拟合。 通过这些停止条件我们可以有效地控制决策树的生长避免过拟合提高模型的泛化能力。
5、剪枝 分类回归树算法容易过拟合通过剪枝去除部分分支降低模型复杂度。 剪枝给定一个完全树自底向上进行剪枝直到根节点。 剪枝准则 C α ( T ) ∑ t 1 ∣ T ∣ ∣ D t ∣ H ( D t ) α ∣ T ∣ C ( T ) α ∣ T ∣ C_{\alpha}(T) \sum_{t1}^{|T|} |\mathcal{D}_t| H(\mathcal{D}_t) \alpha |T| C(T) \alpha |T| Cα(T)t1∑∣T∣∣Dt∣H(Dt)α∣T∣C(T)α∣T∣
其中 ∣ D t ∣ |\mathcal{D}_t| ∣Dt∣ 是叶子结点 t t t的样本数目 H ( D t ) H(\mathcal{D}_t) H(Dt) 是叶子结点 t t t的不纯净度 α \alpha α 是正则因子 ∣ T ∣ |T| ∣T∣ 是叶子结点数目。 决策树划分得越细致叶子结点的样本越纯净但此时叶子结点越多。所以最佳模型是这两方面的折中。 当 α \alpha α从0开始增大树的一些分支被剪掉得到不同 α \alpha α对应的树。
1剪枝过程 剪枝前费用 T T T表示绿色虚线框中的子树 C A ( T ) C ( T ) α ∣ T ∣ C_A(T) C(T) \alpha |T| CA(T)C(T)α∣T∣ 剪枝后的费用子树 T T T变成了一个叶子结点 t t t C B ( t ) C ( t ) α C_B(t) C(t) \alpha CB(t)C(t)α 当 C A ( T ) C B ( t ) C_A(T) C_B(t) CA(T)CB(t)时得到 α eff C ( t ) − C ( T ) ∣ T ∣ − 1 \alpha_{\text{eff}} \frac{C(t) - C(T)}{|T| - 1} αeff∣T∣−1C(t)−C(T) 某个结点是否要被剪枝的 α \alpha α的临界点。 当 α α eff \alpha \alpha_{\text{eff}} ααeff时剪枝后的费用 C B ( t ) C_B(t) CB(t)更小。进行剪枝会得到更优的决策树。 α \alpha α不同时得到的剪枝策略不同。 最佳的 α \alpha α通过验证集上的性能得到。 蓝色虚线框内未剪枝部分费用不变故而在此忽略 2剪枝策略 基于当前决策树结构计算树中每个中间结点的 α eff \alpha_{\text{eff}} αeff。 选择 α eff \alpha_{\text{eff}} αeff最小的中间结点对其进行剪枝得到新的决策树。 迭代地进行剪枝直到达到停止条件如只有2层。
3验证集 对一系列子树计算其在验证集上的性能。 验证集上性能最好的剪枝树胜出。 子树 T 0 T_0 T0在验证集上的性能子树 T 1 T_1 T1在验证集上的性能输出在验证数据集中的预测误差子树 T 2 T_2 T2在验证集上的性能子树 T n T_n Tn在验证集上的性能。
4Scikit-Learn中对剪枝的支持 为了了解 α eff \alpha_{\text{eff}} αeff的哪些值可能是合适的Scikit-learn中的决策树模型提供函数cost_complexity_pruning_path()返回在修剪过程中每一步 α \alpha α的有效性ccp_alpha α eff \alpha_{\text{eff}} αeff和相应的总叶子结点的不纯净度。 再根据验证集上的性能寻找最佳 α eff \alpha_{\text{eff}} αeff。 以下是在Scikit-learn中实现剪枝的代码示例
path clf.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas, impurities path.ccp_alphas, path.impurities
clfs []for ccp_alpha in ccp_alphas:clf DecisionTreeClassifier(random_state0, ccp_alphaccp_alpha)clf.fit(X_train, y_train)clfs.append(clf)train_scores [clf.score(X_train, y_train) for clf in clfs]
test_scores [clf.score(X_test, y_test) for clf in clfs]图中展示了训练集和测试集上的准确率与α值的关系。可以看到随着α值的增加模型的复杂度降低测试集上的准确率先是保持稳定然后逐渐下降。最佳 α eff \alpha_{\text{eff}} αeff即为测试集准确率最高的点对应的α值。
四、决策树的优缺点
1、决策树模型的优点 决策树是一种非常直观且易于理解的模型它具有以下几个显著优点
容易解释决策树的结构清晰易于解释和展示使得非专业人士也能理解和使用。对特征预处理要求少 理论上能处理离散值和连续值混合的输入实际需根据具体工具包的要求对特征的单调变换不敏感只与数据的排序有关能自动进行特征选择 可扩展到大数据规模决策树可以处理大规模数据集且在大数据环境下表现良好。
2、决策树模型的缺点 尽管决策树有许多优点但它也有一些缺点
正确率不高建树过程过于贪心可能导致过拟合。 可作为Boosting的弱学习器深度不太深 模型不稳定方差大输入数据小的变化会带来树结构的变化。 Bagging 随机森林 当特征数目相对样本数目太多时容易过拟合在特征数量远大于样本数量的情况下决策树容易过拟合训练数据。 这些缺点可以通过集成学习方法如随机森林、Boosting等来缓解提高模型的泛化能力和稳定性。
五、DecisionTreeClassifier类 DecisionTreeClassifier是Scikit-learn库中用于分类任务的决策树模型。其构造函数如下
class sklearn.tree.DecisionTreeClassifier(*, criteriongini, splitterbest, max_depthNone, min_samples_split2, min_samples_leaf1, min_weight_fraction_leaf0.0, max_featuresNone, random_stateNone, max_leaf_nodesNone, min_impurity_decrease0.0, class_weightNone, ccp_alpha0.0)决策树算法特有的参数
criterion、splitter、max_featuresmax_depth、max_leaf_nodesmin_samples_split、min_samples_leafmin_weight_fraction_leaf、min_impurity_decreasemin_impurity_split、ccp_alpha
1、DecisionTreeClassifier的参数
参数说明备注criterion权衡划分质量的指标gini默认Gini指数entropy熵splitter划分方式best默认在特征的所有划分点中找出最优值random在一些随机划分点中找最优分裂点best适合样本量不大的时候如果样本数据量非常大推荐random。max_features寻找最佳分裂点时考虑的特征数目None默认考虑所有的特征log2最多考虑 log 2 D \log_2 D log2D个特征sqrt/auto最多考虑 D \sqrt{D} D 个特征。整数考虑的特征的绝对数目。浮点数考虑特征数目的百分比即百分比 × D \times D ×D取整后的特征数。其中 D D D为样本总特征数。如果样本特征数不多如小于50用默认的None即可。如果特征数非常多可以控制分裂时考虑的最大特征数以控制决策树的生成时间。max_depth树的最大深度。None默认在建树时不限制树的深度直到每个叶子结点都是纯净的或叶子结点的样本数目小于min_samples_split。数据少或者特征少的时候可以默认值。如果模型样本量多特征也多的情况下推荐限制最大深度具体的取值取决于数据的分布。常用的可以取值10-100之间。max_leaf_nodes最大叶子节点数目。以最好优先best-first的方式生成树时用该参数限制叶子结点数目。None默认不限制叶子结点数目。如果不为None则忽略max_depth。min_samples_split对中间结点进行分裂的最小样本数。整数样本绝对数目浮点数样本百分比默认值为2如果样本量数量级非常大则推荐增大该参数。如10万样本min_samples_split10。min_samples_leaf叶子节点包含的最小样本数。整数样本绝对数目浮点数样本百分比默认值为1如果某叶子节点数目小于该参数则会和兄弟节点一起被剪枝。min_samples_split约为min_samples_leaf的2倍。min_weight_fraction_leaf叶子结点所有样本权重和的最小值。默认值为0不考虑权重约束。当没有设置sample_weight时每个样本的权重相等。如果某叶子结点样本权重和小于该参数则会和兄弟结点一起被剪枝。min_impurity_decrease结点划分最小不纯度下降量。如果结点划分带来的不纯度下降小于这个阈值则该结点不再划分为叶子结点。不纯度下降可带样本权重 N m N ( impurity − N left N m H ( D L ) − N right N m H ( D R ) ) \frac{N_m}{N}\left(\text{impurity} - \frac{N_{\text{left}}}{N_m} H(\mathcal{D}_L) - \frac{N_{\text{right}}}{N_m} H(\mathcal{D}_R)\right) NNm(impurity−NmNleftH(DL)−NmNrightH(DR))class_weight每个类别的权重{class_label: weight}。如果不给定所有类别的权重均1。balanced模式自动调整权重。n_samples / (n_classes * np.bincount(y))还可以设置样本权重fit函数random_state随机种子ccp_alpha后剪枝中结点有效性的阈值。
2、DecisionTreeClassifier的属性 DecisionTreeClassifier提供了一些有用的属性可以帮助我们了解模型的结构和特征的重要性。以下是这些属性的详细说明
属性说明备注classes_类别标签模型训练后所有可能的类别标签。n_classes_类别数目模型训练后类别的总数。feature_importances_特征重要性每个特征对模型预测的贡献程度可根据特征重要性做特征选择。max_features_max_features的值实际用于模型训练的特征数目的最大值。n_features_训练模型fit的特征数目模型训练时使用的特征总数。n_outputs_训练模型fit的输出的数目模型训练时目标变量的数目。tree_树训练后的决策树模型本身可以用于可视化和分析。 这些属性为我们提供了模型的详细信息有助于我们更好地理解和解释模型的行为。
3、DecisionTreeClassifier的方法 DecisionTreeClassifier提供了一系列的实用方法用于模型训练、预测和评估。以下是这些方法的详细说明
方法说明apply(X[, check_input])返回每个样本对应的叶子结点索引。fit(X, y[, sample_weight])模型训练。参数X, y为训练数据也可以通过sample_weight设置每个样本的权重。predict(X)返回X对应的预测值类别标签。predict_log_proba(X)返回X对应的预测值每个类别对应的概率的log值。predict_proba(X)返回X对应的预测值每个类别对应的概率。score(X, y[, sample_weight])评估模型预测性能返回模型预测的正确率。decision_path(X[, check_input])返回每个样本对应的树的决策路径。 这些方法使得DecisionTreeClassifier不仅能够进行分类任务还能够提供模型内部的详细信息如特征重要性、决策路径等有助于模型的解释和优化。
