网站后台上传文章,看案例网站,商务网页设计与制作是什么,哪个做网站#x1f33a;历史文章列表#x1f33a; 机器学习——损失函数、代价函数、KL散度机器学习——特征工程、正则化、强化学习机器学习——常见算法汇总机器学习——感知机、MLP、SVM机器学习——KNN机器学习——贝叶斯机器学习——决策树机器学习——随机森林、Bagging、Boostin…历史文章列表 机器学习——损失函数、代价函数、KL散度机器学习——特征工程、正则化、强化学习机器学习——常见算法汇总机器学习——感知机、MLP、SVM机器学习——KNN机器学习——贝叶斯机器学习——决策树机器学习——随机森林、Bagging、Boosting、集成学习机器学习——聚类算法Kmeans、GMM-使用EM优化机器学习——降维 文章目录 决策树Decision Tree概述基本概念任务类型分类任务回归任务分类和回归中的差异 决策树算法的具体实现比较总结ID3Iterative Dichotomiser 3原理主要特点信息熵Entropy信息增益Information Gain算法流程优点缺点 C4.5原理主要特点信息增益比Information Gain Ratio固有信息Intrinsic Information处理连续型变量处理缺失值算法流程优点缺点 CARTClassification and Regression Tree原理主要特点分类任务基尼指数Gini Index回归任务均方误差Mean Squared Error, MSE分类树算法流程回归树算法流程优点缺点 决策树的过拟合和欠拟合解决欠拟合解决过拟合 剪枝Pruning预剪枝Pre-pruning后剪枝Post-pruningC4.5 的错误率估计剪枝操作CART 的成本复杂度剪枝操作 总结 决策树Decision Tree概述
决策树是一种基于树形结构的机器学习算法广泛应用于分类和回归任务中。它通过一系列的规则将数据集划分为不同的子集从而进行分类或预测。决策树算法直观、易于解释并且能够处理复杂的特征交互。
基本概念
节点Node 根节点Root Node树的起始节点表示整个数据集。内部节点Internal Node表示数据集的划分条件包含特征和阈值。叶节点Leaf Node表示分类或回归的最终结果包含类别标签或连续值。 分支Branch——决策规则从一个节点到另一个节点的路径。路径Path——决策过程从根节点到叶节点的序列。深度Depth——决策树的复杂度从根节点到最深叶节点的最长路径长度。
任务类型
决策树既可以用于分类任务也可以用于回归任务。
分类任务
在分类任务中决策树用于将数据划分到不同的离散类别中。目标是通过一系列条件判断将数据划分为不同类别并最终在叶节点上输出类别标签。 常用算法不同的划分特征的标准 ID3使用信息增益来选择划分特征。C4.5使用信息增益比来选择划分特征并支持连续特征处理。CART分类树使用基尼系数(Gini Index) 来选择最优划分特征。 应用场景 电子邮件分类垃圾邮件识别。图像识别识别不同的物体类别。医疗诊断预测病人的健康状况类别。
回归任务
在回归任务中决策树用于预测连续值。目标是通过一系列的分裂操作将数据划分成不同的区间并在每个叶节点上输出一个数值通常是该节点中所有样本的均值。 常用算法 CART回归树使用**最小化均方误差(Mean Squared Error, MSE)**或其他度量标准来选择最优划分特征。 应用场景 房价预测预测某个地区的房屋价格。股票市场预测预测股票的未来价格。气象预测预测某个地点的温度或降雨量。
分类和回归中的差异
分类树Classification Tree
输出的是离散类别标签。每个叶节点表示一个类别。划分标准基于分类纯度如信息增益、基尼系数。
回归树Regression Tree
输出的是连续数值。每个叶节点表示一个数值如节点样本的均值。划分标准基于回归误差如均方误差。
决策树算法的具体实现
比较总结
算法划分标准支持连续特征处理缺失值树结构优点缺点适用场景ID3信息增益否否多叉树实现简单适合小规模数据偏向于选择取值多的特征不能处理连续变量小规模、离散特征数据集C4.5信息增益比是是多叉树支持连续特征能处理缺失值计算复杂度高生成树较大大规模数据有连续特征和缺失值的数据CART基尼系数是否二叉树适用于分类和回归问题剪枝方便对噪声数据敏感容易过拟合分类、回归任务要求生成二叉树时
ID3 适合小规模的、离散特征的数据集但不适合处理连续特征和缺失值。C4.5 是 ID3 的改进版本能处理连续特征、缺失值适合处理复杂的大规模数据集。CART 能同时用于分类和回归任务生成简洁的二叉树结构但对噪声敏感适合需要生成二叉树结构的应用场景。
ID3Iterative Dichotomiser 3
原理
ID3 通过信息增益Information Gain来选择划分特征ID3 选择信息增益最大的特征进行划分。信息增益表示划分数据集后信息熵的减少程度熵越小数据纯度越高。主要用于分类任务。
主要特点
划分准则使用信息增益优先选择信息增益最大的特征进行分裂。适用数据类型ID3 主要适用于离散特征不支持连续特征的处理。剪枝ID3 本身没有提供剪枝机制容易出现过拟合问题。
信息熵Entropy
信息熵用于衡量数据集的纯度或混乱程度。信息熵越高数据越混乱信息熵越低数据越纯。 对于数据集 ( D D D )它的熵定义为 H ( D ) − ∑ i 1 m p i log 2 ( p i ) H(D) - \sum_{i1}^m p_i \log_2(p_i) H(D)−i1∑mpilog2(pi) 其中 m m m 是类别的总数。 p i p_i pi 是数据集中属于第 i i i 类的样本所占的比例。
信息增益Information Gain
表示某一特征 A A A 将数据集 D D D 划分后的纯度提升程度。ID3 选择信息增益最大的特征进行划分。信息增益的公式为 信息增益 H ( D ) − ∑ v 1 V ∣ D v ∣ ∣ D ∣ H ( D v ) \text{信息增益} H(D) - \sum_{v1}^V \frac{|D_v|}{|D|} H(D_v) 信息增益H(D)−v1∑V∣D∣∣Dv∣H(Dv) 其中 H ( D ) H(D) H(D) 是数据集 D D D 的信息熵。 V V V 是特征 A A A 的可能取值数。 D v D_v Dv 是根据特征 A A A 的取值 v v v 分割得到的子集。 ∣ D v ∣ / ∣ D ∣ |D_v| / |D| ∣Dv∣/∣D∣ 表示取值 v v v 的样本在数据集 D D D 中的比例。 H ( D v ) H(D_v) H(Dv) 是子集 D v D_v Dv 的熵。
算法流程
计算当前所有特征对数据集的信息增益。选择信息增益最大的特征作为当前节点的划分标准。根据该特征的不同取值划分数据集并在每个子集上递归地重复步骤 1 和步骤 2。当所有特征都被使用或所有样本都属于同一类别时停止划分。
优点
简单易懂ID3 的核心思想和实现相对简单能够快速生成决策树。高效ID3 计算信息增益后即可快速进行划分。
缺点
倾向于选择取值多的特征ID3 更倾向于选择取值多的特征进行划分可能导致过拟合。只能处理离散特征ID3 不能处理连续特征。对缺失值不敏感ID3 不能有效处理数据中的缺失值。
C4.5
原理
选择信息增益比信息增益与分裂信息的比值最大的特征进行划分用于平衡特征数量和划分质量之间的关系。通过引入“分裂信息”Split Information来惩罚分裂数目较多的特征。支持连续特征处理缺失值加入剪枝。
主要特点
划分准则使用信息增益比避免 ID3 中对多值特征的偏向。适用数据类型支持离散和连续特征。剪枝C4.5 支持错误率估计的后剪枝策略防止过拟合。
信息增益比Information Gain Ratio
信息增益比是信息增益与特征的“固有信息”之比。特征的固有信息衡量的是特征取值的均匀性。信息增益比的公式为 信息增益比 信息增益 固有信息 \text{信息增益比} \frac{\text{信息增益}}{\text{固有信息}} 信息增益比固有信息信息增益
其中信息增益的公式与 ID3 相同。
固有信息Intrinsic Information
固有信息衡量的是特征 A A A 的取值分布它的计算公式为 固有信息 − ∑ v 1 V ∣ D v ∣ ∣ D ∣ log 2 ( ∣ D v ∣ ∣ D ∣ ) \text{固有信息} - \sum_{v1}^V \frac{|D_v|}{|D|} \log_2 \left( \frac{|D_v|}{|D|} \right) 固有信息−v1∑V∣D∣∣Dv∣log2(∣D∣∣Dv∣) 其中 V V V 是特征 A A A 的可能取值数。 D v D_v Dv 是数据集 D D D 中特征 A A A 取值为 v v v 的子集。 ∣ D v ∣ / ∣ D ∣ |D_v| / |D| ∣Dv∣/∣D∣ 表示取值 v v v 的样本在数据集 D D D 中的比例。
在 C4.5 算法中处理连续型变量和缺失值的方法具体如下 处理连续型变量
当特征是连续型变量时C4.5 算法将其转化为一个二值问题例如小于某个阈值和大于等于该阈值以便将连续变量用于决策树的分裂。
步骤
生成候选划分点将连续特征值按升序排列计算每个相邻值的中点作为候选划分点。例如如果连续特征的两个相邻值为 x i x_i xi 和 x i 1 x_{i1} xi1候选划分点为 t x i x i 1 2 t \frac{x_i x_{i1}}{2} t2xixi1。计算信息增益比对于每个候选划分点 ( t )将数据集划分成两个子集 子集 1特征值 ≤ t \leq t ≤t 的样本。子集 2特征值 t t t 的样本。 选择最佳划分点计算所有候选划分点的信息增益比选择信息增益比最大的划分点作为最终分裂点。这样可以有效地将连续变量转化为二值判断。 处理缺失值
在 C4.5 算法中对于特征值缺失的样本算法不会简单地丢弃而是利用概率分布填充缺失值从而有效利用数据。
步骤
计算样本权重在计算信息增益比时含缺失值的样本按照其在整个数据集中的比例被赋予一个权重。这些缺失样本将按比例分布到不同分支。按概率分配样本在分裂节点时缺失特征的样本将依据分支上的样本比例进行分配。例如如果一个特征缺失的样本在某节点有 70% 的概率被归入左子树则会将 70% 的权重分配给左子树30% 的权重分配给右子树。分类时的缺失值处理在决策树生成后进行预测时对于测试样本中缺失的特征C4.5 也使用概率分布填充使其根据现有特征值的分布推断分类。
算法流程
计算每个特征的信息增益比。选择信息增益比最大的特征作为划分特征。如果特征是连续型变量将特征值划分为小于某个阈值和大于等于该阈值的两部分。处理缺失值使用概率分布填充。递归地构建子树直到满足停止条件。
优点
支持连续特征C4.5 通过引入阈值分割能够处理连续型变量。减少过拟合倾向使用信息增益比来进行特征选择避免了对取值多的特征的偏好。处理缺失值能够处理数据集中缺失值的问题。 算法流程中的 3. 如果特征是连续型变量将特征值划分为小于某个阈值和大于等于该阈值的两部分。 4. 处理缺失值使用概率分布填充。 缺点
计算复杂度较高相比 ID3C4.5 由于需要计算信息增益比、处理连续特征和缺失值计算复杂度较高。容易产生较大的树C4.5 生成的树结构有时可能过大需要进行剪枝以减少过拟合。
CARTClassification and Regression Tree
原理
CARTClassification and Regression Tree算法可以用于分类和回归任务。CART 构造的是一棵二叉树。
对于分类任务选择基尼指数最小的特征作为划分特征。对于回归任务选择均方误差最小的特征进行分裂。
主要特点
划分准则 分类任务使用基尼指数作为划分准则。回归任务使用均方误差作为划分准则。 适用数据类型支持离散和连续特征。剪枝CART 支持后剪枝策略通过成本复杂度剪枝来防止过拟合。
分类任务基尼指数Gini Index
基尼指数用于衡量数据集的纯度。基尼系数越小数据集的纯度越高。选择基尼指数最小的特征作为划分特征。
对于数据集 D D D其基尼指数定义为 基尼指数 1 − ∑ i 1 m p i 2 \text{基尼指数} 1 - \sum_{i1}^m p_i^2 基尼指数1−i1∑mpi2 其中 m m m 是类别的总数。 p i p_i pi 是数据集中属于第 $ i$ 类的样本所占的比例。
当一个特征 A A A 有多个可能的取值时特征 A A A 对数据集 D D D 的基尼指数可以表示为 Gini ( D , A ) ∑ v 1 V ∣ D v ∣ ∣ D ∣ Gini ( D v ) \text{Gini}(D, A) \sum_{v1}^V \frac{|D_v|}{|D|} \text{Gini}(D_v) Gini(D,A)v1∑V∣D∣∣Dv∣Gini(Dv)
其中 V V V 是特征 A A A 的取值个数。 D v D_v Dv 是根据特征 A A A 的取值 v v v 划分得到的子集。 Gini ( D v ) \text{Gini}(D_v) Gini(Dv) 是子集 D v D_v Dv 的基尼指数。
回归任务均方误差Mean Squared Error, MSE
对于回归任务CART 算法选择均方误差MSE最小的特征进行分裂。均方误差衡量的是预测值和实际值之间的平均平方差。对于数据集 D D D 均方误差定义为 MSE 1 ∣ D ∣ ∑ i 1 ∣ D ∣ ( y i − y ^ ) 2 \text{MSE} \frac{1}{|D|} \sum_{i1}^{|D|} (y_i - \hat{y})^2 MSE∣D∣1i1∑∣D∣(yi−y^)2 其中 ∣ D ∣ |D| ∣D∣ 是数据集中样本的数量。 y i y_i yi 是第 i i i 个样本的真实值。 y ^ \hat{y} y^ 是数据集 D D D 中所有样本的均值。
分类树算法流程
对每个特征计算不同划分下的基尼系数。选择基尼系数最小的特征作为当前节点的划分特征。递归地构建二叉树。当达到停止条件如节点样本数小于设定阈值时停止递归。
回归树算法流程 遍历每个特征对于每个特征尝试在数据集中的不同数值作为可能的分裂点。 计算分裂后的均方误差对于每个分裂点计算其分裂后左右子集的加权均方误差MSE公式如下 选择最优分裂点选择使得分裂后均方误差最小的分裂点将该特征和分裂点作为当前节点的分裂依据。 递归构建树对分裂后的左右子节点重复步骤 1-3继续寻找最优分裂点构建新的子节点。 停止条件当达到预设的停止条件时例如节点样本数小于设定阈值或MSE降低不明显停止递归分裂。此时该节点成为一个叶节点并赋予其目标值的平均值作为预测值。
优点
可处理分类和回归问题CART 不仅适用于分类任务也可用于回归任务。生成二叉树结构树结构简单每个节点最多有两个分支便于实现和计算。易于剪枝CART 提供了剪枝机制可以有效减少过拟合。
缺点
对噪声数据敏感CART 对于数据中的噪声较为敏感容易生成较复杂的树结构。基尼系数局限性基尼系数在处理某些分类问题时效果不如信息增益或信息增益比。连续特征处理较复杂虽然 CART 可以处理连续特征但需要遍历所有特征值进行划分计算量较大。
决策树的过拟合和欠拟合
解决欠拟合
欠拟合要增加模型复杂度
增加树的深度减少最小样本分裂数让更多节点可以分裂减少最小叶子节点数让树生长得更深 欠拟合通常是因为模型的复杂度不够无法很好地拟合训练数据。应对欠拟合的方法通常是增加模型复杂度。包括 增加树的深度max_depth通过增加决策树的深度可以让模型拟合更多的数据特征从而减少欠拟合。减少最小样本分裂数min_samples_split减少节点分裂所需的最小样本数让更多节点可以分裂使模型更复杂。减少最小叶子节点数min_samples_leaf减少叶子节点的最小样本数让树生长得更深、更复杂。 解决过拟合
过拟合要增加模型复杂度
限制树的深度增加最小样本分裂数限制树的生长增加最小叶子节点数减少树的大小 过拟合是因为模型过于复杂导致对训练数据的拟合过度。应对过拟合的方法通常是减少模型复杂度。包括 限制树的深度max_depth限制树的最大深度可以防止树过于复杂有助于防止过拟合。增加最小样本分裂数min_samples_split通过增加节点分裂所需的最小样本数可以限制树的生长使树不至于过度拟合训练数据。增加最小叶子节点数min_samples_leaf增加叶子节点的最小样本数可以减少树的复杂度防止过拟合。使用剪枝技术如代价复杂度剪枝剪枝是控制过拟合的重要技术之一通过减少树的大小来防止模型过度拟合。 剪枝Pruning
剪枝是决策树中用来防止过拟合的一种技术。它通过移除或合并一些不必要的节点来减少树的复杂度从而提高模型的泛化能力。剪枝可以分为两种方式
预剪枝Pre-pruning
原理在构建决策树的过程中提前停止树的生长以避免树过于复杂。方法 设置最大深度限制决策树的最大深度防止树过深导致过拟合。设置最小样本数要求每个节点至少包含一定数量的样本如果样本数不足则停止划分。设置最小信息增益如果划分后的信息增益小于某个阈值则停止划分。 优点节省计算资源减少构建时间。缺点可能会提前停止构建导致欠拟合。
后剪枝Post-pruning
原理在决策树完全生长后通过评估树的各个子树的表现来剪去不必要的分支从而简化模型。方法 子树替换Subtree Replacement用一个叶节点替换一个子树直到错误率最低。子树提升Subtree Raising将子节点提升到父节点位置删除不必要的中间节点。成本复杂度剪枝Cost Complexity Pruning通过最小化模型复杂度和训练误差的加权和选择最优的子树。 优点能够更精确地控制模型复杂度提高泛化能力。缺点计算量较大剪枝过程复杂。
注C4.5 和 CART 都使用了后剪枝post-pruning方法来防止决策树的过拟合。
C4.5 的错误率估计剪枝操作
C4.5 在剪枝过程中采用错误率估计Error-based Pruning来决定是否剪枝。它通过对每个分支的误分类情况估计如果剪去子树后能减少误分类率就将该子树替换为叶节点。 操作步骤 对每个叶节点和子树进行错误率估计。C4.5 引入了拉普拉斯平滑估计来计算每个节点的错误率。计算子树的错误率如果子树的错误率比该子树替换为叶节点后的错误率高则将该子树剪除将其变为叶节点。重复该过程直到所有需要剪枝的子树都被剪除。 优点这种剪枝策略考虑了训练数据中的随机性可以有效防止过拟合。局限性由于需要计算每个节点的错误率并进行多次迭代计算剪枝过程的计算开销较大。
CART 的成本复杂度剪枝操作
CART 使用的是成本复杂度剪枝Cost Complexity Pruning也称为最小代价复杂度剪枝。基于子树的错误率和模型复杂度的权衡。计算每个子树的错误率和复杂度复杂度用子树中节点的数量来衡量。CART 会逐步剪掉那些增加了模型复杂度但并没有显著降低错误率的子树。 原理成本复杂度剪枝通过平衡模型的复杂度和预测误差来选择最佳子树。它会给每个子树分配一个代价复杂度得分Cost Complexity Score该得分考虑了模型的复杂度和训练误差之和。 代价复杂度Cost Complexity 操作步骤 计算当前决策树每个子树的代价复杂度得分 (R_\alpha(T))。找到降低代价复杂度得分最多的子树并将其剪除合并为一个叶节点。重复上述步骤逐步剪枝直到得到最优子树为止。使用交叉验证等方法选择最优的 (alpha) 值确定最终的剪枝结果。 优点能够在模型复杂度和预测性能之间找到最优平衡点较好地控制了模型的复杂度。局限性代价复杂度参数的选择对模型性能影响较大需要进行交叉验证等方法来优化。
总结
C4.5 主要用于分类任务并使用错误率估计的后剪枝策略进行剪枝以防止过拟合。它通过比较子树和叶节点的错误率来决定是否剪枝。CART 可用于分类和回归任务采用成本复杂度剪枝方法通过平衡模型复杂度和训练误差选择最优子树确保模型具有良好的泛化能力。
因此C4.5 和 CART 在剪枝策略上各有特点分别针对不同的任务和模型复杂度进行了优化。
