四、决策树
1．基本流程：
（1）决策树是基于树结构进行决策的，面对问题进行决策时，通常会进行一系列的判断或“子决策”，最后得到最终决策。决策过程的最终结论对应了我们所希望的判定结果。决策过程中提出的每个判定问题都是对某个属性的测试。每个测试的考虑范围是在上次决策结果的限定范围之内。
（2）决策树的叶结点对应于决策结果，其他每个节点则对应于一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集。从根节点到每个叶子结点的路径对应了一个判定测试序列。
（3）决策树的生成是一个递归过程。在决策树的及本算法中，有三种情况导致递归返回：当前节点包含的样本全属于同一类别，无需划分；当前属性集为空，或是所有样本在所有属性上取值相同，无法划分（此时即为叶结点）；当前结点包含的样本集合为空，不能划分（此时也为叶结点）。一个具体的决策树算法如下：
个人理解：这里可以看到，输入的是一个训练集加一个属性集，而输出的是一颗决策树，这是因为我们的学习方法最终想要得到的是一个可以解决问题的学习器，而在这里这个学习器就是这一棵我们得到的决策树。上述是学习方法，即如何生成一颗决策树，首先前两个if相当于是范围的界定，先对yi进行判断是否是全同类别，然后判定属性集是否为空或者训练样本的属性均相同，在不满足这两个条件的时候才能说这个训练集是有效的，才能用来训练。然后重点是第8行的从A中选择最优化分属性，这里不好理解。然后的for循环就是递归的建立一颗决策树，最终就可以得到以node为根节点的决策树。
2．划分选择：
之前已经看出来，决策树学习的关键是第8行，即如何选择最优划分属性，随着划分过程的不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。
（1）信息增益：
“信息熵”是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本（比如好瓜、坏瓜）所占的比例为pk，则D的信息熵定义为：Y为结果类别个数？
Ent(D)的值越小，则D的纯度越高。其中若p=0，则plogp也为0，Ent(D)的最小值为0，最大值为
（此时的Y为2）。
假定离散属性a有V个可能的取值{a1…av}，若使用a来对样本集D进行划分，则会产生V个分支节点，其中第v个分支节点包含了D中所有在属性a上取值为av的样本，记为Dv。我们可以根据上式计算出Dv的信息熵，在考虑到不同的分支节点所包含的样本数不同，给分支节点赋予不同的权重|Dv|/|D|，即样本数越多的分支节点影响越大，于是可计算出用属性a对样本集D进行划分所获得的“信息增益”：
V表示属性a的可能取值为{a1…av}, 信息增益越大，使用a属性来划分所获得的“纯度提升越大”，因此我们可以使用信息增益作为决策树的划分属性选择，就如第8行的
，ID3决策树学习算法就是使用信息增益为准则划分属性。
以下表为例：
该数据集包含17个训练样例，用以学习一颗能预测没剖开的是不是好瓜的决策树。显然|Y|=2，在决策树学习开始时，根节点包含D中的所有样例，其中正例占p1=8/17，反例占p2=9/17，于是可以计算出根节点的信息熵为：
然后我们要计算出当前属性集合{色泽、根蒂、敲声、纹理、脐部、触感}中每个属性的信息增益，以属性“色泽”为例，他有3个可能的取值：{青绿、乌黑、浅白}，可以得到3个子集，分别即为D1（色泽=青绿）D2（色泽=乌黑）D3（色泽=浅白）。D1包含编号为{1,4,6,10,13,17}的6个样例，正例占p1=3/6，反例占p2=3/6；D2包含编号为{2,3,7,8,9,15}的6个样例，正反例分别占p1=4/6,p2=2/6；同理D3包含编号为{5,11,12,14,16}的5个样例，正反例分别占p1=1/5,p2=4/5，计算使用“色泽”划分后获得的的3个分支节点的信息熵为：
于是根据上式可计算出属性“色泽”的信息增益为：
类似的可以计算出其他属性的信息增益：
显然属性“纹理”的信息增益最大，于是他被选为划分属性，基于“纹理”属性对根节点划分：
然后决策树学习算法对每个分支节点作进一步的划分，以第一个分支节点（“纹理=清晰”）为例，此时结点包含的样例集合D1中有编号为{1,2,3,4,5,6,8,10,15}的9个样例，可用属性集合为{色泽，根蒂，敲声，脐部，触感}，基于D1计算出各属性的信息增益：
再选取其中最大的，然后递归进行，直到每个分支节点都完毕，由此得到最终的决策树如下所示：
个人理解：这里个人认为信息增益就是为了得到当前的各个属性对于分类的影响程度，选择影响最大也是最重要的进行首先判断，然后在该属性的基础上再对其他次要属性进行判断，最终得到一颗决策树。
（2）增益率：
由于信息增益准则对可取之数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用“增益率”来选择最优化分属性，增益率的定义为：
称为属性a的“固有值”。属性a的可能取值数目越多，IV(a)的值通常越大，增益率对分支少的属性有偏好。因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益水平高于平均水平的属性，再从中选出增益率最高的。
个人理解：实际上就是信息增益除以了一个该属性固有的参数，该参数由该种属性的可取值数目及可取值的样本个数决定，一般来讲可取值数目越多那么IV(a)越大，增益率变小
（3）基尼指数：
CART决策树使用“基尼指数”来选择划分属性，数据值D的纯度可用基尼值来度量：
直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标志不一致的概率，因此Gini(D)越小，则数据集D的纯度越高。由此属性a的基尼指数定义为：
于是我们在候选属性集合A中选择那个使得划分后的基尼指数最小的属性作为最优化分属性。即：
个人理解：基尼值就是进行了Y组二抽取，计算出随机抽取两个样本不一致的概率是多少，那么样本的纯度越高，两个样本一致的可能性越高，当然可能这个取值不一定，但基尼值一定越小。同时，不管是信息增益还是增益率还是基尼指数，都是为了计算出对于当前的选择分支中影响最大，也就是得到的子分支中纯度最高的属性
3．剪枝处理：
剪枝是决策树学习算法应对“过拟合”的主要手段，基本策略是“预剪枝”和“后剪枝”。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，产生过拟合。
预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶结点
后剪枝是先从训练集生成一颗完整的决策树，然后自底向上得对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
由此可以看出，预剪枝和后剪枝的重点都是要判断决策树泛化性能是否提升，这可以使用性能评估方法，这里采用留出法，即预留一部分数据作为验证集以进行性能评估。以上面的西瓜数据集为例：
划分出的训练集（双线上部）与验证集（双线下部）
（1）预剪枝：
基于信息增益准则，我们会选取属性“脐部”来对训练集进行划分，并产生3个分支，但预剪枝要对划分前后的泛化性能进行估计。下面是未剪枝的决策树：
在划分前，所有的样例集中在根节点若不进行划分，则根据第六行代码：
该类别标记为训练样例数目最多的类别，假设将这个叶结点标记为好瓜，则编号{4,5,6}的样例分类正确，验证集精度为3/7=42.9%
在用属性“脐部”划分后，每个分支节点分别包含编号为{1,2,3,14}、{6,7,15,17}、{10,16}，因此这三个结点分别被标记为叶结点“好瓜”、“好瓜”、“坏瓜”。此时验证集中编号为{4,5,8,11,12}的样例被分类正确，验证精度为5/7=71.4%，于是用“脐部”划分确定。
然后，分别对三个结点进行划分。基于信息增益准则挑选出来的分别是“色泽”、“根蒂”、无（所含训练样例已经为同一类，不能再进行划分）。可是前两个都会导致精度下降，最终得到精度为71.4%，仅有一层的决策树，亦称为“决策树桩”。这里想到如果在信息增益准则挑选出来的被否的时候，能不能用第二位的？
最终得到的预剪枝决策树如下：
预剪枝使得决策树的很多分支没有“展开”，不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，预剪枝的贪心策略可能会忽略一些后续提升性能的分支，给预剪枝决策树带来了欠拟合的风险。
（2）后剪枝：
在没有剪枝的时候得到的决策树通过验证集验证后得到其验证集精度为42.9%。后剪枝首先考察图中的6结点（纹理），若将其减去后替换的叶结点包含编号为{7,15}的训练样本，该结点标记为“好瓜”，此时决策树的验证集精度提高至57.1%，于是减去。
同理，处理结点5（色泽），减去后包含编号为{6,7,15}的训练样本，叶结点标记为“好瓜”，此时验证集精度仍为57.1%，故不剪枝。
处理结点2（色泽），减去后包含编号为{1,2,3,14}的训练样本，叶结点标记为“好瓜”，此时验证集精度为71.4%，剪枝。
处理结点3（根蒂）和结点1（脐部），精度分别为71.4%和42.9%，保留。最终得到的决策树如下所示：
一般情形下，通常保留了更多的分支，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但其训练时间开销比未剪枝决策树 和预剪枝决策树都要大得多。
4．连续与缺失值：
（1）连续值处理：
到目前只是讨论了基于离散属性来生成决策树，县市学习任务重通常会遇到连续属性，有必要讨论如何在决策树学习中使用连续属性。
由于连续属性的可取值数目不再有限，因此不能直接根据连续属性的可取值来对结点进行划分，因此可以使用连续属性离散化技术。最简单的策略是采用“二分法”对连续属性进行处理，这正是C4.5决策树算法中采用的机制。
给定样本集D和连续属性a，假定a在D上有n个不同的值，将这些值从小到大进行排序，记为{a1,…,an}。基于划分点t可将D分为子集
和
，其中包含在属性a上取值不大于t的样本。显然，对梁琳的属性取值ai和ai+1来说，t在区间[ai,ai+1)中取任意值所产生的划分结果相同。因此，可考察n-1个划分点集合：
即把区间[ai,ai+1)的中位点作为候选划分点。然后就可像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。例如信息增益就可以修改为：
其中Gain(D,a,t)是样本集D基于划分点t二分后的信息增益，于是可选择使Gain(D,a,t)最大化的划分点。还是以西瓜为例，增加了密度和含糖率两个连续属性：
对属性“密度”，该属性的候选划分点集合包含16个候选值：={0.9,0.518,0.574,0.60,0.294,0.351,0.381,0.420,0.459,0.518,0.574,0.600,0.621,0.636,0.648,0.661,0.681,0.708,0.746}，可计算出属性“密度”的信息增益为0.262，对应于划分点0.381
同理对于属性“含糖率”，候选划分点也包含16个候选值：={0.049,0.074,0.095,0.101,0.126,0.155,0.179,0.204,0.213,0.226,0.250,0.265,0.292,0.344,0.373,0.418}，可计算出其信息增益为0.349，对应于划分点0.126
计算各个属性的信息增益为：
纹理被选作根节点划分属性，伺候递归进行，最终生成如图所示决策树：
注意，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性（即可反复多次使用连续属性，在父节点使用了密度≤0.381则在子节点仍可使用密度≤0.294）
个人理解：实际上和离散的主要区别就是不采用样本的值而是两样本之间的中值作为划分点，并且可以多次使用同一个属性。
（2）缺失值处理：
遇到不完整样本的时候，不能简单的进行删除，有必要考虑利用有缺失属性值的训练样例来进行学习：
需要解决两个问题：（1）如何在属性值缺失的情况下进行划分属性选择？（2）给定划分属性，若样本在该属性上的值确实，如何进行划分？
显然有：
并将信息增益推广为：
其中
个人理解：实际上就是通过假定每个信息的权重，计算了占比然后模拟出一个信息增益。
个人理解：划分时，如果样本x在属性a上取值已知，则进入相应子节点，权重wx不变；如果样本x在属性a上取值未知，则x进入所有子节点，样本权重在对应子节点中调整为。直观地看，就是让同一个样本以不同的概率进入到不同的子节点中去。C4.5算法使用了这样的方案。以西瓜为例：
开始时，根节点包含样本集D中全部17个样例，各样例的权值均为1.以属性“色泽”
为例，该属性上无缺值的样例子集包含编号为{2,3,4,6,7,8,9,10,11,12,14,15,16,17}的14个样例。显然其信息熵为：
令1、2、3分别表示在属性“色泽”上取值为“青绿”、“乌黑”、“浅白”的样本子集，有：
因此计算属性色泽的在样本集上的信息增益为：
于是样本集D上属性“色泽”的信息增益为：
类似的计算出所有属性在D上的信息增益为：
“纹理”在所有属性中取得了最大的信息增益，被用于对根节点进行划分，划分结果是使编号为{1,2,3,4,5,6,15}的样本进入“纹理=清晰”分支，编号为{7,9,13,14,17}的样本进入“纹理=稍糊”的分支，而编号为{11,12,16}的样本进入“纹理=模糊”分支，且样本在各子节点中的权值保持为1.注意样本{8}在属性“纹理”上出现了缺失值，因此他将同时进入三个分支中，但权重在三个子节点中分别调整为7/15,、5/15和3/15.编号为{10}的样本有类似结果。最终得到的决策树如下：
5．多变量决策树：
如果把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显特点：轴平行，即他的分类边界由若干个与坐标轴平行的分段组成。
一下表为例，将它作为训练集可得到如下的决策树，这棵树对应的分类边界如图所示：
显然分类边界的每一段都是与坐标轴平行的。这样的分类边界使得学习结果有较好的解释性，因为每一段划分都直接对应了某个属性取值，但在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能得到较好的近似。
由于要进行大量的属性测试，预测开销会很大。
“多变量决策树”是一颗能够实现“斜划分”的斜决策树。在此类决策树中，非叶结点不再是针对某个属性，而是对属性的线性组合进行测试。即每个非叶结点是一个形如
的线性分类器，其中wi是属性ai的权重，wi和t可在该节点所含的样本集合属性集上学得。最后得到的决策树如图所示：
个人理解：在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优化分属性，而是试图建立一个合适的线性分类器。