基于DBSCAN聚类分解和过采样的随机森林不平衡数据分类算法

赵小强, 姚青磊

(1. 兰州理工大学 电气工程与信息工程学院, 甘肃 兰州 730050; 2. 兰州理工大学 甘肃省工业过程先进控制重点实验室, 甘肃 兰州 730050; 3. 兰州理工大学 国家级电气与控制工程实验教学中心, 甘肃 兰州 730050)

随着计算机、通信技术的快速发展,互联网和工业等领域产生了大量的数据,如何在这些大量数据中找到并使用有价值的数据已成为目前研究的热点.因此,数据挖掘引起了人们的极大关注,而数据不平衡问题是数据挖掘中的一个难点,该问题是指在数据集中某一类的实例数量远远少于其他类的实例数量的情况,其中实例数较多的称为多数类(负类),实例数较少的称为少数类(正类),多数类和少数类数量的比例称为不平衡比率.传统的机器学习算法,如SVM[1-2]、决策树[3]、KNN[4]等都是假定数据集是在平衡的情况下进行分类的.而在现实生活中,许多领域都存在不平衡数据,如信用卡诈骗[5]、蛋白质分类[6]、故障诊断[7]和癌症诊断[8]等.若使用传统的机器学习分类算法,在处理不平衡数据集时会为了追求较高的准确率而导致分类算法偏向于负类.但是在二分类中,正类负类的错分代价往往是不同的,例如在信用卡诈骗中,将诈骗事件误判为正常事件会导致不可预估的损失;在癌症诊断中,将发病群体比较少的癌症患者误判成正常人,会导致病人错过最佳的治疗时机,严重的可能导致生命威胁.因此,研究高效的不平衡数据分类算法很有意义.

近年来,有许多国内外学者对不平衡数据分类问题进行了大量的研究.在处理不平衡数据分类问题时,改进方法主要包括两个层面:数据预处理层面和分类算法层面.数据预处理层面也称为数据平衡方法,通过对不平衡数据进行采样来改变数据样本分布或消除不平衡性,其代表性的方法包括欠采样、过采样和混合采样.分类算法层面是对现有的算法进行修改,提高模型对少数类的识别能力,典型的算法包括代价敏感法、单类学习法和集成学习法.

Chawla等[9]提出了一种称为SMOTE(synthetic minority oversampling technique)的过采样算法,该算法不像随机过采样算法只是单纯地复制或者简单地旋转来增加样本个数,而是通过合成新的、无重复的小样本并进行插值处理扩充样本数量,并且该方法没有造成数据丢失.Pakrashi等[10]基于一种训练多类集成分类模型的新视角,利用卡尔曼滤波器的传感器融合特性,将多个独立的多类分类器组合在一起,构建了多类集成分类算法.Chawla等[11]在SMOTE的基础上,将SMOTE与AdaBoost结合,提出了SMOTEBoost算法,该算法从少数类中合成实例从而间接改变权重,进一步地提升了分类模型的性能,但是如果原始数据集的不平衡率比较高,使用过采样算法得到最理想的平衡数据集(不平衡率为1∶1)时,生成的假样本会更多,会导致数据集样本数量特别大,从而拖慢算法运行速度.Seiffert等[12]基于SMOTEBoost算法,提出了一种基于随机欠采样和boosting结合的混合算法,称为RUSBoost,随机欠采样随机删除大多数实例以形成平衡的数据集,但是由于随机欠采样的局限性,得到的数据集可能会丢失一部分多数类中的有用信息.Rayhan等[13]提出了一种基于聚类的欠采样和Adaboost结合的算法,称为CUSBoost,该算法将原始数据集分为多数类和少数类,并使用k-means聚类算法将多数类分成多个簇,然后通过随机选择50%的实例对多数类进行欠采样,达到在欠采样的情况下尽可能地保留多数类有用信息.Ahmed等[14]将欠采样和过采样算法结合起来,提出了RSYNBagging算法,该算法在奇数次迭代的过程中使用随机欠采样算法,在偶数次迭代中使用ADASYN过采样算法,并使用集成学习中的Bagging算法进行投票得到分类结果.Elyan等[15]提出了CDSMOTE算法,该算法使用k-means聚类算法将多数类分为多个簇,然后将少数类样本应用SMOTE算法来平衡数据集,避免了信息丢失,但是由于分类器较为单一,没有达到好的效果.上述方法虽然都在一定程度上提高了不平衡数据的分类性能,但是会存在数据丢失或者数据量过大等问题.

针对这些问题,本文提出了一种基于DBSCAN聚类分解和过采样的随机森林不平衡数据分类算法,该算法通过将不平衡数据集分为多数类和少数类,先将DBSCAN算法应用于多数类进行聚类,将多数类分解为多个子类,然后使用Borderline-SMOTE过采样算法对少数类数据进行处理,最后将这个方法和随机森林结合起来.经实验验证,该算法能有效地提升不平衡数据的分类效果.

1 相关算法

DBSCAN[16](density-based spatial clustering of applications with noise)是一种基于密度的聚类算法,它的目的是发现任意形状的簇,参数描述了领域的样本分布紧密程度,其中定义了密度的领域半径,定义了核心点的阈值.

当设定eps和MinPts=5之后,算法原理如图1所示.该算法选定某个核心对象(图中黄色点),不断向密度可达的区域扩张,由密度可达的关系导出最大密度相连的样本集合,这个集合就是一个簇.

图1 DBSCAN算法原理图

1.2 Borderline-SMOTE算法

Borderline-SMOTE[17]是一种改进的SMOTE算法.如图2所示,该算法将少数类样本按边界分为三类,周围一半以上是少数类样本的称为Safe,一半以下是少数类样本的称为Danger,周围没有少数类样本的称为Noise.由于Safe群体被误分可能较小,而Danger群体被误分可能很大,所以Borderline-SMOTE算法只对Danger群体样本进行采样处理.

图2 少数类样本边界划分Fig.2 Minority sample boundary division

2 基于DBSCAN聚类分解和过采样的随机森林不平衡数据分类算法

本文提出一种基于密度的聚类分解技术和过采样技术相结合的随机森林不平衡数据分类算法,通过将DBSCAN算法应用于不平衡数据集,来对数据集中多数类进行聚类分解,将多数类划分为多个子类,以降低多数类在数据集中的优势;然后使用过采样技术,增加少数类的个数,提高少数类在数据集中的优势.对于不平衡数据集A,先将其分解为数据集Ac,然后计算类分解之后类别的平均值,如果少数类数据个数仍然少于平均值个数,再使用过采样算法,以重新评估分解后的数据集Ac,且使用过采样算法后,会创建一个新的数据集Aco,这个新数据集是类分解和过采样之后的结果,最后将随机森林分类技术应用于数据集Aco.基于DBSCAN聚类分解和过采样的随机森林不平衡数据分类流程图如图3所示.

图3 基于DBSCAN聚类分解和过采样的随机森林不平衡数据分类算法流程图

通过DBSCAN聚类分解和过采样方法得到平衡数据集,再建立随机森林分类模型,设随机森林分类模型规模为t,则具体步骤如下:

输入:不平衡样本集A,随机森林决策树数量t.

输出:分类结果.

Step1:对样本集A中多数类negative=(n1,n2,…,nm)使用DBSCAN聚类算法,最终划分为簇c1,c2,…,cn.

Step2:计算簇c1,c2,…,cn的平均值,若少数类样本数量大于平均值,则转至Step5;若少数类样本数量小于平均值,则选取最接近平均值的一个子类作为过采样数量标准,计算少数类样本个数pnum,多数类子类样本个数nnum.

Step3:对少数类按边界划分为Safe样本、Danger样本、Noise样本,将Danger样本记为{p′1,p′2,…,p′a},样本个数记为dnum.计算Danger样本中每个样本p′i与少数类positive的k近邻,根据nnum和pnum的比例设置一个采样比例以确定采样倍率N,根据采样倍率N随机选择s个k近邻与样本p′i进行线性插值,合成少数样本pnew:

pnew=p′i+rand(0,1)×dj(j=1,2,…,s)

(1)

其中:dj代表p′i与其s个k近邻的距离.

Step4:将合成少数样本加入原本的少数类中,构成新的少数类positive-c1.

Step5:将多数类子集和少数类数据集共同合成一个新的平衡数据集Aco.

Step6:计算新的平衡数据集Aco样本个数N,利用Bootstrap有放回地随机抽取N次,生成和原训练集样本个数相同的子训练集,这个过程重复t次,得到t个子训练集,构建t棵分类决策树.

Step7:分裂时从训练样本的R个特征中随机选择r个特征个数(r

Step8:使用生成的t棵决策树组成随机森林,最终的输出结果由每个决策树的分类结果投票决定.

2.1 聚类分解

聚类分解是将聚类算法应用于数据集上,将数据集中的同一类数据分为一组,以分解为多个子集,其目的主要有两个,一是降低多数类的优势,二是不会产生任何的数据信息丢失.当今流行的方法是使用k-means算法对数据集进行聚类,但是该方法易受噪声的干扰.针对这个问题,本文使用了对噪声不敏感的DBSCAN聚类算法,将该算法应用于数据集的多数类上,来生成多个多数类子类,从而减少了异常值对模型的影响,并且不用像k-means算法那样预先设置k值.

应用聚类分解之后,其结果如图4所示,图4a表示二分类不平衡数据集的原始数据分布,图4b表示使用DBSCAN聚类分解之后的数据分布.图4a和图4b中是相同的数据集,但是集群分布不同.通过聚类分解之后,将negative类别分解为negative-c1、negative-c2等(图4b中分别用c1、c2等表示),这样,就可以在保留所有数据信息的同时改变数据集的分布.

图4 聚类分解应用于不平衡数据集

二进制分类任务如下式所示:

h(X):X→Y

(2)

在h(X)中,将每个实例xi映射到yi∈{N,P}.在使用聚类分解之后,得到一个新的分类任务h′(X):

h′(X):X→Y′

(3)

将每个实例xi映射到y′i∈{Nc1,Nc2,Nc3,…,P}.转换数据可以将负类N聚类成多个子类,有效地降低了负类N在数据集中的主导地位,这也意味着通过聚类分解方法,将原始的二进制分类问题转化成了多分类问题.

2.2 少数类过采样

由于样本的分布紧密程度不尽相同,在应用DBSCAN聚类分解算法以后,从原始的多数类实例中可能会产生新的多数类或少数类,所以,需要计算少数类的样本数量是否超过多数类子类的平均样本数,如果没有超过,则需对少数类进行过采样.

当今最流行的过采样算法是Chawla提出的SMOTE算法,SMOTE算法通过特征空间而不是数据空间来使用k近邻算法进行生成合成实例,有多位学者[18]验证了该算法在不平衡数据上得到了不错的效果.但是使用SMOTE算法生成的样例可能会出现样本重叠、噪声等问题[19],为了避免这些问题,本文采用Borderline-SMOTE算法来进行过采样处理,它只对Danger群体的边界样本进行过采样处理,这样可以很好地避免少数类中的噪声问题,并且降低了少数类样本中的类内不平衡问题的影响.

Borderline-SMOTE算法和SMOTE算法一样需要选择一个多数类和一个少数类作为输入,多数类的样本数量是对少数类样本合成数量的参考标准.在本文中,选择使用最接近平均值线的多数类子类样本作为Borderline-SMOTE的多数类输入,例如在图4b中,被选用的多数类子类为negative-c1.使用过采样方法的目的是增加少数类样本数量,进一步减少不平衡比率,降低多数类优势,使正负两类趋于平衡,提高少数类样本的分类精度.

2.3 随机森林

集成学习的原理是将多个弱分类器结合起来,以获得比单一弱分类器更好的结果,最常用的集成学习算法分为Boosting和Bagging.随机森林[20]是Bagging算法的变体,是一种包含多个决策树的集成算法,它训练样本时采用Bootstrap技术,从原始数据集中有放回地随机抽取N个样本作为一棵树的训练集,每次随机选择训练样本特征中的一部分构建决策树,每棵决策树训练生长过程中不进行剪枝,最后采用投票的方式决定分类器最终的结果.由于随机森林的随机性,避免了过拟合的风险,提高了分类准确率[21].

3 实验结果与分析

本文实验是在Windows10系统、AMD 7-4800处理器、NVIDIA GTX 1650ti显卡、16GB内存的计算机上进行,编程语言为Python,使用PyCharm平台实现.

3.1 实验数据

本文使用KEEL公共数据库(http://www.keel.es)[22]中的36个数据集,这些数据集全都常用于不平衡数据分类中.如表1所列,每个数据集具有不同的不平衡比率、不同的实例数量、不同特征的二分类数据集.

Glass数据集的属性有9个,属性名称分别为RI、Na、Mg、Al、Si、K、Ca、Ba、Fe.Glass0是Glass数据集的一个版本,其中第0类属于正类,其余属性属于负类;Glass2中第2类属于正类,其余属性属于负类;Glass-0-1-2-3_vs_4-5-6中0、1、2、3类属于正类,4、5、6类属于负类.

Yeast是一个酵母菌数据集,用于预测酵母菌蛋白质的定位位点.在yeast数据集中属性有8个,属性名称分别为Mcg、Gvh、Alm、Mit、Erl、Pox、Vac、Nuc.Yeast1中Nuc属于正类,其余属性属于负类;Yeast-1-2-8-9_vs_7中Vac属于正类,Nuc、Cyt、Pox、Erl类属于负类;Yeast-1_vs_7中Pox属性已被删除,Vac属于正类,Nuc属于负类.

表1 数据集

3.2 评价指标

不平衡数据分类的难点不只体现在分类模型的训练上,还体现在如何正确地评价不平衡分类模型的性能上.在不平衡数据处理中,因为不平衡数据中多数类和少数类具有不同的错分代价,少数类的错分可能带来比较严重的后果,即便总体准确率较高,但并不代表分类模型是有效的,因此传统评价指标不能很好地反映分类模型的性能好坏.

对于不平衡数据的分类性能评价,有相关学者在混淆矩阵的基础上,提出了F-measure、G-mean等一系列评价标准.混淆矩阵如表2所列.

表2 混淆矩阵

相关评估指标如下:

Precision表示精确率,也称为查准率,表示预测为正类的样本中真正的正类样本所占的比例,其公式为

(4)

Recall表示召回率,也称为查全率,表示正类样本中被预测正确的样本所占的比例,公式为

(5)

F-measure也称为F-score,是可以兼顾精确率和召回率的最佳组合,公式为

(6)

其中:β为参数,当β=1时,称为F1值.

G-mean也称为G均值,是一种衡量数据集整体分类性能的综合评价指标,如下式所示:

(7)

ROC曲线(receiver operating characteristic curve)是表示以假阳性率(FPR)为横轴和以真阳性率(TPR)为竖轴的曲线,曲线越靠近坐标轴左上角代表分类器性能越好.ROC曲线与坐标轴围成的面积被称为AUROC(area under the receiver operating characteristic curve)值,AUROC值越大,代表分类器性能越好.假阳性率和真阳性率公式如下:

(8)

(9)

3.3 实验结果

为验证本文所提算法(DBSRF)的有效性,使用Precision、Recall、F1Score、AUROC、G-mean 5个评价指标对数据集进行实验验证.在实验中,DBSCAN算法敏感参数设定为eps=0.5,MinPts=5;SMOTE、Borderline-SMOTE、ADASYN算法近邻数k设置为5;Borderline-SMOTE算法中最近邻参数m设置为10;Adaboost、Bagging、随机森林(RF)使用C4.5决策树作为基分类器,集成学习的n_estimators设置为50,n_estimators在Adaboost和Bagging中代表迭代次数,在随机森林代表生成的决策树数量.数据集按照70%和30%的比率分为训练集和测试集,实验进行五倍交叉验证训练.

3.3.1不同过采样方法对比

为证明所选过采样方法的有效性,在DBSCAN聚类分解和随机森林分类框架的前提下,使用不同的过采样方法对数据集进行处理,其中对比的过采样方法有SMOTE、Borderline-SMOTE和ADASYN.ADASYN[23]算法对不同的少数类样本赋予不同的权重,从而生成不同数量的样本,其中较难学习的少数类样本比容易学习的少数类样本产生更多的合成数据,因此,ADASYN算法在减少类不平衡的同时,将分类决策边界向较难学习的少数类方向移动.

在KEEL数据集中选取6组不平衡数据集进行实验验证,其结果如表3所列.由表3可知,Borderline-SMOTE在6组数据集中,有4组数据集在五个指标中全优,这是因为该算法仅使用边界上的少数类样本来合成新样本,减少了噪声的干扰.

3.3.2与基于Adaboost和Bagging算法的对比

为验证本文数据预处理方法的有效性,将聚类分解过采样部分与Adaboost和Bagging分别结合.

LIUBoost[24]是将代价敏感和欠采样结合,并与Adaboost结合的混合算法,首先使用欠采样方法来平衡数据集,同时保留有关实例局部特征的重要信息,并将该信息合并到Adaboost的权重更新方程中,最大限度地减少了欠采样带来的信息损失.本文提出算法使用Adaboost分类器时,对比RUSBoost和LIUBoost算法,性能指标使用AUROC.其五次平均分数如表4所列,在验证的17个数据集中10个表现最优.由于篇幅限制,在表4中只列出随机选取的10个数据集的结果.

表3 不同过采样方法的性能对比

表4 不同数据预处理方法与Adaboost结合的AUROC值对比

UnderBagging是一种基于Bagging的随机欠采样算法,数据预处理部分仅对原始数据集进行欠采样;SMOTEBagging将SMOTE过采样算法应用在少数类上并与Bagging结合,显示出了更高的分类精度;ADASYNBagging类似于SMOTEBagging,将ADASYN应用于少数类实例,为较难分类的少数类实例生成更多的合成样本,同时使用Bagging保持多数类实例不受影响,该方法保持了采样率的固定,并且不需要额外的参数调整.本文提出算法使用Bagging分类器时,与四种基于Bagging的算法进行对比,性能指标使用AUROC.其五次平均分数如表5所列,在验证的10个数据集中9个表现最优.

表5 不同数据预处理方法与Bagging结合的AUROC值对比

这可以验证本文提出的算法在处理不平衡问题时是有效的,优势在于聚类分解可以降低多数类优势,并只对少数类边界样本进行过采样,减少了噪声的干扰,提高了分类模型的性能.

3.3.3不同分类器对比

为验证分类器在聚类分解和过采样方法前提下的有效性,将本文所提出的DBSCAN聚类分解和Borderline-SMOTE方法对不平衡数据集进行处理,再使用5种不同的分类器对处理过的数据集进行训练学习,得到分类结果,其中所选分类器有SVM、Adaboost、Bagging、XGBoost和随机森林(RF).SVM在处理小样本高维度的数据时占有优势;Adaboost不改变训练数据,迭代时提升错分样本权重;在Bagging中只取初始训练样本中的一部分来训练,再对分类任务使用简单投票法;XGBoost考虑了训练数据为稀疏值的情况,可以自动学习出它的分裂方向;随机森林在训练过程中加入了随机属性选择.此实验的目的是在聚类分解和过采样的前提下选择最合适的分类器.

在验证的13个数据集中有10个数据集4个指标结果最优、1个数据集3个指标结果最优.由于篇幅限制,在表6中只列出了其中4个数据集的实验结果.由此可以看出,在本文数据预处理的前提下,随机森林分类器比SVM、Adaboost、Bagging、XGBoost的分类性能表现更好.

表6 DBSCAN聚类分解和过采样前提下的不同分类算法的结果

3.3.4 与基于随机森林的算法对比

为了验证分类性能,选取使用随机森林分类的方法进行对比,其中分为两部分,一部分是欠采样与随机森林结合的算法对比,另一部分是过采样与随机森林结合的算法对比.

与欠采样部分中的对比算法有三种,分别为:(1) 传统随机森林算法(RF),该算法直接采用Bootstrap对不平衡数据集随机抽样形成训练样本;(2) 随机欠采样与随机森林结合算法(URF),该算法对多数类样本进行随机欠采样,再与少数类样本混合形成训练样本;(3)k-means聚类算法欠采样与随机森林结合算法(CUSRF)[25],该算法对多数类样本进行聚类形成多个簇,再对每个簇进行随机欠采样,与少数类样本混合形成训练样本.在验证的8个数据集中有5个数据集表现最优,其中shuttle-c2-vs-c4数据集中4个指标全为1.由于篇幅限制,在表7中只列出了其中4个数据集的实验结果.

与过采样部分中对比的算法分别为:(1) SMOTE与随机森林结合算法(SM+RF);(2) 加权SMOTE与随机森林结合(WSM+RF),该算法在SMOTE算法中让靠近类别中心和边界的样本生成更多的假样本数量;(3) SMOTE与加权随机森林(SM+WRF),该算法在决策树训练阶段,给每棵树赋予一个权重;(4) 加权SMOTE与加权随机森林结合(WSM+WRF)[26],该算法先对少数类样本进行加权过采样,然后在分类阶段增加分类效果好的决策树权重.G-mean值如图5所示,从图5可以看到,本文算法在验证的数据集中G-mean值全部最优.

表7 欠采样策略与随机森林结合方法与本文方法的综合性能对比

图5 过采样策略与随机森林结合方法与本文方法的G-mean值对比Fig.5 Comparison of the G-mean value between the combination of oversampling strategy and random forest method and the method in this paper

4 结论

本文针对不平衡数据提出了一种基于DBSCAN聚类算法对多数类分解和Borderline-SMOTE对少数类进行过采样的随机森林不平衡数据分类算法,该算法在不损失多数类样本数据信息的前提下降低了多数类在数据集中的优势,并通过过采样方法增加少数类实例,进一步降低了不平衡率,从而改进了结果.经实验证明,对于不同不平衡率、不同样本数量的数据集,本文算法与当前流行不平衡数据处理方法对比,结果显示本文算法有效地提高了不平衡数据分类性能.下一步将考虑如何减少对聚类结果的依赖,并对大数据集中的不平衡问题进行研究.