新的基于代价敏感集成学习的非平衡数据集分类方法NIBoost

王莉 陈红梅 王生武

摘 要：现实生活中存在大量的非平衡数据，大多数传统的分类算法假定类分布平衡或者样本的错分代价相同，因此在对这些非平衡数据进行分类时会出现少数类样本错分的问题。针对上述问题，在代价敏感的理论基础上，提出了一种新的基于代价敏感集成学习的非平衡数据分类算法——NIBoost （New Imbalanced Boost）。首先，在每次迭代过程中利用过采样算法新增一定数目的少数类样本来对数据集进行平衡，在该新数据集上训练分类器;其次，使用该分类器对数据集进行分类，并得到各样本的预测类标及该分类器的分类错误率;最后，根据分类错误率和预测的类标计算该分类器的权重系数及各样本新的权重。实验采用决策树、朴素贝叶斯作为弱分类器算法，在UCI数据集上的实验结果表明，当以决策树作为基分类器时，与RareBoost算法相比，F-value最高提高了5.91个百分点、G-mean最高提高了7.44个百分点、AUC最高提高了4.38个百分点;故该新算法在处理非平衡数据分类问题上具有一定的优势。

关键词：非平衡数据集;分类;代价敏感;过采样;Adaboost算法

中图分类号： TP181

文献标志码：A

文章编号：1001-9081（2019）03-0629-05

Abstract： The problem of misclassification of minority class samples appears frequently when classifying massive amount of imbalanced data in real life with traditional classification algorithms， because most of these algorithms only suit balanced class distribution or samples with same misclassification cost. To overcome this problem， a classification algorithm for imbalanced dataset based on cost sensitive ensemble learning and oversampling — New Imbalanced Boost （NIBoost） was proposed. Firstly， the oversampling algorithm was used to add a certain number of minority samples to balance the dataset in each iteration， and the classifier was trained on the new dataset. Secondly， the classifier was used to classify the dataset to obtain the predicted class label of each sample and the classification error rate of the classifier. Finally， the weight coefficient of the classifier and new weight of each sample were calculated according to the classification error rate and the predicted class labeles. Experimental results on UCI datasets with decision tree and Naive Bayesian used as weak classifier algorithm show that when decision tree was used as the base classifier of NIBoost， compared with RareBoost algorithm， the F-value is increased up to 5.91 percentage points， the G-mean is increased up to 7.44 percentage points， and the AUC is increased up to 4.38 percentage points. The experimental results show that the proposed algorithm has advantages on imbalanced data classification problem.

Key words： imbalanced dataset; classification; cost sensitive; over-sampling; Adaboost algorithm

0 引言

非平衡數据集的分类是指在各类样本数目不相等的情况下的分类问题[1]。在实际应用中非平衡数据集分布广泛，比如医疗诊断、金融诈骗、网络入侵检测、电信用户检测、石油勘探等[2-6]。传统的分类算法大部分都以提高分类器总体分类精度为目标，然而当传统的分类算法应用在非平衡数据集上时很容易造成少数类的错分。国内外学者通过不断的研究，从算法层面和数据层面提出了许多改进优化的算法。数据层面主要是通过采样技术对数据集进行重构，以降低非平衡度进而提高分类准确率。常见的采样方法有两种：过采样和欠采样。欠采样是通过减少多数类样本个数使数据集分布相对平衡。过采样是通过增加少数类样本个数使数据集分布相对平衡。Chawla等[7]于2002年提出合成少数类过采样技术（Synthetic Minority Oversampling TEchnique， SMOTE）算法，其基本思想是在对样本集中所有的少数类样本，分别求出与其距离较近的少数类样本，然后在它们之间通过线性插值的方式来生成新的少数类样本，以降低数据集的非平衡度。算法层面主要有集成学习、代价敏感和单类别学习等算法。集成学习法是通过对多个基分类器进行集成从而获得更强的泛化性能。Qian等[8]提出将采样方法与集成学习理论相结合，其中运用的采样方法有欠采样和SMOTE算法。Douzas等[9]提出一种基于k-means聚类和SMOTE的简单、有效的过采样方法，该方法设法仅在安全区域进行过采样来避免产生噪声。Galar等[10]提出在集成学习中通过对基分类器进行选择，以提高其分类效率。Zhang等[11]提出通过将少数类与多数类多次组合，得到不同的训练样本集，然后再运用集成学习思想进行分类，其结果提高了少数类的分类精度。Kim等[12]提出GMBoost（Geometric Mean based Boosting）算法将弱分类器的评价标准由错误率改为多数类样本错误率与少数类样本错误率的几何均值，然后与采样算法相结合，以解决非平衡分类问题。李雄飞等[13]提出的PCBoost（Perturbation Correction Boosting）算法，该算法每次迭代开始时通过增加少数类样本的个数，平衡训练数据集，在子分类器形成后，删除分类错误的合成样本，然后通过多个基分类器的组合来解决非平衡的问题，其方法具有很好的泛化能力。He等[14]提出了一种新颖的集成模型，该模型拓展了BalanceCascade方法，且用随机森林（Random Forest， RF）和XGBoost（eXtreme Gradient Boosting）两种树型分类器作为基分类器，具有很高的性能和稳健性。代价敏感学习（Cost Sensitive Learning，SCL）[15]用于处理非平衡分类的基本思路是在非平衡分类中正确识别出少数类样本的价值比正确识别出多数类样本的价值要高，因此在分类中应赋予不同的损失代价。Fan等[16]提出的AdaCost算法是一种基于代价敏感的Boosting方法，该算法给予分错的少数类样本与多数类样本不同的代价因子，实验证明当以精度和召回率衡量分类结果时，AdaCost的性能优于其他版本的Boosting算法。Sun等[17]根据样本权重更新方式的不同，提出三种不同的代价敏感Boosting算法。Joshi等[18]提出的RareBoost算法按照每次迭代之后的TP/FP（True Positive/False Positive）与TN/FN（True Negative/False Negative）的比值分别为预测为正类的样本和预测为负类的样本进行权值更新。代价敏感学习也可以与传统的分类算法相结合，进而使传统分类算法具有代价敏感性[19-24]。

本文提出一种将代价敏感集成学习算法与过采样技术相结合的非平衡数据分类算法——NIBoost（New Imbalanced Boost）算法。其基本思想是首先采用GMBoost算法中多数类样本错误率与少数类样本错误率的几何均值作为分类器的评价标准。然后在每次迭代中融入NKSMOTE（New Kernel Synthetic Minority Over-Sampling TEchnique）算法，即通过增加少数类样本平衡数据集;然后在该数据集上训练分类器，随后根据TP/FP与TN/FN的比值分别为预测为正类的样本和预测为负类的样本进行权值更新，使得分类器在训练中更加关注被分错的样本。

1 相关基础知识

本章对相关的基础知识及对本文所提出的NIBoost算法中迭代过程需要用到的过采样算法（NKSMOTE）的基本原理进行介绍。

1.1 AdaBoost算法简介

AdaBoost基本思想是首先为数据集中的每个样本赋予一个初始权值，然后在该数据集上训练基分类器，最后根据基分类器的分类结果对样本权值进行更新，使得错分样本在后续训练时可以得到更多的关注。最后组合分类器的判决结果是所有弱分类器判决结果的加权和。AdaBoost算法流程如下。

1.2 代价敏感集成算法

非平衡数据集的分类问题中，少数类往往是分类的重点，即正确识别出少数类比识别出多数类样本具有更大的价值。代价敏感学习就是基于该思想设计，给错分的少数类样本赋予较高的错分代价。

1.3 SMOTE算法简介

SMOTE基本思想是通过人工合成新的少数类样本来改变样本分布。其基本原理是在相距较近的少数类样本之间进行线性插值，从而生成新的少数类样本。下面对SMOTE关键步骤进行简单的介绍。

1.4 核距离

将样本通过非线性映射函数映射到核空间，在核空间中度量的样本之间的距离称为核距离。NKSMOTE算法中涉及核距离的计算，对于核空间中任意两个样本点φ（x）和φ（y），其核距离计算如下：

目前常用的核函数有高斯核函数、多项式核函数、S型核函数等。

1.5 NKSMOTE算法简介

1）对任意少数类样本x在核空间上寻找距其最近的K个样本。根据其K个样本近邻中少数类样本的个数与多数类样本的个数的比例，将少数类样本x分为安全样本，危险样本，噪声样本。若少数类样本的个数多于多数类样本的个数，则少数类样本x为安全样本;若少数类样本的个数少于多数类样本的个数，且存在少數类样本，则少数类样本x为危险样本;若全是多数类样本则该少数类样本x为噪声样本。

2）若少数类x不是噪声样本，则从其K近邻中随机选择两个样本，在三个样本之间按照一定的合成规则合成N个新样本，其中N值是向上采样倍率。若选中的两个样本y1，y2均是多数类样本，则利用式（12）和（13）得到新的少数类样本。

3）若少数类样本x是噪声样本，对其进行过采样时有给数据集引入噪声的风险，但是噪声样本又有其积极作用，为了使风险降到最低，设定其向上采样倍率N为1。在其余少数类样本中随机选择一个少数类样本y，在x与y之间进行随机线性插值，其中增量因子是一个在（0.5，1）区间上服从均匀分布的随机数，使新的少数类样本更靠近样本y。

2 NIBoost算法基本原理

本文所提出的NIBoost算法是一种结合了代价敏感和过采样技术的Boosting算法。它能在每次迭代的过程中逐渐地增加少数类样本的数目来平衡数据集和调整错分样本的权重，使得最终训练出来的强分类器对非平衡数据集有很高的分类性能。

2.1 NIBoost原理介绍

2.2 NIBoost的时间复杂度分析

由于所提出的算法需要用到NKSMOTE算法来平衡训练数据集，故NIBoost算法的时间复杂度要高于一般的Boost算法。若各变量符号如之前的算法流程所示，数据集的大小为n，算法的迭代次数为T，则在数据的预处理阶段，需要为各个样本初始化权重，时间复杂度为O（n）;然后调用NKSMOTE算法来生成新的少数类，当计算少数类与其他样本的距离时，时间复杂度为O（f·ni·（m+n）），再将距离排序，其时间复杂度为O（n log（n）），其中： f是样本的特征个数，ni表示在第i次迭代过程中少数类样本的个数，m为之前迭代过程中新增的少数类样本个数总和。最后更新样本权重的时间复杂度也为O（n+m）。因为少数类样本的数量ni远小于样本个数n，新增的少数类样本个数m也不会超过n，算法共要迭代T次，故NIBoost的整体时间复杂度可简化为O（2·T·f·n2）。

3 实验设计与结果分析

为了验证本文所提算法的有效性，在实际的非平衡数据集上用NIBoost算法对其分类。对实验结果的分析证明，NIBoost算法在处理非平衡数据集时具有一定的优势。

3.1 数据集

实验所用数据集来自UCI数据库，表1列出了这些非平衡数据集的基本信息，包括数据集名称、样本数、属性数、少数类数以及非平衡度（Imbalanced Rate， IR）。

3.2 评价标准

在传统分类学习方法中，一般采用分类精度作为评价指标，然而对于非平衡数据集而言，用分类精度来评价分类器的性能是不合理的。在机器学习领域中对于非平衡数据分类的常用评价标准有ROC（Receiver Operating Characteristic）曲线、AUC（Area Under Curve）以及基于混淆矩阵的F-value，G-mean。在非平衡数据学习中，少数类对应为正类，多数类对应为负类，表2给出了二分类问题的混淆矩阵。

根据混淆矩阵可以得到以下评价指标。

如果同时关注两个类的性能，可以使用G-mean评价算法在两个类上的性能：

3.3 实验结果及分析

实验用Java实现SMOTE、RareBoost、PCBoost、NIBoost算法，采用决策树（J48）、朴素贝叶斯（Naive Bayesian， NB）算法为基分类器算法。实验采用五折交叉验证。表3展示了上述4个算法在5个数据集上的F-value值、G-mean值、AUC值的比较结果。

通过对表3的观察可以发现，当以J48作为基分类算法，用F-value作为评价度量时，在所有数据集上，NIBoost均比PCBoost、RareBoost效果好，比PCBoost最高提高了2.3个百分点，比RareBoost最高提高了5.91个百分点;除了在数据集ecoli3上略逊于SMOTE外，在其他数据集上NIBoost均比SMOTE算法效果好，最高提高了2个百分点。当用G-mean作为评价度量时，在所有数据集上，NIBoost均比RareBoost、SMOTE效果好，比RareBoost最高提高了7.44个百分点;除了在数据集ecoli1上略逊于PCBoost外，在其他数据集上NIBoost也都比PCBoost效果好。当用AUC作为评价度量时，在所有数据集上，NIBoost均比SMOTE、RareBoost效果好，比SMOTE最高提高了1.54个百分点，比RareBoost最高提高了4.38个百分点;除了在数据集ecoli3、yeast3上略逊于PCBoost外，在其他数据集上NIBoost均比PCBoost效果好。

当以NB作为基分类算法，用F-value作为评价度量时，除了在数据集ecoli1上略逊于SMOTE外，在其他数据集上NIBoost均比SMOTE算法效果好，最高提高了3.9个百分点;除了在数据集ecoli1上NIBoost略逊于PCBoost外，在其他数据集上NIBoost均比PCBoost效果好，最高提高了5.22个百分点;在所有数据集上，NIBoost均比RareBoost效果要好，最高提高了9.6个百分点。当用G-mean作为评价度量时，在所有数据集上，NIBoost均比SMOTE、RareBoost效果好，比SMOTE最高提高了2.3个百分点，比RareBoost最高提高了20.3个百分点;除了在数据集ecoli1上NIBoost略逊于PCBoost外，在其他数据集上NIBoost均比PCBoost效果好。当用AUC作为评价度量时，除了在数据集ecoli1、yeast3上略逊于SMOTE外，在其他數据集上NIBoost均比SMOTE算法效果好，最高提高了1.74个百分点;除了在数据集ecoli1上略逊于PCBoost外，在其他数据集上NIBoost均比PCBoost效果好，最高提高了4.1个百分点;在所有数据集上，NIBoost均比RareBoost算法效果好，最高提高了16.14个百分点。

所以总的来说，NIBoost算法在处理非平衡数据时具有一定的优势。

4 结语

针对非平衡数据集的分类问题，本文从算法层面入手，结合RareBoost算法和GMBoost算法的思想，给出一种将代价敏感思想与过采样技术相结合的非平衡数据分类算法——NIBoost算法。该算法是在每次迭代中融入过采样算法（NKSMOTE），即通过增加少数类样本逐步平衡数据集;然后在该数据集上训练分类器。随后根据样本的原始类标与分类结果分别进行权值调整。实验结果表明NIBoost算法具有更好的分类性能。进一步的研究工作是将欠采样和集成学习的思想融合起来以解决非平衡数据分类困难的问题。

参考文献 （References）

[1] WEISS G M， ZADROZNY B， SAAR M. Guest editorial： special issue on utility-based data mining [J]. Data Mining and Knowledge Discovery， 2008， 17（2）： 129-135.

[2] del CASTILLO M D， SERRANO J I. A multistrategy approach for digital text categorization from imbalanced documents [J]. Association for Computing Machinery Special Interest Group on Knowledge Discovery and Data Mining ExplorationsACM SIGKDD Explorations Newsletter， 2004， 6（1）： 70-79.

[3] WEI W， LI J， CAO L. Effective detection of sophisticated online banking fraud on extremely imbalanced data [J]. World Wide Web， 2013， 16（4）： 449-475.

[4] 江颉，王卓芳，GONG R S，等.不平衡数据分类方法及其在入侵检测中的应用研究[J].计算机科学，2013，40（4）：131-135.（JIANG J， WANG Z F， GONG R S， et al. Imbalanced data classification method and its application research for intrusion detection [J]. Computer Science， 2013， 40（4）： 131-135.）

[5] KUBAT M， HOLTE RC， MATWIN S. Machine learning for the detection of oil spills in satellite radar images [J]. Machine Learning， 1998， 30（2）： 195-215.

[6] SCHAEFER G， NAKASHIMA T. Strategies for addressing class imbalance in ensemble classification of thermography breast cancer features [C]// Proceedings of the 2015 IEEE Congress on Evolutionary Computation. Piscataway， NJ： IEEE， 2015： 2362-2367.

[7] CHAWLA N V， BOWYER K W， HALL L O. SMOTE： synthetic minority over-sampling technique [J]. Journal of Artificial Intelligence Research， 2002， 16（1）： 321-357.

[8] QIAN Y， LIANG Y， LI M. A resampling ensemble algorithm for classification of imbalance problems [J]. Neurocomputing， 2014， 143： 57-67.

[9] DOUZAS G， BACAO F， LAST F. Improving imbalanced learning through a heuristic oversampling method based on k-means and SMOTE [J]. Information Sciences， 2018， 465： 1-20.

[10] GALAR M， FERNANDEZ A， BARRENECHEA E. Ordering-based pruning for improving the performance of ensembles of classifiers in the framework of imbalanced datasets [J]. Information Sciences， 2016， 354： 178-196.

[11] ZHANG Y， ZHANG D， MI G. Using ensemble methods to deal with imbalanced data in predicting protein-protein interactions [J]. Computational Biology and Chemistry， 2012， 36（2）： 36-41.

[12] KIM M J， KANG D K， KIM H B. Geometric mean based boosting algorithm with over-sampling to resolve data imbalance problem for bankruptcy prediction [J]. Expert Systems with Applications， 2015， 42（3）： 1074-1082.

[13] 李雄飛，李军，董元方，等. 一种新的不平衡数据学习算法PCBoost [J]. 计算机学报， 2012， 35（2）： 202-209.（LI X F， LI J， DONG Y F， et al. A new learning algorithm for imbalanced data PCBoost[J]. Chinese Journal of Computers， 2012， 35（2）： 202-209.）

[14] HE H， ZHANG W， ZHANG S. A novel ensemble method for credit scoring： adaption of different imbalance ratios [J]. Expert Systems with Applications， 2018， 98： 105-117.

[15] 付忠良.多标签代价敏感分类集成学习算法[J]. 自动化学报， 2014， 40（6）： 1075-1085.（FU Z L. Cost-sensitive ensemble learning algorithm for multi-label classification problems [J]. Acta Automatica Sinica， 2014， 40（6）： 1075-1085.）

[16] FAN W， STOLFO S J， ZHANG J， et al. AdaCost： misclassification cost-sensitive boosting [C]// ICML 99： Proceedings of the 16th International Conference on Machine Learning. San Francisco， CA： Morgan Kaufmann Publishers， 1999： 97-105.

[17] SUN Y， KAMEL M S， WONG A K C. Cost-sensitive boosting for classification of imbalanced data [J]. Pattern Recognition， 2007， 40（12）： 3358-3378.