不平衡类分类问题的逻辑判别式算法

邬长安,郑桂荣,郭华平

(信阳师范学院 计算机与信息技术学院, 河南 信阳 464000)

0 引言

数据不平衡问题普遍存在于现实世界，其特点是某些类实例明显多于类.这种不平衡分布使得许多传统机器学习[1-2]方法失效，尤其表现在少数类实例的预测性能上.然而，在许多实际应用中，正确地识别少数类比正确识别多数类更有价值.例如，在癌症检测中，大部分病人只是患有一些正常的疾病，少数病人可能会患有癌症，因此如何正确地识别癌症患者就显得十分有意义.传统的分类模型(例如逻辑判别式等)以分类准确率或与其相关的指标作为代价函数监督模型学习过程，进而使学习到的分类器具有较高的分类准确率.其做法的前提是假设数据集中所有类实例数目相当，这有可能导致学习到的模型忽略了少数类实例，进而把少数类实例误分为多数类.然而，在不平衡类问题中准确率并不是一个有效的评价标准，相反，f-measure[3]、g-mean[4]和召回率是评价不平衡类问题更合适的评估指标.传统不平衡类问题处理方法大致可以分为两大类：基于数据和基于算法的方法.前者通过抽样技术以重新平衡数据分布进而在平衡的数据集上学习模型，如过抽样、欠抽样以及SMOTE等[5-6].这些技术经常应用于处理不平衡类分类问题中，但是数据分布总是千差万别，很难确定数据的实际分布情况.后者通过调整算法或目标函数使得学习到的模型更倾向于正确分类少数类实例，如两阶段规则学习方法[7]、代价敏感方法[8-9]、one-class方法[10]等.与以上所提方法不同，本文将逻辑判别式应用于不平衡类问题.与传统逻辑判别式不同，本文同时使用似然函数和召回率构建新的目标函数LERM(Likelihood Estimation and Recall Metric).以LERM为基础，本文提出一种LDAI(Logistic Discrimination Algorithms for Imbalance)模型来处理数据不平衡问题.16个UCI[11]数据集上的实验结果表明，与传统的逻辑判别式相比，在保持逻辑判别式高准确率的前提下，LDAI有效地提高了召回率、f-measure值以及g-mean值.与基于欠抽样和过抽样的逻辑判别式相比，LDAI也表现出明显优势.

1 相关工作

逻辑判别式是一种典型的概率统计分类模型，它通过线性函数来拟合对数似然比.对于两类问题可以表示如下：

(1)

其中：x代表实例，w是拟合参数，所有实例的各个类的概率之和是1，如下：

(2)

结合式(1)和式(2)可以得到，

(3)

其相应对数似然函数为：

(4)

所以目标函数(4)可写为：

(5)

其中，c是一个与w无关的参数.

从目标函数(5)中可以发现，传统的逻辑判别式试图最大化正确分类实例的概率之和.这种做法同等对待每种类，而不考虑该实例是多数类还是少数类.这导致目标函数忽视了不同类具有不同价值的重要事实，所以该方法不适用于数据不平衡问题中.与以上方法不同，本文同时使用似然函数和召回率构建一个新的目标函数来解决不平衡类的分类问题.

2 基于逻辑判别式的不平衡类学习

2.1 新的目标函数

传统的逻辑判别式使用最大似然函数监督参数学习过程，以期获得最高的分类准确率.然而，这忽略了少数类往往比多数类更有价值的事实，导致少数类不能正确分类.为了解决该问题，本文使用似然函数和召回率重新定义了指导参数学习的目标函数.下面给出相关符号：

令类j为Cj={xi|yi=j}，又令

(6)

其中，pij=p(y=j|xi).Pj反映了类j正确分类的实例数.进一步地，定义Rj为类j的召回率，即:

(7)

基于似然函数和召回率的目标函数构建如下：

f(w)=L(w)+r×(R1+R2),

(8)

其中：L(w)为对数似然函数，其表达式如式(5)所示；r=qN(q[0,1]，N是实例数目).通过q，我们可以控制L(w)和召回率的作用.

定理f(w)的梯度是：

(9)

证明对f(w)求导，可以得到:

(10)

其中

(11)

(12)

(13)

算法1 LDAI

输入：D—训练数据集

输出：拟合参数w

1.随机初始化w(1)，给定允许误差ε>0;

2.设置H1=In(单位矩阵)，置k=1;

3.重复;

4.用式(9)计算gk=▽f(w(k))；

5.用式(16)计算p(k)和q(k)；

6.用式(15)计算Hk+1；

7.令d(k)=-Hkgk；

8.求步长λk，使得

w(k+1)=w(k)-λkHkf(w(k));

9.令w(k+1)=w(k)+λkd(k)；

10.直到(‖▽f(w(k+1))>ε‖);

11.返回w.

2.2 算法

根据2.1提供的目标函数，提出一种新的算法叫作LDAI.在学习阶段，LDAI运用了拟牛顿算法[11]，最优化目标函数(9)，计算最佳拟合参数w.形式化地，该方法可以写为如下迭代过程：

w(k+1)=w(k)-λkHkf(w(k)),

(14)

其中：λk是第k次迭代沿牛顿方向搜索的最优步长,Hk是用BFGS公式对目标函数Hesse矩阵的近似，Hk的计算方法为：

(15)

其中

p(k)=w(k+1)-w(k),

q(k)=f(w(k+1))-f(w(k)).

(16)

相关细节见算法1.首先，算法1随机初始化参数w，然后用拟牛顿方法优化f(w)，从而找到最佳拟合参数w.

3 实验

3.1 数据集及实验设置

16个数据集是从UCI[11]机器学习库中随机选取的(见表1).这些不平衡数据集使用如下方法获得：1)如果源数据是多数类，选择其中的两类，一类被看作少数类，另一类被视为多数类；2)如果源数据集是二类的，且不平衡率(少数类实例数/总实例数)大于0.25，则移出部分少数类样本，否则，保持该数据不动.

为了评估LDAI(提出的方法)的有效性，把LD、US-LD(欠抽样逻辑判别式)和OS-LD作为比较参照，其中LD为逻辑判别式，US-LD首先将欠抽样技术应用于数据集，然后在抽样后的数据集上学习LD模型.与US-LD类似，OS-LD首先将过抽样技术应用于数据集，然后在抽样后的数据集上学习LD模型.对于每一个数据集，采用10折交叉验证分析算法的性能.另外，在算法公式(9)中，设置平衡参数r=0.55.相关实验结果都是使用数据挖掘工具洛阳铲(LySpoon)[12]获得的.

3.2 实验结果

LDAI、LD、US-LD和OS-LD在16个数据集的实验结果如表2至5所示(括号里表示标准差)，其中*、•(○)表明在算法相当的数据集上LDAI显著优于其他算法，其中，使用配对t测试(显著水平为0.05)测试算法优劣的显著性.表的最后一行为算法在所有数据集上性能的平均值.

表1 实验数据集信息

表2 LDAI、LD、US-LD和OS-LD的准确率及标准差

表2显示，在准确度上LDAI仅次于LD，但又比US-LD和OS-LD显著好.US-LD和OS-LD的低准确率是由抽样改变了数据集类分布导致的.

表3显示了4种算法在g-mean上的性能.LDAI在8个数据集上优于LD，与US-LD和OS-LD相比，LDAI也表现出明显优势.在平均值上，LDAI提升LD的g-mean指标高达16.2个百分点.

表4显示，在召回率上，LDAI在5个数据集上明显优于其他算法.与US-LD相比，LDAI在7个数据集上表现稍差，类似地，与OS-LD相比，LDAI在8个数据集上表现稍差.该结果是可以接受的，因为，即使LDAI在某些数据集上表现稍差，但该差距并不明显.总体上，LDAI在召回率上的性能接近OS-LD，而略输于US-LD.在平均水平上，OS-LD提升LD在召回率的性能高达21.4%.

表5显示LDAI在f-measure上表现出明显优势，具体地，LDAI在12个数据集上获得最好结果.在平均结果上，LDAI提升LD的f-measure值到14.1，提升US-LD和OS-LD分别高达30.2%和25.4%.

以上结果表明，LDAI能有效提升逻辑判别式在非平衡分类问题中的性能，值得进一步研究.

表3 LDAI、LD、US-LD和OS-LD的g-mean值及标准差

表4 LDAI、LD、US-LD和OS-LD的召回率及标准差

表5 LDAI、LD、US-LD and OS-LD的f-measure值及标准差

4 结论

首先重写了传统逻辑判别式的损失函数，该损失函数同时考虑模型在少数类和多数类上的性能.在此基础上，提出了一个LDAI(Logistic Discrimination Algorithms for Imbalance)方法用以解决不平衡分类问题.在16个UCI数据集上的实验结果表明，与传统的逻辑判别式相比，在保持LD高准确率的前提下，LDAI有效地提高了召回率、f-measure以及g-mean.与基于欠抽样和过抽样的逻辑判别式相比，LDAI也表现出明显优势.