基于低秩张量补全的QoS数据预测技术研究
来源:用户上传
作者:王凤伟 董庆义
摘要：随着网络服务的发展，具有相同或相似功能的Web服务逐渐增多。基于服务质量（Quality of Service，QoS） 向用户推荐优质的服务已成为主要标准。因此，有效预测Qos数据的缺失值为用户推荐Web服务成为亟须解决的问题。该文针对QoS数据预测问题引入了一种基于低秩核范数张量补全方法。该方法通过构建张量来表示多元的 QoS 数据。利用核范数近似秩最小化来挖掘QoS数据之间的相关性。最后通过交替方向乘子法迭代优化得到预测结果。同时，在真实的数据集WS-Dream上进行了大量的实验验证。
关键词：QoS 预测；Web服务；张量补全；协同过滤
中图分类号： TP301 文献标识码：A
文章编号：1009-3044（2022）28-0053-03
1 引言
近年来，Web服务的QoS数据缺失预测问题受到广泛关注，被认为是服务选择和服务推荐的关键。随着物联网的快速发展，Web服务数量逐渐增多，用户对功能相似的Web服务无法分辨，面对多种服务难以抉择。由于Web服务的QoS数据值是缺失的，是无法根据缺失的QoS值为用户推荐高质量服务。而且，由于不同的用户在不同的服务调用环境存在着极大的差异，使得QoS属性值变得不稳定。所以，精确地预测Web服务的QoS数据缺失值是非常必要的，这能够便于用户进行服务选择，也可以通过QoS数据向用户推荐高质量的服务。帮助用户在大量的服务中选择最合适的服务。
基于 QoS 数据向用户推荐服务直接取决于 QoS 数据的预测精度。其中，在各种 QoS 预测方法中，协同过滤方法 （Collaborative Filtering CF） 是解决QoS预测的问题有效方法。协同过滤方法分为两类：基于邻域的和基于模型的[1]。基于邻域的f同过滤方法只是基于历史相似的用户或服务来预测 QoS 数据缺失值。然而，在真实的 Web服务平台调用环境中，QoS 数据往往高度稀疏，难以基于历史相似的用户和服务进行预测。基于模型的CF方法的矩阵分解方法是通过学习潜在因子得到两个低维目标矩阵。尽管基于矩阵分解的QoS预测方法总体上优于传统基于邻域的QoS预测方法，但仍存在一些不足。没有考虑时间因素对QoS数据的影响，只是考虑了“用户-服务”二者的关系。考虑到严重影响 QoS 数据的时间因素，需要引入张量数据模型来对现有 QoS 数据进行建模。
针对QoS数据缺失值预测问题，本文受到文献[2]中对时空交通流量数据预测的启发。首先，基于现有 QoS 数据的整体结构进行数据三阶张量建模。针对此数据模型提出了基于低秩核范数张量补全的CF预测方法。因为张量秩最小化问题通常是 NP-hard [3]，所以引用核范数近似秩最小化求解。本文的主要贡献总结如下：
（1） 为了更好地表达复杂多元的QoS数据，针对时间信息的作用，本文在先的二阶“用户-服务”的基础上加入时间的维度构成三阶张量表达Qos值，此QoS数据张量能够很好地表达Qos数据的复杂三元关系。
（2） 提出QoS数据低秩张量补全（Low-Rank Tensor Completion，LRTC） 预测方法预测Qos数据缺失值，该方法通过核范数近似张量秩最小化求解，以此挖掘QoS数据之间的相关性提高预测精度。最后利用交替方向乘子（Alternating Direction Method of Multiplies， ADMM）法进行迭代优化。
（3） 本文提出基于低秩张量补全预测方法在公开的大规模的数据集WS-Dream上进行了实验评估。经过实验对比，本文提出的QoS数据预测模型的实验结果优于其他对比基线。
2 QoS预测技术原理
2.1 QoS 数据模型
通常情况下用户调用服务时是需要时间的积累，用户调用的服务的 Qos 值会被记录下来形成一系列的 Qos 数据集。基于现有的研究工作，具体构建QoS数据模型张量步骤如下[4]。
步骤一：获取用户所记录的所有的 QoS 数据值集合[<user，service，time，value>]。
步骤二：通过QoS数据记录四元组中的[<user，service，0，value>]构造一个“用户-服务”的矩阵[R（0）]，将在时间间隔0处的[U]个用户作为矩阵行，[S]个服务作为矩阵列。同理，时间间隔从1到[k]构造出[k]的矩阵。
步骤三：根据QoS数据记录四元组中的[<user，service，time，value>]填充对应的QoS值在矩阵中。
步骤四：按照时间间隔将矩阵进行叠加构造张量[Y∈?U×S×T]，其中“用户-服务”矩阵是张量的每一个切片。
2.2 低秩张量补全方法
低秩张量补全方法用于解决高维数据的缺失数据已经变得成熟。我们受到低秩矩阵数据补全[5]和张量低秩补全在交通流量数据预测的启发，将张量低秩补全扩展应用到Web环境中QoS数据缺失值预测问题上。
针对2.1节构建的QoS数据张量模型，提出了QoS数据低秩张量补全预测方法，该方法通过张量秩近似最小化能确保QoS数据的全局一致性和局部一致性。秩最小化已被证明是利用结构数据中固有的相关性和依赖性的有力工具。具体QoS数据预测优化模型如下：
[minY：rank（Y） s.t. ： PΩ（Y）=PΩ（T）] （1）
其中[Y]表示缺失的低秩张量，[rank（Y）]表示张量[Y]的张量秩，张量秩最小化问题通常是 NP-hard，于是将QoS预测模型（1） 转化为：
nlc202212021015
[minY：Y* s.t. ： PΩ（Y）=PΩ（T）] （2）
其中[Y*=k=13αkY（k）*]是张量的核范数，张量的核范数具体定义为沿每个张量模式展开所有矩阵的核范数之和[3]。[k]表示张量展开的第[k]模矩阵，[αk]表示张量展开的权重参数。
2.3 ADMM优化
LRTC方法采用交替方向乘数法（Alternating Direction Multiplier Method， ADMM） 进行迭代优化。ADMM算法是解决约束最小化问题的经典方法。推导出公式（2） 的增广拉格朗日函数：
[LY（k），T（k）3k=1，λ=k=13αkY（k）*+ρ（k）2Y（k）-T（k）2F+λ，Y（k），T（k）] （3）
其中[ρ]是ADMM的学习率。分别依次迭代求解变量[Y]和[T]得出最终结果。
3 实验数据与研究分析
在本节中，本文对提出的QoS数据预测算法LRTC进行了实验评估。实验分析张量密度对实验结果的影响并与其他预测方法进行了比较。为了保证避免实验的结果的偶然性，把每组实验在同一数据集进行了10次实验验证。
3.1 数据集
本文采用公认的大规模数据 WS-Dream 进行实验，数据集记录着 142 个用户在 64 个间隙中调用 4532 个服务产生的QoS属性值[4]。本文主要研究QoS数据中具有代表性的响应时间（Response Time） 和吞吐量（Throughput） 两个属性。响应时间定义为服务用户发送请求和接收响应之间的持续时间。吞吐量定义为每秒成功消息大小的平均速率。Qos数据的吞吐量的平均值是9.609kbps，应时间的平均值是3.165s。 为符合真实Web环境下QoS数据稀疏的问题，本文将随机剔除数据保证其QoS数据的稀疏性。如表1对原有数据集进行了预处理。将训练数据集的密度设置在10% 至 30% 之间，每次递增 5%。
3.2 参数设置
对于LRTC预测框架中的参数要进行初始化，权重参数[αk]和ADMM中学习率[ρ]，这两个参数会直接影响整个模型预测指标的性能。对于参数的选择采用交叉验证确定，ADMM框架中学习[ρ]参数它决定了整个模型的收敛性。较大的数值通常会减慢收敛过程，而较小的数值则会让模型在几次迭代中满足收敛。在吞吐量和响应时间的两个Qos属性数据集设置为[ρ=1×10-4] ，迭代次数设置为30能达到收敛。根据先验经验将权重参数[αk]设置为使用相同的权重遵循张量核范数进行展开。
3.3 实验分析
在本小节中，我们对真实世界的 Qos 数据进行广泛的实验以评估低秩张量补全方法，数据集有两个属性响应时间和吞吐量。使用的评价指标为通用的平均绝对误差（Mean Absolute Error， MAE） 和均方根误差（Root Mean Squared Error， RMSE） [6]。通常情况下预测方法的MAE和RMSE的值越小，说明预测方法精度越高。
本文选择与两种个经典预测方法在数据密度缺失率不同的情况进行实验对比。
UIPCC[7]：一种结合了UPCC和IPCC的CF预测方法。利用历史用户和服务的相似度进行最终预测。
PMF[8]：利用高斯假设分解用户服务 QoS 矩阵来预测缺失值。
实验结果表明，预测精度与QoS数据张量密度缺失有很大的关联。从图1可以清楚地看出，将训练张量的密度从10%变化到30%，以5%为步长增加。图1（a）和 1（b）为Response Time的MAE值和RMSE值结果。图1（c）和 1（d）是Throughput的MAE值和RMSE值结果。实验分析得出：
（1） 随着训练密度的增加，LRTC方法的性能增强，说明QoS数据越多，预测效果越好。此外还能看出基于邻域的UIPCC预测方法的预测精度低于基于模型的PMF预测方法，是因为UIPCC太依赖于用户和服务的历史记录值，但是通常情况下在Web环境下所记录的QoS 数据是高度稀疏的。
（2） 另外，本文提出的LRTC方法的预测精度始终高于UIPCC和PMF方法。产生这种现象的原因是UIPCC和PMF方法两者都只考虑了QoS数据的“用户-服务”二阶静态关系，而没有考虑QoS数据中“用户-服务-时间”模型中更有用的时间信息。即实验结果表明，构造张量模型能够表达出QoS数据复杂的多元关系。
（3） 此外，对于利用矩阵因子模型PMF预测方法，其分解过程中没有太关注分解所带来的数据丢失，造成了预测精度比预想结果要差许多。LRTC方法采用了核范数低秩近似张量补全的方法，避免了数据丢失问题，并使得局部数据相关性得到提高，所以LRTC方法的预测精度优于其他对比基线。
4 结束语
在真实Web环境下为了更好地表达出 QoS 数据的结构全局性，本文针对原有 QoS 数据模型上引入了时间维度信息将传统的“用户-服务”二阶矩阵构建成三阶 QoS 数据张量“用户-服务-时间”。 针对QoS数据张量模型，为了能提高QoS数据预测精度；通过LRTC方法预测数据的缺失值，该方法引入张量核范数低秩近似能捕获不同用户和不同服务之间的数据局部相关性。最后基于乘子交替方向法的框架求解各变量的最优解，从而得到预测张量来填补缺失值。同时，在公开的大规模的数据集WS-Dream上进行了实验评估。经过实验对比，本文提出的QoS数据预测模型的实验结果优于其他对比基线。
参考文献：
[1] 刘珍珍，杨怀洲.综合时空信息的Web服务QoS预测方法研究[J].电脑知识与技术，2021，17（18）：233-235.
nlc202212021015
[2] Chen X Y，Lei M Y，Saunier N，et al.Low-rank autoregressive tensor completion for spatiotemporal traffic data imputation[J].IEEE Transactions on Intelligent Transportation Systems，2022，23（8）：12301-12310.
[3] Song Y，Li J，Chen X，et al.An efficient tensor completion method via truncated nuclear norm[J].Journal of Visual Communication and Image Representation，2020，70：102791.
[4] Chen Y P，Zhang Y Q，Xia H，et al.A hybrid tensor factorization approach for QoS prediction in time-aware mobile edge computing[J].Applied Intelligence，2022，52（7）：8056-8072.
[5] Han Z F，Leung C S，Huang L T，et al.Sparse and truncated nuclear norm based tensor completion[J].Neural Processing Letters，2017，45（3）：729-743.
[6] Haihong E，Tong J J，Song M N，et al.QoS prediction algorithm used in location-aware hybrid Web service[J].The Journal of China Universities of Posts and Telecommunications，2015，22（1）：42-49.
[7] Zheng Z B，Ma H，Lyu M R，et al.QoS-aware web service recommendation by collaborative filtering[J].IEEE Transactions on Services Computing，2011，4（2）：140-152.
[8] Mnih A， Salakhutdinov R. Probabilistic matrix factorization[C]//NIPS'07： Proceedings of the 20th International Conference on Neural Information Processing Systems. December 3-6， Vancouver Canada， 2007： 1257-1264.
【通编辑：梁书】
nlc202212021015
转载注明来源:https://www.xzbu.com/8/view-15442876.htm
