决策树算法

决策树算法1.1算法导入决策树基于“树”结构来进行决策。1.2决策树定义决策树(DecisionTree)又称为判定树,是数据挖掘技术中的一-种重要的分类与回归方法,它是一-种以树结构(包括二叉树和多叉树)形式来表达的预测分析模型。 决策树(DecisionTree)是有监督学习的一种算法。 决策树有两种:分类树和回归树。1.3决策树发展第一个决策树算法:CLS(ConceptLearningSystem) 使决策树受到关注、成为机器学习主流技术的算法:I…

目录

1. 概述

1.1 算法导入

1.2 决策树定义

1.3 决策树发展

1.4 结构

1.5 从树到规则

2.决策树的构建

2.1 基本原理

2.2 特征选择

2.3 实例分析–ID3

2.4 增益率–C4.5算法

2.5 基尼指数–CART算法

 3. 决策树剪枝

 3.1 预剪枝

 3.2 后剪枝

 3.3 预剪枝vs后剪枝

 4. 连续值与缺失值处理

4.1 连续值处理

4.2 缺失值处理

5. 决策树的本质 

6. 决策树算法总结


1. 概述

1.1 算法导入

决策树基于“树”结构来进行决策。

决策树算法

1.2 决策树定义

  • 决策树( Decision Tree) 又称为判定树,是数据挖掘技术中的一-种重要的分类与回归方法,它是一种以树结构(包括二叉树和多叉树)形式来表达的预测分析模型。
  • 决策树(Decision Tree) 是有监督学习的一种算法。
  • 决策树有两种:分类树和回归树。

1.3 决策树发展

  • 第一个决策树算法: CLS (Concept Learning System)
  • 使决策树受到关注、成为机器学习主流技术的算法: ID3
  • 最常用的决策树算法: C4.5
  • 可以用于回归任务的决策树算法: CART (Classification and Regression Tree
  • 基于决策树的最强大算法: RF (Random Forest)

1.4 结构

  • 决策树由节点和分支组成。
  • 节点有三种类型:根节点,内部节点和叶节点。-般的,一棵决策树包含一个根节点,若干个内部节点和若干个叶节点。
  • 分支:用于连接各个节点。

决策树算法

        决策树学习的目的是为了产生一棵泛化能力强的决策树

1.5 从树到规则

        决策树转换成if- then规则:
                ●由决策树的根 节点到叶节点的每一条路径构建一 条规则;
                ●路径上内部节点的特征对应着规则的条件,而叶节点的类标签对应着规则的结论。

决策树算法

         互斥并且完备:每一个实例都被有且仅有一条路径或一条规则所覆盖。

2.决策树的构建

2.1 基本原理

策略:自上而下分而治之
        ●.自根至叶的递归过程, 在每个中间结点寻找一 个“划分” 属性。
        ●1)开始:构建根节点;所有训练数据都放在根节点,选择-个最优特征,按着这一特征将训练数据集分割成子集,进入子节点。
        ●2)所有子集按内部节点的属性递归的进行分割。
        ●3)如果这些子集已经能够被基本正确分类,那么构建叶节点,并将这些子集分到所对应的叶节点去。
        ●4)每个子集都被分到叶节点.上,即都有了明确的类,这样就生成了一颗决策树。

策略:分而治之”(divide- -and-conquer)
        自根至叶的递归过程,在每个中间结点寻找一个“划分”(split or test)属性
        三种停止条件:
                (1)当前结点包含的样本全属于同一类别,无需划分;
                (2)当前属性集为空,或是所有样本在所有属性.上取值相同,无法划分;
                (3)当前结点包含的样本集合为空,不能划分.

伪代码:

解释:

训练集D={(x1,y1),(x2,y2)…..}  x表示输入,y表示标签;x中有许多属性;属性集A={a1,a2,…..}

属性:要学习,不要学习;学习则为属性;

类别:要学习,不要学习;属于两种类别;C表示类别.

终止条件1:样本进来属于同一个类别,直接输出结果是C类返回。

终止条件2:没法划分了,特征向量中所有属性都用完了;或者D样本中的属性A都相同;然后将此节点标记为叶子节点,将样本D中数目最多的类当做类别返回。

终止条件3:当对数据进行划分成多个分支,如果存在分支中没有数据(分支为空),将划分前类别数目多的当做类别返回。

决策树算法

        决策树算法的核心如何选择最优划分属性。

2.2 特征选择

        特征(属性)选择
                ●特征选择 是决定用哪个特征来划分特征空间。
                ●特征选择表示从众多 的特征中选择-个特征作为当前节点分裂的标准。
                ●如何选择特征有 不同的量化评估方法,从而衍生出不同的决策树。

        ◆特征选择的准则是什么?什么样的划分属性是最优的?
        我们希望决策树的内部节点所包含的样本尽可能属于同一类别,即节点的纯度”越来越高,可以高效地从根结点到达叶节点,得到决策结果。

        信息熵(entropy)是度量样本集合“ 纯度”最常用的一种指标
                ●假定当前样本集合D中第k类样本所占的比例为pk
                ●则D的信息熵定义为

决策树算法

                 若p=0,则plog2 p=0。Ent(D )的最小值为0,最大值为log2 |y|

        Ent (D)的值越小,则D的纯度越高。

        信息增益直接以信息熵为基础,计算当前划分对信息熵所造成的变化。离散属性a的取值: {a,.,.,a”}          Dv:D中在a,上取值为aV的样本集合
        以属性a对数据集D进行划分所获得的信息增益为:

决策树算法

         ●信息增益越大,则意味着使用属性a来进行划分所获得的“纯度提升”越大。

        ●决策树算法第8行选择属性:       著名的ID3决策树算法

2.3 实例分析–ID3

决策树算法

         该数据集包含17个,   训练样例 |y|= 2,    其中正例占p1=\frac{8}{17}     反例占p2= \frac{9}{17}
         根节点的信息熵为:

决策树算法

        ●以属性“色泽”为例,其对应的3个数据
                子集分别为:D1(色泽=青绿)、D2(色泽=乌黑)、D3(色泽=浅白)
        ●^{D^{1}}(色泽=青绿)包含的编号为:{1,4,6,10,13,1 7}
        ●其中正样本占3/6、负样本占3/6

决策树算法

 分别计算^{D^{1}}(色泽=青绿)、^{D^{2}}(色泽=乌黑)、^{D^{3}}(色泽=浅白)

决策树算法

 属性“色泽”的信息增益为:

决策树算法

 再计算其他五个属性的信息增益:

决策树算法

显然,属性“纹理”的信息增益最大,选为划分属性

决策树算法

 开始递归:

        ●第一个分支( “纹理=清晰” )
        ●该分支包含的样例集合D1中有编号为{1,2,3,4,5,6,8,10,15}的9个样例
        ●用属性集合为{色泽,根蒂,敲声,脐部,触感},基于D1计算出各属性的信息增益:

决策树算法

 “根蒂”、”脐部”、”触感” 3个属性均取得了最大的信息增益,可任选其中之一作为划分属性.

         ●对每个分支做进一 步划分,最终得到决策树

决策树算法

        分析发现信息增益会对对属性越多被选中的概率越大,属性较少的选中概率越小…

2.4 增益率–C4.5算法

        信息增益:对可取值数目较多的属性有所偏好( 缺点)

        增益率:

决策树算法

  •  属性a的可能取值数目越多(即V越大),则IV(a)的值通常就越大。
  • 启发式:先从候选划分属性中找出信息增益高于平均水平的,再从中选取增益率最高的。

2.5 基尼指数–CART算法

        反映了从D中随机抽取两个样例,其类别标记不一致的概率
        Gini(D)越小,数据集D的纯度越高

                        决策树算法决策树算法

        属性a的基尼指数: 

决策树算法

        在候选属性集合中,选取那个使划分后基尼指数最小的属性

 3. 决策树剪枝

         研究表明:划分选择的各种准则虽然对决策树的尺寸有较大影响,但对泛化性能的影响很有限;例如信息增益与基尼指数产生的结果,仅在约2%的情况下不同;剪枝方法和程度对决策树泛化性能的影响更为显著;剪枝是决策树防止过拟合的手段,在数据带噪时甚至可能将泛化性能提升25%

        为了尽可能正确分类训练样本,有可能造成分支过多,出现过拟合可通过主动去掉一些分支来降低过拟合的风险
        基本策略:
                ◆预剪枝(pre-pruning):提前终止某些分支的生长
                ◆后剪枝(post-pruning):生成一棵完全树, 再“回头”剪枝

 原先的决策树只有训练集;现在我们挑选10个数据当做训练集,另外7个当做验证集

决策树算法

         使用训练集后生成的决策树,我们再使用验证集的数据对生成的决策树进行验证。验证后发现7个数据有4个数据是错误的,模型很不理想;模型出现过拟合,如何解决这个问题?——剪枝决策树算法

 3.1 预剪枝

        若不划分,则将其标记叶节点,类别标记为训练样例中最多的”类别,若选“好瓜”验证集中,{4,5,8}被分类正确, 得到验证集精度为3/7=42.9%

        若划分,根据结点2,3,4的训练“好瓜”、集分别标记为‘好瓜”、“坏瓜”验证集中,{4,5,8,11,12} 的样例被划分正确,验证集精度提升为5/7=71.4%

决策树算法

 根据“脐部”划分完成后是否需要根据“色泽”来划分?我们分析划分后的精度。

决策树算法

 3.2 后剪枝

        先生成一棵完整的决策树,其验证集精度测得为42.9%

决策树算法

         首先考虑结点6若将其替换为叶结点,根据落在其上的训练样例{7,15}将其标记为“好瓜”,测得验证集精度提高至57.1%,于是可以剪枝。

        剪枝后的决策树:

决策树算法

        考虑结点5若将其替换为叶结点,根据落在其上的训练样例{6,7,15}将其标记为“好瓜”,测得验证集精度仍为57.1%,于是可以不剪枝。

        再考虑父节点结点2若将其替换为叶结点,根据落在其.上的训练样例{1,2,3,14}将其标记为“好瓜”,测得验证集精度提升至71 .4%,于是可以剪枝。剪枝后的决策树:

决策树算法

 考虑结点3,1若将其替换为叶结点,先后替换为叶结点,均未测得验证集精度提升,不需要剪枝。

最终经过后剪枝得到的决策树:

决策树算法

 3.3 预剪枝vs后剪枝

        时间开销:
                ●预剪枝:训练时间开销降低,测试时间开销降低
                ●后剪枝:训练时间开销 增加,测试时间开 销降低
        过/欠拟合风险:
                ●预剪枝:过拟合风险降低,欠拟合风险增加
                ●后剪枝:过拟合风险降低,欠拟合风险基本不变
        泛化性能:
                后剪枝通常优于预剪枝

 4. 连续值与缺失值处理

4.1 连续值处理

        连续属性如何划分?
        由于连续属性的可取值数目不再有限,因此不能直接根据连续属性的可取值来对结点进行划分。基本思路:连续属性离散化,常见做法:二分法

4.2 缺失值处理

        现实应用中,经常会遇到属性值“缺失”(missing)现象仅使用无缺失的样例->对数据的极大浪费
使用带缺失值的样例,需解决:
        Q1:如何进行划分属性选择?
        Q2:给定划分属性,若样本在该属性上的值缺失,如何进行划分?
        基本思路:样本赋权,权重划分

        假设还是这个数据集,并且数据集有部分数据是缺失的。学习开始时,根结点包含样例集D中
全部17个样例,权重均为1

决策树算法

划分前:以属性“色泽”为例,该属性上无缺失值的样例子集D包含14 个样例,信息熵为

决策树算法

划分后:令\widetilde{^{D^{1}}}(色泽=青绿)、\widetilde{^{D^{2}}}(色泽=乌黑)、\widetilde{^{D^{3}}}(色泽=浅白)分别表示在属性“色泽”上样本子集,有

决策树算法

 因此,样本子集\widetilde{D}上属性“色泽”的信息增益为

决策树算法

 于是,样本集D上属性“色泽”的信息增益为

决策树算法

 类似地可计算出所有属性在数据集上的信息增益:

决策树算法

决策树算法

5. 决策树的本质 

树的分类本质–轴平行分类

  •         每个属性视为坐标空间中的一个坐标轴d个属性描述的样本就对应了d维空间中的一个数据点对样本分类===》在这个坐标空间中寻找不同类样本之间的分类边界
  •         决策树的分类边界特点:   轴平行,即它的分类边界由若干个与坐标轴平行的分段组成

 产生“轴平行”分类面实例分析:当属性是连续属性,我们使用二分法将其分类并构造一个决策树,通过构造密度与含糖率数据的值分布,我们就可以找到一个与轴平行区分好瓜与坏瓜的分类面。

决策树算法

         当学习任务所对应的分类边界很复杂时,需要非常多段划分才能获得较好的近似

决策树算法

 我们可以给决策树叠加一些东西,让他可以实现更加平滑的分类边界——斜决策树

“斜决策树”(oblique decision tree)不是为每个非叶结点寻找最优划分属性而是建立一个线性分类器

决策树算法

         所以决策树不单纯是一棵树,而是一颗可以挂载东西嵌入很多模型算法        的树,更复杂的“混合决策树”甚至可以在结点嵌入神经网络或其他非线性模型

6. 决策树算法总结

优点:
        (1)速度快:计算量相对较小,且容易转化成分类规则。只要沿着树根向下一直走到叶,沿途的分裂条件就能够唯一确定一条分类的谓词。
         (2)准确性高:挖掘出的分类规则准确性高,便于理解,决策树可以清晰的显示哪些字段比较重要。
         (3) 非参数学习,不需要设置参数。

缺点:
        (1)缺乏伸缩性:由于进行深度优先搜索,所以算法受内存大小限制,难于处理大训练集。
        (2)为了处理大数据集或连续值的种种改进算法(离散化、取样)不仅增加了分类算法的额外开销,而且降低了分类的准确性,对连续性的字段比较难预测,当类别太多时,错误可能就会增加的比较快,对有时间顺序的数据,需要很多预处理的工作。

决策树算法实现:

from sklearn.tree import Decis ionTreeClassifier
model = Decis ionTreeClassifier( )
 

今天的文章决策树算法分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/8461.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注