今天写决策树的第一篇文章。
首先对决策树有个感性的认识，类似于Galgame每个选择会导致不同分支，进而导致不同结局一样，决策树的本质就是构造一棵类似Galgame的选择树，使得在每一个节点，可以通过所输入特征的不同表现将不同的类甄别出来。这是一个分类算法。可以将决策树转化为一个if-then规则的集合
决策树的要素：
非叶子结点：判断模块（decision block）用长方形表示
叶子节点：终止模块（terminating block）用椭圆形表示
分支：分支（branch）用箭头表示，在线上搭载了进入该子节点的信息
Definition：分类决策树是一种描述对实例进行分类的树形结构。
决策树学习：
决策树学习本质上是从训练数据集中归纳出一种规则。我们需要的是一个和训练数据矛盾较小的决策树，同时其应该具有很好的泛化能力。
假设给定一系列训练数据集
其中表示输入实例，
为类标记，i=1，2，...，N，N为样本容量。
学习的目标是构建一个决策树模型对实例进行归类
决策树的算法优劣性分析：
优点：计算时空复杂度不高，输出结果易理解，对特征缺失不敏感，可以不进行特征处理
缺点：出现过拟合（Overfitting）问题
留坑：时间复杂性分析
基于离散属性的决策树的算法过程：(IO3 Algorithm)//不完全采用二分法
伪代码：
node CreateNode(dataSet，node)：
if all data in dataSet belongs to the same Label//已经分类完成
return node
else
chooseBestFeatureToSplit//如果要剪枝，在这里剪信息增益占原信息的比
newnode[]=splitDataSet
for subDataSet in dataSet//递归建树
CreateNode(subDataSet，newnode)
return node;
六步法运用算法：
（1）收集数据
（2）准备数据：需要对离散数据进行离散化
（3）分析数据：正常
（4）训练算法：基于验证集构造一棵经验树
（5）测试算法：使用经验树，计算错误率
（6）使用算法
怎么划分数据集：
我们需要让无序的数据变得更加有序。衡量数据集混乱程度的定量特征有三个：
用表示分成的类数，
表示每一类出现的概率。
熵（entropy）
条件熵(conditional entropy)
当熵和条件熵是由数据估计得到的时候，所对应的熵称作经验熵（empirical entropy)和经验条件熵（empirical conditional entropy)
信息增益(informatioan gain)表示已知一个特征的信息而使得类的信息的不确定的减少程度
考虑一个特征和训练集
，
对
的信息增益定义为集合D的经验熵
和特征A给定的经验条件熵
之差
决策树中的信息增益等价于训练数据集中类和特征的互信息。
基尼不纯度（Gini impurity）（常用于基于连续属性的决策树衡量）
分类误差率（常用于基于连续属性的决策树衡量）
注意：可以进行多分类，也可以合并一些类，进行二分类。如果这些类彼此不相关，则没有问题。如果类之间有序数关系（高收入、中等收入、低收入）应该注意同一个选择分支中的类应该要相连。
信息增益算法和信息增益比算法
训练集，K 个类
，特征
有n个不同的取值，并记
输入数据集，特征
，输出信息增益
empirical entropy:
empirical conditional entropy:
information gain:
information gain ratio: while
C4.5和ID3使用不同的衡量标准选择特征，ID3用信息增益衡量特征，会偏向于数据多的特征。C4.5用信息比增益衡量选择特征，可以进行一定矫正。
决策树的代价函数和剪枝问题
决策树如果不进行剪枝，在数据量很大而具有噪音的时候，不可避免地会出现overfit的问题。
决策树剪枝的算法有很多，以下介绍基于验证集精度和划分的。
第一种方法（预剪枝或后剪枝）是基于验证结合精度的算法。
预剪枝算法：
在分类的过程中，先假设不对节点分类，先用举手表决计算验证集精度。
分类之后，我们继续举手表决计算分成子集之后的验证集合精度，若没有提升，则不再分类。若有提升，递归下去进行分类。
预剪枝会避免决策树很多分支的展开，降低过拟合的风险，显著地减少了决策树的训练时间开销和测试时间开销。
但是我们注意到，有的分支当下的展开虽然没有很大的影响，但是在之后的分支中可能会产生很大的影响。这是一个贪心策略，不一定对应全局最优，有一定的风险导致欠拟合。
后剪枝算法：
先生成决策树再考虑叶子节点如果缩回去，精度是否有提升进而决定是否剪枝。直到无法剪枝递归过程结束
第二种方法是基于叶子结点个数和信息熵（其实要考虑层数也是可以），进而构造一个决策树算法的loss function，设计一个剪枝算法，也属于后剪枝。
考虑一棵树的叶节点个数
,
是
的叶节点，该叶节点有
个样本点，其中第
类的样本点有
个，
是叶节点
的经验熵，
是个参数，定义决策树学习的损失函数：
我们用表示模型对训练数据的预测误差
注意到这里叶子结点越多，损失函数越大。
其中的经验熵可以表示为：
也就是每个结点的熵的和。
剪枝算法：
输入：生成算法产生的树，参数
，输出修剪后的子树
：
（1）计算每个结点的经验熵；
（2）尝试递归从叶子缩回，如果回缩使得损失函数减小，则进行剪枝，将父节点变为新结点；
（3）递归直到不能继续为止。
