一、决策树
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型：内部结点(internal node )和叶结点(leaf node)。内部结点表示一个特征或属性，叶结点表示一个类。（简单说就是用我们熟悉的树结构去做回归和分类）
学习时， 利用训练数据， 根据损失函数最小化的原则建立决策树模型。 预测时， 对新的数据， 利用决策树模型进行分类。 决策树学习通常包括3个步骤： 特征选择、决策树的生成和决策树的修剪。
与决策树相关的重要算法包括：CLS，ID3、 C4.5与CART。
决策树的基本组成部分：决策结点、分支、叶子
决策树中最上面的节点称为根结点。是整个决策树的开始，每个分支是一个新的决策节点，或者是树的叶子。每个决策结点代表一个问题或者决策。通常对应待分类对象的属性。每个叶结点代表一种可能的分类结果。
在沿着决策树从上到下遍历过程中，在每个节点都有一个测试。对每个结点上问题的不同测试输出导致不同的分歧，最后会打到一个叶子结点。这一过程就是利用决策树进行分类的过程，利用若干个变量来判断属性的类别
决策树与条件概率分布
决策树还表示给定特征条件下类的条件概率分布。
条件概率分布定义在特征空间的一个划分上，将特征空间划分为互不相交的单元或区域，并在每个单元定义的一个类的概率分布就构成了一个条件概率分布。
决策树的一条路径对应于划分中的一个单元。
决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。这个条件概率分布可以表示为P(Y|X)。 X取值于给定划分下单元的集合， Y取值于类的集合。 各叶结点（单元） 上的条件概率往往偏向某一个类， 即属于某一类的概率较大。 决策树分类时将该结点的实例强行分到条件概率大的那一类去。
决策树学习
- 决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树
- 能对训练数据进行正确分类的决策树可能有多个，也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。
- 决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个
- 我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。
决策树学习的策略：以损失函数为目标函数的最小化
二、决策树算法
决策树的学习算法分为三步：首先递归的选择特征、用选择的特征构造一个决策树、解决过拟合进行决策树剪枝。
1、特征选择
特征选择问题：特征选择在于选取对训练数据具有分类能力的特征。通常特征选择的准则是信息增益或信息增益比。
（1）信息增益：
熵：信息量大小的独立，即表示随机变量不确定性的度量。
假设有n个互不相容的时间a1,a2,a3,...,an,他们中有且仅有一个发生，则其平均的信息量（熵）可以如下度量：
熵越大，随机变量的不确定性越大，从定义可验证。
设有随机变量(X,Y)， 其联合概率分布为
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。 随机变量X给定的条件下随机变量Y的条件熵（conditionalentropy） H(Y|X)， 定义为X给定条件下Y的条件概率分布的熵对X的数学期望：
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵
信息增益：
特征A对训练数据集D的信息增益g(D,A)， 定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差， 即
信息增益表示得知特征X的信息而使得类Y 的信息的不确定性减少的程度
一般地，熵H(Y)与条件熵H(Y|X)之差称为互信息
决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
信息增益的算法
（2）信息增益比
特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比：
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，使用信息增益比可以对这一问题进行校正
2、决策树的生成
（1）ID3算法
ID3算法的核心：是在决策树各个结点上应用信息增益准则选择特征， 递归地构建决策树。
** 具体方法是：** 从根结点（root node） 开始，对结点计算所有可能的特征的信息增益， 选择信息增益最大的特征作为结点的特征， 由该特征的不同取值建立子结点； 再对子结点递归地调用以上方法， 构建决策树； 直到所有特征的信息增益均很小或没有特征可以选择为止。 最后得到一个决策树。
基本思想：以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变为最小的属性，以构造一颗熵值下降最快的决策树，到叶子节点处的熵值为0，此时每个叶子节点对应的实例集中的实例属于同一类。
（2）C4.5的生成算法
用信息增益比来选择特征。
（3）决策树的枝剪
决策树生成算法递归地产生决策树， 直到不能继续下去为止。 但这种操作容易造成过拟合现象。
过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类， 从而构建出过于复杂的决策树。 解决这个问题的办法是考虑决策树的复杂度， 对已生成的决策树进行简化 。
在决策树学习中将已生成的树进行简化的过程称为剪枝（pruning） 。 具体地， 剪枝从已生成的树上裁掉一些子树或叶结点， 并将其根结点或父结点作为新的叶结点， 从而简化分类树模型。
决策树学习的剪枝算法：
（4）CART算法
CART算法由两部分组成：
- 决策树生成
- 决策树剪枝
回归树(目标变量是连续的)：平方误差最小化
分类树(目标变量是类别的)：Gini Index
CART与ID3不同
二元划分：二叉树不易产生数据碎片，精度往往也会高于多叉树
CART中选择变量的不纯性独立：
分类目标：Gini指标，Towing、orderTowing
连续目标：最小平方残差、最小绝对残差
剪枝：用预剪枝或后剪枝对训练集生长的树进行剪枝
树的建立：
如果目标变量是标称的，并且是具有两个以上类别，则CART可能考虑将目标类别合并成两个超类别（双化）；
如果目标变量是连续的，则CART算法找出一组基于树的回归方程来预测目标变量
CART的生成：
1、回归树的生成
如何对输入空间进行划分？
最小二乘回归树生成算法
2、分类树的生成
基尼指数：
CART生成算法
CART剪枝
两步组成：
- 从生成算法产生的决策树T0底端开始不断剪枝，直到T0的根结点，形成一个子树序列{T0,T1...Tn}
- 通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树
1、剪枝，形成一个子树序列
2、在剪枝得到的子树序列{T0,T1...Tn}中通过交叉验证选取最优子树Ta.
利用独立的验证数据集，测试子树序列中各子树的平方误差或基尼指数，最小的决策树就是最优决策树。
CART剪枝算法：
