决策树会有哪些特性？

决策树(Decision Tree)是机器学习中最常见的算法， 因为决策树的结果简单，容易理解， 因此应用超级广泛， 但是机器学习的专家们在设计决策树的时候会考虑哪些特性呢？

本文根据已有的决策树来分析， 一个想象中万能的决策树会有哪些变化？在这以前， 先总结下使用决策树的优缺点：

优缺点

优点：

• 天然的可解释性。 这是决策树最大的优点了。 可解释性有两方面的考虑。 一方面， 树结构的理解不需要机器学习专家来解读。 另一方面， 很容易转化成规则。
• 可以处理缺失值（missing）， 字符型（nominal）， 数值型（numeric）等数据类型。
• 非参数模型（non-parametric）。 没有复杂的参数设置，谁跑效果都相对一样。
• 对相关（Correlation）属性能够比较好的处理。
• 运算速度相对比较快。

缺点：

• 最大的缺点就是很容易过拟合。 导致实际预测的效果并不高。
• 决策树中，重复的部分过多难以概括， 譬如对于 ( F1 && F2 ) || ( F3 && F4 ) 的表达（如下图，划圈的部分重复）， 决策树就有很大的重复。
• 不适合处理高维数据， 当属性数量过大的时候， 部分决策树就不太适用了。
• 对异常值（Outlier）过于敏感， 很容易导致树的结构的巨大的变换。
• 泛化（Generalization）能力太差， 对于没有出现过的值几乎没有办法。

决策树们

CART (Classification and Regression Trees) ：

是Breiman 提出的一个二叉树， 采用贪心的递归分支方法进行生长。 CART不仅可以用来分类，也可以做回归。 在CART里面首次使用了Missing的替代划分（surrogate splits）的技巧。 CART树首先提出并使用了Variable Importance（VI）的概念， 这是个很牛的衡量属性特征权重的概念。需要注意的是VI是随着树的变化而变化的， 所以不同树之间的VI是不能相互比较的， 细节可以参考 （https://www.salford-systems.com/videos/tutorials/how-to/variable-importance-in-cart）。另外CART也是最早引入Cross Validation来进行Pruning的。

ID3 (Iterative Dichotomiser)：

是C4.5的一个早期版本， 因此在后面说明中不会提及。 ID3不能处理连续值， 没有剪枝， 不能处理缺失（Missing）。但是ID3提出了很好的Information Gain的框架。

C4.5：

是Quinlan提出的一系列算法的流传最广的一个。前续版本有ID3， 后续还有C5.0， 但是C5.0是商业版本的。 C4.5在ID3的基础上做了很多重大改进， 其中一个就是ID3不能处理连续数值的情况， 而C4.5通过阈值自动把连续变量分成两部分来处理。

AID (Automatic Interaction Detection) ：

是CHAID的早期版本，或者说一个更一般的方法， 因此在后面说明中不会提及。 AID首次提出利用F-Test来进行选择和划分，进而引入Interaction的概念。

CHAID (Chi-Squared Automatic Interaction Detection) ：

是AID的后续版本， 在认识的AID的偏差性后， 利用χ2-Test和F-Test结合的方式来选择属性，来降低偏差。 同时CHAID也意识到二叉树的复杂性， 运行多叉树合并产生更小的决策树。

FACT (Fast Algorithm for Classification Trees)：

是QUEST的一个早期版本， 因此在后面说明中不会提及。FACT讲符号的属性全部转换成数值型的， 然后，利用LDA（linear discriminant analysis）来将属性进行分割的。 它进行特征选择的时候， 利用ANOVA (analysis of variance)的F-Test， 优先选择最大的F Ratio的属性进行划分。

QUEST (Quick, Unbiased, Efficient, Statistical Tree)：

是FACT的后续版本， 并且将FACT的基于LDA（linear discriminant analysis）的划分， 修改成了基于QDA（quadratic discrimination analysis）的划分。 并且在特征选择的时候， 连续特征和FACT一样基于F-Test， 但是离散特征是基于χ2-Test的。 在QUEST中Missing处理比较简单，就是用插值（Imputation）。

CRUISE (Classification Rule with Unbiased Interaction Selection and Estimation)：

是QUEST的后续算法， 除了继承了QUEST的F-Test（连续值）和χ2-Test（离散值）的划分， 还引入了叫2D的特征划分方式。 2D的划分中， 两两属性之间都要进行5次测试（2次marginal tests和3次interaction tests）
并且划分也有改变， 先进行Box-Cox Transformation预处理， 再进行LDA划分。 另外还有一个重大改变是CRUISE经过Box-Cox变换后，可以将一个属性划分成多个分支（多叉树）。 CRUISE采用了CART树处理Missing的Surrogate Splitting办法。

GUIDE （Generalized, Unbiased, Interaction Detection and Estimation）：

GUIDE更像一个QUEST 和CART树的一个综合体的Bagging升级版。 它继承了QUEST和CRUISE的特征划分方式， 但是加入了Variable Importance的排序和按阈值选择部分特征集。 并且GUIDE和CART类似也可以用作Regression。 由于受到Random Forest成功的影响， GUIDE自带了Bagging的两种机制（Random Forest 和Extremely Randomized Trees）。 但是GUIDE里面Missing没有采用CART的方式， 而是把Missing看成一类特殊值，但是同时根据数据类型，具有插值的mean（连续型），或者是常量（符号型）。

MARS（Multivariate Adaptive Regression Splines）：

是Frieman提出的一个多变量回归的线性样板。 基于多个Hinge Function把不同变量的回归部分拼接起来。 因此来说， MARS与传统的树还是差异蛮大的，因此在后面说明中不会提及。 但是这个过程中Friedman应用了Stepwise Regression的思想。这或许是他后来提出Gradient Boosting方法的一个基础。

结构特征

既然是树，树是二叉还是多叉的呢？

二叉：CART， QUEST， GUIDE
二叉或者多叉：C4.5，CHAID， CRUISE

是一颗树还是多棵树？

多颗树：GUIDE (两种Bagging方式)

生长特征

在树生长过程中要判断按属性来分， 在这个过程有几个指标会带来变化。

参考一个属性还是多个属性进行划分？只支持一个属性还是支持多个属性？
一个属性： CART C4.5 CHAID QUEST CRUISE
多个属性： CART QUEST CRUISE

计算属性的什么值？ 信息增益（Information Gain）的计算方式？

Gini ： CART
Entropy： C4.5
Misclassification Error ： CART
F-Test / χ2-Test : QUEST CRUISE

是否对属性按重要性排序(Variable Importance)？

有重要性排序：CART GUIDE
没有重要性排序： C4.5 CHAID QUEST CRUISE

连续值如何划分？

Information Gain （Ratio） based Threshold： C4.5
Twoing Criteria （类似Information Gain）：CART
LDA/QDA based Threshold：QUEST CRUISE
Adjusted p value：CHAID

数据特征

是否能够处理Missing值？ 如果能， 是如何处理的？

不能处理: --
插值法（Imputation）： QUEST, CRUISE
替代法（Alternate/Surrogate Splits）：CART， CRUISE
缺失值单独分支（Missing value branch）：CHAID， GUIDE
概率权重（Probability weights）： C4.5

数值型和符号型（类别型）属性值是如何计算的？

阈值来划分连续型：CART， C4.5， CHAID
符号型变换成数值型：QUEST, CRUISE
连续型通过Box-Cox变换：GUIDE

正则化特征

剪枝（Pruning）是决策树正则化的最重要办法。

一个剪枝的方法是？

（Stopping rule）：CHAID
（Pre-pruning）：C4.5
（Cross-validation pruning）：CART QUEST CRUISE

剪枝参考值得计算方式？

Cost-Complexity Minimization　（standard misclassification cost vs number of leaves ）：　CART
Error-Based Pruning　（Wilson’s confidence intervals）：　C4.5
Maximum Depth: CHAID

Gini， Entropy， 和Misclassification Error的异同

这些都可以作为信息增益框架下的信息计算公式。 信息增益的框架如下：

他们的公式和曲线不一样：

Gini：

Entropy：

Missclassification Error：

根据公式衍生有如下不同：

Gini更适合连续数值变量， 而Entropy更适合符号型变量。
Gini降低最小误分率， 而Entropy具有更好的概率解释性。
Gini运算要比Entropy运算快。

但是根据实际运行情况：

Gini， Entropy， 和Misclassification Error 基本一致， 一般不超过2%的区别。