本文主要介绍决策树的基本算法！决策树算法很简单，这个想法简单直接。但如果你有更深入的了解，内部的内容相当丰富，还有更多的细节。这一次，我使用了我最近审查的内容和我在访谈中遇到的一些问题，作为分析决策树中更深层次事项的线索。然后，我将完成决策树的算法，从决策树到随机森林，GBDT，XGBOOST。

        在决策树方面，我们首先想到的是分类树。这是决策树中使用最广泛的方面。这项工作很容易理解。我不打算在这里花很多时间，毕竟太简单的事情没有意义。我主要提到每个人都可能容易忽视的观点，而不是深思熟虑。为了澄清这些要点，一般的分类决策树不会有太大问题。
        分类决策树的核心思想是在数据集中找到最优特征，然后从该特征的选定值中找到最佳候选值（本段稍后解释），并根据以下内容划分数据集。最佳候选值。对于两个子数据集，然后递归上述操作，直到满足指定的条件。
以上段落是我的分类决策树的简要概述。有几点需要注意：

        1.最优特征怎么找？这个问题其实就是决策树的一个核心问题了。我们常用的方法是更具信息增益或者信息增益率来寻找最优特征，信息增益这东西怎么理解呢！搞清这个概念我们首先需要明白熵这个东西！熵简单的讲就是说我们做一件事需要的代价，代价越高肯定就越不好了。放到机器学习的数据集中来讲就是我们数据的不确定性，代价越高对应的不确定就越高，我们用决策树算法的目的就是利用数据的一些规则来尽可能的降低数据集的不确定性。好了，有了这个思想我们要做的事就很简单了，给定一批数据集，我们可以很容易得到它的不确定性(熵)，然后呢！我们要想办法降低这个不确定性，我们需要挖掘数据集中有用的特征，在某个特征的限制下，我们又能得到数据集的不确定性（这个其实就是书上的条件熵），一般而言给定了一个有用的特征，数据的不确定性肯定降低了(因为有一个条件约束，比没有条件约束效果肯定会好一点，当然你的特征没有用，那就另说了)。我们用两次的值作差，这个结果的含义很明了，给定了这个特征，让我们数据集的不确定性降低了多少，当然降低的越多这个特征肯定就越好了。而我们讲了这么多就是要找到那一个让数据集不确定性降低最多的特征。我们认为这个特征是当前特征中最好的一个。
        2.我们找到了最优特征，为什么还要找最优特征的最优候选值？其实呀，找不找主要看我们面对的问题，一般的二分类问题确实没必要找(因为总共就两个类)，但对于多分类问题，这个还是建议找，为什么要找呢？我们来分析一下：假如我们的某个最优特征有三个类别：我们如果不找就直接分为三个子节点了。这样会出现一个问题，就是我们的这个分类对特征值会变得敏感，为什么这么说，我们来讲一个很简答的例子：我们平时考试规定了60分及格，这个控制对于大多数学生很好把控，因为就一个条件，相当于一个二分类。但是如果我们把条件控制严格一些，比如超过60分，不超过80分为优秀学生(当然有点扯蛋了)。这个控制很多学霸就不好控制了，对于多分类问题也是这个道理，如果我们一下子从父节点直接分了多个子节点，那么我们的数据肯定会对这个控制很敏感，敏感就会导致出错。出错不是我们希望看到的，所以我们建议对多分类问题找最优候选值来转化为二分类问题，同样多个二分类问题其实也是一个多分类问题，只是多了几个递归过程而已。
        3.什么时候停止？停止条件是什么？这个问题其实书上也讲得很简单，基本都是一笔带过的，我来稍微详细说一下：我们从问题的根源出发去想一下，我们构造一颗决策树的目的是什么？当然是为了能在数据集上取得最好的分类效果，很好这就是一个停止标准呀！当我们检测到数据的分类效果已经够好了，我们其实就可以停止了。当然我们常用的是控制叶节点，比如控制叶节点的样本数目，比如当某个子节点内样本数目小于某一个指定值，我们就决定不再分了。还有叶节点的纯度，我们规定叶节点样本必须属于同一类才停止，这也是一个停止条件。还有最大树的深度，比如我们规定树的最大深度为某一个值，当树深度到达这个值我们也要停止。还有比如：分裂次数，最大特征数等等。总之停止条件不是死的，我们可以更具自己的问题来随意控制，开心就好！
讲完上面几个问题，基本分类决策树的思想应该差不多了。这里为了阅读方便我还是帖几个公式仅供参考：熵：$entropy(D) = -\sum_{i=1}^n P_ilog_2 P_i$
其中D为数据集，i为数据集D的可能分类标签,$P_i$为该标签的概率
条件熵：$entropy(D,A) = \sum_{i=1}^k \frac {D_{A_i}}{D} log_2D_{A_i}$
其中A表示约束特征，k表示A特征的种类
信息增益:$gain(D,A) = entropy(D) - entropy(D,A)$
信息增益率： $gain_rate(D,A) = gain(D,A)/entropy(D,A)$

        在这里，我们简要介绍最基本的决策树，并详细解释一些可能无法理解的要点。当然，很多人认为决策树几乎是一样的。实际上，决策树的想法就是这么简单，但下一个内容是决策树的核心。首先介绍两个决策树的核心算法ID3和C4.5。
ID3算法实际上是我们通常理解的决策树算法。基本步骤是我们上面提到的步骤。该算法的核心思想是使用信息增益来选择最优分类特征。上面还给出了信息增益的公式。我们仔细分析了这个公式，我们会发现一个问题：我们需要找到最大的增益特征（D，A）。对于数据集，给出了熵（D），也就是说，我们需要熵（D，A）是最小的。意思是我们选择的特征是分裂后具有最高纯度的子节点的特征。在划分特征之后，子节点的特征纯度相对较高（熵相对较小），并且特征的子类别很多。很多这种类型的功能。总而言之，信息增益偏向于具有许多子类的特征。这也是该算法的致命缺陷。任何具有主观偏差的算法都不是一个好的算法。当然，ID3算法的另一个缺点是显而易见的。它只能处理这些分类的功能。方法（事实上，我们可以人为地离散连续属性，但人为地不可避免地导致不准确）。所以有以下算法
C4.5是对ID3算法的改进。主要的改进是解决ID3的几个缺点。首先，C4.5算法使用信息增益率而不是ID3中的信息增益。从表达式可以看出，这样做实际上削弱了这些偏见，并使选择最佳功能更公平。
此外，C4.5的改进是它可以处理连续值（这种方法类似于上面提到的连续值离散化，可以理解为单点离散化）。具体步骤如下：

       1.首先对于连续值属性的值进行排序(A1,A2......An);
       2.我们可以在每两个值之间取一个点，用这个点就可以把该组连续值分为两部分，比如我们去一个点a1($A1
       3.缺失值的处理，ID3不能直接处理(需要我们人工处理，比如单独赋值或赋一个平均值)，C4.5给出了一种非常优雅的方式，为什么它优雅，让我们来谈谈吧！我们的每个功能都有许多值。训练集的每个可能值都有可能。我们用这个概率来表明这确实是值得的。这使得它非常合理。 C4.5在所有方面都赢得了ID3，所以C4.5一出现就被广泛使用。后来，为了解决该算法的时间开销，引入了C5.0的改进版本。有一个国外博客比较C4.5和C5.0的表现非常好，可以搜索。一般来说，C5.0的速度是C4.5的10倍以上。
我们谈了很多，以至于我们没有逃过分类树。我们仍然有一个我们没有谈论的大问题，那就是回归。这里我们讨论的是回归树。回归树时，我们不禁提到着名的CART（分类和回归树）树。这是核心决策树。为什么这么说呢，因为我们将来使用的随机森林，gbdt和xgboost中的基本估算器是一个CART树。所以我会认真谈论这件事。

        CART树可用于分类问题也可以用于回归问题，对问题进行分类的想法是我们上面介绍的ID3、C4.5相同，唯一的区别在于CART树使用基尼指数来决定最佳的分割点。基尼指数:$gini(D)=sum_{i=1}^np_k(1-p_k)$基尼指数的一般解释表示事物的不确定性,并且基尼指数越大,越有不确定性越高。首先简单记述决策树处理的回归问题的流程：对于1个数据集，m个子区间（R1，R2．．．．。对于每个Rm），每个区间都可以进行1个对应。输出cm.最终输出$f(x)=sum_{i=1}^mc_mI(xinR)每单位的损失$sum_{x_iinR_m}(y_i-f(x_i))^2$表示对于给定回归树的平方误差，每个单元的最优输出是单元损失的函数最小。每个单元格的最终输出为。$C=avg(y_i|x_i)(x_iinR_m)$（区间$R_m$上的所有$x_i$的输出$y_i）$的平均值是回归问题，问题是如何确定拆分点（决策），CART树的处理方式是C4。在5中与处理连续变量的方式有些相似，即对于每个特征的值，从其中寻找1个点j，这一点j可以将其特征分为2个部分＄R＿1＠（｛x｜x）。＠equation＿0＠。我们的目标是拆分后丢失语句的最小值：$$min{min(y_i-c_i)^2(x_iinR_1)min(y_i-c_i)^2(x_iin)R_2)$$，可以将此特征的所有值循环一次，然后查找一个。将上式最小化的j，将该j作为最佳的分割点，对应的特征是最适合的特征，将数据集分为2个部分的回归进行递归，在这里，使用决策树在每个步骤中找出最佳的分割点时，一般使用贪婪算法，在贪婪算法中存在问题是局部最佳的。确定树在选择特征和分割点时需要注意的一个站部的最佳问题。上面是决定树最常用的3个算法，分类树和回归树这2个古典的算法ID3和C4.5，下面介绍了回归树CART树，并且，CART树作为现在主流的决策树被广泛使用。