4.1 基本流程
决策树是一类常见的机器学习方法，是基于树结构来进行决策的，进行决策时，通常会进行一系列的判断或"子决策"，决策过程中提出的每个判定问题都是对某个属性的"测试"，每个测试的结果或是导出最终结论，或是导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内。
一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；
叶结点对应于决策结果，其他每个结点则对应于一个属性测试；
每个结点包含的样本集合根据属性测试的结果被划分到子结点中；
根结点包含样本全集；
从根结点到每个叶结点的路径对应了一个判定测试序列；
决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的"分而治之"策略。如图
决策树的生成是一个递归过程，3种情形会导致递归返回：
( 1 )当前结点包含的样本全属于同一类别，无需划分。
( 2 )当前属性集为空，或是所有样本在所有属性上取值相同，无法划分，则把当前结点标记为叶节点，并将其类别设定为该结点所含样本最多的类别，是在利用当前结点的后验分布。
( 3 )当前结点包含的样本集合为空，不能划分，同样把当前结点标记为叶结点，且将其类别设定为其父结点所含样本最多的类别，是把父结点的样本分布作为当前结点的先验分布。
4.2 划分选择
选择最优划分属性，使结点的“纯度”越来越高。
一些符号表示：
样本集合为D；离散属性为a；分支结点个数为V；pk 为样本集合D中第k类样本所占的比例；Dv 为第v个分支结点包含了D中所有在属性a上取值为av 的样本
方法一：信息增益
划分选择：一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此选择信息增益最大的属性作为划分属性。
信息增益缺点：对可取值数目较多的属性有所偏好
用属性a对样本集D进行划分所获得的“信息增益”为：
其中信息熵Ent(D)是度量样本集合纯度最常用的一种指标，定义为：
方法二：增益率
划分选择：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
增益率优点：能减少信息增益准则对可取值数目较多的属性偏好带来的不利影响
缺点：增益率准则对可取值数目较少的属性有所偏好
增益率的定义：
其中IV（a）为属性a的固有值，定义为：
方法三：基尼指数
划分选择：基尼值Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，基尼值越小，则数据集D的纯度越高。因此选择那个使划分后基尼指数最小的属性作为最优划分属性。
基尼值定义：
基尼指数定义：
4.3 剪枝处理
剪枝是决策树学习算法对付“过拟合”的主要手段。
数据：
未剪枝的决策树：
方法一：预剪枝
预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
预剪枝决策树：
方法二：后剪枝
后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
后剪枝决策树：
比较：
1.剪枝决策树通常比预剪枝决策树保留了更多的分支。
2.一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。
3.后剪枝训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
4.4 连续与缺失值
1.连续值处理：连续属性离散化技术——二分法
给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大进行排序，记为{a1,a2,...,an} .基于划分点t可将D分为子集和
，其中
包含那些在属性a上取值不大于t的样本，
则包含那些在属性a上取值大于t的样本。对相邻的属性取值ai与ai+1来说，t在区间[ ai,ai+1)中取任意值所产生的划分结果相同。对连接属性a，考察包含n-1个元素的候选划分点集合：
样本集D基于划分点t二分后的信息增益为Gain(D,a,t)：
2. 缺失值处理
在属性值缺失的情况下进行划分属性选择：
给定划分属性，在样本在该属性上的值缺失的情况下对样本进行划分的方法：
4.5 多变量决策树
相当于对特征进行了一个线性的组合，之前的特征是单变量，组合之后单个结点相当于一个 线性的分类器。
