基于情境的Web服务推荐方法

古凌岚

（广东轻工职业技术学院 计算机工程系，广东 广州510300）

0 引 言

Web服务组合现已成为面向服务的计算模式下应用构造的主要方式，随着面向服务技术的广泛应用，功能相似性能相异的Web服务也越来越多，使得用户需要花费大量时间搜索自己满意的服务，因此，在匹配功能需求的前提下，如何快速有效地发现服务质量（quality of service，QoS）良好、适合用户个性化需求的Web服务，已成为Web服务组合技术成功应用的关键和研究热点。目前，许多研究成果对此进行了阐述，如文献［1，2］在功能匹配的基础上，结合用户QoS约束和QoS属性偏好，更好地满足了用户对服务质量的要求。文献［3，4］基于聚类思想，对于功能相似而QoS不同的语义Web 服务先分类后排序，缩小了搜索范围，在满足功能和质量要求的同时，提高了服务发现的效率。文献［5］以语义Web服务发现的结果为基础，利用用户和服务的情境信息、预定义的情境规则和规则等级，进一步筛选和排序得到适应用户情境的Web服务，提高了用户满意度。通过分析发现已有研究存在以下不足：

（1）对用户信息的利用不充分。Web服务资源的迅速膨胀，使得用户的个性化需求逐渐成为服务发现的重要依据，但目前主要从当前用户背景和QoS属性偏好来考虑，较少关注历史数据（如历史用户评价、历史用户信息等）的利用，而历史数据反映了用户的行为习惯和服务体验的满意度，对于发现用户个人偏好具有重要的价值。

（2）忽视了服务动态性和网络特性对于QoS 的影响。已有研究中多采用服务提供者提供的原始QoS值，由于服务的动态性和网络的不确定性，QoS的许多指标是动态变化的，直接影响了服务发现的有效性。

针对Web服务组合过程中服务发现的问题，本文提出一种基于情景的Web服务推荐方法，构建情境模型刻画用户和服务的信息，利用服务历史执行信息建立和更新服务缓存，采用K－MEANS算法实现服务情境聚类，并进行服务查找和初步QoS约束筛选；综合用户特征和用户评价相似性，结合服务聚类集，进行用户情境聚类，利用情境相似用户的预测和使用频率优化初步推荐结果，从而最大限度地满足了用户个性化需求，同时也提高了服务发现的效率。

1 情境模型

情境是用来描述任何一个实体情况的所有信息，本文总结文献［6，7］情境的定义及分类工作，把情境分为用户特征情境、服务情境和用户评价情境3个部分。用户特征情境包括用户背景和平台环境，其中用户背景是指用户的基本特征，包括姓名、性别、年龄、职业和民族。平台环境是指用户所在位置、硬件设备和网络状态，硬件设备是指用户所使用的设备，如PDA 或PC，网络状态包括网络带宽、延迟和安全性。服务情境包括服务描述和QoS 情境。其中服务描述包括服务名、输入／输出属性、前提和结果。QoS情境是指经过一段时间统计到的服务质量有关属性，包括响应时间、服务费用、可用性和可靠性。用户评价情境是指用户对于服务的满意程度，包括服务标识、用户标识和用户评分。

为了充分利用情境信息，需要建立统一的描述和表示模型，以刻画服务、用户特征和用户评价信息，给出以下定义：

定义1 服务情境模型定义为SC＝（SInfo，QoS，TStat），其中SInfo＝｛Name，Inpu，Outp，Cond，Effe｝表示服务描述，包括服务名、输入属性、输出属性、前提和结果集，QoS＝｛Time，Cost，Avai，Reli｝表示服务质量，包括响应时间、费用、可用性和可靠性，TStat为更新时间。

定义2 用户特征情境模型定义为UC＝（Feat，Plat）。其中Feat＝｛Name，Gend，Age，Prof，Nati｝表示用户背景，包括姓名、性别、年龄、职业和民族，Plat＝｛Loca，Devi，NStatu｝表示平台环境，包括用户所在位置、硬件设备（PDA／PC）和网络状态，NStatu＝｛NBand，NDela，NSecu｝表示网络状态，包括网络带宽、网络延迟和网络安全性。

定义3 用户评价情境模型定义为UR ＝（Uid，Sid，Score），其中Uid、Sid 和Score 分别表示用户标识、服务标识和用户评分。

2 基于情境的Web服务推荐方法

本文方法的基本思路是：①构建情境模型描述用户特征、服务和用户评价信息；②收集服务运行时信息，建立和更新服务缓存；③对于相似情境的服务和用户进行聚类；④基于服务情境发现符合功能和QoS 要求的初步结果；⑤基于用户情境进一步推荐符合用户偏好的候选服务，从而得到最适合用户的推荐结果。服务推荐框架如图1所示。

图1 Web服务推荐框架

图1中各部分的主要功能：

服务代理：负责解析用户提出的服务请求，向服务推荐引擎提交其可识别的功能需求和QoS约束描述，返回服务推荐结果给用户，并负责捕获服务执行信息，收集用户的使用评价，提交给推荐引擎。

服务推荐引擎：由服务情境推荐、用户情境推荐、服务缓存管理、服务聚类和用户聚类模块组成。事先服务聚类和用户聚类模块分别利用服务信息、用户评价和用户信息库，对相似情境的服务和用户进行聚类。用户提出请求时，服务情境推荐模块负责查找功能匹配服务所在类，若查找失败，则通过UDDI注册中心搜寻并返回功能和QoS匹配的具体服务，服务推荐结束；若查找成功，则计算其总的QoS值，按QoS降序排序，并剔除小于QoS约束最低容忍度的服务，得到初步推荐结果集。用户情境推荐模块负责查找用户所在类，结合预测评价和使用频率降序排序，得到最终推荐结果集，提交给服务代理。服务缓存管理模块负责建立和更新服务缓存，包括QoS参数的更新。

UDDI注册中心：负责Web服务的发布，并提供服务查询功能。

2.1 服务缓存的建立和更新

为了提高服务查询效率，本文引入了服务缓存机制。每当服务被调用时，服务代理主动进行监测，收集该服务执行时信息，包括服务标识、服务描述、响应时间、费用、可用性和可靠性，保存在服务信息库作为服务缓存。当用户请求服务时，服务推荐引擎先查询服务缓存，查找成功则进入推荐的下一步工作，只有查询不成功时，才需要通过UDDI注册中心发现服务，随着服务缓存中数据的不断积累，服务查询效率将会不断提高。

由于Web服务的动态性，服务缓存中的数据需及时更新，一方面，对于长时间无人访问的服务或是服务质量低下的服务定期进行删除；另一方面，根据每次服务执行情况，需重新评估QoS各参数，以保证QoS的时效性。QoS数据是本文初步推荐服务的主要依据，下面重点对于QoS参数评估的方法进行说明。

由于Web服务的动态性，使得QoS 值也随之不断变化，越近时间得到的QoS数据对于服务质量评估的贡献越大，为此，引入时间衰减因子λ，每当服务被调用时，利用每次服务执行时收集的QoS数据，结合λ对QoS的各参数进行重新评估

式中：qijold、qij′——缓存中服务QoS参数、最新评估的服务QoS参数，qij——服务执行时QoS 参数，λ——时间衰减因子，值域为［0，1］，为了尽量准确地反映服务当前的状态，忽略时间跨度很近的衰减影响，取λ＝0.5，而时间跨度过大的QoS 已无太大价值，取λ＝1，因此，λ计算公式如下

式中：tcur、told——当前、QoS统计时间，T——有效时间跨度，T0——可忽略衰减的时间跨度，λ越大，则qijold的重要性越低。

由于QoS参数包括成本型和效益型两种，成本型包括服务费用和响应时间，取值越大，质量越低；效益型包括可用性和可靠性，取值越大，质量越高。为了便于计算和比较，在计算服务总的QoS之前还需要对QoS 各参数进行归一化处理，将其规格化到相同量纲上。本文采用的归一化公式如下

式中：qij′、qij″——某QoS参数处理前、后的值，、——该项参数最大、最小值，式（a）用于成本型参数，式（b）则应用于效益型参数。

2.2 服务情境聚类

聚类算法通过对n 个对象不断地分类，形成若干个聚类集合，同一类中对象的相似度较高，而不同类中对象的差别较大。本文采用K－MEANS聚类算法，通过计算服务情境相似性，对于服务进行聚类。

服务相似性通过服务情境信息中服务描述属性的语义相似度来体现，计算公式如下。

式中：w1～w5——服务名称、输入／输出、前提和结果属性的权重，式中的本体间距离和属性间语义相似度的计算参考文献［6］中方法。

服务情境聚类的算法描述：

算法1：服务情境聚类

输入：服务情境集合SC＝｛sc1，sc2，…，scn｝。

输出：服务类的集合C＝｛C1，C2，…，Ck｝。

（1）任意选K 个相互间相似度小于阈值δ的服务，将其服务情境向量作为初始的聚类中心，记为c＝｛c1，c2，…，ck｝；

（2）初始化服务类的集合C；

（3）REPEAT

2.3 用户情境聚类

协同过滤推荐算法是基于用户评价项目相似性计算用户相似性，来发现目标用户的最近邻，从而成功地预测用户感兴趣的项目。本文将其用户相似度计算方法引入用户情境聚类中，综合用户评价相似性和用户特征相似性度量用户情境相似度，考虑到实际上用户评价服务的数量偏少所引起的数据稀疏性对于计算准确性的影响，在服务聚类基础上，先计算各服务类内的用户情境相似度，以减少相似用户搜寻空间，而后据此进行类之间聚合，最终得到用户聚类的集合。

（1）用户评价相似性采用常用的Person 相关系数度量，该方法是基于用户共同评分过的服务集合来计算的，为了避免共同评分服务较少时出现相似性度量的偶然性，总结文献［8］工作，引入评分服务交集最小阈值η对于相似度计算进行修正

（2）对于用户特征相似性，本文假设用户特征的各属性均可量化，包括数值型和区间型两类，而数值型属性分为成本型和效益型，为了便于计算采用式（3）进行了规范化处理。用户特征相似度包括数值型和区间型属性相似度计算。

数据型属性相似度

区间型属性相似度。

采用相对长度法计算区间型属性的相似度，计算公式为

式中：L（ui）、L（vi）和L（ui∩vi）——u 和v 的第i 个属性区间长度，以及两个属性间重叠长度。

（3）根据用户评价相似性和用户特征相似性的度量方法，可得到用户情境相似性计算公式为

式中：w1，w2——权重系数，w1＋w2＝1，且w1＞w2，k是聚类数。

2.4 Web服务推荐算法

服务情境和用户情境聚类无实时性要求，可采用离线方式，在服务推荐处理之前完成。算法描述如下：

算法2：基于情境的Web服务推荐算法

输入：服务类的集合C、用户类的集合U、用户标识v、服务功能需求Sreq、服务QoS约束Qreq和用户QoS偏好权重w。

教学手段和方法的创新 基于前述搭建的虚拟共享实训平台，本改革对变速箱拆装实训课程的教学手段和方法进行创新，将整个拆装实训课程划分为课前、课中和课后三个阶段（如图1所示）。

输出：满足用户个性化需求的服务集合RSfinal。

1.For each cluster Ci∈C do i∈｛1，…，k｝ ／／在服务类的集合中查找功能匹配的服务

2.For si∈S do／／对于功能匹配的服务计算QoS

If（qi＞Qreq）／／若大于QoS约束则结合用户QoS偏好计算服务总的QoS

S′＝S′∪scj；／／将功能匹配且大于QoS约束的服务加入S′

3.RSfirst＝sort（S′，Q）；／／按服务总的QoS 降序排序，得到初步推荐结果

4.For 1to m do

find v∈Ui；Ui∈U／／查找用户v所在的类

5.For each user uj∈Uido／／计算RSfirst预测评价，统计使用频率

6.If Frsi＝0filter（rsi，RSfirst）；／／剔除频率为0的服务

7.For each service rsi∈RSfirstdo

EFrsi＝αQi＋βPrsi，v＋γFrsi；／／计算每个服务得到的总体评价，权重α＋β＋γ＝1

8.RSfinal＝sort（RSfirst，EFrsj）；／／按总评价降序排序，得到最终推荐结果

3 实例分析

下面以一实例说明本文Web服务推荐的方法。假设有50个Web服务，包括5个酒店订房服务、10个订票服务、10个天气预报服务和25个景点查询服务，这些服务均已被使用过，其中酒店订房服务有6人使用过，包括一名学生u6。他现准备在酒店订房，并希望酒店提供订票服务。表1描述了酒店订房服务使用情况，各服务的QoS和业务特点，假设已通过情境聚类得到了服务类的集合C 和用户类的集合U（表2），为了减少计算复杂度，QoS仅列出响应时间和服务费用属性量化后的值，U 仅包含使用过酒店订房服务的用户类，用户情境也仅列出用户背景的职业属性。

表1 用户使用酒店订房服务的评价（平均评分／使用次数）

表2 用户类的集合和服务类的集合列表

采用本文方法推荐Web服务的过程：

（1）在服务类的集合C 中发现酒店订房服务所在类C1，得到候选服务sc1，sc2，sc3，sc4，sc5；

（2）计算各服务总的QoS值，假设sc5总的QoS值小于用户QoS约束被剔除，则得到sc1，sc2，sc3，sc4各自总的QoS值排名（3，1，1，2）；

（3）按QoS 降序排序，得到初步推荐结果sc2，sc3，sc4，sc1；

（4）在用户类的集合U 中发现用户所在类U2；

（5）计算u6对服务sc2，sc3，sc4，sc1的预测评分（4.1，4.3，0，3.2）；

（6）统计U2使用服务sc2，sc3，sc4，sc1的频率（11，6，0，9）；

（7）剔除频率为0 的服务sc4，设α＝0.5，β＝0.3，γ＝0.2，计算U2对sc2，sc1，sc3的总评价为（3.52，2.92，2.57）；

（8）按总评价降序排序；

（9）得到最终推荐结果sc2，sc1，sc3返回给用户u6。

用户u6可优先选sc2，其次sc1，通过本文的服务推荐算法，为用户提供了功能匹配、达到QoS约束要求，且满足用户个性化需求的服务。

4 实验及结果分析

为了进一步验证本文方法的可行性和有效性，本文设计了3组实验。

实验环境：2台服务器CPU Intel Core 2Duo 2.1GHz，内存4G，操作系统Window Server 2003，数据库SQL Server 2008。1台PC 机CPU Intel Core 2 1.86GHz，内存2G，操作系统Window XP。服务器1、2 分别用于配置Web服务和运行本文的Web服务推荐算法，Web服务代理也配置在服务器2上。PC用于用户提出请求。

实验数据：鉴于现在没有标准的测试数据集，实验数据均以模拟方式产生，共生成200个Web服务。服务的QoS属性包括响应时间、费用、可用性和可靠性，在一定范围内随机生成。500个用户已使用过，用户评价在［0，5］整数范围内随机生成。实验以响应时间为例进行测试，事先以随机次数调用每个Web服务，以获得真实响应时间参数。

实验1：QoS动态变化对服务推荐的影响

设T0＝60s，T＝250s，响应时间约束Time＝40s，选取9个功能相同的Web服务（sc1～sc9），且sc4～sc9均满足QoS约束。利用程序模拟延迟1s，对于服务sc1～sc3减少响应时间，对于sc4～sc6增加响应时间，对于sc7～sc9不做改变，对9个服务的QoS值进行计算排序，得到最初推荐结果，共进行5次实验。

分析表3数据，当某次服务被调用时QoS 发现变化，该服务情境的QoS响应时间属性也被重新评估，间隔越久的原有QoS数据重要性越低，当再次请求时，若重新评估后的响应时间不能满足QoS约束最低容忍度，将被剔除，如服务sc4在第一次延迟后其响应时间大于40s，第二次请求时被剔除，实验结果表明，利用每次服务运行时QoS数据动态更新服务QoS参数，保证了提供给用户的QoS数据的真实性、可信性。

表3 QoS变化时对服务推荐的影响

实验2：本文方法与其它方法在准确性上的比较

初选20个服务，之后每次增加20 个服务，对于本文方法与通过功能和QoS匹配方法 （FQM）进行比较，图2表明，由于本文方法中服务QoS参数得到了及时更新，在服务推荐过程中从历史数据挖掘用户偏好，发现的候选服务数相对较少，为用户提供了满意度较高的服务，并且随着服务数量的增加，其效果更加明显。

图2 服务推荐的准确性比较

实验3：本文方法与其它方法在时间开销上的比较

初选20个服务，之后每次增加20 个服务，比较本文方法与FQM 发现候选服务所用的时间，图3 表明，由于FQM 需通过服务器1查找候选服务，随着服务数量增多服务发现所用的时间大幅度增加，而本文方法由于引入了缓存机制，仅在缓存查找失败时，才需要访问服务器1，并且事先对服务信息库中的服务进行了聚类处理，使得服务推荐的实时性得到了明显改善。

图3 服务推荐的时间开销比较

5 结束语

服务发现是Web服务组合成功应用的关键，为了解决服务发现的效率和用户满意度问题，本文提出了基于情境的服务推荐方法。该方法建立情境模型描述服务执行信息和用户相关信息，利用服务历史执行信息建立和更新服务缓存，采用K－MEANS算法进行相似情境服务的聚类，基于功能和QoS匹配实现初步服务推荐，通过综合用户特征和用户评价相似性度量用户情境相似度，先计算各服务类内的用户相似度，而后据此进行类之间聚合，实现用户情境聚类，利用用户所在类对初步结果的预测评价和统计使用频率，使得推荐结果得到了进一步精化和优化，实例分析和实验结果表明，本文方法能够快速有效地发现质量良好、满足用户个性需求的服务。下一步工作重点是服务组合过程中服务发现的安全性问题。

［1］WANG P.QoS－aware Web services selection with intuitionistic fuzzy set under consumer’s vague perception ［J］.Expert System with Applications，2009，36 （3）：4460－4466.

［2］FENG Jianzhou，KONG Lingfu.Research on web service composition based on fuzzy QoS and preference weight［J］.Journal of Chinese Computer Systems，2012，33 （7）：1517－1521 （in Chinese）. ［冯建周，孔令富.基于模糊QoS 和偏好权重的Web服务组合方法研究 ［J］.小型微型计算机系统，2012，33（7）：1517－1521.］

［3］BAI Wen，LI Shuyu，DU Xuezhi.Fuzzy C－means clustering semantic web service discovery ［J］.Computer Engineering and Design，2012，33 （11）：4183－4186 （in Chinese）.［白雯，李蜀瑜，杜学智.模糊C－均值聚类语义Web服务发现 ［J］.计算机工程与设计，2012，33 （11）：4183－4186.］

［4］MA Hua，LI Jianhua，CHEN Songqiao，et al.Business useroriented service discovery model based on ontology clustering［J］.Computer Engineering，2007，33 （4）：215－217 （in Chinese）.［马华，李建华，陈松乔，等.基于本体聚类的面向业务用户服务发现模型 ［J］.计算机工程，2007，33 （4）：215－217.］

［5］FENG Zaiwen，HE Keqing，LI Bing，et al.A method for semantic web service discovery based on context inference ［J］.Chinese Journal of Computers，2008，31 （8）：1354－1363 （in Chinese）.［冯在文，何克清，李兵，等.一种基于情境推理的语义Web服务发现方法 ［J］.计算机学报，2008，31 （8）：1354－1363.］

［6］ZOU Jin’an.Exploration of semantic web service discovery based on QoS ［J］.Journal of Computer Applications，2009，29 （10）：2844－2846 （in Chinese）.［邹金安.基于聚类的QoS语义Web服务发现研究 ［J］.计算机应用，2009，29 （10）：2844－2846.］

［7］YANG Yueming，CHEN Lichao，XIE Binhong，et al.Study on approach of web services discovery based on clustering of users’context information ［J］.Computer Engineering and Design，2012，33 （4）：1442－1446 （in Chinese）.［杨岳明，陈立潮，谢斌红，等.基于用户情境聚类的Web服务发现方法研究 ［J］.计算机工程与设计，2012，33 （4）：1442－1446.］

［8］HUANG Chuangguang，YIN Jian，WANG Jing，et al.Uncertain neighbors collaborative filtering recommendation algorithm ［J］.Chinese Journal of Computers，2010，33 （8）：1369－1377 （in Chinese）.［黄创光，印鉴，汪静，等.不确定近邻的协同过滤推荐算法［J］.计算机学报，2010，33（8）： 1369－1377.］

［9］ZHU Hongkang，YU Xueli.Research on recommendation of web services based on QoS execution information ［J］.Computer Engineering and Applications，2010，46 （18）：237－239（in Chinese）. ［朱红康，余雪丽.基于服务QoS执行信息的Web服务推荐研究 ［J］.计算机工程与应用，2010，46 （18）：237－239.］

［10］WANG Guoxia，LIU Heping.Survey of personalized recommendation system ［J］.Computer Engineering and Applications，2012，48 （7）：66－76 （in Chinese）. ［王国霞，刘贺平.个性化推荐系统综述 ［J］.计算机工程与应用，2012，48 （7）：66－76.］

［11］WEN Junhao，QIN Jia，LIU Ling.Approach to web services selection under uncertain user preferences ［J］.Application Research of Computers，2010，27 （6）：2147－2149 （in Chinese）.［文俊浩，秦佳，柳玲.一种在用户偏好不确定情况下的Web服务选择方法 ［J］.计算机应用研究，2010，27 （6）：2147－2149.］

［12］Blake M B，Nowlan M F.A web service recommender system using enhanced syntactical matching ［C］／／Salt Lake City，Utah，USA：Proceedings of International Conference on Web Services，2007：575－582.

［13］Aciar S，Zhang D，Simoff S，et al.Informed recommender：Basing recommendations on consumer product reviews ［J］.IEEE Intelligent Systems，2007，22 （3）：39－47.

［14］Sufyan Beg MM，Nesar Ahmad.Web search enhancement by mining user actions ［J］.Information Science，2007，177（23）：5203－5218.

［15］ZHU Zhengzhou，WU Zhongfu，WU Kaigui，et al.E－learning services discovery algorithm based on user satisfaction ［J］.Computer Engineering，2009，35 （3）：71－73（in Chinese）.［朱郑州，吴中福，吴开贵，等.基于用户满意度的学习服务发现算法［J］.计算机工程，2009，35 （3）：71－73.］

［16］Laddawan Kulnarattana，Songsak Rongviriyapanish.A client perceived QoS model for web services selection ［C］／／6th International Conference on Electrical Engineering／Electronics，Computer，Telecommunications and Information Technology，2009：731－734.