基于QoS感知的Web服务推荐算法综述

高文斌　董晨辰　王 睿　胡谷雨

摘  要： 随着Web服务数量的迅速增长，服务过载的问题逐步显现。为了解决服务过载的问题，基于服务质量（Quality of Service，QoS）感知的服务推荐成为了服务计算领域的研究热点。从起初的基于协同过滤算法到目前基于深度学习的服务推荐算法，这些算法从各个角度提升着服务推荐的精度。文章以算法的改进过程为主线，对主要的服务推荐算法及其存在的弊端进行了分析与总结，并对未来服务推荐算法的发展进行了展望。

关键词： 服务质量; 服务过载; 服务推荐算法; 分析

中图分类号：TP393          文献标识码：A     文章编号：1006-8228（2022）03-01-04

Abstract： With the rapid growth of the number of Web Services， the problem of service overload has gradually emerged. To relieve service overload， the QoS-aware service recommendation has become a hot research topic in the field of service computing. Whether the original collaborative filtering algorithm or the current service recommendation algorithms based on deep learning， these algorithms applied in the field of service recommendation have been improving the accuracy of service recommendation from all angles. Taking the improvement process of the algorithm as the main line， this paper analyzes and summarizes the main algorithms of service recommendation and their disadvantages， and prospects the development of service recommendation algorithm in the future.

Key words： Quality of Service; service overload; service recommendation algorithm; analysis

0 引言

随着服务化理念的推广和面向服务的计算模式（SOC）的广泛应用，越来越多的企业选择为用户提供服务化的产品。作为面向服务的架构（SOA）最主流的实现方式，Web服务（Web Service，ws）的数量成指数级增长。Web服务模型中包含三个实体：服务提供者、服务注册中心、服务消费者。

图1显示了传统Web服务模型的基本结构。服务提供者将其提供的服务信息注册到服务注册中心，这一过程称为服务发布。服务发现指服务消费者向服务注册中心发送携带服务功能性需求的服务调用需求，服务注册中心通过检索服务数据库，为服务消费者匹配满足功能性需求的服务的过程。服务消费者从服务注册中心获取到服务的注册信息后，直接访问服务提供者提供的服务，无需再经过注册中心，这一过程称为服务绑定。

然而截至2021年6月29日，仅programableweb上发布的Web服务数量已经达到22200个。服务发现效率越来越低下，服务过载逐步显现。服务过载，意为通过常规的服务发现手段已经难以实现对服务有效的处理和利用。如何解决服务过载问题，帮助用户快速定位高质量（Qualityofservice，QoS）服务成为目前服务计算领域一个研究热点。推荐系统在电商、电影等易产生信息过载领域的成功，为服务计算领域的专家学者提供了解决服务过载的新思路。以服务推荐的方式替代服务发现过程，不仅可以解决服务过载的问题，更是一个由用户被动搜索转向用户定向主动推荐的过程。目前已经有一些学者对于服务推荐做过综述性研究，张等人[1]从服务推荐要解决的问题、面临的挑战、未来的发展等角度对服务推荐领域的研究成果做了综述;闫[2]等人对基于协同过滤的推荐算法做了综述。随着推荐算法的不断推陈出新，服务推荐算法也不再局限于协同过滤。本文将从推荐算法发展的角度对近十年的服务推荐算法作一个综述。

本文的组织结构如下：第1节介绍服务推荐所要完成的目标以及目前服务推荐算法的评价指标;第2节介绍基于协同过滤的服务推荐算法;第3节介绍基于矩阵分解的服务推荐算法;第4節介绍基于深度学习的服务推荐算法;第5节总结全文。

1 服务推荐目标及算法评价指标

表1显示的是用户和服务关于响应时间的QoS矩阵，称为“用户-服务”矩阵，也称为共现矩阵。表中的数值分别表示用户调用对应服务时的响应时间数据，“-”表示用户并未调用过该服务。基于QoS的服务推荐所要解决的问题便是预测出共现矩阵中“-”位置处的QoS数值，并以QoS值为排序指标，为用户推荐服务。

其中[fxi]表示待评估模型的预测值，[yi]表示样本真实值，m表示样本总数。MAE、RMSE的值越小，表示预测值与实际值之间的误差越小，模型的推荐性能越好。

2 基于协同过滤的服务推荐算法

协同过滤算法是最早应用在服务推荐领域的算法，以基于用户的协同过滤算法为例，其计算原理为：假设相似用户具有相似的喜好，在该假设的基础上，通过计算用户的相似群体完成推荐。用户[i，j]的相似度[sim（i，j）]的计算常用以下两种方法。

其中[θ]表示用户向量[i，j]之间的夹角。余弦相似度衡量了向量夹角的大小，由式⑶可见，夹角越小，余弦相似度越大。

其中，[Ri，p]表示用户[i]对物品[p]的评分，[Ri]代表用户[i]对所有物品的平均评分，[P]代表物品集合。与余弦相似度相比，皮尔逊相关系数通过用户平均分对独立评分进行修正，降低了用户评分偏置的影响。

基于协同过滤的服务推荐算法主要在服务推荐早期较多采用，Sarwar等人[2]提出了基于服务的协同过滤服务推荐算法IPCC，算法输入特征为服务，以服务为中心，应用皮尔逊相关系数计算服务的相似邻居，并将邻居服务推荐给用户。Shao[4]等人提出了基于用户的协调过滤服务推荐算法UPCC，算法的输入特征为用户，以用户为中心，应用皮尔逊相关系数计算用户的相似邻居，并将相似邻居调用过的服务推荐给中心用户。张等人[5]提出了基于混合协同过滤的Web服务推荐算法，算法中结合了基于用户的协同过滤和基于服务的协同过滤的共同优点，并设计了考虑用户个性化的Web服务推荐框架。张[6]等人认为用户的评价中存在部分恶意评价，其可信度有待考量，因此，他们提出了具有稳定性和可行评价的服务推荐算法，该方法通过“云模型”计算服务的稳定性，计算用户间的“反馈相似度”以剔除虚假用户评价，最后在稳定和可信的基础上为用户推荐服务。Adeli等人[7]认为用户和服务之间的依赖性和流行度对服务推荐精度有着重要的影响，因此，他们提出了基于流行度依赖的协同过滤服务推荐算法，通过引入“用户-服务”流行度依赖关系，提高算法在应对冷启动问题时的推荐精度。

3 基于矩阵分解的服务推荐算法

虽然基于协同过滤的服务推荐算法在服务推荐领域初期取得了优异的成效，但其仍然存在许多问题，其中最为严重的问题是：推荐结果的头部效应十分明显，且难以克服数据稀疏带来的推荐精度下降问题。为了解决这一问题，矩阵分解的方法被众多学者应用到服务推荐中。矩阵分解引入了“隐向量”的概念，增强了算法应对数据稀疏问题的能力。

矩阵分解的算法过程如图2所示，矩阵分解算法通过“用户隐矩阵”与“服务隐矩阵”的乘积拟合“用户-服务”矩阵，应用矩阵分解算法求解服务推荐问题的过程可归纳为：

对“用户-服务”矩阵[R=rm*n]，“用户隐矩阵”[U=um*k]，“服务隐矩阵”[V=vk*n]，通过优化目标函数：[minrui≠"-"（rui-uTivu）2]完成模型参数学习，而后通过训练好的“用户隐矩阵”与“服务隐矩阵”的乘积得到共现矩阵中所有QoS预测值并完成推荐。

在矩阵分解应用到服务推荐领域以后，服务推荐的精度获得了大幅度提高，唐[8]等人提出了基于位置聚类和张量分解的Web服务推荐算法ClustTD，该方法首先应用聚类算法，以位置信息为指标，分别对用户、服务聚类，而后对聚类所得用户向量、服务向量进行张量分解，再加权组合完成QoS值预测。Xu[9]等人提出了基于矩阵分解的上下文感知服务推荐算法LE-MF，为了解决冷启动的问题，LE-MF算法中引入了服务位置信息、用户位置信息，通过位置信息先完成用户聚类、服务聚类，通过聚类缩小“用户-服务”矩阵的体积，再通过矩阵分解完成服务QoS预测，并完成推荐。Yin等人[10]提出了基于网絡位置感知邻居选择的Web服务推荐QoS预测方法，与Xu等人不同的是，Yin等人没有使用用户、服务经纬度信息作为聚类指标，而是通过自治系统（AS）来获取用户、服务的网络位置，从而缩小求解空间，再通过矩阵分解的方法完成服务QoS预测。Qi等人[11]从服务推荐中的数据安全角度入手，他们认为算法中引入用户、服务的时空信息虽然可以提高推荐精度，但时空数据往往包含用户的敏感信息，因此他们提出了一种具有隐私保护的时空数据驱动的服务推荐，通过引入QoS数据的时空信息和位置敏感哈希技术，提高在使用时空数据时的安全性。Botangen等人[12]从矩阵分解方法的角度入手，通过改进算法的方式提升推荐精度，在引入地理位置信息的基础上，提出了一种基于概率矩阵分解的地理位置感知Web服务推荐算法。

4 基于深度学习的服务推荐算法

矩阵分解的引入虽然提高了服务推荐的精度，但是就矩阵分解算法本身，参与计算的特征数量只能是两个，对于其他上下文信息不友好，且难以克服冷启动带来的推荐精度降低问题。

随着AlexKrizhevsky于2012年提出AlexNet[13]，深度学习的大幕正式拉开，往后的时间里，其应用迅速地从图像领域扩展到语音领域，再到自然语言处理领域以及推荐系统领域。推荐系统进入深度学习时代后产生的大量优秀模型、算法也被众多学者引入服务计算领域，基于深度学习的服务推荐算法应运而生。

Xiong[14]等人提出了基于混合协同过滤的Web服务推荐，首先通过“词嵌入”方法将用户、服务的上下文信息编码成输入特征向量，将多个输入特征向量连接以后喂入全连接网络，网络输出为服务的QoS预测;Bai等人[15]提出了长尾Web服务推荐的深度学习框架，论文中对“长尾服务”的定义为自发布以来，被调用次数低于5次的服务，他们通过论证得出随着服务数量的增长，用户越发倾向于长尾服务，提高长尾服务的推荐效率可以很大程度提高用户的体验。他们使用堆叠自编码器分别提取用户、服务特征，而后通过矩阵分解的方法实现QoS的预测。实验证明，他们的方法可以有效改善传统方法导致的头部效应问题。唐等人[16]从特征交叉角度入手，提出基于一阶因子分解机的质量感知Web服务推荐算法，该方法在逻辑回归基础上，加入非线性的一阶特征交叉，提升了算法的学习能力。实验表明他们的方法比传统线性特征学习的方法效果提升很多。但是由于算法复杂度限制，因子分解机难以实现特征的二阶交叉，随着特征数的增加，二阶特征交叉会产生“参数爆炸”的问题。曹等人[17]考虑到基于因子分解的方法无法实现特征的高阶交叉，将DeepFM方法引入服务推荐领域，该算法首先应用SOM神经网络进行聚类，而后对于聚类结果喂入DeepFM网络，最终输出服务QoS的预测数据。

5 总结

从起初基于协同过滤到目前基于深度学习，服务推荐算法的发展可以总结为围绕以下两个核心点进行突破：

⑴ 增加及优化输入特征，增加算法中的先验知识;

⑵ 实现特征之间的高阶交叉，提升算法的学习能力。

硬件能力的不断提升，使更多的特征可以被喂入网络而不用担心计算能力;深度学习带来更深层的特征之间的交叉学习，使得模型的泛化能力以及特征表达能力不断增强，未来的服务推荐领域将继续在这两个方面努力。

参考文献（References）：

[1] 张秀伟，何克清，王健，等.Web服务个性化推荐研究综述[J].计算机工程与科学，2013，35（9）：132-140

[2] 闫红丹，杨怀洲.Web服务QoS预测与主动推荐方法综述[J].智能计算机与应用，2019，9（1）：199-202

[3] B. Sarwar， G. Karypis， J. Konstan， and J. Riedl， "Item-based collaborative filtering recommendation algorithms，"[C] Proc. International Conference on World Wide Web， ACM Press，2001（5）：285-295

[4] L. Shao， J. Zhang， Y. Wei， J. Zhao， B. Xie and H. Mei，"Personalized QoS prediction for Web Services via collaborative filtering，"[C] IEEE International Conference on Web Services， Salt Lake City， UT，2007.7：439-446

[5] 张雪洁，王志坚，张伟建.基于混合协同过滤的个性化Web服务推荐[J].计算机科学与探索，2015，9（5）：565-574

[6] 张永胜，樊悦芹，郑志华，等.考虑稳定性与可信评价的云服务推荐网络研究[J].小型微型计算机系统，2018，39（1）

[7] S.Adeli， P.Moradi QoS-based Web Service Recommenda-tion using Popular-dependent Collaborative Filtering[J].Joural of AI and Data Mining，2020，8（1）：83-93

[8] 唐妮，熊庆宇，王喜宾，等.基于位置聚类和张量分解的Web服务推荐算法[J].计算机工程与应用，2016（15）：65-72

[9] Xu Y ， Yin J ， Deng S ， et al. Context-aware QoSprediction for Web Service recommendation and selection[J]. Expert Systems with Applications，2016（53）：75-86

[10] Yuyu Yin，Song Aihua，Gao Min，et al.QoS Prediction for Web Service Recommendation with Network Location-Aware Neighbor Selection[J]. International Journal of Software Engineering and Knowledge Engineering，2016，26（4）：611-632

[11] Qi L， Zhang X， Li S， et al. Spatial-Temporal Data-driven Service Recommendation with Privacy-preservation[J]. Information Sciences，2019：515

[12] Botangen K A， Yu J， Sheng Q Z， et al. Geographic-aware Collaborative Filtering for Web Service Recommendation[J]. Expert Systems with Applications，2020，151：113347

[13] ImageNet Classification with Deep Convolutional Neural Networks[J].Advances in neural information processing systems，2012，25（2）

[14] Xiong R，  Wang J，  Zhang N， et al. Deep Hybrid Collaborative Filtering for Web Service Recommendation[J]. Expert Systems with Applications，2018，110：191-205

[15] B. Bai， Y. Fan， W. Tan and J. Zhang， "DLTSR： A Deep Learning Framework for Recommendations of Long-Tail Web Services，"[C]IEEE Transactions on Services Computing，2020，13（1）：73-85

[16] 唐明董，張婷婷，杨亚涛，等.基于因子分解机的质量感知Web服务推荐方法[J].计算机学报，2018，41（6）：1300-1313

[17] 曹步清，肖巧翔，张祥平，等.融合SOM功能聚类与DeepFM质量预测的API服务推荐方法[J].计算机学报，2019（6）：1367-1383