在实际应用中,需要处理的数据常常具有类别不平衡的特点.例如,用于信用卡欺诈检测、垃圾邮件过滤、机械故障诊断、疾病诊断、极端天气预测预报等的数据都是类别非平衡数据.研究非平衡数据分类问题具有重要意义和实际应用价值,引起机器学习领域研究人员的广泛关注.《非平衡数据分类理论与方法》结合作者团队在非平衡数据分类中的研究成果,系统介绍非平衡数据分类的理论基础、模型评价、数据级方法、算法级方法和集成学习方法.

第1章 理论基础
　　本章介绍后续章节要用到的理论基础.*先，介绍什么是数据分类.然后，介绍解决数据分类问题的常用方法，包括K-近邻、决策树、神经网络、极限学习机、支持向量机和分类器集成.
　　1.1 数据分类
　　数据分类是机器学习[1-3]的基本任务，为了易于理解，方便描述，假设用于机器学习的数据组织成表结构.如果数据表中包含样例的类别信息，则称这种数据表为决策表，否则称为信息表.下面先给出决策表的两种形式化定义，然后给出分类问题的定义.
　　定义1.1.1 一个决策表是一个二元组DT={(xi，yi)|xi∈U，yi∈C，1.i.n}.其中，xi表示决策表中的第i个样例，yi表示样例xi对应的类别，C是样例所属类别的集合，U是决策表中n个样例的集合.
　　定义1.1.2 一个决策表是一个四元组DT=(U，A∪C，V，f).其中，U={x1，x2， ，xn}是n个样例的集合，A={a1，a2， ，ad}是d个条件属性(或特征)集合，C是决策属性(或类别属性)，V=V1×V2× ×Vd是d个属性值域的笛卡儿积，Vi是属性ai的值域，i=1，2， ，d，f是信息函数:U×A→V.
　　决策表的这两种形式化定义实际上是等价的.在本书中，我们会交替使用这两种定义.包含n个样例的决策表的直观表示如表1.1所示.下面给出分类问题的定义.
　　定义1.1.3 给定决策表DT={(xi，yi)|xi∈U，yi∈C，1.i.n}，如果存在一个映射f:U→C，使得对于任意的xi∈U，都有yi=f(xi)成立.用给定的决策表DT寻找函数y=f(x)的问题，称为分类问题，函数y=f(x)也称为分类函数.
　　说明:
　　(1)在分类问题中，因变量y的取值范围是一个由有限个离散值构成的集合C，相当于高级程序设计语言(如C++语言)中的枚举类型.若C变为实数集R或R中的一个区间[a，b]，则这类问题称为回归问题.显然，分类问题是回归问题的特殊情况.
　　表1.1 包含n个样例的决策表
　　(2)函数y=f(x)不一定有解析表达式，可以用其他的形式，如树、图、网络来表示.
　　(3)如果所有的Vi都是实数集R，此时V=Rd.
　　(4)在机器学习中，因为求解分类问题或回归问题时，要用到样例的类别信息，所以学习分类函数或回归函数的过程是有导师学习.
　　下面举几个分类问题的例子.
　　例1.1.1(天气分类问题) 天气分类问题[2]是一个两类分类问题，用来预测什么样的天气条件适宜打网球.天气分类问题数据集是机器学习领域的一个**数据集，如表1.2所示.
　　表1.2 天气分类问题数据集
　　天气分类问题数据集有14个样例，即U={x1，x2， ，x14};4个条件属性，即A={a1，a2，a3，a4}，其中a1=Outlook，a2=Temperature，a3=Humidity，a4=Wind，它们都是离散值属性，相当于高级程序设计语言中的枚举类型属性.决策属性C={y}，y=PlayTennis，只取Yes和No两个值，所以天气分类问题是一个两类分类问题.显然，从该数据集中找到的分类函数y=f(x)不可能有解析表达式.在1.4节，我们将看到y=f(x)可用一棵树表示.
　　例1.1.2(鸢尾花分类问题) 鸢尾花分类问题[4]是一个三类分类问题，它根据花萼长(Sepal length)、花萼宽(Sepal width)、花瓣长(Petal length)和花瓣宽(Petal width)四个条件属性对鸢尾花进行分类.鸢尾花分类问题数据集Iris包含三类共150个样例，每类50个样例，如表1.3所示.
　　表1.3 鸢尾花分类问题数据集
　　Iris数据集有150个样例，即U={x1，x2， ，x150};4个条件属性，即A={a1，a2，a3，a4}，其中a1=Sepal length，a2=Sepa lwidth，a3=Petal length，a4=Petal width，它们都是连续值属性.即V=R4.决策属性C={y}，y∈{Iris-setosa，Iris-versicolor，Iris-virginica}.由于Iris数据集中的四个条件属性都是连续值属性，因此该数据集是一个连续值数据集.
　　例1.1.3(助教评估分类问题) 助教评估(teaching assistant evaluation，TAE)分类问题[4]也是一个三类分类问题.它根据母语是否是英语(A native English speaker)、课程讲师(Course instructor)、课程(Course)、是否正常学期(A regular semester)和班级规模(Class size)五个条件属性对助教评估分类.助教评估分类问题数据集包含三类151个样例，**类(Low)49个样例，第二类(Medium)50个样例，第三类(High)52个样例，如表1.4所示.
　　助教评估分类问题数据集有151个样例，即;5个条件属性，即，其中，a1=A native English speaker，a2=Course instructor，a3=Course，a4=A regular semester，a5=Class size.a1表示母语是否是英语，是一个二值属性;a2表示课程讲师，共25位课程讲师，每位课程讲师用一个符号值表示，共25个值;a3表示助教课程，共26门课程，每门课程用一个符号值表示，共26个值;a4表示是否正常学期，是一个二值属性;a5表示班级规模，是一个数值属性.显然，TAE数据集是一个混合类型数据集.
　　表1.4 助教评估分类问题数据集
　　1.2 K-近邻
　　K-近邻(K-nearestneighbors，K-NN)算法[5]是一种著名的分类算法.K-NN算法的思想非常简单，对于给定的待分类样例(也称为测试样例)x，*先在训练集中寻找距离x*近的K个样例.这K个样例就是x的K个*近邻.然后，统计这K个样例的类别，类别数*多的即x的类别.图1.1所示为K-NN算法思想示意图.
　　图1.1 K-NN算法思想示意图
　　在图1.1中，K=9，训练集由二维空间的点(样例)构成，每个点用两个属性(或特征)a1和a2描述.这些样例分成两类，正类(positive)样例用符号“+”表示，负类(negative)样例用符号“.”表示.实心的小圆是待分类样例x，大圆内的其他点是x的9个*近邻.可以看出，在x的9个*近邻中，有7个属于正类，2个属于负类，所以x被分类为正类.K-NN算法的伪代码在算法1.1中给出.
　　算法1.1:K-NN算法
　　1输入:测试样例x，训练集T={(xi，yi)|xi∈Rd，yi∈C，1.i.n}，参数K.
　　2输出:x的类标y∈C.
　　3for(i=1;i.n;i=i+1)do
　　4计算x到xi之间的距离d(x，xi);5end
　　6在训练集T中选择x的K个*近邻，构成子集N;
　　7计算y=argmaxl∈CΣx∈NI(l=class(x));
　　8//其中，I( )是特征函数.
　　9returny.
　　下面分析K-NN算法的计算时间复杂度.从算法1.1可以看出，K-NN算法的计算代价主要体现在计算x与训练集T中每一个样例之间的距离上，即算法1.1中的第3～5步.这个for循环的计算时间复杂度为O(n).显然，第6步和第7步的计算时间复杂度均为O(1).因此，K-NN算法的计算时间复杂度为O(n).
　　K-NN算法的优点是思想简单，易于编程实现.但是，K-NN算法也有如下缺点[6].
　　(1)为了分类测试样例x，需要将整个训练集T存储到内存中，空间复杂度为O(n).
　　(2)为了分类测试样例x，需要计算它到训练集T中每个样例之间的距离，计算时间复杂度为O(n).
　　(3)在K-NN算法中，训练集T中的样例被认为是同等重要的，没有考虑它们对分类测试样例x做出贡献的大小.
　　针对这些缺点，研究人员提出许多改进算法.例如，为了克服缺点(1)和(2)，一些研究人员提出近似*近邻方法和基于哈希技术的方法[7.10]，还有些研究人员提出基于层次数据结构的方法[11，12];为了克服缺点(3)，Keller等[13]提出模糊K-近邻算法.感兴趣的读者可以参考相关文献.
　　1.3 决策树
　　决策树是求解分类问题的有效算法，它既可以解决离散值分类问题，也可以解决连续值分类问题.
　　1.3.1 离散值决策树
　　ID3[14]算法是著名的决策树算法，用于解决离散值(或符号值)分类问题.符号值分类问题指决策表中条件属性是离散值属性的分类问题.属性的取值是一些符号值.因为ID3算法用树描述从决策表中挖掘出的决策(分类)规则，所以称这种树为决策树.
　　决策树的叶子结点是决策属性的取值(类别值)，内部结点是条件属性，分支是条件属性的取值.例如，表1.2是一个有关天气分类问题的符号值决策表，图1.2是用ID3算法生成的决策树.这棵树共有5个叶子结点(用椭圆框表示)，它们是决策属性PlayTennis的取值(Yes或No);共有3个内部结点(用矩形框表示)，即Outlook、Humidity和Wind.其中，Outlook是这棵树的根结点，有3个孩子结点，即Sunny、Cloudy和Rain，它们是条件属性Outlook的取值.条件属性Humidity和Wind各有两个值，它们各自有两个孩子结点.下面介绍ID3算法.
　　图1.2 由表1.2用ID3算法生成的决策树
　　ID3算法是一种贪心算法，它用信息增益作为贪心选择标准(也称启发式)来选择树的根结点(也称扩展属性)，递归地构建决策树.ID3算法的输入是一个离散值属性决策表，输出是一棵表示规则的决策树.在介绍ID3算法之前，先介绍相关的概念.
　　给定离散值属性决策表DT=(U，A∪C，V，f)，设U={x1，x2， ，xn}，A={a1，a2， ，ad}，即决策表DT包含n个样例，每个样例用d个属性描述.又假设决策表中的样例分为k类，即C1，C2， ，Ck.Ci中包含的样例数用|Ci|表示，1.i.k.第i类样例所占的比例用pi=|Ci|n表示.
　　定义1.3.1 给定离散值属性决策表DT=(U，A∪C，V，f)，集合U的信息熵定义为

目录
“信息科学技术学术著作丛书”序
前言
第1章 理论基础1
1.1 数据分类1
1.2 K-近邻4
1.3 决策树5
1.3.1 离散值决策树6
1.3.2 连续值决策树19
1.4 神经网络25
1.4.1 神经元模型25
1.4.2 梯度下降算法26
1.4.3 多层感知器模型29
1.4.4 卷积神经网络33
1.5 极限学习机43
1.6 支持向量机46
1.6.1 线性可分支持向量机46
1.6.2 近似线性可分支持向量机50
1.6.3 线性不可分支持向量机51
1.7 集成学习54
1.7.1 集成学习简介54
1.7.2 Bagging算法55
1.7.3 Boosting算法56
1.7.4 随机森林算法57
1.7.5 模糊积分集成算法60
第2章 模型评价63
2.1 基本度量63
2.2 ROC*线与AUC面积65
2.2.1 ROC*线65
2.2.2 AUC面积68
2.3 损失函数71
2.4 偏差与方差80
2.5 多样性度量81
2.5.1 成对多样性度量82
2.5.2 非成对多样性度量83
2.5.3 分类器集成的多样性和分类精度之间的关系85
第3章 数据级方法86
3.1 数据级方法概述86
3.2 SMOTE算法88
3.3 B-SMOTE算法89
3.4 基于生成模型上采样的两类非平衡数据分类算法89
3.4.1 基于极限学习机自动编码器的上采样算法91
3.4.2 基于生成对抗网络的上采样算法93
3.4.3 算法实现及与其他算法的比较98
3.5 基于自适应聚类和模糊数据约简下采样的两类非平衡大数据分类算法109
3.5.1 大数据概述109
3.5.2 大数据处理系统110
3.5.3 聚类分析127
3.5.4 两类非平衡大数据分类算法134
3.5.5 算法实现及与其他算法的比较138
第4章 算法级方法144
4.1 算法级方法概述144
4.2 基于代价敏感性学习的非平衡数据分类方法146
4.2.1 代价敏感性学习基础146
4.2.2 代价敏感性支持向量机151
4.2.3 代价敏感Boosting算法151
4.3 基于深度学习的非平衡图像数据分类方法153
4.3.1 针对非平衡图像数据的深度表示学习153
4.3.2 针对长尾识别的目标监督对比学习156
4.3.3 针对长尾识别的深度嵌入和数据增广学习方法159
第5章 集成学习方法163
5.1 集成学习方法概述163
5.2 SMOTEBoost算法与SMOTEBagging算法164
5.3 基于改进D2 GAN上采样和分类器融合的两类非平衡数据分类166
5.3.1 基于改进D2 GAN的上采样方法166
5.3.2 基于改进D2 GAN上采样和分类器融合的两类非平衡数据分类169
5.3.3 算法实现及与其他算法的比较172
5.4 基于MapReduce和极限学习机集成的两类非平衡大数据分类179
5.4.1 交替上采样方法179
5.4.2 基于交替上采样和集成学习的两类非平衡大数据分类180
5.4.3 算法实现及与其他算法的比较182
5.5 基于异类*近邻超球上采样和集成学习的两类非平衡大数据分类186
5.5.1 基于MapReduce和异类*近邻超球的上采样186
5.5.2 基于异类*近邻超球上采样和模糊积分集成的两类非平衡大数据分类188
5.5.3 算法实现及与其他算法的比较188
参考文献194