基本流程
决策树是异类常见的机器学习方法，以二分类任务为例，我们希望从给定训练数据集学得一个模型以对新示例进行分类，决策树是基于树的结构进行决策的。
一般地，一颗决策树包含一个根节点，若干个内部节点和若干个叶节点，叶节点对应于决策结果，其他各个节点则对应于下一个属性测试。
算法原理
从逻辑角度，一堆if else语句的组合
从几何角度，根据某种准则划分特征空间
最终目的：将样本越分越纯
- 信息增益
“信息熵”是度量样本集合纯度最常用的一个指标
E n t ( D ) = − ∑ K = 1 N p k l o g 2 p k Ent(D)=-\displaystyle\sum_{K=1}^Np_klog_2p_k Ent(D)=−K=1∑Npklog2pk
信息熵的值越小，D的纯度越高
信息增益
G a i n ( D , a ) = E n t ( D ) − ∑ K = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a)=Ent(D)-\displaystyle\sum_{K=1}^V\frac{|D^v|}{|D|} Ent(D^v) Gain(D,a)=Ent(D)−K=1∑V∣D∣∣Dv∣Ent(Dv)
一般而言，信息增益越大，则意味着使用属性a来进行划分所得到的的“纯度提升”越大。因此，我们可以用信息增益来进行决策树的划分 - 增益率
信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能所带来的的影响，C4.5决策树算法使用信息增益率来选择最优划分
G a i n − r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) Gain_-ratio(D,a)=\frac{Gain(D,a)}{IV(a)} Gain−ratio(D,a)=IV(a)Gain(D,a)
其中
I V ( a ) = − ∑ K = 1 V ∣ D v ∣ ∣ D ∣ l o g 2 ∣ D v ∣ ∣ D ∣ IV(a)=-\displaystyle\sum_{K=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|} IV(a)=−K=1∑V∣D∣∣Dv∣log2∣D∣∣Dv∣
称为属性a的"固有值"，属性a的可能取值越多，IV(a)的值通常越大。增益准则对可取值数目较少的属性有所偏好。因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是直接使用一个启发式算法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最大的。 - 基尼指数
CART决策树使用“基尼指数”来选择划分属性，数据集D的纯度可以用基尼值来度量
G i n i ( D ) = 1 − ∑ k = 1 V p k 2 Gini(D)=1-\displaystyle\sum_{k=1}^Vp_k^2 Gini(D)=1−k=1∑Vpk2
直观来说，基尼指数反映了从数据集中随机选取两个样本，其类别标记不一样的概率，因此，基尼指数越小，数据集的纯度越高
G i n i − i n d e x ( D , a ) = ∑ k = 1 V ∣ D v ∣ ∣ D ∣ G i n i ( D v ) Gini_-index(D,a)=\displaystyle\sum_{k=1}^V\frac{|D^v|}{|D|}Gini(D^v) Gini−index(D,a)=k=1∑V∣D∣∣Dv∣Gini(Dv)
于是，我们可以在候选属性集合A中，选择那个使得划分之后基尼指数最小的属性作为最优划分属性即可。
剪枝处理
剪枝是决策树学习算法对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类样本，结点划分过程将不断重复，有时候会造成决策树分支过多，以至于吧训练集自身的一些特点当做所有数据具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。
决策树剪枝的基本策略有“预剪枝”和后剪枝。
-
预剪枝
是指在决策树生成过程中，对每个点在划分前先进行分析，若当前结点划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶节点。
在数据集中留出来一部分作为验证集
在划分之前对比划分之后和未划分的精度，再决定要不要huafeb -
后剪枝
后剪枝先在训练集中生成一个决策树，然后从底向上来对比划分前后的精度 -
比较
后剪枝通常比预剪枝决策树保留了更多的分支，后剪枝决策树欠拟合风险很小，泛化性能往往优于预剪枝决策树，但是后剪枝是在完全生成决策之后记性，并且要自底向上地对树中所有叶节点进行逐一考察。