Paper Reading 是从个人角度进行的一些总结分享，受到个人关注点的侧重和实力所限，可能有理解不到位的地方。具体的细节还需要以原文的内容为准，博客中的图表若未另外说明则均来自原文。

论文概况	详细
标题	《Hashing-Based Undersampling Ensemble for Imbalanced Pattern Classification Problems》
作者	Wing W.Y.Ng, Shichao Xu, Jianjun Zhang, Xing Tian, Tongwen Rong, Sam Kwong
发表期刊	IEEE Transactions on Cybernetics
发表年份	2022
期刊等级	中科院 SCI 期刊分区(2022年12月最新升级版）1 区，CCF-B
论文代码	文中未公开

作者单位：

Guangdong Provincial Key Laboratory of Computational Intelligence and Cyberspace Information
School of Computer Science and Engineering, South China University of Technology, Guangzhou
Department of Computer Science, Hong Kong City University, Hong Kong

研究动机

不平衡分类问题是机器学习中具挑战性的问题之一，传统的分类器不是为处理不平衡分类问题而设计的，由于存在代表性不足的数据和严重的类分布倾斜，它们在不平衡数据集上表现不佳。影响分类性能的另一个重要因素是不恰当的评价指标，许多传统的分类器以平均精度为导向，这样往往会忽略少数类中的样本以获得较高的平均准确率。欠采样是一种常用的解决分类不平衡问题的方法，它的原理是减少用于分类器训练的多数样本的数量。欠采样具有所有的训练样本都是真实样本和训练时间少的优点，但是当移除太多的多数样本时会丢失太多的信息。

文章贡献

针对欠采样方法会丢弃大量多数类样本导致信息缺失的问题，本文提出了基于哈希的欠采样集成 HUE 模型，它利用 Bagging 和多数类样本的分布特征来构建多样化的训练子集。首先 HUE 通过散列将大多数类样本划分为不同的特征子空间，然后使用所有少数样本和主要从同一哈希子空间中提取的部分多数样本来构建训练子集，最后使用每个训练子集来训练一个基分类器，通过投票法将这些基分类器集成在一起。该方法在 25 个 UCI 数据集和两个大型数据集上与多种方法进行了对比，实验结果表明该方法优于其他方法，在高度不平衡的数据集上取得了良好的效果。

本文方法

本文的 HUE 方法主要包括以下三个主要组件，其中用于划分散列子空间的散列方法是迭代量化方法(ITQ)，集成策略主要基于 Bagging。由于 Bagging 中每个基分类器仅从多数类的一部分学习，因此理想的情况是每个基分类器使用多数类的不同子集进行学习，实现集成学习整个多数类样本空间的目的。

将多数样本划分到不同的散列子空间中；
通过从不同的哈希子空间采样来构建多样化的训练子集；
使用训练子集训练基分类器，通过投票法得到集成分类器。

整体流程

二分类不平衡数据集分别由 Nmaj 和 Nmin 个样本的多数类和少数类组成，HUE 算法的流程如下伪代码所示。第一步是使用 ITQ 对所有样本执行二进制哈希编码，保留样本之间的相似性信息，将多数类划分成 n 个散列子空间。每个多数样本具有 B 位散列码，散列码相同的样本属于相同的散列子空间。对于每个散列子空间 Sj，先通过 wi=1/di2^B 对每个样本进行加权，其中 di 表示样本 i 与对应于子空间 Sj 的散列码之间的汉明距离，当 di=0 时 wi=1。接着将所有少数类样本和根据权重分布 wi 采样的 Nmin 个多数类样本组成 n 个训练子集，进而训练 n 个基分类器，通过多数投票进行集成得到最终的集成分类器 H。

基于哈希的子空间划分方法

Hash 方法将样本划分成 Hash 子空间，其中每个子空间对应于唯一的 Hash 码，相同子空间中共享相同 Hash 码的样本彼此相似。ITQ 是最有代表性的无监督 Hash 方法之一，为了令 Hash 更加紧凑，ITQ 希望每一个 bit 的方差最大，而且 bit 之间是线性无关的。而 PCA 的原理也是令每一维特征样本间的方差最大，而且特征向量之间是相互正交的，与 ITQ 的目的一致。因此 ITQ 首先应用 PCA 处理所有多数类样本，令 PCA 投影空间的原点为超立方体的中心，该超立方体的每个顶点表示一个 Hash 码，最接近这些顶点的样本被分配有顶点对应的 Hash 码。
但是简单的 PCA 对于不同维度的数据的方差并不平衡，因此需要随机将 PCA 进行旋转进行优化，使 Hash 码与样本的原始特征向量之间的量化损失最小化。ITQ 的目标函数如下所示，其中 C、V、R 和 ||·|| 分别表示数据集的 Hash 码、PCA 投影之后的实值数据描述符、旋转矩阵和 Frobenius 范数。通过迭代地更新 Hash 码和旋转矩阵来最小化量化损失，最终得到样本的最优散列码集和最优旋转矩阵。

基于距离的样本选择

HUE 的第二步是为基分类器建立多样化的训练子集，每个训练子集由所有少数类样本中和相同数量的多数类的样本组成。某个子集中的多数类的样本主要从一个 Hash 子空间中获取，该子空间被称为参考子空间，同时结合一部分周围子空间的样本进行辅助。为了实现这点需要对每个样本设置采样权重，使用汉明距离作为度量，更接近参考子空间的样本具有更高的权重。
基于距离的抽样权重分配方案如下公式所示，其中 B 和 di 表示 Hash 位的数量以及样本 i 与参考子空间之间的汉明距离，位于参考子空间中的多数类样本的 di = 0，并被设置了最高的权重。

下图展示出了 B=3 的基于距离的采样权重分布，对于每个 Hash 子空间基于(2)中的采样权重，可以通过从多数类样本中替换采样并与所有少数类样本组合来构建相应的训练子集。

实验结果

数据集和实验设置

使用 25 个 UCI 不平衡数据集进行实验，数据集的信息如下表所示。使用 AUC 作为性能指标，所有方法均采用五折交叉验证，每个数据集重复运行 20 次后取平均，对比算法使用 AsymBag、IRUS、NBBAG、CBUS、CBUS_NN、DSUS 和 bagging 方法。

不同子空间划分方法的影响

除了使用 Hash 方法，也可以使用聚类算法来划分子空间，聚类的代表性算法为 k-means 算法。该部分实验中使用 k-means 替代 HUE 中的 ITQ 方法进行子空间划分，称为基于聚类的欠采样集合(CUE)。k-means 聚类中心的个数设置为 2B，与 ITQ 中 Hash 码的个数相同，实验主要从训练时间和 AUC 进行对比。
下表给出了 HUE 和 CUE 在 25 个数据集上的 AUC 和训练时间，在 AUC 方面 HUE 在 20 个数据集上优于 CUE，其中 16 个数据集的显著性水平为 0.05。对于小数据集而言两种方法在训练时间的差异并不明显，对于大型数据集 HUE 在子空间划分方面明显速度更快。

进一步在两个大型数据集：MNIST 和 CIFAR100 上进行实验，两个数据集的基本信息如下表所示，并将它们转换为不平衡二分类数据集。

实验结果如下表所示，可见在 CIFAR100_1 和 MNIST_4 中，HUE 在子空间划分时间上分别比 CUE 快 734.46% 和 615.28%。总而言之在 HUE 中使用 Hash 方法进行子空间划分比基于聚类的方法更有效，并且产生更好的 AUC 性能。

不同加权方案的抽样

此处评估了 HUE 中使用五种不同采样加权方案的有效性，五种加权方案如公式 (3)~(7) 所示。

下图为当 B=3 时不同 di 方案的权重，这五种赋权方案都满足权值随距离增加而减小的规则。

为了展示不同加权方案的效果，下图展示了一个人工合成的二分类数据集，其中红点为少数类样本。

下图显示了在上述合成数据集的基础上，用 ITQ Hash 方法划分的四个哈希子空间。

使用五种不同的加权方案进行抽样会产生不同的训练子集分布，以右下角的区域为参考区域，下图展示了这些策略得到的样本的分布情况。

下表展示了详细不同加权策略在不同的区域中采样得到的样本数量。

下表显示了在 25 个数据集上 HUE 的五种加权方案的 AUC 比较，可见使用 IV 策略性能更优。

下表显示了使用五种不同加权方案的 HUE 的符号秩检验结果，加权方案 II 与加权方案 I、V 之间差异极显著，加权方案 III 和 IV 与加权方案 I 和 V 的差异显著，与加权方案 II 的差异显著，加权方案 III 和 IV 之间的差异不是很显著。

与其他方法比较

将 HUE 与多种不平衡集成算法进行比较，AUC 的平均结果如下表所示，其中 DSUS 方法在时间和空间的开销非常大，在包含大量样本的 SDD 和 skin 数据集上无法得到结果。总体而言 HUE 在 25 个数据集中的 8 个中取得了最好的结果，表现最优。

下表展示了使用 AUC 的 WIN-TIE-LOSE 结果，t 检验的显著性水平为 0.05，结果说明了 HUE 显著优于所有其他方法(p<0.01)。

接着比较了三种最优的方法的训练时间，下面两张表。分别给出了这三种方法在 25 个 UCI 数据集和两个大型数据集上的训练时间。可见在这些数据集上 HUE 产生的训练时间最短，特别是对于具有近 24.5 万个样本的 skin 数据集，HUE 比 NBBag 和 CBUS_NN 快 100 倍以上。在 MNIST_4 数据集的实验中，HUE 分别比 NBBag 和 CBUS_NN 快 57.97 倍和 369.60 倍。在 CIFAR100_1 的实验中，HUE 分别比 NBBag 和 CBUS_NN 快 3.89 倍和 263.45 倍。

综上所述，HUE 在比较下优于所有方法，特别是对于大量样本和高失衡率的数据集。