Written by Yitong Huang
on March 24, 2018

数据挖掘 - 组合方法

组合分类器是一个复合模型，由多个分类器组合而成，能有效提高分类的准确率。装袋、提升和随机森林都是流行的组合分类方法。

组合分类把k个学习得到的模型（基分类器）\(M_1, M_2, …, M_k\)组合在一起，创建一个改进的复合分类模型\(M^*\)。使用给定的数据集D创建k个训练集\(D_1, D_2, …, D_k\)，其中\(D_i\)用于创建分类器\(M_i\)。给定一个待分类的新数据元组，每个基分类器通过返回类预测投票。

graph LR
A[数据D]
A -->|D1| B((M1))
A -->|D2| C((M2))
A -->|Dk| D((Mk))
B -->E(组合投票)
C -->E
D -->E
F[新数据元组] -->E
E -->G((预测))

一、装袋

对于d个元组的集合D，装袋过程如下：

算法：装袋。

输入：
    D：d个训练元素的合集
    k：组合分类器的模型数
    一种学习方案（如决策树算法）
    
输出：组合分类器。

方法：
    1. for i = 1 to k do  // 创建k个模型
    2.     通过对D有放回抽样，创建自助样本Di；
    3.     使用Di和学习方法得到模型Mi；
    4. endfor

    使用组合分类器对元组x分类：让k个模型对x分类并返回对数表决。

二、提升和AdaBoost

提升方法中，赋予每个训练元组权重。迭代地学习k个分类器。

AdaBoost是一种流行的提升算法。训练数据的每一个样本，并赋予其一个权重。开始时，这些权重都是相等的，首先在训练数据集上训练出一个弱分类器并计算该分类器的错误率，然后在该数据集上再次训练弱分类器，但是在第二次训练时，将会根据分类器的错误率，对数据集中样本的各个权重进行调整，分类正确的样本的权重降低，而分类错的样本权重则上升，但这些权重的总和保持不变为1。以下是该算法过程：

算法：AdaBoost

输入：
    D：d个训练元素的合集
    k：轮数（每轮产生一个分类器）
    一种学习方案
    
输出：组合分类器。

方法：
将D中每个元组的权重初始化为1/d；
for i = 1 to k do
    根据元组的权重从D中有放回抽样，得到Di；
    使用训练集Di学习模型Mi；
    计算Mi的错误率error(Mi);
    if error(Mi) > 0.5 then
        转入步骤3重试；
    endif
    for Di的每个被正确分类的元组 do
       元组的权重乘以error(Mi)/(1-error(Mi))；
    规范化每个元组的权重；
endfor

使用组合分类器对元组x分类：
将每个类的权重初始化为0；
for i = 1 to k do    // 对于每个分类器
    wi=log((1-error(Mi))/error(Mi))；    // 分类器的投票权重
    c = Mi(x)；
    将wi加到类c的权重；
endfor
返回具有最大权重的类

其中为了计算模型\(M_i\)的错误率，求\(M_i\)误分类\(D_i\)中的每个元组的加权和：

\[error(M_i)=\sum\limits^d_{j=1}w_i\times err(X_j)\]

其中\(err(X_j)\)是元组\(X_j\)的误分类误差：如果\(X_j\)被误分类，则\(err(X_j)\)为1；否则为0。如果分类器\(M_i\)的性能太差（错误率超过0.5）则丢弃它，并重新产生新的训练集\(D_i\)，重新学习新的\(M_i\)。

\(M_i\)的错误率影响训练元组权重的更新。如果一个元组在第i轮正确分类，则其权重更新为原权重乘以\(error(M_i)/(1-error(M_i))\)。所有正确被正确分组的权重完成更新后，就对所有元组权重规范化，使得它们的和与之前一样。规范化过程为将权重乘以旧权重之和，除以新权重之和。

三、随机森林

以下是随机森林的生成过程：

我们从D中有放回地取出d个元组的训练集\(D_i\)，用于生成决策树；
在每个待分裂节点上，随机选取F个属性，F远小于可用属性数；
从选取的F个属性中根据某种策略（如Gini Index）确定分裂属性；
重复步骤2、3，直到不能分裂或达到设定的阈值，此时建立了一棵决策树；
重复步骤1~4，直到达到预定的总棵树为止。

参考资料：
《数据挖掘·概念与技术》 8.6

← → Top