基于RepVGG和LSTM两阶段移动众包任务分配算法

于 嵩,潘庆先,童向荣,刘庆菊,褚佳静

(烟台大学 计算机与控制工程学院,山东 烟台 264005)

随着手持智能设备和移动互联网的迅速发展,移动众包已经成为了一种新的问题解决方式,通过手机等智能设备中嵌入的传感器和用户的移动性来感知周围环境,并利用现有的通信基础设施(如蜂窝移动网、WiFi、蓝牙等)从散落在各处的智能设备上收集数据。一个典型的移动众包系统包含众包平台、众包商和工人。众包商通过众包平台发布任务,众包平台将任务分配给合适的工人,工人收集到任务所需的数据并反馈给众包平台然后获取他们的报酬[1]。任务分配直接影响众包平台的性能,这也是移动众包领域内的研究热点之一。

在移动众包中,为了最大化任务覆盖率,将感知任务分配给合适的工人是系统平台完成感知活动的主要目标之一。为了实现这一目标,任务分配被研究人员广泛关注,并开展了一系列深入的研究工作。随着基于位置的服务和信息通信技术的快速发展,地理大数据的获取变得更加方便。出租车轨迹、手机记录和社交媒体数据等大数据都包括地理位置和一系列时间信息。这些数据来自于人类的日常生活并实时更新,被广泛用于解决人类与环境的关系问题[2]。由于众包平台在初始并不了解所有的众包任务,任务是动态到达的,此时进行任务分配往往会陷入局部最优。因此在任务分配过程中,挑战之一是对任务可用性和持续性的预测。近年来,深度学习方法和技术已成功应用于各种现实世界具有挑战性的预测问题,包括序列预测。长短期记忆网络(Long Short-Term Memory,LSTM )和卷积神经网络(Convolutional Neural Networks,CNN)可能是最流行、最有效和广泛使用的深度学习技术[3]。在序列问题上使用这些模型的基本思想是,LSTM 模型由于其特殊的架构设计可以有效地捕获序列模式信息,而 CNN 模型可以过滤掉输入数据的噪声并提取更有价值的特征,从而对最终的预测模型更有用。

在移动众包中,基于预测的方法可以提高任务分配的效率。LI 等人[4]设计了一种基于预测的任务分配算法,该算法可以获得最大的总体效用和最低的旅行成本。何杏宇等人[5]提出了一种基于LSTM 的预测模型来预测工人的轨迹,基于预测结果来进行任务分配,进而优化感知活动的质量。PIAO 等人[6]研究了多充电桩场景下的无人车数据收集应用,提出了一种结合LSTM 和强化学习的新型序列预测模型,通过近端策略优化训练完成该模型,用于任务分配和路径规划;ZHU 等人[7]提出了一组基于深度学习的车辆轨迹预测方案,以平台预算为约束,采用贪婪策略招募更多的车辆来优化平台数据质量。ZHAO 等人[8]提出了一种两阶段的数据驱动框架,该框架考虑当前和未来的工人和任务,目的是预测未来工作人员的位置和路线。

任务持续性的预测依托于对时间序列的准确预测,在此领域研究人员做出了大量的贡献。PEDRO 等人[9]对时间序列预测领域的七种现有架构的适用性进行了深入的研究,结果表明LSTM 和CNN 是最好的选择,LSTM 可以获得最准确的预测,而CNN 在不同的参数配置下实现了可比的性能。SONG 等人[10]提出了一种基于LSTM 的模型来进行针对于油井性能的时间序列预测,并采用粒子群优化算法来优化模型的基本配置。LI 等人[11]介绍了一种基于时间序列成像的自动化方法来提取时间序列特征,基于此来进行预测会得到具有竞争力的性能。ZEROUAL 等人[12]介绍了五种深度学习方法,用于抗击并预测COVID-19 时间序列的相关信息。SAGHEER 等人[13]尝试解决传统预测方法的局限性,提出了一种深度长短期记忆网络(Deep Long Short-Term Memory,DLSTM)架构,实验结果表明了该模型的优越性。TAO 等人通过考虑外部特征之间的相关性,提出了HRHN模型,提高了序列预测精度。BEN 等人[14]针对于移动众包提出了一种基于深度神经网络(Deep Neural Networks,DNN)的预测框架,对来自于众包商的任务进行预测。然而,现有的时间序列预测方法在移动众包领域应用较少,且大多是单一的序列预测,未与任务可用性预测相结合。在移动众包领域,只有任务可用性得到确认后,任务持续性的预测才有意义。因此,面向移动众包领域的任务分配预测问题具有重要研究意义。

为了解决任务分配预测问题,本文提出了一种基于深度学习的移动众包任务分配算法,用于预测移动众包任务可用性和持续性。

本文工作如下:

提出了一种新的基于深度学习的移动众包服务的任务分配模型,该模型基于利用深度学习技术优势的原理思想。具体地说,为了提取出时间数据的内在相关性,模型利用来自众包商的历史数据,使用马尔可夫变迁场将历史数据转化为图像来学习数据的内部表示,然后使用一种新的、简洁的卷积神经网络模型RepVGG 学习时间数据的空间自相关性用于预测任务存在性。最后,利用LSTM 层识别短期和长期依赖关系的有效性来预测任务的持续时间。所提出的模型针对于先进的机器学习和深度学习模型进行了评估,以预测任务的存在性和持续性。实验表明,所提出的算法可以显著地提高预测性能。

1.1 聚类

聚类是统计数据分析的一种常用技术,属于无监督学习问题,在包括模式识别、深度学习、生物信息学等许多领域都有应用。聚类是将相似的对象分组到不同组的过程,更精确地说,是将数据集划分为子集,以便每个子集中的数据根据某个定义的距离度量[15]。

对于移动众包平台中的任务来说,地理位置是一个十分重要的属性。来自现实世界的数据集对于地理位置信息通常采用由WGS84 坐标系统记录的经纬度数值。对于样本数量足够多的数据集来说,这种离散型位置信息不仅难于处理,且也无法作为序列输入至模型中。因此,工作的第一步是对数据的地理位置信息进行聚类操作,将离散的位置信息依据其相关性划分为合理的簇,划分结束后,在同一簇内的任务即被视为同一位置。

K-Means 算法[16]是使用最广泛的聚类算法之一,具有收敛速度快、原理简单等优点。该算法将数据集分为n个簇,每个簇使用簇内所有样本均值来表示,将该均值称为“质心”。K-Means 使用两个目标之间的距离来度量它们的相似性:

公式(1)代表了K-Means 算法的目标函数,其中,C1,C2,…,Cn分别是初始化的n个簇的中心点,C(Xi)表示Xi所属簇的中心点,d代表两点之间距离的平方。由于现实世界多是利用经纬数值来记录地理位置信息,因此采用半正矢距离来表示两点之间的距离。半正矢距离是指球面上以经纬度度量的两点之间的距离。半正矢距离的求解公式为

其中:h(θ)是半正矢函数;r是地球的半径;φ1、φ2分别表示两点的纬度,以弧度制度量;λ1、λ2分别表示两点的经度,以弧度制度量。

对于K-Means 算法来说,初始的聚类簇数n是重要的,n的选择对聚类结果会有较大的影响。为此,采用手肘法来确定初始聚类簇的数目,手肘法的核心指标是误差平方和。

手肘法的基本思想是随着n的增大,簇的数量会不断增多,每个簇的紧密程度也会不断提高,LSSE会逐渐变小,LSSE的求解公式为

当n离最佳簇数目比较远时,随着n的增大,LSSE会迅速下降,而当n接近最佳簇数目时,LSSE的下降幅度将会变缓,因此下降幅度最大处对应的n就是数据的最佳聚类簇数目。

1.2 特征工程

特征工程指的是通过特征转换、特征生成或特征提取、特征构建、特征选择等方法从原始数据中提取信息以用于机器学习或深度学习算法,特征工程优化了特征空间尺寸,从而降低了复杂性[17]。一个良好的特征提取方法决定了预测性能的下限,而一个良好的网络模型决定了预测性能的上限。对于深度学习任务来说,对数据集中的数据进行分析和特征提取是极其重要的,这有助于提高模型预测效果。

在本文的预测模型中,任务的时间信息是重要的输入之一,因此需要对任务的时间信息进行特征提取,扩充特征维度。本文对参与分配的任务定义如下:

定义1任务 对于一个时空众包任务集合T,有T={ti|1≤i≤Nt},其中Nt是任务的数量。对于其中一个任务t∈T,将其属性表示为四元组的形式t=〈id,ts,dura,loc〉。其中,id表示任务的唯一标识,ts表示任务产生的时间戳,dura表示任务的持续时间,loc表示任务的位置信息。

对于每个任务t∈T,进一步扩充属性ts,令ts=〈d,h,m,w,v,q〉,其中:

d:任务t与基线任务的天数差,d∈{0,1,…,364};h:任务t此刻所处小时,h∈{0,1,…,23};m:任务t此刻所处分钟,m∈{0,1,…,59};w:任务t此刻处于星期几,w∈{0,1,…,6};v:任务t此刻是否处于法定节假日,v∈{0,1};q:任务t此刻所处时间段,q∈{0,1,…,8}。

为了达到所需的预测精度,需要对原始数据进行重采样。在重采样后的数据中,根据任务可用性,可以将任务划分为两类。任务可用的数据为正类,任务不可用的数据为负类,而负类的数量会远远大于正类,这也符合现实世界的情况。由于两种类别的数量并不相等,这就会造成类别不平衡问题。因此,需要对负类数据进行下采样,使得两种类别的数据均匀分布。然后,为了防止训练过程中出现梯度爆炸问题,需要将下采样后的数据进行独热编码,这样做也同时扩充了特征。

1.3 马尔可夫变迁场

为了将序列转化为图像,并且转化后的图像仍然能够保留时间信息,本文采用马尔可夫变迁场(Markov Transition Field,MTF)来解决这一问题。

马尔可夫变迁场通过原始的时间序列获得信息,表示时间序列之间的转变概率场。

给定一个时间序列X,将X按照其长度划分为Q个区域,并将X中的每个数据点划分给相对应的分位数qi,i∈{1,2,…,Q}。然后,通过沿时间轴以一阶马尔可夫链的方式计算分位数区域之间的转换来构造一个Q×Q加权邻接矩阵A,ai,j由分位数qi和qj之间相邻的频率给出。通过使用对矩阵进行归一化处理后,A即是马尔可夫转移矩阵。通过将数据分成Q个区域构建了Q×Q的马尔可夫转移矩阵A,包含时间戳i和j的数据的分位数分别是qi和qj,i,j∈{1,2,…,Q},但它对X的分布和时间步长的依赖性并不敏感,去除时间依赖性将会导致矩阵A中过多的信息丢失,为了克服这一缺点,利用矩阵A中的信息,将MTF 矩阵M定义如下:

Mij表示qi到qj的跃迁概率。也就是说,通过考虑时间位置进而将包含转移概率的矩阵A展开成了MTF 矩阵M,MTF 实际上编码了时间序列的多跨度转移概率。Mij|i-j|=k表示时间间隔为k的点之间的跃迁概率[18]。

为了提高效率,减小M的尺寸,通常的做法是将M网格化,然后每个网格中的子图用其平均值替代,如图1所示。整个特征提取过程如图2所示。

图1 MTF 图像转化过程Fig.1 The transformation process of MTF image

图2 特征提取过程Fig.2 The process of feature extraction

2.1 众包任务可用性预测算法

本节使用CNN 来构建任务可用性的预测模型。CNN 由多层感知机(Multilayer Perceptron,MLP)[19]演变而来,常被用于处理计算机视觉方面的工作。

本节使用基于RepVGG 的网络结构训练模型。RepVGG 是一个简单但功能强大的卷积神经网络架构,由DING 等人在2021年提出[20],其网络结构如图3所示。它属于VGG 式的网络结构,仅使用3×3 卷积。与残差神经网络(Residual Neural Network,ResNet)[21]相似的是,RepVGG 也引入了残差结构以用于解决网络层数过多所带来的退化问题,具有比ResNet 更快的准确度和速度。

图3 RepVGG 模型结构Fig.3 The structure of RepVGG model

网络的输入是经由马尔可夫变迁场变换得到的图像。本节所使用的网络模型包含若干个卷积块,卷积块由三层网络构成,分别是1×1 卷积层、3×3 卷积层和批标准化(BatchNorm,BN)层。需要注意的是,若输入数据波动极大,则有可能导致部分数据在经过激活函数后变得几乎无差别,导致模型无法学习到输入数据的特征,这种现象被称之为“梯度消失”。为了解决该问题,网络在卷积块构造初应用BN 层,这是一种归一化方法,用于减少数据之间的绝对值差异。3×3 卷积层用于从图像中提取特征,3×3 卷积的计算密度可以达1×1 和5×5 卷积的4 倍,且速度更快,内存开销更小。卷积块的输出由 1×1 卷积层、3×3 卷积层与来自于上一层的原始输入所构成。最后,对输出应用线性整流函数,引入非线性因素。

RepVGG 网络结构将所有卷积块分为5 组,在每个卷积块伊始设置步长为2 以便于进行降采样操作。在本文使用的模型中,5 组分别由[1,2,4,14,1]个卷积块组成,由于第一阶段的图像输入分辨率较高,在第一组仅采用一个卷积块进行卷积,目的是降低延迟。对于剩下的4 组卷积块,卷积输出通道数分别是[64,128,256,1 280]。在卷积操作之后,使用自适应平均池化层对来自卷积块的输出进行降采样,最后,使用一个全连接层来输出最终预测结果,卷积块网络结构如图4。

图4 RepVGG 卷积块网络结构Fig.4 The structure of RepVGG convolutional network block

本节使用带动量的随机梯度下降算法(SGD with Momentum,SGDM)[22]作为模型的优化器。相比于普通的随机梯度下降算法,SGDM 算法有着加速收敛,不易陷入局部最优点的特点。梯度更新规则为

其中,γ一般取值为0.9。

对于二分类问题,一个较好的选择是使用交叉熵损失作为损失函数。在二分类的情况下,模型最终输出两个类别,损失函数为

其中,N为样本数量,y为期望输出,为实际输出。

学习率是网络中另一个重要的参数,学习率太大可能造成权重参数在最优值附近反复震荡,使得网络无法收敛,而过小的学习率会使得网络收敛速度非常缓慢,甚至无法找到真正的最优解。理想的方案是在网络训练开始采用较大的学习率,在训练轮数增加后,动态地调低学习率,既能够避免网络收敛的太慢,又可以降低网络陷入鞍点的风险。本节使用余弦退火学习率作为动态更新学习率的方法,计算公式为

其中,lrn表示新学习率,lrm和lri表示最小学习率和初始学习率,nepoch表示训练轮数,T表示余弦函数周期的1/2。经过多次反复训练迭代,最终得到的模型能够将误差控制在可接受范围内并给出准确的预测结果。本阶段提出的算法如算法1所示。

2.2 众包任务持续性预测

对于已经确定其服务可用性的任务,还需要进一步预测出其持续时间,以此来作为任务分配的依据。本文将这一阶段的预测任务看作时间序列预测问题,使用基于LSTM[23]的方法来解决这个问题。

与上一节所采用的网络结构不同,LSTM 强调序列的连续性,因此由序列转化成的图像并不能直接输入到LSTM 网络模型中去,因为图像是无序的。首先需要将原始数据进行数据清洗,仅保留任务时间戳和任务持续时间,然后构造时间序列。对于时间序列预测来说,一个重要的参数就是步长step,即滑动窗口的大小。第二阶段的预测属于单变量单步预测,即通过过去长度为step的时间序列来预测第step+1 个时间戳。设原始时间序列为X,序列长度为n,则X=(x1,x2,…,xn)。假定使用step为3 来构造时间序列,则,其中,依此类推。由此可见,由此方法构造的时间序列得到的是时间序列随时间变化的特性。

本节选择均方误差(mean-sauqre error,MSE)作为损失函数,MSE 可以反映实际输出值与真实值之间差异,计算公式为

其中,N是样本的数量,yi是模型输出值,是目标值。

本节选择适应性矩估计法作为损失函数优化算法,该算法吸收了自适应梯度算法和SGDM 的优点,既能适应稀疏梯度,又能缓解梯度震荡的问题。

本节使用等间隔学习率调整作为动态更新学习率的方法,

间隔一定轮数后将学习率调整为原来的γ倍。本阶段提出的算法如算法2所示。

训练开始,首先将输入序列送入输出隐藏层为32 的LSTM 网络块(行4),然后接受输出并重构张量维度(行5),将其送入输出通道为32 的全连接层(行6)。获取到全连接层的预测结果后使用公式(9)来进行损失的计算,根据损失进行反向传播,调整模型参数,最后采用(10)来更新学习率。

2.3 基于预测的任务分配算法

本节提出一种基于预测的任务分配算法,该算法综合前两阶段的预测模型,预测未来的任务情况,对未来即将到来的任务进行预分配,如算法3所示。

首先,对于现阶段存在的任务,算法会将其分配给合适的工人(2～8 行)。而对于那些没有被分配到任务的工人,算法首先会使用模型M1来预测下一刻是否会出现新的任务(行11),若出现了新的任务,则继续使用模型M2来预测新任务的持续时间(行13),然后将任务分配至工人,直到所有的工人都被分配到了任务。

为了验证本文提出的预测模型和算法的性能,本文在多个真实数据集上进行了大量实验。

3.1 数据集

ECML/PKDD 15:该数据集记录了从2013年7月至2014年7月葡萄牙波尔图市运行的所有442 辆出租车的运行数据。

Uber Pickups in New York City:该数据集包含了2014年4月至9月纽约市超过450 万辆Uber出租车的数据,以及其他相关数据。

3.2 众包服务可用性预测实验

本文把8:2 作为划分训练集和验证/测试集的比例。对于ECML/PKDD-15 数据集,设置nepoch为100,LR 为0.005,训练轮数为64;对于Uber 数据集,设置nepoch为100,LR 为0.005,batch size 为96。所有的训练数据最后会通过一个1 280 个通道的全连接层进行分类。所有的RepVGG 模型都在RTX3060 6GB 上进行训练。实验结果如图5所示。

图5 众包服务可用性预测实验结果Fig.5 Experimental results of crowdsourcing service availability prediction

参与对比的算法包括机器学习算法和深度学习算法。其中,随机森林(Random Forest,RF)、决策树(Decision Tree,DT)、K近邻(K-Nearest Neighbor,K-NN)、支持向量机(Support Vector Machines,SVM)以及文献[14]中提出的基于DNN的网络结构均采用序列化数据进行模型训练。文献[24]中提出的基于自注意力机制的Transformer网络结构采用由序列数据生成的简单图像进行训练。本文所使用的RepVGG 网络结构采用第一节提出的方法生成MTF 图像来进行训练。

在准确率上,本文提出的算法具有最好的性能,在相同数据集的对比下,DT 算法的正确率为71%,RF 算法为79%,SVM 和K-NN 算法仅有61%和54%。将序列数据简单编码为图像会丢失序列自相关性,Transformer 结构仅实现了70%和64.6%的正确率,因此提取序列自相关性这一过程是极为重要的。基于DNN 的网络实现了较高的精度,但仍逊色于本文提出的算法。

为了探究网络结构及参数对模型的精度的影响,本文设置了如下消融实验,网络参数如表1～2所示,不同的网络结构卷积块数量和块内宽度有所不同,其中,结构a 和e 是本节所使用的网络结构。

表1 众包任务可用性网络结构对比(ECML/PKDD-15)Tab.1 Crowdsourcing task availability network structure comparison(ECML/PKDD-15)

表2 众包任务可用性网络结构对比(Uber)Tab.1 Crowdsourcing task availability network structure comparison(Uber)

首先,对于不同的网络结构,图6(a)、图7(a)展示了在两个数据集上,通过变换网络结构带来的模型性能的变化。如图6(a),面对复杂度不高的训练数据,结构a,b,d 表现接近,而结构c 过于复杂,需要更多轮迭代后才会达到理想的精度。随着数据复杂度的上升,结构b,d 对复杂数据的拟合不足,在初期出现了欠拟合问题,如图7(a)。

其次,对于不同的LR,图6(b)、图7(b)展示了在两个数据集上学习率的增减对模型性能的影响。过高的学习率容易使得权重参数在最优值之间来回震荡,无法收敛。

最后,图6(c)和图7(c)是BN 层对模型性能的影响。可以看到,没有BN 层的网络模型收敛速度慢甚至无法收敛,而加入BN 层的模型收敛速度明显更快。

图6 网络参数对性能的影响(ECML/PKDD-15)Fig.6 The effect of network parameter on performance(ECML/PKDD-15)

图7 网络参数对性能的影响(Uber)Fig.7 The effect of network parameter on performance(Uber)

3.3 众包服务持续性预测实验

在众包任务的可用性得到确认后,下一步即是对任务持续时间进行预测。首先需要对数据进行清洗工作,仅保留任务编号和任务持续时间,训练集和验证/测试集的比例为8 ∶2。对于ECML/PKDD-15 数据集,nepoch、LR、步长和隐藏层大小分别被设置为200、0.001、30 和32。对于Uber 数据集,nepoch、LR、步长和隐藏层大小分别被设置为200、0.000 1、20 和32。所有的模型均在RTX3060 6GB 上进行训练,参与对比的算法分别为MLP、初始化矩阵循环神经网络(Identity Matrix Recurrent Neural Networks,IRNN)、分层递归神经网络(Hierarchical Recurrent Neural Networks,HRNN)、文献[13]提出的DLSTM 网络结构、文献[14]提出的基于Resnet 的网络结构,实验结果如图8～10所示。

图8 众包服务持续性预测(1 min 内)Fig.8 Crowdsourced service persistence forecast(within 1 minute)

图9 众包服务持续性预测(2 min 内)Fig.9 Crowdsourced service persistence forecast(within 2 minute)

图10 众包任务持续性预测(3 min 内)Fig.10 Crowdsourced service persistence forecast(within 3 minute)

在图8 中,所有的方法精确度相差不大,但是本文提出的方法还是取得了最高的准确率。在图10 中,所有的实验方法的准确率均有所降低,其中基于MLP 的方法降幅最大,准确率只有0.76 和0.75,其次是基于IRNN 的方法,准确率分别是0.92 和0.71。

为了探究超参数对模型的精度的影响,本文设置了如下消融实验,网络参数如表3、4所示,不同结构的学习率、步长和隐藏层大小有所差异。其中,结构a 和e 是本文所使用的网络结构,实验结果如图11、12所示。

表3 众包服务持续时间网络结构对比(ECML/PKDD-15)Tab.3 Crowdsourcing service duration network structure comparison(ECML/PKDD-15)

表4 众包服务持续时间网络结构对比(Uber)Tab.4 Crowdsourcing service duration network structure comparison(Uber)

图11(b)、12(b)展示了学习率对模型性能的影响。可以发现,过大的学习率会使得数据在训练集上拟合程度变高,验证集上的泛化程度变差,出现过拟合问题。

图11(c)、12(c)展示了隐藏层大小对模型性能的影响,隐藏层大小的增加会使得模型提高对复杂时间序列的学习能力。多数情况下过强的学习能力会适得其反,使得模型学习到序列中的噪声,从而降低模型的泛化能力,使得验证集上同样出现了过拟合现象。

图11 网络结构对性能的影响(ECML/PKDD-15)Fig.11 The effect of network structure on performance(ECML/PKDD-15)

图12 网络结构对性能的影响(Uber)Fig.12 The effect of network structure on performance(Uber)

图11(d)、12(d)展示了步长规模对模型性能的影响。此时数据在训练集上的拟合程度变低,但是MSE 却没有显著提高。通过观察模型的拟合情况可以发现,此时模型已经失去了预测突变值的能力,预测的值多倾向于平缓。如果继续增加步长,模型的预测值最终会趋向于一条直线。

本文提出了一种基于深度学习的二阶段预测算法。第一阶段使用基于RepVGG 的网络进行任务可用性的预测,第二阶段使用基于LSTM 的网络进一步进行任务持续时间的预测,综合二阶段的预测结果,对即将到来的任务进行预分配。通过实验对比,本文所提出的算法在预测任务可用性上的准确度比传统的机器学习算法提高了32%,比同样基于深度学习的算法提高了14.2%,在预测任务持续性上的准确度相比其他算法提高了10.5%。大量实验表明了本文提出的算法的有效性和优越性,该算法有望在实际生活中得到使用。在实现过程中,一个重要的挑战是如何进行特征提取以提高预测性能。

推荐访问:算法 分配 阶段