决策树学习的三个步骤：特征选择、决策树的生成和决策树的修剪。其本质上是从训练数据集中归纳出一组分类规则。决策树算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子集由一个最好的分类结果，这一过程对应着对特征空间的划分，也对应着决策树的构建。开始将所有训练数据都放在根节点，选择一个最优特征，按照该特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类，如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点。如此递归下去，直到所有的训练数据子集被基本正确分类，或者没有合适特征为止。

    决策树常用的算法有ID3、C4.5和CART.

    （1）ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点。

        缺点：没有考虑连续特征；用信息增益作为标准容易偏向于取值较多的特征；对于缺失值的情况没有考虑；没有考虑过拟合的情况；

    （2）C4.5改进了ID3的缺点

        对于问题一：C4.5的思路是将连续的特征离散化，C4.5取相邻两样本值的中位数，一共取得m-1个划分点。

        对于问题二：信息增益作为标准容易偏向于取值较多的特征的问题，引入一个信息增益比的变量IR(X,Y)，它是信息增益和特征熵的比值。特征数越多的特征对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。

        对于问题三：缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。

        对于问题四：C4.5引入了正则化系数进行初步的剪枝。

    （3）CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。CART分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树。这样一可以进一步简化基尼系数的计算，二可以建立一个更加优雅的二叉树模型。

优点：模型具有可读性，分类速度快，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。

    （1）简单直观，生成的决策树很直观。

    （2）基本不需要预处理，不需要提前归一化，处理缺失值。

    （3）使用决策树预测的代价是O(log2m)。 m为样本数。

    （4）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。

    （5）可以处理多维度输出的分类问题。

    （6）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释。

    （7）可以交叉验证的剪枝来选择模型，从而提高泛化能力。

    （8）对于异常点的容错能力好，健壮性高。

缺点：可能会产生过渡匹配问题。

    （1）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。

    （2）决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。

    （3）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。

    （4）有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。

    （5）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。