不平衡学习研究

不平衡学习研究

马小艳

重庆对外经贸学院 401520

摘要：数据智能分类是机器学习研究的热点问题之一。经典的分类方法一般没有考虑不平衡数据的本身特性。所以分类效果往往表现不好。然而少数类识别错误其代价往往高于多数类。提升少数类的识别精度是目前数据分类中的研究重点。针对不平衡数据分类研究，涌现出的大量分类方法。本文对近年来方法进行整理，并作出宏观梳理。对新学者起一个快速上手的介绍。先对现有算法大致归重采样法、特征选择法、分类算法改进法等三大类、然后分别对每个类进行小类划分整理。最后对不平衡学习进行总结与展望。

关键词：不平衡学习；机器学习；分类算法

Abstract：Data intelligent classification is one of the hot topics in machine learning. Classical classification methods generally do not consider the characteristics of imbalanced data. So the classification effect is often poor. However, the cost of recognition errors of a few classes is often higher than that of most classes. Improving the recognition accuracy of minority classes is the focus of current research in data classification. A large number of classification methods have emerged in the study of imbalanced data classification. This paper sorts out the methods in recent years and makes a macro carding. Give a quick introduction to new scholars. First, the existing algorithms are roughly classified into three categories: re-sampling method, feature selection method, and improved classification algorithm, and then each category is classified into subcategories. Finally, it summarizes and prospects the imbalanced learning.

Key words: imbalanced learning; Machine learning; Classification algorithm

0引言

随着信息技术的不断进步，很多领域产生了大量数据。对数据进行智能分类是机器学习研究技术之一。分类是通过已有的数据进行建模构建一个模型，然后对新样本类别进行一个预测。分类技术广泛地应用于生物、化学、医疗、计算机、企业管理、环境管理等领域[1]。经典的分类算法有朴素贝叶斯（Naive Bayesian）、支持向量机（简称SVM，Support Vector Machine）、k-近邻算法（简称KNN，K-Nearest neighbors Algorithms）、决策树(Decision Trees)、随机森林（Random Forest）等等。传统的分类策略一般是假设数据集相对平衡。即样本在类上近似均匀分布。 然而，这种假设在实践中并不总是成立。由于类分布的自然偏斜性，类不平衡在计算机视觉、欺诈检测、入侵检测、医学诊断等许多实际应用领域中被广泛观察到。不平衡数据是在一个数据集中，类别与类别之间的比例不一样多，比例可能严重失调。比如在入侵检测数据集S中只有两个类，异常类的数据少，正常类的数据非常多。这种就属于不平衡数据。

经典的学习算法学习过程是以全局精度为导向的，这些算法往往会对多数类的偏向。即经过学习计算分类结果都判为多数类，这样下来分类准确率也比较高。这就导致在全局精度方面看起来很好，但在少数类的精度方面却很差。这样的结果利用价值不大，因为少数类的判断通常是最重要的。

为了解决分类结果偏向多数类问题，近年来，一个新兴的研究领域不平衡学习吸引了越来越多的研究人员。计算机顶级会议与期刊关于不平衡学习论文数量曾上升趋势。其解决不平衡学习算法大致分为重采样法、特征选择法、分类算法改进法。分类算法改进法又可以细分为代价敏感学习法、单类学习法、主动学习法、集成学习法、硬例挖掘法等

[2, 3]。本文接下来分别对上述方法做简要概述，然后对不平衡学习方法进行总结与展望。

1重采样法

不平衡数据集少数类要比多数类要少很多，为了训练一个良好的分类器，需要构建一个类平衡的训练集。因此要对原数据进行重采样。重采样其实就是对数据进行强行重构，调整多数类与少数类的数量，使之达到一个平衡的技术。根据采样方式的异同，重采样技术大致分为三种：分别是过采样技术、欠采样技术、过采样和欠采样结合的技术。

过采样是增加少数类类样本以达到平衡的目的。读者很容易想到最简单增加少数类样本的方法就是随机复制少数类样本。但这种方法有很大的缺点就是容易造成过度拟合，泛化能力不行。为了解决泛化能力不行的问题，Chawla等人提出了经典的过采样技术SMOTE[4]。其原理是随机的在少数类样本处进行插值，合成的值不与原数据重复，一定程度上解决了随机复制数据过采样的缺点。但此方法也有可能产生噪声等问题，为了解决噪声等系列问题，学者不断对合成过采样进行改进。为了选择安全的数据Douzas等人提出k-means聚类与SMOTE相结合的方法，先聚类再合成新数据方法，超出聚类圈的数据摒弃，一定程度上解决了SMOTE方法出现噪声问题。围绕SMOTE方法的有很多，[5]文献对基于SMOTE算法提出15年以来的改进或结合算法进行了总结与展望。近年来还有学者通过新颖方法[6]合成新数据，例如模糊学习、神经网络等技术智能合成数据，在一定程度上提升了少数类的分类精度。

欠采样是降低对多数类数据的数量来达到类平衡的技术。直接随机的丢弃多数类样本是最简单的欠采样法[7]。其最大的优点是计算速度快。但很有可能丢失重要数据信息而导致泛化性不强。为了弥补随机欠采样的缺点，经典的算法是编辑最近邻(ENN)算法,在ENN的基础上提出了领域清理法(NCL)[8]。NCL的基本思想是随机选个样本，如果是少数类且它周围三个样本中有两个或超过两个多数类，那么踢掉邻近的多数类。如果随机选的样本属于多数类，它的三个近邻样本中又超过两个少数类，则直接删除这个样本。Lin等人提出两种基于K-近邻欠采样算法[9]，第一种策略使用聚类中心来表示大多数类，而第二种策略使用了聚类中心的最近邻数据。其试验表明第二种方法更优。上述算法中未能考虑数据中的信息样本，而决策边界处的重采样对类重叠敏感。这两种技术都忽略了训练数据集的分布信息。Ng[10]等人提出了基于敏感度的多样化采样算法，随机敏感性度量用于从多数类和少数类的聚类中选择样本。通过迭代聚类和采样，选择高灵敏度分类器产生的平衡样本集。很好的保证了数据集的内在联系信息。取得了良好的分类效果。

过采样与欠采样相结合的技术就是把上述两种方法都用在不平衡学习中。多数类用欠采样，少数类用过采样，这样有可能克服两种方法的缺点。Seiffert[11]等人提出了一种混合采样机制，使用两种采样技术的组合来创建平衡数据集。通过使用多个采样技术，可以结合各个技术的优点，同时减少缺点。实验构建了超过一百万个分类器，表明混合采样过程几乎总是优于单独采样技术。张明等人提出的混合采样基本思想是先计算出样本的变异系数。如果大于变异系数的为稀疏域否者为密集域，然后分别在稀疏域和密集域找出少数类与多数类。少数类用BSMOTE算法过采样，多数类用IS算法欠采样。接着合成新样本。最后用随机森林训练模型。取得了良好的分类效果。

重采样技术不太依赖分类器，部署起来简单明了。但采样的量也没有确定的值。遇到极端不平衡数据也不太适应。如何确定采样规模与如何处理极端不平衡数据，是一个研究难点。

2特征选择法

与重采样法相比特征选择法研究相对较少。有许多用于特征提取的技术，例如主成分分析(PCA)、奇异值分解(SVD)和非负矩阵分解(NMF)。在数据集中往往掺杂噪声或冗余。特征选择的目标通常是从原始特征空间中选择使分类器能达到最佳性能的特征子集。特征选择一般可以划分为过滤式、封装式和嵌入式方法[1]。

过滤式法一般用一种测度方法进行特征选择。与“过滤”的字面意思比较接近。再用选择后的特征进行训练模型，这种方法往往与分类器独立。Hou[12]等人系统地比较了八种特征选择领域中的不平衡数据分类问题。此外，还研究了特征维数、样本数和不平衡度对解决不平衡数据特征选择性能的影响。

封装式一般是与分类器联合，通过遍历选择分类最优的特征子集。Beyan[13]等人提出了一种新的不平衡数据集的层次分解方法，它不同于以前提出的类不平衡问题的解决方案。不需要任何其他解决方案所需的数据预处理步骤。该方法基于聚类和离群点检测。该层次结构使用层次结构的每个级别上的标记数据子集的相似性来构建，不同级别由不同的数据和特征子集构建。聚类用于划分数据，而离群点检测用于检测少数类样本。该方法在不平衡数据上性能很好。

嵌入式法是上述两种方法的融合体。一边进行训练分类器，一边进行特征选择。Maldonado

[14]等人提出基于连续保持步骤的反向消除方法，其贡献度量基于在独立子集上获得的平衡损失函数。在高维的不平衡数据中，选择不同属性的特征去衡量少数类的特征。最后达到一个选择最优特征的目的。

文献[15]对特征选择方法进行了综述与展望。回顾了特征选择研究在一组众所周知的机器学习应用中的主要贡献。不平衡数据中出现了两个主要问题作为共同问题：大输入维度，以及小样本量。为了解决这些问题，生物信息学、机器学习和数据挖掘领域的研究人员设计了大量的特征选择技术。在过去几年中，在单变量滤波器特征选取技术的适应和建议方面进行了大量卓有成效的工作。一般而言，我们观察到，该领域的许多研究人员仍然认为滤波函数方法仅限于单变量方法。多元选择算法的提出可以被认为是生物信息学界最有前途的未来工作之一。未来研究的第二个方向是开发特别适合的集成特征选择方法，以增强最终选择的特征子集的鲁棒性。

3分类算法改进法

传统的分类算法（如朴素贝叶斯、SVM、C4.5或神经网络）在不平衡的数据集上表现出不令人满意的性能。 当数据集规模大且同时存在噪声时，情况可能会更糟。 由于它们不恰当地假定正负样本之间的相对平衡分布，少数类通常被忽略。为了在不平衡数据集上有更好的分类效果，应予对传统算法进行相应的改进。目前分类算法改进法大致可以分为：代价敏感学习法、集成学习法、单类学习法、主动学习法、硬例挖掘法等等。

代价敏感学习往往是对分类器错分代价进行修改。一般是对少数类错分代价进行判高。如Sahin[16]提出了一种成本敏感决策树方法。该方法在选择每个非终端节点处的拆分属性时最小化误分类成本之和，并将该方法的性能与现实世界信用卡数据集上众所周知的传统分类模型进行了比较。通过在欺诈检测系统中实施这种方法，可以更多地减少欺诈交易造成的财务损失。

集成学习也称为多分类器系统，已知通过组合几个基本分类器来提高单个分类器的性能，这些基本分类器的性能优于每个独立的分类器。经典的集成学习方法有Bagging、Boosting、Stacking法。为了更好学习类中的不平衡问题，文献[17]回顾了基于集成学习的方法。比较了6个基于Boosting、7个基于Bagging和2个混合集成学习算法在不平衡学习中的性能。在七个不平衡数据上评估这些方法的性能，这些数据的类不平衡比率从1.82到129.44。经过分析，证明了RusBoost集成算法在不平衡数据情况下优于其他集成。

单类学习是指对数据集中的某一类进行学习。比如多数类数据容易获得，可以只对多数类进行训练学习获得模型。然后在样本中直接识别此样本即可。单类学习法计算量要比上述方法更小，计算效率高。但样本边界难以确定。单类学习经典算法单类支持向量机还有其变体。单类支持向量机是一般支持向量机的一种特殊变体，单类支持向量机广泛用于异常检测。然而，实验表明，单类支持向量机对训练数据集中的异常值敏感。为了解决这个问题，文献[18]提出了一种鲁棒的单类支持向量机。通过设计惩罚因子，鲁棒的单类支持向量机可以抑制异常值的影响。基于稳健的单类支持向量机构造了故障检测方案。仿真实例表明，鲁棒单类支持向量机优于一般的单类支持向量机，特别是当训练数据集被离群值破坏时，基于鲁棒单类支持向量机的故障检测方法具有不错的性能。

主动学习的框架是识别信息丰富的未标记数据，然后从专家或实际中查询它们的真实标签。目标是使用尽可能少的查询标签来学习更准确的分类器。主动学习法常常与重采样、普通分类算法结合。比如用SMOTE算法得到初分类器，然后再用主动学习法调整分类器的精度，最终达到更好的分类效果。Fu[19]提出了一种确定性主动学习分类算法。在处理不平衡学习问题时，关注的是特定的局部分类行为，而不是整个全局分类行为。

硬例挖掘一般指对训练过程中的困难负样本再次的训练。硬例挖掘方法缓解了类内部的不平衡，因为其假设难以学习的样本信息更丰富，并强调了它们的重要性。文献[20]深入研究了类不平衡的本质。发现不仅类之间的不平衡，而且数据本质中的其他困难，特别是噪声和类重叠，阻碍了学习有效的分类器。考虑到这些因素，提出了一种新的不平衡分类框架，旨在通过欠采样自定步调协调数据硬度来生成一个强集合。

4总结

本文对平衡学习进行了综合研究。对已有的不平衡学习算法进行了整理。算法大致分为重采样法、特征选择法、分类算法改进法。重采样法可细分为过采样法、欠采样法、过采样欠采样相结合法。特征分类算法可分为过滤式、封装式和嵌入式方法。分类算法改进法又可以细分为代价敏感学习法、单类学习法、主动学习法、集成学习法、硬例挖掘法等。

关于重采样层面，采样规模难以确定是目前研究的难点。如何控制如何平衡是一个有趣的点。特征层面的研究方向可以从如何避开噪点，挖掘高表达能力的特征。分类算法上现有的工作没有明确地考虑到类间和类内的不平衡这两个不平衡，也许是一个新思路。还有深度学习如何应用到不平衡学习中也值得进一步的探索。

参考文献

[1]   Guo, H., Y. Li, et al., Learning from class-imbalanced data: Review of methods and applications. Expert Syst. Appl., 2017. 73: p. 220-239.

[2]   李艳霞, 柴毅, et al., 不平衡数据分类方法综述. 控制与决策, 2019. 34(04): p. 673-688.

[3]   徐玲玲,迟冬祥, 面向不平衡数据集的机器学习分类策略. 计算机工程与应用, 2020. 56(24): p. 12-27.

[4]   Chawla, N.V., K.W. Bowyer, et al., SMOTE: Synthetic minority over-sampling technique. Journal of Artificial Intelligence Research, 2002. 16: p. 321-357.

[5]   Fernández, A., S. García, et al., SMOTE for Learning from Imbalanced Data: Progress and Challenges, Marking the 15-year Anniversary. J. Artif. Intell. Res., 2018. 61: p. 863-905.

[6]   Liu, S., J. Zhang, et al., Fuzzy-Based Information Decomposition for Incomplete and Imbalanced Data Learning. Ieee Transactions on Fuzzy Systems, 2017. 25(6): p. 1476-1490.

[7]   方昊,李云, 基于多次随机欠采样和POSS方法的软件缺陷检测. 山东大学学报(工学版), 2017. 47(01): p. 15-21.

[8]   Laurikkala, J. Improving Identification of Difficult Small Classes by Balancing Class Distribution. in AIME. 2001.

[9]   Lin, W.-C., C.-F. Tsai, et al., Clustering-based undersampling in class-imbalanced data. Information Sciences, 2017. 409: p. 17-26.

[10]   Ng, W.W.Y., J. Hu, et al., persified Sensitivity-Based Undersampling for Imbalance Classification Problems. Ieee Transactions on Cybernetics, 2015. 45(11): p. 2402-2412.

[11]   Seiffert, C., T.M. Khoshgoftaar, et al., Hybrid sampling for imbalanced data. Integrated Computer-Aided Engineering, 2009. 16(3): p. 193-210.

[12]   Hou, X., T. Zhang, et al., Combating highly imbalanced steganalysis with small training samples using feature selection. Journal of Visual Communication and Image Representation, 2017. 49: p. 243-256.

[13]   Beyan, C.,R. Fisher, Classifying imbalanced data sets using similarity based hierarchical decomposition. Pattern Recognition, 2015. 48(5): p. 1653-1672.

[14]   Maldonado, S., R. Weber, et al., Feature selection for high-dimensional class-imbalanced data sets using Support Vector Machines. Information Sciences, 2014. 286: p. 228-246.

[15]   Saeys, Y., I. Inza, et al., A review of feature selection techniques in bioinformatics. Bioinformatics, 2007. 23 19: p. 2507-17.

[16]   Sahin, Y., S. Bulkan, et al., A cost-sensitive decision tree approach for fraud detection. Expert Syst. Appl., 2013. 40: p. 5916-5923.

[17]   Galar, M., A. Fernandez, et al., A Review on Ensembles for the Class Imbalance Problem: Bagging-, Boosting-, and Hybrid-Based Approaches. Ieee Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, 2012. 42(4): p. 463-484.

[18]   Yin, S., X. Zhu, et al., Fault detection based on a robust one class support vector machine. Neurocomputing, 2014. 145: p. 263-268.

[19]   Fu, J.,S. Lee, Certainty-based active learning for sampling imbalanced datasets. Neurocomputing, 2013. 119: p. 350-358.

[20]   Liu, Z., W. Cao, et al., Self-paced Ensemble for Highly Imbalanced Massive Data Classification. 2020 IEEE 36th International Conference on Data Engineering (ICDE), 2020: p. 841-852.

校级科研项目编号:KYKJ202002