• 欢迎光临~

决策树

开发技术 开发技术 2022-05-29 次浏览

对决策树分类算法当中的某一个算法进行论述并进行实例讲解其过程

什么是决策树:

所谓决策树,就是一个类似于流程图的树形结构,树内部的每一个节点代表的是对一个特征的测试,树的分支代表该特征的每一个测试结果,而树的每一个叶子节点代表一个类别。树的最高层是就是根节点。

决策树的学习过程

决策树通过特征选择进行学习,通过在众多特征中选择出单个特征最为当前点的分裂标准,并一当前特征的不同种类作为分支向下分裂,从上至下递归地生成子节点,直到数据集不可分则停止决策树停止生长。
对于连续数据的处理,一般情况下需要选择将连续数据离散化,将连续数据的每个数据点都分别作为分类指标并依次进行计算相应指标的大小,选择其中最好的数据点,依次数据点将连续数据离散化。

评价指标

信息熵

信息是个很抽象的概念。人们常常说信息很多,或者信息较少,但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。
直到1948年,香农提出了“信息熵”的概念,才解决了对信息的量化度量问题。信息熵这个词是香农从热力学中借用过来的。热力学中的热熵是表示分子状态混乱程度的物理量。香农用信息熵的概念来描述信源的不确定度。信源的不确定性越大,信息熵也越大
从机器学习的角度来看,信息熵表示的是信息量的期望值。所以信息熵H(x)的定义如下(其中n为数据集中类别的数量):

[H(X)=-sum_{i=1}^{n}p(x_i)log_2{p(x_i)} ]

从这个公式也可以看出,如果概率是0或者是1的时候,熵就是0, 因为这种情况下随机变量的不确定性是最低的, 所以呢,熵越大,不确定性就越高。

条件熵

在实际的场景中,我们可能需要研究数据集中某个特征等于某个值时的信息熵等于多少,这个时候就需要用到条件熵。条件熵H(Y|X)表示特征X为某个值的条件下,类别为Y的熵。条件熵的计算公式如下:

[H(Y|X)=-sum_{i=1}^{n}p_iH(Y|X=x_i) ]

当然条件熵的一个性质也熵的性质一样,概率越确定,条件熵就越小,概率越五五开,条件熵就越大。

信息增益

信息增益就是表示我已知条件X后能得到信息Y的不确定性的减少程度。所以信息增益如果套上机器学习的话就是,如果把特征A对训练集D的信息增益记为g(D, A)的话,那么g(D, A)的计算公式就是:

[g(D,A)=H(D)-H(D,A) ]

信息熵减去条件熵即为信息增益。

信息增益率

信息增益准则对可取值数目较多的属性有所偏好,为减少这种偏好可能带来的不利影响,可以采用信息增益率来选择最优划分属性。增益率公式

[GainRatio(D|A)=frac{infoGain(D|A)}{IV(A)} ]

[IV(A)=-sum_{k=1}^{K}frac{|D_k|}{|D|}*log_2frac{|D_k|}{|D|} ]

其中$ A=[a_1,a_2,…a_k]$,K个值。若使用A来对样本集D进行划分,则会产生K个分支节点,其中第k个节点包含D中所有属性A上取值为 (a_k) 的样本,记为 (D_k) 。通常,属性A的可能取值数越多(即K越大),则IV(A)的值通常会越大。

基尼系数

表示在样本集合中一个随机选中的样本被分错的概率。Gini指数越小表示集合中被选中的样本被参错的概率越小,也就是说集合的纯度越高,反之,集合越不纯。当集合中所有样本为一个类时,基尼系数为0。计算公式为:

[G(p)=sum_{k=1}^{K}p_k(1-p_k)=1-sum_{k=1}^{K}p_k^2 ]

决策树常见模型

ID3.5:

决策树ID3算法的核心思想是以信息增益度量属性选择,选择分裂后信息增益最大的属性进行分裂。

C4.5:

ID3有一些缺陷,就是选择的时候容易选择一些比较容易分纯净的属性,尤其在具有像ID值这样的属性,因为每个ID都对应一个类别,所以分的很纯净,ID3比较倾向找到这样的属性做分裂。所以C4.5使用了新的评价指标信息增益率进行特征选择操作。同时可以将连续数值离散化。

CART:

与ID3 算法,C4.5 算法不同,CART算法只支持二叉树,同时既可以做分类数也可以做回归树,选用的特征选择指标为基尼系数。

剪枝

由于噪声等因素的影响,会使得样本某些特征的取值与样本自身的类别不相匹配的情况,基于这些数据生成的决策树的某些枝叶会产生一些错误;尤其是在决策树靠近枝叶的末端,由于样本变少,这种无关因素的干扰就会突显出来;由此产生的决策树可能存在过拟合的现象。树枝修剪就是通过统计学的方法删除不可靠的分支,使得整个决策树的分类速度和分类精度得到提高。
预剪枝:在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶节点。
后剪枝:先从训练集生成一棵完整的决策树,然后自底向上地对非叶节点进行考察,若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升,则将该子树替换为叶结点。

程序员灯塔
转载请注明原文链接:决策树
喜欢 (0)