网站制作成本,山东免费网站建设,吉林省吉林市邮政编码,有什么做设计接任务的网站决策树的定义#xff1a;
决策树利用树形数据结构来展示决策规则和分类结果#xff0c;它是一种归纳学习算法#xff0c;可以将复杂数据转化为可以预测未知数据的模型。每一条从根节点到叶节点的路径都代表一条决策规则。
决策树内的一些重要名词#xff1a;
信息熵
决策树利用树形数据结构来展示决策规则和分类结果它是一种归纳学习算法可以将复杂数据转化为可以预测未知数据的模型。每一条从根节点到叶节点的路径都代表一条决策规则。
决策树内的一些重要名词
信息熵
用来衡量一个随机变量出现的期望值。如果信息的不确定性越大熵的值也就越大出现的各种情况也就越多。 H(X) -∑p(x)log_2p(x)
范围 0 ~ log分类个数 以2为底
条件熵
条件熵是在信息论中用来描述在一个随机变量X的值给定的前提下另一个随机变量Y的不确定性。它反映了在已知X的条件下Y的信息量或者说是剩余的不可预测性。
具体来说条件熵H(Y|X)定义为在已知随机变量X的条件下随机变量Y的条件概率分布的熵对X的期望值。这可以理解为在知道了X的具体值之后Y的不确定性或者信息量的平均值。
可以理解为加上某个条件后的信息熵
信息增益
信息增益是在知道某个条件后事件不确定性下降的程度。
信息增益是信息论中的一个重要概念它量化了在给定一个条件下随机变量不确定性的减少量。具体来说信息增益被定义为信息熵和条件熵之差这里的信息熵指的是随机变量的不确定性而条件熵则表示在已知一个随机变量的条件下另一个随机变量的不确定性。数学上信息增益可以表示为 H(X) - H(Y|X) )其中 \( H(X) 是随机变量X的信息熵 H(Y|X) H(Y∣X) 是在给定X的条件下随机变量Y的条件熵。
值得一提的是信息增益越大意味着这个条件对于分类或决策过程越重要。例如在决策树算法中选择信息增益最大的特征作为节点分裂的依据因为它能够最大限度地降低系统的不确定性从而提高分类的准确性。
信息增益率
信息增益率是一种特征选择的度量方法它通过比较信息增益和条件的信息熵来评估特征的重要性。
信息增益率是在信息增益的基础上发展起来的它考虑了信息增益中可能存在的偏差即某些属性可能因为其取值较多而具有较高的信息增益但并不意味着该属性对分类有实质性的帮助。信息增益率通过引入“条件的信息熵”这一概念来对信息增益进行校正从而得到一个更为准确的特征重要性评估标准。
在决策树算法中尤其是在C4.5算法中信息增益率被用来衡量特征对于分类的贡献程度。与ID3算法中使用的信息增益不同信息增益率提供了一个更稳定的特征选择标准特别是在数据集含有多个属性或者属性之间存在相关性时能够避免选择那些看似有信息但实际上并不具有预测能力的属性。
决策树的构建过程
特征选择从训练数据的特征中选择一个特征作为当前节点的分裂标准特征选择的标准不同产生了不同的特征决策树算法。
决策树生成根据所选特征评估标准从上至下递归地生成子节点直到数据集不可分则停止决策树停止生长。
剪枝决策树容易过拟合需要剪枝来缩小树的结构和规模包括预剪枝和后剪枝。 决策树的生成是一个递归的过程在决策树的基本算法中有三种情况会导致递归返回 当前节点包含的样本全属于同一类别无需划分 当前属性集为空或是所有样本在所有属性上取值相同无法划分 当前节点包含的样本集为空不能划分。
决策树的三种算法
一.ID3算法现在基本不用了
ID3算法是由Ross Quinlan提出的决策树的一种算法实现以信息论为基础以信息熵和信息增益为衡量标准从而实现对数据的归纳分类。
ID3算法是建立在奥卡姆剃刀的基础上越是小型的决策树越优于大的决策树be simple简单理论。
ID3算法的核心思想以信息增益度量属性选择选择分裂后信息增益最大的属性进行分裂。
ID3算法流程
1、初始化属性集合和数据集合。
2、计算数据集合信息熵S和所有属性的条件熵选择信息增益最大的属性作为当前决策节点。
3、更新数据集合和属性集合删除掉上一步中使用的属性并按照属性值来划分不同分支的数据集合。
4、依次对每种取值情况下的子集重复第二步。
5、若子集只包含单一属性则为分支为叶子节点根据其属性值标记。
6、完成所有属性集合的划分。
优缺点
ID3算法的优点主要包括决策树易于理解和解释、可以处理多种类型的数据以及计算复杂度相对较低。
易于理解和解释决策树的结构直观可以帮助人们更好地理解分类过程。
数据处理能力ID3算法可以处理离散型和连续型数据也能够应对多分类问题。
计算复杂度低与其他算法相比ID3算法的计算复杂度不高使得它在实际应用中效率较高。
对数据缺失不敏感ID3算法对中间值的缺失不敏感这意味着它可以处理不完整或不相关特征的数据。
ID3算法的缺点则主要体现在它倾向于选择取值较多的特征并且容易发生过拟合。
特征选择偏好信息增益偏向于选择取值较多的特征这可能导致那些实际上并不具有强预测能力的特征被选中。
过拟合问题决策树容易过拟合即模型可能会过于复杂对训练数据过度拟合从而降低了对新数据的泛化能力。为了解决这个问题通常会采用剪枝技术包括前置剪枝和后置剪枝两种策略来避免决策树过于“茂盛”。
C4.5算法ID3算法的改进版
C4.5的改进
上面讨论的决策树的ID3算法属性只能是离散的当然属性值可以是连续的数值型但是需要对这些数据进行预处理变为离散型的才可以运用ID3算法。 C4.5是继承了ID3算法的优点并在此基础上做出改进
改进1用信息增益率代替信息增益来选择属性克服了用信息增益选择属性时偏向选择取值多的属性不足
改进2能够完成对连续值属性的离散化处理。
改进3能处理属性值缺失的情况。
改进4在决策树构造完成之后进行剪枝。预剪枝和后剪枝
**预剪枝是在决策树构建过程中提前停止树的增长。它通过在每个节点处评估划分前后的泛化性能如果划分不能显著提高性能则不进行划分。这种方法可以有效地控制决策树的复杂度减少计算成本但可能会导致欠拟合。
**后剪枝则是在构建完整的决策树之后进行优化。它允许决策树完全增长然后通过删除或合并一些子树来简化模型以提高泛化能力。后剪枝通常能够得到比预剪枝更复杂的模型因此欠拟合的风险较小但计算成本较高。
优缺点
C4.5算法是一种广泛使用的分类决策树算法它通过信息增益率选择属性、对连续属性的离散化处理、对不完整数据的处理、以及在树构造过程中的剪枝操作提高了决策树的精度和鲁棒性。
C4.5算法的优点
易于理解和解释C4.5算法产生的分类规则清晰易懂非专业人士也能理解决策树所表示的规则。
处理连续属性C4.5能够处理连续属性通过离散化过程将连续属性转化为离散值。
处理不完整数据C4.5可以处理含有缺失值的数据这增强了算法的实用性和鲁棒性。
避免过拟合通过剪枝技术C4.5可以有效降低模型复杂度防止过拟合提高泛化能力。
C4.5算法的缺点
计算效率较低在构建树的过程中需要多次扫描和排序数据集导致算法效率不高尤其是在大数据集上更为明显。
对噪声和异常值敏感C4.5对噪声和异常值较为敏感可能会造成决策树不稳定。
偏向于选择取值多的属性尽管使用信息增益率作为选择标准已经减轻了这一问题但在某种程度上仍存在偏向于选择取值较多的属性的倾向。
处理大规模数据时的挑战由于算法需要将整个数据集加载到内存中对于超出内存容量的大型数据集C4.5算法面临挑战。
CART算法最常用的
CART的基本概念
CART既能是分类树又能是回归树。 当CART是分类树时采用GINI值作为节点分裂的依据
当CART是回归树时采用样本的最小方差作为节点分裂的依据。
CART是一棵二叉树即CART只能做二分类。
https://blog.csdn.net/qq_35269774/article/details/88593661 回归树
CART的节点分裂
分裂的目的是为了能够让数据变纯使决策树输出的结果更接近真实值。如果是分类树CART采用GINI值衡量节点纯度如果是回归树采用样本方差衡量节点纯度。节点越不纯节点分类或者预测的效果就越差 小结
ID3: ID3决策树可以有多个分支但是不能处理特征值为连续的情况。在ID3中每次根据“最大信息增益”选取当前最佳的特征来分割数据并按照该特征的所有取值来切分也就是说如果一个特征有4种取值数据将被切分4份一旦按某特征切分后该特征在之后的算法执行中将不再起作用所以有观点认为这种切分方式过于迅速。
C4.5: 针对ID3采用的信息增益度量存在一个缺点它一般会优先选择有较多属性值的特征,因为属性值多的特征会有相对较大的信息增益。C4.5中是用信息增益比率(gain ratio)来作为选择分支的准则。信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的Feature在候选属性中选择基尼系数最小的属性作为最优划分属性。除此之外C4.5还弥补了ID3中不能处理特征属性值连续的问题。
CART: 分类回归树只做二分类。CART分类时使用基尼指数(Gini)来选择最好的数据分割的特征gini描述的是纯度与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。当CART是分类树时采用GINI值作为节点分裂的依据当CART是回归树时采用样本的最小方差作为节点分裂的依据。
