基于信誉感知与嵌入式学习的Web服务QoS预测研究

邓 璇，吕晟凯

（1.湖北大学 计算机与信息工程学院，湖北 武汉 430062；2.应用数学湖北省重点实验室，湖北 武汉 430062；3.湖北省软件工程技术研究中心，湖北 武汉 430062）

0 引 言

协同过滤（Collaborative Filtering）是目前应用广泛的QoS预测方法之一[3]，传统计算用户（或服务）相似性的方法是基于皮尔逊相关系数或余弦相似性计算相似度，实际上只挖掘了用户之间的二阶相似度，而忽略了用户之间更高阶的隐式关系[4]。

为解决以上问题，我们在考虑用户信誉的同时引入网络嵌入式学习（Network Embedding Learning），提出一种基于信誉感知的QoS预测方法。该方法能从历史数据中充分挖掘用户（或服务）间的高阶隐式关系，为目标用户找到更多潜在的可靠相似用户，不仅考虑了不可信用户对预测精度的影响，也在一定程度上缓解了数据稀疏性问题[5-6]。

1 研究方法

本文方法主要包括如下4部分。

（1）用户信誉计算：利用K-means聚类对Web服务的历史QoS值进行聚类，聚类结果用于计算用户的信誉度，将信誉度低于阈值的用户标记为不可信用户，并过滤。

（2）网络建模：将计算得到的用户信誉度作为用户节点属性，构建带属性的用户-服务二分网络。

（3）网络嵌入式学习：对带属性的用户-服务二分网络进行嵌入式学习，获得用户的表征向量。

（4）QoS预测：给定一个目标用户，为其返回Top-K个相似用户，并利用相似用户提供的信息预测缺失的QoS值。

1.1 K-means聚类

对每一项服务，使用K-means聚类对其所有用户标记的QoS值进行聚类。聚类后，包含元素个数最少的集群中的用户视为不可信用户。聚类算法中的参数K为确定要划分的组数，表示服务j的第k个集群，其中k是集群的索引，0≤k

长阳县水产局局长田继桥向记者解读该项工作的艰巨难行之处时说，整个清理取缔概算需要2亿元以上的资金，这相当于该县过去30年农业投入的总和。当这个数字报到县人大常委会时，大家都愣住了。

矩阵A是由m个用户和n个服务组成的m×n矩阵，用来记录用户的不可信索引，初始化矩阵A，其每一项值均为0。如果用户i被标识为服务j上的候选不可信用户，则aij设置为1。重复聚类过程，对每个服务更新矩阵A，直到所有服务的QoS值均已聚类。

用户信誉度：在对所有QoS值聚类后，使用以下公式得到用户不可信索引集：

式中，wu表示用户u被识别为不可信用户的次数，wu越大，表示该用户的信誉度越低，即ru=1⁄wu。

1.2 用户-服务二分网络学习

1.2.1 带属性的用户-服务二分网络建模

结合用户信誉和用户与服务的交互信息，可以构建一个带属性的用户-服务二分网络G={U,S,R,E}，其中，U={u1,u2,...,um}是用户集合，S={s1,s2,...,sn}是服务集合，R是用户信誉，E={eij|i=1, 2,...,m；j=1, 2,...,n}是边集合，在边集合中eij=QoSij，表示用户ui对服务sj的个性化QoS值。用户u1，u2，u3的信誉值分别为r(u1)，r(u2)，r(u3)，其用户-服务二分网络如图1所示。

图1 用户-服务二分网络

1.2.2 网络嵌入学习

二分网络嵌入（Bipartite Network Embedding）用于学习二分网络中的节点表示[7]。它通过执行有偏和自适应的随机游走，很好地保持了原始二分网络中节点的长尾分布。它在学习节点表示时，同时对显式关系（即观察到的连接）和高阶隐式关系（即未观察到但可传递的连接）进行建模。通过二分网络嵌入式学习，可以为目标用户发掘更多可信的间接相似用户，有效减少不可信用户和数据稀疏性对预测精度的影响。

1.3 协同过滤

对目标用户i，选择与其相似度最高的前K个用户作为其相似用户集合。

依据相似用户提供的信息，缺失的QoS值可以用以下公式计算：

2 实验与结果分析

本文在公开数据集[8]WS-Dream上进行实证分析，与3种已有方法进行对比。采用常用的平均绝对误差（Mean Absolute Error, MAE）作为测量预测方法准确性的评价指标，MAE定义为：

式中：N为所有预测值的个数；Ru,i表示实际QoS值；u,i表示预测的QoS值。

将QoS矩阵密度以1%的步长从5%增加到10%。在K-means聚类中K取值为5，选择反馈20个相似用户进行预测。嵌入式学习中的负采样数为4，窗口为5，游走停止概率p为 0.15，损失权衡参数α=0.01，β=0.01，γ=4，学习率λ=0.15。表1显示了在不同密度条件下不同方法的MAE结果，实验结果表明：随着矩阵密度的增加，所有方法的MAE值都呈下降趋势。说明矩阵的密度越大，可获得的用户和服务交互信息越多，预测精度也就越高。在各密度条件下，本文方法与已有方法相比，MAE值更小，即预测精度更高。说明采用信誉感知的网络嵌入式方法，能够缓解数据稀疏性对预测精度的影响。具体而言，与TAP方法相比，本文方法的预测精度最大可提高20.93%。

表1 各方法在不同矩阵密度条件下取得的MAE结果

3 结 语

本文将网络嵌入式方法引入QoS预测过程中，考虑用户的实际信誉度，提出了一种基于信誉感知网络嵌入的QoS预测方法。该方法能够充分利用用户-服务二分网络信息与用户信誉度信息，能从历史数据中充分挖掘用户-服务间的高阶隐式关系，为目标用户找到更多潜在的可靠相似用户。实验表明，本文方法不仅考虑了用户信誉对预测精度的影响，也在一定程度上缓解了数据稀疏性问题，相比已有三种其他方法准确度更高[9-10]。