综合时空信息的Web服务QoS预测方法研究

    刘珍珍 杨怀洲

    

    

    

    摘要：随着Web服务技术的发展，网络中涌现出很多功能性属性相同或相似但非功能性屬性如QoS具有明显差异的Web服务。如何选择最佳的Web服务构建满足用户QoS需求的Web应用成为一个极具价值的研究课题[1]。时间和空间因素是影响Web 服务的QoS属性的主要因素，在实际应用中，时空信息不同Web服务的性能有很大差异。该文针对综合时空信息的Web服务QoS预测方法进行了综合对比分析，总结了当下QoS预测方法的研究趋势和发展前景。

    关键词：Web服务;QoS预测;协同过滤;矩阵分解;个性化推荐

    中图分类号：TP301? ? ? 文献标识码：A

    文章编号：1009-3044（2021）18-0233-03

    开放科学（资源服务）标识码（OSID）：

    1 背景

    Web服务的QoS属性是选取最佳候选服务时需要考虑的关键性因素，是动态服务发现、查询、选择和主动推荐的基础，通常用来体现Web服务的非功能特性。由于在实际应用中，Web服务数量非常多，用户对大多数服务并不了解，因此Web服务的QoS属性值不完整。而且，不同用户的网络环境及服务运行环境均存在差异，QoS属性表现得很不稳定。因此预测活动用户缺少的QoS值非常必要，不仅能更好地进行服务推荐，还便于用户进行服务的选择。Web服务的QoS性能与用户地理位置高度相关，QoS性能受网络距离及各自的网络环境的影响。同时，Web服务的QoS性能与调用时间高度相关，网络环境以及服务状态会随时间而变化。互联网上不同用户调用同一Web服务时，感受到的服务性能也不同。通过综合时空信息进行QoS预测不仅可以对Web服务的多个QoS属性进行合理的综合评价，还可以准确地预测 QoS值，帮助用户选择在海量的Web服务中选择最合适的服务，完成服务的个性化推荐。

    2 Web服务QoS主要预测方法说明

    2.1 基于内容（content-based）的预测方法

    基于内存的预测算法使用用户服务数据库的整个或一个样本来生成预测。这种算法易于实现且效率很高，直观易懂、更容易解决冷启动问题、容易落地到真实的业务场景中，但推荐精准度不太高，且无法扩展。基于内容的推荐算法有很多的应用实例，比如今日头条中有很大比例是基于内容的推荐算法。

    2.2 基于协同过滤（collaboration filtering）的预测方法

    1）基于历史记录（memory-based）的CF算法

    基于用户的协同过滤算法是通过对邻居用户的QoS信息进行分析生成待推荐服务，然后为目标用户推荐其相似用户喜欢的服务。此算法首先计算用户间相似度，然后选择目标用户近邻，最后基于用户近邻预测QoS值。近邻筛选通常用Top-K 近邻选择算法。

    基于服务项的协同过滤算法是通过用户对相似服务的QoS信息进行分析，然后预测目标服务项的QoS值，最后为用户推荐喜欢及相似的服务。其过程与基于用户的CF算法类似。

    基于混合的协同过滤算法是将基于用户和基于Web服务的CF算法结合，提出了混合的推荐系统来预测缺失的QoS值。后来有许多学者通过调整参数改变基于用户的CF算法和基于Web服务项的CF算法对不同数据集的依赖程度，不仅提升了信息的利用价值，还提高预测的准确度。

    基于历史记录的CF算法是使用现有的数据进行预测，是一种启发式算法。这种算法虽然计算简单，但由于QoS值的不完整性和不稳定性，存在QoS矩阵稀疏性和在处理大量数据时的时效性等问题。同时，该算法对历史数据集的依赖性比较大，存在一定的局限性，例如冷启动问题，忽略了网络环境等外部因素的影响。

    2）基于模型（model-based）的协同过滤算法

    近年来，随着机器学习的兴起，已有学者提出多种基于模型的协同过滤方法，除了可以克服QoS矩阵极度稀疏和在处理大量数据时的时效性等问题，在推荐效果以及算法可行性方面均有突破。基于模型的协同过滤是通过各种机器学习算法对历史QoS数据进行训练得到一个学习模型，再使用此学习模型进行QoS预测。目前，基于模型的CF算法有矩阵因子模型、聚类模型、潜在语义模型、贝叶斯模型等。下面我主要介绍基于矩阵分解（MF）的各个模型（如表1所示）。

    矩阵分解是协同过滤是目前使用很广泛的一种方法，它的核心思想是将矩阵分解成两个低维度矩阵，分解后的两个特征矩阵突出了重要特征，减少了一些无关因素的干扰，可以更好地挖掘用户与服务间的关系，进一步提高预测的准确性。常用两种矩阵分解的技术如表2所示。

    3 综合时空信息预测关键技术

    由于时空因素对Web服务的QoS性能有一定影响，为此众多学者对加入空间信息和时间信息的预测方法都做了不少的研究，并取得了一定的成果。

    3.1 空间信息的研究

    部分研究工作注意到用户的地理位置对于QoS属性值的影响，即网络环境与地理位置存在差异的用户调用相同的 Web 服务时，QoS记录可能不同。例如Zheng[2]等人认为 QoS 受到地理位置以及网络环境的影响比较大，提出了一种基于邻域综合矩阵分解（NIMF）的个性化Web服务QoS值预测方法。通过融合基于邻域和基于模型的协同过滤方法，探索用户过去的Web服务使用情况，以获得更高的预测精度。P.He[3]等人针对QoS预测方法预测精度上不足的问题，提出了一种基于位置的层次矩阵分解（HMF）方法。根据用户的位置将用户和服务分为多个组，使用全局QoS矩阵和基于位置的局部QoS矩阵对HMF模型进行分层训练，将两者紧密结合来预测丢失的QoS值。实验表明，此方法较之前的算法预测精度更高。有研究者针对数据稀疏，Web服务QoS预测精度不高，算法可扩展性的问题，增加网络位置正则项来预测用户的QoS值，根据用户功能需求对待推荐服务进行排序，然后选择最合适的服务进行推荐。实验表明，该方法不仅在预测精度上优于目前主流的推荐算法，可以在一定程度上解决数据稀疏和可扩展性差的问题。还有学者针对冷启动，QoS数据中存在异常值的问题，提出了以矩阵分解为基础的服务推荐模型：LA-LFM和LA-PMF。这种模型加入Web服务隐式反馈因子，根据用户网络位置特征进行聚类分析，在数据稀疏的情形下，预测精确度要比一些经典方法更好。X等人从概率的角度出发，提出了改进的矩阵分解模型，即基于位置的概率矩阵分解模型（PMF），并在真实QoS数据集进行了验证。在Netflix竞赛中，PMF模型取得了较好的成绩。

    3.2 时间信息的研究

    T.Chen[4]等人为了有效地解决基于特征的矩阵分解问题，设计了SVD特征，构建包含时间动态、层次信息和邻域关系等边信息的因子分解模型。通过对模型的改进，提出了SVD Feature模型，并且用于Twitter的好友推荐系统。C.Zhou[5]等人针对数据稀疏以及Web服务的QoS值可能会随着时间推移而改变的问题，提出了一个考虑时态信息的Web服务推荐框架。针对包含用户、服务和时间等多维信息的模型，提出了一种Tucker分解方法，将QoS值数据视为张量，将其转化为张量分解问题。同时为了处理具有服务质量价值的动态数据流，引入了一种可扩展的、节省空间的增量张量因子分解（ITF）方法。实验结果表明，该方法在效率和准确度上优于其他方法。除此之外，有些学者针对缺乏时间信息导致的静态性模型问题，提出一个能够处理用户服务时间模型三元关系的非负张量分解（NTF）算法，将二维用户服务矩阵扩展为一个由三维张量表示的更复杂的用户服务时间三元关系，核心思想是考虑不同时刻QoS值的差异，用用户服务时间交互关系代替MF中的用户服务矩阵，利用张量将MF模型扩展到三维空间，采用非负张量分解方法来提高考虑时态信息的QoS感知Web服务推荐性能，进一步的提高的预测的精度。

    通过大量研究，基于矩阵分解的协同过滤算法在大规模数据稀疏的情况下预测效果更好，加入时空信息能更好地提高预测的准确性，提升服务推荐的性能，但其算法复杂度较高，更适合离线计算。

    4 结束语

    由此可见，基于矩阵分解的协同过滤算法在研究综合时空

    信息的Web服务QoS预测值得进一步研究。基于模型的CF算法能更加全面的考虑QoS信息，丰富时空信息，提高了QoS值完整性及预测精确度，不仅能提升推荐质量，还可以实现准实时预测。然而，随着Web服务数量激增以及用户要求的不断提高，综合时空信息的Web服务QoS预测方法还要有很多改进的空间。冷启动问题、相似度的计算方法以及预测模型的效果及时间复杂度等都需要进一步的深入研究和改善。

    参考文献：

    [1] 唐妮.基于位置聚类和张量分解的Web服务推荐研究与应用[D].重庆：重庆大学，2016.

    [2] Zheng Z B，Ma H，Lyu M R，et al.Collaborative web service QoS prediction via neighborhood integrated matrix factorization[J].IEEE Transactions on Services Computing，2013，6（3）：289-299.

    [3] He P J，Zhu J M，Zheng Z B，et al.Location-based hierarchical matrix factorization for web service recommendation[C]//2014 IEEE International Conference on Web Services.June 27 - July 2，2014，Anchorage，AK，USA.IEEE，2014：297-304.

    [4] Chen T，Zhang W，Lu Q，et al.SVDFeature：a toolkit for feature-based collaborative filtering[J].Journal of Machine Learning Research，2012，13（1）：3619-3622.

    [5] Zhou C，Zhang W C，Li B.Web service recommendation via exploiting temporal QoS information[C]//Algorithms and Architectures for Parallel Processing，2014：15-27.

    【通聯编辑：谢媛媛】