机器学习中的算法决策树与随机森林

原创文章,如需转载请保留出处
本博客为唐宇迪老师python数据分析与机器学习实战课程学习笔记

一. 决策树
1.1 树模型
决策树：从根节点开始一步步走到叶子节点（决策）
所有的数据最终都会落到叶子节点，既可以做分类也可以做回归

1.2 树的组成

• 根节点：第一个选择点
• 非叶子节点与分支：中间过程
• 叶子节点：最终的决策结果

1.3 节点
增加节点相当于在数据中切一刀，节点越多越好吗？

1.4 决策树的训练与测试

• 训练阶段：从给定的训练集构造出来一棵树（从根节点开始选择特征，如何进行特征切分）
• 测试阶段：根据构造出来的树模型从上到下走一遍就好
• 一旦构造好了决策树，那么分类或者预测任务就很简单了，只需要走一遍就好了，那么难点就在于如何构造出来一棵树，这就没那么容易了，需要考虑的问题还有很多的！

1.5 如何切分特征（选择节点）

• 问题：根节点的选择该用哪个特征呢？如何切分？
• 想象一下：我们的目标应该是根节点就像一个老大似的能更好的切分数据（分类的效果更好），根节点下面的节点自然就是二当家的。
• 目标：通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当成根节点，依次类推。

二. 衡量标准-熵
2.1 熵的定义
熵：表示随机变量不确定性的度量。（就是物体内部的混乱程度，比如杂货市场里面什么都有那肯定混乱，专卖店里面只卖一个牌子就稳定的多）（越乱熵值越大）
2.2 熵的公式
公式：H(X) = -∑pi * log pi, i = 1,2,3,……,n
2.3 一个例子
A集合[1，1，1，1，1，1，1，1，2，2]
B集合[1，2，3，4，5，6，7，8，9，1]
显然A集合的熵值要低，因为A里面只有两种类别，相对稳定一些而B中类别太多，熵值就会大很多。（在分类任务中我们希望通过节点分支后数据类别的熵值大还是小呢?）
2.4 熵

• 熵：不确定性越大，得到的熵值也就越大
  当p=0或p=1时，H§=0，随机变量完全没有不确定性
  当p=0.5时，H§=1，随机变量不确定性最大
• 如何决策第一个节点的选择呢？
• 信息增益：表示特征X使得类Y的不确定性减少的程度。（分类后的专一性，希望分类后的结果同类在一起）（信息增益最大的特征作为第一个分类的特征）
  
  三. 决策树构造实例
  3.1 构造实例
• 数据：14天打球情况
• 特征：4种环境变化
• 目标：构造决策树
  
  3.2 构造实例-划分特征
• 划分方式：4种
• 问题：谁当根节点？
• 依据：信息增益
  
• 在历史数据中(14天)有9天打球，5天不打球，所以此时的熵应为：
  -9/14log₂9/14 - 5/14log₂5/14 = 0.940
  -（基于天气划分） 4个特征逐一分析，先从outlook特征开始：
  Outlook = sunny时，熵值为0.971
  （ -2/5log₂2/5 - 3/5log₂3/5）
  Outlook = overcast时，熵值为0
  （ -4/4log₂4/4）
  Outlook = rainy时，熵值为0.971
  （ -3/5log₂3/5 - 2/5log₂2/5）
• 根据数据统计，outlook取值分别为sunny，overcast，rainy的概率分别为：5/14，4/14，5/14
• 熵值计算：5/14 * 0.971 + 4/14 * 0 + 5/14 * 0.971 = 0.693
  （gain(temperature)=0.029 gain(humidity)=0.152 gain(windy)=0.048）
• 信息增益：系统的熵值从原始的0.940下降到了0.693，增益为0.247
• 同样的方式可以计算出其他特征的信息增益，那么我们选择最大的那个就可以了，相当于遍历了一遍特征，找出来了大当家，然后再其余的中继续通过信息增益找二当家。

四. 信息增益率
4.1 决策树算法

• 4.1.1 ID3：信息增益（有什么问题？）
  
• 4.1.2 C4.5：信息增益率（解决ID3问题，考虑只身熵）
  信息增益率的计算：
  
  
  
  
• 4.1.3 CART：使用GINI系数来当做衡量标准
  (相比于信息增益，信息增益比等作为特征选择方法，基尼指数省略了对数计算，运算量比较小，也比较容易理解，所以CART树选择使用基尼系数用来做特征选择。)
• GINI系数：
  
  （和熵的衡量标准类似，计算方式不相同）
  GINI系数的计算：
  
  

五.决策树剪枝策略
5.1 连续值离散化

5.2决策树剪枝策略

• 为什么要剪枝：决策树递归地构建树，直到不能继续分裂下去为止，这样的树对于训练集可能拟合的较好，但对于训练集可能产生过拟合现象，原因是过多的考虑对训练集的划分精确度，从而构建出了复杂的决策树，缓解过拟合的方法是通过剪枝。决策树过拟合风险很大，理论上可以完全分得开数据（想象一下，如果树足够庞大，每个叶子节点不就一个数据了嘛）
• 剪枝策略：预剪枝，后剪枝
• 预剪枝：边建立决策树边进行剪枝的操作（更实用）
• 后剪枝：当建立决策树后来进行剪枝操作

5.3 预剪枝与后剪枝
预剪枝：限制深度，叶子节点个数叶子节点样本数，信息增益量等
后剪枝：通过一定的衡量标准

（叶子节点越多，损失越大）

根据后剪枝的衡量标准通过计算，①和②。比较①和②的值，哪个值大，说明哪个效果不好。如果②比①小，说明②比①好，分裂比较好；如果①比②小，说明①比②好，则不分裂比较好。
六. 集成算法-随机森林
6.1 Ensemble learning

• 目的：让机器学习效果更好，单个不想，群殴走起
• Bagging：训练多个分类器取平均
  
• Boosting：从弱学习器开始加强，通过加权来进行训练
  
• Stacking：聚合多个分类或回归模型（可以分阶段来做）
  6.2 Bagging模型
• 全称：bootstrap aggregation（说白了就是并行训练一堆分类器）
• 最典型的代表就是随机森林
• 随机：数据采样随机，特征选择随机
• 森林：很多个决策树并行放在一起
  
  七. 特征重要性衡量
  7.1 随机森林
• 构造树模型
  
• 由于二重随机性，使得每个树基本上都不会一样，最终的结果也不一样。
  7.2 Bagging模型
• 树模型
  
  之所以要进行随机，是要保证泛化能力，如果树都一样，就没意义。
  7.3 随机森林优势
• 它能够处理很高维度（feature很多）的数据，并且不用做特征选择
• 在训练完后，它能够给出哪些feature比较重要
• 容易做成并行化方法，速度比较快
• 可以进行可视化展式，便于分析
  7.4 Bagging模型
  树模型：
  
  理论上越多的树效果越好，但实际上基本超过一定数量就差不多上下浮动。

八. 提升模型
Boosting模型

• 典型代表：AdaBoost，Xgboost
• AdaBoost会根据前一次的分类效果调整数据权重
• 解释：如果某一个数据在这次分错了，那么在下一次我就会给它更大的权重
• 最终的结果：每个分类器根据只身的准确性来确定各自的权重，再合体

九. 堆叠模型
9.1 Stacking模型

• 堆叠：很暴力，拿来一堆直接上（各种分类器都来了）
• 可以堆叠各种各样的分类器（KNN，SVN，RF等）
• 分阶段：第一阶段得出各自结果，第二阶段再用前一阶段结果训练
• 为了刷结果，不择手段

• 堆叠在一起确实能使得准确率提升，但速度是个问题