构造决策树就是根据现有样本数据生成一个树结构，现在考虑一种最简单的情况，即样本数据特征均为离散的，如下。

    假设我们有如上样本，如何从根节点开始一步步得到一个决策树呢？

    第一步：确定一个分裂属性（即以样本数据的哪个特征进行划分）。

    此处确定最优划分特征的方法是整个决策树的关键部分。最优划分特征的选择基于一个目标：使得分裂后各个节点数据的“纯度”最高。即尽量使得通过该特征进行分类后的分支节点所包含的样本属于同一类别。选择一个合适的特征作为判断节点，可以快速的分类，减少决策树的深度。

    如何量化这种“纯度”？

    1.信息增益

    给出一个信息熵的定义，假设样本用D表示,

    其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。M为类别数，上例中是、否有能力偿还贷款，m=2。

    熵表示样本的混乱程度，样本数据越无序，越混乱，熵就越大。可以考虑通过比较划分特征前后样本数据熵的变化，来确定样本的纯度变化。

    定义信息增益:

    其中，a代表划分的特征，特征a有V个可能的取值（a1,a2,…aV），D中在特征a^(v)上取值为的所有样本定义为D^(v)，|D|表示D中样本个数。

    可以认为，信息增益越大，则意味着以特征a来进行划分，所获得的“纯度提升越大”。因此可以遍历所有特征，选取使得信息增益最大的特征作为当前结点的分裂特征。

    需要知道的是信息增益准则对可取值数目较多的特征有所偏好，如果将表1中的ID列也作为特征，可以计算其信息增益，是所有特征里面最大的，因为其将原始样本分成10个分支，且每个分支都只有一个样本，纯度自然是最高的，但这并没有泛化能力。

    2.增益率

    增益率是在信息增益偏向多取值特征的特性上做出的改进，减少了该偏向可能带来的不利影响。具体定义为：

    该公式利用IV(a)，表示特征a的一个特性，特征的取值数目越多，则IV的值通常会越大，可以达到消除多取值特征带来的不利影响。

    3.基尼指数

    基尼指数用于度量数据集D的纯度:

    直观来说，Gini(D)反映了从数据集D随机选取两个样本，其类别标记不一致的概率，则基尼系数越小，代表其纯度越高。（与熵类似）

    选取合适的纯度量化方式，可以从当前样本数据中找到最好的划分特征，从而将数据集划分为若干个分支。

    第二步：观察划分的各个分支，如果分支中样本数据均属于同一类别，则该分支应为叶节点，无需再进行计算；

    如果分支中样本所有特征都相同，无法再继续分解下去，那么当前分支就为叶节点，类别标记为当前分支中样本数最多的一种（多数表决）；

    如果以上均不符合，应针对每一组样本数据重复第一步的过程，将分支继续递归分解下去，直至每个分支的样本数据都具有相同的类别。（可以预见的是，树的层数最大不会超过特征的个数，因为每一层进行分割时，肯定不会采用其上层节点采用的分割特征进行分裂）

    以上面的贷款偿还能力评价为例，

    根节点开始时我们的数据集是所有的10个样本，通过以信息增益作为纯度评价标准，发现最优划分特征为是否有房，这时按照有房和无房两种情况，将10个样本分为两组，然后可以观察，有房的样本都具备偿还能力，这属于我们第一个的递归停止条件，即此时无需再进行计算，根节点的左子结点即为根节点，在是否有房这一特征上的值为是，则输出为“具备偿还能力”；而其他没有房的样本则需要继续递归分割，直至全部都生成叶子节点为止。

    注：这种决策树的自顶向下递归分治的方法，属于贪心算法的一种，虽然其每步都选取了当前最优的分割特征，但是其总体不一定是最优的。

    连续值处理：上面的特征默认认为是离散的，即只有有限的几种情况，但很多时候，特征值常常是连续的，比如具体工资的数额，温度的数值等等。

    这时候不能直接采用上面的特征分割方法，首先需要将连续属性离散化，最简单的方法是二分法，就是设置一个阈值，小于这个值的为一类，大于这个值的为另外一类。

    给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将其从小到大排序，即为(a1,a2,a3…an)。然后可以计算出n-1个潜在划分点Ti。

    即将每两个相邻元素的中间点可以看做潜在分裂点，这样一来，以潜在分裂点为界，就可以将连续数据当作离散的来处理了。但是连续特征的信息增益略有不同，如下

    其中，表示以特征a上不大于潜在分裂点t的所有样本集合，表示以特征a上大于潜在分裂点t的所有样本集合。上述公式计算了连续特征的信息增益大小。需要注意的是，采用该方法最多只会产生两个分支，并且与离散数据不同的是，当其下属分支继续划分时，仍可以使用当前划分的连续特征。（因为离散特征划分后一个分支内的样本数据在该特征上不可能出现多于一种的值，而采用二分法选取的连续特征显然不具备这一条件。）

    剪枝处理：剪枝操作是为了对付决策树学习算法中“过拟合”的情况，由于决策树算法会不断的重复特征的划分过程，或者由于噪声数据的存在，有时候会使得决策树分支过多，造成过拟合的情况，即对训练数据的分类很准确，但是对未知的测试数据的分类确没那么准确。这种情况下可以采用主动去掉分支的方法来降低过拟合的风险。一般存在“预剪枝”和“后剪枝”两种策略。

    预剪枝即为在决策树生成过程中，对当前节点的划分结果进行评价，如果该划分不能带来决策树泛化能力（即处理未见过示例的能力）的提升，则停止划分，将当前结点标记为叶节点；后剪枝则是先生成一棵完整的决策树，然后自底向上的对非叶节点进行评价，如果剪掉该枝可以使得泛化性能提升，则将该子树替换为叶节点。预先剪枝可能过早的终止决策树的生长，后剪枝一般能够产生更好的效果。但后剪枝在子树被剪掉后，决策树生长的一部分计算就被浪费了。

    这里简单介绍一个剪枝算法，首先明确，我们剪枝的目的是为了减小过拟合带来的不良影响，降低决策树模型的复杂度，但是同时也要保证其对于训练数据有较好的分类效果。因此，定义一个损失函数，如下

    其中，a>=0为参数，C(T)表示模型对于训练数据的预测误差，我们先不必关心C(T)的具体公式，理解其含义就行。|T|表示叶节点的个数，可用于表示模型的复杂度。可以看出，参数a控制着模型复杂度和对训练数据拟合程度两者之间的影响。较大的a促使我们选择一个较简单的树，而较小的a则偏向于对训练数据的有更好的拟合效果。

    因此可以利用上面的损失函数进行剪枝操作，这样得到的决策树即考虑到对训练数据的拟合，又增强了泛化能力。

    其他一些剪枝算法有的借助验证集实现，也有算法通过设置信息增益的阈值来作为剪枝判断标准，具体的算法过程可以参考相关文献。

    随机森林：简单来说就是利用训练数据生成多个决策树，形成一个森林，然后利用这个森林对未知数据进行预测，选取投票最多的分类。