在中，我们对Boosting家族的Adaboost算法做了总结，本文就对Boosting家族中另一个重要的算法梯度提升树(Gradient Boosting Decison Tree, 以下简称GBDT)做一个总结。GBDT有很多简称，有GBT（Gradient Boosting Tree）,&GTB（Gradient Tree Boosting&），&GBRT（Gradient Boosting Regression Tree）, MART(Multiple Additive Regression Tree)，其实都是指的同一种算法，本文统一简称GBDT。GBDT在BAT大厂中也有广泛的应用，假如要选择3个最重要的机器学习算法的话，个人认为GBDT应该占一席之地。
1. GBDT概述
　　　　GBDT也是集成学习Boosting家族的成员，但是却和传统的Adaboost有很大的不同。回顾下Adaboost，我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同。
　　　　在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是$f_{t-1}(x)$, 损失函数是$L(y,&f_{t-1}(x))$, 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器$h_t(x)$，让本轮的损失损失$L(y,&f_{t}(x) =L(y,&f_{t-1}(x)+ h_t(x))$最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。
　　　　GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。
　　　　从上面的例子看这个思想还是蛮简单的，但是有个问题是这个损失的拟合不好度量，损失函数各种各样，怎么找到一种通用的拟合方法呢？
2. GBDT的负梯度拟合
　　　　在上一节中，我们介绍了GBDT的基本思路，但是没有解决损失函数拟合方法的问题。针对这个问题，大牛Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。第t轮的第i个样本的损失函数的负梯度表示为$$r_{ti} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial&f(x_i)}\bigg]_{f(x) = f_{t-1}\;\; (x)}$$
　　　　利用$(x_i,r_{ti})\;\; (i=1,2,..m)$,我们可以拟合一颗CART回归树，得到了第t颗回归树，其对应的叶节点区域$R_{tj}, j =1,2,..., J$。其中J为叶子节点的个数。
　　　　针对每一个叶子节点里的样本，我们求出使损失函数最小，也就是拟合叶子节点最好的的输出值$c_{tj}$如下：$$c_{tj} = \underbrace{arg\; min}_{c}\sum\limits_{x_i \in R_{tj}} L(y_i,f_{t-1}(x_i) +c)$$
　　　　这样我们就得到了本轮的决策树拟合函数如下：$$h_t(x) = \sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj})$$
　　　　从而本轮最终得到的强学习器的表达式如下：$$f_{t}(x) = f_{t-1}(x) + \sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj})&$$
　　　　通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。
&3.&GBDT回归算法
　　　　好了，有了上面的思路，下面我们总结下GBDT的回归算法。为什么没有加上分类算法一起？那是因为分类算法的输出是不连续的类别值，需要一些处理才能使用负梯度，我们在下一节讲。
　　　　输入是训练集样本$T=\{(x_,y_1),(x_2,y_2), ...(x_m,y_m)\}$， 最大迭代次数T, 损失函数L。
　　　　输出是强学习器f(x)
　　　　1) 初始化弱学习器$$f_0(x) = \underbrace{arg\; min}_{c}\sum\limits_{i=1}^{m}L(y_i, c)$$
　　　　2) 对迭代轮数t=1,2,...T有：
　　　　　　a)对样本i=1,2，...m，计算负梯度$$r_{ti} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial&f(x_i)}\bigg]_{f(x) = f_{t-1}\;\; (x)}$$
　　　　　　b)利用$(x_i,r_{ti})\;\; (i=1,2,..m)$, 拟合一颗CART回归树,得到第t颗回归树，其对应的叶子节点区域为$R_{tj}, j =1,2,..., J$。其中J为回归树t的叶子节点的个数。
　　　　　　c) 对叶子区域j =1,2,..J,计算最佳拟合值$$c_{tj} = \underbrace{arg\; min}_{c}\sum\limits_{x_i \in R_{tj}} L(y_i,f_{t-1}(x_i) +c)$$
　　　　　　d) 更新强学习器$$f_{t}(x) = f_{t-1}(x) + \sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj})&$$
　　　　3) 得到强学习器f(x)的表达式$$f(x) = f_T(x) =f_0(x) + \sum\limits_{t=1}^{T}\sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj})$$
4. GBDT分类算法
　　　　这里我们再看看GBDT分类算法，GBDT的分类算法从思想上和GBDT的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。
　　　　为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论用对数似然损失函数的GBDT分类。而对于对数似然损失函数，我们又有二元分类和多元分类的区别。
4.1 二元GBDT分类算法
　　　　对于二元GBDT，如果用类似于逻辑回归的对数似然损失函数，则损失函数为：$$L(y, f(x)) = log(1+ exp(-yf(x)))$$
　　　　其中$y \in\{-1, +1\}$。则此时的负梯度误差为$$r_{ti} = -\bigg[\frac{\partial L(y, f(x_i)))}{\partial&f(x_i)}\bigg]_{f(x) = f_{t-1}\;\; (x)} = y_i/(1+exp(y_if(x_i)))$$
　　　　对于生成的决策树，我们各个叶子节点的最佳残差拟合值为$$c_{tj} = \underbrace{arg\; min}_{c}\sum\limits_{x_i \in R_{tj}} log(1+exp(-y_i(f_{t-1}(x_i) +c)))$$
　　　　由于上式比较难优化，我们一般使用近似值代替$$c_{tj} =&\sum\limits_{x_i \in R_{tj}}r_{ti}\bigg /&&\sum\limits_{x_i \in R_{tj}}|r_{ti}|(1-|r_{ti}|)$$
　　　　除了负梯度计算和叶子节点的最佳残差拟合的线性搜索，二元GBDT分类和GBDT回归算法过程相同。
4.2 多元GBDT分类算法
　　　　多元GBDT要比二元GBDT复杂一些，对应的是多元逻辑回归和二元逻辑回归的复杂度差别。假设类别数为K，则此时我们的对数似然损失函数为：$$L(y, f(x)) = - &\sum\limits_{k=1}^{K}y_klog\;p_k(x)&$$
　　　　其中如果样本输出类别为k，则$y_k=1$。第k类的概率$p_k(x)&$的表达式为：$$p_k(x) = exp(f_k(x)) \bigg / \sum\limits_{l=1}^{K}&exp(f_l(x))&$$
　　　　集合上两式，我们可以计算出第$t$轮的第$i$个样本对应类别$l$的负梯度误差为$$r_{til} =&-\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial&f(x_i)}\bigg]_{f_k(x) = f_{l, t-1}\;\; (x)} = y_{il} - p_{l, t-1}(x_i)$$
　　　　观察上式可以看出，其实这里的误差就是样本$i$对应类别$l$的真实概率和$t-1$轮预测概率的差值。
　　　　对于生成的决策树，我们各个叶子节点的最佳残差拟合值为$$c_{tjl} = \underbrace{arg\; min}_{c_{jl}}\sum\limits_{i=0}^{m}\sum\limits_{k=1}^{K}&L(y_k, f_{t-1, l}(x) + \sum\limits_{j=0}^{J}c_{jl} I(x_i \in R_{tj}))$$
　　　　由于上式比较难优化，我们一般使用近似值代替$$c_{tjl} = &\frac{K-1}{K} \; \frac{\sum\limits_{x_i \in R_{tjl}}r_{til}}{\sum\limits_{x_i \in R_{til}}|r_{til}|(1-|r_{til}|)}$$
　　　　除了负梯度计算和叶子节点的最佳残差拟合的线性搜索，多元GBDT分类和二元GBDT分类以及GBDT回归算法过程相同。
5. GBDT常用损失函数
　　　　这里我们再对常用的GBDT损失函数做一个总结。
　　　　对于分类算法，其损失函数一般有对数损失函数和指数损失函数两种:
　　　　a) 如果是指数损失函数，则损失函数表达式为$$L(y, f(x)) = exp(-yf(x))$$
　　　　其负梯度计算和叶子节点的最佳残差拟合参见Adaboost原理篇。
　　　　b)&如果是对数损失函数，分为二元分类和多元分类两种，参见4.1节和4.2节。
　　　　对于回归算法，常用损失函数有如下4种:
　　　　a)均方差，这个是最常见的回归损失函数了$$L(y, f(x)) =(y-f(x))^2$$
　　　　b)绝对损失，这个损失函数也很常见$$L(y, f(x)) =|y-f(x)|$$
　　　　　　对应负梯度误差为：$$sign(y_i-f(x_i))$$
　　　　c)Huber损失，它是均方差和绝对损失的折衷产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量。损失函数如下：
$$L(y, f(x))=\begin{cases}\frac{1}{2}(y-f(x))^2& {|y-f(x)| \leq \delta}\\\delta(|y-f(x)| - \frac{\delta}{2})& {|y-f(x)| & \delta}\end{cases}$$
　　　　对应的负梯度误差为：
$$r(y_i, f(x_i))=\begin{cases}y_i-f(x_i)& {|y_i-f(x_i)| \leq \delta}\\\delta sign(y_i-f(x_i))& {|y_i-f(x_i)| & \delta}\end{cases}$$
　　　　d) 分位数损失。它对应的是分位数回归的损失函数，表达式为$$L(y, f(x)) =\sum\limits_{y \geq f(x)}\theta|y - f(x)| + \sum\limits_{y & f(x)}(1-\theta)|y - f(x)|&$$
　　　　　　其中$\theta$为分位数，需要我们在回归前指定。对应的负梯度误差为：
$$r(y_i, f(x_i))=\begin{cases}\theta& { y_i \geq f(x_i)}\\\theta - 1 & {y_i & f(x_i) }\end{cases}$$
　　　　对于Huber损失和分位数损失，主要用于健壮回归，也就是减少异常点对损失函数的影响。
6. GBDT的正则化
　　　　和Adaboost一样，我们也需要对GBDT进行正则化，防止过拟合。GBDT的正则化主要有三种方式。
　　　　第一种是和Adaboost类似的正则化项，即步长(learning rate)。定义为$\nu$,对于前面的弱学习器的迭代$$f_{k}(x) = f_{k-1}(x) + h_k(x) $$
　　　　如果我们加上了正则化项，则有$$f_{k}(x) = f_{k-1}(x) + \nu h_k(x) $$
　　　　$\nu$的取值范围为$0 & \nu \leq 1 $。对于同样的训练集学习效果，较小的$\nu$意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。
　　　　第二种正则化的方式是通过子采样比例（subsample）。取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。
　　　　使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样，程序可以通过采样分发到不同的任务去做boosting的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。
　　　　第三种是对于弱学习器即CART回归树进行正则化剪枝。在决策树原理篇里我们已经讲过，这里就不重复了。
7. GBDT小结　
　　　　GBDT终于讲完了，GDBT本身并不复杂，不过要吃透的话需要对集成学习的原理，决策树原理和各种损失函树有一定的了解。由于GBDT的卓越性能，只要是研究机器学习都应该掌握这个算法，包括背后的原理和应用调参方法。目前GBDT的算法比较好的库是xgboost。当然scikit-learn也可以。
　　　　最后总结下GBDT的优缺点。
　　　　GBDT主要的优点有：
　　　　1) 可以灵活处理各种类型的数据，包括连续值和离散值。
　　　　2) 在相对少的调参时间情况下，预测的准备率也可以比较高。这个是相对SVM来说的。
　　　　3）使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。
　　　　GBDT的主要缺点有：
　　　　1)由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
　　　　以上就是GBDT的原理总结，后面会讲GBDT的scikit-learn调参，敬请期待。
（欢迎转载，转载请注明出处。欢迎沟通交流： liujianping-）&
阅读(...) 评论()没有更多推荐了，
不良信息举报
举报内容：
N问GBDT（1-12答案）
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！没有更多推荐了，
新书&&深度剖析Hadoop HDFS&&发布上市，此书源自于笔者博客，重新经过整理，完善而成，此书的定位并不是一本纯源码分析的书籍，其中有许多笔者在工作和学习中对于HDFS的一些有趣的看法和理解。
不良信息举报
举报内容：
随机森林和GBDT的学习
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！随机森林，adaboost，GBDT回归方法应该如何选择？ - 知乎2被浏览329分享邀请回答03 条评论分享收藏感谢收起写回答随机森林和GBDT的学习
提到森林，就不得不联想到树，因为正是一棵棵的树构成了庞大的森林，而在本篇文章中的&树&，指的就是Decision Tree-----决策树。随机森林就是一棵棵决策树的组合，也就是说随机森林=boosting+决策树，这样就好理解多了吧，再来说说GBDT，GBDT全称是Gradient Boosting Decision Tree，就是梯度提升决策树，与随机森林的思想很像，但是比随机森林稍稍的难一点，当然效果相对于前者而言，也会好许多。由于本人才疏学浅，本文只会详细讲述Random Forest算法的部分，至于GBDT我会给出一小段篇幅做介绍引导，读者能够如果有兴趣的话，可以自行学习。
随机森林算法
要想理解随机森林算法，就不得不提决策树，什么是决策树，如何构造决策树，简单的回答就是数据的分类以树形结构的方式所展现，每个子分支都代表着不同的分类情况，比如下面的这个图所示：
当然决策树的每个节点分支不一定是三元的，可以有2个或者更多。分类的终止条件为，没有可以再拿来分类的属性条件或者说分到的数据的分类已经完全一致的情况。决策树分类的标准和依据是什么呢，下面介绍主要的2种划分标准。
1、信息增益。这是ID3算法系列所用的方法，C4.5算法在这上面做了少许的改进，用信息增益率来作为划分的标准，可以稍稍减小数据过于拟合的缺点。
2、基尼指数。这是CART分类回归树所用的方法。也是类似于信息增益的一个定义，最终都是根据数据划分后的纯度来做比较，这个纯度，你也可以理解为熵的变化，当然我们所希望的情况就是分类后数据的纯度更纯，也就是说，前后划分分类之后的熵的差越大越好。不过CART算法比较好的一点是树构造好后，还有剪枝的操作，剪枝操作的种类就比较多了，我之前在实现CART算法时用的是代价复杂度的剪枝方法。
这2种决策算法在我之前的博文中已经有所提及，不理解的可以点击我的ID3系列算法介绍和我的CART分类回归树算法。
原本不打算将Boosting单独拉出来讲的，后来想想还是有很多内容可谈的。Boosting本身不是一种算法，他更应该说是一种思想，首先对数据构造n个弱分类器，最后通过组合n个弱分类器对于某个数据的判断结果作为最终的分类结果，就变成了一个强分类器，效果自然要好过单一分类器的分类效果。他可以理解为是一种提升算法，举一个比较常见的Boosting思想的算法AdaBoost，他在训练每个弱分类器的时候，提高了对于之前分错数据的权重值，最终能够组成一批相互互补的分类器集合。详细可以查看我的AdaBoost算法学习。
OK，2个重要的概念都已经介绍完毕，终于可以介绍主角Random Forest的出现了，正如前言中所说Random Forest=Decision Trees + Boosting，这里的每个弱分类器就是一个决策树了，不过这里的决策树都是二叉树，就是只有2个孩子分支，自然我立刻想到的做法就是用CART算法来构建，因为人家算法就是二元分支的。随机算法，随机算法，当然重在随机2个字上面，下面是2个方面体现了随机性。对于数据样本的采集量，比如我数据由100条，我可以每次随机取出其中的20条，作为我构造决策树的源数据，采取又放回的方式，并不是第一次抽到的数据，第二次不能重复，第二随机性体现在对于数据属性的随机采集，比如一行数据总共有10个特征属性，我每次随机采用其中的4个。正是由于对于数据的行压缩和列压缩，使得数据的随机性得以保证，就很难出现之前的数据过拟合的问题了，也就不需要在决策树最后进行剪枝操作了，这个是与一般的CART算法所不同的，尤其需要注意。
下面是随机森林算法的构造过程：
1、通过给定的原始数据，选出其中部分数据进行决策树的构造，数据选取是&有放回&的过程，我在这里用的是CART分类回归树。
2、随机森林构造完成之后，给定一组测试数据，使得每个分类器对其结果分类进行评估，最后取评估结果的众数最为最终结果。
算法非常的好理解，在Boosting算法和决策树之上做了一个集成，下面给出算法的实现，很多资料上只有大篇幅的理论，我还是希望能带给大家一点实在的东西。
随机算法的实现
输入数据(之前决策树算法时用过的)input.txt:
Rid Age Income Student CreditRating BuysComputer
1 Youth High No Fair No
2 Youth High No Excellent No
3 MiddleAged High No Fair Yes
4 Senior Medium No Fair Yes
5 Senior Low Yes Fair Yes
6 Senior Low Yes Excellent No
7 MiddleAged Low Yes Excellent Yes
8 Youth Medium No Fair No
9 Youth Low Yes Fair Yes
10 Senior Medium Yes Fair Yes
11 Youth Medium Yes Excellent Yes
12 MiddleAged Medium No Excellent Yes
13 MiddleAged High Yes Fair Yes
14 Senior Medium No Excellent No
树节点类TreeNode.java:
package DataMining_RandomF
import java.util.ArrayL
* 回归分类树节点
* @author lyq
public class TreeNode {
// 节点属性名字
private String attrN
// 节点索引标号
private int nodeI
//包含的叶子节点数
private int leafN
// 节点误差率
// 父亲分类属性值
private String parentAttrV
// 孩子节点
private TreeNode[] childAttrN
// 数据记录索引
private ArrayList&String& dataI
public String getAttrName() {
return attrN
public void setAttrName(String attrName) {
this.attrName = attrN
public int getNodeIndex() {
return nodeI
public void setNodeIndex(int nodeIndex) {
this.nodeIndex = nodeI
public double getAlpha() {
public void setAlpha(double alpha) {
this.alpha =
public String getParentAttrValue() {
return parentAttrV
public void setParentAttrValue(String parentAttrValue) {
this.parentAttrValue = parentAttrV
public TreeNode[] getChildAttrNode() {
return childAttrN
public void setChildAttrNode(TreeNode[] childAttrNode) {
this.childAttrNode = childAttrN
public ArrayList&String& getDataIndex() {
return dataI
public void setDataIndex(ArrayList&String& dataIndex) {
this.dataIndex = dataI
public int getLeafNum() {
return leafN
public void setLeafNum(int leafNum) {
this.leafNum = leafN
决策树类DecisionTree.java:
package DataMining_RandomF
import java.util.ArrayL
import java.util.HashM
import java.util.M
* @author lyq
public class DecisionTree {
// 树的根节点
TreeNode rootN
// 数据的属性列名称
String[] featureN
// 这棵树所包含的数据
ArrayList&String[]&
// 决策树构造的的工具类
public DecisionTree(ArrayList&String[]& datas) {
this.datas =
this.featureNames = datas.get(0);
tool = new CARTTool(datas);
// 通过CART工具类进行决策树的构建，并返回树的根节点
rootNode = tool.startBuildingTree();
* 根据给定的数据特征描述进行类别的判断
* @param features
public String decideClassType(String features) {
String classType = &&;
// 查询属性组
String[] queryF
// 在本决策树中对应的查询的属性值描述
ArrayList&String[]& featureS
featureStrs = new ArrayList&&();
queryFeatures = features.split(&,&);
for (String name : featureNames) {
for (String featureValue : queryFeatures) {
array = featureValue.split(&=&);
// 将对应的属性值加入到列表中
if (array[0].equals(name)) {
featureStrs.add(array);
// 开始从根据节点往下递归搜索
classType = recusiveSearchClassType(rootNode, featureStrs);
return classT
* 递归搜索树，查询属性的分类类别
* @param node
当前搜索到的节点
* @param remainFeatures
剩余未判断的属性
private String recusiveSearchClassType(TreeNode node,
ArrayList&String[]& remainFeatures) {
String classType =
// 如果节点包含了数据的id索引，说明已经分类到底了
if (node.getDataIndex() != null && node.getDataIndex().size() & 0) {
classType = judgeClassType(node.getDataIndex());
return classT
// 取出剩余属性中的一个匹配属性作为当前的判断属性名称
String[] currentFeature =
for (String[] featureValue : remainFeatures) {
if (node.getAttrName().equals(featureValue[0])) {
currentFeature = featureV
for (TreeNode childNode : node.getChildAttrNode()) {
// 寻找子节点中属于此属性值的分支
if (childNode.getParentAttrValue().equals(currentFeature[1])) {
remainFeatures.remove(currentFeature);
classType = recusiveSearchClassType(childNode, remainFeatures);
// 如果找到了分类结果，则直接挑出循环
//进行第二种情况的判断加上!符号的情况
String value = childNode.getParentAttrValue();
if(value.charAt(0) == '!'){
//去掉第一个！字符
value = value.substring(1, value.length());
if(!value.equals(currentFeature[1])){
remainFeatures.remove(currentFeature);
classType = recusiveSearchClassType(childNode, remainFeatures);
return classT
* 根据得到的数据行分类进行类别的决策
* @param dataIndex
根据分类的数据索引号
public String judgeClassType(ArrayList&String& dataIndex) {
// 结果类型值
String resultClassType = &&;
String classType = &&;
int count = 0;
int temp = 0;
Map&String, Integer& type2Num = new HashMap&String, Integer&();
for (String index : dataIndex) {
temp = Integer.parseInt(index);
// 取最后一列的决策类别数据
classType = datas.get(temp)[featureNames.length - 1];
if (type2Num.containsKey(classType)) {
// 如果类别已经存在，则使其计数加1
count = type2Num.get(classType);
count = 1;
type2Num.put(classType, count);
// 选出其中类别支持计数最多的一个类别值
count = -1;
for (Map.Entry entry : type2Num.entrySet()) {
if ((int) entry.getValue() & count) {
count = (int) entry.getValue();
resultClassType = (String) entry.getKey();
return resultClassT
随机森林算法工具类RandomForestTool.java:
package DataMining_RandomF
import java.io.BufferedR
import java.io.F
import java.io.FileR
import java.io.IOE
import java.util.ArrayL
import java.util.HashM
import java.util.M
import java.util.R
* 随机森林算法工具类
* @author lyq
public class RandomForestTool {
// 测试数据文件地址
private String fileP
// 决策树的样本占总数的占比率
private double sampleNumR
// 样本数据的采集特征数量占总特征的比例
private double featureNumR
// 决策树的采样样本数
private int sampleN
// 样本数据的采集采样特征数
private int featureN
// 随机森林中的决策树的数目,等于总的数据数/用于构造每棵树的数据的数量
private int treeN
// 随机数产生器
// 样本数据列属性名称行
private String[] featureN
// 原始的总的数据
private ArrayList&String[]& totalD
// 决策树森林
private ArrayList&DecisionTree& decisionF
public RandomForestTool(String filePath, double sampleNumRatio,
double featureNumRatio) {
this.filePath = fileP
this.sampleNumRatio = sampleNumR
this.featureNumRatio = featureNumR
readDataFile();
* 从文件中读取数据
private void readDataFile() {
File file = new File(filePath);
ArrayList&String[]& dataArray = new ArrayList&String[]&();
BufferedReader in = new BufferedReader(new FileReader(file));
String[] tempA
while ((str = in.readLine()) != null) {
tempArray = str.split(& &);
dataArray.add(tempArray);
in.close();
} catch (IOException e) {
e.getStackTrace();
totalDatas = dataA
featureNames = totalDatas.get(0);
sampleNum = (int) ((totalDatas.size() - 1) * sampleNumRatio);
//算属性数量的时候需要去掉id属性和决策属性，用条件属性计算
featureNum = (int) ((featureNames.length -2) * featureNumRatio);
// 算数量的时候需要去掉首行属性名称行
treeNum = (totalDatas.size() - 1) / sampleN
* 产生决策树
private DecisionTree produceDecisionTree() {
int temp = 0;
String[] tempD
//采样数据的随机行号组
ArrayList&Integer& sampleRandomN
//采样属性特征的随机列号组
ArrayList&Integer& featureRandomN
ArrayList&String[]&
sampleRandomNum = new ArrayList&&();
featureRandomNum = new ArrayList&&();
datas = new ArrayList&&();
for(int i=0; i&sampleN){
temp = random.nextInt(totalDatas.size());
//如果是行首属性名称行，则跳过
if(temp == 0){
if(!sampleRandomNum.contains(temp)){
sampleRandomNum.add(temp);
for(int i=0; i&featureN){
temp = random.nextInt(featureNames.length);
//如果是第一列的数据id号或者是决策属性列，则跳过
if(temp == 0 || temp == featureNames.length-1){
if(!featureRandomNum.contains(temp)){
featureRandomNum.add(temp);
String[] singleR
String[] headCulumn =
// 获取随机数据行
for(int dataIndex: sampleRandomNum){
singleRecord = totalDatas.get(dataIndex);
//每行的列数=所选的特征数+id号
tempData = new String[featureNum+2];
headCulumn = new String[featureNum+2];
for(int i=0,k=1; i&featureRandomNum.size(); i++,k++){
temp = featureRandomNum.get(i);
headCulumn[k] = featureNames[temp];
tempData[k] = singleRecord[temp];
//加上id列的信息
headCulumn[0] = featureNames[0];
//加上决策分类列的信息
headCulumn[featureNum+1] = featureNames[featureNames.length-1];
tempData[featureNum+1] = singleRecord[featureNames.length-1];
//加入此行数据
datas.add(tempData);
//加入行首列出现名称
datas.add(0, headCulumn);
//对筛选出的数据重新做id分配
for(String[] array: datas){
//从第2行开始赋值
if(temp & 0){
array[0] = temp + &&;
tree = new DecisionTree(datas);
* 构造随机森林
public void constructRandomTree() {
random = new Random();
decisionForest = new ArrayList&&();
System.out.println(&下面是随机森林中的决策树：&);
// 构造决策树加入森林中
for (int i = 0; i & treeN i++) {
System.out.println(&\n决策树& + (i+1));
tree = produceDecisionTree();
decisionForest.add(tree);
* 根据给定的属性条件进行类别的决策
* @param features
给定的已知的属性描述
public String judgeClassType(String features) {
// 结果类型值
String resultClassType = &&;
String classType = &&;
int count = 0;
Map&String, Integer& type2Num = new HashMap&String, Integer&();
for (DecisionTree tree : decisionForest) {
classType = tree.decideClassType(features);
if (type2Num.containsKey(classType)) {
// 如果类别已经存在，则使其计数加1
count = type2Num.get(classType);
count = 1;
type2Num.put(classType, count);
// 选出其中类别支持计数最多的一个类别值
count = -1;
for (Map.Entry entry : type2Num.entrySet()) {
if ((int) entry.getValue() & count) {
count = (int) entry.getValue();
resultClassType = (String) entry.getKey();
return resultClassT
CART算法工具类CARTTool.java：
package DataMining_RandomF
import java.util.ArrayL
import java.util.HashM
import java.util.LinkedL
import java.util.Q
* CART分类回归树算法工具类
* @author lyq
public class CARTTool {
// 类标号的值类型
private final String YES = &Yes&;
private final String NO = &No&;
// 所有属性的类型总数,在这里就是data源数据的列数
private int attrN
private String fileP
// 初始源数据，用一个二维字符数组存放模仿表格数据
private String[][]
// 数据的属性行的名字
private String[] attrN
// 每个属性的值所有类型
private HashMap&String, ArrayList&String&& attrV
public CARTTool(ArrayList&String[]& dataArray) {
attrValue = new HashMap&&();
readData(dataArray);
* 根据随机选取的样本数据进行初始化
* @param dataArray
* 已经读入的样本数据
public void readData(ArrayList&String[]& dataArray) {
data = new String[dataArray.size()][];
dataArray.toArray(data);
attrNum = data[0].
attrNames = data[0];
* 首先初始化每种属性的值的所有类型，用于后面的子类熵的计算时用
public void initAttrValue() {
ArrayList&String& tempV
// 按照列的方式，从左往右找
for (int j = 1; j & attrN j++) {
// 从一列中的上往下开始寻找值
tempValues = new ArrayList&&();
for (int i = 1; i & data. i++) {
if (!tempValues.contains(data[i][j])) {
// 如果这个属性的值没有添加过，则添加
tempValues.add(data[i][j]);
// 一列属性的值已经遍历完毕，复制到map属性表中
attrValue.put(data[0][j], tempValues);
* 计算机基尼指数
* @param remainData
* @param attrName
* @param value
* @param beLongValue
分类是否属于此属性值
public double computeGini(String[][] remainData, String attrName,
String value, boolean beLongValue) {
// 实例总数
int total = 0;
// 正实例数
int posNum = 0;
// 负实例数
int negNum = 0;
// 基尼指数
double gini = 0;
// 还是按列从左往右遍历属性
for (int j = 1; j & attrNames. j++) {
// 找到了指定的属性
if (attrName.equals(attrNames[j])) {
for (int i = 1; i & remainData. i++) {
// 统计正负实例按照属于和不属于值类型进行划分
if ((beLongValue && remainData[i][j].equals(value))
|| (!beLongValue && !remainData[i][j].equals(value))) {
if (remainData[i][attrNames.length - 1].equals(YES)) {
// 判断此行数据是否为正实例
total = posNum + negN
double posProbobly = (double) posNum /
double negProbobly = (double) negNum /
gini = 1 - posProbobly * posProbobly - negProbobly * negP
// 返回计算基尼指数
* 计算属性划分的最小基尼指数，返回最小的属性值划分和最小的基尼指数，保存在一个数组中
* @param remainData
* @param attrName
public String[] computeAttrGini(String[][] remainData, String attrName) {
String[] str = new String[2];
// 最终该属性的划分类型值
String spiltValue = &&;
// 临时变量
int tempNum = 0;
// 保存属性的值划分时的最小的基尼指数
double minGini = Integer.MAX_VALUE;
ArrayList&String& valueTypes = attrValue.get(attrName);
// 属于此属性值的实例数
HashMap&String, Integer& belongNum = new HashMap&&();
for (String string : valueTypes) {
// 重新计数的时候，数字归0
tempNum = 0;
// 按列从左往右遍历属性
for (int j = 1; j & attrNames. j++) {
// 找到了指定的属性
if (attrName.equals(attrNames[j])) {
for (int i = 1; i & remainData. i++) {
// 统计正负实例按照属于和不属于值类型进行划分
if (remainData[i][j].equals(string)) {
tempNum++;
belongNum.put(string, tempNum);
double tempGini = 0;
double posProbably = 1.0;
double negProbably = 1.0;
for (String string : valueTypes) {
tempGini = 0;
posProbably = 1.0 * belongNum.get(string) / (remainData.length - 1);
negProbably = 1 - posP
tempGini += posProbably
* computeGini(remainData, attrName, string, true);
tempGini += negProbably
* computeGini(remainData, attrName, string, false);
if (tempGini & minGini) {
minGini = tempG
spiltValue =
str[0] = spiltV
str[1] = minGini + &&;
public void buildDecisionTree(TreeNode node, String parentAttrValue,
String[][] remainData, ArrayList&String& remainAttr,
boolean beLongParentValue) {
// 属性划分值
String valueType = &&;
// 划分属性名称
String spiltAttrName = &&;
double minGini = Integer.MAX_VALUE;
double tempGini = 0;
// 基尼指数数组，保存了基尼指数和此基尼指数的划分属性值
String[] giniA
if (beLongParentValue) {
node.setParentAttrValue(parentAttrValue);
node.setParentAttrValue(&!& + parentAttrValue);
if (remainAttr.size() == 0) {
if (remainData.length & 1) {
ArrayList&String& indexArray = new ArrayList&&();
for (int i = 1; i & remainData. i++) {
indexArray.add(remainData[i][0]);
node.setDataIndex(indexArray);
// System.out.println(&attr remain null&);
for (String str : remainAttr) {
giniArray = computeAttrGini(remainData, str);
tempGini = Double.parseDouble(giniArray[1]);
if (tempGini & minGini) {
spiltAttrName =
minGini = tempG
valueType = giniArray[0];
// 移除划分属性
remainAttr.remove(spiltAttrName);
node.setAttrName(spiltAttrName);
// 孩子节点,分类回归树中，每次二元划分，分出2个孩子节点
TreeNode[] childNode = new TreeNode[2];
String[][] rD
boolean[] bArray = new boolean[] { true, false };
for (int i = 0; i & bArray. i++) {
// 二元划分属于属性值的划分
rData = removeData(remainData, spiltAttrName, valueType, bArray[i]);
boolean sameClass =
ArrayList&String& indexArray = new ArrayList&&();
for (int k = 1; k & rData. k++) {
indexArray.add(rData[k][0]);
// 判断是否为同一类的
if (!rData[k][attrNames.length - 1]
.equals(rData[1][attrNames.length - 1])) {
// 只要有1个不相等，就不是同类型的
sameClass =
childNode[i] = new TreeNode();
if (!sameClass) {
// 创建新的对象属性，对象的同个引用会出错
ArrayList&String& rAttr = new ArrayList&&();
for (String str : remainAttr) {
rAttr.add(str);
buildDecisionTree(childNode[i], valueType, rData, rAttr,
bArray[i]);
String pAtr = (bArray[i] ? valueType : &!& + valueType);
childNode[i].setParentAttrValue(pAtr);
childNode[i].setDataIndex(indexArray);
node.setChildAttrNode(childNode);
* 属性划分完毕，进行数据的移除
* @param srcData
* @param attrName
划分的属性名称
* @param valueType
属性的值类型
* @parame beLongValue 分类是否属于此值类型
private String[][] removeData(String[][] srcData, String attrName,
String valueType, boolean beLongValue) {
String[][] desDataA
ArrayList&String[]& desData = new ArrayList&&();
// 待删除数据
ArrayList&String[]& selectData = new ArrayList&&();
selectData.add(attrNames);
// 数组数据转化到列表中，方便移除
for (int i = 0; i & srcData. i++) {
desData.add(srcData[i]);
// 还是从左往右一列列的查找
for (int j = 1; j & attrNames. j++) {
if (attrNames[j].equals(attrName)) {
for (int i = 1; i & desData.size(); i++) {
if (desData.get(i)[j].equals(valueType)) {
// 如果匹配这个数据，则移除其他的数据
selectData.add(desData.get(i));
if (beLongValue) {
desDataArray = new String[selectData.size()][];
selectData.toArray(desDataArray);
// 属性名称行不移除
selectData.remove(attrNames);
// 如果是划分不属于此类型的数据时，进行移除
desData.removeAll(selectData);
desDataArray = new String[desData.size()][];
desData.toArray(desDataArray);
return desDataA
* 构造分类回归树，并返回根节点
public TreeNode startBuildingTree() {
initAttrValue();
ArrayList&String& remainAttr = new ArrayList&&();
// 添加属性，除了最后一个类标号属性
for (int i = 1; i & attrNames.length - 1; i++) {
remainAttr.add(attrNames[i]);
TreeNode rootNode = new TreeNode();
buildDecisionTree(rootNode, &&, data, remainAttr, false);
setIndexAndAlpah(rootNode, 0, false);
showDecisionTree(rootNode, 1);
return rootN
* 显示决策树
* @param node
待显示的节点
* @param blankNum
行空格符，用于显示树型结构
private void showDecisionTree(TreeNode node, int blankNum) {
System.out.println();
for (int i = 0; i & blankN i++) {
System.out.print(&
System.out.print(&--&);
// 显示分类的属性值
if (node.getParentAttrValue() != null
&& node.getParentAttrValue().length() & 0) {
System.out.print(node.getParentAttrValue());
System.out.print(&--&);
System.out.print(&--&);
if (node.getDataIndex() != null && node.getDataIndex().size() & 0) {
String i = node.getDataIndex().get(0);
System.out.print(&【& + node.getNodeIndex() + &】类别:&
+ data[Integer.parseInt(i)][attrNames.length - 1]);
System.out.print(&[&);
for (String index : node.getDataIndex()) {
System.out.print(index + &, &);
System.out.print(&]&);
// 递归显示子节点
System.out.print(&【& + node.getNodeIndex() + &:&
+ node.getAttrName() + &】&);
if (node.getChildAttrNode() != null) {
for (TreeNode childNode : node.getChildAttrNode()) {
showDecisionTree(childNode, 2 * blankNum);
System.out.print(&【
Child Null】&);
* 为节点设置序列号，并计算每个节点的误差率，用于后面剪枝
* @param node
开始的时候传入的是根节点
* @param index
开始的索引号，从1开始
* @param ifCutNode
是否需要剪枝
private void setIndexAndAlpah(TreeNode node, int index, boolean ifCutNode) {
TreeNode tempN
// 最小误差代价节点，即将被剪枝的节点
TreeNode minAlphaNode =
double minAlpah = Integer.MAX_VALUE;
Queue&TreeNode& nodeQueue = new LinkedList&TreeNode&();
nodeQueue.add(node);
while (nodeQueue.size() & 0) {
// 从队列头部获取首个节点
tempNode = nodeQueue.poll();
tempNode.setNodeIndex(index);
if (tempNode.getChildAttrNode() != null) {
for (TreeNode childNode : tempNode.getChildAttrNode()) {
nodeQueue.add(childNode);
computeAlpha(tempNode);
if (tempNode.getAlpha() & minAlpah) {
minAlphaNode = tempN
minAlpah = tempNode.getAlpha();
} else if (tempNode.getAlpha() == minAlpah) {
// 如果误差代价值一样，比较包含的叶子节点个数，剪枝有多叶子节点数的节点
if (tempNode.getLeafNum() & minAlphaNode.getLeafNum()) {
minAlphaNode = tempN
if (ifCutNode) {
// 进行树的剪枝，让其左右孩子节点为null
minAlphaNode.setChildAttrNode(null);
* 为非叶子节点计算误差代价，这里的后剪枝法用的是CCP代价复杂度剪枝
* @param node
待计算的非叶子节点
private void computeAlpha(TreeNode node) {
double rt = 0;
double Rt = 0;
double alpha = 0;
// 当前节点的数据总数
int sumNum = 0;
// 最少的偏差数
int minNum = 0;
ArrayList&String& dataI
ArrayList&TreeNode& leafNodes = new ArrayList&&();
addLeafNode(node, leafNodes);
node.setLeafNum(leafNodes.size());
for (TreeNode attrNode : leafNodes) {
dataIndex = attrNode.getDataIndex();
int num = 0;
sumNum += dataIndex.size();
for (String s : dataIndex) {
// 统计分类数据中的正负实例数
if (data[Integer.parseInt(s)][attrNames.length - 1].equals(YES)) {
// 取小数量的值部分
if (1.0 * num / dataIndex.size() & 0.5) {
num = dataIndex.size() -
rt += (1.0 * num / (data.length - 1));
//同样取出少偏差的那部分
if (1.0 * minNum / sumNum & 0.5) {
minNum = sumNum - minN
Rt = 1.0 * minNum / (data.length - 1);
alpha = 1.0 * (Rt - rt) / (leafNodes.size() - 1);
node.setAlpha(alpha);
* 筛选出节点所包含的叶子节点数
* @param node
待筛选节点
* @param leafNode
叶子节点列表容器
private void addLeafNode(TreeNode node, ArrayList&TreeNode& leafNode) {
ArrayList&String& dataI
if (node.getChildAttrNode() != null) {
for (TreeNode childNode : node.getChildAttrNode()) {
dataIndex = childNode.getDataIndex();
if (dataIndex != null && dataIndex.size() & 0) {
// 说明此节点为叶子节点
leafNode.add(childNode);
// 如果还是非叶子节点则继续递归调用
addLeafNode(childNode, leafNode);
测试类Client.java：
package DataMining_RandomF
import java.text.MessageF
* 随机森林算法测试场景
* @author lyq
public class Client {
public static void main(String[] args) {
String filePath = &C:\\Users\\lyq\\Desktop\\icon\\input.txt&;
String queryStr = &Age=Youth,Income=Low,Student=No,CreditRating=Fair&;
String resultClassType = &&;
// 决策树的样本占总数的占比率
double sampleNumRatio = 0.4;
// 样本数据的采集特征数量占总特征的比例
double featureNumRatio = 0.5;
RandomForestTool tool = new RandomForestTool(filePath, sampleNumRatio,
featureNumRatio);
tool.constructRandomTree();
resultClassType = tool.judgeClassType(queryStr);
System.out.println();
System.out
.println(MessageFormat.format(
&查询属性描述{0},预测的分类结果为BuysCompute:{1}&, queryStr,
resultClassType));
算法的输出
下面是随机森林中的决策树：
--!--【1:Income】
--Medium--【2】类别:Yes[1, 2, ]
--!Medium--【3:Student】
--No--【4】类别:No[3, 5, ]
--!No--【5】类别:Yes[4, ]
--!--【1:Student】
--No--【2】类别:No[1, 3, ]
--!No--【3】类别:Yes[2, 4, 5, ]
查询属性描述Age=Youth,Income=Low,Student=No,CreditRating=Fair,预测的分类结果为BuysCompute:No
输出的结果决策树建议从左往右看，从上往下，【】符号表示一个节点，---XX---表示属性值的划分，你就应该能看懂这棵树了，在console上想展示漂亮的树形效果的确很难。。。这里说一个算法的重大不足，数据太少，导致选择的样本数据不足，所选属性太少，，构造的决策树数量过少，自然分类的准确率不见得会有多准，博友只要能领会代码中所表达的算法的思想即可。
下面来说说随机森林的兄弟算法GBDT，梯度提升决策树，他有很多的决策树，他也有组合的思想，但是他不是随机森林算法2，GBDT的关键在于Gradient Boosting，梯度提升。这个词语理解起来就不容易了。学术的描述，每一次建立模型是在之前建立模型的损失函数的梯度下降方向。GBDT的核心在于，每一棵树学的是之前所有树结论和的残差，这个残差你可以理解为与预测值的差值。举个例子：比如预测张三的年龄，张三的真实年龄18岁，第一棵树预测张的年龄12岁，此时残差为18-12=6岁，因此在第二棵树中，我们把张的年龄作为6岁去学习，如果预测成功了，则张的真实年龄就是A树和B树的结果预测值的和，但是如果B预测成了5岁，那么残差就变成了6-5=1岁，那么此时需要构建第三树对1岁做预测，后面一样的道理。每棵树都是对之前失败预测的一个补充，用公式的表达就是如下的这个样子：
F0在这里是初始值，Ti是一棵棵的决策树，不同的问题选择不同的损失函数和初始值。在阿里内部对于此算法的叫法为TreeLink。所以下次听到什么Treelink算法了指的就是梯度提升树算法，其实我在这里省略了很大篇幅的数学推导过程，再加上自己还不是专家，无法彻底解释清数学的部分，所以就没有提及，希望以后有时间可以深入学习此方面的知识。}