目录

前言

一、面向分类问题的决策树特征选择

1、纯节点、不纯节点

2、节点的不纯度（杂度）

1.2.1 熵不纯度

1.2.2  方差不纯度

1.2.3  误差不纯度

3、基于不纯度的节点特征选择规则 ---- 以分类树为例

3.1  信息增益

3.2  增益率

3.3  基尼指数

二、分类树的构建

1、决策树算法的研究历史

2、ID3决策树算法

2.1  ID3算法基本思想

2.2  算法基本点

2.3  算法说明

2.4  算法步骤

3、C4.5决策树

3.1  C4.5算法简述

3.2  C4.5算法是ID3算法的后继和改进

3.3  C4.5算法步骤

3.4  C4.5算法关于连续数值特征的处理方法 ---- 二分法

3.5  C4.5算法关于特征缺失值的处理方式

4、CART决策树

4.1  CART树的引入

4.2  递归二叉分类树的生成算法

三、回归树的构建

1、基本思想

2、CART树 ---- 最小二乘回归树生成算法

---

前言

有很多新手刚刚接触大数据与人工智能方向学习，如果不知道怎么着手的，跟我一起慢慢进步叭~

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、面向分类问题的决策树特征选择

1、纯节点、不纯节点

若到达某节点的训练样本集只含一类样本，则该节点为纯节点，或同质节点；

否则，为不纯节点，或异构节点。

2、节点的不纯度（杂度）

关于决策树节点不纯程度的度量。

节点不纯度的典型度量方式：

前提：

1.2.1 熵不纯度

1.2.2  方差不纯度

1.2.3  误差不纯度

两类别分类，关于同一个数据集的三种不纯度度量与某类概率关系：

3、基于不纯度的节点特征选择规则 ---- 以分类树为例

一般而言，随着节点划分的不断进行，希望决策树分支节点所含样本尽量来自相同类别，即：节点的纯度不断增加。

3.1  信息增益

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

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

假定离散属性a有v个可能的取值{a1,a2,…,av}，若使用a来对样本集D进行划分，则会产生v个分支节点，其中第v个分支节点包含了D中所有在属性a上取值为av的样本，记为Dv，我们可根据上式计算出Dv的信息熵，再考虑到不同的分支节点所包含的样本数不同，给分支节点赋予权重|Dv| / |D|，即样本数越多的分支节点的影响越大，于是可计算出用属性a对样本集D进行划分所获得的信息增益：

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的纯度提升越大，即每次划分分支时选择信息增益最大的那个属性。

3.2  增益率

实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的决策树算法不直接使用信息增益，而是使用增益率来选择最后划分属性。增益率定义为：，其中，称为属性a的固有值。

一般来说，属性a的可能取值数目越多（即v越大），则IV(a)的值通常会越大。

需要注意的是，增益率准则对可取值数目较少的属性有所偏好。因此，我们并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3.3  基尼指数

CART决策树使用基尼指数来选择划分属性。数据集D的纯度可用基尼值来度量：

直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D)越小，数据集D的纯度越高。

属性a的基尼指数定义为：

我们在侯选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

二、分类树的构建

1、决策树算法的研究历史

第一个决策树算法：CLS

真正引发决策树研究热潮的算法：ID3，其增量版本还有：ID4,ID5等。

最流行的决策树算法：C4.5，以ID3为基础，可处理连续特征的算法。

通用的决策树算法：CART

基于决策树的较强学习算法还有：随机森林的集成算法

其他决策树算法：SLIQ、SPRINT、RainForest等

2、ID3决策树算法

2.1  ID3算法基本思想

节点的评价 ---- 熵不纯度；新节点的生成 ---- 基于最大信息增益

2.2  算法基本点

①若当前节点只含同一类样本，则为纯节点，停止分裂；

②若当前特征列表中再无可用特征，则根据多数表决确定该节点的类标号，停止分裂；

③其他：选择最佳分裂的特征（最大信息增益足够大），根据所选特征取值（特征取值数目决定了该节点分裂为后继子节点的数目），逐一进行分裂，即递归构造决策树。

2.3  算法说明

①ID3决策树仅仅适用于离散或者非数值型特征描述的样本集

②ID3算法仅涉及决策树的生成，无剪枝步骤

③每个节点的分支数目与该节点所用的特征取值数目一致

④基于“最大信息增益”准则，确定当前节点分裂所使用的特征

⑤算法直到所有叶节点的不纯度最小（例如：到达该节点的训练样本来自同一类别）或不再有可用的特征时停止

2.4  算法步骤

输入：训练样本集D，特征集A，非负阈值

输出：决策树T

STEP1.若D中所有样本属于同一类别，则T为单节点树，并将作为该节点的类别标记，返回T

STEP2.若A为空集，则T为单节点树，并将D中具有最多训练样本数目的类别作为该节点的类别标记，返回T

STEP3.若A不是空集，计算A中各个特征a对样本集D的信息增益{g(D,a),a∈A}，并选择具有最大信息增益的特征：

若特征的信息增益小于，则执行3.1，否则执行3.2

        3.1 置T为单节点树，将D中具有最多训练样本数目的类别作为该节点的类别标记，并且返回T；

        3.2 对特征的每一可能值，按照 = ，并将D划分为若干非空子集D(i)，将D(i)中具有最多训练样本数目的类别作为标记，构建子节点，由节点及其子结点构成树T，返回T。

STEP4.对第i个子节点，以D(i)为训练集，以A-{}为特征集，递归调用，得到子树Ti，返回Ti。

3、C4.5决策树

3.1  C4.5算法简述

C4.5算法是对ID3算法的扩展。

C4.5的特别之处：对连续数值特征的处理；对缺失值的处理。

3.2  C4.5算法是ID3算法的后继和改进

①可以处理实值数据（连续数据）

②每个划分的分支因子等于查询属性的取值个数

③采用信息增益率作为选择查询的依据

④首先让树充分生长，然后利用分支的统计显著性来实现剪枝

3.3  C4.5算法步骤

输入：训练样本集D，特征集A，非负阈值

输出：决策树T

STEP1.若D中所有样本属于同一类别，则T为单节点树，并将作为该节点的类别标记，返回T

STEP2.若A为空集，则T为单节点树，并将D中具有最多训练样本数目的类别作为该节点的类别标记，返回T

STEP3.若A不是空集，计算A中各个特征a对样本集D的信息增益{g(D,a),a∈A}，并选择具有最大信息增益率的特征：

若特征的信息增益率小于，则执行3.1，否则执行3.2

        3.1 置T为单节点树，将D中具有最多训练样本数目的类别作为该节点的类别标记，并且返回T；

        3.2 对特征的每一可能值，按照 = ，并将D划分为若干非空子集D(i)，将D(i)中具有最多训练样本数目的类别作为标记，构建子节点，由节点及其子结点构成树T，返回T。

STEP4.对第i个子节点，以D(i)为训练集，以A-{}为特征集，递归调用，得到子树Ti，返回Ti。

3.4  C4.5算法关于连续数值特征的处理方法 ---- 二分法

3.5  C4.5算法关于特征缺失值的处理方式

几个核心问题：

问题一：决策树的构建过程中，如何在训练样本存在特征取值缺失的情况下，进行节点的特征选择？

问题二：若已经完成了决策树某节点的特征选择，并且该节点使用的特征为具有缺失值的特征，如何基于该特征对到达当前节点的训练集进行有效划分？

问题三：若已经完成了决策树的构建，若待决策的样本关于决策树某些节点的特征存在缺失，如何对该样本的类别进行预测？

解决方案：

问题一的等价问题：若到达当前节点的训练样本中，存在部分样本关于某特征的取值缺失，如何估计基于该特征的信息增益？信息增益率？

问题二的实质：训练样本集的划分问题

问题三的实质：如何预测具有特征缺失的样本的类别？

4、CART决策树

4.1  CART树的引入

①CART树既可用于分类，也可用于对连续变量的回归

②每个节点只能有两个子节点，说白了，CART决策树为二叉树。这样做的目的是不易产生数据碎片，精确度往往也会高于多叉树

③在CART算法中，采用了二元划分 ------ 递归二叉树

④不纯性度量：面向分类问题：基于最小GINI指数规则

                         面向回归问题：基于最小平方残差、最小绝对残差

⑤用独立的验证集对训练集生长的树进行剪枝

4.2  递归二叉分类树的生成算法

基本思想：a.一个分类树对应输入空间（特征空间）的一个划分，以及在该划分单元上的类别输出值；

b.根据训练样本集D，从根节点开始，将输入空间进行划分，递归构建二叉分类树；

c.借助基尼指数进行特征选择，同时决定该特征的最优二值切分点。

即：CART决策树是二叉树，内部节点特征的取值为“是”或“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

输入：训练样本集，其中：

           停止计算的条件

输出：CART决策树

步骤：

STEP1.设节点的训练数据集为D，计算现有特征对该数据集的GINI指数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割为D1和D2两部分，计算A=a时的GINI指数

STEP2.在所有可能的特征A以及它们所有可能的切分点a中，选择GINI指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现节点生成两个子节点，将训练数据集依据特征分配到两个子节点中去

STEP3.对两个子节点递归地调用STEP1和STEP2，直至满足停止条件。停止条件：节点中的样本个数小于预定阈值，或样本集的GINI指数小于预定阈值，或者没有更多特征

STEP4.递归生成CART决策树

三、回归树的构建

1、基本思想

一个回归树对应输入空间（或特征空间）的一个划分，以及在该划分单元上的输出值。在训练样本集D所在的输入空间，递归地将每个区域划分为两个子区域，并根据落入每个子区域的训练样本输出值，决定该子区域的输出，构建二叉树。

2、CART树 ---- 最小二乘回归树生成算法

输入：训练样本集，其中：

输出：回归树f(x)

步骤：

STEP1.从输入向量x中选择最优切分变量j和切分点s，求解：

遍历变量，对固定的切分变量扫描切分点，选择使上式最小值的（j，s）对

STEP2.用选定的（j，s）对，确定划分区域R1(j,s)，R2(j,s)，并确定相应的输出值

STEP3.继续对两个子区域调用STEP1和STEP2，直到满足停止条件

STEP4.将输入空间划分为M个区域：R1,R2,…,Rm；生成决策树

最后

以上就是凶狠台灯为你收集整理的大数据与人工智能方向基础 ---- 特征选择与决策树的构建前言一、面向分类问题的决策树特征选择二、分类树的构建三、回归树的构建的全部内容，希望文章能够帮你解决大数据与人工智能方向基础 ---- 特征选择与决策树的构建前言一、面向分类问题的决策树特征选择二、分类树的构建三、回归树的构建所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。