一种不平衡数据集成分类方法

王思晨 丁家满

摘要：不平衡数据在各个应用领域普遍存在。在处理不平衡数据时，破坏原始数据的分布特点和丢弃多数类样本的潜在信息都会降低分类精度，为此，提出一种不平衡数据集成分类方法。从多数类样本中依据计算得到的综合权重进行随机采样，并与少数类样本组成新的训练样本子集；为了保证基分类器的差异性，将投影得到的不同样本子集作为各个基分类器的训练样本，通过多分类器集成学习获得最终分类结果；在UCI数据集下进行实验。结果表明，该方法不仅能够提高少数类样本的分类性能，而且能够有效提高整体分类精度。

关键词：不平衡数据；分类；集成学习；综合权重

DOIDOI：10.11907/rjdk.173258

中图分类号：TP301

文献标识码：A 文章编号文章编号：1672-7800（2018）008-0076-05

英文摘要Abstract：Imbalanced data is widespread in various application fields.When dealing with imbalanced data，breaking the distribution characteristics of the original data and discarding the latent information in the majority class samples will decrease classification accuracy.Therefore，in this paper，an integrated classification method for imbalance data is proposed.Firstly we randomly extract from the majority samples based on the calculated comprehensive weight，combine the extracted samples with the minority samples into new training samples； then，in order to ensure the difference between the base classifiers，we use the same subset of projections as the training samples of each base classifier，and get the final classification results by ensemble learning of multiple classifiers.Finally，experiments have been done on UCI data sets and the results show that this method can not only improve the classification performance of the minority class samples，but also effectively improve the overall classification accuracy.

英文关键词Key Words：imbalance data；classification；ensemble learning；comprehensive weight

0 引言

分类是数据挖掘、机器学习领域研究的重要内容，可以有效帮助人们对获取的数据进行预测分析、对未知的模式样本进行判断识别。目前，已有许多经典的分类算法，例如人工神经网络、决策树、支持向量机（SVM）等，用它们对平衡数据进行分类一般都能取得较好的分类效果。但是在实际应用中不平衡数据普遍存在于各个应用领域，例如文本分类[1]、疾病诊断[2]以及网络入侵检测[3]等。然而传统分类算法为了追求总体分类性能，通常只基于平衡数据分布或者忽略样本中的少数类样本，从而导致少数类样本分类准确率过低，分类器性能下降[4-7]。因此，研究用于处理不平衡数据集的分类方法，有效提高对少数类的分类准确率与分类器的整体性能显得尤为重要。

当前，不平衡数据分类问题的解决思路主要包括改变数据分布和改进已有分类算法。改变数据分布以达到数据平衡最常见的策略有随机过采样（over-sampling）、随机欠采样（under-sampling）[8-9]。随机过采样是指对少数类的样本进行复制，使数据集的样本数达到平衡，随机欠采样则以一定策略选取多类样本中的一个子集达到同样目的。过采样中应用最广泛的是 Chawla 等[10]提出来的SMOTE 算法，该算法的本质是改进随机过采样策略，通过扩充少数类样本集使得样本数目达到均衡。文献[11]提出基于RSBoost算法的不平衡数据分类方法，该方法采用SMOTE算法对少数类进行过采样处理，然后对整个数据集进行随机欠采样处理，以改善整个数据集的不平衡性，提高少数类的分类准确性。文献[12]针对采用随机过采样处理不平衡数据后，可能会导致不平衡数据集分布的整体变化以及模糊正负类边界问题，提出基于 KM-SMOTE 和随机森林的不平衡数据分类方法。文献[13]提出的RUSBoost算法是在AdaBoost算法迭代过程中采用随机欠采样技术（RUS）从多数类中随机选择样本，但不分配新的权重，从而使算法更加关注少数类样本，该算法具有实现简单、训练时间短等优势，但是在欠采样中可能会移除潜在的有用多数类样本。文献[14]提出了EusBoost算法，采用欠采样方法选择多数类样本中具有代表性的样本，实现样本数据平衡，并引入适应度函数保证基分类器的差异性，最终提高不平衡数据的分类精度。文献[15]提出一种新的不平衡数据学习算法PCBoost，该算法用数据合成方法添加合成的少数类样本，以平衡训练样本。文献[16]提出一种处理不平衡数据的欠采样方法，用以解决因样本过于集中导致的过拟合问题。文献[17]提出一种过采样算法，将过采样与欠采样进行融合，利用过采样的优点增加少数类样本数量，使分类器能够更好地提高少数类的分类性能。文献[18]提出多类类别不平衡学习算法EasyEssemble M，该算法采用多数类样本多次随机欠采样方法，学习多個子分类器提高分类效果。虽然以上通过改变数据分布达到数据平衡的算法能够在一定程度上解决多类类别不平衡问题，但是存在一定的局限性：简单机械地采样将破坏原始数据的分布特点，移除过多的多类样本将会导致信息丢失[19]。

现有不平衡数据处理方法的另一种思路是改进已有分类算法。如文献[20]在AdaBoost算法基础上使用基于级联模型的分类器，以逐步缩小多类别，使数据集趋于平衡，通过迭代训练得到一系列分类器并以集成方式对预测样本进行分类。文献[21，22]针对现有AdaBoost系列算法未考虑类的先验分布问题，改进并提出了不平衡分类问题连续AdaBoost算法。文献[23]在SVM分类算法基础上，针对不平衡数据导致SVM的分类超平面偏移问题，提出了一种改进 SVM-KNN 算法。这些改进方法能够在某种程度上提高分类精度，但泛化性不够强大，并且算法参数和阈值的设定或选取存在一定主观性，稍有不当将破坏原始数据的分布特点且无法充分利用多数类样本潜在信息[24]。

综上所述，虽然以上两种思路及方法能够在特定环境下一定程度上解决数据不平衡问题，但是数据平衡按比例机械地抽样将破坏原始数据的分布特点，而对多数类样本进行简单抽样则可能移除潜在有用分类信息，导致分类效率低、分类精度差等问题。

针对上述问题，本文提出一种不平衡数据集成分类方法（Integrated Classification Method for Imbalanced Data，简称ICMID），首先多数类样本中依照多数类样本的权重以及少数类样本得到的综合权重进行不放回随机抽取，并与少数类样本组成训练样本集；再随机选取若干项特征构造特征子集，将特征子集对训练样本子集进行投影，得到的对应特征子集样本作为算法训练基分类器的训练样本，经过多次迭代产生多个弱分类器，通过弱分类器权重投票得出最终输出结果。因此，在保证基分类器差异性的前提下，提高了少数类的分类准确率，还挖掘了多数类样本中的潜在有用信息。

1 问题描述与建模

2 不平衡数据集成分类方法

为了保持原始数据的分布特点，更好地利用潜在有用的分类信息，保证集成学习中各分类器之间的差异性，本文提出基于综合权重的不平衡数据集成分类方法。主要包括3个阶段：①去除多数类中的噪声样本；②通过综合样本权重抽取多数类样本生成合成样本集；③训练不同的基分类器进行集成分类。具体流程如图1。

2.1 不平衡数据处理

为了保持原有样本的分布特点，同时又能更好地利用多数类样本中潜在有用的信息，在不平衡数据处理阶段，首先循环随机选取n个特征子集，然后按照少数类样本的数量和多数类样本中每个类别样本数量占比计算综合权重，并依据综合权重抽取每一类别的样本数量，再将少数类样本与抽取的样本组合，使少数类样本在训练样本中所占比例升高，重复抽取M次，最后获得处理过的训练样本子集和特征子集。具体过程见算法1。

为了增强分类器之间的差异性以及提高分类准确率，做法如下：第一，根据特征子集Fi对训练样本子集D′j进行投影，得到相对应特征子集的样本Yij，将该样本作为训练基分类器的样本；第二，初始化样本权重；第三，通过T次迭代训练得到多个弱分类器，在每次迭代中计算每个基分类器的错误率，判断分类错误率是否超过给定阈值，当超过给定阈值时，说明该部分样本分类困难，则退出迭代过程进行下一轮，当错误率小于给定阈值时，依据错误率更新权重；第四，依据所有基分类器错误率以及分类正确的样本个数综合计算投票权重，得出最终输出结果。具体过程见算法2。

3 实验与结果

3.1 实验数据

为评价本文方法对不平衡数据集分类问题的有效性，选择6个少数类和多数类样本比例不平衡的数据集进行实验，数据集来源于 UCI 机器学习数据库，见表1。其中数据集样本数用#Ex表示，#F代表特征数，#Minority代表少数类样本数，#R代表少数类样本占数据集的比重。采用决策树C4.5算法以及AdaBoost.M1算法进行对照，Adaboost.M1迭代时用 C4.5 作为基分类器，迭代 20次，此外还对数据采用十交叉验证。其中，C4.5决策树算法直接对不平衡数据集进行分类，基分类器算法使用C4.5算法，利用weka平台中J48分类器实现。

3.2 评估指标

采用查全率、查准率和F-measure作为评价分类器性能的指标，其在机器学习、数据挖掘等领域应用广泛，能被广大学者接受。传统的二分类评价指标基于混淆矩阵，在不平衡数据集中正类和反类分别代表少数类和多数类。TP和 TN分別表示正确分类的正类和反类样本个数；FP表示误分为正类的样本个数；FN表示误分为负类的样本个数，见表2。

3.3 实验结果分析

在不平衡数据集中，多数类样本个数远远多于少数类，传统分类算法预测会倾向于多数类，如把所有样本分为多数类，依然会获得很高的分类精度，但是却不能识别一个少数类。因此在处理不平衡数据时，提高少数类样本在训练样本中所占比重，能够有效提高少数类样本的分类性能。从表3及图2可以看出，不平衡数据经过处理后，每个数据集训练样本中少数类样本的比例明显提高。

从表4和表5可以看出，AdaBoos.M1算法在Segment、Vehicle数据集上的查准率偏低，而C4.5算法在Segment、Sick数据集上有较高的查准率和查全率。同AdaBoost.M1和C4.5算法相比较，本文算法在Balance-scale 、Satimage以及Yeast 数据集上的查准率具有显著优势。在这几个数据集上，本文算法显著优于AdaBoost.M1算法，在Segment 、Sick数据集上与C4.5算法水平相当。

表6是几种不同方法在不平衡数据分类性能中评估指标F-measure的分类结果比较。只有当查全率和查准率都较大时，F-measure才会相应地较大。因此，F-measure可以合理地评价分类器对于少数类的分类性能。本文提出采用基于综合权重采样和集成学习相结合的方法处理不平衡数据的分类问题，相较于其它两种方法，分类性能得到大幅度提升。比如在数据集Satimage、Sick以及Yeast中比其它两种算法提高了10%以上。

文献[15]提出处理不平衡数据的PCBoost算法在每次迭代初始，利用数据合成方法添加合成的少数类样本达到平衡。其在数据集Satimage、Segment以及Vehicle中，与本文算法在F-measure方面的比较见图3。从图3可以看出，本文算法在数据集Satimage中明显高于PCBoost算法，但是在数据集Vehicle明显低于PCBoost算法，而在数据集Segment中两种方法水平相当。对于每一个数据集，PCBoost算法在实验中选取不同的迭代次数以获得最佳预测性能的分类器，使其在某些数据集上比本文算法取得更为明显的效果。

5 结语

为了保持原始数据的分布特点，更好地利用潜在有用的分类信息，保证集成学习中各分类器之间的差异性，本文采用基于综合权重采样与集成学习相结合的方法处理不平衡数据分类问题。通过UCI数据集实验，以查全率、查准率和F-measure为度量对算法进行评价，与决策树算法、AdaBoost.M1算法以及PCBoost算法进行比较，实验结果表明本文方法不仅能够提高少数类样本的分类性能，而且能够有效提高整体分类精度。

在不平衡数据处理阶段，本文随机选择特征构成特征子集，并没有考虑到每个特征对类的贡献程度以及特征与特征之间对类的贡献程度；另外还未考虑分类效率问题。因此，将来需考虑对特征的选择以及提高分类效率，以进一步提高该方法的泛化性能。

参考文献：

[1] KIM H，HOWLAND P，PARK H.Dimension reduction in text classification with support vector machine[J].Journal of Machine Learning Research，2005，6（1）：37-53.

[2] 邹权，郭茂祖，刘扬，等.类别不平衡的分类方法及在生物信息学中的应用[J].计算机研究与发展，2010，47（8）：1407-1414.

[3] 陆悠，李伟，罗军舟，等.一种基于选择性协同学习的网络用户异常行为检测方法[J].计算机学报，2014，37（1）：28-40.

[4] CHAWLA N V，JAPKOWICA N，KOTCZ A.Editorial：special issue on learning from imbalanced data sets[J].ACM SIGKDD Explorations Newslettter，2004，6（1）：1-6.

[5] HE H B，EDWARDO A G.Learning from imbalanced data[J].IEEE Transactions on Knowledge and Data Engineering，2009，21（9）：1263-1284.

[6] 陶新民，郝思媛，张冬雪，等.不均衡数据分类算法的综述[J].重庆邮电大学学报：自然科学版，2013，25（1）：102-110.

[7] CEDER A，HASSOLD S，DANO R.Approaching even-load and even-head way transit timetables using different bus sizes[J].Public Transport，2013，5（3）：193-217.

[8] 林智勇，郝志峰，杨晓伟.不平衡数据分类的研究现状[J].计算机应用研究，2008，25（2）：332-336.

[9] 钱洪波，贺广南.非平衡类数据分类概述[J].计算机工程与科学，2010，32（5）：85-88.

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

[11] 李克文，杨磊，刘文英，等.基于RSBoost算法的不平衡数据分类方法[J].计算机科学，2015，42（9）：249-252.

[12] CHEN B，SU Y D，HUANG S.Classification of imbalance data based on KM-SMOTE algorithm and random forest[J].Computer Technology And Development，2015，9（25）：17-21.

[13] SEIFFERTC，KHOSHOFTAARTM，VAN H，et al.RUBoost：a hybrida approach total levitating classing balance[J].IEEE Tran on Systems，Man and Cybernetics，PartA：Systems and Humans，2010，40（1）：185-197.

[14] GALAR M，FERNNDEZ A，BARRENCHEA E，et al.EUSBoost：enchancing ensembles for highly imbalanced data-sets by evolutionary under sampling[J].Pattern Recognition，2013，46（12）：3460-3471.

[15] 李雄飛，李军，董元方，等.一种新的不平衡数据学习算法PCBoost[J].计算机学报，2012，35（2）：2202-2209.

[16] LIN S Y，LI C H，JIANG Y，et al.Under-sampling method research in class-imbalanced data[J].Journal of Computer Research and Development，2011，48（2）：47-53.

[17] HAN H，WANG W Y，MAO B H.Over-sampling algorithm based on AdaBoost in unbalanced data set[J].Computer Engineering，2007，10（33）：207-209.

[18] 李倩倩，刘胥影.多类类别不平衡学习算法：EasyEnsemble.M [J].模式识别与人工智能，2014（2）：187-192.

[19] 胡小生，温菊屏，钟勇.动态平衡采样的不平衡数据集成分类方法[J].智能系统学报，2016，11（2）：257-263.

[20] 刘胥影，吴建鑫，周志华.一种基于级联模型的类别不平衡数据分类方法[J].南京大学学报：自然科学版，2006，42（2）：148-155.

[21] FU Z L.Real AdaBoost algorithm for multiclass and imbalanced classification problems[J].Journal of Computer Research and Development，2011，48（12）：2326-2333.

[22] 凌晓峰，SHENG V S.代价敏感分类器的比较研究[J].计算机学报，2007，30（8）：1203-1212.

[23] WANG C X，ZHANG T，MA C.Improved SVM-KNN algorithm for imbalanced datasets classification[J].Computer Engineering and Applications，2016，52（4）：51-55.

[24] 马彪，周瑜，贺建军.面向大规模类不平衡数据的变分高斯过程分类算法[J].大连理工大学学报，2016，56（3）：279-284.

（责任编辑：何 丽）