本篇博客主要讲解决策树是如何分类的。
概念
决策树也称判定树，基于树结构进行决策，决策树是一个预测模型，代表的是对象属性与对象值之间的一种映射关系。
一般的，一棵决策树包含一个根节点、若干个内部节点和若干个叶节点。叶节点对应于决策结果，其他每个节点对应于一个属性测试；每个节点包含的样本根据属性测试的结果被划分到子节点中；根节点包含样本全集。
决策树学习目的：为了产生一个泛化能力强，即处理未见示例能力强的决策树。
一样通过一个简单的例子先来了解一下什么是决策树
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
那我们可以用一个决策树去表达母亲和女儿的对话：
那下面我们就可以先引入决策树的算法流程了：
算法流程
输入: 训练集D={(x1,y1),(x2,y2),……,(xm,ym)} ;
属性集A= {a1,a2,……ad}.
过程: 函数TreeGenerate(D,A)
l: 生成结点node;
2: if D 中样本全属于同一类别 C then
3: 将node 标记为C类叶结点; return
4: end if
5: if A= Ø OR D 中样本在A 上取值相同then
6: 将node 标记为叶结点，其类别标记为D中样本数最多的类; return
7:end if
8: 从A 中选择最优划分属性;
9: for 的每一个值 do
10: 为node 生成一个分支; 令 表示D中在 上取值为 的样本子集;
11: if 为空then
12: 将分支结点标记为叶结点，其类别标记为D 中样本最多的类; return
13: else
14: 以TreeGenerate( ,A{ })为分支结点
15: end if
16: end for
输出: 以node 为根结点的一棵决策树
分析一下算法中三个返回情况
(1)当前结点包含的样本全部属于同一类别，无需划分。
(2)当前属性集为空，或者是所有样本在所有属性上的取值相同，无法划分。(当前结点标为叶子结点，其类别也是该节点所含样本最多的类别)
(3)当前结点包含的样本集合为空，不能划分。(当前结点标为叶子结点，其类别为父结点所含样本最多的类别)
(2)和(3)是不一样的，(2)是在利用当前结点的后验分布，(3)是把父结点的样本分布作为当前结点的先验分布。
算法的核心思想在于划分选择，下面对划分选择进行介绍
划分准则：随着划分过程的不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高。
方法：信息增益（ID3）
优化方法：增益率（C4.5）
相关概念
“信息熵”information entropy：是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本所占比例为pk（k=1,2,…,|y|）,则D的信息熵定义为：
End(D)的值越小，则D的纯度越高。
信息增益”information gain:用离散属性a有V个可能取值{a1,a2,…,aV}对样本集D进行划分,其中第v个分支结点包含了D在属性a上取值为av的样本，记为
。所获得的“信息增益”：
一般而言，信息增益越大，使用属性a来进行划分所获得的“纯度提升”越大。ID3决策树学习算法就是以信息增益为准则来选择划分属性。
接下来用西瓜数据集来详细解释这些概念
以属性“色泽”为例：有3个可能取值{青绿、乌黑、浅白}，用该属性对D进行划分，可以得到3个子集D1(色泽=青绿),D2(色泽=乌黑)，D3(色泽=浅白)。
D1包含编号{1,4,6,10,13,17}六个样例，正例占p1=3/6，反例占p2=3/6；
D2包含编号{2,3,7,8,9,15}六个样例，正例占p1=4/6，反例占p2=2/6；
D3包含编号{5,11,12,14,16}五个样例，正例占p1=1/5，反例占p2=4/5；
三个分支的信息熵分别为：
Ent(D1)=-(3/6log23/6+3/6log23/6)=1.000
Ent(D2)=-(4/6log24/6+2/6log22/6)=0.918
Ent(D3)=-(1/5log21/5+4/5log24/5)=0.772
属性“色泽”的信息增益为：
其他属性信息属性增益为：
Gain(D,根蒂)=0.143; Gain(D,敲声)=0.141;
Gain(D,纹理)=0.381; Gain(D,脐部)=0.289;
Gain(D,触感)=0.006;
属性“纹理”的信息增益最大，于是被选为划分属性。划分结果如下：
决策树学习算法将对每个分支结点做进一步划分
当然ID3算法是有问题的：
如果使得每个样例的编号作为属性，每个分支有一个样本，这些分支结点的纯度已达到最大，但是这样的决策树不具有泛化能力，无法对新样本进行有效预测，信息增益准则对可取值数目较多的属性有所偏好。
著名的C4.5决策树算法使用“增益率”gain ratio来选择最优划分属性。下面来简单介绍C4.5算法
相关概念
“增益率”gain ratio：
其中
称为属性a的“固有值”。属性a的可能取值越多（V越大），IV(a)的值通常越大，IV(触感)=0.874(v=2);IV(色泽)=1.580(v=3)；IV(编号)=4.008(v=17)。
增益率准则对可取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选取增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
接下来对我们的这棵树进行剪枝处理
“剪枝”是决策树学习算法对付“过拟合”的主要手段。
在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，造成决策树分支过多，这时就可能因训练样本学的“太好”了，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过拟合。
决策树剪枝的基本策略有“预剪枝”和“后剪枝”
同样，对喜瓜数据集进行讨论，红色的作为验证集，黑色作为测试集：
未剪枝决策树
该决策树的验证集精度为：42.9%
预剪枝：
预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
假设在脐部不划分：直接把其标记成叶节点，那么{4,5,8}是划分对的，验证集精度：3/7
划分后：将凹陷、稍凹记为好瓜，平坦记为坏瓜{4,5,8,11,12}划分正确，验证集精度：5/7
故，划分得以确定，预剪枝决策：划分
然后，决策树算法对结点2进行划分，基于信息增益准则，挑选“色泽”属性。划分后发现{5}由正确转换为错误，验证集精度下降为57.1%。
故，预剪枝决策：禁止被划分。
后剪枝：
后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
先考察结点6，若把结点6当做叶节点，叶节点类别标为“好瓜”，替换后叶节点包含{7，,1}，此时决策树的验证精度提升至57.1%，故，后剪枝决策决定：剪枝。
再考察结点5，，将其作为叶子结点，替换后叶节点包含编号{6,7,15}，叶节点类别标记为“好瓜”，此时决策树验证集精度仍未：57.1%，故，后剪枝决策决定：不剪枝。
两种剪枝的优缺点：
优点：
后剪枝决策树通常比预剪枝决策树保留了更多分支。一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于与剪枝决策树。
缺点：
但是后剪枝序是在生成完全决策树之后进行的，并且要自底向上地对树中所有非叶结点进行逐一考察，因此训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
python代码实现可参考
https://www.cnblogs.com/MrLJC/p/4099404.html
决策树内容就先告一段落了，谢谢浏览。