本次学习我们将详细介绍什么是CART决策树算法，以及它的前身ID3算法。介绍所涉及到的概念，算法的原理和步骤。
一、介绍ID3算法
1、概念
信息熵：
用来度量一个属性的信息量。
假定S为训练集，S的目标属性C具有m个可能的类标号值，$C={C_1,C_2,…,C_m}$，假定训练集S中，$C_i$在所有样本中出现的频率为$P_i(i=1,2,3,…,m)$，则该训练集S所包含的信息熵定义为：
$$Entropy(S = Entropy(p_i,p_2,…,p_m) = -{\sum_{i=1}^m}{p_ilog_2p_i}$$
熵越小表示样本对目标属性的分布越纯，反之熵越大表示样本对目标属性分布越混乱。
信息增益：
信息增益是划分前呀根本数据的熵和划分后样本数据集的熵的差值
假设划分前样本数据集为S，并用属性A来划分样本集S，则按属性A划分S的信息增益$Gain(S,A)$为样本集S的熵减去按属性A划分S后的样本自己的熵：
$$Gain(S,A)=Entropy(S)-Entropy_A(S)$$
按属性A划分S后的样本自己的熵定义如下：假定属性A有k个不同的取值，从而将S划分为k个样本子集${S_1,S_2,…,S_k}$，则按属性A划分S后的样本子集的信息熵为：
$$Entropy_A(S)={\sum_{i=1}^k}\frac{|S_i|}{|S|}Entropy(S_i)$$
其中$|S_i|(i=1,2,…,k)$为样本子集$S_i$中包含的样本数，$|S|$为样本集S中包含的样本数。信息增益越大，说明使用属性A划分后的样本子集越纯，越有利于分类。
问题：用哪个属性最适合充当根节点？答：选择信息增益最大的。
2、ID3算法步骤
ID3算法的具体详细实现步骤如下。
1）对当前样本集合，计算所有属性的信息增益；
2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同一个子样本集；
3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处；否则对子样本集递归调用本算法。
其核心是在决策树的各级节点上，使用信息增益方法作为属性的选择标准，来帮助确定生成每个节点时所应采用的合适属性。即选择合适的属性节点及其顺序来构建决策树。
二、CART决策树
1、理解
它既是回归树，又是分类树，但它是二叉树。ID3只能分类。
CART算法是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子节点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能选择“是”或者“否”，即使一个feature有多个取值，也就是把数据分为两部分。在CART算法中主要分为两个步骤：
（1）将样本递归划分进行建树的过程
（2）用验证数据进行剪枝
2、建树原理
1、如何进行划分
属性是按照顺序一层层，着重划分属性值，注意，这里选的是属性值，而不是选属性。
设$x_1,x_2,…x_n$代表单个样本的$n$个属性，$y$表示所属类别。CART算法通过递归的方式将n维的空间划分为不重叠的矩形，划分步骤大致如下：
（1）选一个自变量$x_i$，再选取$x_i$的一个值$v_i$，$v_i$把$n$维空间划分为两部分，一部分的所有点都满足$x_i{\leq}v_i$，另一部分的所有点满足$x_i>v_i$，对非连续变量来说属性值的取值只有两个，即等于该值或不等于该值。
（2）递归处理，将上面得到的两部分按照步骤（1）重新选取一个属性继续划分，知道把整个$n$维空间都划分完。
2、按照什么标准来划分？
每个属性的划分按照能减少的杂质的量来进行排序，而杂质的减少量定义为划分前的杂质减去划分后的每个节点的杂质量划分所占比率之和。而杂质度量方法常用$Gini指标$，假设一个样本Y共有C类，那么一个节点A（属性的某个确定值）的Gini不纯度可定义为：
$$Gini(A)=1-\sum_{i=1}^C{p_i^2}$$
其中$p_i$表示属于$i$类的概率，当$Gini(A=0$时，所有样本属于同类；
所有类在节点中以等概率出现时，$Gini(A)$最大化，此时等于$\frac{C(C-1)}{2}$。
我们选最小的Gini作为节点
$$Gini(M)=\frac{|A|}{|Y|}Gini(A)+\frac{|B|}{|Y|}Gini(B)$$
其中，Y表示样本总数，A，B是属性M的两个值
3、剪枝
1、为什么要剪枝
原因是避免决策树过拟合（Overfitting）样本。前面的算法生成的决策树非常详细并且庞大，每个属性都被详细地加以考虑，决策树的叶子节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进行分类的话，你会发现对于训练样本而言，这个树表现很好，误差率极低且能够正确的对训练样本集中的样本进行分类。训练样本中的错误数据也会被决策树学习，成为决策树的部分，但是对于测试数据的表现就没有想象的那么好，或者极差，这就是所谓的过拟合问题。在数据集中，过拟合的决策树的错误率比经过简化的决策树的错误率要高。
2、剪枝原理
CART算法用的是Cost complexity prune
$T(i+1)$总是从$Ti$生成。
