耦合样本先验分布信息的加权极限学习机

席晓燕,于化龙

(江苏科技大学计算机学院,江苏 镇江 212003)

0 引 言

当数据集中某一类(或多个类)的样本数远高于其他类的样本数时，使用传统的以最小化整体误差为目标的分类器进行学习，会导致分类面偏向多数类，少数类分类准确率下降，这类问题称为“类不平衡问题”。类不平衡问题广泛存在于实际应用中，如医疗诊断[1]、诈骗电话检测[2]、文本分类[3]等。针对这一问题，前人已经做了大量研究并给出了诸多解决方法，包括采样技术[4]、代价敏感学习[5]、决策输出补偿[6]等。

极限学习机(Extreme Learning Machine, ELM)是2006年Huang等[7]提出的一种单隐层前馈神经网络(Single hidden Layer Forward Neural network, SLFN)方法。与传统的训练方法相比，其最为显著的优点在于训练速度快、泛化能力强。ELM在很多方面得到广泛应用，如分类回归[8]、聚类[9]、增量及在线学习[10-11]等。在处理类不平衡方面，Zong等[12]提出了一种加权极限学习机(Weighted Extreme Learning Machine，WELM)算法。该算法通过为不同类的样例赋予不同权重，从而改变其惩罚因子的方式，达到提升少数类样例识别精度的目的。Vong等[13]将ELM与随机过采样技术(Random OverSampling，ROS)相结合，Lin等[14]则将SMOTE(Synthetic Minority Oversampling Technique)算法引入到ELM集成学习的框架中，以此获得了性能的提升。

在ELM框架下，尽管已有多种类不平衡处理方法，但均没有考虑样本先验信息对模型性能的影响。本文针对这一问题，将样本的先验分布信息与WELM算法相结合，提出一种耦合样本先验分布信息的加权极限学习机CPWELM(Coupling sample Prior distribution Weighted Extreme Learning Machine)算法。该算法首先利用样本先验信息对每个样本的相对“重要度”进行估计；其次采用估计出的相对值对样本进行加权处理；然后利用加权后的样本训练极限学习机；最后通过计算并排序所有样本的重构误差来确定模型阈值。该方法利用了样本先验信息对各类复杂分布自适应性与相对准确性，以及极限学习机训练速度快、泛化能力强等优点，提升了少数类预测的准确率。通过多组比较实验验证了上述假设，即与多种前人方法相比，本文方法在一定程度上提升了G-mean和F-measure值。

1 理论基础

1.1 极限学习机

ELM完全摒弃了传统的迭代误差调整策略，改为随机设置隐层权重与偏置，利用最小二乘的思想直接对输出层权重矩阵进行求解，使用更少的训练时间，即可获得同等的泛化性能。

假设训练集包含N个样本，且这些样本能被分入m个类当中，其中第i个训练样本可以表示为(xi,ti)，xi是一个n维的输入向量，而ti则对应于一个m维的输出向量。另假设ELM中包括L个隐层节点，该层上的权重w与偏置b在[-1,1]区间完全随机生成，那么对于样本xi，其对应的隐层输出可以表示为一个行向量h(xi)=[h1(xi),h2(xi),…,hL(xi)]。ELM的数学模型可以表示为：

Hβ=T

(1)

其中，H=[h(x1),h(x2),…,h(xN)]T为所有样本对应的隐层输出矩阵，β为待求解的输出层权重矩阵，而T=[t1,t2,…,tN]则表示样本类标所对应的期望输出矩阵。利用最小二乘法，β可通过式(2)进行求解：

(2)

其中，H†表示H的Moore-Penrose广义逆，其可以保证所求得的为式(1)的最小范数最小二乘解。

也可从优化的角度对ELM进行描述与求解。由于在ELM中，希望同时对‖Hβ-T‖2和‖β‖2做最小化处理，因此该问题也可以描述为式(3)：

(3)

其中，ξi=[ξi,1,ξi,2,…,ξi,m]表示样本xi在第m个输出节点上所对应的训练误差向量，而C则表示惩罚因子，用于调控模型训练准确性与泛化性二者之间的关系。根据Karush-Kuhn-Tucker(KKT)理论[15]，式(2)的解可表示为：

(4)

1.2 加权极限学习机

鉴于传统的ELM在训练时，通常将每个训练样例看作同等重要，因而易于受到噪声和离群点的干扰，同时也无法在样本类别分布极度不均衡时取得好的分类效果，对此在文献[12]提出了一种WELM算法。该算法通过为不同类的样例赋予不同权重，从而改变惩罚因子的方式来有效降低少数类样例被错分的概率，故式(3)转变为如下形式：

(5)

其中，W是一个N阶的对角矩阵，Wii代表第i个训练样例所对应的权重。对应值越大，代表该样本越重要。文献[12]提供了2种权重分配方式：

WELM1: Wii=1/#(ti)

(6)

(7)

其中，#(ti)代表训练集中属于ti类的样本数，AVG表示所有类的平均训练样本数。显然，上述2种权重分配方式，少数类样本都会被赋予更大的权重，且类不平衡比率越高，少数类与多数类之间的权重比也将越高。对式(4)求解，可得：

(8)

2 本文方法

WELM算法虽然在一定程度上考虑了类不平衡数据特性，但仅仅处于类别层次。为了充分挖掘每个样本点的重要程度，本文在WELM基础之上，从样本的先验信息分布出发，考虑样本的类覆盖的大小(即不同类样本重叠区域的占比)、样本的不平衡比率、训练集中噪声与离群样本的比例以及类内子聚集对极限学习机的影响，并为处于不同分布的样本赋予不同的权值，从而进一步提升模型性能。

2.1 不纯度指标

不纯度(Impurity)通常用在决策树模型中，用于选择最佳划分。在本文算法中，可以用来度量类分布的倾斜程度，不纯度越低，类分布越倾斜，即其中一类样本的比例越大。其计算方式有2种：

(9)

(10)

其中，c是类的个数，p(i|t)表示给定邻域t中属于类i的样本所占比例，且规定，计算熵时0log20=0。

具体来说，数据集的重叠区域是各类样本的交叠部分，其不纯度比较高；而安全区域是离分类面较远的各类区域，绝大多数样本属于同一类，故此区域的不纯度低；同理，离群点噪声点邻域的不纯程度也较低。因此，不纯度越高代表此区域样本包含的信息越多，应被赋予更大的权重。

2.2 隶属度函数及权重矩阵

为了区分安全区域及离群点噪声点，本文采用k近邻的思想。若样本离同类k近邻的距离小则表示此样本很大概率处于其所属类的密集区域，其“重要度”较大。

令di表示同类k近邻距离，entropy(xi)和gini(xi)表示邻域内不纯度，本文构建出样本xi的2种隶属函数f(xi)如下：

(11)

(12)

可以看出样本的隶属度函数由k近邻距离及不纯度决定。k的选择关系到其隶属度大小，若k太小则不能将离群点区分开来，若k太大会导致不能区分不同样本，本文算法取经验值Nj/10，其中Nj是样本所属类别j的训练集个数。同理，样本邻域的大小也关系到不同区域的样本能否辨别，本文取样本所属类平均距离的1/γ。

隶属度函数转化为权重需归一化处理，如下：

(13)

2.3 CPWELM算法流程

根据上文提供的权重计算准则，给出CPWELM算法流程如算法1所示：

算法1 CPWELM算法

输入：训练集S={(xi,yi),i=1,2,…,N,yi=(1,2,…,m)}

输出：极限学习机分类器L

算法步骤：

1 遍历训练集S，并从中分别统计出每类的样本数Nj，其中，j=1,…,m，进而计算出类别不平衡比率IR的值；

2 设k=Nj/10，且γ=5

For i=1:N

2.1根据样本xi所属类别，得到其所属邻域范围内所属类别的比例，根据式(9)或式(10)计算其邻域不纯度；

2.2计算样本xi与其k近邻的距离di；

2.3并根据式(11)或式(12)计算其隶属度值f(xi)；

End

4 调用式(13)计算各样本的加权系数Wi；

5 随机生成隐层权重w与偏置b，并利用激活函数g(x)计算各样本所构成的隐层输出矩阵H；

6 根据式(8)生成输出权重β；

7 For i=1: N

7.1 利用预处理信息计算每个样本的Wi值；

7.2 若样本为正类，则令mi=Wi×IR，若样本属负类，则令mi=Wi；

End

8 利用步骤7所得各样本权重生成对角权重矩阵W；

9 利用式(5)训练加权极限学习机分类器L。

3 结果与讨论

3.1 数据集与实验设置

本文实验重点验证CPWELM算法的有效性与可行性。实验数据为从Keel数据库[16]中随机抽取的12个二类不平衡数据集，这些数据集的具体信息如表1所示。

表1 本文采用的数据集

为了验证本文算法在类不平衡学习中的有效性，将其与基于ELM的类不平衡学习算法进行比较，包括标准的ELM算法[7]、WELM1[12]、WELM2[12]、RUS-ELM[17]、ROS-ELM[13]、SMOTE-ELM[4]、FWELM-C[18]、FWELM-H[18]。同时，为了保证比较结果的公正性，对不同算法的共有参数进行统一设置，其中ELM中隐层节点数L及惩罚因子C均给定统一的取值范围，采用格搜索(Grid Search)策略以确定最优的参数组合，具体取值范围为L∈{50,100,…,950,1000},C∈{2-10,2-8,…,28,210}。此外，考虑到ELM算法具有随机性，故对上述每种算法的分类结果均以10次外部随机五折交叉验证取均值和方差的方式给出。针对FWELM算法特有的参数Δ及β，前者取值固定为10-6，而后者的取值范围[0,1]，步长为0.1，以内部五折交叉验证的方法来加以确定。至于SMOTE算法中最重要的参数k,则取缺省值5。鉴于类不平衡学习的特性，本文实验采用F-measure和G-mean这2种测度来比较各类算法的性能。

3.2 结果与讨论

表2和表3分别给出各比较算法在二类数据集上的F-measure和G-mean评价测度值。其中每个数据集中对应的最优值用粗体进行突出显示，且本文算法括号中的g及e分别代表算法中选择的不纯度指标是Gini或Entropy。

从比较结果中，可以得出如下结论：

1)基于经验的代价敏感学习算法(WELM1与WELM2)的性能在不同数据集上有差别。对比这2种算法，发现WELM1的G-mean值更高，而WELM2的F-measure测度更优异。该现象与二者的权重分配有密切的关系，前者调整更为保守，后者则为多数类分配更小的权重，使得多数类的精度下降。

2)与其他类别不平衡算法相比，CPWELM系列算法在性能上有大幅度的提升。尤其是CPWELM1算法，分别在6和7个数据集上获得了最高的值，进一步验证了结论1，说明了保守性加权更为合理。另外，从结果中亦可以看出，CPWELM算法优于依据分类面加权的FWELM-H，原因是FWELM-H中分类面偏离太严重时此算法得到的权重并不能反映样本的分布，此进一步说明了对样本精细划分(如重叠区域、噪声区域、安全区域等)更有利于生成精细且公正的分类面，指明了代价敏感学习中充分耦合样本先验信息的重要性。

3)在少量数据集，比如wisconsin、vehicle0等上，本文算法与FWELM-H性能相当，是与数据集的分布有关，当数据集分布接近均匀分布，FWELM-H与本文算法的加权值大致相等，导致性能相当。

4)对比CPWELM的2种算法中最优结果中用到的不纯度指标的比例，显然用Entropy得到最优值的概率更高，原因是Entropy的阈值是[0,0.5]而Gini的阈值是[0,1]。说明了权重调整的幅度要适当。

表3 各算法在数据集上的G-mean测度值

3.3 统计结果分析

表4表示各类算法不平衡数据集上的Friedman排序及其F-measure和G-mean测度在Holm后验假设检验中的APV值，其中，rankingF及rankingG分别表示算法在F-measure和G-mean测度上的平均排序值，而APVF及APVG则分别表示算法在F-measure和G-mean测度上采用Holm后验假设检验所获得的APV值。

从统计结果中可以看出，所有的类别不平衡学习算法中，CPWELM算法对应最低的rankingF及rankingG值，表明本文算法要优于其他的比较算法。同时，对应于除WELM1、FWELM-H的APVF和APVG及WELM2算法的APVF外，其他的APV值均低于标准的显著性测度α=0.05，这也表明，CPWELM算法在统计上要显著优于其他算法。而考虑到CPWELM算法ranking的值仍要低于WELM及FWELM-H算法，故可认为前者仍要优于后者。

表4 各算法在数据集上统计结果

4 结束语

本文采用代价敏感思想解决类不平衡分类问题，在经验加权的基础上耦合样本先验信息，给予每个样本精细准确的权重以代表其在分布中的重要度，提出了CPWELM算法。CPWELM算法克服了经验加权及FWELM算法的局限性，利用样本局部邻域的不纯度及其近邻信息充分描述了样本的先验分布信息，提高了分类器的性能。最后通过多个数据集验证了本文算法的有效性。

在未来的研究工作中，希望能在以下几方面做一些扩展性的工作：

1)对现有隶属函数做出改进，将其应用于多类不平衡分类问题。

2)将本文算法应用到各种实际应用领域中，从而对其有效性做进一步评估。