10.2 决策树技术的实践应用和注意事项

决策树模型是数据挖掘应用中常见的一种成熟技术,因其输出规则让人容易理解而备受数据分析师和业务应用方的喜欢和推崇。自从1960年Hunt等人提出概念学习系统框架方法(Concept Learning System Framework,CLSF)以来,决策树多种算法一直在不断发展、成熟,目前最常用的3种决策树算法分别是CHAID、CART和ID3,包括后来的C4.5,乃至C5.0。

决策树,顾名思义,其建模过程类似一棵树的成长,从根部开始,到树干,到分叉,到继续细枝末节的分叉,最终到一片片的树叶。在决策树里,所分析的数据样本形成一个树根,经过层层分枝,最终形成若干个结点,每个结点代表一个结论。从决策树的根部到叶结点的一条路径就形成了对相应对象的类别预测。

10.2.1 决策树的原理和核心要素

构造决策树采用的是自顶向下的贪婪算法,它会在每个结点选择分类效果最好的属性对样本进行分类,然后继续这个过程,直到这棵树能准确地分类训练样本,或者所有的属性都已被用过。

决策树算法的核心是在对每个结点进行测试后,选择最佳的属性,并且对决策树进行剪枝处理。

最常见的结点属性选择方法(标准)有信息增益、信息增益率、Gini指数、卡方检验(Chi-Square Statistics)等。在10.2.2~10.2.4节将对它们分别进行介绍。

决策树的剪枝处理包括两种方式:先剪枝(Prepruning)和后剪枝(Postpruning)。

所谓先剪枝,就是决策树生长之前,就人为定好树的层数,以及每个结点所允许的最少的样本数量等,而且在给定的结点不再分裂。

所谓后剪枝,是让树先充分生长,然后剪去子树,删除结点的分枝并用树叶替换。后剪枝的方法更常用。CART算法就包含了后剪枝方法,它使用的是代价复杂度剪枝算法,即将树的代价复杂度看做是树中树叶结点的个数和树的错误率的函数。C4.5使用的是悲观剪枝方法,类似于代价复杂度剪枝算法。

10.2.2 CHAID算法

CHAID(Chi-Square Automatic Interaction Detector)算法历史较长,中文简称为卡方自动相互关系检测。CHAID是依据局部最优原则,利用卡方检验来选择对因变量最有影响的自变量的,CHAID应用的前提是因变量为类别型变量(Category)。

关于卡方检验的具体公式和原理,此处从略,详情可参考本书8.6.5节。

关于CHAID算法的逻辑,简述如下。

首先,对所有自变量进行逐一检测,利用卡方检验确定每个自变量和因变量之间的关系。具体来说,就是在检验时,每次从自变量里抽取两个既定值,与因变量进行卡方检验。如果卡方检验显示两者关系不显著,则证明上述两个既定值可以合并。如此,合并过程将会不断减少自变量的取值数量,直到该自变量的所有取值都呈现显著性为止。在对每个自变量进行类似处理后,通过比较找出最显著的自变量,并按自变量最终取值对样本进行分割,形成若干个新的生长结点。

然后,CHAID在每个新结点上,重复上述步骤,对每个新结点重新进行最佳自变量挑选。整个过程不断重复,直到每个结点无法再找到一个与因变量有统计显著性的自变量对其进行分割为止,或者之前限度的条件得到满足,树的生长就此终止。

卡方检验适用于类别型变量的检验,如果自变量是区间型的变量(Interval),CHAID改用F检验。

10.2.3 CART算法

CART(Classification and Regression Trees)算法发明于20世纪80年代中期,中文简称分类与回归树。CART的分割逻辑与CHAID相同,每一层的划分都是基于对所有自变量的检验和选择。但是,CART采用的检验标准不是卡方检验,而是Gini(基尼系数)等不纯度指标。两者最大的不同在于CHAID采用的是局部最优原则,即结点之间互不相干,一个结点确定了之后,下面的生长过程完全在结点内进行。而CART则着眼于总体优化,即先让树尽可能地生长,然后再回过头来对树进行修剪(Prune),这一点非常类似统计分析中回归算法里的反向选择(Backward Selection)。CART所生产的决策树是二分的,即每个结点只能分出两枝,并且在树的生长过程中,同一个自变量可以反复多次使用(分割),这些都是不同于CHAID的特点。另外,如果自变量存在数据缺失(Missing)的情况,CART的处理方式是寻找一个替代数据来代替(或填充)缺失值,而CHAID则是把缺失数值作为单独的一类数值。

10.2.4 ID3算法

ID3(Iterative Dichotomiser)与CART发明于同一时期,中文简称迭代的二分器,其最大的特点在于自变量的挑选标准是基于信息增益度量的,即选择具有最高信息增益的属性作为结点的分裂(或分割)属性,这样一来,分割后的结点里分类所需的信息量就会最小,这也是一种划分纯度的思想。至于C4.5,可以将其理解为ID3的发展版本(后继版),主要区别在于C4.5用信息增益率(Gain Ratio)代替了ID3中的信息增益,主要的原因是使用信息增益度量有个缺点,就是倾向于选择具有大量值的属性,极端的例子,如对于Member_id的划分,每个Id都是一个最纯的组,但是这样的划分没有任何实际意义,而C4.5所采用的信息增益率就可以较好地克服这个缺点,它在信息增益的基础上,增加了一个分裂信息(Split Information)对其进行规范化约束。

10.2.5 决策树的应用优势

在数据挖掘的实践应用中,决策树体现了如下明显的优势和竞争力:

❑决策树模型非常直观,生成的一系列“如果……那么……”的逻辑判断很容易让人理解和应用。这个特点是决策树赢得广泛应用的最主要原因,真正体现了简单、直观、通俗、易懂。

❑决策树搭建和应用的速度比较快,并且可以处理区间型变量(Interval)和类别型变量(Category)。但是要强调的是“可以处理区间型变量”不代表“快速处理区间型变量”,如果输入变量只是类别型或次序型变量,决策树的搭建速度是很快的,但如果加上了区间型变量,视数据规模,其模型搭建速度可能会有所不同。

❑决策树对于数据的分布没有特别严格的要求。

❑对缺失值(Missing Value)很宽容,几乎不做任何处理就可以应用。

❑不容易受数据中极端值(异常值)的影响。

❑可以同时对付数据中线性和非线性的关系。

❑决策树通常还可以作为有效工具来帮助其他模型算法挑选自变量。决策树不仅本身对于数据的前期处理和清洗没有什么特别的要求和限制,它还会有效帮助别的模型算法去挑选自变量,因为决策树算法里结点的自变量选择方法完全适用于其他算法模型,包括卡方检验、Gini指数、信息增益等。

❑决策树算法使用信息原理对大样本的属性进行信息量分析,并计算各属性的信息量,找出反映类别的重要属性,可准确、高效地发现哪些属性对分类最有意义。这一点,对于区间型变量的分箱操作来说,意义非常重大。关于分箱操作,请参考本书8.5.3节。

10.2.6 决策树的缺点和注意事项

事物都是具有两面性的,有缺点不可怕,关键在于如何扬长避短,数据分析师不仅要清楚知道决策树的缺点,更需要掌握相应的注意事项,才可能取长补短,达到事半功倍的效果。

❑决策树最大的缺点是其原理中的贪心算法。贪心算法总是做出在当前看来最好的选择,却并不从整体上思考最优的划分,因此,它所做的选择只能是某种意义上的局部最优选择。学术界针对贪心算法不断进行改进探索,但是还没有可以在实践中大规模有效应用的成熟方案。

❑如果目标变量是连续型变量,那么决策树就不适用了,最好改用线性回归算法去解决。

❑决策树缺乏像回归或者聚类那样的丰富多样的检测指标和评价方法,这或许是今后算法研究者努力的一个方向。

❑当某些自变量的类别数量比较多,或者自变量是区间型时,决策树过拟合的危险性会增加。针对这种情况,数据分析师需要进行数据转换,比如分箱和多次模型验证和测试,确保其具有稳定性。

❑决策树算法对区间型自变量进行分箱操作时,无论是否考虑了顺序因素,都有可能因为分箱丧失某些重要的信息。尤其是当分箱前的区间型变量与目标变量有明显的线性关系时,这种分箱操作造成的信息损失更为明显。