目前,最常用的3种决策树算法分别是CHAID、CART和ID3(包括后来的C4.5,乃至C5.0)。
CHAID(Chi-square Automatic Interaction Detector)算法的历史较长,中文简称为卡方自动相互关系检测。CHAID依据局部最优原则,利用卡方检验来选择对因变量最有影响的自变量,CHAID应用的前提是因变量为类别型变量(Category)。
CART(Classification and Regression Tree)算法产生于20世纪80年代中期,中文简称为分类与回归树,CART的分割逻辑与CHAID相同,每一层的划分都是基于对所有自变量的检验和选择上的。但是,CART采用的检验标准不是卡方检验,而是基尼系数(Gini)等不纯度的指标。两者最大的区别在于CHAID采用的是局部最优原则,即结点之间互不相干,一个结点确定了之后,下面的生长过程完全在结点内进行。而CART则着眼于总体优化,即先让树尽可能地生长,然后再回过头来对树进行修剪(Prune),这一点非常类似统计分析中回归算法里的反向选择(Backward Selection)。CART所生产的决策树是二分的,每个结点只能分出两枝,并且在树的生长过程中,同一个自变量可以反复使用多次(分割),这些都是不同于CHAID的特点。另外,如果是自变量存在数据缺失(Missing)的情况,CART的处理方式将会是寻找一个替代数据来代替(填充)缺失值,而CHAID则是把缺失数值作为单独的一类数值。
ID3(Iterative Dichotomiser)算法与CART是同一时期产生的,中文简称为迭代的二分器,其最大的特点在于自变量的挑选标准是:基于信息增益的度量选择具有最高信息增益的属性作为结点的分裂(分割)属性,其结果就是对分割后的结点进行分类所需的信息量最小,这也是一种划分纯度的思想。至于之后发展起来的C4.5可以理解为ID3的发展版(后继版),两者的主要区别在于C4.5采用信息增益率(Gain Ratio)代替了ID3中的信息增益度量,如此替换的主要原因是信息增益度量有个缺点,就是倾向于选择具有大量值的属性。这里给个极端的例子,对于Member_Id的划分,每个Id都是一个最纯的组,但是这样的划分没有任何实际意义。而C4.5所采用的信息增益率就可以较好地克服这个缺点,它在信息增益的基础上,增加了一个分裂信息(SplitInformation)对其进行规范化约束。