本文共 1924 字，大约阅读时间需要 6 分钟。

讲决策树之前，先引入分类算法的概念： 分类算法概念：定义：分类（classification)分类任务就是通过学习得到一个目标函数(target funciotn)f，把每个属性集x映射到一个预先定义的类标号y。

目标函数：目标函数也称为分类模型（classification model）。

目标函数的作用：

（1）描述性建模，分类模型可以作为解释性工具，用以区分不同类中的对象。

（2）预测性建模：分类模型还可以用来预测未知记录的类标号。

建模的过程可以由下图来说明：

如上图所示，建立了分类模型之后，可以讲未知类别的属性集输入分类模型，然后通过分类模型得出类标号，那么如何通过原有的数据集建立分类模型，该建立什么样的分类模型就是我们主要需要考虑的问题。

如下图所示，分类模型的建立分为两个阶段，一个是学习阶段，一个是检验阶段。总体来讲，就是通过已有数据集来产生分类模型，然后通过训练集来检验分类模型。

如何建立分类模型？

决策树算法就是建立分类模型的算法之一，其他的有基于规则的分类法、支持向量机、朴素贝叶斯分类法、神经网络分类法等。

决策树：顾名思义，是一种树，一种依托于策略抉择而建立起来的树。

决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。

下面是简单的生活中的例子，参考别人的一篇博客：

左边是一棵通过训练集建立好的决策树，我们在树根处输入对象张三的属性集，通过树的各个条件分支进行筛选，我们最终可以得出类别（见或者不见）。

建立决策树的基本步骤如下:

1.开始，所有记录看作一个节点

2.遍历每个变量的每一种分割方式，找到最好的分割点

3.分割成两个节点N1和N2

4.对N1和N2分别继续执行2-3步，直到每个节点足够“纯”为止

那么如何找到最“纯”的分割点，什么样的分割叫“纯”，如何去量化？这里就要引入一个新的概念，叫做“属性度量选择度量“。

属性选择度量是一种选择分裂准则，把给定类标记的训练元组的数据分区D“最好地”划分或单独类的启发方法。如果我们根据分裂准则的输出把D划分成较小的分区，理想的情况是，每个分区应当是纯的（即落在一个给定分区的所有元组都属于相同的类）。从概念上讲，“最好的|”分裂准则是导致最接近这种情况的划分。属性选择度量又称为分裂规则，因为它们决定给定结点上的元组如何分裂。

如上例所示，所选的属性度量依次是年龄、长相、收入、公务员，每次选择一个属性去进行分支选择，而”属性度量选择“正是每次选择什么样的属性去进行分支的依据。

下面介绍两种属性选择度量，并通过示例加以说明：

一、信息增益（主要应用于ID3算法）

我们通过对选择不同属性产生的信息增益进行比较来得出该次选择什么样的属性进行分支。

例子：

        

二、增益率（主要应用于C4.5算法)

采用了此两种方法建立了决策树之后可能导致一个问题，就是穷举了所有的属性进行决策树分支，有可能使得产生的决策树过于庞大，这时候就需要对决策树进行剪枝。

决策树的剪枝：

在决策树创建时，由于数据中的噪声和离群点，许多分歧反映的是训练数据中的异常。剪枝方法处理这种过分拟合数据的问题。通常，这种方法使用统计度量剪枝掉最不可靠的分支。一棵未剪枝的树和它剪枝后的版本显示如图所示。剪枝后的树更小、更简单，因此更容易理解。通常，它们在正确地独立的检验集分类时比未剪枝的树更快、更好。

剪枝分为两种：

1、先剪枝（prepruning）

通过提前停止树的构建（例如，通过决定在给定的结点不再分裂或划分训练元组的子集）而对树“剪枝”。一旦停止，结点就成为树叶。该树叶可以持有子集元组中最频繁的类，或这些元组的概率分布。

在构造树时，可以使用诸如统计显著性、信息增益、基尼指数等度量来评估划分的优劣。如果划分一个结点的元组导致低于预定义阈值的划分，则给定子集的进一步划分将停止。

例如：假定我们将信息增益的阈值设为Gain（D）=0.3， 信息增益一节中Gain（age）=0.246 小于所设定的阈值，那么就需要将整个属性集作为一个结点不需要继续划分。

2、后剪枝（postpruning），它由“完全生长”的树剪去子树。通过删除结点的分枝并用树叶替换它而剪掉给定结点上的子树。该树叶的类标号用子树中最频繁的类标记。

      如左边图所示，对于A3的划分中，A3子树中叶子结点的类别绝大多数都是B，假设想将基于A3的划分剪枝掉，就可以用类B去代替A3的划分。