基于用户聚类的Web服务QoS预测与服务选择算法研究

摘要

近年来，Web服务计算领域随着SOA技术的广泛应用而得到了快速发展，从中衍生出了服务发现、服务组合、服务选择等若干子领域。服务选择，作为服务执行前的重要步骤，其中的QoS预测和skyline计算等课题亦成为了热门的研究方向。
　　 对于服务选择中的上述课题，主要还面临着以下几个问题:基于传统协同过滤算法的QoS预测面临与推荐系统中类似的冷启动和稀疏性问题;对于单一维度的QoS预测研究不能解决真实场景下QoS多维度并存的问题;由于QoS预测和skyline计算的在线特性，使得其在服务数量和用户数量大幅增长时，需要提高其在线计算效率的问题。
　　 针对上述问题，我们提出了基于用户聚类的QoS预测和服务选择算法。首先通过引入图挖掘技术中的图摘要算法，对用户-服务QoS关系进行建模，实现了基于图摘要的用户聚类算法LAC，利用聚类-服务关系替代原用户-服务关系，将稀疏的大数据集转化为密集的小规模数据。基于LAC算法的结果，引入对用户非QoS特征的分析，实现了基于朴素贝叶斯的用户分类器，解决了QoS预测中的冷启动问题，并且将此思想用于对LAC算法的优化。最后，对基于用户聚类的QoS预测与服务选择系统进行了设计，将计算过程划分为离线与在线阶段。在离线计算阶段进行LAC聚类和基于用户聚类的结果预处理的基础上，针对服务选择请求在线处理中QoS预测和skyline计算两个关键过程，提出了基于用户聚类的QoS在线预测算法和聚类辅助的改进skyline算法。通过充分利用离线运算生成的中间结果，上述算法有效的提高了对在线请求的处理效率。
　　 最后，我们通过实验分析上述算法的效果以及其对在线计算效率的提升，并验证了其在数据稀疏、冷启动场景下的有效性。

目录

摘要

第1章 绪论

1．1 课题背景

1．2 相关概念

1．2．1 Web服务

1．2．2 服务的QoS

1．2．3 服务组合与服务选择

1．3 关键技术与国内外研究现状

1．3．1 QoS预测

1．3．2 基于QoS的服务选择

1．3．3 聚类算法

1．4 图挖掘算法概述

1．4．1 图挖掘算法与社交网络

1．4．2 图摘要算法

1．5 本文工作

1．6 文章结构

1．7 本章小结

第2章 总体设计

2．1 问题与挑战

2．2 QoS的图模型定义

2．2．1 加权二部图模型

2．2．2 QoS的多维加权二部图模型

2．2．3 问题定义

2．3 基于图摘要的OoS预测与服务选择系统设计

2．4 各模块说明

2．4．1 用户聚类生成器

2．4．2 聚类特征计算模块

2．4．3 聚类skyline预处理模块

2．4．4 用户分类器

2．4．5 QoS预测器

2．4．6 skyline在线计算模块

2．5 本章小结

第3章 基于图摘要的用户聚类算法

3．1 概述

3．2 图摘要用户聚类算法描述(LAC)

3．2．1 定义

3．2．2 自底向上的聚类算法

3．2．3 自顶向下的聚类算法

3．2．4 对多维QoS的扩展

3．3 算法分析

3．3．1 算法复杂度

3．3．2 算法的启动与终止

3．3．3 聚类结果

3．4 本章小结

第4章 聚类结果处理与用户分类

4．1 聚类结果处理

4．1．1 聚类QoS矩阵

4．1．2 用户特征统计

4．1．3 聚类skyline预处理

4．1．4 离线计算结果

4．2 用户分类器

4．2．1 算法原理

4．2．2 贝叶斯定理和朴素贝叶斯假设

4．2．3 基于用户特征的用户分类器实现

4．3 对用户聚类算法的优化

4．4 本章小结

第5章 基于用户聚类的QoS预测与skyline计算

5．1 QoS预测

5．1．1 在线计算模块概述

5．1．2 基于用户聚类的QoS预测算法

5．1．3 算法分析

5．2 聚类辅助的改进skyline算法

5．2．1 离线的聚类特征skyline计算

5．2．2 在线skyline计算

5．3 本章小结

第6章 实验与分析

6．1 QoS预测

6．1．1 算法准确率和效率

6．1．2 冷启动预测

6．1．3 聚类参数的影响

6．2 skyline计算

6．3 本章小结

第7章 总结与展望

7．1 工作总结

7．2 未来展望

参考文献

攻读硕士学位期间主要的研究成果

致谢