基于邻域检测与反馈的混合重采样进化挖掘方法

潘笑天,王丽萍,邱启仓,张梦辉

1(浙江工业大学 计算机科学与技术学院,杭州 310023) 2(之江实验室,杭州 311100)

1 引 言

在现实生活中,数据不平衡问题十分常见,如故障诊断[1]、医疗诊断[2]和金融诈骗[3]等,异常事故,罕见病例及异常行为通常少于正常情况,而对少数类事件的准确识别意义更为重大.由于传统机器学习算法是建立在类分布相对均衡的样本学习基础上的,因此将其直接迁移到非均衡数据学习环境,其分类结果常常将少数类样本识别为多数类样本,导致在多数类上精度较高,而在少数类上精度较低[4].并且由于少数类数据的稀疏性和离散性,也会导致整个样本的分布偏态,进一步降低分类器对少数类样本的判别能力[5].因此,解决数据不平衡问题通常是提高分类器泛化性能的关键,目前不平衡处理技术主要分为两大类:

1)数据级方法:在数据空间利用过采样或欠采样方法来平衡数据量.如随机过采样简单的复制少数类样本[6];或随机欠采样利用集成学习机制[7],将多数类随机划分为若干个集合供不同学习器使用,然而随机技术并未达到理想的分类效果.

2)算法级方法:包括(1)修改传统分类算法的分类规则,如调整支持向量机的惩罚因子,以适应数据分布不均衡分类问题;(2)代价敏感方法:为少数(多数)类指定一个较大(较小)的误分类代价,并通过最小化总误分类代价来训练分类器[8];与数据级方法相比,算法级方法需要根据样本分布特征修改其学习机制,需要对所使用的算法及应用领域有专门的知识.因此,本文主要面向数据级方法,并结合模型性能反馈研究不平衡数据处理技术.

近年来研究发现,数据不平衡并不是导致分类性能下降的直接原因,因此,单纯地增加或减少样本数量并不能解决分类器性能下降的问题.而导致分类性能退化的主要原因[9,10]是类别不平衡和正例的稀缺性导致数据在样本空间的复杂分布,这些复杂分布包括小间断(少数类分解成多个子集群)、类间重叠、罕见和异常值等[11].这是因为现有分类算法大多是根据训练样本的分布来生成分类边界或决策规则,因此很难对复杂分布的样本进行学习和分类.

在数据级方法研究中,以SMOTE[12]合成少数类技术最具代表性,通过探测数据的分布特征,并有目的地生成新样本来解决上述问题,在平衡数据分布上效果明显,但是也会出现数据重叠和过度泛化等问题.因此,在SMOTE基础上,改进过采样方法通过划分样本属性并指导样本的生成,如Borderline-SMOTE[13]、Safe-Level SMOTE[14]、DB-SMOTE[15]、radius-SMOTE[16]等在样本的生成方向上进行改进,加强局部少数类样本的生成,但是新生成的样本可能会改变原始样本分布特征,造成分类误差.近年来,混合重采样方法(Hybrid sampling methods)在SMOTE生成新样本后,采用数据清洗方法调整样本的局部分布,如SMOTE-ENN[17],SMOTE-IPF[9],SMOTE-WENN[18]等,这种事后修补技术通常表现出更好的分类结果.但是目前混合重采样方法主要采用距离估算和位置分布估计,预见性地对可能造成误分类的样本进行删减.并且由于样本清洗过程独立于分类器训练过程,被删减的样本对分类结果的实际影响无法估计,易造成过度删除或不合理删减等问题.为解决上述问题,研究在混合重采样的基础上,结合分类器评估结果对样本组合进行优化选择,提出了基于邻域检测与反馈的混合重采样进化挖掘方法(APMMOEA-EC).该方法首先通过SMOTE方法合成新的少数类样本;然后通过邻域检测对样本属性进行划分,根据K近邻中异类样本个数,将样本划分为安全区域样本和异构区域样本;并设计了基于自适应模式挖掘的多目标进化算法(APMMOEA)对异构区域样本进行组合优化.在7种具有不同复杂分布属性的数据集上,通过参数对比实验选择最佳容忍值t,并与5种流行的优化算法进行对比实验,分析APMMOEA算法的性能表现,最后与5种不平衡处理方法在3种不同学习规则的分类器上,验证APMMOEA-EC方法的有效性和优越性.本文主要贡献如下:

1)利用模型训练过程的信息反馈指导样本的清洗过程,通过迭代优化对样本清洗结果进行评估并及时修正,其样本清洗规则实质上是由分类器的学习机制决定的,这改变了传统混合重采样方法利用先验知识删减样本,被删减样本的价值及其对分类器的影响无法评估等问题.

2)设计了邻域检测方法,通过K近邻计算获得样本的邻域样本信息,将邻域内异类样本个数大于容忍值的样本视为待优化样本,其余为安全样本,安全样本无需优化,从而实现对样本优化空间的降维,有利于降低优化难度.

3)在优化算法设计上,提出自适应搜索行为切换方法,结合NSGA-Ⅱ的优势度排序方法对目标空间进行全局优化,并对满足收敛条件的非支配解,自适应转换为进化模式挖掘阶段,对决策变量进行局部优化,由此进一步提高解集质量,获得优化后的样本组合方案.

2 相关工作

2.1 现有不平衡数据处理方法综述

SMOTE是最具代表性的过采样方法,在不损失原有样本信息的基础上,在少数类周围生成一些新样本从而提高样本的平衡度,使分类算法能够捕捉到更多少数类样本分布特征,其算法流程如下:

1)对于少数类中每一个样本x,用欧式距离计算它到少数类样本集Smin中所有样本的距离,得到其K近邻;

2)根据样本不平衡比例设置一个采样倍率N,对于每一个少数类样本x,从其K近邻中随机选择若干个样本,设为u;

3)对于每一个随机选择的样本u,按照下列公式与原样本x构建新的样本xnew:

xnew=x+rand(0,1)×|x-u|

(1)

由于SMOTE使用线性插值方法合成新的少数类样本,因此可能会引入新的噪声样本,如图1所示,新生成的少数类样本(用实心五角星表示)位于多类样本的安全区域,这也是SMOTE算法造成分类算法过度泛化的主要原因.

图1 SMOTE生成新样本及过度泛化问题Fig.1 New samples generated by SMOTE and overgeneralization

实际上,所有的过采样技术都可能会生成分布不合理的新样本,解决这类问题,现有方法是有目的地增加或删减部分个体来改变样本局部分布,分为以下三方面研究:

1)欠采样技术:NBComm[19]旨在消除重叠区域的多类样本,从而提高少类样本的可见性;

2)改进过采样技术:Borderline-SMOTE[13]根据少类样本K近邻的类别数量,来划分少类样本的位置属性(危险、安全、噪声样本),通过在决策边界(即危险样本)周围生成少类样本降低样本不平衡度.Safe-level SMOTE[14]主张在安全区域增加少类样本来减低不平衡度.诸如此类方法的DBSMOTE[15]、radius SMOTE[16]分别采用密度和半径距离指导样本的生成方向,改变样本的局部分布不平衡度.上述方法是在样本产生时改变少类样本的局部分布,但也可能存在两个问题:(1)在边界重叠区域引入新样本增加决策边界的分类难度;(2)强调在安全区域生成样本,并不能解决间断、重叠等区域数据难分类问题.

3)混合重采样方法:如SMOTE-IPF[9]通过训练多个决策树对“有争议”的样本进行删减,即全数或者超过半数决策树不能准确预测的样本,但是该方法依赖决策树的训练效果;Tomerlink寻找不同类别中互为最近邻的个体,并删除其中的多数类样本,这种方式实际上是压缩了多类样本空间;SMOTE-ENN[17]使用编辑的最近邻规则,但可能会删除低密度区域的少数类样本,压缩少类样本空间;SMOTE-WENN[18]使用加权编辑最近邻规则,对正负样本采用了不同尺度距离计算方法,增加少数类样本的局部密度,尽可能的保留重叠区域的少数类样本.

上述方法仍存在的问题:1)在重叠区域偏向于压缩某一类样本分布,或者将稀疏分布样本或异常点视为“易误分类样本”进行删减,然而在稀疏区域和重叠区域移除少数类样本会加重样本分布不均,少数类样本分布特征更难被分类器捕捉,可能会过度消除;2)在分类之前对数据进行清洗,其删减样本的价值及对分类的影响均无法得到评估,在小规模样本中,异常值或稀有样本的数量可能占比不低,这些例子有可能是典型的、罕见的、分散的少数群体,因此不能简单地剔除;3)对于不同的分类算法,其对样本分布的学习机制不同,清洗规则也应该做出改变,然而现有的混合重采样方法并不能自适应改变清洗规则,并且对于不合理删减行为无法获得及时反馈和修正.

2.2 基于非支配排序的多目标优化算法

Deb于2002年[20]提出了经典的带有精英保留策略的快速非支配排序多目标优化算法(NSGA-II),通过定义Pareto支配排序准则和拥挤距离比较算子实现对目标空间中解集的优势度排序,相关定义如下:

定义1.(Pareto支配):对于一组决策向量X1,X2,当且仅当∀m∈{1,2,…,M},fm(X1)≤fm(X2)时,称X1Pareto支配X2,m为优化目标,M为目标总数(下同).

定义2.(非支配等级):个体i的非支配等级Ri=|J|+1,其中,J∈1,2,…,N,iJ,N为个体总数(下同),即Ri计算为支配i的解集J的个数.

定义3.(Pareto非支配解):对于一组解i=1,2,…,N中,若Xi不被其他任何解支配时,称Xi为Pareto非支配解.

2.3 进化模式挖掘方法

Tian等人[21]2020年提出了基于模式挖掘的大规模稀疏多目标进化算法(PMMOEA),引入频繁模式挖掘方法探索Pareto非支配解的稀疏分布规律,该方法非常适用于本文样本的组合优化过程.原因包括:该方法考虑通过变量的稀疏性来降低决策空间的搜索难度,并且稀疏性降低了样本选择个数,防止训练过拟合;此外,通过模式挖掘有助于发现最优样本组合的频繁模式,而在此基础上对决策变量进行局部优化,有利于进一步提高解集质量.在PMMOEA中,将全零变量,最大、最小非零候选集定义如下:

定义5.(全零变量):当前种群中所有非支配解中全为0的变量.

定义6.(最小非零候选集):当前种群中所有非支配解中全为1的变量,则最小非零候选集需满足的目标定义如下:

(2)

其中,x是挖掘的最大候选集,ND为当前种群中非支配解集,Px表示ND中非零变量是x中非零变量子集的集合;|·|表示集合数目;p为Px中的集合,∑p为变量之和,等于非零变量个数;∑x为最大候选集中变量之和.

定义7.(最大非零候选集):至少在几个非支配解中是非零的变量,则最大非零候选集需满足的目标定义如下:

(3)

其中,y是挖掘的最小候选集,ND和|·|同公式(2),Py表示ND中非零变量是y中非零变量超集的集合;p为Py中的集合,∑p为变量之和,等于非零变量个数;∑y为最小候选集中变量之和.

在PMMOEA中,挖掘上述集合的步骤如下:

步骤1.从当前种群中选出非支配种群ND,找到所有非支配解中含有零变量的项确定为全零变量,对含有非零变量的项确定为非零候选集;

步骤2.初始化最大非零候选集,从当前非支配解的非零向量中随机选择N′个超集;初始化最小非零候选集,从当前非支配解的非零向量中随机选择N′个子集;

步骤3.采用多目标优化方法根据公式(2)和公式(3)评估当前和上一代解集候选集,并迭代优化选择当代最优候选集;

步骤4.输出当前最优的N′个最大、最小候选集,以及非零变量集.

2.4 研究动机

根据2.1节对现有不平衡处理方法的缺陷分析,本文研究通过多目标优化过程,结合分类器性能反馈指导混合重采样的清洗过程;但是随着数据集中样本个数的增加,样本组合优化问题规模也随之增加,巨大的搜索空间增加了算法求解难度[22],因此需要对优化空间进行降维;NSGA-II虽然具有良好的全局搜索能力,但其强调个体在目标空间的表现,缺乏对决策空间的优化.PMMOEA强调对决策变量的频繁模式挖掘,有利于发现最优解的变量特征,但是该算法采用每代对非支配解进化挖掘的方法,其计算复杂度较高,为O(g×N′×D2),其中,g是模式挖掘迭代次数,N′是挖掘种群大小,D为决策变量大小;并且在算法早期获得的非支配解不一定具有最优解的变量特征,因此不一定能够引导高质量后代解的生成.为解决上述问题,本文首先定义了多目标混合重采样优化问题,并确定了优化目标;然后通过邻域检测划分样本属性,对优化样本空间进行降维;在算法设计上,提出了自适应搜索行为转换方法,当满足预设条件时调整全局和局部两种搜索行为,根据模型性能反馈指导样本的选择,最终迭代优化获得最优样本组合.具体算法设计见第3节.

3 算法设计

3.1 多目标混合重采样问题定义

在不平衡数据分类问题中,由于对多数类样本(负例)预测正确率高,仍然会取得较高的准确率.因此,更应该关注少数类样本(正例)被分类正确的比例.目前有两个常用的评价指标:

1)精确率(Precision)即查准率,预测为正例的样本正确的比例,其值越大越好.

(4)

其中,TP为实际类别为正例,预测也为正例的样本个数.FP为实际为负例,而将其错分为正例的样本个数.

2)召回率(Recall)即查全率,正例被正确预测的比例,其值越大越好.

(5)

其中,TP的定义同公式(4),FN为实际类别为正例,而被错分为负例的样本个数.

P和R的取值均在[0,1]之间,两者取值均越大越好,但是P和R不能同时达到最优,P升高会导致R降低,反之亦然,但是良好的分类精度是希望两者性能均达到最优.

因此,将多目标混合重采样问题定义为:满足最小化f1=1-P和f2=1-R两个优化目标的样本组合方案.

minF=(f1(X),f2(X))

(6)

设待优化样本个数为D,则决策空间含有D维变量,即X=(x1,x2,…,xD),初始化过程采用二进制编码随机产生N个个体,0表示删除样本,1代表保留该样本,则每一个个体代表一种样本组合方案,如图2所示.

图2 优化样本的二元编码方式Fig.2 Binary coding method of the optimization samples

对于随机初始化个体,利用选定的分类器评估当前样本组合方案的分类精度,即利用公式(6)计算该个体的目标函数值,作为后续进化的依据.

3.2 邻域检测

由3.1节样本编码方法可知,随着样本个数的增加,编码长度会随之增加,巨大的解空间也增加了算法的搜索难度.因此,将所有样本不加区分输入到算法中,仅依赖算法自身寻优能力找到最佳的样本组合,对算法性能也是一种考验.事实证明[22],虽然进化算法在大多数优化问题上能够通过进化迭代推动算法收敛到最优解,但是搜索空间和问题的复杂特性也会给进化算法的搜索效率提出挑战.

为了减小算法搜索空间,降低算法搜索难度,在本节,提出了邻域检测方法,如算法1所示.对于每一个样本,计算并获得距离其最近的K个样本(K=7),设置最大容忍值t,将样本属性划分为安全样本和待优化样本.其中,安全样本是指K近邻中异类样本个数小于等于容忍值的样本,即位于同类样本区域,对分类器生成分类边界或决策规则不会造成困难的一类样本;优化样本是K近邻中异类样本个数大于容忍值的样本,如重叠边界、小间断区域样本,这些样本通常与异类样本分布较为紧密,使分类器难以划分决策边界或确定决策规则.

算法1.邻域检测

输入:训练样本Train_data和SMOTE生成的新样本New_sample

输出:安全样本safeD和优化样本optiD

1.组成新样本集:NTraindata =[Train_data;New_sample];

2.计算每个样本距离最近的K个样本(K=7);

3.计算每个样本的K近邻中与其类别不同的样本数量Diff;

4.for p=1:length(NTraindata)

5. if Diff(p)<=t% 若Diff<=容忍值

6. safeD=[safeD,p];%将该样本存储到安全样本集中

7. else % 反之,若Diff>容忍值

8. optiD=[optiD,p,p_IDX];%将该样本及其k近邻样本存储到优化样本集中

9.end

10.end

11.optiD = unique(optiD,’rows’);%删除optiD中相同样本

因此,通过上述邻域检测过程剔除了安全区域样本,减少了待优化样本个数,缩短了编码长度,实质上是减少了算法搜索空间,有利于算法收敛.

3.3 基于自适应模式挖掘的多目标优化算法

本节提出了一种自适应模式挖掘的多目标优化算法(APMMOEA)用于求解样本组合优化问题,该算法提出了自适应阶段转换方法,对满足一定收敛程度的非支配解集进行自适应切换全局和局部搜索行为.在全局优化阶段采用NSGA-II的优势度排序获得当前最优解,在局部优化阶段采用进化挖掘方法对非零候选集进行优化,由此提高解集质量.其中,自适应阶段转换条件计算方式如下:

(7)

其中,

(8)

(9)

(10)

(11)

基于上述思想的APMMOEA算法,如算法2所示.

算法2.APMMOEA算法

输入:初始化种群(N个初始化样本组合方案)

输出:当前优化获得的样本组合方案OptimP

1.初始化全零矩阵作为最大、最小非零候选集:maxP和minP.

2.环境选择:使用非支配排序和拥挤距离比较算子(见2.2节)进行非支配排序,并选择排序值靠前的N个最优解;

3.For gen = 1:maxgen

4.使用锦标赛选择法确定父代交配池;

5.根据公式(7)计算解集变化率;

6.Ifrg<ε%采用进化挖掘进行局部优化;

7. 使用2.3节进化挖掘方法确定最大非零候选集maxP、最小非零候选集集minP及全零变量;

8. 使用PMMOEA算法的遗传操作,见文献[21];

9. 对当前种群,上一代种群,及非零候选集进行环境选择,同2;

10.Else

11. 使用NSGA-II算法的遗传操作,见文献[20];

12. 对当前种群和上一代种群进行环境选择,同2;

13. End

14.End

15.输出当前环境选择后的样本组合方案OptimP;

3.4 基于邻域检测与反馈的混合重采样进化挖掘方法

综上,结合邻域检测和APMMOEA算法,提出了基于邻域检测与反馈的混合重采样进化挖掘方法(APMMOEA-EC),其算法流程示意图如图3所示.

图3 APMMOEA-EC算法流程图Fig.3 Flow diagram of APMMOEA-EC

APMMOEA-EC伪代码总结如算法3所示.

算法3.主程序APMMOEA-EC

输入:样本集Dataset

输出:训练后模型,分类性能评价指标

% 数据集划分

1.对训练样本归一化:Dataset = mapminmax(Dataset’,0,1)’;

2.按6∶2∶2划分训练集Train_data,测试集Test_data和验证集Valid_data;

3.计算Train_data的不平衡度IR = Minor./(Minor+Major);

4.SMOTE算法以邻域大小为5,采样倍率为IR生成少数类样本:New_sample = SMOTE(Train_data,IR,5);

5.组成新样本集NTraindata=[Train_data;New_sample];

6.利用算法1对NTraindata进行邻域检测,获得待优化样本optiD和安全样本safeD;

7.计算optiD样本数量D,随机初始化种群,如图2;

8.利用算法2获得N个最优样本组合方案集OptimP;

9.forp= 1∶N

10. 提取最优方案中编码不为0的样本,与安全样本组成训练样本:FinalTData = [SafeD;optiD(find(OptimP(p,:)～=0))];

11. 利用训练样本对分类器进行训练:model = ML(FinalTData(:,end),FinalTData(:,1:(end-1));

12. 输出训练模型model,并在测试集上进行分类测试 Predict_Test=predict(model,Test_data);

13. 输出训练模型model,并在验证集上进行分类测试 Predict_ Valid=predict(model,Valid_data);

14. 计算并存储评估指标 ResultTest(p,:)= [F1,GM,AUC];

15. 计算并存储评估指标 ResultValid(p,:)= [F1,GM,AUC];

16.End

APMMOEA-EC算法主要分为邻域检测和反馈优化过程两部分.其中,邻域检测时间复杂度为O(Ndata2),Ndata,为训练样本个数;由于优化过程使用了自适应搜索行为切换策略,其复杂度介于O(MN2)和O(gN′D2)之间,其中,N为种群大小,M为优化目标个数,本文M=2,O(gN′D2)同2.4节PMMOEA时间复杂度,一般情况下,N≪D,因此,O(MN2)≪O(gN′D2).

4 实验对比及结果分析

为了验证APMMOEA-EC算法的有效性,本节实验设计共分为三部分:1)参数对比实验选取最佳的容忍值参数;2)对比APMMOEA算法与5种多目标优化算法NSGA-II(2002)[20],MOEA/D(2007)[23],SparseEA(2020)[25],MOEAPSL(2021)[26]和PMMOEA(2020)[21]在不平衡率(IR)不同的数据集上的优化效果和效率;3)在学习规则不同的分类器上,对比APMMOEA-EC算法与5种不平衡数据处理方法SMOTE[12],Safe level-SMOTE[14],SMOTE-IPF[9],NBcomm[19],SMOTE-WENN[18]在4个真实数据集上性能评估指标.所有实验均在MATLAB R2020b中运行.

4.1 实验数据集

真实数据集和合成数据集来源于http://www.keel.es/,数据集参数见表1.其中,合成数据集用于测试算法处理小间断、非线性边界和边界重叠问题的能力,其边界重叠点个数由扰动率DR控制.真实数据集含有多个复杂分布特性,如离散分布、高度重叠和异常点等,用于测试不同数据处理方法对具有复杂分布特征的不平衡数据的分类能力.

表1 4个真实数据集和3个合成数据集(含6个子集)概况Table 1 Brief descriptions of 4 real datasets and 3 synthetic datasets(including 6 subsets)

4.2 性能评价指标

为了评估不同不平衡数据处理方法的分类效果,用各方法获得的新样本对分类器进行训练,并将训练好的分类器在独立的验证样本上进行测试,评估利用该样本所构建的分类器的泛化能力.有以下3个不平衡二分类算法的综合性能评估指标:

1)F1调和平均数:

(12)

其中,P同公式(4),R同公式(5).F1是对P和R的综合评价指标,取值范围在[0,1],取值越大越好.

2)Gmean均值[24]:

(13)

3)AUC:ROC曲线下面积,可大致计算如下:

(14)

其中,ranki为第i个样本的排序值(根据概率得分),T和F为正负例样本个数.AUC取值越大越好.

4.3 参数对比实验

对邻域检测中容忍值t进行参数对比实验.为了确定APMMOEA-EC算法中最佳容忍值t,在邻域样本选择个数K=7的情况下,选取t=0,1,2,3,4,及不使用邻域检测(即将所有样本作为待优化样本)在不同边界扰动率的3个合成数据集上(IR=5)进行对比实验.以KNN分类器为例,所有对比实验重复10次,取每次实验在测试集(test)上的最佳F1值及其对应在验证集(valid)上的F1值为该次实验对比结果,并计算10次实验的平均值及方差作为最终实验结果,如表2所示.

表2 当K=7时,容忍值的参数对比实验结果Table 2 Experimental parameter comparison results of tolerance value when setting K=7

由表2可以直观看出,当邻域检测个数K为7,容忍值t=1时,在不同扰动率(DR=0.5和0.7)的3个合成数据集上获得更多的平均最优值.具体分析如下:Paw具有小间段、异常点和边界重叠3个复杂分布特征,因此无邻域检测方法(即将所有样本均作为优化样本)以及较低的容忍值(t=0)旨在对更多的样本进行优化选择来满足上述多个复杂特性,因此能够获得较优的F1值.Subcluster和Clover含有上述复杂特征的其中两种,其分类难度(以KNN分类规则为例)较低于Paw数据集,因此相对宽松的容忍值(t≥1)能够通过减少待优化样本个数来降低优化算法的求解难度,从而获得更优的样本组合方案,提高分类精度.

此外,随着扰动概率的增加,即重合边界的面积增加,不同容忍值设置获得F1值均有一定程度的下降,但是没有明显优势的参数设置.综上,当K=7时,容忍值t的最佳取值为t=1,此时在3个合成数据集上F1值相对较好,且待优化个数较无邻域检测方法明显降低,较其他容忍值参数设置相差不大.图4给出了在不同数据集上各参数设置10次重复实验的平均待优化样本个数.其中,无邻域检测方法的待优化样本个数等于样本个数(600个),而采用邻域检测和样本属性划分方法能够明显减少待优化样本个数,而待优化样本个数越少,图2中决策变量编码长度越短,优化空间维度和求解难度也相应降低,更易获得高质量方案解.

图4 设置不同t时,待优化样本个数变化曲线Fig.4 Curve of the number of samples to be optimized when different t is set

4.4 优化算法对比实验

为了验证本文提出的基于自适应模式挖掘的多目标优化算法(APMMOEA)在混合重采样优化问题上的优化效果,将APMMOEA与经典多目标优化算法NSGA-II、MOEA/D,和大规模优化算法SparseEA、MOEAPSL和PMMOEA在设置不同不平衡比率的3个合成数据集上(DR=0.5)进行对比实验.各对比算法流程及遗传算子可参照原文献,其中,PMMOEA和APPMOEA中进化挖掘种群N′=20,迭代g=10.其他算法无额外参数设置.此外,实验参数设置种群大小N为20,进化代数maxgen为40,所有实验重复10次,以HV均值和方差作为最终实验结果,如表3所示.

表3 6种优化算法在不同IR设置的3种合成数据集上的HV结果Table 3 HV results of five optimization algorithms on three synthetic data sets with different IR settings

HV值是衡量各算法最终获得的解集综合性能的评价指标,计算方式如下:

(15)

其中,δ为Lebesgue测度,用来计算体积,|S|表示获得的非支配解个数,vi表示参考点(1,1)与第i个非支配解所构成的超体积;HV越大,算法综合性能越好,所获得的解集收敛性和分布性越好.

由表3可以直观看出,在大多数数据集上,APMMOEA算法获得解集的综合性能更好.这是因为混合重采样优化问题实质上是样本组合优化问题,除了满足P和R两个目标同时优化外,随着数据集样本量的增加,通常决策变量个数也随之增加,因此该问题同时是大规模多目标优化问题.传统经典优化算法NSGA-II和MOEA/D注重目标空间优化,忽略了对决策空间变量的探索和优化.并且MOEA/D生成均匀分布的权重向量,但在实际优化问题中,由于最优前沿形状未知,因此均匀分布的权重向量并不一定能够产生分布性良好的解集,因此,MOEA/D的HV值相对劣于其他几种对比算法.SparseEA、MOEAPSL、PMMOEA和APPMOEA均具有稀疏大规模优化特征,而变量的稀疏优化,即减少样本选择有利于防止过拟合.但是针对本文优化问题,最优样本组合通常在迭代过程中呈现出一定的稳定特征,即频繁模式,PMMOEA和APPMOEA采用进化模式挖掘方法确定变量中的全零变量和非零候选集,并针对非零变量进行局部优化,因此理论上更适用于本文优化问题,但是PMMOEA在进化过程的每代均采用进化挖掘,不仅算法复杂度较高,而且算法早期解集并未收敛,当前非支配解不一定具有最优解特征,因此可能导致局部优化结果不佳.APMMOEA提出了自适应进化挖掘方法,仅对满足一定收敛条件的非支配解进行模式挖掘,并对非零候选集局部优化,因此在HV值上有明显提升.

图5给出了6种对比算法在IR=5,DR=0.5的3个测试集上的HV值变化趋势,可以明显看出APMMOEA较其他对比算法在HV值上增长速度更快,且算法后期仍然具有优于其他算法的提升动力,这是因为APMMOEA在算法后期(即算法收敛到一定程度时)挖掘最优解变量特征,并进行局部优化,由此提高解集质量.

图5 6种对比算法在IR=5,DR=0.5的3个测试集上的HV值变化趋势Fig.5 HV trend of six comparison algorithms on three dataset with IR=5 and DR=0.5

4.5 在不同分类器上不平衡处理方法实验对比结果

APMMOEA-EC算法根据分类器的性能反馈结果指导样本的选择过程,并且能够根据不同分类器的学习机制,优化获得适合各分类器学习规则的样本组合.为了验证这一效果,选取判别式分类器K最近邻(KNN,K=5)、支持向量机(SVM,线性核函数)和生成式分类器朴素贝叶斯(NB),将APMMOEA-EC与5种不平衡处理方法分别在各分类器上对4个真实数据集进行对比实验,其中,APMMOEA算法采用6∶2∶2划分训练集,测试集和验证集,实验参数同4.4节,其他五种不平衡处理方法采用8∶2划分训练集和验证集,并使用4.2节的F1、AUC和GM 3个指标对各算法获得的新样本在验证集上的分类效果进行评价,所有实验重复10次,取各指标平均值和方差作为最终实验结果,如表4～表6所示.由于APMMOEA在优化过程中获得的是一组最优解,其最终解选取为在测试集上F1值最优的样本组合方案,则最终实验结果为利用该方案训练分类器及其在验证集上的分类结果.

表4 6种不平衡数据处理方法在KNN分类器上的性能对比结果Table 4 Performance results of six imbalance data processing methods on KNN classifier

5种对比方法为2.1节介绍的几种流行的不平衡处理方法,其中,NB为欠采样方法,SMOTE为过采样方法,Safe-level SMOTE为改进过采样方法,SMOTEIPF和SMOTEWENN为混合重采样方法.

表4为6种不平衡数据处理方法在4个真实数据集上的KNN分类结果.由表4可以直观看出,APMMOEA-EC在大多数数据集和多数指标上的性能表现优于对比方法.由于Balance数据集具有较高的不平衡率,且正例离散分布,因此采用KNN分类器根据最近邻中大多数样本的类别进行判断,对正例的识别准确率(召回率)较低.在F1指标上,原数据(不使用任何不平衡处理方法)表现更好,分析其原因是由于正例样本离散分布,使用不平衡数据处理方法难以确定正例样本的分布特征,而在此基础上的过采样(SMOTE和Safe-level SMOTE)或欠采样(NBComm)方法增减样本,可能过拟合或改变原有样本分布特征,进一步降低对正例的识别准确性,而混合重采样方法SMOTE-IPF、SMOTE-WENN和APMMOEA-EC在SMOTE生成新样本的基础上进行数据再清洗,一定程度上能够减少不合理样本的产生,因此在F1值上优于上述3个不平衡数据处理方法,且在AUC和GM指标上也具有明显优势.对于3种混合重采样方法,在Balance数据集上基于决策树(SMOTE-IPF)和基于正负例位置分布(SMOTE-WNEE)的数据清洗方法比基于KNN模型性能反馈(APMMOEA-EC)方法本身依赖邻域样本类别数量,对离散样本的分类准确率更好,因此其指标值较优于APMMOEA-EC方法.而对于边界重叠和异常样本,APMMOEA-EC通过邻域检测能够找到此类易造成分类误差的样本并进行优化选择,因此在Cmc和Transfusion数据集上优于其他6种对比方法.在newthyroid数据集上,3种混合重采样方法结果相差不大,由于APMMOEA-EC同时对P和R两个目标进行优化,因此对正例分类准确率更高,即F1值相对较高.

表5为6种不平衡数据处理方法在4个真实数据集上的SVM分类结果.由表5可以直观看出,APMMOEA-EC在大多数数据集和多数指标上的性能表现优于对比方法.由于SVM最大化决策边界来实现样本分类,因此在具有离散数据特征的Balance数据集上和具有重合边界的其他3个数据集上分类效果总体不佳,因此在原数据上的分类结果明显劣于KNN分类效果.在Balance数据集上,过采样方法(SMOTE和Safe-level SMOTE)效果不佳,其原因是正例分布的离散性,难以根据其位置分布特征生成具有明显决策边界的新样本.而NBcomm通过减少正例样本周围负例样本的分布密度,有利于提高正例样本的可见性,因此NBcomm与混合重采样方法在Balance数据集上的指标值相对较好;在其他3个数据集上,6种不平衡处理方法获得的分类结果较原数据有明显的提升,APMMOEA-EC在大多数评价指标上优于其他对比方法,这是因为邻域检测方法有助于找到决策边界上的易混淆样本,并根据SVM性能反馈优化边界样本,从而帮助SVM找到决策边界;其中,Transfusion和Cmc数据集上,APPMOEA-EC的指标值明显优于其他方法,表明在边界重叠和异常点数据处理上效果更好.

表5 6种不平衡数据处理方法在SVM分类器上的性能对比结果Table 5 Performance results of six imbalance data processing methods on SVM classifier

表6为6种不平衡数据处理方法在4个真实数据集上的NB分类结果.由表6可以直观看出,APMMOEA-EC在大多数数据集和多数指标上的性能表现优于对比方法.与KNN和SVM判别式分类器不同的是,NB是生成式分类器,在Balance(高不平衡率)数据集上能够明显提高原数据的分类效果,这是因为不平衡数据处理方法首要目的是平衡正负例样本的数量,因此有利于提高对正例样本的识别准确率;但是在Cmc和Newthyroid两个数据集上(边界重叠、异常点),由于NB是基于概率的分类规则,表中不平衡处理方法(除了APPMOEA-EC和SMOTE-IPF)大多是基于样本空间距离的样本生成或删减方法,其分类效果较劣于原数据;而混合重采样方法中,APPMOEA-EC和SMOTE-IPF是基于学习规则(NB和DT)的数据清洗方法,在Tansfusion和Cmc数据集上较其他不平衡数据处理方法的分类效果有一定程度提高,但是由于APPMOEA-EC方法是基于NB分类器性能反馈对样本组合迭代优化,更适合NB分类器学习规则本身,因此其优化结果明显优于基于DT学习规则和基于样本空间距离的不平衡处理方法.

综上,APPMOEA-EC在具有不同学习规则的分类器上的样本组合优化结果,能够在大多数数据集上较对比方法训练出分类性能更好的分类模型,验证了APPMOEA-EC方法在不平衡数据分类问题上的有效性和优越性.

5 总结及展望

本文提出了基于邻域检测与反馈的混合重采样进化挖掘方法(APPMOEA-EC),该方法旨在将样本的清洗过程与分类器的学习过程进行交互,以召回率和精准率作为优化目标,通过多目标优化过程获得最优样本组合,这改变了传统不平衡数据处理方法利用先验知识删减样本可能存在盲目性和局限性等不足.同时提出邻域检测方法实现了对样本属性划分和决策空间降维,并且在算法设计时提出了自适应搜索行为切换方法,在优化过程中平衡了算法全局和局部优化能力,进一步提高了最优解质量.但同时本文方法仍存在两方面不足,一是在算法设计上:针对二元变量优化问题,其遗传操作设计方法比较单一,可能需要尝试新遗传算子,加速算法收敛;二是编码方式上:由于编码长度与样本数量成正比,因此本文方法仍然只适合小样本和离线数据处理,未来工作将致力于解决上述两个问题.