决策树概况

决策树是一种常见的机器学习方法，非常有名。决策树可用于分类与回归任务，在很多领域得到普遍应用。以分类任务为例，其目的是根据样例的属性预测其类别。决策树分类器与人们日常决策时采用的逻辑非常相似。

以是否进行高尔夫运动为例，人们会根据天气、温度、湿度、风况等决定是否去打球。例如某人的决策逻辑为：如果天气为阴天，则打球；如果天气为晴天，还要看湿度情况，如果湿度较低则打球；如果天气为雨天，… 。这一决策过程可以用树状结构表示：

在现实中你并不知道此人的决策逻辑，只是收集到他的一些历史数据，比如某天的天气、温度、湿度，以及他是否打了高尔夫。是否可以根据历史数据将他的决策逻辑倒推出来，这才是机器学习该做的事情。

决策树的结构

在数据挖掘中，对于类标签未知的实例，通过回答一系列关于属性的问题可以判定其类别，将一系列关于属性的问题及回答组织成一颗决策树。决策树是一个分层结构，它有三种类型的节点：

• 根节点 决策问题的起点，一颗决策树至少有一个根节点，它覆盖全部样例。
• 内部节点 内部节点对应一个属性测试，属性测试的每个结果用一条分支表示，该节点所包含的样例集根据属性测试结果划分为多个子集，对应到它的各子节点中。
• 叶节点（终端节点） 叶节点对应决策结果，与一个类标签相关联。

决策树构建完成后，对于任何一个样例，存在从根节点到叶节点的一条路，对应一个属性判定序列，根据判定结果将该样例归为某一类别。

决策树形式简洁、比较直观、具有解释性，对很多分类问题有较高的准确率，目前得到广泛应用。

分类树与回归树

根据目标属性的数据类型，决策树大致分为分类树（classification tree）与回归树（regression tree）。目标属性为标称型的数据使用分类树,目标属性是连续数值型使用回归树，也有一些决策树如分类与回归树（CART， Classification and Regression Tree），既能用于分类也能用于回归。在集成学习方法中，可以构建多颗决策树进行数据挖掘，比较著名的算法有随机森林。

决策树模型与算法

决策树已经得到广泛而深入的研究。作为一种机器学习方法，决策树的核心问题是如何根据训练集构造一棵泛化能力强的决策树。最早的决策树算法是Hunt等人1966年提出。20世纪70年代著名机器学习专家Quinlan提出了决策树归纳算法ID3，Quinlan后来对ID3做了一些改进，提出C4.5算法，后续还发展了商业化版本See5/C5.0。1986年统计学家Breiman等在其著作《Classification and Regression Tree》中提出CART算法。Kass于1980年提出了卡方自动交互检测（CHAID），CHAID是一种基于调整后的显着性检验（Bonferroni检验）的决策树技术，可以产生多分支决策树。CHAID可以用于回归与分类，以及检测变量之间的相互作用。决策树也可作为基本模块与集成方法结合起来，如随机森林、梯度提升决策树（GBDT）等。

决策树算法框架

根据数据集构建决策树有很多算法，著名的ID3、C4.5、CART等算法都采用贪心策略，自顶向下以递归方式构造决策树。

在决策树构造算法中有两个关键问题：

（1）分裂准则。对非叶节点必须从多个属性中选择一个“最优”属性，根据属性测试结果将样例集划分为几个子集。根据何种准则选择“最优”属性，使得决策树的泛化能力较强，并且决策树的构造简单快速，是决策树算法中的重要问题。

（2）终止条件。理想情况下，当节点包含的样例都具有同样的类标签时，算法停止扩展。但是如果数据集有两个以上的样例具有同样的属性但类别不同，则不可能达到理想的终止条件。另外，为了追求算法效率或控制决策树的规模，即使当前节点包含的样例类标签不一致也有可能停止扩展，这样的情形有多种，需要根据实际需要形成终止条件。