改进的GDBT迭代决策树分类算法及其应用

曹颖超

【摘 要】传统的决策树分类方法有ID3和C4.5，由于单棵决策树的局限性，在训练数据过程中由于属性值的过多容易出现过拟合现象，本文研究使用多颗决策树和Boosting算法结合在一起的GDBT分类方法。GDBT算法是基于回归的思想，对复杂数据有较强的处理能力，且它是由多棵树组成的，构造树不复杂，每次用残差进行调整，保证分类的精确。

【关键词】分类算法；决策树；GBDT

0 引言

决策树分类方法是一种自上而下，在分支节点进行属性值的比较得到分裂点属性，根据不同的属性值判断构造向下的分支，最终在叶子节点得到分类结果。传统的决策树分类方法有ID3和C4.5，他们都是以信息熵作为分类依据，是单颗决策树。然而，由于单棵决策树的局限性，在训练数据过程中由于属性值的过多容易出现过拟合（Over-Fitting）现象。为了弥补单棵决策树的缺陷，本研究使用多颗决策树和Boosting算法结合在一起的GDBT分类方法。

1 改进的决策树分类算法

1.1 Boosting方法

Boosting方法其实是一个框架，是用来提升算法准确度的，可以将其他算法放到boosting框架里面，boosting方法通过构造一系列的预测函数然后将它们合并形成一个最终的预测函数。Boosting方法主要是通过操作样本集获得一些子集，然后用弱分类算法去训练样本子集来生成一系列基分类器。每得到一个样本集就用该基分类算法在该样本集上产生一个基分类器，这样迭代N次后，就可以得到N个基分类器，然后运用Boosting框架将这 N个基分类器赋予不同的权值融合在一起合，产生一个最终的结果分类器，在这 N个基分类器中，每个单独的基分类器识别度不同，也许有的基分类器识别率很低，但是当他们加权融合在一起生成的最终结果分类器识别率就很高，这样就提高了算法的识别率或者准确度。

1.2 随机森林

随机森林这个术语最早由1995年由贝尔实验室的Tin Kam Ho所提出的随机决策森林（random decision forests）而来的，后来是结合 Breimans 的“Bootstrap aggregating”想法和 Ho 的“random subspace method”以建造决策树的集合，就形成了随机森林算法。

随机森林算法运用重采样技术，从原始训练样本集中有放回地重复随机抽取N个样本形成样本子集，然后根据N个样本子集生成N决策树，当输入测试数据时，在每一颗决策树上进行判断，得到分类结果，最后统计哪一个分类选择最多，就预测这个测试样本属于哪一个分类。随机森林算法能处理很高维度的数据，并且不用做特征选择，有很多颗决策树，不会对数据过度拟合，抗噪声能力强。缺点就是一个测试样本在每一颗树上都要判断，计算过于复杂，对线性数据不敏感，且对算法的准确度没有过多的提升。

1.3 GBDT算法

1.3.1 GDBT 思想与原理

不同于随机森林，GBDT 是决策树与 Boosting 方法相结合的应用。GBDT 模 型 全 称 Gradient Boosted Decision Trees，是一种迭代的决策树算法，该算法由多棵决策树组成，通常都是上百棵树，而且每棵树规模都较小。模型预测的时候，对于输入的一个样本实例，首先会赋予一个初值，然后会遍历每一棵决策树，每棵树都会对预测值进行调整修正，最终的结果是将每一棵决策树的结果进行累加得到的最后得到预测的结果，具体算法思想如图1所示。

从图1中可以看出GBDT的训练过程是线性的，它不像随机森林算法那样并行训练多棵树，第一颗T1训练结果与真实值T的残差作为第二颗决策树T2的样本，第n颗决策树Tn的样本就是第N-1颗决策树Tn-1的训练结果，所以该模型的最终分类结果就是将每一颗决策树上的结点值累加。即得到公式：

T=T1+T2…Tn（1）

1.3.2 GBDT分裂点

如果对于一个模型有多种特征值如何选择特征值去分类，在ID3算法中选择每个属性中条件熵最小也就是信息增益最大的属性作为分裂点，在GBDT算法中选择属性的最小均方差或者是使得（左子树样本目标值和的平方均值+右子树样本目标值和的平方均值-父结点所有样本目标值和的平方均值）最大的那个分裂点作为分类特征。

当特征很多的时候，特征的选取对于决策树的创建有很大的影响，他决定这颗回归树的深度，所以必须通过正确的方式找到最能决定样本分类的分裂特征，才能创建预测效果较好的决策树。

1.3.3 GDBT算法示例

有四个训练样本A、B、C、D，他们的年龄分别是14、16、24、26，现在要对他们进行年龄预测。其中A、B是学生，C、D是已经工作的人。使用GBDT算法得到第一棵树如图2所示。

首先，输入样本的均值，这里均值为20，选择第一个特征分类（具体选择是根据上文的G来判断的），可以把4个样本分成两类，一类是购物金额<1K，一类是>1K的。根据这个特征可以把样本分成两类，如果到这里就停止学习了，就要统计叶子节点包含了哪些样本，如果A、B被分到了一组，那么该节点的值就是分到左子树所有样本的平均值，这里为15，也就是这些样本的预测值，即A、B的预测值都为15，右子树同理計算；如果学习还没有停止，那么就要计算分到该类的样本与预测值的差，A=-1，B=1，C=-1，D=1，这些得到的残差作为下一颗决策树的样本，下一颗树的学习过程如图3所示。

第二棵决策树，把第一棵的残差样本（A，-1岁）、（B，1岁）、（C，-1岁）、（D，1岁）输入。此时要选取第二个特征值来分类（具体选择的特征还是上文求出G的公式）。接下来又可以把样本分成两类，一部分是A、C组成了左叶子，另一部分是B、D组成的右叶子，先计算记一下残差发现都是0，GBDT算法的分类过程就是不断的将残差接近0，所以直到残差为0的时候就可以结束学习了，那么可以得到ABCD的预测值，即AC的预测结果都是-1，BD都是1。

现在给一个特征表测试一下，如表1所示。

2 结论

通过分析传统决策树和迭代决策树有何区别，并举例说明，可以得到以下结论：传统决策树一般适用于一个属性的特征值较少的情况，决策树构造不是很复杂，对于复杂的数据，传统决策树分类效果并不是很好，构造的树会很深，横向也很广，有可能最终还会造成无法分类；这时就要找寻新的算法来代替传统决策树，幸运的是GBDT算法是一个可行的算法，基于回归的思想对复杂数据有较强的处理能力，而且它是由多棵树组成的，构造树不复杂，每次用残差进行调整，保证分类的精确。

【参考文献】

[1]孟岩，汪云云.典型半监督分类算法的研究分析[J].计算机技术与发展，2017（09）：1-7.

[2]龙浩.用于不平衡分类问题的自适应加权极限学习机研究[D].深圳大学，2017.

[3]杨志辉.基于机器学习算法在数据分类中的应用研究[D].中北大学，2017.

[4]沈龙凤，宋万干，葛方振，等.最优路径森林分类算法综述[J].计算机应用研究，2018（01）：1-9.

[责任编辑：朱丽娜]endprint