面向不平衡数据集分类模型的优化研究

,,

(1.东北林业大学 信息与计算机工程学院,哈尔滨 150040; 2.国家林业局 哈尔滨林业机械研究所,哈尔滨 150086)

0 概述

在这个信息大爆炸的时代,为了从海量数据中挖掘出有效信息[1],许多实际应用的数据集需要进行分类处理,如防火墙过滤、入侵检测[2]和缺陷预测[3]等。但多数情况下,这些数据集是不平衡的,表现出来的现象是,数据集中各个样本之间的数量差距悬殊。在机器学习过程中,一般将数据集中关于类别分布的不均衡问题称为数据集的不均衡问题(Class Imbalance Problem of Data Set,CIPD),体现在样本的数量差异较大。采用传统分类方法解决CIPD时,分类结果往往倾向于多数类。对CIPD学习效果进行改善,提高CIPD的分类准确率是当前机器学习算法领域的热点之一[4-6]。

支持向量机以其效果稳定、精确度高的优点得到了广泛应用。但是在利用支持向量机(Support Vector Machine,SVM)对不均衡数据集分类时效果都不够理想,原因是SVM算法学习得到的超平面倾向于少数类样本,导致分类器性能较差。

过采样通过生成少类样本来减少数据的不均衡性。文献[7]提出SMOTE算法,该算法通过随机合成而不是复制少类样本的方式有效解决了过拟合的现象,但是由于没有对少类样本进行区域划分,致使合成的样本分布区域存在局限性。

针对SMOTE算法的不足,文献[8]提出了B-SMOTE算法,用SMOTE算法对决策边界的少数类样本进行人工合成。文献[9]提出了对错分样本进行循环采样人工合成新样本的方法(L-SMOTE)。虽然这些方法有效地提升了SMOTE算法的性能,但是仍然存在一些不足。如B-SMOTE算法在执行过程中,忽略了决策边界外的少类样本中的重要信息;L-SMOTE算法在执行过程中,忽视了错分样本中的噪声点,不断合成新的噪声样本,影响了分类精确度。

文献[10]通过精确选择参数ε值提高了ε-SVM在均衡与不均衡数据集上的分类精度。文献[11]引入双隶属度的非对称加权算法对混合核SVM的核函数进行优化,并将其应用到不平衡数据集分类中。以上2种方法有效改善了分类算法对不平衡数据集的分类效果,但是到目前为止,对于混合核ε-SVM的优化方法只涉及到预测方面,而关于混合核ε-SVM对不平衡数据集分类方面的优化方法还没有提出过。

针对以上不足,本文提出一种从样本采样和分类算法两方面同时优化的分类模型。在样本采集方面,给出一种面向决策边界少类样本循环过采样的LD-SMOTE算法,并将新生成的样本集与决策边界外新生成的少类样本进行合并。在分类算法方面,将正负惩罚系数引入到混合核ε-SVM中,并将更具有客观性的熵值法运用到惩罚系数的选择上。

1 基于决策边界的L-SMOTE优化方法

1.1 L-SMOTE算法

和传统的SMOTE算法不同,L-SMOTE算法关注的是影响分类平面的错分样本,根据错分样本循环合成新样本,提升这些关键样本的质量,提高分类的精确度。

但是该算法在执行时存在一定的缺陷,如图1所示,P3、P4和P5是少数类样本,P1和P2是新生成的样本,P2是较为合理的合成样本,但是P1的有效性却是值得商榷的,因为P1生成的位置正好位于多数类的散列点中间,属于噪声点,根据L-SMOTE算法,P1点是错分样本点,采取错分样本的重采样,那么生成的新样本也必然是噪声点,循环执行将会严重影响分类效果。

图1 合成样本的有效性

1.2 D-SMOTE算法

因为错分类样本主要集中在决策边界,只对决策边界的少类样本进行循环重采样就会有效避免噪声点的不断生成。针对决策边界少类样本的人工合成,本文提出一种基于样本间距的决策边界过采样算法(D-SMOTE)。

该算法的具体步骤如下:

步骤4对各个决策样本计算在少数类样本集中的k近邻,从中任取一个aj,利用aj和ai两个样本,结合SMOTE算法合成新的样本。公式如下:

anew=ai+random(0,1)×|ai-aj|

(1)

在对决策边界的少类样本进行人工合成时,本文用D-SMOTE算法取代传统的B-SMOTE算法,因为B-SMOTE算法在处理少数类样本极少的样本集时,往往会造成合成的新样本分布不均、过于集中的现象,而D-SMOTE通过比对数类和多数类样本的间距来确定决策边界样本,有效地控制了决策样本的分布范围,样本分布更均匀,提升了决策边界样本集的质量。

1.3 LD-SMOTE算法

将本文提出的D-SMOTE算法与L-SMOTE算法相结合,得到LD-SMOTE算法。该算法的具体操作步骤如下:

步骤1用D-SMOTE算法选出少数类样本的决策样本集合,记为Pd。

步骤2用标准SMOTE算法对少数类样本进行人工合成,合成后的新样本集合记作Pl。

步骤3用标准SMOTE算法对Pd中的样本进行人工合成,生成新的样本集合,记为Pe。

步骤4令Pd=Pe,Pld=Pd+Pl,重复步骤3,直到Pld=nN。

Pld就是LD-SMOTE算法执行后最终得到的少数类样本集,与B-SMOTE算法合成的样本集不同,该样本集包含了非决策边界的少数类样本的重要信息,而且通过循环合成让决策边界的少数类样本能够反复学习,从而提高了最终合成的少数类样本集的质量。

该算法的伪码如下:

输入样本集T,少数类样本集P,多数类样本集N,少数类样本数量nP,多数类样本数量nN

输出最终生成的少数类样本集:Pld

1. Pd= D-SMOTE(P)

2. Pl= SMOTE(P)

3. Pe= SMOTE(Pd)

4. Pd=Pe,Pld= Pd+ Pl

5. While Pld!= nN

6. Pe= SMOTE(Pd)

7. Pd=Pe,Pld= Pd+ Pl

8. Endwhile

2 基于熵值法的混合核ε-SVM优化方法

2.1 ε-SVM

SVM分为线性可分、非线性可分以及需要核函数映射3种情况。设训练样本T={(xi,yi)}(i=1,2,…,l),xi为SVM的输入特征,yi为类别标签,l为训练样本个数。基于二分类目标核函数SVM实现非线性划分的分类算法,其模型的原始问题可表示为:

s.t.yi((w·φ(xi))+b)≥1-ξi,i=1,2,…,

ξi≥0,i=1,2,…,l

(2)

其中,w是一个被确定的权重向量,C和ζi分别为惩罚系数和松弛变量。

L(y,f(x,a))=L(|y-f(x,a)|ε)

(3)

f(xi)=ω·φ(xi)+b

(4)

其中,ω为回归系数,φ(xi)为输入空间到特征空间的映射函数,b为阈值。

2.2 混合核函数

混合核函数是指通过组合的方式将单个核函数合并成新的核函数,同时考虑局部核函数和全局核函数的特性,将两者的优势充分发挥,弥补两者在应用上的不足。由于Polynomial核函数有着良好的全局性质,而RBF核函数则是局部性强,本文将这2种核函数组合起来,得到学习能力和推广性都很强的混合核函数,其构造形式如下:

kPoly=[(x×xi)+1]q

(5)

kRBF=exp(-‖x-xi‖2/σ2)

(6)

k(x,x′)=λkPoly(x,x′)+(1-λ)kRBF(x,x′)

(7)

(8)

式(5)和式(6)分别表示Polynomial核函数和RBF核函数。式(7)表示构造的混合核函数,其中的λ表示的是单个核函数在混合核函数中占有的比重,0<λ<1。式(8)表示的是Mercer核函数约束条件。将k(x,x′)带入到式(8)中,符合Mercer核函数约束条件[14-15]。文献[14]已对k(x,x′)的线性组合进行验证,满足Mercer条件,这里不作具体论证。

将混合核函数植入到传统的ε-SVM,构造成混合核ε-SVM,分类算法具有了更强大的学习能力和泛化能力。

2.3 混合核ε-SVM的优化

通过LD-SMOTE算法生成新样本能够使样本数据集变得均衡,但是扩充样本集合时,并不能改变原有样本分布的外围轮廓特征,这就意味着对分类问题中分类边界的影响比较小,所以利用混合核ε-SVM训练样本时超平面依然会偏向少数类,分类效果依然会受到影响。受文献[16]的启发,在样本训练过程中,将正负惩罚系数C+和C-引入到混合核ε-SVM中,并在正负惩罚系数的选择上运用了熵值法进行优化。

1)正负惩罚系数

二分类平面图如图2所示。圆和星分别表示多数类样本和少数类本,虚线表示的是使用一个惩罚系数时的分割效果。在这种情况下,如果对2类样本赋予不同的惩罚系数C+和C-,灵活地调节误差代价,最终就会得到理想的分类效果,图中的实线表示调整正负惩罚系数后的分割效果。

图2 二分类平面图

通过以上分析,结合式(2)～式(4)、式(7),最终推导出改进的混合核ε-SVM的约束化问题:

i=1,2,…,l

(9)

其中,ζi和ζi*为松弛因子,C+和C-表示少类样本(正类)和多类样本(负类)的惩罚系数。

在惩罚系数C+和C-的选择上,传统方法都没有考虑到样本内各个属性的相对变化程度,使得惩罚系数在选择上过分依赖个人经验,具有很强的主观性。

2)熵值法确定正负惩罚系数

本文将信息熵的思想用于到惩罚系数的选择上,提出熵值法[17]确定惩罚系数的方法。根据多数类和少数类样本的离散程度确定不同的惩罚系数,避开主观人为因素的干扰,即一种客观的赋值方法,选出的惩罚系数更具有价值,其具体实现方法如下:

(10)

同理,负类样本S-包含m个子类,负类样本S-的熵值为:

(11)

计算正类样本S+和负类样本S-的差异性系数,将式(10)、式(11)代入得:

(12)

(13)

其中,d+、d-分别表示正类和负类的差异性系数。令C+=C,得:

(14)

通过以上优化方法,使得分类算法在对不平衡数据集分类时的性能进一步提高。在参数的选择上,本文利用文献[18]提出的AMPSO算法进行参数寻优。将优化后的混合核ε-SVM算法和LD-SMOTE算法相结合,最终得出本文的分类模型,如图3所示。

图3 本文的分类模型

本文的分类模型伪码如下:

输入训练样本集中的多数类样本D1,训练样本集中的少数类样本D2,测试数据集D3

输出D3数据集的分类结果

1.计算LD-SMOTE决策边界样本语料库

2.计算SMOTE非决策边界样本语料库

3.DNEW = LD-SMOTE + SMOTE

4. 使用式(11)～式(16)训练模型ε-SVM参数

5.result =[]

6.for i in range(0,len(D3))

7. result_D3 =ε-SVM(D3[i])

8. result.append(result_D3)

9.end for

10.return result

3 实验设置与结果分析

3.1 数据来源

为了验证本文提出的分类模型的分类效果,采用UCI数据集[19]中的6个不平衡数据集作为测试性能的数据,各个数据集的信息如表1所示,其中的比例表示的是少数类与多数类的比值。

表1 不平衡数据集

3.2 分析指标

在对不平衡数据集进行分类时,常用的分析指标有3种,分别是查准率(Precision)p、敏感度(Sensitivity)s和综合考虑F-measure指标f,具体公式如下:

(15)

(16)

(17)

其中,FP表示将负类样本错分成正类的数目,FN是指将正类样本错分成负类的数目,TP表示正类样本被正确分类的个数。

3.3 实验结果分析

将数据的70%作为样本的训练集,30%作为样本的测试集。利用word2vec对样本进行词向量的训练,生成向量空间。实验中所有的数据集都采用了5折交叉验证,以便于验证分类模型的性能。

1)近邻值参数k值的确定

k值的选择对于本文提出的LD-SMOTE算法至关重要,将k值范围设置在2～10之间进行讨论。实验数据采用UCI不平衡数据集中30%的测试数据,对6个数据集分别进行测试,将不同k值下的F-measure值作为评价指标,F-measure取6个数据集的平均值。用本文提出的改进混合核ε-SVM作为分类算法,图4表示的是在本文分类算法下,不同k值取得F-measure值的折线图。当k值到6时,F-measure达到最高值,因此在接下来的实验中,将LD-SMOTE算法的k值设定为6。

图4 不同k值下的实验结果

2)3种分类算法的实验结果对比

实验采用abalone作为测试数据集,该数据集是一个极度不均衡的数据集。该实验用本文提出的LD-SMOTE算法进行样本过采样处理,然后用改进的混合核ε-SVM算法、改进的单核ε-SVM算法(采用RBF核函数,运用熵值法确定正负惩罚系数)和传统的ε-SVM算法(采用RBF核函数)进行学习和最终的预测,利用文献[18]提出的AMPSO算法对3种分类算法进行参数优化,下面的实验均用该方法进行参数优化。实验采用查准率、敏感度和F-measure值作为评估标准。利用AMPSO算法寻找出最优参数组合如表2所示,实验结果如图5所示。

表2 参数寻优结果

图5 3种分类算法的实验结果

如图5所示,本文提出的改进混合核ε-SVM的3个评估指标比其他2种分类算法明显提高。因为采用了熵值法确定正负惩罚系数,所以在处理极度不均衡数据集时,2种改进算法的分类精度要比传统ε-SVM算法有所提高。而混合核比单核分类精确度高是因为混合核函数具有更强的泛化能力和鲁棒性。

3)传统SMOTE算法和LD-SMOTE算法的分类结果对比

实验采用6个不平衡数据集作为测试数据集,分类算法均采用标准SVM,F-measure值作为评估标准,实验结果如图6所示。

图6 2种采样算法的实验结果

实验结果表明,LD-SMOTE+SVM的分类精确度比SMOTE+SVM算法有明显提升。但是当样本集极度不均衡时(abalone数据集),只对训练样本进行重采样处理,不对分类算法进行改进,分类精确度明显偏低。

4)3种分类方法实验结果对比

为了更好地验证本文提出的分类模型的性能,在相同实验条件下,与标准的SVM[20]和SD-ISMOTE+SVM[21]进行实验比较。实验选用F-measure指作为评价标准。实验结果如表3和图7所示。

表3 3种分类方法的F-measure值对比 %

图7 3种分类方法的实验结果

表3显示了3个算法对6个数据集进行分类预测的实验结果。实验结果表明,本文提出的分类模型比SD-ISMOTE+SVM和标准SVM在F-measure值上取得了明显提升。F-measure值比标准SVM平均高出18.1%,比SD-ISMOTE+SVM平均高出4.35%,说明本文提出的分类模型在对不平衡数据集进行分类时具有明显优势。

在图7中,标准SVM算法的折线始终在图像的最下方,尤其是在car和abalone两个数据点上,其F-measure值达到了最低。产生的原因是,标准SVM算法没有对训练样本做任何处理,尤其是当数据集的正负类样本数量差距悬殊,分类平面严重向另一侧倾斜时,如果直接采用SVM算法对测试样本进行分类,分类的精确度会大大降低。而本文的分类模型和SD-ISMOTE+SVM都针对不平衡的训练样本集进行过采样处理,都获得了较好的分类效果。但是本文的分类模型的分类精确度更高一些,原因在于在分类算法的改进上,将正负惩罚系数、熵值法和多核学习引入到支持向量机中,进一步提高了分类模型的分类性能。

4 结束语

本文构建一种面向不平衡数据集的分类模型。在样本集过采样优化方面,针对L-SMOTE算法对错分样本进行循环采样时不断生成噪声点的问题,通过对决策边界样本进行循环过采样的方法生成新的样本集,并将第一次过采样时生成的决策边界范围外的少类样本添加到新生成的样本集中,提升了样本的重要度。在算法优化方面,针对传统的ε-SVM算法在对不平衡数据集分类时超平面偏移的问题,把正负惩罚系数引入到支持向量机模型中,并且采用了更具有客观性的熵值法选取惩罚系数。同时构造了混合核ε-SVM,加强了支持向量机的泛化能力和学习能力,分类精确度明显提高。下一步将改进粒子群算法,选出最优参数,并减少算法运行消耗的时间。

[1] GARCA S,LUENGO J,HERRERA F.Data preprocessing in data mining[M].Berlin,Germany:Springer,2016.

[2] 沈夏炯,王 龙,韩道军.人工蜂群优化的BP神经网络在入侵检测中的应用[J].计算机工程,2016,42(2):190-194.

[3] YU Qiao,JIANG Shujuan,ZHANG Yanmei.The performance stability of defect prediction models with class imbalance:an empirical study[J].IEICE Transactions on Information & Systems,2017,100(2):265-272.

[4] ZHANG Chunkai,WANG Guoquan,ZHOU Ying,et al.A new approach for imbalanced data classification based on minimize loss learning[C]//Proceedings of the 2nd International Conference on Data Science in Cyberspace.Washington D.C.,USA:IEEE Press,2017:82-87.

[5] NAPIERALA K,STEFANOWSKI J.Types of minority class examples and their influence on learning classifiers from imbalanced Data[J].Journal of Intelligent Information Systems,2016,46(3):563-597.

[6] HERRERA F.Cost-sensitive linguistic fuzzy rule based classification systems under the MapReduce framework for imbalanced Big Data[J].Fuzzy Sets & Systems,2015,258(3):5-38.

[7] 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.

[8] HAN Hui,WANG Wenyuan,MAO Binghuan.Borderline-SMOTE:a new over-sampling method in imbalanced data sets learning[C]//Proceedings of International Conference on intelligent Computing.Berlin,Germany:Springer,2005:878-887.

[9] 衣柏衡,朱建军,李 杰.基于改进SMOTE的小额贷款公司客户信用风险非均衡SVM分类[J].中国管理科学,2016,24(3):24-30.

[10] 杨俊燕,张优云,朱永生.ε不敏感损失函数支持向量机分类性能研究[J].西安交通大学学报,2007,41(11):1315-1320.

[11] 赵淑娟.基于非对称加权和核方法的不平衡数据集[D].南京:南京邮电大学,2013.

[12] ALZATE C,SUYKENS J.Kernel component analysis using an epsilon-insensitive robust loss function[J].IEEE Transactions on Neural Networks,2008,19(9):1583-1598.

[13] WATANABE K.Vector quantization based on ε-insensitive mixture models[J].Neurocomputing,2015,165(3):32-37.

[14] 唐 奇,王红瑞,许新宜,等.基于混合核函数SVM水文时序模型及其应用[J].系统工程理论与实践,2014,34(2):521-529.

[15] 颜根廷,马广富,肖余之.一种混合核函数支持向量机算法[J].哈尔滨工业大学学报,2007,39(11):1704-1706.

[16] 刘东启,陈志坚,徐 银,等.面向不平衡数据分类的复合SVM算法研究[EB/OL].[2017-11-06].http://kns.cnki.net/kcms/detail/51.1196.TP.20170401.1738.050.html.

[17] 朱喜安,魏国栋.熵值法中无量纲化方法优良标准的探讨[J].统计与决策,2015(2):12-15.

[18] FRANK A,ASUNCION A.UCI machine learning repository[EB/OL].[2017-11-06].http://archive.ics.uci.edu/ml.

[19] 刘文贞,陈红岩,李孝禄,等.基于自适应变异粒子群算法的混合核ε-SVM在混合气体定量分析中的应用[J].传感技术学报,2016,29(9):1464-1470.

[20] 常甜甜.支持向量机学习算法若干问题的研究[D].西安:西安电子科技大学,2010.

[21] 古 平,杨 炀.面向不均衡数据集中少数类细分的过采样算法[J].计算机工程,2017,43(2):241-247.