一。介绍

决策树是一种分类算法。它的算法思想是：根据单一特征对类别的重要性，将特征进行“排序”；然后分类的时候，用这些“排序”的特征，高效的分类。

二。算法步骤

1，特征选择

       首先，对于特征选择下面介绍三种最普通的方法，它们有许多共同之处，差别在于对某一特征重要性的度量不一样。

        前两者的度量跟熵有非常密切的关系，那么什么是熵呢？——熵是对不确定性的度量。对于一件事情，如果它是确定性事件，则熵为0；如果对于这件事情，每种可能出现的概率相同，则熵达到最大。具体的公式见上面。

        计算技巧：由于要计算的是信息增益最大，在划分前信息总量infobeforeSplit()一定的情况下，我们完全可以直接求划分后信息量最小的特性即可。

1.1 ID3

以信息增益为基础，进行特征选择。其思想是：对于某一个特征，在知道该特征后，根据类别的信息量减少的量，对特征进行排序。

1.2 C4.5

       如果某一个特征只含一个纯结点，这样决策树在选择属性时，将偏向于选择该属性，但这肯定是不正确（导致过拟合）的。因此有必要使用一种更好的方法，那就是C4.5中使用的信息增益率。

其考虑了分支数量和尺寸的因素，使用称为内在信息的概念。【1】

      内在信息，可简单地理解为表示信息分支所需要的信息量。

      实际上可以看出，属性的重要性会随着其内在信息（Intrinsic Information）的增大而减小。信息增益率作为一种补偿（Compensate）措施来解决信息增益所存在的问题，但是它也有可能导致过分补偿，而选择那些内在信息很小的属性，这一点可以尝试：首先，仅考虑那些信息增益超过平均值的属性，其次再比较信息增益。

1.3 CART

【2】

2，剪枝

        假如原本有1000个特征，在经过特征选择后，就是1000个特征的排序。但是实际上，后面的很多特征是没什么参考价值的，但是却还会影响分类的结果。所以要使用剪枝，来避免过拟合。

        剪枝分为预剪枝和后剪枝。预剪枝就是一边生成决策树一边将没用的枝剪掉；后剪枝是生成一整颗完整数之后再剪枝。

前者好处是效率高，坏处是没能从全局的角度来剪枝，容易导致剪枝过度；（该剪枝方法尽管不是统计有效的，但是在实践中有效。【2】）

后者的好处是从全局最优的思路下进行剪枝，坏处是效率低、数据量少时易过拟合。

2.1 预剪枝

在构造决策树的同时进行剪枝。所有决策树的构建方法，都是在无法进一步降低熵的情况下才会停止创建分支的过程，为了避免过拟合，可以设定一个阈值，熵减小的数量小于这个阈值，即使还可以继续降低熵，也停止继续创建分支。但是这种方法实际中的效果并不好。【3】

2.2 后剪枝

REP的步骤：

1，从底到顶，试着删除某一个节点下的子树，给该节点最大概率的分类；2，如果删除后没有降低总体的准确率，则删除该节点的子树。3，然后往树的跟节点方向继续删除，直到都不能删除。

其它如Minimum Error Pruning(MEP)，Critical Value Pruning(CVP)，Optimal Pruning(OPP)，Cost-Sensitive Decision Tree Pruning(CSDTP)、PEP等方法。【2】反正我没看，具体要用再看。

3，分类预测

通过上面的两步，已经确定了最终用于分类的决策树。或者你还在郁闷，有了这样的一颗树，又怎么进行分类呢？？

实际上，这棵树从根节点到叶子的每一根树枝都有一个概率，然后不断地往叶子方向计算其概率，就可以得到每个叶子下的概率，而叶子对应的就是类别。

三。优缺点

优点：这个算法总的来说，还是基于一定的统计学意义，结合信息量的知识（当然啦，像贝叶斯等其他分类算法也都有这两点，而且也很偏重这两点）进行分类。这类算法不涉及迭代优化等，所以计算复杂度不高，效率快。

这个算法其实也是有一个致命的缺点：只能对离散的特征进行处理，对连续特征效果不好（虽然连续的特征也能转变为离散的特征，但是决策树受这些处理的影响很大，分类效果就差了），此外，对于特征中离散值的个数也有一定的限制（其实主要是个数多了，每个值对应的数据量就少了），容易出现纯节点，影响特征选择的效果，最终影响分类的结果。

四。参考文章：

【1】http://blog.csdn.net/cyningsun/article/details/8735169

【2】数据挖掘十大经典算法 https://wizardforcel.gitbooks.io/dm-algo-top10/content/cart.html

【3】http://www.jianshu.com/p/794d08199e5e