参考资料：

• 《机器学习与R语言实战》机械工业出版
• 《机器学习》周志华
• [随机森林(2)R实战][https://www.yuque.com/biotrainee/biostat/chapter3-24]
• Document in R
• [ “mean decrease accuracy” 和 “mean decrease gini” ][https://blog.csdn.net/chishuideyu/article/details/80206815]

决策树

1. 基本概念

决策树是基于树结构来进行决策的，这是一种人在决策时自然的处理机制，即进行决策时，会进行一系列的“子决策”，每个决策过程中进行的判断，都是在上次决策结果的限定范围内，每个决策都只考虑在当前的判断，经过这些子决策，得到最终决策。

一颗决策树包含：

• 一个根结点

根结点包含所有样本。

• 若干内部结点
• 若干叶结点

叶结点对应决策结果，其他节点对应于一个属性测试。

2. 决策树基本算法

决策树的生成是一个递归（直接/间接的调用自身函数）过程。

• 生成结点

• 判断1：所有训练集样本是否属于同一种类别

• 判断2：所有的训练集属性特征取值都否都相同

• 从属性中选择最优划分属性

选择属性：

D是样本集，a是属性

• 根据最优划分属性的每个取值，生成各个分支，得到样本子集，判断3：如果样本子集为空，那么分支的类别标记为整个训练集中样本最多的类

在三种情况下递归返回：

1. 当前结点下的样本全部属于同一类，不需要划分。
2. 当前属性为空/所有样本在所有属性上取值相同，划分不了样本——设当前结点为叶节点，类为该结点下最多的类
3. 当前结点包含的样本为空，不能划分——设当前结点为叶节点，类为父结点下最多的类

3. 划分选择

随着划分的进行，结点“纯度”应该越来越高，即决策树的分支结点包含的样本尽可能属于同类。

3.1 信息增益

• 信息熵：

度量样本集合纯度的一种指标，值越小，纯度越高。

y是结果的类别有几类，k是第k类，pk就是当前样本集合D中第k类样本占的比例。

• 信息增益：

计算信息熵，考虑不同分支结点样本数不同，分支结点有权重（样本多影响大），可计算出每个属性对总体样本的信息增益。信息增益越大，该属性划分的“纯度”高。

a就是属性a，V是属性a有V个取值，会产生V个分支结点，$D^v$ 是 其中第v个分支结点包含了D中所有在属性a上取值为$a^v$的样本

• 从属性中选择最优划分属性

选择属性，得到这个属性后，对根结点进行划分，随后要对分支结点进行进一步划分，进一步划分时，再对各个属性的信息增益进行计算，选择该值最大的属性作为划分属性。

• 增益率

  

由于信息增益准则对可取值数据多的属性有偏好，为了减少这种偏好的影响，引入增益率。

IV(a)为属性a的“固有值”：

属性a的可能取值数目越多，IV(a)的值通常越大。不过，增益率对可取值数目少的属性有偏好，C4.5算法采用的解决方法是：从候选属性中找到信息增益率高于平均值的属性，再从中找到增益率最高的。

3.2 基尼指数（Gini index）

数据集的基尼值：

属性a的基尼指数：

该指标直观反映了从数据集中随机抽取两个样本，类别标记不同的概率，该指标越小，数据集的纯度越高。

4 剪枝处理

判断决策树泛化性能是否提升，采用性能评估方法：留出法（将样本分为训练集和验证集）。

用训练集生成决策树，用验证集计算泛化能力变化。

• 预剪枝

划分前进行判断，判断划分前后的泛化能力有没有提升（使用精度进行判断，精度提升，泛化能力提高），如果该结点能够提升验证集精度，采取该划分，否则禁止划分。

缺点：由于只考虑了当前划分后泛化能力有没有提升，没有考虑到后续的划分是否会对泛化能力进行提升，因此可能会欠拟合。

• 后剪枝

先生成决策树，然后再判断。生成决策树之后，先得到决策树的验证精度，考察结点，如果将结点替换成叶结点，决策树的验证集精度如果提高了，就将该结点替换成叶结点。如果剪枝前后的模型精度没有发生变化，根据奥卡姆剃刀准则，剪枝后的模型更好，进行剪枝。

优点：欠拟合风险小，且泛化性能往往优于预剪枝决策树。

缺点：完全生成决策树之后，需要自底部向上对非叶节点逐一考察，因此训练时间要多。

5. 连续

• 连续属性

上述描述的都是离散属性生成决策树，这里学习连续属性中决策树的应用，采用了连续属性离散化技术，比如C4.5决策树算法中的二分法。

连续属性的特点：可取值数目不有限，因此不能够根据连续属性的取值对结点进行划分。

连续属性作为划分属性的区别：父结点使用的划分属性，仍可作为后代结点的划分属性。

给定样本集D和连续属性a，假定a在D上有n个不同的取值，对这些取值进行从小到大排序，基于划分点t将样本集分为两个子集，分别包含属性a取值不大于t的样本和属性a取值大于t的样本。划分点t前后的属性a的两个取值，由于t在该两个取值之间取任意值都不会对划分结果产生影响，所以，可以考虑候选划分点集合，把区间中位点作为候选划分点，集合中包含n-1个元素。可以对这些划分点进行考察，选择最优划分点。

6. 多变量决策树

对属性的线性组合进行测试，非叶节点线性分类器，也就是说不是找最优划分属性，而是建立合适的线性分类器。

集成学习

1. 基本概念

通过构建并结合多个学习器来完成学习任务。个体学习器通常由一个现有的学习算法从训练数据中产生，这些学习器可以是同种类型的，也可以是不同类型的。

• 基学习器

集成中只包含同种类型的个体学习器，这些个体学习器就是基学习器，相应的学习算法成为“基学习算法”。

• 组件学习器

集成中包含不同类型的个体学习器，是不同的算法生成的，不存在基学习算法，这些学习器就是组件学习器或者就成为个体学习器。

• 集成学习的结果：

通过投票法产生，少数服从多数。

• 如何获得好的集成结果：

个体分类器好而且不同。

• 分类：

• • 个体学习器存在强依赖关系、必须串行生成的序列化方法：Boosting
  • 个体学习器不存在强依赖关系、可同时生成的并行化方法：Bagging，随机森林（Random Forest）

2. Boosting

• 流程

从初始训练集训练出一个基学习器，根据基学习器的表现对训练样本分布进行调整，让之前学习器做错的训练样本得到更多关注，基于调整后的样本分布来训练下一个基学习器，重复进行，直到基学习器数目达到事先指定值T，将这T个基学习器进行加权结合。

3. Bagging与随机森林

3.1 Bagging

• 对预测进行组合输出

• • 分类：简单投票法
  • 回归：简单平均法

• 为了得到泛化性能强的集成，个体学习器最好相互独立，可以通过：

• • 对训练样本采样生成不同的子集
  • 从每个数据子集中训练出一个基学习器

优点：由于训练数据不同，获得的基学习器可能具有比较大的差异。

缺点：采样的子集完全不同，每个学习器只用了小部分训练数据，不一定得到很好的学习器满足集成学习的需要。

解决：使用相互有交叠的采样子集，比如：自助采样（Bootstrap sampling）采取了又放回的抽样，样本可能被多次采样。

• 自助采样的优点

• • 由于每个基学习器只使用了初始训练集中约63.2%的样本，剩下的样本可作为验证集对泛化能力进行“包外估计”（OOB）。
  • 基学习器是决策树时，可使用包外样本来辅助剪枝，当基学习器是神经网络时，可使用包外样本来辅助早期停止以减小过拟合风险。

随机森林

• 基本概念

是以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。传统决策树在选择划分属性是在当前结点的属性集合中选择一个最优属性；但是在随机森林中，对基决策树的每个结点，先从该结点的属性集合（假设共有d个属性）中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分，一般情况下推荐k = log2(d)。

• 载入包并准备数据

  library(randomForest)
  library(modeldata)
  data(mlc_churn)
  

• 删除无效贡献的特征

  mlc_churn <- mlc_churn[, !names(mlc_churn) %in% c("state","area_code","account_length")]
  

• 划分训练集和测试集

  按照70%训练集，30%验证集，进行划分。

  set.seed(1126)
  ind <-  sample(2, nrow(mlc_churn), replace = T, prob = c(0.7, 0.3))
  trainset <- mlc_churn[ind == 1, ]
  testset <- mlc_churn[ind == 2, ]
  

  

• 建立模型

  churn.rf <- randomForest::randomForest(churn ~ ., data = trainset, importance = T)
  

  

• 用训练好的模型进行预测

  churn.prediction <- predict(churn.rf, testset)
  table(churn.prediction, testset$churn)
  

  

  

• 绘制森林对象的均方差

  plot(churn.rf)
  

  

• 评价各个属性的重要度

  importance(churn.rf)
  varImpPlot(churn.rf)
  

  

  Mean Decrease in Accuracy

  把一个变量的取值变为随机数，随机森林预测准确性的降低程度。该值越大表示该变量的重要性越大

  Mean Decrease Gini

  计算每个变量对分类树每个节点上观测值的异质性的影响，从而比较变量的重要性。该值越大表示该变量的重要性越大。