基于关联规则挖掘与用户情景感知的Web服务QoS预测

摘要：作为Web服务的非功能性属性，QoS在服务选择与服务组合中扮演着重要角色。由于一些QoS属性值会随着用户情景属性的变化而动态变化，因此在做服务选择或服务组合之前先对Web服务的QoS做预测是非常必要的。该文提出运用数据挖掘技术挖掘服务组合执行日志，研究服务QoS和用户情景间的关联关系，根据得到的关联规则对不同用户做个性化服务预测。实验结果表明我们的方法非常有研究价值。

关键词：Web服务；服务质量（QoS）；用户情景；服务预测；关联规则挖掘

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）34-8158-02

作为近年来非常有前景的一项技术，Web服务的核心任务是产生和共享独立自主的软件程序。通常情况下，对于一个Web服务，有三个实体与之密切相关：服务提供者，服务注册机构以及用户。随着Web服务需求的不断增长，越来越多的服务提供者开始提供种类繁多的Web服务，其中有许多功能相同、模型结构相似，但服务质量（QoS）各异。

研究者普遍认为，基于QoS的Web服务的搜索和选择是一项非常重要的技术，因为它可以有效保证以Web服务为基本元组的应用系统的质量。Web服务的QoS属性包括可用性、费用、响应时间和产量等。作为衡量Web服务的非功能性属性的主要指标之一，QoS是重要的决策依据。通过测量和比较不同候选Web服务的QoS值，我们可以找出最优值所对应的那个Web服务。在实际情况中，一些QoS属性如服务价格的值基本上保持稳定，但另一些如响应时间和产量却常常是动态变化的，因此QoS的应用较为复杂。事实上，我们很难预先知道一个Web服务的非功能性性能。一种解决方法就是预测服务的QoS值。QoS预测的方法包括利用统计学模型、仿真模拟和数据挖掘等技术[1]。

近年来，利用数据挖掘技术做服务预测得到了较大关注。常见的运用于服务组合领域的数据挖掘技术主要有对Web服务或用户进行分类、挖掘服务之间、用户之间或服务与用户之间的关联规则等。Ying Chen收稿日期：2014-11-08

作者简介：刘宇乔（1990-），女，内蒙古鄂尔多斯人，同济大学硕士研究生，研究方向为服务组合预测。等人在一个服务型系统框架的研究中详细阐述了4种数据挖掘技术的用法，包括服务分类分析、服务（用户）聚类、服务关联规则分析和服务顺序调用模式分析等。Jorge Cardoso[1]利用数据挖掘技术对组合服务工作流的QoS数据进行处理，实现对工作流QoS值的预测。目前，关联规则挖掘在服务组合领域运用较为广泛。如张明卫[3]等人曾提出挖掘组合服务分支路径关联规则的方法。

现存研究有一个共同的缺点：不能充分反应用户的偏好，即不能体现用户情景对服务组合的影响。其结果就是，相同请求得到的组合服务总是相同的，而用户的差异性被忽略了。事实上，在服务组合中，仅仅考虑客观属性指标（包括功能性属性和非功能性属性）是不够的，用户情景属性（如地理位置和偏好等）也是影响组合结果的重要因子。具体说来，用户情景与Web服务的QoS密切相关，一些QoS属性会根据用户情景属性的变化而发生变化。基于此，该文提出结合QoS和用户情景对组合服务的影响，运用数据挖掘技术找出QoS与用户情两者之间的关联规则，根据找到的关联规则对Web服务做出QoS预测，从而明确哪些Web服务对特定用户是最优选择。

1 问题描述

理想情况下，当用户的服务请求相似时，同一组Web服务即可满足他们的需求。但实际情况是，虽然功能性需求可以保证满足，但非功能性需求的实现情况对不同用户的差异性很大。由于QoS会随着用户情景的变化而变化，即使用户的服务请求相似，适合某一用户的Web服务不一定是其他用户的最优选择。这些用户不同的地理位置或网络环境都将对服务的调用结果产生重要影响。

下面我们具体用一个例子来加以说明。如图1所示，用户A和用户B发出同一个服务请求。4个组件服务对其功能性需求做出响应（假设该服务组合的模式是序列模式）。被两个用户调用后，Web服务S1，S2 和Sr的QoS值是一样的，但服务S3的QoS值却存在差异。有时候，即使是很小的差异，也会对整个组合服务的运行结果产生巨大影响。引起这种QoS差异的主要因素是用户情景因子，A、B用户的情景（如地理位置、偏好等）不同，导致调用同一Web服务S3得到的QoS值不同。为解决这个问题，一些学者对用户相似性进行了研究，认为同一Web服务经相似用户调用后得到的QoS值是一致的，所以相似用户的相同的服务请求可得到相同的执行结果。因此，要想知道某个Web服务对一个新用户是否合适，可以通过研究与该用户具有相似情景的用户调用这个服务的日志，预测服务的QoS值来间接判断。

2 基于关联规则挖掘的Web服务QoS预测方法

与传统的量化属性因子值、计算用户相似度的方法不同，本研究把不同情景属性作为影响QoS的独立因子，运用数据挖掘方法挖掘用户情景与服务QoS的相互关系。关联规则挖掘对于分析一个数据集中各元素关联关系非常有效。一个关联规则常被表示为X→Y，意思是当元素集合X出现的时候，集合Y会以较大概率出现。对于本研究，用户情景属性与服务QoS属性作为元素单元组成数据集，我们的主要目标就是挖掘这两种属性元素的关联关系。为了保证得出有效关联规则，在应用挖掘算法的时候需设置限制参数。关联规则挖掘最常用的两个参数是支持度和置信度。

假设I={I1，I2，I3，...Im}是元素项的集合。给定一个交易数据库D，其中每个事务（Transaction）t是I的非空子集，即，每一个交易都与一个唯一的标识符TID对应。关联规则在D中的支持度（support）是D中事务同时包含X、Y的百分比，即概率，算法如公式（1） 所示；置信度 （confidence）是D中事务已经包含X的情况下，包含Y的百分比，即条件概率，算法如公式（2） 所示。如果满足最小支持度阈值和最小置信度阈值，则认为关联规则是有趣的。这些阈值是根据挖掘需要人为设定的。endprint

为了运用关联挖掘算法，首先需要建立数据事务集D。为此，对于每条服务组合执行日志，我们提取出所有的用户情景属性和Web服务QoS属性，以及对应的Web服务ID，将它们组成一条有效事务，每个情景属性（或QoS属性）即为该条事务一个元素项目（简称项目）。表1所示为一条包含两个情景属性元素项和一个QoS属性项目的服务事务。一条组合服务包含的组件服务可能有2个、3个甚至更多，则可从该条组合服务中可提取出满足要求的相应个数的服务事务。

其次，需要对各元素项目的值进行规范化，使它们落在重复出现的几个值域内，以便进行关联规则挖掘。具体处理措施如下：对离散分布的用户情景属性值，我们把它们根据需要分在若干个区间域内；对连续分布的QoS属性值，我们把它们划分成不同的等级，用整数1～5表示，代表质量从高到低。

3 总结与未来工作展望

本文提出一种运用关联规则挖掘技术做Web服务QoS预测的方法。作为Web服务的重要特征指标，QoS受用户情景影响，随着用户的不同而动态变化。为了针对不同用户作个性化服务推荐，本研究着力于挖掘用户情景属性与QoS属性的关联关系，根据关联关系分析某一Web服务是否可为某一用户提供高质量QoS，从而判断是否将该服务推荐给该用户。实验结果表明我们的方法能够保证较高的预测准确率，有广阔的应用前景。

虽然本研究实现了准确预测服务QoS的目标，但所用算法有待进一步改进：传统的Apriori算法有两大缺点，即可能产生大量的候选集，以及可能需要重复扫描数据库，当实验数据量较大时，实验性能可能会受到影响。未来的研究工作拟探索用FP-树频集算法挖掘用户情景与服务QoS的关联关系。

参考文献：

[1] Cardoso J.Workflow Quality of Service Management using Data Mining Techniques[C].3rd International IEEE Conference Intelligent Systems London， 2006：479-482.

[2] Chen Y，Cohen B.Data mining and service rating in service-oriented architectures to improve information sharing[C]. Aerospace Conference， 2005 IEEE，2005：1-11.

[3] 张明卫，魏伟杰，张斌，等.基于组合服务执行信息的服务选取方法研究[J].计算机学报，2008，31（8）： 1398-1411.

[4] Agrawal R， Imielinski T， Swami A N.Mining Association Rules between Sets of Items in Large Databases[C].Proceedings of 1993 ACM International Conference on Management of Data，Washington D.C，USA， 1993：207-216.endprint

为了运用关联挖掘算法，首先需要建立数据事务集D。为此，对于每条服务组合执行日志，我们提取出所有的用户情景属性和Web服务QoS属性，以及对应的Web服务ID，将它们组成一条有效事务，每个情景属性（或QoS属性）即为该条事务一个元素项目（简称项目）。表1所示为一条包含两个情景属性元素项和一个QoS属性项目的服务事务。一条组合服务包含的组件服务可能有2个、3个甚至更多，则可从该条组合服务中可提取出满足要求的相应个数的服务事务。

其次，需要对各元素项目的值进行规范化，使它们落在重复出现的几个值域内，以便进行关联规则挖掘。具体处理措施如下：对离散分布的用户情景属性值，我们把它们根据需要分在若干个区间域内；对连续分布的QoS属性值，我们把它们划分成不同的等级，用整数1～5表示，代表质量从高到低。

3 总结与未来工作展望

本文提出一种运用关联规则挖掘技术做Web服务QoS预测的方法。作为Web服务的重要特征指标，QoS受用户情景影响，随着用户的不同而动态变化。为了针对不同用户作个性化服务推荐，本研究着力于挖掘用户情景属性与QoS属性的关联关系，根据关联关系分析某一Web服务是否可为某一用户提供高质量QoS，从而判断是否将该服务推荐给该用户。实验结果表明我们的方法能够保证较高的预测准确率，有广阔的应用前景。

虽然本研究实现了准确预测服务QoS的目标，但所用算法有待进一步改进：传统的Apriori算法有两大缺点，即可能产生大量的候选集，以及可能需要重复扫描数据库，当实验数据量较大时，实验性能可能会受到影响。未来的研究工作拟探索用FP-树频集算法挖掘用户情景与服务QoS的关联关系。

参考文献：

[1] Cardoso J.Workflow Quality of Service Management using Data Mining Techniques[C].3rd International IEEE Conference Intelligent Systems London， 2006：479-482.

[2] Chen Y，Cohen B.Data mining and service rating in service-oriented architectures to improve information sharing[C]. Aerospace Conference， 2005 IEEE，2005：1-11.

[3] 张明卫，魏伟杰，张斌，等.基于组合服务执行信息的服务选取方法研究[J].计算机学报，2008，31（8）： 1398-1411.

[4] Agrawal R， Imielinski T， Swami A N.Mining Association Rules between Sets of Items in Large Databases[C].Proceedings of 1993 ACM International Conference on Management of Data，Washington D.C，USA， 1993：207-216.endprint

为了运用关联挖掘算法，首先需要建立数据事务集D。为此，对于每条服务组合执行日志，我们提取出所有的用户情景属性和Web服务QoS属性，以及对应的Web服务ID，将它们组成一条有效事务，每个情景属性（或QoS属性）即为该条事务一个元素项目（简称项目）。表1所示为一条包含两个情景属性元素项和一个QoS属性项目的服务事务。一条组合服务包含的组件服务可能有2个、3个甚至更多，则可从该条组合服务中可提取出满足要求的相应个数的服务事务。

其次，需要对各元素项目的值进行规范化，使它们落在重复出现的几个值域内，以便进行关联规则挖掘。具体处理措施如下：对离散分布的用户情景属性值，我们把它们根据需要分在若干个区间域内；对连续分布的QoS属性值，我们把它们划分成不同的等级，用整数1～5表示，代表质量从高到低。

3 总结与未来工作展望

本文提出一种运用关联规则挖掘技术做Web服务QoS预测的方法。作为Web服务的重要特征指标，QoS受用户情景影响，随着用户的不同而动态变化。为了针对不同用户作个性化服务推荐，本研究着力于挖掘用户情景属性与QoS属性的关联关系，根据关联关系分析某一Web服务是否可为某一用户提供高质量QoS，从而判断是否将该服务推荐给该用户。实验结果表明我们的方法能够保证较高的预测准确率，有广阔的应用前景。

虽然本研究实现了准确预测服务QoS的目标，但所用算法有待进一步改进：传统的Apriori算法有两大缺点，即可能产生大量的候选集，以及可能需要重复扫描数据库，当实验数据量较大时，实验性能可能会受到影响。未来的研究工作拟探索用FP-树频集算法挖掘用户情景与服务QoS的关联关系。

参考文献：

[1] Cardoso J.Workflow Quality of Service Management using Data Mining Techniques[C].3rd International IEEE Conference Intelligent Systems London， 2006：479-482.

[2] Chen Y，Cohen B.Data mining and service rating in service-oriented architectures to improve information sharing[C]. Aerospace Conference， 2005 IEEE，2005：1-11.

[3] 张明卫，魏伟杰，张斌，等.基于组合服务执行信息的服务选取方法研究[J].计算机学报，2008，31（8）： 1398-1411.

[4] Agrawal R， Imielinski T， Swami A N.Mining Association Rules between Sets of Items in Large Databases[C].Proceedings of 1993 ACM International Conference on Management of Data，Washington D.C，USA， 1993：207-216.endprint