决策树

基本流程

决策树学习的目的是为了产生一颗泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”(divide-and-conquer)策略，如下所示：

• 决策树的关键在于当前状态下选择哪个属性作为分类条件(即划分选择)。
• 最佳分类属性这种“最佳性”可以用非纯度（impurity）进行衡量。
• 如果一个数据集合中只有一种分类结果，则该集合最纯，即一致性好
• 有许多分类，则不纯，即一致性不好

划分选择

1.ID3(信息增益)：分类

信息熵(information entropy)是度量样本集合纯度最常用的一种指标。假定当前样本集合$D$D中第$k$k类样本所占的比例为$p_k(k=1,2,\cdots,\begin{vmatrix}y\end{vmatrix})$pk​(k=1,2,⋯,∣∣​y​∣∣​)，这里的$\begin{vmatrix}y\end{vmatrix}$∣∣​y​∣∣​标示样本类别总数，即标签(labels)总数，则$D$D的信息增益熵定义为：
$Ent(D)=-\sum_{k=1}^{\begin{vmatrix}y\end{vmatrix}} p_klog_2p_k$Ent(D)=−k=1∑∣y​∣​pk​log2​pk​
$Ent(D)$Ent(D)的值越小，则$D$D的纯度越高。

假定离散属性$a$a有$V$V个可能的取值$\{a^1,a^2,\cdots,a^V\}${a1,a2,⋯,aV}(注意：这里指的是数据中的某一个特征，以及该特征的具体值)，若使用$a$a来对样本集$D$D进行划分，则会产生$V$V个分支节点，其中第$v$v个分支节点包含了$D$D中所有在属性$a$a上取值为$a^v$av的样本，记为$D^v$Dv。在通过上述公式计算出该分支样本的信息熵，由于各个分支节点数的样本不平均，需要给分支结点分配相对于的权重$\begin{vmatrix}D^v\end{vmatrix}/\begin{vmatrix}D\end{vmatrix}$∣∣​Dv​∣∣​/∣∣​D​∣∣​。由此可得到信息增益(information gain):
$Gain(D,a)=Ent(D)-\sum_{v=1}^{V} \frac{\begin{vmatrix}D^v\end{vmatrix}}{\begin{vmatrix}D\end{vmatrix}}Ent(D^v)$Gain(D,a)=Ent(D)−v=1∑V​∣∣​D​∣∣​∣∣​Dv​∣∣​​Ent(Dv)

一般而言，信息增益越大，则意味着使用属性$a$a来进行划分所获得的“纯度提升”越大

2.C4.5(信息增益比)：分类

ID3的信息增益存在一个缺点：一般会优先选择有较多属性值的特征。

解决方案：增加惩罚项，C4.5使用信息增益比率(gain ratio)
$Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)},$Gainr​atio(D,a)=IV(a)Gain(D,a)​,
其中
$IV(a)=-\sum_{v=1}^{V} \frac{\begin{vmatrix}D^v\end{vmatrix}}{\begin{vmatrix}D\end{vmatrix}}log_2\frac{\begin{vmatrix}D^v\end{vmatrix}}{\begin{vmatrix}D\end{vmatrix}}$IV(a)=−v=1∑V​∣∣​D​∣∣​∣∣​Dv​∣∣​​log2​∣∣​D​∣∣​∣∣​Dv​∣∣​​
称为属性$a$a的“固有值”，该值描述了$a$a特征中不同特征值数目的大小，数目越多，则$IV(a)$IV(a)越大。

增益率准则是对可取值数目较少的属性有所偏好，因此，C4.5算法是先从候选划分属性中找出信息增益率高与平均水平的属性，再从中选择增益率最高的。

3.CART(GINI系数)：分类与回归

数据集$D$D的纯度可用基尼值来度量：
$\begin{aligned} Gini(D)& =\sum_{k=1}^{\begin{vmatrix}y\end{vmatrix}}\sum_{k'\ne k}p_kp_{k'} \\ & = 1-\sum_{k=1}^{\begin{vmatrix}y\end{vmatrix}}p^2_k \\ \end{aligned}$Gini(D)​=k=1∑∣y​∣​k′​=k∑​pk​pk′​=1−k=1∑∣y​∣​pk2​​
$Gini(D)$Gini(D)越小，则数据集$D$D的纯度越高。

属性$a$a的基尼指数(Gini index)定义为：
$Gini_index(D,a)=\sum_{v=1}^{V} \frac{\begin{vmatrix}D^v\end{vmatrix}}{\begin{vmatrix}D\end{vmatrix}}$Ginii​ndex(D,a)=v=1∑V​∣∣​D​∣∣​∣∣​Dv​∣∣​​
选择使得划分后基尼指数最小的属性作为最优划分属性。

剪枝算法

预剪枝

• 在构造决策树的同时进行剪枝。
• 所有决策树的构建方法，都是在无法进一步降低熵的情况下才会停止创建分支的过程，
  为了避免过拟合，可以设定一个阈值。
• 例如：熵减小的数量小于这个阈值，即使还可以继续降低熵，也停止继续创建分支。

后剪枝

• 决策树构造完成后进行剪枝。
• 剪枝的过程是对拥有同样父节点的一组节点进行检查，判断如果将其合并，熵的增加
  量是否小于某一阈值。
• 如果满足阈值要求，则这一组节点可以合并一个节点，其中包含了所有可能的结果。
• 示例：???????????????????????????? − ???????????????????? ???????????????????????????? (????????????)错误率降低剪枝
  • 思路：决策树过度拟合后，通过测试数据集来纠正。
  • 步骤：
    1. 对于完树中每一个非叶子节点的子树，尝试着把它替换成一个叶子节点
    2. 该叶子节点的类别用子树覆盖训练样本中存在最多的那个类来代替，产生简化决策树
    3. 然后比较这两个决策树在测试数据集中的表现
    4. 简化决策树在测试数据集中的错误比较少，那么该子树就可以替换成叶子节点
    5. 以bottom-up的方式遍历所有的子树，当没有任何子树可以替换提升，算法终止

随机森林

基本流程

• 随机森林以随机的方式建立一个森林
• 森林里有很多决策树，且每棵树之间无关联
• 当有一个新样本进入后，让森林中每棵决策树分别各自独立判断，看这个样
  本应该属于哪一类（分类算法）
• 然后看哪一类被选择最多，就选择预测此样本为那一类

Out of bag error (OOBE)

• 关于oob的解释，stackoverflow上有比较全面的解释：OOB的解释

  • RF需要从原始的特征集中随机sampling，然后去分裂生成单颗树.

  • 每个树的训练样本是从原始的训练集boostraping而来.

  • 由于boostraping的有放回抽样方式，导致每个树的训练集合不同且只是原始训练集的一个部分.

  • 对于第t个树来说，原始训练集中那些不在第t个树的训练集的数据，可以使用第t个树来进行test.

  • 现在生成n(n是原始数据集的大小)个树，每个树的训练样本大小为n-1，对第i个树来说其训练集不包含(xi,yi)这个样本.

  • 使用不包含(xi,yi)这个样本的所有的树(n-1个)，vote的结果作为最终(xi，yi)这个样本的test结果.

    参考博客:Out of bag error in Random Forest

优缺点

• 优点：
  1. 适用数据集广
  2. 高维数据
  3. Feature重要性排序
  4. 训练速度快，并行化
• 缺点：
  1. 级别划分较多的属性影响大

boost算法

• 决策树：单决策树时间复杂度较低，模型容易展示，但是容易过拟合（Over-Fitting）
  • 分类树
  • 回归树
• 决策树的????????????????????方法：迭代过程，新的训练为了改进上一次的结果
  • 传统????????????????????: 对正确、错误的样本进行加权，每一步结束后，增加分错点的权重，减少对分
    对点的权重
  • ????????????????????????????????????????????????????：梯度迭代，每一次建立模型是在之前建立的模型损失函数的梯度下降方向

Adaboost算法

• Adaboost的核心思想
  • 关注被错分的样本，器重性能好的分类器
• 如何实现
  • 不同的训练集 -> 调整样本权重
  • 关注 -> 增加错分样本权重
  • 器重 -> 好的分类器权重大
  • 样本权重间接影响分类器权重
• 算法实例：
  
  由图可以看出第一次训练中，存在三个错误值（被圈出），在第二次训练前加强上述错误值的权重，再进行训练，以此类推。循环T次训练，T为人工选取次数。

GBDT(Gradient Boosting Decision Tree)算法

• 用一个初始值来学习一棵决策树，叶子处可以得到预测的值，以及预测之
  后的残差，然后后面的决策树就要基于前面决策树的残差来学习，直到预
  测值和真实值的残差为零。
• 最后对于测试样本的预测值，就是前面许多棵决策树预测值的累加。
• 优点：
  • 适用问题广，可扩展性好（万金油算法）
  • 几乎可以用于所有回归问题（线性、非线性）
  • 常用于各大数据挖掘竞赛
• 实例：
  
• Random Forest VS GBDT：
  • 准确度：树少时，GBDT > RF
  • 拟合：RF容易欠拟合， GBDT容易过拟合
  • 建模能力：GBDT > RF，因为因为boosted trees是通过优化目标函数得出的，所以基本上可以用于解决几乎所有可以写出梯度的目标。
  • 并行化：GBDT < RF,由于随机森林可以并行运行，因此可以轻松地以分布式方式进行部署，而Gradient Boosted Machines只能在多个实验之间进行。

XGBoost

• Boosting分类器将成百上千个分类准确率较低的树模型组合起来，成为一个
  准确率很高的模型。
• 数据集较大较复杂的时候，我们可能需要几千次迭代运算，这将造成巨大的
  计算瓶颈。
• XGBoost正是为了解决这个瓶颈而提出。单机它采用多线程来加速树的构建，
  并可以进行分布式计算。
• XGBoost提供了 Python和R语言接口。

集成学习

Bagging

让该学习算法训练多轮，每轮的训练集由从初始的训练集中随机取出的n个训练样本组
成，某个初始训练样本在某轮训练集中可以出现多次或根本不出现，训练之后可得到一个预
测函数序列$h_1,\cdots,h_n$h1​,⋯,hn​，最终的预测函数H对分类问题采用投票方式，对回归问题采用简单平均方法对新示例进行判别。

Boosting

• 初始化时对每一个训练例赋相等的权重$\frac{1}{n}$n1​
• 然后用该学算法对训练集训练$t$t轮
• 每次训练后，对训练失败的训练例赋以较大的权重，也就是让学习算法在后续的学习中集中对比较难的训练例进行学习，从而得到一个预测函数序列$h_1,\cdots,h_n$h1​,⋯,hn​, 其中$h_i$hi​也有一定的权重，预测效果好的预测函数权重较大，反之较小。
• 最终的预测函数H对分类问题采用有权重的投票方式，对回归问题采用加权平均的方法对新示例进行判别。

不难看出Adaboost类似于Bagging和Bossting的综合

Stacking

• 将训练好的所有基模型对训练基进行预测，第????个基模型对第????个训练样本的预测值将作为新的训练集中第????个样本的第????个特征值，最后基于新的训练集进行训练。
• 同理，预测的过程也要先经过所有基模型的预测形成新的测试集，最后再对测试集进行预测