分类是机器学习、数据挖掘领域的重要研究内容，通过对输入的训练样本数据进行分析、学习后获得决策模型，随后即可对未知样本进行预测。目前，已经有许多经典的分类算法，例如决策树、支持向量机、人工神经网络，这些算法在类别数据分布均匀的条件下具有良好的分类性能，得到了广泛应用。但是，在许多实际应用领域中，存在着非常明显的类别不平衡数据，例如信用卡欺诈检测、医疗疾病诊断、网络入侵检测等，在这些情况的分类处理过程中，少数类需要受到特别关注，往往具有更大的误分类代价，然而传统分类算法基于平衡的数据分布或者相等的误分类代价之基本假设，为保证算法总体分类准确率，通常将少数类错分至多数类，从而导致少数类识别准确率过低。因此，传统分类算法面对类不平衡数据，分类效果不佳。

当前，不平衡数据分类问题的解决方法主要有3个方面:1) 数据层面，移除部分多数类样本或者增加新的合成样例，改变数据分布，降低不平衡度，称之为重采样方法^{[1, 2, 3, 4, 5]}；2) 算法层面，分析已有算法在面对不平衡数据分类的缺陷，改进算法或者提出新算法来提升少数类的分类准确率，例如代价敏感学习^[6]、集成学习^{[7, 8]}、单类学习^[9]等；3) 评价标准层面，提出新的适合不平衡数据分类的分类器性能评价标准，常见的有基于混淆矩阵基础上的少数类精确度与召回率的调和均值F_measure ^[10]，几何均值G_mean ^[11]和ROC曲线等。

本文从数据层面和算法层面着手，融合数据采样和boosting技术，提出在动态平衡采样基础上集成提升的不平衡数据分类算法，目标旨在提高小类样本的分类精度。为了论述方便，后续部分将少数类称之为正类，多数类称之为负类。

1 采样方法

数据层面的采样技术针对不平衡数据特点，通过过采样、欠采样等方式进行数据处理，以期获得一个相对均衡的数据分布。相关研究表明，平衡的数据分布更加有利于提高传统算法的分类性能^{[12, 13]}。

1.1 过采样

最简单的过采样是随机过采样，其随机选择若干正类样本，随后简单复制该样本，添加至训练集。随机过采样仅仅复制正类样本，没有增加任何新的额外合成样例，对于提高正类识别率没有多大帮助；另外，当数据不平衡度非常高时，需要在正类上进行多倍采样才能使最终数据分布趋于平衡，结果使得训练数据规模变大，分类器学习到的决策域变小，容易导致过拟合。

针对随机过采样的不足，Chawla等^[3]提出一种SMOTE(synthetic minority over-sampling technique)方法，该方法为每个正类样本选择若干(5或者7)个近邻，随后在选定样本与近邻样本之间进行线性插值，生成无重复的合成样例。SMOTE方法能够使正类的决策边界远离负类空间，正类具有更大泛化空间；但是其缺点是没有考虑近邻样本的分布特点，合成样例具有一定的盲目性，容易产生噪声样例，以及出现类间混叠现象，影响后续分类器的分类性能。

为了解决SMOTE方法的不足之处，基于SMOTE的改进算法相继被提出。Han等^[10]提出仅为靠近类边界的正类样本生成合成样例的Borderline-SMOTE方法，更有利于分类器的学习，但是需要依据输入的近邻参数k来确定正类边界样本集合，如何合理确定参数k以及科学判断边界有待深入研究。He等^[14]提出ADASYN算法，将输入数据的密度分布作为确定合成样例数目的依据，自适应方式控制正类样本的分布。Batista等^[15]提出SMOTE+Tomek算法，该方法利用SMOTE生成合成样例；利用Tomek算法对连接样例进行移除，较好地克服了SMOTE带来的噪声问题。

1.2 欠采样

随机欠采样是随机性减少负类样本，其方法简单，操作容易，但是存在去除样本的盲目性和去除样本比例参数不确定问题，以及代表性样本的丢失而影响分类精度。

Kubat等^[16]将在负类上的单边采样与Tomek links相结合，利用Tomek link删除噪声样本，利用压缩最近邻算法删除远离边界区域的样本，将剩下的负类样本与所有正类样本一起构成训练集，用于分类器学习。

文献^{[17, 18, 19, 20]}提出利用聚类提取代表性样本的平衡数据分布的方法。算法首先对负类样本进行聚类操作，聚类个数与正类样本数目相同，然后提取各个聚类质心作为聚簇的代表样本，与所有正类样本一起组成平衡训练集。由于用聚类质心代表聚簇内的所有样本，不可避免地损失了数据分布的特征信息，使得抽样后的数据分布与原始数据分布出现一定的差异，从而影响算法的分类性能。

由上述分析可知，过采样和欠采样均存在一定的局限性：

1)过采样不断合成新的正类合成样例使得数据规模变大，增加了算法的学习时间；

2)过采样使得分类器训练得到的决策域变小，容易导致过拟合；

3)欠采样存在富含分类信息样本丢失问题，特别是在高度不平衡数据集中，移除过多负类样本使得信息丢失严重，造成样本代表性差，严重背离初始数据分布；

4)欠采样难以合理确定抽样比例参数。

针对过采样和欠采样方法存在的局限性，本文提出基于动态平衡采样的不平衡数据集成分类方法，在集成迭代的每次数据采样过程中，无需给定抽样比例参数，而是基于随机生成的样本规模数值，或者对正类进行过采样，或者在负类上进行欠采样，获得类别平衡的训练集，然后参与后续的集成算法训练。

2 动态平衡采样不平衡数据分类方法

本文算法包括动态平衡采样的训练数据获取和子分类器学习2个步骤，主要包括4个阶段：1)对初始数据集的各个样本设置相同的初始权值；2)调用动态平衡采样算法，生成合成样例，组成样本规模一致的训练集，对于新生成的合成样例，需要赋予权值；3)应用AdaBoost算法，生成子分类器，之后根据子分类器的分类情况对初始训练集的各个样本进行权值更新，以及权值归一化；2)、3)重复迭代执行T次；最后将T个子分类器集成。

2.1 动态平衡采样

作为数据预处理的采样技术，需要预先确定数据采样参数，不合理的数据采样参数会导致生成的数据分布严重背离初始数据分布，进而影响算法的分类性能。动态平衡采样依赖随机函数产生的数值确定各类别的采样方式及采样比例，通过重复多次的动态提取初始数据集的样本，获取充分的数据分布特性信息，降低富含分类信息样本点丢失现象。整体算法如算法1所示。

算法1 动态平衡采样算法

输入 初始数据集 S={x_i,y_i}_i=1^m,y_i∈Y={+1,-1}，+1表示正类样本，-1表示负类样本；

输出 新数据集S′。

1) 计算集合S中的样本数目，负类样本集合S_N，其数量记为a，正类样本集合S_P的样本数记为b，m=a+b；

2) 利用随机函数，生成一个随机整数k，2<k<m-2；

3) 如果k<a，则从数据集S_N中进行随机欠采样，采样数目为k，将其加入集合S′，在集合S_P中应用SMOTE进行过采样，生成m-k-b个新合成样例，连同S_P中的b个样本，均加入集合S′；

4) 如果k≥a，则从数据集S_P中进行随机欠采样，采样数目为m-k，将其加入集合S′，在集合S_N中应用SMOTE进行过采样，生成k-a个合成样例，连同S_N中的a个样本，都加入集合S′；

5)输出集合S′ 。

算法依据2)中所产生的随机整数值大小来决定相应的采样操作，如果产生的随机数k小于初始数据集的负类样本数量，则在负类样本集进行欠采样，在正类样本集进行过采样，使得最终输出集合S′的样本数量与初始数据集数量一致，反之，则进行相反的采样。与传统的采样方法不同的是，在步骤4中对正类样本进行欠采样，对负类样本进行过采样，通过随机函数产生的随机数，使得输出集合S′在总数量一定的情况下保持对对各类别样本的中立性。

2.2 训练样例权值更新

在第t次迭代过程中，需要对两个集合中的样例权重进行更新，分别是动态平衡采样后的输出集合S′和子分类器形成之后的初始数据集S。

分析动态平衡采样算法过程可知，经过数据采样之后，新数据集S′的样例总数与初始数据集S一致，均为m，其中包括从数据集S抽取的部分样例，以及部分由SMOTE方法产生的合成样例。S′中的样本权值按照式(1)更新：

第t次迭代训练结束时，AdaBoost分类算法在数据集S′进行学习后得到子分类器h_t:x→{-1,+1},t=1,2，…,T,h_t(x)给出数据集S中的样例x的所属类别，根据子分类器的分类情况，更新样本权值，增加错分样本的权值，减少正确分类样本权值，以便下次迭代时，“错分”样本得到更多关注。

计算子分类器h_t(x)的分类错误率ε_t：

计算子分类器投票权重α_t：

更新样例权值:

完整算法如算法2所示。

算法2 动态平衡采样的不平衡分类算法

输入 初始数据集 S={x_i,y_i}_i=1^m,y_i∈Y={+1,-1}，其中+1表示正类样本，-1表示负类样本；

输出 H(x)=arg${\max _{y \in Y}}\sum\nolimits_{t = 1}^T {{\alpha _t}{h_t}\left( x \right)} $。

1) 初始化数据集S中各个样本权重D₁(i)=${1 \over m}$；

2) for t=1,2,…,T

① 调用动态平衡采样算法，获得数据集S′；

② 利用式(1)设置S′中的样例权值；

③ 使用数据集S′及其中的样例权值，训练基于AdaBoost算法的子分类器h_t(x)；

④ 按照式(2)计算分类器h_t(x)的误差ε_t，按照式(3)计算h_t(x)的投票权重α_t；

⑤ 按照式(4)更新数据集S中的样本权重；

3)输出模型：H(x)=arg ${\max _{y \in Y}}\sum\nolimits_{t = 1}^T {{\alpha _t}{h_t}\left( x \right)} $。

3 实验结果与分析

3.1 评价度量

传统分类器采用分类精度指标衡量分类性能，其追求整体分类准确率，忽略了在不平衡数据分类过程中需要特别关注的正类分类准确率。针对不平衡数据，许多学者提出了在两类混淆矩阵基础上的F_measure^[10]、G_mean^[11]等评价方法。

在混淆矩阵中，TP(true positive)、FN(false negative)、TN(true negative)、FP(false positive)分别代表分类正确的正类样本、假的负类样本、正确的负类样本以及假的正类样本的数目。基于混淆矩阵，F_measure定义如下: $${F_{{\rm{measure}}}}{\rm{ = }}{{\left( {1 + {\beta ^2}} \right) \times {\mathop{\rm Re}\nolimits} {\rm{call}} \times \Pr {\rm{ecision}}} \over {{\beta ^2} \times {\mathop{\rm Re}\nolimits} {\rm{call}} + \Pr {\rm{ecision}}}}$$ 式中：Recall为查全率，Precision为查准率，${\mathop{\rm Re}\nolimits} {\rm{call}} = {{{\rm{TP}}} \over {{\rm{TP}} + {\rm{FN}}}},\Pr {\rm{ecision}} = {{{\rm{TP}}} \over {{\rm{TP}} + {\rm{FP}}}}$，β用于调节Recall和Precision的相对重要性，通常取为1。

F_measure定义说明：较大值表示Recall和Precision都较大，因此，其能够较好评价正类分类性能。

G_mean其定义如下： $${G_{{\rm{mean}}}} = \sqrt {{\rm{TPR}} \times {\rm{FPR}}} $$ 式中 $${\rm{真正率}} {\rm{TPR}}{\mathop{\rm Re}\nolimits} {\rm{call}} = {{{\rm{TP}}} \over {{\rm{TP}} + {\rm{FN}}}}$$ $${\rm{真负率}} {\rm{FPR}}\Pr {\rm{ecision}} = {{{\rm{TN}}} \over {{\rm{TN}} + {\rm{FP}}}}$$

G_mean兼顾了正类准确率和负类准确率，比整体分类准确率更适合于不平衡数据分类评价。

本文使用F_measure准则来衡量正类的分类性能，使用G_mean准则来衡量数据集整体分类性能。

3.2 UCI数据

为了检验本文所提方法的有效性，选择6组具有实际工程应用背景的UCI数据^[21]进行测试，对于含有多个类别的数据，取其中某个类为正类，合并其余类为负类，各数据集的基本信息见表 1。

3.3 实验结果及分析

实验中对比算法如下：

1)随机森林(random forest，RF)算法，RF算法作为一种集成算法，在处理不平衡数据时有独特的优势，能够在某种程度上减少不均衡数据带来的影响^[22]，因此将其直接应用在初始不平衡数据集进行分类。

2)SMOTEBoost^[23]算法，将SMOTE方法与AdaBoost.M2结合，在每次集成迭代中生成新的合成样例，使得分类器更加关注小类样本。

3)RUSBoost^[24]，与SMOTEBoost方法相类似，采用随机欠采样从负类样本中随机移除样例，然后应用AdaBoost进行多次迭代。

4)文献^[4]提出的集成方法K-means+Bagging，首先在负类样本上应用K-means聚类，提取与正类样本数量一致的聚类质心，组成平衡训练集，参与Bagging集成。

上述3种集成方法以及本文算法均使用C4.5决策树算法作为基分类器算法。

为客观对比上述不平衡数据分类方法，实验数据采用10折交叉验证方式，重复10次，以平均值作为最终的分类结果。

表 2和表 3分别列出5种方法在6个UCI数据集上的正类F_measure值和数据集整体的G_mean值，最后一行列出每种方法在所有数据集上的平均结果。

从表 2的F_measure值可以看出，本文方法除了在sick数据集稍微低于SMOTEBoost算法之外，在其他5个数据集上均有最佳表现，比较各种算法在6组UCI数据上的平均值，本文方法比随机森林RF算法有14.2%的提升，与基于聚类欠采样的集成算法相比有27.3%的提升，说明本文所提方法在少数类分类性能方面有巨大的提升。

比较各个算法的整体分类性能G_mean，从表 3可以看出，本文方法也仅在sick数据集上稍逊于最优算法SMOTEBoost，二者精度相差不超过1‰；在6个数据集上的平均分类性能上，本文方法获得最优精度。

结合表 1~3可以看出，随着数据不平衡度的提高，无论是随机欠采样还是基于聚类的欠采样，由于都会对原始数据集造成样本丢失，分类性能都有所下降，特别是在letter和page-blocks数据集上，差距比较明显。与之对比，本文方法在数据采样过程中也需要对某类样本进行欠采样，通过多次动态、随机性采样调和，使得抽样数据能够较好地保持对原始数据的分布；与此同时，对另外一类样本进行SMOTE过采样，在没有增加数据规模条件下，保持对各类样本的中立性，或者对正类过采样，或者对负类过采样。从最终分类结果来看，本文方法在不降低数据集整体G_mean值的基础上，提高了正类的F_measure值，对正类和负类都具有较高的识别率。

本文算法中经过动态平衡采样后参与基分类器训练的数据集样本规模与初始数据集一致，即集合数据大小比例为100%，为考察参与训练的不同数据规模比例对算法分类性能的影响，选取本文算法、随机森林和SMOTEBoost 3种算法，同时选择以letter数据集为例，在20%~100%范围内每次增加20%比例的数据，参与集成学习，迭代10次，相关算法的F_measure、G_mean均值如图 1所示。

图 1 不同数据规模对分类性能影响Fig. 1 Performance measures of different ensemble size

图选项

从图 1可看出，随着参与训练数据集比例的增大，无论是正类分类性能还是整体分类精度，都有所上升，但是随着数据比例的增大，相应的分类性能提升幅度有限。另外，在数据比例为20%、40%时，3种算法相对应的F_measure和G_mean值几乎是线性提升，这说明过低比例的抽样数据由于损失太大的原始数据分布信息，会严重影响算法的分类性能。

4 结束语

针对类别不平衡数据分类问题，本文提出了一种混合数据采样与Boosting技术相结合的集成分类方法。该方法统筹运用欠采样和过采样，在保持训练集数据规模一致条件下，灵活调整各类别样本数量比例，较好地保持原始数据分布，然后采用Boosting技术进行多次迭代学习，获得更强性能分类器。实验结果表明，该方法能够有效提高正类样本的分类性能。

由于数据集本身的多样性和复杂性，诸如类重叠分布、噪声样本等均会影响不平衡数据性能，如果进行有针对性的数据预处理工作，将会使得动态平衡采样的数据分布更加合理，对正类的分类性能将会进一步提高。此外，将本文方法应用于多类别不平衡数据分类，也是今后需要进一步研究的方向。