基于受限玻尔兹曼机的Web服务质量预测方法

王兴菲，万健, 3，陈璐，殷昱煜，俞立峰



基于受限玻尔兹曼机的Web服务质量预测方法

王兴菲1, 2，万健1, 2, 3，陈璐1, 2，殷昱煜1, 2，俞立峰4

(1. 杭州电子科技大学计算机学院，浙江 杭州，310018；2. 复杂系统建模与仿真教育部重点实验室，浙江 杭州，310018；3. 浙江科技学院 信息与电子工程学院，浙江 杭州，310023；4. 杭州核新同花顺网络信息股份有限公司，浙江 杭州，310023)

针对协同过滤算法无法有效处理数据稀疏的问题，提出1种基于受限玻尔兹曼机的Web服务质量(QoS)预测方法；第1阶段使用受限玻尔兹曼机模型对所有缺失的QoS值进行预测，并对原始的QoS矩阵进行填充；在第2阶段基于该QoS矩阵进行全局邻居筛选，同时将受限玻尔兹曼机引入到用户近邻的协同过滤模型中，以预测目标QoS值。研究结果表明：该方法能提高QoS预测精确度，在一定程度上降低数据稀疏对预测的影响。

Web服务；服务质量预测；协同过滤；受限玻尔兹曼机

Web服务分为功能性属性和非功能需属性，其中，服务质量(quality of service，QoS)通常用来描述非功能属性[1]。基于QoS的Web服务预测是服务推荐的重要基础[2]。随着互联网技术不断发展，功能相似的Web 服务数量大量增加，如何提高QoS预测精度进行有效的Web服务推荐是服务推荐领域的热点问题。目前，协同过滤由于具有简易性而受到了广泛关注[3]。在服务推荐领域，许多研究者开始将协同过滤应用于QoS预测[2]，并取得了较好的效果。传统协同过滤算法主要分为基于近邻和基于模型2类[4]。基于近邻的协同过滤算法具有很好的可解释性以及较高的预测精确度，但无法有效处理数据稀疏情况[5]。由于数据稀疏，基于近邻的协同过滤算法无法准确地获取相似邻居进而无法进行精确预测，因此，人们提出基于模型的协同过滤。目前，基于模型的协同过滤算法包括奇异值分解(singular value decomposition, SVD)模型[6]以及基于受限玻尔兹曼机(restricted Boltzmann machine, RBM)的无向图模型[7]。奇异值分解模型通过降低矩阵维度进行模型学习，对稀疏问题并不敏感。近年来，RBM模型因其具有有效的特征提取能力和泛化能力以及较强的可靠性，在推荐系统领域受到较大的关注。在数据稀疏情况下，RBM能根据历史行为提取有效的目标特征进行预测。但是，RBM需要从全局进行训练，在预测中易产生局部最优而影响预测精度。基于近邻的协同过滤虽是从局部中学习，但数据稀疏会导致其无法获得准确的局部信息来进行精确预测。本文作者将两者融合，提出一种基于受限玻尔兹曼机的Web服务QoS预测算法；通过训练基于RBM的协同过滤模型提取目标近邻的特征，将目标特征用于第1阶段预测，利用这些预测结果填充用户服务矩阵以降低数据稀疏的影响；在第2阶段，利用重新形成的用户服务矩阵进行全局筛选，并使用基于RBM与用户近邻融合的协同过滤模型预测得到最终QoS结果。

1 基于受限玻尔兹曼机的Web服务QoS预测

1.1 基于受限玻尔兹曼机的Web服务QoS预测框架

基于受限玻尔兹曼机的Web服务QoS预测算法框架如图1所示。由图1可知：在第1阶段，该方法使用基于RBM的协同过滤模型进行预测，并将其结果填充于用户服务矩阵，缓解了数据稀疏问题。在第2阶段，通过重新形成的用户服务矩阵进行全局筛选，使用基于RBM与用户近邻融合的协同过滤模型进行预测，最终得到QoS预测结果。

1.2 第1阶段预测

RBM是一种无监督的、具有2层结构、对称连接且无自反馈的随机神经网络模型。该网络模型可以视为1个无向图，由一些可见单元(对应可见变量，即训练数据集项目数)和一些隐藏单元(对应隐藏变量，可视为特征提取器)构成。只有可见单元和隐藏单元之间才会存在边，可见单元之间以及隐藏单元之间都不会有边连接。RBM模型是一种基于能量的模型，能量最小化时网络达到理想状态，而网络的训练就是最小化其能量函数。

图1 基于受限玻尔兹曼机的Web服务QoS预测框架图

基于受限波尔兹曼机模型的协同过滤模型如图2所示。该模型将可见单元转化为1个维的0−1向量单元。其中，表示评分范围，将用户评分所在的分量置为1，其余分量置为0。其次，对于没有评分的数据用单元表示，且这类单元不与隐藏单元连接，可将其视为分量全为0的向量单元。

图2 基于受限波尔兹曼机的协同过滤模型图

本研究中，由于用户服务矩阵中的QoS值为浮点数，考虑到RBM需要的为整数，由QoS值四舍五入得到。在本文采用的数据集中，范围为[0, 1, …, 20]。

该模型的能量函数为

由于RBM层间全连接，层内无连接，可见单元和隐藏单元之间是独立的特殊结构。当给定可见单元时，各个隐藏单元的激活概率之间是相互独立的；反之，当给定隐藏单元时，各个可见单元的激活概率之间也是相互独立的，且RBM结构是对称的，因此，根据得到的可见单元和隐藏单元可以分别得到第个隐藏单元和第个可见单元的激活概率：

HINTON[8]提出了基于对比散度的快速学习算法(contrastive divergence，简称CD算法)。有了以上条件概率，就可以直接使用CD算法训练RBM，其中各参数的更新准则如下：

模型训练好后，若用户调用服务的QoS值已知，则该用户调用服务的QoS值为的概率可直接通过公式求出。根据RBM预测当前用户调用服务的QoS值为

1.3 第2阶段预测

在第2阶段预测中，首先利用填充后的QoS矩阵全局筛选相似邻居，然后通过基于RBM与用户近邻的协同过滤模型预测最终QoS结果。

1.3.1 相似度计算

1.3.2 全局筛选

全局筛选相似邻居流程图如图3所示。传统的协同过滤算法仅仅使用有调用目标服务记录的用户作为相似邻居，忽略了具有较高相似度但有未调用目标服务记录的用户以及具有相同网络位置的用户，导致基于近邻协同过滤算法在数据稀疏的情况下筛选邻居不准确。为了提高筛选准确率，本文作者在相似度的基础上利用网络位置信息与RBM预测结果进行进一步筛选。

网络位置信息包括自主网络系统(autonomous system, AS)与国家。将具有相同AS的用户聚类为1组，称为AS用户组；再将具有相同国家的用户聚类为1组，称为国家用户组。在基于相似度筛选的基础上，将处于同一AS或是同一国家的用户视为相似 邻居。

通过第1阶段预测，QoS矩阵得到了填充，缓解了由于数据稀疏性而无法得到准确近邻的问题。在第2阶段预测中，利用通过填充后的QoS矩阵进行全局筛选，充分考虑了具有较高相似度但有未调用目标服务记录的用户。

最后，通过加入网络位置信息的全局筛选结果得到最终的相似邻居集合()，()包括原始未调用目标服务记录的用户1()以及原始有调用目标服务记录的用户集合2()。

1.3.3 基于受限玻尔兹曼机与用户近邻的QoS预测方法

由于QoS值属于离散分布，而RBM需要从全局进行训练，在预测中易产生局部最优。基于近邻的协同过滤虽是从局部中学习，但因为数据稀疏而无法获得准确的局部信息，为此，本文作者提出基于RBM与用户近邻的QoS预测方法，并构建基于RBM的Web服务QoS预测模型。

首先基于用户近邻的协同过滤算法，根据TopK算法选择与目标用户最为相似的用户邻居集合，记为N()。其次，通过该目标用户的相似邻居集合对目标服务的历史行为预测目标用户对目标服务的行为。基于用户近邻的协同过滤算法表达式为

在基于用户近邻协同过滤算法的基础上，构建基于RBM的Web服务QoS预测模型：

最后，将所得模型命名为基于受限玻尔兹曼机的Web服务QoS预测模型(RBMCF)。

2 实验分析

2.1 数据集

实验采用WSDream公开数据集[9]。该数据集包括5 825个服务和339个用户，以及2个服务质量属性即响应时间和吞吐量。本文使用其中的响应时间数据集，该数据集被广泛用于QoS预测准确度评估，因此，基于该数据集的实验是可信且可靠的。

2.2 评估标准

实验采用平均绝对误差MAE，即计算预测值与实际值的平均误差来评估系统的推荐质量，MAE越小，则预测的准确率越高。MAE的计算公式如下：

同时使用归一化平均绝对误差NMAE来进一步衡量算法的预测准确度。归一化平均绝对误差的计算公式如下：

式中：t为测试集；为测试集中待预测服务质量的个数；(,)为测试集中待预测服务质量的(用户，服务)对。平均绝对误差和归一化平均绝对误差越小，表示预测准确度越高。

2.3 实验环境设置

在真实环境下，用户服务矩阵是非常稀疏的，用户通常只调用少部分服务，不同用户之间重合的服务调用更稀少。为了模拟真实环境，本文作者从原始WSDream数据集中抽取部分数据作为训练集，其余则为测试集。本文选取4个不同稀疏度的训练集进行实验，稀疏度分别为5%，10%，15%和20%，其余全部作为测试集。对4个不同稀疏度的训练集进行10次实验并取平均结果作为最终结果。

2.4 性能比较

为了更好地评估本文提出算法的性能，本文实现下述几个常见的服务质量值预测算法，并在该实验集上进行了大量比较实验。

1) UserMean。该方法通过求每个用户的平均QoS值对缺失值进行预测。

2) RBM[7]。该方法是利用RBM的算法对缺失值进行预测。

3) ItemMean。该方法通过求每个Web服务的平均QoS值对缺失值进行预测。

4) UPCC[10]。该方法基于用户协同过滤算法，使用皮尔逊相似度计算用户间的相似度。

5) IPCC[11]。该方法采用基于物品的协同过滤算法，使用皮尔逊相似度计算物品间的相似度。

6) WSRec[9]。该方法对UPCC和IPCC的预测结果进行线性组合，将线性组合后的值作为预测结果。

7) LFM[6]。该方法通过对用户服务矩阵进行降维分解，发现用户与服务之间的隐含特征，根据隐含特征信息来进行预测。

8) NLBR[12]。该方法利用网络位置信息结合矩阵分解发现隐含特征，并进行预测。

表1所示为不同训练矩阵密度下不同模型的预测性能比较。表1中，MAE为平均绝对误差，NMAE为归一化平均绝对误差，为训练矩阵的数据稀疏度。从表1可以看出：本文提出的预测方法RBMCF的预测准确度比其他方法的高；另外，在不同数据稀疏度下，算法的性能差异不明显，特别是在数据稀疏性高的情况下，RBMCF模型的预测准确度仍旧较高，这说明RBMCF能够较好地应对数据稀疏性问题。

2.5 参数Tu的敏感性分析

参数u表示协同过滤算法中基于相似度为用户选择的相似邻居数量，其中相似度是基于历史数据并使用平均欧式距离计算得到的。平均欧式距离越大，表示用户之间的相似度越小。图4所示为不同数据稀疏度下，u对预测准确度的影响。数据稀疏度越高，意味着可用信息越少。

表1 不同训练矩阵密度情况下不同模型的预测性能比较

d/%：(a) 5；(b) 10；(c) 15；(d) 20

从图4可以看出：在初始阶段，随着u逐渐增大，MAE迅速减小。这是因为随着相似邻居数量增多，选中目标用户真正的相似邻居的可能性变大，同时，由于本文利用全局信息进行相似邻居筛选，会添加那些因稀疏而被过滤的用户(这些用户和目标用户表现出很强的相似性，却因为没有公用调用记录而被过滤)，同时排除那些因为偶然原因成为相似邻居的用户(这些用户和目标用户并没有表现出很强的相似性，仅仅因为需要满足相似邻居数量而成为目标用户的相似邻居)，因此，相似邻居的可靠性增强。由此可见，通过使用全局过滤可以提高筛选邻居准确度进而提高模型的预测精确度。

另一方面，当u增大到一定程度后，MAE趋向于平缓，这是由于参数取较大值后，相似度的定义变得宽松，很多相似性不强的用户也被筛选为目标用户的相似用户，影响了预测精确度。

3 讨论

目前，已有大量基于近邻的协同过滤方法被成功应用于实际系统中[13−14]。WU等[15]提出了1种基于新型相似度计算方法的协同过滤算法。该方法采用比例值作为新的相似度度量方法，提高了预测准确度且计算时间更短。TANG等[16]提出了利用位置信息的协同过滤算法并将其应用于服务推荐，使得筛选邻居更加准确。

基于近邻的协同过滤算法的难点之一是数据稀疏问题[5]。由于数据稀疏，基于近邻的协同过滤算法无法准确获取相似邻居进而无法进行精确预测。近年来，已有研究者提出了解决基于近邻协同过滤算法数据稀疏问题的方法。WU等[17]提出了1种利用时间感知的基于近邻的协同过滤方法，在高稀疏度情况下有较高的精确度。但基于近邻的方法难以处理大数据量，有研究者提出基于模型的协同过滤方法，主要有SVD模型[18]、外观模型[19]以及基于RBM的协同过滤方法[7]。YU等[20]提出1种结合了相似邻居的隐语义(latent matrix factorization, LFM)模型，提高了服务推荐的精确性。外观模型是1种概率隐空间模型，使用偏好因子的1个凸组合来对用户偏好进行建模[19]。

RBM的快速学习算法即对比散度(contrastive divergence, CD)算法[8]具有强大的非监督学习能力，引起了研究者的密切关注。RBM成功地应用于解决协同过滤、图像特征提取等机器学习问题[21]。近年来，RBM在推荐系统中也得到了应用[22]。实践表明，RBM是一种有效的特征提取方法[23]，能有效地应对数据稀疏情况；将RBM用于初始化前馈神经网络可明显提高泛化能力，多个RBM堆叠组成的深度置信网络能提取更抽象的特征[24]。SALAKHUTDINOV等[7]提出了基于RBM模型的协同过滤算法，其对传统的受限玻尔兹曼机进行改造以处理协同过滤问题：首先，将可见单元转化为1个维的0−1向量单元；其次，对于没有评分的数据用缺失单元表示，且这类单元不与隐藏单元连接。GEORGIEV等[25]提出了1个基于实值的RBM模型并改进了模型的训练过程，使RBM的可见单元可以直接表示为实值，模型的训练和预测也得到简化。由于基于近邻的方法与基于模型的方法各有优缺点，KOREN等[26]提出将矩阵分解与近邻方法相结合，并取得了较好的预测结果。然而，这些基于近邻的协同过滤方法忽略了具有较高相似度但有未调用目标服务记录的用户，因此，无法准确地筛选相似邻居。同时，RBM在应用中易产生局部最优导致无法得到精确的预测结果。

4 结论

1) 本文提出了1种基于受限玻尔兹曼机的Web服务QoS预测算法；通过引入受限玻尔兹曼机降低数据稀疏对预测结果的影响，并结合基于用户的协同过滤算法得到最终QoS预测结果。

2) 本文算法的QoS预测算法结果优于已有的协同过滤模型所得结果。

[1] LIU Yutu, NGU A H, ZENG Liangzhao. QoS computation and policing in dynamic web service selection[C]// Proceedings of the 13th International World Wide Web Conference on Alternate Track Papers & Posters. New York, USA: ACM, 2004: 66−73.

[2] ZHENG Zibin, MA Hao, LYU M R, et al. QoS-aware web service recommendation by collaborative filtering[J]. IEEE Transactions on Services Computing, 2011, 4(2): 140−152.

[3] LANGSETH H, NIELSEN T D. Scalable learning of probabilistic latent models for collaborative filtering[J]. Decision Support Systems, 2015, 74: 1−11.

[4] BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[J]. Uncertainty in Artificial Intelligence, 1998, 98(7): 43−52.

[5] MIHA Grčar, DUNJA Mladenič, BLAŽ Fortuna, et al. Data sparsity issues in the collaborative filtering framework[C]// International Workshop on Knowledge Discovery on the Web. Berlin, Germany: Springer, 2005: 58−76.

[6] KOREN Y, BELL R, VOLINSKY C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8): 30−37.

[7] SALAKHUTDINOV R, MNIH A, HINTON G. Restricted Boltzmann machines for collaborative filtering[C]// International Conference on Machine Learning. New York, USA: ACM, 2007: 791−798.

[8] HINTON G E. Training products of experts by minimizing contrastive divergence[J]. Neural Computation, 2002, 14(8): 1771−1800.

[9] ZHENG Zibin, MA Hao, LYU M R, et al. WSRec: a collaborative filtering based web service recommender system[C]// International Conference on Web Services. Washington D C, USA: IEEE Computer Society, 2009: 437−444.

[10] RESNICK P, IACOVOU N, SUCHAK M, et al. GroupLens: an open architecture for collaborative filtering of netnews[C]// ACM Conference on Computer Supported Cooperative Work. New York, USA: ACM, 1994: 175−186.

[11] SARWAR B, KARYPIS G, KONSTAN J, et al. Item-based collaborative filtering recommendation algorithms[C]// International Conference on World Wide Web. New York, USA: ACM, 2001: 285−295.

[12] ZHOU Li, SONG Zhibo, ZHAI Suichu, et al. Predicting web service QoS via combining matrix factorization with network location[J]. International Journal of u- and e-Service, Science and Technology, 2014, 7(3): 303−318.

[13] HERLOCKER J L, KONSTAN J A, BORCHERS A, et al. An algorithmic framework for performing collaborative filtering[C]// Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York, USA: ACM, 1999: 230−237.

[14] LINDEN G, SMITH B, YORK J. Amazon.com recommendations: item-to-item collaborative filtering[J]. IEEE Internet Computing, 2003, 7(1): 76−80.

[15] WU Xiaokun, CHENG Bo, CHEN Junliang. Collaborative filtering service recommendation based on a novel similarity computation method[J]. IEEE Transactions on Services Computing, 2017, 10(3): 352−365.

[16] TANG Mingdong, JIANG Yechun, LIU Jianxun, et al. Location-aware collaborative filtering for QoS-based service recommendation[C]// IEEE, International Conference on Web Services.Washington D C, USA: IEEE Computer Society, 2012: 202−209.

[17] WU Chen, QIU Weiwei, WANG Xinyu, et al. Time-aware and sparsity-tolerant QoS prediction based on collaborative filtering[C]// IEEE International Conference on Web Services (ICWS). Washington D C, USA: IEEE Computer Society, 2016: 637−640.

[18] ZHANG Sheng, WANG Weihong, FORD J, et al. Using singular value decomposition approximation for collaborative filtering[C]// Seventh IEEE International Conference on E-Commerce Technology. Washington D C, USA: IEEE Computer Society, 2005: 257−264.

[19] HOFMANN T, PUZICHA J. Latent class models for collaborative filtering[C]//Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. San Francisco, USA: Morgan Kaufmann Publishers, 1999: 688−693.

[20] YU Dongjin, LIU Yu, XU Yueshen, et al. Personalized QoS prediction for web services using latent factor models[C]//IEEE International Conference on Services Computing. Washington D C, USA: IEEE Computer Society, 2014: 107−114.

[21] MIDHUN, M. E, NAIR, et al. Deep model for classification of hyperspectral image using restricted Boltzmann machine[C]//Proceedings of the 2014 International Conference on Interdisciplinary Advances in Applied Computing. New York, USA: ACM, 2014: 1−7.

[22] HINTON G E. A practical guide to training restricted Boltzmann machines[M]. Berlin, Germany: Springer, 2012: 599−619.

[23] TRAMEL E W, MANOEL A, CALTAGIRONE F, et al. Inferring sparsity: compressed sensing using generalized restricted Boltzmann machines[C]// IEEE Information Theory Workshop (ITW). Washington D C, USA: IEEE, 2016: 265−269.

[24] POLANIA L, BARNER F, KENNETH E, et al. Exploiting restricted Boltzmann machines and deep belief networks in compressed sensing[J]. IEEE Transactions on Signal Processing, 2017, 65(17): 4538−4550.

[25] GEORGIEV K, NAKOV P. A non-IID framework for collaborative filtering with restricted Boltzmann machines[C]// Proceedings of the 30th International Conference on Machine Learning. New York, USA: ACM, 2013: 1148−1156.

[26] KOREN Y. Factorization meets the neighborhood: a multifaceted collaborative filtering model[C]// International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2008: 426−434.

(编辑 伍锦花)

Web service QoS prediction based on restricted Boltzmann machines

WANG Xingfei1, 2, WAN Jian1, 2, 3, CHEN Lu1, 2, YIN Yuyu1, 2, YU Lifeng4

(1. School of Computer, Hangzhou Dianzi University, Hangzhou 310018, China; 2. Key Laboratory of Complex Systems Modeling and Simulation of Ministry of Education,Hangzhou 310018, China; 3. School of Information and Electronic Engineering,Zhejiang University of Science and Technology, Hangzhou 310023, China; 4. Hithink RoyalFlush Information Network Co. Ltd., Hangzhou 310023, China)

Considering that collaborative filtering algorithm can not cope with data sparseness effectively, an approach for Web service QoS prediction based on restricted Boltzmann machine was proposed. In the first phase, restricted Boltzmann machine was used to predict all the missing QoS values and fill the original QoS matrix. In the second phase, global filtering was performed based on the filled QoS matrix to obtain the neighbors. Then restricted Boltzmann machine was integrated into user-based collaborative filtering model to predict target QoS values. The results show that the proposed method can improve the accuracy of QoS prediction and reduce the effect of data sparsity on prediction to a certain extent.

Web service; QoS prediction; collaborative filtering; restricted Boltzmann machine

10.11817/j.issn.1672-7207.2018.11.015

TP312

A

1672−7207(2018)11−2745−08

2017−12−11；

2018−01−28

国家重点研发计划项目(2017YFB1400601)；浙江省自然科学基金资助项目(LY12F02003)；国家自然科学基金资助项目(61100043) (Project(2017YFB1400601) supported by the National Key R&D Program of China; Project(LY12F02003) supported by the Natural Science Foundation of Zhejiang Province; Project(61100043) supported by the National Natural Science Foundation of China)

殷昱煜，博士，硕士生导师，从事服务计算、业务流程管理、形式化方法研究；E-mail: yinyuyu@hdu.edu.cn