7.4 决策树学习

7.4.1 机器学习的主要策略

      1、决策树的学习过程（一颗决策树的生成过程）：

        （1）特征选择：从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。

                        三种纯度计算方法：基尼指数、信息熵、错误率

        （2）决策树生成： 根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。 树结构来说，递归结构是最容易理解的方式。

        （3）剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种.

     2、决策树的分类过程

        决策树对给定实例的分类过程是按照实例各属性取值情况，在已建好的决策树上从根节点到叶子节点的匹配过程。具体步骤：

         （1）从树的根节点开始，测试当前节点指定的属性；

        （2） 按照给定实例该属性的取值对应的树枝向下移动，到达下一个节点；

        （3） 步3 在以新节点为根的子树上重复步1、2，直到到达叶子节点，得到该实例的正确分类

7.4.2 决策树学习算法ID3

        自顶向下构造决策树，最关键的问题是属性选择问题

        （1）按照某标准选取一个属性，以该属性作为根节点，以这个属性的全部不同取值作为根节点的分枝，向下增长树，同时按这个属性的不同取值将实例集划分为子集，与相应的分支节点相关联。

        （2）考察所得的每一个子类，看其中的所有实例的目标值是否完全相同；

                如果完全相同，则以这个相同的目标值作为相应分枝路径末端的叶子节点

                否则，选取一个不同于祖先节点的属性

        （3）重复上面过程，直到每个子集中的全部实例的目标值完全相同，得到所有的叶子节点为止

        如何决定重要的节点？——通过属性的信息增益Gain

        信息增益Gain使用熵Entropy来描述的

               熵的计算公式：

          S：关于某个目标概念的正反样例集，      c：目标值的总数      pi：取第i个目标值的样例子集占的比率

          熵刻画了任意样本集的纯度

                 信息增益：

         S：训练样例集，A：某个属性，Sv：属性A取值为v的样例集，例如打网球和不打网球

        例题：

        

         属性Wind的信息增益计算如下：

               

         类似地，计算其他属性的信息增益：

             Gain（ S，Outlook）=0.246

             Gain（ S，Humidity）=0.151

             Gain（ S，Wind）=0 .048

             Gain（ S，Temperature）=0 .029

        在根节点选择Outlook属性（吟哦他的信息增益值最大）作为测试属性。根节点及其分支的构造如下图所示

                

        最终可以得到决策树 ：