机器学习模型——决策树

发布于:2024-04-05 ⋅ 阅读:(23) ⋅ 点赞:(0)

决策树的定义: 

决策树利用树形数据结构来展示决策规则和分类结果,它是一种归纳学习算法,可以将复杂数据转化为可以预测未知数据的模型。每一条从根节点到叶节点的路径都代表一条决策规则。

决策树内的一些重要名词:

信息熵:

用来衡量一个随机变量出现的期望值。如果信息的不确定性越大,熵的值也就越大,出现的各种情况也就越多。

                                     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是回归树时,采用样本的最小方差作为节点分裂的依据。


网站公告

今日签到

点亮在社区的每一天
去签到