CCF-A论文：DM-UCML

原文链接：Muitiset Feature Learning for Highly Imbalanced Data Classification

介绍

动力

在很多真实世界的数据集中，大部分数据都是不平衡的，也就是说，其中一个分类的数据量非常多，但其他很多分类的数据量就很少，这样的数据集常见于软件故障预测、文档分类、对象检测和生物信息学等。不平衡的数据集就会导致学习模型向着数据量极大的分类学习，而忽略那些数据量少的分类。

目前为止，很多学者提出了各种方法试图去解决这样的数据不平衡问题，他们大多数分为三种：

1. 基于重采样的方法，这样的方法会为了对高度不平衡数据进行分类而移除或增加大量的样本
   1. 欠采样技术，这种技术通过将多数类（指数据量大的类）进行欠采样，降低多数类数据量
   2. 过采样技术，这种技术通过将少数类（指数据量少的类）进行重采样，增加少数类数据量，这种技术的代表为少数类综合过采样技术（Synthetic Minority Over-Sampling Technique，SMOTE）
   3. 综合采样技术
2. 基于代价敏感学习的方法，这种方法重点关注误分类样本，而如何设置代价cost会是一个值得考虑的问题
3. 基于集成学习的方法。这种方法将多种分类器进行集成学习，代表为WEOB2（undersampling based online bagging with adaptive weight adjustment），而如何保证和利用多种分类器进行集成学习仍然是一个未解问题

除了上述几种方法以外，在最近一段时间，深度表示学习（Deep representation learning）因为其强大学习能力在这方面获得了成功，DML（Deep Metric Learning）也被用来解决数据不平衡问题。这些方法和卷积神经网络（Convolutional Neural Network，CNN）以及上述三种方法结合起来，生成了Deep Metric分类器。

但是，虽然上述这些方法在不平衡比例（Imbalance Ratio，IR）为10：1的时候能够正常处理数据，但是在极大不平衡数据集上仍然收效甚微。

图一.在Abalone19数据集上，高度不平衡学习算法随IR增大的G-mean变化曲线

我们可以看到，随着IR的不断增大，之前的高度不平衡学习算法的G-mean下降非常剧烈。所以，基于此，学者们也提出了诸如Granular SVMs-repetitive undersampling（GSVM-RU）和Evolutionary under-sampling boost（EUSBoost）等模型。也有学者提出了基于边界综合少数类重采样技术（borderline synthetic minority over-sampling technique）的两种采样方法

但目前的这些采样方法也存在很多问题。对于重采样而言，大量对少数类（指数据量极少的类）的重复采样会过度放大少数类的特征，大量对多数类的欠采样又会导致多数类的特征丢失。在最近几年，很多学者对MFL（Multiset Feature Learning，多集合特征学习）进行了研究，我们发现，可以利用MFL将不平衡数据集分成众多平衡子数据集，然后利用子数据集进行学习。但是，我们不能直接使用MFL，原因有：

1. 直接进行分类的子数据集相互之间的关联性极强，这会影响MFL对于全部特征的学习
2. 少数集和多数集分类代价不相等，这会导致分类器更偏向于多数集

根据以上分析，本文设计了一个不相关代价敏感多集学习算法（Uncorrelated Cost-sensitive Multiset Learning，UCML）来处理高度不平衡数据集。这是一种MFL改进算法。

但是在实际中，还有两个重要的问题会影响MFL的性能：

1. 在真实世界中，我们很难保证高度不平衡数据在线性空间中，UCML虽然能够正确处理高度不平衡数据，但是UCML没有考虑数据都处于非线性空间中的情况。
2. 子数据集和全数据集之间的相似程度也会影响模型学习数据集特征的性能

图二.在各种数据集中，分类准确度和子数据集、全数据集之间的相似程度的关系（横轴表示子数据集编号） 图二展示了子数据集、全数据集之间的相似程度对分类准确度的影响，其中，本文使用了Jenson-Shannon Divergence（JSD，JS散度）来刻画相似程度。我们可以发现：

1. 按照随机分布的子数据集，其与全数据集之间的相似程度各有不同
2. 子数据集越像全数据集，其分类准确度越高

贡献

1. 本文是第一个利用MFL去解决高度不平衡数据集的，本文还提出了一种不相关代价敏感多集特征学习算法。
2. 本文提出了基于度量（Deep Metric）的UCML（DM-UCML）算法。DM-UCML算法首先设计了一个基于生成对抗网络（Generative Adversarial Network，GAN）的多集生成策略，它能保证生成的子数据集拥有与原数据集相同的数据分布特征。然后DM-UCML将度量学习（Deep Metric Learning）技术融合进MFL中去解决多数据集中的非线性问题
3. 我们对十个数据集进行了对应的实验（包括八个传统高度不平衡数据集和两个大数据集，CelebA和X-Domain）

UCML

多集生成策略

第一步：我们随机将多数类样本分为多个子类，每个子类的样本和少数集样本相同。如果多数集分类后还剩余少量的多余样本，那么就四舍五入（少于少数集样本数量一半则舍弃，否则随机从其他子类中复制样本加入这些样本中凑成新的子类）

图三.多集生成策略图解）

第二步：我们将每个子类和少数集样本组合，形成平衡样本集。这样，我们就生成了多个平衡数据集。

代价敏感的多集特征学习（UCML）

当v个集合生成了之后，我们将敏感代价因子组合进MFL中以降低误分类代价并提高分类效果。UCML使用了类内离散度（Within-Class Scatter）和类间离散度（Between-Class Scatter）的差并加入了关联约束来衡量分类效果并改进权重。其中类内离散度公式为：

$S_{W}^{y}=\sum_{i=1}^{c} \sum_{j=1}^{v} \sum_{k=1}^{n_{i j}}\left(y_{i j k}-u_{i}\right)\left(y_{i j k}-u_{i}\right)^{T}$

其中c是分类数量，v是集合数量，$n_{ij}$是第i个分类，第j个集合中的样本总数量，$y_{ijk} = w^{T}_{j} x_{ijk}$，$u_i$是第i个分类中所有y的平均值，上述公式可转化为：

$S_{W}^{y}=\left[w_{1}^{T} w_{2}^{T} \ldots w_{v}^{T}\right]\left(\begin{array}{ccc} s_{11} s_{12} & \ldots & s_{1 v} \\ s_{21} s_{22} & \ldots & s_{2 v} \\ \vdots & \vdots & \vdots & \vdots \\ s_{v 1} s_{v 2} & . & s_{v v} \end{array}\right)\left[\begin{array}{c} w_{1} \\ w_{2} \\ \vdots \\ w_{v} \end{array}\right]=w^{T} S w$

其中：

$s_{j m}=\left\{\begin{array}{l} \left.\sum_{i=1}^{c}\left(\sum_{k=1}^{n_{i j}} x_{i j k} x_{i j k}^{T}-\frac{n_{i j} n_{i j}}{n_{i}} u_{i j}^{(x)} u_{i j}^{(x) T}\right\}\right) \quad j=m \\ \sum_{i=1}^{c}\left(-\frac{n_{i j} n_{i j}}{n_{i}} u_{i j}^{(x)} u_{i j}^{(x) T}\right) \quad \text { otherwise. } \end{array}\right.$

同样，类间离散度公式为：

$S_{B}^{y}=\sum_{i=1}^{c} \sum_{l=1, l \neq i}^{c} \operatorname{cost}(i, l)\left(u_{i}-u_{l}\right)\left(u_{i}-u_{l}\right)^{T}$

可转化为：

$\boldsymbol{S}_{B}^{y}=\left[\begin{array}{cc} w_{1}^{T} w_{2}^{T} & \ldots & w_{v}^{T} \end{array}\right]\left(\begin{array}{ccc} d_{11} d_{12} & . . & d_{1 v} \\ d_{21} d_{22} & \ldots & d_{2 v} \\ \vdots & \vdots & \vdots & \vdots \\ d_{v 1} d_{v 2} & . & d_{v v} \end{array}\right)\left[\begin{array}{c} w_{1} \\ w_{2} \\ \vdots \\ w_{v} \end{array}\right]=w^{T} D w$

其中：

$\begin{aligned} d_{j m}=& \sum_{i=1}^{c} \sum_{l=1, l \neq i}^{c} \operatorname{cost}(i, l) \\ &\left(\frac{n_{i j} n_{i m}}{n_{i}^{2}} u_{i j}^{(x)} u_{i m}^{(x) T}-\frac{n_{i j} n_{l m}}{n_{i} n_{l}} u_{i j}^{(x)} u_{l m}^{(x) T}\right) \\ &+\left(\frac{n_{l j} n_{l m}}{n_{l}^{2}} u_{l j}^{(x)} u_{l m}^{(x) T}-\frac{n_{l j} n_{i m}}{n_{i} n_{l}} u_{l j}^{(x)} u_{i m}^{(x) T}+\right) \end{aligned}$

加权不相关约束

为了加速MFL，我们需要去除各个集合之间的不利的相关性以便学习到更多的特征并去除冗余特征。本文根据UODV（uncorrelated optimal discrimination vectors）和WGUDT（ weighted global uncorrelated discriminant transforms）设计了一种加权不相关约束以便减少从多个集合中学习到的各个特征的相关性。

本文设计的不相关约束特征公式为：

$\sum_{j=1}^{v} \sum_{m=1, m \neq j}^{v} w_{j}^{T} s_{t}^{j, m} w_{m}=w^{T} H w=0$

其中$H=\left[\begin{array}{cccc}0 & s_{t}^{1,2} & \ldots & s_{t}^{1, v} \\ s_{t}^{2,1} & 0 & \ldots & s_{t}^{2, v} \\ \vdots & \vdots & \vdots & \vdots \\ s_{t}^{v, 1} & s_{t}^{v, 2} & \ldots & 0\end{array}\right]$

目标函数和解法

UCML的目标函数为：

$\begin{array}{r} \max _{w} w^{T}(D-S) w \\ \text { s.t. } w^{T} H w=0 \end{array}$

其可以转化为求解特征方程：

$(D-S) w=\lambda H w$

基于度量学习的UCML

从之前的分析我们可以知道：

1. 构造的平衡子集和全数据集的相似分布会影响MFL的分类效果
2. 不平衡数据的非线性应该被考虑进MFL的过程中

而普通的UCML只考虑了线性分割，并且其平衡子集的构造方式也存在问题，所以我们需要从两方面提升UCML：

1. 设计一个多集构造方法去保证构造了的平衡子集和全数据集之间拥有相似的分布
2. 将度量学习引入MFL中以解决非线性问题

基于生成对抗网络的多集构造方法

生成对抗网络（Generative Adversarial Network，GAN）能够生成与原数据相似程度很高的数据，而平衡子集与原数据集相似程度越高，我们进行分类的效果也就越好。整个基于生成对抗网络的多集构造方法分为三步：

第一步：先将多数类的样本随机分为v个子集，保证每个子集的样本数量和少数类的样本数量相同。如果存在冗余样本，则将每个冗余样本放入不同的生成的子集中

第二步：通过GAN，让每个子集的样本分布和原多数类的样本分布相同。本文使用的GAN的目标函数为：

$L=L_{1}+L_{2}$

其中，L1是GAN的损失函数，其表示为：

$\begin{aligned} L_{1}=& \mathbb{E}_{x \sim X^{N}}[\log D(x)] \\ &+\mathbb{E}_{z \sim Z_{i}}\left[\log \left(1-D\left(G_{i}^{N}(z)\right)\right)\right] \end{aligned}$

L2是相似度判别式，可表示为：

$L_{2}=\mathbb{E}_{x \sim X^{N}, z \sim Z_{i}}\left\|\frac{1}{n_{i}} \sum_{p=1}^{n_{i}} G_{i}^{N}\left(z_{p}\right)-\frac{1}{m} \sum_{q=1}^{m} x_{q}\right\|_{2}^{2}$

第三步：将每个生成的子类和少数类结合，形成平衡子数据集

图四.DM-UCML流程图

对于生成后的每一个平衡数据集，我们使用多集深度神经网络去对每个样本做非线性变换，就如同图四下半部分那样。每个x的输出公式为：

$\begin{aligned} f_{k}^{(m)}(x) &=h_{k}^{(m)} \\ &=\varphi\left(W_{k}^{(m)} h_{k}^{(m-1)}+b_{k}^{(m)}\right) \in \mathbb{R}^{p^{(m)}}, \end{aligned}$

其中，$\varphi$是激活函数，比如sigmoid，tanh等。

最后，通过结合度量学习以及UCML，本文为DM-UCML设计了一个新的损失函数：

$\begin{aligned} \min L=& \sum_{k=1}^{V} L_{k}=S_{k c}^{(M)}-\alpha S_{k d}^{(M)}+\beta D_{k} \\ &+\gamma \sum_{m=1}^{M}\left(\left\|W_{k}^{(m)}\right\|_{F}^{2}+\left\|b_{k}^{(m)}\right\|_{F}^{2}\right) \\ & \text { s.t. }\left(W_{i}^{(M)}\right)^{T} H\left(W_{j}^{(M)}\right)=0(i \neq j) \end{aligned}$

其中，$\alpha$是一个自由参数，它可以平衡类内紧密程度和类间松散程度。$\beta$和$\gamma$是可调的正则参数。$\sum_{m=1}^{M}\left(\left\|W_{k}^{(m)}\right\|_{F}^{2}+\left\|b_{k}^{(m)}\right\|_{F}^{2}\right)$是避免过拟合的正则表达式。$S_{k c}^{(M)}$，$S_{k d}^{(M)}$和$D_{k}$分别表示类内的紧密程度、类间的松散程度和第k个集合的误分类代价。最后，本文使用了随机次梯度下降方法来更新权重。

实验

本文最后对上述提到的十个不同的高度不平衡数据集和大数据集进行了实验，实验结果显示，使用了DM-UCML模型之后的各方面结果比其他模型得到的结果都要更好，同时运行速度也在可接受范围内。使用了GAN之后得到的新平衡子数据集也能在这些数据集上显著增强分类效果。

图五.在Abalone19数据集上，各种不平衡数据学习算法的G-mean值随IR增加的变化曲线（包含DM-UCML）