编辑推荐

《类别不平衡学习：理论与算法》首先系统地介绍了与类别不平衡学习相关的一些基础概念及理论，并进而在上述理论的基础上，讨论了一些主流的类别不平衡学习技术及对应算法，具体包括样本采样技术、代价敏感学习技术、决策输出补偿技术、集成学习技术、主动学习技术及一类分类技术等。此外，也探讨了类别不平衡分布的危害预评估技术。最后，对该领域未来的发展方向及应用前景作出了评述与展望。

内容简介

类别不平衡学习是机器学习与数据挖掘领域的重要分支之一，其在很多应用领域中均发挥着重要作用。《类别不平衡学习：理论与算法》首先系统地介绍了与类别不平衡学习相关的一些基础概念及理论(第1、2章)，进而在上述理论的基础上，讨论了一些主流的类别不平衡学习技术及对应算法，具体包括样本采样技术(第3章)、代价敏感学习技术(第4章)、决策输出补偿技术(第5章)、集成学习技术(第6章)、主动学习技术(第7章)及一类分类技术(第8章)等。此外，也探讨了样本不平衡分布的危害预评估技术(第9章)。最后，对该领域未来的发展方向及应用前景做出了评述与展望(第10章)。
《类别不平衡学习：理论与算法》可作为高等院校与研究院所计算机、自动化及相关专业研究生的课外阅读书籍，也可供对机器学习及数据挖掘感兴趣的研究人员和工程技术人员阅读参考。

目录

第1章绪论
1.1引言
1.2基本概念
1.3常用技术
1.4应用领域
1.5《类别不平衡学习：理论与算法》主要内容及安排
1.6文献导读
参考文献
第2章基础理论
2.1类别不平衡分布对传统分类器性能的影响机理
2.1.1类别不平衡分布对朴素贝叶斯分类器的影响
2.1.2类别不平衡分布对支持向量机的影响
2.1.3类别不平衡分布对极限学习机的影响
2.2类别不平衡学习的影响因素
2.3类别不平衡学习的性能评价测度
2.4本章小结
2.5文献导读
参考文献
第3章样本采样技术
3.1样本采样技术的基本思想及发展历程
3.2随机采样技术
3.2.1随机降采样法
3.2.2随机过采样法
3.3人工采样技术
3.3.1SMOTE采样法
3.3.2BorderlineSMOTE采样法
3.3.3ADASYN采样法
3.3.4OSS采样法
3.3.5SBC采样法
3.4优化采样技术
3.5实验结果及讨论
3.5.1数据集描述及参数设置
3.5.2结果与讨论
3.6本章小结
3.7文献导读
参考文献
第4章代价敏感学习技术
4.1代价敏感学习的基本思想
4.2代价矩阵
4.3基于经验加权的代价敏感学习算法
4.3.1CSSVM算法
4.3.2WELM算法
4.4基于模糊加权的代价敏感学习算法
4.4.1FSVMCIL算法
4.4.2FWELM算法
4.5实验结果与讨论
4.5.1数据集与参数设置
4.5.2结果与讨论
4.6本章小结
4.7文献导读
参考文献
第5章决策输出补偿技术
5.1决策输出补偿技术的基本思想
5.2基于经验的决策输出补偿算法
5.3基于关键位置比对的决策输出补偿算法
5.4基于优化思想的决策输出补偿算法
5.5实验结果与讨论
5.5.1实验一
5.5.2实验二
5.6本章小结
5.7文献导读
参考文献
第6章集成学习技术
6.1集成学习的基本思想
6.2两种经典的集成学习范式
6.2.1Bagging集成学习范式
6.2.2Boosting集成学习范式
6.3基于样本采样技术的集成学习算法
6.3.1AssymetricBagging及asBaggingFSS算法
6.3.2SMOTEBoost及RUSBoost算法
6.3.3EasyEnsemble及BalanceCascade算法
6.4基于代价敏感学习技术的集成学习算法
6.5基于决策输出补偿技术的集成学习算法
6.6实验结果与讨论
6.6.1实验一
6.6.2实验二
6.6.3实验三
6.7本章小结
6.8文献导读
参考文献
第7章主动学习技术
7.1主动学习的基本思想
7.2基于支持向量机的主动不平衡学习算法
7.3样本不平衡分布中的主动学习算法设计
7.4实验结果与讨论
7.4.1实验一
7.4.2实验二
7.5本章小结
7.6文献导读
参考文献
第8章一类分类技术
8.1一类分类的基本思想
8.2基于密度的一类分类器
8.2.1基于高斯模型的一类分类器
8.2.2基于高斯混合模型的一类分类器
8.2.3基于Parzen窗的一类分类器
8.2.4基于K近邻的一类分类器
8.3基于支持域的一类分类器
8.3.1一类支持向量机
8.3.2支持向量数据描述
8.4一类极限学习机
8.5实验结果与讨论
8.5.1数据集与参数设置
8.5.2结果与讨论
8.6本章小结
8.7文献导读
参考文献
第9章样本不平衡分布的危害预评估技术
9.1预评估的必要性说明
9.2基于样本几何可分测度的预评估算法
9.3基于留一交叉验证的预评估算法
9.4实验结果与讨论
9.4.1实验一
9.4.2实验二
9.5本章小结
9.6文献导读
参考文献
第10章未来研究展望
10.1现有的挑战
10.2未来的研究方向与发展前景
10.3文献导读
参考文献

精彩书摘

第3章样本采样技术
3.1样本采样技术的基本思想及发展历程
3.2随机采样技术
3.3人工采样技术
3.4优化采样技术
3.5实验结果及讨论
3.6本章小结
3.7文献导读
参考文献
3.1样本采样技术的基本思想及发展历程
如前所述采样技术是一种数据层的处理方法，它通过修正数据集的方式来平衡训练样本的类分布，以达到修复分类结果的目的。严格来讲，采样可被视作一种数据预处理技术，其最为突出的优点即是与后期选用何种分类算法无关。实际上，因其简便性，采样也是在类别不平衡学习领域中应用最为广泛的一项技术，在面向实际应用问题时，人们首先会考虑采用此技术。
根据采样时所针对样本类别的不同，样本采样技术可大致分为以下三类：①降采样技术，该技术针对的是多数类样本，通过删除该类中部分样本的方式来达成训练集的类分布平衡；②过采样技术，该技术针对的是少数类样本，通过为此类补充一定样本的方式来谋求训练集的平衡；③混合采样技术，该技术针对的是每类样本，即通过结合过采样与降采样的方式来寻求训练集平衡，对于极端不平衡的数据而言，此类技术通常较为有效［1］。
在样本采样技术中，还有一个较为重要的概念，那就是采样率(samplingrate,SR)。假设某二类不平衡样本集中共有N个训练样本，其中包括N+个少数类样本与N-个多数类样本，N=N++N-。则对于过采样而言，其需生成的少数类样本为N+×SR个，而对于降采样而言，其需移除的多数类样本则为N-×SR/(SR+1)个。特别需要指明的是，SR的取值范围通常在(0,IR-1］之间，当SR=IR-1时，可保证采样后的样本集达到完全平衡，即N+=N-。
接下来回顾一下样本采样技术的发展史。可以说，自20世纪90年代末起，样本采样技术一共经历了以下三个主要的发展阶段：
第一阶段(1997—2001年)：在该阶段，随机采样技术开始流行，人们尝试去初步探索了类别不平衡问题的本质，并观察到了样本采样技术的有效性。
第二阶段(2002—2008年)：在这一阶段，随机采样技术的缺点被发现并不断放大，取而代之的是人工采样技术。人工采样技术既可在一定程度上缓解随机降采样所带来的重要分类信息缺失问题，又可以避免随机过采样所导致的过适应问题。
第三阶段(2009年至今)：在这一阶段，一些更为复杂的样本采样算法被陆续提出，人们开始注意到优化算法及集成学习算法在克服传统采样算法弱点方面的优势，同时也注意到在采样时保持样本原始分布的重要性。
下面，将分别从上述三个发展阶段，选出一些有代表性的样本采样算法，对其核心思想、算法流程及优缺点做详细说明与评述。
3.2随机采样技术
随机采样是最为简单也是应用最为广泛的一类采样技术，主要分为以下两个类别：随机降采样(randomundersampling,RUS)及随机过采样(randomoversampling,ROS)。其中，前者通过随机移除一定数量的多数类样本来缓解类分布不均衡的影响，而后者则通过简单复制少数类样本的方式来达成不同类在训练样本规模上的平衡。下面将分别对上述两类算法的流程及特点进行简要介绍。
3.2.1随机降采样法
随机降采样法，即RUS算法的基本思想是随机地移除一定数量或比例的多数类样本，以达到训练样本集的平衡。RUS算法的基本流程如下。
算法31：RUS算法
输入：训练集S={(xi,yi),i=1,2,…,N,yi∈{+,－}}；多数类样本数N-，少数类样本数N+，其中，N-+N+=N；不平衡比率IR=N-/N+；采样率SR。
输出：降采样后的训练集S′={(xi,yi),i=1,2,…,N－N－×SR/(SR+1),yi∈{+,－}}。
算法步骤：
1.从训练集S中取出全部多数类与少数类样本，组成多数类训练样本集S-及少数类训练样本集S+；
2.Fori=1:N-×SR/(SR+1)
2.1在1~(N--i+1)之间随机选择一个数字，于S-中找到对应的样本x′；
2.2在多数类样本集中移除2.1步所选出的样本，S-=S--x′；
End
3.得到降采样后的训练集S′=S-∪S+。
从上述算法流程不难看出，经过RUS算法处理过的训练集在样本规模上大幅减小了，且由于样本移除的随机性，这一算法的时间复杂度是相对较低的。然而，也正是由于对多数类样本不加以区别地进行移除，可能会造成较多的分类信息损失，从而导致后期建模的分类器质量不高。一般而言，当IR值较低，即类别不平衡问题不是非常严重时，RUS算法的效果通常较好，而当IR值较高时，即对于极度不平衡的分类问题，RUS算法的性能则往往不可控，且有较大概率获得较差的分类结果。图31给出了一个简单的示例，训练集中的多数类与少数类样本分别为100∶50与100∶5，即IR值分别为2及20，且保持SR=IR-1时，分别两次调用RUS算法，所得到的训练样本分布情况。
图31不同IR值下两次随机调用RUS算法的训练样本分布
(a1)IR=2的原始训练样本分布；(a2)IR=2的第1次随机降采样样本分布；(a3)IR=2的第2次随机降采样样本分布；(b1)IR=20的原始训练样本分布；(b2)IR=20的第1次随机降采样样本分布；(b3)IR=20的第2次随机降采样样本分布
从图31不难看出，当IR值较低时，采用RUS算法降采样后仍能很好地保留原始的多数类样本分布信息，从而保证后期所训练的分类器能得到稳定的分类性能；而当IR值较高时，由于少数类样本稀缺，导致每次调用RUS算法所得到的多数类样本均存在较大差异，原始分布信息几乎完全丢失，分类性能的稳定性也就无从谈起。
实际上，在早期的一些应用中，人们已经开始注意到了类别不平衡分布对分类性能的负面影响，并开发了一种样本集的人工划分方法［3,4］(见图32)。该方法将整个样本集划分为一个平衡的训练集与一个不平衡的测试集，由于分类器是在训练集上学习得到，故能保证其分类结果的公正性。严格来讲，人工划分法也可被视为RUS法的一种扩展，即训练集是对原始样本集做随机降采样而得到，只不过，在该方法中，随机降采样并不仅仅针对多数类，同时也针对少数类。人工划分法尽管有效，但并不合理，因为它假设测试集在训练前便是存在的，而这与实际应用情况并不相符。
图32人工划分法示意图
3.2.2随机过采样法
随机过采样法，即ROS算法的基本思想是随机地抽取少数类样本并进行多次复制，从而达到增加少数类样本，平衡训练集类别分布的目的，其基本流程如下。
算法32：ROS算法
输入：训练集S={(xi,yi),i=1,2,…,N,yi∈{+,－}}；多数类样本数N-，少数类样本数N+，其中，N-+N+=N；不平衡比率IR=N-/N+；采样率SR。
输出：过采样后的训练集S′={(xi,yi),i=1,2,…,N+N+×SR,yi∈{+,－}}。
算法步骤：
1.从训练集S中取出全部多数类与少数类样本，组成多数类训练样本集S-及少数类训练样本集S+；
2.Fori=1:N+×SR
2.1在1~N+之间随机选择一个数字，于S+中找到对应的样本x′；
2.2在少数类样本集中添加2.1步所选出的样本，S+=S+∪x′；
End
3.得到过采样后的训练集S′=S-∪S+。
显然，由于没有移除任一样本，故与RUS算法相比，ROS算法能有效克服其重要分类信息缺失的问题。但是，ROS算法也有其固有的缺点：一是由于增加了大量的样本，扩充了训练样本集，故将不可避免地在后期增加分类器的训练时间开销；二是由于仅是对少数类样本进行复制，必然会造成各少数类样本在样本空间的“叠加”效应，这就导致分类器难以学习到一个分布，而是趋向于逼近一些离散的样本点，从而出现过适应的现象。
3.3人工采样技术
针对随机采样技术的缺点，人们陆续开发出了一些更为高级的采样算法，这类算法均或多或少地利用了样本的局部先验分布信息，并利用这些信息，通过人工干预的方式来移除少数类样本或添加人工合成的多数类样本，从而达到了提升分类性能的目的。在此，我们将此类算法统称为“人工采样技术”。下面将对此类技术中最具代表性的五种算法做展开介绍。
3.3.1SMOTE采样法
SMOTE(syntheticminorityoversamplingtechnique)算法于2002年为Chawla等人所提出，主要用于解决ROS采样法易于陷入过适应的问题［5］。不同于ROS算法，SMOTE算法不再简单地复制少数类样本，而是通过一定策略生成大量新样本的方式来谋求训练样本集类分布的平衡。当然，为了保证样本原始分布不被严重破坏，必须确定某种规则来保证新生成样本的合理性。一般而言，抛除噪声的因素不谈，我们所常见的样本集在属性空间中往往都存在以下特性：某类样本往往趋于出现在同类样本附近，即同类样本的邻域区间当中。SMOTE算法即以上述经验为准则，在原有少数类样本的邻域空间中填充新样本。在SMOTE算法中，邻域空间的确定采用了最为简单的K近邻法，即首先在少数类样本中随机选择一个主样本x，然后在剩余全部少数类样本中找到它的K近邻样本，从中随机选取一个主近邻样本x′，进而在主样本x与其主近邻样本x′的连接线的某个随机位置上生成新样本。新样本的生成过程如图33所示。
图33SMOTE算法中，一个新样本的生成图示
(a)找到主样本x的同类K近邻样本(在此例中，K=5)；(b)新样本生成
注：★表示少数类样本；●表示多数类样本
从图33中不难看出,采用SMOTE算法所新生成的样本往往都出现在少数类的决策空间内，从而足以保证其合理性。此外，新生成的样本与原始样本不再是简单的覆盖关系，这就可以保证经SMOTE算法处理后的训练集可近似逼近原始少数类样本训练集的分布，从而在一定程度上避免后期所训练的分类器出现过适应的现象。SMOTE算法的基本流程如下。
算法33：SMOTE算法
输入：训练集S={(xi,yi),i=1,2,…,N,yi∈{+,－}}；多数类样本数N-，少数类样本数N+，其中，N-+N+=N；不平衡比率IR=N-/N+；采样率SR；近邻参数K。
输出：过采样后的训练集S′={(xi,yi),i=1,2,…,N+N+×SR,yi∈{+,－}}。
算法步骤：
1.从训练集S中取出全部多数类与少数类样本，组成多数类训练样本集S-及少数类训练样本集S+；
2.置新生成样本集SNew为空;
3.Fori=1:N+×SR
3.1在1~N+之间随机选择一个数字，于S+中找到对应的主样本x；
3.2在S+中找到主样本x的K近邻样本，并将其置于近邻样本集SNer中；
3.3在1~K之间随机选择一个数字，并在SNer中找到对应的主近邻样本x′；
3.4通过下式计算得到新少数类样本xnew:xnew=x+rand×(x′-x)，其中，rand∈［0,1］；
3.5添加xnew至SNew，SNew=SNew∪xnew；
3.6置近邻样本集SNer为空；
End
4.得到过采样后的训练集S′=S∪SNew。
特别需要说明的是，近邻参数K在SMOTE算法中是最为重要的一个参数，其设置得合理与否将直接影响到最终的分类性能，通常情况下，K取值为5。此外，尽管SMOTE算法有诸多优点，但也存在三个不可回避的缺点：
图34SMOTE算法中噪声
信息的传播
①由于涉及大量的近邻关系运算，其时间复杂度过高；②当少数类样本中含有较多噪声信息时，SMOTE算法会受其干扰，将噪声信息进一步传播，从而影响到分类的性能(见图34)；③由于每轮主样本的选取是完全随机的，故当少数类样本数较少时，可能会造成各原始少数类样本被选作主样本的频次差较大，从而偏离原始的样本分布。
3.3.2BorderlineSMOTE采样法
Han等人［6］注意到对分类面起决定作用的往往是那些处于分类边界上的样本，即处于类重叠区域或在这一区域附近的样本，因此，他们认为在全部少数类样本上运行SMOTE算法是没有必要的，只需要在边界区域生成新的少数类样本即可。他们所提出的改进算法为BorderlineSMOTE算法，即边界线SMOTE算法。
在BorderlineSMOTE算法中，少数类样本被归为以下互不相交的三类：①安全样本，即远离边界区域，且处于少数类决策区域的样本；②边界样本，即处于决策边界附近的样本；③噪声样本，即远离边界区域，且处于多数类决策区域的样本。BorderlineSMOTE算法给出了这三类样本的确定条件：首先，在整个训练集S上确定每个少数类样本x+i（i=1,2,…,N+）的K近邻，其中，多数类近邻数记为Nmaj，若有：①NmajNmaj≥K/2，则表明该样本的少数类近邻少于多数类近邻，该样本很可能处于决策边
图35安全、噪声及边界样本
判别示例图
界附近，将其保留到一个命名为DANGER的样本集中；③Nmaj=K，则表明该样本的全部近邻样本均来自于多数类，极有可能处于多数类决策区域，应将其视为噪声样本，需移除。图35给出了上述三类样本的判别示例。
在经过上述判别操作后，仅对DANGER集中保留的少数类样本进行SMOTE操作即可，所生成的新样本均处于决策边界附近。特别地，BorderlineSMOTE算法有两个不同的版本，可分别将其命名为BSO1算法及BSO2算法，它们的具体流程分别描述如下。
算法34：BSO1算法
输入：训练集S={(xi,yi),i=1,2,…,N,yi∈{+,－}}；多数类样本数N-，少数类样本数N+，其中，N-+N+=N；不平衡比率IR=N-/N+；采样率SR；近邻参数K。
输出：过采样后的训练集S′={(xi,yi),i=1,2,…,N+N+×SR,yi∈{+,－}}。
算法步骤：
1.从训练集S中取出全部多数类与少数类样本，组成多数类训练样本集S-及少数类训练样本集S+；
2.置DANGER集为空；
3.置新生成样本集SNew为空;
4.Fori=1:N+
4.1在S+中找到对应样本xi；
4.2在S中找到xi的K近邻，记录其多数类近邻数为Nmaj；
4.3若K>Nmaj≥K/2，则将xi加入DANGER，即DANGER=DANGER∪xi；
End
5.Fori=1:N+×SR
5.1在DANGER集中随机选出一个主样本x；
5.2在S+中找到主样本x的K近邻样本，并将其置于近邻样本集SNer中；
5.3在1~K之间随机选择一个数字，并在SNer中找到对应的主近邻样本x′；
5.4通过下式计算得到新少数类样本xnew:xnew=x+rand×(x′-x)，其中，rand∈［0,1］；
5.5添加xnew至SNew，SNew=SNew∪xnew；
5.6置近邻样本集SNer为空；
End
6.得到过采样后的训练集S′=S∪SNew。
……

前言/序言

随着数据生成与收集技术的快速发展，如今每天在各行各业的服务器中都会新增海量的数据，这就迫使我们不得不大跨步地迈入“大数据”时代。在很多领域(尤其是商业和科研领域)的从业人员眼中，大数据犹如一座未开采的宝矿，内中裹有取之不尽的财富。而机器学习与数据挖掘技术就是那柄能开山凿路、攫取财富的“利剑”。
近年来，在产业界与学术界的双重关注下，机器学习与数据挖掘技术得到了飞速的发展，且在不断面向新应用与新挑战时，衍生出众多的新分支。类别不平衡学习便是这众多分支之一，其在机器学习与数据挖掘领域备受瞩目，很多业内主流的会议与期刊都曾以此为题举办过专刊或研讨会，如AAAI00，ICML03,ACMSIGKDDExplorationsNewsletter04以及PAKDD09等。在ICDM05会议上，类别不平衡问题更是被列为数据挖掘领域待解决的十大挑战性难题之一。
所谓类别不平衡问题，顾名思义，即数据集中存在某一类样本，其数量远多于或远少于其他类样本，从而导致传统的分类模型失效的问题。通常，将用于解决上述问题的算法称为类别不平衡学习算法。类别不平衡学习有着较为广阔的应用范围，如文本分类、网络入侵检测、信用卡欺诈检测、工业故障检测、软件缺陷检测、石油泄漏检测、医学诊断、药物筛选及生物信息学等。故对这一技术展开深入研究不但具有理论意义，而且还有着广泛的应用价值。
《类别不平衡学习：理论与算法》主要对类别不平衡学习的基本概念、基础理论及主流技术与算法展开介绍。《类别不平衡学习：理论与算法》共10章，大体上可分为以下3个部分：第1部分包括第1，2章，介绍类别不平衡的基本概念和基础理论；第2部分包括第3～9章，主要介绍一些用于解决类别不平衡问题的基础技术与前沿算法；第3部分为第10章，从笔者的视角对该技术未来的发展方向和应用前景做出了评述与展望。特别需要说明的是，由于此领域文献众多，初入此领域者难免会有该选读何种文献的困惑，故笔者已将一些重要及经典的文献列出，并加以说明，置于每章后面的文献导读部分。
在此，向那些为《类别不平衡学习：理论与算法》出版工作提供帮助的人表达谢意。首先，感谢东南大学自动化学院的博士后合作导师孙长银教授，在东南大学做博士后的几年时间里，孙老师给了我充分的自由度，使我能安心于自己的研究课题，《类别不平衡学习：理论与算法》很多内容都是在这段时间研究完成的。此外，江苏科技大学的高尚教授、杨习贝副教授、王平心副教授、左欣副教授、邵长斌、郑尚、秦斌、徐丹、鞠恒荣、洪淑芳、袁玉龙、杨菊、李青雯、席晓燕，东南大学的杨万扣副教授、刘金花、姚乔兵，天津大学的穆朝絮老师以及美国爱荷华大学的倪军副教授等均在《类别不平衡学习：理论与算法》出版过程中给予了支持与帮助，在此一并表示感谢。
其次，感谢国家自然科学基金(No.61305058)、江苏省自然科学基金(No.BK20130471)、国家博士后特别资助计划项目(No.2015T80481)、国家博士后基金(No.2013M540404)、江苏省博士后基金(No.1401037B)、江苏省教育厅高等学校自然科学研究项目(No.12KJB520003)及江苏科技大学“深蓝学者”计划培养基金对本课题研究工作及《类别不平衡学习：理论与算法》出版工作所提供的经费支持。
笔者深知自己才疏学浅，对类别不平衡学习技术仅可做到管中窥豹，且鉴于时间与精力有限，成稿仓促，书中难免会有错误与疏漏之处，望读者不吝指出，笔者将不胜感激。
笔者于江苏科技大学


其他推荐