第2章 基础理论

2.1 类别不平衡分布对传统分类器性能的影响机理

在第1章中，已经以样本分布图的形式为读者直观地呈现了类别不平衡分布的负面影响。然而，读者可能仍不清楚其对各传统分类器性能的影响机理。在本章中，将分别以朴素贝叶斯、支持向量机及极限学习机这三种常用的分类器为例，从其各自的独特构造出发，在理论上分析类别不平衡分布对它们性能的影响机理，从而使读者能对类别不平衡分布的危害有更加深刻的认识。

2.1.1 类别不平衡分布对朴素贝叶斯分类器的影响

众所周知，朴素贝叶斯分类器是提出较早且应用较为广泛的一种分类模型。该模型具有较强的理论基础，主要理论依据为贝叶斯定理及特征条件独立假设理论[1]。

假设用于分类建模的训练集共包括N个样本x1, x2, …, xN，且这些样本可被划分为互不相交的M个类别c1, c2, …, cM，则对于一个新样本x，根据贝叶斯决策理论，其隶属于类别ci的概率可由下式求得

其中，P（ci|x）为后验概率，表示样本x被划分为类别ci的可能性；P（ci）为先验概率，它表示在全部训练样本中，类标为ci的样本所占的比例；P（x|ci）则被称为类条件概率，即统计归属于类别ci的样本中，与x具有相同属性取值的样本比例；P（x）是用于归一化的证据因子，即统计整个训练集中所出现的与x具有相同属性取值的样本比例。

显然，只要给定一个训练集，先验概率、类条件概率及证据因子均可直接统计得到，代入式（2-1）即可计算得出最终的后验概率。计算样本x隶属于每一类的后验概率，再通过下式即可判定其归属类别：

也就是将样本x判归为能使其后验概率最大的类别。

在贝叶斯判别规则中，还有一个需要关注的问题，即类条件概率P（x|ci）的计算问题。考虑到对于绝大多数的分类问题而言，其样本通常都包含不止一个属性，在此情况下，则显然类条件概率P（x|ci）应被分解为多个属性的联合概率，若训练样本有限，那么就会导致P（x| ci）在其分布区间中的大部分位置取值为零，这显然是不合理的，因为“未被观测到”和“出现概率为零”是截然不同的两个概念[2]。另外，样本中各属性的取值也未必都是离散的，对于取值为连续区间的属性而言，频率更是难以通过“查数”来统计得出。对于上述问题，贝叶斯决策理论通常是采用极大似然估计法来解决的。采用该方法，可近似估计得出属性空间中的概率密度分布，再用对应点的概率密度来近似替代类条件概率P（x|ci）的估计值。

那么，若样本的分布是类别不平衡的，它是否会对贝叶斯决策的结果造成影响呢？若有影响，这种影响又会是正面还是负面的呢？为回答上述问题，不妨以一个简单的例子来加以说明。不失一般性，假设待分类问题为二类不平衡问题，其中少数类为正类，类标表示为c+，多数类为负类，其类标用c-来表示，每个样本只含有一个属性x，且两类样本在该属性上均服从正态高斯分布（见图2-1）。由于先验概率P（c+）, P（c-）及类条件概率P（x|c+）, P（x|c-）均已知，则可调用贝叶斯公式，计算得出其后验概率，分别为

显然，当分类边界出现在两类后验概率相等位置时，即P（c+|x）=P（c-|x），也就是P（x|c+）P（c+）=P（x|c-）P（c-）时，分类器的经验风险将会达到最小化。从图2-1可看出，若训练集中的样本是类别平衡的，即两类具有相等的先验概率P（c+）=P（c-），则分类边界应出现在两类类条件概率相等的位置，即图2-1中最优边界的位置。而若训练集是类别分布不平衡的，即P（c+）＜P（c-），则为了保证后验概率相等，即P（x|c+）P（c+）=P（x|c-）P（c-），分类边界将必然会出现在一个少数类的类条件概率高于多数类的类条件概率的位置，如图2-1中实际边界的位置。显然，实际的分类边界偏离了最优边界的位置，它被更多地推向了少数类所在的区域。

基于上述理论解释，则不难回答前面的两个问题，即贝叶斯决策的结果会受到样本类别不平衡分布的影响，且这种影响是负面的。从图2-1中也可以看出，两类样本的重叠程度越高，类别不平衡比率越大，则分类边界的偏离度也将越大。关于这些影响因素，将在2.2节展开讨论。

2.1.2 类别不平衡分布对支持向量机的影响

支持向量机（support vector machine, SVM）为Vapnik于1995年提出[3]，在2000年前后迅速发展成为机器学习领域的热点技术之一。不同于传统的分类算法，支持向量机不再以经验风险最小化为训练目标，转而追求结构风险最小化。所谓结构风险最小化，可以通过图2-2中的例子加以解释。

从图2-2中可以看出，这是一个典型的二分类问题，利用这两类样本进行分类器建模，可以得到无数分类面，并可保证这些分类面的训练精度均为百分之百。图2-2中为大家展示了上述分类面中的三个，可分别标记为H1, H2及H3。那么，究竟哪个分类面更好呢？从直观上看，显然H2的视觉效果要更好一些，因为它与两类边界样本的距离是相同的，且在它的垂直方向上，两类样本间存在最大的间隔，这就能保证其对训练样本的局部扰动具有最强的容忍度，也可以说它有最强的泛化能力。故若采用0-1损失函数作为分类器建模的度量标准，上述三个分类面均可保证经验风险最小化，而若考虑结构风险最小化，分类面H2无疑是唯一选择。

支持向量机建模的目标就是要在样本空间中找到那个能使结构风险达到最小化的分类面。这个分类面可通过如下的线性方程来描述：

其中，w为法向量，它决定了分类超平面的方向；b表示位移项，其决定了分类超平面与原点间的距离。显然，任一分类超平面的位置均可由其法向量w及位移项b唯一确定。样本空间中任意样本x到超平面的距离可由下式计算：

若超平面可将全部训练样本均正确分类，即对于训练集中任一样本（xi, yi），若yi=+1，则有wTxi+b＞0；若yi=-1，则有wTxi+b＜0。此时，可令

如图2-3所示，距离超平面最近的几个圈起来的训练样本点可使式（2-6）的等号成立，我们通常将它们称为“支持向量”（support vector）。显然，两个异类支持向量到超平面的距离之和为

该距离被称为“间隔”（margin）。

支持向量机的目的就是要找到那个具有最大间隔的分类面，也就是要找到对应的约束参数w和b，使得2/‖w‖最大。要使2/‖w‖最大，实际上就是要使‖w‖最小，于是待解的优化式可以写为如下形式：

上述优化式是一个典型的二次规划问题，可以通过拉格朗日乘子法求解。

前面仅仅考虑了训练样本线性可分的情况，然而在实际应用中，这种情况并不常出现。若训练样本在样本空间中线性不可分，则可考虑采用核方法将样本映射到线性可分的高维空间，再对分类面进行求解。核函数可表示为如下形式：

同时，为了避免分类间隔过小，从而降低分类器的泛化性能，可考虑令部分训练样本不满足约束式（2-6），这可通过在优化式中加入“惩罚因子”C来实现，则式（2-8）可被改写为

其中，ξi称为“松弛因子”，用来表示其不满足约束式yi（＜w, ϕ（xi）＞+b≥1的程度。通过拉格朗日乘子法，式（2-10）的对偶形式可被写为如下形式，并进行求解：

观察式（2-11）可以发现，任一样本的拉格朗日乘子项系数αi均对应如下三类情况之一：

情况1:αi=0，这意味着对应样本能被正确分类，且位于间隔线外。

情况2:0＜αi＜C，这意味着对应样本位于间隔线上，也就是支持向量。

情况3:αi=C，这意味着对应样本位于两条间隔线之间，能否被正确分类是未知的。

下面考虑类别不平衡问题，假设N个训练样本可被划分为两类，其中少数类样本数为N+，多数类样本数为N-，显然有N+＜N-，且有N++N-=N。此外，分别采用及表示两类样本中的支持向量个数，及来表示两类样本中被置于间隔区域中的样本数。则根据式（2-11），显然有

由于αi的取值至多为C，故可推得如下两个不等式：

通过整合式（2-14）及式（2-15），可得

同理可得

在此，不妨令，式（2-16）及式（2-17）分别除以N+×C及N-×C，则可得

从式（2-18）和式（2-19）中可以看出，/N +及/N -分别表示两类样本中位于间隔区域的样本比例，由于间隔区域中样本的预测类标不可控，故上述两个指标也可分别看做是对两类训练样本错误率的一种近似。又由于有N+＜N-，故显然有M/（N+×C）＞M/（N-×C），即表明正类（少数类）错误率的上限要高于负类（多数类）错误率的上限。由此，不难得出如下结论：支持向量机的训练结果会受到样本类别分布不平衡的影响，且这种影响是负面的。此外，也可看出：两类样本的训练样本数差别越大，则其对应的错误率上限的差别也将越大，负面影响的效果也越大。实际上，由于SVM的分类面仅与少量的支持向量有关，故其与其他分类器相比，受类别不平衡分布的影响要相对小得多。

2.1.3 类别不平衡分布对极限学习机的影响

极限学习机（extreme learning machine, ELM）由南洋理工大学的Huang等人[4]于2006年正式提出，经过近十年的发展，已经成为机器学习领域的研究热点之一。不同于传统的误差反传（back-propagation, BP）算法[5]，极限学习机通过随机指定隐层参数，并利用最小二乘法求解输出层权重的方式来训练单隐层前馈神经网络（single-hidden layer feedback network, SLFN），故其具有泛化能力强、训练速度快等优点[6],[7]。SLFN的基本结构如图2-4所示。

设训练集包括N个训练样本，将其表示为（xi, ti）∈，其中，xi表示n ×1维的输入向量，ti表示第i个训练样本的期望输出向量，对于分类问题而言，n即代表训练样本的属性数，m则代表样本的类别数。如图2-4所示，若一个具有L个隐层节点的单隐层前馈神经网络能以零误差拟合上述N 个训练样本，则意味着存在βi, ai及bi，使得下式成立：

其中，ai和bi分别表示第i个隐层节点的权重与偏置；βi表示第i个隐层节点的输出权重，即第i个隐层节点到各输出节点的连接权重；G表示激活函数，则式（2-20）可进一步简化为

其中

其中，G（ai, bi, xj）表示第j个训练样本在第i个隐层节点上的激活函数值；T为所有训练样本对应的期望输出矩阵，通常将每个样本所对应类别输出节点的期望输出值设为1，其他节点的输出值则设为-1; H被称为隐层输出矩阵，其第i列为第i个隐层节点在所有训练样本上的输出向量，第j 行为第j 个训练样本在整个隐藏层中对应的输出向量。

在极限学习机中，由于所有ai和bi均是在[-1,1]区间内随机生成的，故输入样本、隐层权重与偏置、期望输出（类别标记）均已知，则输出权重矩阵β的近似解即可由下式直接计算得到：

其中，H†为隐层输出矩阵的Moore-Penrose广义逆。根据其定义，可推知为该网络的最小范数最小二乘解。因此，极限学习机可通过进一步计算得到，而无须迭代训练，这就保证了神经网络的训练时间能被大幅缩减。同时，由于在求解过程中，约束了输出权重矩阵β的l2范数，使其最小化，故可保证网络具有较强的泛化性能。

2012年，极限学习机的优化版本被提出，类似于支持向量机，其优化式可表示如下：

其中，εi表示第i个训练样本的实际输出与期望输出之差；h（xi）为第i个样例xi在隐层上的输出向量，而C则为惩罚因子，用于调控网络的泛化性与精确性间的平衡关系。上述优化式可通过求解得到，给定一个具体的样本x，其对应的实际输出向量可由下式求得

其中，I表示单位矩阵；f（x）=[f1（x）, …, fm（x）]则表示样本x的实际输出向量，并可进一步通过下式确定该样本的预测类标：

下面考察样本类别不平衡分布对极限学习机会产生何种影响。从上面的理论分析可知，对于极限学习机而言，那些在属性空间中相邻较近的样本通常会有极其相似的输出值，而在类重叠区域，多数类样本会将少数类样本紧密地包裹其中，它们的输出值将极为接近。为同时保证所训练的极限学习机具有较强的泛化能力与较低的训练误差，少数类必然做出更多的牺牲。不失一般性，假设分类任务只有两个类别，其中在极限学习机中，少数类对应的期望输出为1，而多数类的期望输出为-1。考虑属性空间中两类样本的重叠区域，若可从该区域分割出一个足够小且样本分布致密的子区域，并保证在这一区域中多数类样例有S个，而少数类样例数恰好只有1个，即在此区域中，不平衡比率为S，则根据极限学习机的构造机理，这S+1个样例将有极其近似的输出值。设该少数类样本的特征向量为x0=（x01, x02, …, x0n），则S个多数类样例的特征向量可表示为：xi=（x01+Δxi 1, x02+Δxi2, …, x0n+Δxin）, i∈{1,2, …, S}，其中，Δxij表示第i个多数类样例与少数类样例x0相比，在第j个特征上的变化量，则在极限学习机训练完成后，这些样本的实际输出可表示为

若以Δf（xj）来表示第j个多数类样本对比少数类样本x0在实际输出上的变化量，则其可表示如下

若其中的激活函数G采用的是连续函数，且同时相邻样本在属性空间上的变化量Δxj，隐层权重与偏置的l2范数‖a‖、‖b‖，以及输出权重矩阵‖β‖的l2范数均足够小时，可保证两个邻近样本实际输出的变化量Δf（xj）足够小。回顾式（2-25），假定输出权重矩阵β已预先确定，则该致密区间的样例子集Qsub的均方训练误差可表示为

为最小化该子集的均方训练误差，可通过如下偏导式求解：

对式（2-31）进行求解，可得该子区间内的少数类样本的实际输出为

通过前面的分析可知足够小，故可忽略。此外，已知S≫1，则可推得该样本倾向于输出一个负值，且随着S的增大，该值越来越逼近多数类的期望输出值-1。通过上述推导分析，可得出如下结论：对于类别不平衡数据而言，在不同类的样本重叠区域，由于某类样本远远多于另一类，则样本相对较少的一类将会付出更大的错分代价。由此可知，类不平衡分布会对极限学习机的分类结果产生影响，且这种影响也是负面的。