决策树简介决策树是机器学习中非常常用的一种分类方法，也可以说是所有算法中最直观、最容易理解的算法。先举个最简单的例子：A：你要吃饭吗？B：你去，我就去。“你去，我就去”，这是典型的决策树思维。又如：有人找我借钱（当然不太可能……），我借还是不借？我会结合自己有没有钱，是否需要钱，对方信用好不好这三个特点。决定我的答案。让我们转向更普遍的观点。对于一些特征数据，如果我们能有这样一棵决策树，我们就可以很容易地预测出样本的结论。于是问题转化为如何找到合适的决策树，即如何对这些特征进行排序。在对特征进行排序之前，想象一下，在对某个特征进行决策时，肯定希望分类样本的纯度越高越好，也就是说分支节点的样本属于同一类的越多越好尽可能。因此，在选择根节点时，我们应该选择能使“分支节点纯度最高”的特征。根节点处理完之后，对于它的分支节点，继续应用根节点的思想不断递归，这样就可以形成一棵树。这其实就是贪心算法的基本思想。那么如何量化“最高纯度”呢？熵是衡量纯度最常用的指标。其数学表达式如下：其中N表示结论有多少个可能值，p表示取第k个值时出现的概率，对于样本，是出现的频率/总次数。熵越小，样品越纯。让我们用两点分布样本X（x=0或1）的熵函数图像来说明它。横坐标表示样本值为1的概率，纵坐标表示熵。可以看出，当p(x=1)=0时，即所有样本均为0，熵为0。当p(x=1)=1时，即所有样本均为1，熵也为0。当p(x=1)=0.5时，即样本中0和1各占一半，此时熵可以达到最大值。展开一下，样本X可能取n个值（x1...xn）。可以证明，当p(xi)等于1/n时，即样本绝对均匀，熵可以达到最大。当p(xi)其中一个为1，其他为0时，即样本值都是xi，熵最小。决策树算法ID3假设在样本集X中，对于一个特征a，它可能有(a1,a2...an)这些值，如果用特征a来划分样本集X（将其作为根节点），必须有n个分支节点。刚才说了，我们希望划分之后，分支节点的样本越纯越好，也就是分支节点的“总熵”越小越好。因为每个分支的节点数不同，所以我们在计算“总熵”的时候应该做一个加权。假设第i个节点的样本数为W(ai)，其在所有样本中的权重为W(ai)/W(X)。所以我们可以得到一个总熵：这个公式用一句话表达的意思：加权后各节点的熵之和。这个值应该越小，纯度越高。这时候我们引入一个术语叫做信息增益G(X,a)，意思是特征a给样本带来的信息的提升。公式为：由于H(X)对于一个样本是固定值，信息增益G应该尽可能的大。找到使信息增益最大化的特征作为目标节点，逐步递归构建树。这就是ID3算法的思路。举一个简单的例子来说明信息增益的计算：在上面的例子中，我在计算特征1的信息增益时先计算样本的熵H(X)，然后再计算总熵。可以看出特征1有3个节点A、B、C，分别为6、6、5，所以A的权重为6/（6+6+5），B的权重为6/(6+6+5)，而C的权重为5/(6+6+5)因为我们希望划分的节点纯度越高越好，所以还需要计算熵特征1=A节点A、B、C分别为：3是，3否，熵为特征1=B：2是，4否，熵为特征1=C：4是，1否，其熵是这样的即分支节点的总熵等于：特征1的信息增益等于0.998-0.889=0.109同理，我们还可以计算其他特征的信息增益，最后取信息增益最大的特征作为根节点。上面的计算也可以用经验条件熵推导：G(X,A)=H(X)-H(X|A)，有兴趣的同学可以了解这部分。C4.5其实在ID3算法上有一个明显的问题。如果有一个样本集具有称为id或name的（唯一）特征，则结束。想象一下，如果有n个样本，id特征肯定会将样本分成n份，即有n个节点，每个节点只有一个值，每个节点的熵为0。也就是说，所有分支节点的总熵为0，则该特征的信息增益必然达到最大值。所以此时如果使用ID3作为决策树算法，根节点一定是id的特征。但显然这是不合理的。..当然，以上是极限情况。一般来说，如果一个特征对于样本划分来说过于稀疏，这也是不合理的（换句话说，它偏向于具有更多值的特征）。为了解决这个问题，C4.5算法采用信息增益率作为特征选择准则。所谓信息增益率，就是根据除一项拆分信息外的信息增益，对取值较多的属性进行惩罚。而这个分割信息其实就是特征个数的熵H(A)。为什么这个可以减少？拿上面id的例子来理解。如果id把n个样本分成n份，那么id特征取值的概率就是1/n。文章引言中提到，当样本绝对均匀时，熵最大。所以，这种情况下，以id为特征，虽然信息增益最大，但是惩罚因子分裂信息也最大，从而降低增益率，这就是C4.5的思路。CART决策树的目的最终是为了找到一个区分样品纯度的定量标准。在CART决策树中，以基尼指数作为其衡量标准。基尼系数直观的理解就是从集合中随机抽取两个样本。样本集越纯，得到不同样本的概率就越小。这个概率反映了基尼系数。所以如果一个样本有K个类别。假设样本的某个特征a有n个值，则某个节点取不同样本的概率为：因此，k个类别的概率之和称为基尼系数；而基尼指数是对所有节点的基尼系数进行加权计算后，我们会选择基尼系数最小的特征作为最优划分特征。剪枝剪枝的目的其实就是为了防止过拟合，这是决策树防止过拟合最重要的手段。在决策树中，为了尽量对训练样本进行分类，我们的决策树会一直增长。然而，有时训练样本可能学习得很好，以至于某些样本的独特属性被视为一般属性。这时候我们就需要主动去掉一些分支来降低过拟合的风险。剪枝一般有两种方式：预剪枝和后剪枝。预剪枝一般情况下，直到节点样本达到100%纯时，树才会停止生长。但是这样可能会造成过拟合，所以我们不需要让它增长到100%，所以在此之前，设置一些终止条件让它提前终止。这称为预剪枝，这个过程发生在决策树生成之前。一般我们的预剪枝方法有：1.限制树的深度2.一个节点的子节点数小于阈值3.设置节点熵的阈值等等。后剪枝顾名思义，这种剪枝是在决策树构建过程之后进行的。有很多后剪枝算法，其中一些算法非常深奥。这里提一个简单的算法思路，就不赘述了。Reduced-ErrorPruning(REP)这种剪枝方法将树上的每个节点都视为剪枝的候选者，但是有一些条件决定是否剪枝，通常有以下步骤：1.删除它的所有子树，使其成为一棵叶节点。2.将最相关的类别分配给节点。3、使用验证数据验证其精度不比处理前差，然后删除其子树。然后从下往上反复处理节点。这种处理方式其实就是对付那些“有害”的节点。随机森林随机森林的理论不应该涉及决策树本身。决策树只能作为其思维的一种算法。为什么要引入随机森林。我们知道，同一批数据，只能生成一棵决策树，这个改动比较简单。多种算法的组合呢？这就有了综合学习的概念。从图中可以看出，每个单独的学习器（弱学习器）都可以包含一个算法，算法可以相同也可以不同。如果它们相同，我们称它为同构集成，否则它是异构的。随机森林是使用基于装袋策略的集成学习的一个特例。从上图可以看出，bagging的individuallearner的训练集是通过随机抽样得到的。通过n次随机抽样，可以得到n个样本集。对于这n个样本集，我们可以独立训练n个个体学习器，然后使用集合策略得到这n个个体学习器的最终输出。这n个个体学习器彼此独立。可以并行化。注意：还有另一种集成学习方式称为提升。以这种方式，学习者之间存在很强的相关性。有兴趣的可以了解一下。随机森林采用的采样方式一般是Bootstap采样。对于原来的样本集，我们每次随机抽取一个样本放入抽样集中，然后再放回去，也就是说下一次抽样的时候可能还会抽到这个样本。一定数量的样本后得到一个样本集。由于随机抽样，每个抽样集不同于原始样本集，也不同于其他抽样集，因此得到的个体学习器也不同。随机森林的主要问题是当有n个结果时如何设置组合策略。主要有以下几种方法：加权平均法：平均法常用于回归。其方法是先给每个学习器预先设定一个权重wi，然后最后的输出是：当学习器的权重都为1/n时，这种平均法称为简单平均法。投票方式：投票方式类似于我们生活中的投票，如果每个学习者的权重相同。然后是绝对投票法，即超过半数的选票。与表决法相比，少数服从多数。如果有加权的话，少数还是服从于多数，但是这里的数字是有加权的。我们以一个简单的二次函数代码为例，看看如何使用决策树。训练数据为100个随机实方块数据。不同的深度会产生不同的曲线。测试数据也是随机数据，但是不同深度的树模型产生的预测值也不同。如图，代码如下：我的环境是python3.6，需要安装numpy、matplotlib、sklearn这三个库。#!/usr/bin/python#-*-coding:utf-8-*-importnumpyasnpimportmatplotlibasmplimportmatplotlib.pyplotaspltfromsklearn.treeimportDecisionTreeRegressorif__name__=="__main__":#准备训练数据N=100x=np.random.rand(N)*6-3x.sort()y=x*xx=x.reshape(-1,1)mpl.rcParams['font.sans-serif']=['SimHei']mpl.rcParams['axes.unicode_minus']=False#决策树深度及其曲线颜色depth=[2,4,6,8,10]clr='rgbmy'#实际值plt.figure(facecolor='w')plt.plot(x,y,'ro',ms=5,mec='k',label='actualvalue')#准备测试数据x_test=np.linspace(-3,3,50).reshape(-1,1)#构建决策树dtr=DecisionTreeRegressor()#在不同深度循环决策树的模型，用它来测试数据的输出.fit(x,y)#用训练数据得到的模型来验证测试数据y_hat=dtr.predict(x_test)#绘制模型得到的曲线plt.plot(x_test,y_hat,'-',color=c,linewidth=2,markeredgecolor='k',label='Depth=%d'%d)#Some绘图基本参数plt.legend(loc='uppercenter',fontsize=12)plt.xlabel('X')plt.ylabel('Y')plt.grid(b=True,ls=':',color='#606060')plt.title('二次函数决策树',fontsize=15)plt.tight_layout(2)plt.show()原文链接：https://www.qcloud.com/community/article/160232作者：王一雄【本文为专栏作者《腾讯云技术社区》原创稿件，转载请联系原作者获得授权】点此查看更多本站好文章作者
