【机器学习】决策树算法总结|ID3 C4.5/C5.0 CHAID CART与QUEST

会员服务 ·

【机器学习】决策树算法总结|ID3 C4.5/C5.0 CHAID CART与QUEST

2017 年 8 月 23 日 数萃大数据 louwill

● 概要

● 决策树模型

● 特征选择

● 决策树学习

● 决策树剪枝

● 决策树算法

● ID3

● C4.5/C5.0

● CHAID

● CART

● QUEST

概要

决策树作为一种基本的分类与回归方法（更多时候指分类），是学习数据挖掘与机器学习的首要算法。决策树之所以排在各类机器学习算法首位更多是因为其概念简单且容易理解，在入门以前，不需要学习者有多少算法基础。对于决策树，可以把它理解为一组 if-then 规则的集合，也可以认为是定义在特征空间（自变量）与类空间（因变量）的条件概率分布。通常对于分类问题决策树处理速度较快，其算法也有较强的可读性。决策树的学习策略是基于损失函数最小化原则，生成决策树后可对决策树进行剪枝以防止决策树过于复杂而产生过度拟合。

决策树生成的过程就是不断进行特征选择的过程，因而熵和基尼指数等概念被引入进来。通过遍历计算每类特征的信息贡献，一个最优的决策树得以被构造出来。如果说决策树是一个 if-then 规则的集合，其本质在于由决策树的根结点到叶节点的每一条路径构建了一条规则的条件，而叶节点的类对应着规则的结论。如果说决策树还表示给定特征空间下类的条件概率分布，这一条件概率分布定义在特征空间的一个划分上。而决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。

常见的景点决策树算法包括ID3，C4.5/C5.0，QUEST，CHAID以及CART算法。各种决策树算法既有区别也有联系，小编在学习之后便写个总结对决策树好有个宏观的把握。

决策树模型

一棵决策树通常由结点和有向边组成，结点包括根结点、内部结点和叶节点，根结点和内部节点表示一个特征或者属性，而叶节点表示一个具体分类，一颗常见的决策树如下：

特征选择

所谓特征选择，即在于选取可以对训练数据进行较好分类的特征。在统计与机器学习里叫特征选择，在数据挖掘里又叫属性测试条件。通常特征选择的准则是信息增益、信息增益比或者基尼指数等。

说到信息增益那就不得不引入熵的概念了。在信息论中，熵表示对随机变量不确定度的度量（偷偷说一句，小编的研究生论文做的就是最大熵贝叶斯），当 X 为一个离散随机变量时，其熵 H（X）定义为

而条件熵 H（Y|X）表示在已知随机变量 X 的条件下随机变量 Y 的不确定性。随机变量 X 给定的条件下随机变量 Y 的条件熵 H（Y|X）定义为

所谓的信息增益表示在已知特征 X 的信息而使得类 Y 的信息的不确定性减少的程度。若特征 A 对训练数据集 D 的信息增益为 g(D,A) ，则 g(D,A) 定义为集合 D 的经验熵 H(D) 与特征 A 给定条件下 D 的经验条件熵 H（D|A）之差

为选择最好的特征进行分类，需对训练数据集计算每个特征的信息增益，通常信息增益值最大的特征被选为最优分类特征。而信息增益比定义为信息增益 g(D,A) 与训练数据集 D 关于特征 A 的值的熵 HA(D) 之比

决策树学习

决策树学习本质上是从训练集中归纳出一种分类规则。能对训练数据集进行完美分类的决策树可能有许多个也可能一个也没有，而我们需要的一个能对训练集进行最大程度分类的决策树，即分类规则出现错误最小的决策树，同时该决策树还能对未知数据集具有很好的泛化能力。从概率模型的角度看，决策树学习是由训练数据集估计条件概率模型，基于特征空间划分的类的条件概率模型有无穷多个，而我们选择的条件概率模型应该不仅对训练数据有很好的拟合能力，且对未知数据有很好的预测。

决策树学习用损失函数来表示对未知数据进行很好的预测能力的目标。决策树学习的损失函数通常是正则化的极大似然函数，学习策略则是以损失函数为目标函数的最小化。

决策树剪枝

按照决策树学习方法生成的决策树可能对训练数据集有很好的分类能力，但对未知的测试数据集却未必有很好的分类能力，即有可能产生拟合过度的情况，这时就需要对决策树自下而上的进行剪枝，将复杂的树进行简化，使其具有较好的泛化能力。决策树剪枝算法可描述为：计算每个结点的经验熵，然后递归地从树的叶节点向上回缩，如果对应叶节点的损失函数值要大于父节点的损失函数值，则进行剪枝，即将父节点变为新的叶节点。不断的递归回缩，直至不能继续剪枝为止，以此便可得到损失函数最小的决策子树。

由上我们可以看出，决策树学习方法包括特征选择、决策树的生成与决策树的剪枝这三个过程。下面就结合具体的决策树算法进行介绍。

决策树算法

下表是由15个样本组成的贷款申请训练数据集，包括四个特征（年龄、有无工作、有无房子、信贷情况）和一个类别（是否同意贷款），以此训练数据进行决策树算法的分析。（表格来自李航. 统计学习方法）

ID3

ID3算法的全称叫 Iterative Dichotomiser 3（迭代二叉树三代），是由 Ross Quinlan于1986年提出的决策树思想方法，当然 C4.5/C5.0 算法也是他提出的。ID3 算法的核心就是在决策树各个结点上应用信息增益准则进行特征选择，以此递归地构建决策树。对于上表中的贷款数据集应用 ID3 算法构建决策树。

首先计算每个特征的信息增益，以此来选择最优特征进行分类。分别以 A1，A2，A3，A4表示年龄、有工作，有房子和信贷情况这4个特征，则各特征的信息增益可计算为

同理可计算A2，A3，A4 的信息增益值为 0.324，0.420和0.363，可见特征A3的信息增益值最大，首选A3作为最优特征进行决策树构造。

特征A3将训练数据集划分为两个子集D1（A3取值为是，有房）D2（A3取值为否，无房），然后继续按照信息增益条件选择余下的特征，计算A1，A2和A4的信息增益值。

根据计算结果选择信息增益最大的 A2（有无工作）作为结点特征，该结点可引出两个子节点：一个是有工作的子节点，一个是无工作的子节点，分属于两个子节点的样本均属各自同一类别，因此该决策树只用了两个特征即可构造完成。

以上便是 ID3算法构造决策树的过程。

C4.5/C5.0

C4.5算法与 ID3 算法极为相似，只是在特征选择上有所不同，算是一种对 ID3 算法的改进了。C4.5算法在决策树生成过程中，用信息增益比来选择特征。信息增益比的定义如前文所述。而 C5.0 算法作为 C4.5的改进版，其算法原理都是一致的，都是采用信息增益比来进行特征选择，但C5.0适用于处理大数据集，采用 Boosting 方式来提高模型准确率，计算速度较高，对计算内存占用也较少。关于 C4.5和C5.0的实际计算可参考R语言实现方式。

CHAID

CHAID算法全称叫做卡方自动交叉检验法（Chi-squaredAutomatic Interaction Detector），是 Kass于1974年提出来一种决策树算法。这里涉及到卡方检验，故在此对此进行简单解释。首先需要明确的一点是，卡方检验针对的是分类变量，是统计样本的实际观察值与理论观察值之间偏离程度的量，这个偏离程度决定了卡方值的大小，偏离程度越大，卡方值也就越大，若二者无差异，卡方值就为零。

CHAID算法通过计算类别变量与特征变量之间的相关性检验统计量的 p 值，即卡方统计量对应的 p值，p 值越小，说明特征变量与类别变量之间的关系越密切，应当被选为最佳分组特征变量。然后继续按此准则选择后续特征变量，直至所有样本被分类完毕。CHAID算法在构建决策树时具有一定的优势，它是从统计显著性的角度来确定特征变量和分割数值，对决策树的分枝过程优化明显。

CART

CART（classification and regression tree）分类与回归树算法是由 Breiman等人在1984年提出的一种决策树算法，CART 算法既可用于分类也可用于回归，是一种应用广泛的决策树学习方法。

CART是在给定输入随机变量X条件下输出变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出条件概率分布。

与ID3 C4.5/C5.0不同的是，CART算法构造决策树是通过基尼指数来选择最优特征的，同时也决定该特征的最优二值切分点。在特征 A 的条件下，集合 D 的基尼指数定义为