一种新的过采样算法DB_SMOTE

刘余霞，刘三民，刘涛，王忠群

1.安徽工程大学建筑工程学院，安徽芜湖 241000

2.安徽工程大学计算机与信息学院，安徽芜湖 241000

3.南京航空航天大学计算机科学与技术学院，南京 210016

4.安徽工程大学管理工程学院，安徽芜湖 241000

◎数据库、数据挖掘、机器学习◎

一种新的过采样算法DB_SMOTE

刘余霞1，刘三民2，3，刘涛2，王忠群4

1.安徽工程大学建筑工程学院，安徽芜湖 241000

2.安徽工程大学计算机与信息学院，安徽芜湖 241000

3.南京航空航天大学计算机科学与技术学院，南京 210016

4.安徽工程大学管理工程学院，安徽芜湖 241000

针对非平衡数据集中类分布信息不对称现象，提出一种新的过采样算法DB_SMOTE（Distance-based Synthetic Minority Over-sampling Technique），通过合成少数类新样本解决样本不足问题。算法基于样本与类中心距离，结合类聚集程度提取种子样本。根据SMOTE（Synthetic Minority Over-sampling Technique）算法思想，在种子样本上实现少数类新样本合成。根据种子样本与少数类中心距离构造新样本分布函数。基于此采样算法并在多个数据集上进行分类实验，结果表明DB_SMOTE算法是可行的。

非平衡数据学习；过采样；数据分类

1 引言

非平衡数据学习（Imbalanced Data Learning，IDL）是指学习的数据集类别分布不均匀，其中某类样本数量在整个数据集内占据绝对优势。这一现象广泛存在各种领域，如医疗诊断、故障检测、金融欺诈等[1]。而传统机器学习算法均是基于样本分布均匀基础之上建立的，直接迁移到非平衡数据学习环境是不可取的。

非平衡数据学习的关键问题是如何弥补少数类样本在分布信息方面不足的问题，常用方法包括数据采样、代价敏感学习、集成学习、主动学习等[1]。基于数据层面的采样方法简单、直观，倍受研究人员青睐。数据采样主要包括过采样和欠采样两种途径。在过采样研究中，由Chawla等[2]提出的SMOTE算法成为经典，现有很多算法均是基于此原型提出。SMOTE算法是通过寻找样本的近邻集，从近邻集中随机选择样本与之形成线，并在线上合成新样本点。为避免SMOTE算法样本覆盖问题，文献[3]提出Borderline-SMOTE算法，它寻找少数类当中“危险”样本，基于此类样本合成新样本。在此基础上，文献[4]根据样本的“危险”程度，构造出合成新样本的分布函数，来决定依据各“危险”样本合成新样本的个数。文献[5]实现了基于聚类的抽样算法CBO（Cluster-based Over-sampling），它适合于类分布中含有多个不连接的聚集点情况。文献[6]通过保留多数类边界附近样本，实现欠采样策略，其中难题是邻域半径难以确定。结合抽样技术，Chawla等提出SMOTEBoost算法，它在每次迭代中引入合成样本，保证各子分类器更多地获取少数类样本信息，使集成分类器获得更优性能[7]。RUSBoost算法应用随机欠采样从多数类中随机移出样本形成多个子分类器进行集成，该算法简单易实现[8]。李雄飞等[9]提出分类算法PCBoost，它用随机采样方式的数据合成方法，平衡样本分布信息，同时具备及时“扰动修正”和删除错分合成样本的功能。文献[10]结合迁移技术和集成学习解决了样本非平衡问题，在学习过程中通过样本权重的动态调整和冗余样本的淘汰策略保证分类器的性能。文献[11]在特征空间合成新样本，引入核的方法实现空间转换，保证合成样本的质量，有效提高了SVM的分类效果。文献[12]针对SMOTE采样算法的不足，将支持度概念和轮盘选择技术，并结合异类近邻的分布信息实现对少数样本合成。为解决集成学习对少数类样本分类准确率不高问题，把Bagging集成学习和SMOTE过采样方法相结合，提高了少数类分类准确率[13]。

上述文献所涉及的数据合成大多是基于K-近邻思想，计算量较大，易受噪声问题影响。本文通过用样本距离结合类的聚集程度（类平均距离），提出一种新的非平衡数据集学习算法DB_SMOTE。算法依据是假设凡位于类边缘的样本更有助于形成分类边界，通过直接比较样本与类中心距离和聚集程度相比得到种子样本，并在种子样本和类中心的连线上合成新样本，实现过采样策略。

2 非平衡数据集学习算法DB_SMOTE

为便于讨论，本文主要关注只有两类样本的非平衡数据学习问题，且规定少数类样本为正类样本，多数类样本为负类样本。算法DB_SMOTE主要包括三个阶段：首先是寻找少数类种子样本；其次是构建合成样本的分布函数；最后是结合平衡因子和分布函数实现过采样。

2.1 少数类样本数据合成

为便于叙述，首先给出下列相关定义。

设某类样本集合S={di，i=1，2，…，n}，其中di表示m维向量，维数大小代表样本特征个数。

定义1类中心（class center）是指某类样本在数据空间的平均中心点。类中心点cc是与样本维数相同的向量，计算方法如公式（1）所示：

定义2类平均距离（class average distance）是指某类中各样本到类中心距离和的平均值，是一标量。该距离cd能够反映出类的聚集程度，值越小类聚集程度越紧，反之较松散。计算如下式所示：

其中函数D(，)表示欧氏距离计算方法。

基于过采样策略的新样本生成关键是找出种子样本，在此基础上迭代生成新样本。在样本分类过程中，位于类边缘的样本是最易出现分类错误的，因此其所拥有的分类信息是最多的。在本文结合类平均距离很容易定义出所需要的种子样本。

定义3种子样本（seed sample）指样本到类中心距离大于类平均距离的样本。计算如公式（3）所示：

由种子样本构成的样本集称为侯选集（candidate set）。为避免在合成样本中引入过多的噪声，本文结合现有文献进行改进：指定类中心作为参照点，由侯选集内样本与参照点形成线段，在线段内合成新样本，保证合成样本位于类的内侧。根据SMOTE算法思想，本文算法合成新样本（synthetic new sample）生成公式如式（4）所示：

其中si属于侯选集内样本，r是取值于[0，1]之间的随机数。

由前文所述可知，侯选集内的样本与类中心的距离越远，其所带有效信息相对较多。因此基于此类样本合成新样本个数应该越多，越有利于提高分类模型的精度。据此算法利用距离信息，构造出合成样本分布函数。

若侯选集cs={csi，i=1，2，…，k}，根据欧氏距离计算方法易得出每个样本到中心的距离D(csi，cc)，表示侯选集中第i个样本与类中心cc间距离，累加可得距离和s。在此基础上可以得出分布函数P，具体如公式（5）所示：

把样本分布概率值乘以样本合成总数即可得到基于每个侯选样本合成新样本的个数。

2.2 算法实现

在上述合成策略的基础上，可得出具体的学习算法DB_SMOTE。

设样本集合DS={(di，ci)，i=1，2，…，n}，其中di表示样本向量，ci表示样本所属类别。在本文中以二类问题作为研究对象，ci取值设定为0和1。

算法：DB_SMOTE(DS，L，σ)

输入：数据集DS，学习器L，平衡因子σ

步骤：

（1）调用分层抽样对数据集DS进行处理，形成训练集(tr)和测试集(ts)。

（2）对训练集tr进行统计得到少数类样本集min和多数类样本集maj。

（3）根据公式（1）和公式（2）求出少数类样本中心cc和类平均距离cd。

（4）计算合成样本总数num=(|maj|-|min|)*σ。

（5）由公式（3）可得到侯选集cs，在此基础上根据公式（5）得到概率分布函数。

（6）fori=1，|cs|

（7）forj=1，Int(pi*num)

（8）产生随机数r

（9）根据公式（4）合成新样本sns

（10）tr=tr∪sns

（11）得到分类模型L(tr)，并在ts测试。

算法中Int（）函数表示取整。平衡因子σ决定合成样本总数，根据需要可自由设定。在本文中，平衡因子σ取值为1，保证过采样后的训练集是平衡的。

3 实验分析

为验证文中所提算法的可行性，实验时同另外三种方法（未采样、SMOTE、Borderline_SMOTE）在九个数据集上针对分类器的F-value和G-mean进行对比分析。

3.1 数据集

实验中九个实验数据集源自UCI公开数据集。每个数据集的样本总数、少数类样本和多数类样本等详细信息如表1所示。其中数据集yeast_I（CYT和EXC）、yeast_II（NUC和VAC）和yeast_III（MIT和POX）均来自UCI中yeast数据集，它们分别由原数据集中的样本构成。原数据集wine中包含三类样本，本文实验过程中把前两类合并成一类。

表1 数据集

由文献[9，14]可知，数据集中两类样本数比例超过1∶2，即可认为数据集是不平衡的。

3.2 评价度量

由于数据集的非平衡性，按照传统方法用准确率来衡量分类器的性能是不合适的。为客观、公正地评价分类器的性能，满足实际需求（人们常常更关注的是少数类的分类情况），应寻求新的度量参数。

文中分类器性能评价参数是基于表2所示的混淆矩阵定义所得到。

表2 混淆矩阵

由表2很容易得出分类模型的准确率（accuracy）、精度（precision）、召回率（recall）等概念。

而F-value是精度和召回率的调和均值，其值接近两数的较小者。在非平衡数据学习中用F-value能全面反映分类器性能，因为只有当精度和召回率均较大时，F-value才会变大，满足实际需求。计算方法如公式（7）所示：

在公式（7）中参数β通常取值1，用以调节两个参数的重要程度。

若要同时衡量分类器对两类样本分类平均性能，可以用G-mean参数度量，它是两类召回率的几何平均值。

综上，本文在进行算法对比时，主要关注少数类的F-value值和分类器的G-mean值。

3.3 实验数据分析

本文的仿真实验均是基于Weka平台在Eclipse环境中实现，记录了学习器（决策树）在四种实验方案下的实验数据，即未采样方案、SMOTE采样、Borderline_SMOTE采样和本文的采样方案。其中学习器决策树是用Weka平台内的J48算法，采用默认参数设置。由于每个算法中具有随机因子，所以每种算法在各数据集上运行五次，取其平均值作为结果比较。同原文献相似，算法SMOTE和Borderline_SMOTE中的K-近邻参数均取值为5。

为便于对比算法的优势，图1和图2分别表示四种学习策略在九个数据集上的F-value和G-mean变化趋势曲线，其中横坐标表示每种具体的实验方案。图中九个数据集上的曲线表明，本文提出的DB_SMOTE算法是可行的。分类器的F-value值和G-mean值均得到显著提升，说明通过对少数类样本的合成能够弥补信息不足问题，且其分类器指标值均大于未采样和SMOTE采样方案，表明本文的算法在样本合成精度方面优于其他算法。图1主要反映分类器在少数类样本上的F-value值，各个数据集通过DB_SMOTE过采样后，其F-value值均得到改善。对于三个严重不平衡数据集yeast，四种实验方案的F-value值变化较大，只有本文的实验方案F-value值均得到提高，说明在数据严重不平衡的环境下，其他采样算法并不能充分地弥补少数类样本分布信息。从九个数据集上的实验数据变化情况分析看，SMOTE、Borderline_SMOTE过采样算法并不是很稳定，它们在某些数据集上的F-value值比未采样方案还要低。从图2的G-mean值曲线也能得到相似的结论，九个数据集通过DB_SMOTE过采样后，其G-mean值相比未采样情况均能得到提升。由前文所述可知，G-mean是用来反映分类器针对两类样本综合分类情况。由图2可知，DB-SMOTE采样方案能够弥补少数类样本信息，同时又不影响多数类样本信息的表示，相比其他方案来说比较稳定。结合图表和上述分析可知，不合适的采样策略并不能明显提高分类器的相关性能，同时也说明了DB_SMOTE算法具有更好的适应性。

图1 F_value变化曲线图

图2 G-mean变化曲线图

4 结束语

针对非平衡数据学习问题，文中通过改变传统求K-近邻的方法，结合样本距离和类聚集特点提出了DB_SMOTE算法。算法的关键是提取到种子样本和构建合成样本分布函数。从实验数据分析可知，该算法能够解决非平衡数据学习问题。目前非平衡数据学习问题，主要考虑的是静态数据环境，如何解决在数据流环境下的非平衡数据学习将是研究问题之一。同时，噪声问题的处理也是非平衡数据学习问题难点。

[1]He Haibo，Garcia E A.Learning from imbalanced data[J]. IEEE Transactions on Knowledge and Data Engineering，2009，21（9）：1263-1284.

[2]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：321-357.

[3]Han H，Wan W Y，Mao B H.Borderline-SMOTE：a new over-sampling method in imbalanced data sets learning[C]// LNCS 3644：ICIC 2005，Part I，2005：878-887.

[4]He H，Bai Y，Garcia E A，et al.ADASYN：adaptive synthetic sampling approach for imbalanced learning[C]//Proc of the International Joint Conference on Neural Networks，2008：1322-1328.

[5]Jo T，Japkowicz N.Class imbalances versus small disjuncts[J].ACM SIGKDD Explorations Newsletter，2004，6（1）：40-49.

[6]程险峰，李军，李雄飞.一种基于欠采样的非平衡数据分类算法[J].计算机工程，2011，37（13）：147-149.

[7]Chawla N V，Lazarevic A，Hall L O，et al.SMOTEBoost：improving prediction of the minority class in boosting[C]// Proc of the 7th European Conf Principles and Practice of Knowledge Discovery in Databases，Cavtat-Dubrovnik，Croatia，2003：107-119.

[8]Seiffert C，Kboshgoftaar T M，Hulse J V，et al.RUSBoost：improving classification performance when training data is skewed[C]//Proc of the 19th IEEE International Conference on Pattern Recognition，Tampa，FL，USA，2008：1-4.

[9]李雄飞，李军，董元方，等.一种新的非平衡数据学习方法PCBoost[J].计算机学报，2012，35（2）：202-209.

[10]于重重，田蕊，谭励，等.非平衡样本分类的集成迁移学习算法[J].电子学报，2012（7）：1358-1364.

[11]曾志强，吴群，廖备水.一种基于核SMOTE的非平衡数据集分类方法[J].电子学报，2009（11）：2489-2496.

[12]王超学，潘正茂，董丽丽，等.基于改进SMOTE的非平衡数据集分类研究[J].计算机工程与应用，2013，49（2）：184-187.

[13]李明方，张化祥.针对不平衡数据的Bagging改进算法[J].计算机工程与应用，2013，49（2）：40-42.

[14]Orriols-Puig A，Bernado-Mansilla E.Evolutionary rulebased systems for imbalanced data sets[J].Soft Computing，2009，13（3）：213-225.

LIU Yuxia1,LIU Sanmin2，3,LIU Tao2,WANG Zhongqun4

1.College of Civil Engineering and Architecture,Anhui Polytechnic University,Wuhu,Anhui 241000,China
2.College of Computer and Information,Anhui Polytechnic University,Wuhu,Anhui 241000,China
3.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China
4.College of Management and Engineering,Anhui Polytechnic University,Wuhu,Anhui 241000,China

In order to solve the asymmetry of class distribution information in imbalanced data,DB_SMOTE（Distance-based Synthetic Minority Over-sampling Technique）algorithm is presented by minority new sample synthetic.According to the distance between sample and the centre of class,seed sample is gained by combining class aggregation.Based on SMOTE（Synthetic Minority Over-sampling Technique）,new sample is synthesized.Based upon the distance between seed sample and the centre of minority class,new sample distribution function is formed.Classification experiment results show DB_SMOTE is feasible.

imbalanced data learning;oversampling;data classification

A

TP391

10.3778/j.issn.1002-8331.1308-0099

LIU Yuxia,LIU Sanmin,LIU Tao,et al.New oversampling algorithm DB_SMOTE.Computer Engineering and Applications,2014,50（6）：92-95.

国家自然科学基金（No.61300170，No.71371012）；教育部人文社科基金（No.13YJA630098）；安徽省自然科学基金重点资助项目（No.KJ2013A040）；高校省级优秀青年人才基金重点项目（No.2013SQRL034ZD）；校青年基金（No.2013YQ31，No.2012YQ32）。

刘余霞（1980—），女，硕士研究生，研究方向：信号处理、模式识别。E-mail：guiyuxia@163.com

2013-08-09

2013-11-08

1002-8331（2014）06-0092-04