决策树 Decision Tree
决策树是一个有监督的分类算法，在每次分裂中都找到最容易区分一个集合和另一个集合的特征。
在寻找最优特征时，DT算法保证了局部最优，但整体上看不一定是全局最优。
一、目标 target
因为决策树是一个有监督的算法，所以样本已经有一个变量用来表征这个样本的target，可能是正例/反例，也可以是多个类别（比如高/中/低）
二、模型输入 model input
在实际应用中，无论是离散特征还是连续特征，其实都可以用DT模型，但是处理方法略有不同
离散特征：
无序类别特征
有序类别特征， 通常会用数字代替特征，有序体现在顺序上
连续特征：连续变量
样本有限的时候，其实采样数据在特征上的取值仍然是离散的（数值非常多，可以理解为连续变量），如果考虑每个数值作为一个类别进行分析，计算量过大。
因此，可以根据这个连续变量的分布，选择几个数值对数据进行分类，有两种方法推荐：
（1）根据变量的分布，选取几个位置对数据分类。 比如根据25% 和75%的值，将连续特征划分为低/中/高等，数字可以为1/2/3
优点：计算简单
缺点：分隔位置也许不是最佳的分隔位置
（2）对特征取值进行排序，选择两个特征值的中点（选择特征值也可以）作为可能的分裂点，分隔数据，通过某些指标（比如信息增益）的比较选取最优的分裂点。
如果是分成两个特征，只需要选取一个最佳分裂点即可，如果分成多个特征，可以用嵌套循环的方式（先确定一个最佳分裂点，在每个分组中再选择最佳分裂点）
优点：分割位置最优
缺点：计算复杂
注意：
1. 如果希望分成二叉树，但是特征的类别>=3，在进行样本分类时，对无序变量和有序变量需要进行不同的处理
- 无序特征---根据样本是否等于某个类别将所有样本划分成两组e.g. 对于西瓜形状，一共有“圆”，“扁”，“方”三种分类，在进行分类的时候会根据“是否圆”“是否扁”“是否方”进行三次指标计算。
- 有序特征---根据样本是否小于等于某个类别将所有样本划分成两组e.g. 对于西瓜重量，一共有“低”，“中”，“高”三种类别，用数字“1”，“2”，“3”来进行代替。在分类的时候会根据“是否≤1”“是否≤2”“是否≤3”来进行三次指标计算
2. 如果希望分成多叉树，那么DT算法的样本分类主需要选择最合适的特征进行指标计算，不需要根据特征内的类别进行多次的指标计算了
e.g 对于西瓜形状，一共有“圆”，“扁”，“方”三种分类，会分成三叉树，计算一次指标即可
三、 决策树算法的流程：
（1）特征选择
（2）决策树生成
（3）剪枝（防止过拟合)
（1）特征选择
说了这么多，通常模型输入都有很多个特征，每个特征又有多个类别，怎么知道哪个特征哪个分割点比较好呢？
常用的有三种指标方法：
1）信息增益---ID3算法
信息增益运用了信息熵（越大，不确定越大，纯度越低）的概念
假设目标有|y|个类别，特征a有V个可能的取值{a1,a2,...,av} ，可以将数据D划分为V个节点，每个节点中应该有多个目标类别（≤|y|）。
计算出D以及每个节点中的信息熵：
计算属性a对样本集D进行划分所得到的信息增益（information gain):
注意：如果是二叉树，每个特征的每个节点都会进行一次分类，计算一次信息增益，所以最终进行比较时，既有不同特征之间的比较，又有同一特征不同分裂点的比较
缺点：倾向去取可取值数目较多的特征（对于二叉树，没有这个问题；而对于多叉树，这个问题存在）
从信息熵的公式可以看出，当V比较大时，每个分支中的样本纯度会相对更高，信息熵更低，信息增益更大
2）增益率 Gain Ratio---C4.5算法
为了解决信息增益偏向于可取值数目较多的特征的缺陷，出现了Gain_ratio
缺点：倾向于选择可取值数目较少的属性
在C4.5中不是直接选取最大增益率的属性，而是（1）先选取信息增益高于平均水平的属性，（2）再选取增益率最高的属性
3）基尼指数 ---CART（classification and regression tree)算法
求出节点的基尼值：
基尼指数：
越小，说明纯度越高
（2）决策树生成
每次分裂过后，根据节点内的各个类别的样本数目{N1,N2,...,Nn}，决定这个节点的类别，主要有两种情况：
1. max{N1,N2,...,Nn}只有一个时，占比最大的类别就是这个节点的类别
2. max{N1,N2,...,Nn}≥2时，可以随意定义节点类别，或者根据项目需求选择
（3）剪枝
剪枝的目的是为了防止过拟合，泛化能力差，即对于实验数据集分类过于细致，不适用于其他的数据集。
剪枝的时候其实就是比较灵活的了，只要大家觉得有意义就可以啦，业界也有一些常用的方法，列举在下面啦！
主要分成两种剪枝方式：
预剪枝 pre-pruning
在构建DT的同时进行剪枝，剪枝的方法有：
1）设置节点包含的最小样本数---一旦小于这个数值，则停止分裂
2）指定树的高度（深度）---一旦超过这个阈值，则停止分裂
3）指定一个系统增益阈值---一旦对比分裂前后系统性能的增益小于这个阈值，则停止分裂
e.g. 个人觉得信息增益Gain(D,a)就是一个很好的指标，当Gain(D,a) < 阈值，停止分裂；
基尼指数也可以，对比分裂前后的基尼指数差值就可以
优点：算法简单，效率高，适合解决大规模问题
缺点：难以找到合适的阈值得到合适的树结构
后剪枝 post-pruning （常用）
在DT构建结束后，有如下几种剪枝方法：
1）在商业中更多的是结合商业意义进行剪枝 ---个人认为更常用
2）Reduced Error Pruning (REP，错误率降低剪枝）---常用
在训练之初，将数据分成两个部分：训练接和测试集
利用训练集已经定义出分类规则以及每个节点的target类别；将同样的规则应用于测试集。
对于每一个非叶节点：
step1: 删除以此节点为根的子树，并设这个节点为叶节点
step2:计算删除子树前后的验证集精度，剪枝后精度≥剪枝前（或者在可接受范围内），则实行剪枝
验证集精度 =所有叶节点的分类正确样本数/测试集的样本总数 ----具体实例可以参考《机器学习》周志华 4.3节
优点：简单
缺点：倾向于过度修剪，因为一些稀少的特殊类别的样本可能在训练集中出现，在测试集中没有，从而一些叶节点被剪枝
个人认为前面两种方法就足够了，后面的三种方法，之后有时间会在补上的，大家也可以参考这个网页：
3）Pesimistic Error Pruning (PEP, 悲观错误剪枝）
4）Cost Complexity Pruning (CCP, 代价复杂度剪枝）
5）Error Based Pruning (基于错误的剪枝）
四、几种DT算法
1. ID3算法
2. C4.5算法
3. CART算法
CART是classification and regression tree的简称，构成的是二叉树。
主要步骤有两个：
1). 用训练集递归划分建树
- 因为二叉树，所以对于有序离散特征和连续特征，通常利用阈值将特征分成两部分，即x≤a, x>a； 对于无序离散特征，根据是否=/≠分成两组
- 计算每种分组下的Gini指数，最小的即为最佳分裂点 （因此，一个特征如果有多个类别或者多个阈值，是会有多个分组
2.) 用测试集进行剪枝或者根据商业意义进行剪枝