基于分布式核的在线AUC最大化算法

2018-10-22潘志松周星宇

网络安全与数据管理 2018年10期

刘鑫,潘志松,周星宇,白玮，尤峻

(1.陆军工程大学指挥控制工程学院，江苏南京 210007;2.陆军工程大学通信工程学院，江苏南京 210007)

0 引言

接收者操作特性曲线下面积(Area Under ROC Curve，AUC)[1-2]是一种重要的评价分类性能的指标，它衡量了分类器对任意正样本比任意负样本有更高决策值的概率。与常用的评价指标错分率相比，以AUC为优化目标的分类器能在不均衡数据集上获得更好的测试结果。因此AUC广泛地应用于处理类别不均衡问题，比如癌症诊断[3]和异常值检测[4]问题。

文献[5]研究了采用批处理学习算法来处理AUC最大化问题，但批处理算法训练之前需要存储所有训练数据并且在获得新样本后需要使用所有数据用于更新模型。因此传统的批处理学习算法不适用于处理大规模的流式数据。为了解决这个问题，一些研究者利用在线学习算法来高效地处理按序达到的大规模流式数据。但与传统在线算法不同，AUC最大化问题需要优化一个不同类样本间的成对损失，这样就需要存储所有接收到的训练样本。为了减少存储空间消耗，文献[6]提出了一种利用抽样来模拟历史数据的在线AUC学习方法，该方法是用两个固定大小的缓存空间来存储历史数据，并使用蓄水池抽样方法来动态更新缓存空间，在计算成对损失时只需要与缓存空间中的历史数据进行比较即可。文献[7]提出了一种利用成对平方损失来处理在线AUC最大化问题，该方法利用历史数据的均值向量和协方差矩阵的信息使得对所有数据仅需要计算一次。但以上两类方法都是在原数据特征空间使用线性分类，对于非线性可分的数据集就难以取得理想效果。文献[8]提出了利用可扩展的核学习方法使用线性特征来近似表示核函数。但是随着网络的发展，数据产生的速度更快、维度更高并且数据是以分布式的形式存在。如果将所有数据发送到一个节点进行结算，那么对单个节点的性能和处理时延就提出了很大的挑战。

本文提出了一种基于分布式网络结构的核在线AUC最大化算法(Distributed Kernel-based Online AUC Maximization，DKOAM)。利用中心化分布式网络结构的特点，将计算分散到每个工人节点上，中心节点只需要收集工人节点的信息后更新模型分类器。这样能够更高效地处理分布式数据源数据，并且采用基于核方法的特征映射，在非线性可分的数据集上比使用原特征数据有更好的效果。

1 DKOAM方法介绍

与传统在线学习算法不同，分布式在线学习算法有多个数据源。如果将多个数据源的数据汇总到一台服务器节点上进行计算，单台服务器将难以高效处理海量的数据。因此针对多数据源的分布式计算环境，本文采用一种中心化的分布式在线学习算法来处理AUC最大化的问题。

1.1 核表示

(1)

那么核函数可以表示成对应于变量u的期望函数:

κ(x1,x2)=Eu[eiuΤx1·e-iuΤx2]

=Eu[cos(uΤx1)cos(uΤx2)+sin(uΤx1)sin(uΤx2)]

=Eu[[cos(uΤx1),sin(uΤx1)]·[cos(uΤx2),sin(uΤx2)]]

(2)

根据式(2)平移不变核可以表示成新特征内积的期望，其中新特征可表示为z(x)=[cos(uΤx),sin(uΤx)]。因此为了近似表示式(3)中的期望，通过从分布p(u)中独立采样多个随机傅里叶样本u1,…,um来得到输入特征x的新特征表示：

1.2 在线AUC最大化

AUC(w)=

(3)

其中Ι(·)为指示器函数，当条件满足时输出1，否则输出0。但是由于直接优化式(3)是一个NP难问题，因此一般采用一个凸函数来替换指示器函数，这里采用成对的hinge损失来进行替换：

(4)

那么可以通过最小化下面这个目标函数来得到最优的分类器：

(5)

但是优化式(5)需要计算当前样本和所有不同标签训练样本之间的成对损失，因此需要存储所有已接收数据，这对于大数据条件下的在线学习需要消耗大量的存储空间。为了解决这个问题，文献[6]、[11]中引入两个固定大小N+和N-的缓存空间B+和B-来存储正负类的样本。而缓存空间的更新采用蓄水池抽样技术，通过蓄水池抽样能够保证缓存空间刻画了对所有已接收数据的均匀采样。在一个新样本(zt,yt)到达时，当缓存空间B的大小小于固定上限N时，就将该样本插入缓存空间中。当第t轮接收到的样本大小Nt超过N时，就按照一定概率用新样本随机替换一个缓存空间中的老样本。具体算法细节见算法1。

算法1：缓存空间更新算法(UpdateBuffer)

1：输入：Bt,zt,N,Nt+1

2：if |Bt|

3：Bt+1=Bt∪{zt}

4：else

5：按照Pr(Z=1)=N/Nt+1的概率从伯努利分布中抽取一个样本Z

6： ifZ=1

7：随机从Bt中删除一个样本

8：Bt+1=Bt∪{zt}

9： end if

10：end if

11：输出:Bt+1

1.3 DKOAM方法

在中心化分布式环境下，如图1所示，存在一个中心节点和多个工人节点。工人节点同中心节点相连，工人节点之间没有连接。

图1 中心化分布式拓扑示意图

在中心化在线学习中，所有工人节点采样同样的随机傅里叶样本。每个工人节点独立接收来自不同数据源数据，本地独立计算梯度值。中心节点采用同步的方式汇总所有工人节点的梯度值后进行模型更新。为了解决分布式大数据环境下的线性不可分数据的在线AUC最大化学习，本文提出了一种中心化的基于核的在线AUC最大化学习算法DKOAM，具体算法细节见算法2。

算法2：基于核的中心化在线AUC最大化学习算法(DKOAM)

工人节点(i=1,…,n):

2：fort=1,2,…,T

10： else

14： end if

16：end for

中心节点：

1：输入：学习率η

2：fort=1,2,…,T

5：end for

2 实验验证与分析

本节对提出的DKOAM算法在3个标准数据集上与4种在线AUC最大化算法进行比较。

2.1 比较算法

比较算法包括以下4种：

(1)OAMseq：基于蓄水池抽样和序列更新算法的在线AUC最大化算法[6]。

(2)OAMgra:基于蓄水池抽样和在线梯度更新算法的在线AUC最大化算法[6]。

(3)OPAUC：基于平方损失的单遍AUC最大化算法[7]。

(4)FOAM：基于随机傅里叶特征方法的核在线AUC最大化算法[8]。

2.2 实验准备

为了比较DKOAM与其他4种在线AUC最大化算法之间的性能，本文实验在3种标准数据集上进行测试。数据集的特征都重新调整到[-1,1]之间。多分类数据集(letter和acoustic)转化为二分类数据集，即随机选择一类作为正样本，其他类作为负样本。数据集的具体特征见表1。

表1 数据集特征

DKOAM使用4个工人节点和1个中心节点的中心化分布式网络，每个节点运行在一个CPU核心上，算法使用MPI完成节点间通信。DKOAM的学习率η和高斯核σ参数的寻参空间分别为[2-10,210]和[1,20]。参数通过五折交叉验证确定，即随机将数据集分成5份，4份用于训练，1份用于测试。其他算法的参数按照推荐参数进行设置。

2.3 实验结果

调参结束后，采用4次五折算法进行测试以进一步减少随机分割数据集带来的随机性。对20次测试结果取平均值作为测试结果。为了比较算法的运行效率，对25次测试运行时间取平均值。测试结果见表2。

表2 DKOAM与4种在线AUC最大化算法测试结果

注：表中每一项为：平均AUC值/平均运行时间(s)

从表2的结果可以看出，使用核方法的FOAM和DKOAM相较于使用原特征的其他在线AUC最大化算法有更高的精度。这验证了在数据线性不可分的情况下，将原数据特征通过核方法映射到新的核特征空间有更好的分类效果。而DKOAM和FOAM相比，两者精度相当。从算法时间复杂性方面分析，基于分布式计算框架的DKOAM相较于FOAM有更高的效率。这验证了分布式计算框架在处理分布式多数据的问题中相较于单节点的算法有更高的运算效率。

从图2中能够看出，DKOAM和FOAM两种基于核方法的算法相较于其他在原特征空间的线性模型算法有更快的收敛速率。本文提出的DKOAM相较于FOAM收敛更快，并且相较于OAMseq和OAMgra两种方法收敛更稳定，波动更小。这也验证了采用小批量更新方法对模型更新过程中的噪音更加鲁棒。