基于覆盖随机游走算法的服务质量预测

Service Quality Prediction Based on Covering Random Walk Algorithm

随着互联网上Web服务的日益增多,面对大量功能相同的候选服务,用户希望能够选择质量最优的候选服务.然而,用户通常并不知道所有候选服务的服务质量(Quality of Service,QoS).因此,基于Web服务的历史记录预测QoS值得到了广泛关注.传统的基于协同过滤(CF)的预测方法可能会遭遇数据稀疏、用户信任等问题,导致该方法在预测精度方面表现一般.为解决上述问题,该文提出一种基于覆盖随机游走算法的服务质量预测方法.该方法首先基于用户服务历史QoS记录,使用改进的覆盖算法对用户进行聚类,选取与每个用户聚类次数的Top-k个用户为该用户的信任用户,连接所有用户与其信任用户构建用户信任网;其次,基于用户信任网提出一种随机游走预测方法,在随机游走的过程中,不仅考虑目标服务的QoS信息,同时考虑相似服务的QoS信息,以确保QoS预测的准确性;最后,每次随机游走获得一个QoS值,为使预测更加准确,作者进行多次随机游走,汇总所有QoS值进行预测.为验证文中方法的有效性,作者在真实的Web服务数据集进行了大量实验,其中包括来自339个用户的5825个真实世界Web服务的1 974 675个Web服务调用.实验结果表明文中方法在预测精度上明显优于现有方法,同时可以很好地解决推荐系统的数据稀疏和用户信任问题.

As the software components, Web services are designed to support interoperable machine - to-machine interaction over a network. With the increasing number of the Web services on the Internet, users always want to choose the best candidate services when facing a large number of similar candidate services with the same function. However, users usually do not know the Quality of Service （QoS of all candidate services. Therefore, the prediction of QoS based on the historical records of the Web services has attracted extensive attention from academia and industry. The traditional prediction methods based on Collaborative Filtering （CF have been successfully employed by some studies to address the Web service prediction problem. However, these methods usually suffer from the problems such as data sparseness and user trust, which may cause poor performance even failures of Web service QoS prediction. In the recent literature, the random walk algorithm is successfully applied to the recommendation models, which can effectively solve the data sparse problem. However, the performance of recommendation accuracy is not ideal, especially when it applied to the user-service classic recommendation model. To solve the above problems, this paper proposes a service quality prediction method based on the covering random walk algorithm, which is a random walk model that takes into account the influence of trust between users and users on Web service prediction, and the method employs a covering algorithm to find trust users. The clustering method does not require the number of clusters to be pre - specified or the initial centers to be manually selected, thus it can ensure the stability of the prediction. Firstly, the proposed method, based on the QoS records of user service history, employs an improved covering algorithm to cluster the users, and the Top- k users who are clustered with each user are selected as trusted users of the user, then all users are connected to their trusted users to build a user trust network. Secondly, based on the user trust network, a random walk prediction method is proposed. In the process of the random walk, not only does the QoS information of the target service is considered, but also the QoS information of the similar service is considered. The reason is that the relationship between these users and the source user will become weak and the QoS values obtained will become unreliable when the walks go too far from the source user in the trust network. Finally, a single random walk can only return a QoS value. To acquire more QoS values and obtain a more reliable prediction, several random walks are desirable and integrate all QoS values returned by different random walks for prediction. To verify the performance of the proposed approach, we conducted a large number of experiments in the real Web service datasets, including 1 974 675 Web service records of 5825 real-world Web services from 339 users. The experimental results show that the proposed method is obviously superior to the existing methods in the prediction accuracy, and it can solve the problems of data sparseness and user trust of the recommended system at the same time.