上一篇介绍了决策树中涉及的各分类依据指标的概念，信息增益、信息增益率和基尼系数。在构建树模型时选择的分类指标不同，就有不同的决策树构建方法，如本篇将要介绍的最经典决策树构建法：ID3和C4.5

1.0 ID3算法

1.1 算法简介

        ID3算法是基于“信息增益”的一种决策树构建算法，用于对离散变量进行分类。算法的本质就是通过计算每个特征的信息增益，每次划分选取信息增益最高的属性为划分标准，递归地构建决策树。

        ID3决策树的一般构建流程：

        1）从根结点(root node)开始，对数据集的所有特征的信息增益进行计算，选择信息增益最大的特征作为结点的特征；

        2）由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，继续向下构建树；

        3）直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。

        从ID3的构建树过程而言，该算法使用了贪婪搜索，从不回溯重新考虑之前的选择情况，因此无法保证是最优的。

1.2 伪码实现

        使用递归思想实现决策树构建函数：

定义函数   createTree(dataSet,featList,bestFeatLists)

        Step 1：原始数据集dataSet中切割出特征矩阵和分类标签X，y

        Step 2：如果y中只有一类标签，说明已经递归到分类边界了，则返回该标签

        Step 3：如果X中只有一类属性（特征列），但是类标签依然不是唯一的，采用投票法决定该子节点的标签

        Step 4：如果未存在S2和S3中的情况，找出X中最优划分（信息增益最大）的特征，确定bestFeatIndex（在特征的列名集合featList中的索引）和最优划分特征bestFeatLabel（列名），将该特征值存储到bestFeatLists中

        Step 5：将最优划分特征值作为当前（子）树的根节点，生成初始决策树myTree

        Step 6：从featList中删除当前已经使用过的特征、从X删除对应的列数据，形成新的子数据集（此时X.shape[0] = 子数据集.shape[0]，但是X.shape[1] = 子数据集.shape[1]+1)

        Step 7：确定子树分支。获取已选择的最优划分特征所对应分类值categories（如“年龄”是最优特征，则“老”“中”“青”三个子类），将子数据集再进行分割（如最优特征“年龄”按“老”“中”“青”三类取值进一步分词三个子数据集，此时 子数据集.shape[0] = "老"_子数据集.shape[0]+"中"_子数据集.shape[0]+"青"_子数据集.shape[0]）

        Step 8：遍历每一个当前特征下的子数据集，对每个子数据集递归地调用创建决策树的方法，将递归调用的结果作为当前特征节点的一个分支（如“老”“中”“青”就是“年龄”的分支）

# 构建树的采用字典存储结构，即特征作为字典的key，所得到的分类结果作为value，子树递归嵌套

1.3 算法优缺点

       ID3算法具备决策树算法的优点，但存在一些问题：

       没有剪枝过程，为了去除过渡数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点；

       信息增益的方法偏向选择具有大量值的属性，也就是说某个属性特征索取的不同值越多，那么越有可能作为分裂属性，这样是不合理的；

       只可以处理离散分布的数据特征；

       ID3算法只考虑了树的生成，即尽可能的是模型拟合当前训练数据集，所以该算法生成的树容易过拟合。

2.0 C4.5算法

2.1 算法简介

        C4.5算法是数据挖掘十大算法之一，是在ID3算法基础上进行了多项改进，主要包括：

        1）用信息增益比来判断特征；

        2）在决策树的构造过程中进行剪枝；

        3）对非离散数据也能处理

        4）能够对不完整数据进行处理

        C4.5算法与ID3算法过程相似，仅在特征选择时，使用信息增益比作为特征选择准则。

2.2 实现伪码

输入：训练数据集D（标签），特征集A，阈值

定义函数   :

        S1：计算当前节点的信息增益率GainRatio，找到GainRatio最大的特征，并以该特征生成节点node

                S1.1：计算经验熵

                S1.2：计算经验熵   # 选择某特征a作为划分特征时的条件熵

                S1.3：计算信息增益   # 选择特征a作为划分特征时的条件熵

                S1.4：计算特征熵

                S1.5：计算信息增益率 

        S2：if D中的所有标签都为同一类，记为C：

                        将node标记为叶节点，标签为C；return

                end if

        S3：if A为空 或 D在A特征上的取值都相同：

                    将node标记为叶节点，其标签标记为D中数量最多的标签；return

                end if

        S4：for  中的每一个值:

                        给node生成一个分支；令表示在的样本子集；

                        if  为空  then  将该分支标记为叶节点，类别标签为此时D中数量最多的标签；return

                        else  调用递归构建子树

                        end if

                end for

3.0 ID3和C4.5比较

        1）ID3：

        熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是希望的划分之后每个子节点的样子。信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说，用属性 a 来划分训练集，得到的结果中纯度比较高。ID3 仅仅适用于二分类问题，ID3 仅仅能够处理离散属性。

        2）C4.5：

        C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。

        3）信息增益 vs 信息增益比：

        之所以引入了信息增益比，是由于信息增益的一个缺点。那就是：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。