杨岳明，陈立潮，谢斌红，潘理虎

（1.太原科技大学 计算机科学与技术学院，山西 太原030024；2.晋中师范高等专科学校 现代信息技术系，山西 晋中030600）

0 引 言

由于提供相同功能的Web服务越来越多，Web服务发现的研究重点逐渐由功能发现转向了非功能发现，即在功能发现的基础上，快速发现用户适合度较高的Web服务。目前已有相关文献在非功能性Web服务发现方面进行了描述。文献 ［1－3］对语义 Web服务集合进行了聚类预处理，有效缩小了服务查找范围，从而提高了Web服务发现的效率。文献 ［4－5］借助逻辑推理功能，实现对情境／语境信息的相关推理，从而能够自动地找到适宜用户的服务。文献 ［6－14］利用本体为情境信息建模，服务发现主要采用本体映射和本体推理的方法。首先对直接感知到的用户情境进行推理，得到与用户相关的隐含的情境，然后将用户隐含情境信息与服务描述模型直接匹配，从而发现对用户合适的服务。文献 ［15］提出了使用倒排索引优化面向组合的语义服务发现方法，该方法利用倒排索引的优势，极大地减少了搜索空间，从而能够快速定位侯选服务。

通过对现有文献进行分析，目前的Web服务发现方法存在以下不足：

（1）用户信息利用率不高。在目前的Web服务发现方法中，当前用户信息承担了服务过滤的角色，在服务发现时，其推理关系仅是服务语义的扩展。这些方法没有充分利用历史用户信息及其与当前用户信息之间的关系进行服务发现，而与当前用户有关的历史用户信息对服务发现具有重要的价值。

（2）没有兼顾时间效率和用户适合度。文献 ［1－3］对语义Web服务进行聚类的服务发现方法，虽然在一定程度上提高了Web服务发现的时间效率，但不能保证服务发现结果对用户的适合度。文献 ［4－14］借助逻辑推理的服务发现方法，虽然提升了服务发现结果对用户的适合度，但不能保证服务发现的时间效率。

针对以上不足，本文提出了一种基于用户情境聚类的Web服务发现方法，该方法实现了相似情境用户的聚类，并利用倒排索引快速得到了用户适合度较高的Web服务。

1 基于用户情境的本体建模

一般来讲，用户情境指的是用户自身及所处的环境信息，它既有动态的信息，也有静态的信息。为了充分利用用户情境信息进行Web服务发现，需要对这些动态和静态的信息进行刻画。本体是共享概念的形式化的规范描述，为了刻画用户情境信息，本文采用本体来为用户情境建模。

用户情境本体要能尽量全面准确地描述用户的情境信息，本文的用户情境本体模型 （如图1所示）包括用户描述、环境和平台3部分。

图1 用户情境本体

用户情境形式化描述如下：

U （UserDiscription，Environment，Platform）

其中UserDiscription表示用户描述，包括用户静态描述和个人偏好，即：

UserDiscription＝ （StaticDiscription，Preference）

而StaticDiscription又可以从职业、性别和年龄等方面来描述，即：

StaticDiscription＝ （Professional，Sex，Age）

Environment表示环境，包括地点和网络状态，即：

Environment＝ （Location，NetworkStatus）

Platform表示平台，包括PDA和电脑，即：

Platform＝ （PDA，Computer）

2 基于用户情境的聚类算法

聚类是数据挖掘领域的一个术语，它是指对一个对象集合进行不断分类，从而最终形成若干个集合，同一集合中的对象相似度很大，不同集合中的对象相似度很小。通过对大量用户情境信息及服务发现结果的分析，发现情境相似的用户所使用的Web服务具有较大的相似性。基于该特点，在进行Web服务查找之前可以预先进行用户的聚类，从而形成若干用户类，使Web服务的查找局限于当前用户所在类，这样Web服务发现的效率就可以进一步提高。

在对用户情境进行聚类处理中，本文借助BIRCH聚类算法得到了基于用户情境的聚类思想，即初始时每一个对象都看成是一个单独的新聚类，在接下来的迭代中，把那些类相似度大于阈值的类合并成一个新聚类，直到满足某个条件为止，其中类相似度为两个类中用户情境相似度的最小值。基于用户情境的相似度计算公式为：

SimUserContext＝Sim （UserDis，UserDis）＊W1＋Sim （Env，Env）＊W2＋Sim （Platf，Platf）＊W3

式中：W1——用户描述权重，W2——环境权重，W3——平台权重，W1＋W2＋W3＝l。公式中涉及的本体概念间的相似度计算方法可以参阅文献 ［16－18］，本文不在重复。

在上述基础上，本文提出的基于用户情境的聚类算法描述如下：

算法1：基于用户情境的聚类算法

输入：用户情境信息

输出：用户类的集合

Begin

Get（UserContext）；／／获取用户情境信息及其权重

初始化新聚类U＝ ｛（U1）， （U2），…， （Un）｝及阈值N；

Do｛

Val（Degree＿SimCluster）； ／／计算类相似度

将类相似度大于阈值N的聚类合并；

阈值N减少一个固定值；

｝While（特定用户所在类的对象个数小于某固定值K）；／／K值依据历史用户总数取值而定

Return （U）；

End

3 服务发现算法

Web服务发现面临的挑战是如何快速发现用户满意度较高的服务，本文利用情境相似的用户使用的Web服务具有较大相似性的特点，给出了一个基于用户情境聚类的Web服务发现流程框架 （如图2所示）。

为了实现图2的服务发现流程框架，具体的服务发现算法描述如下：

图2 服务发现流程框架

算法2：基于用户情境聚类的Web服务发现算法

输入：用户服务请求

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

Begin

Request（User.need）； ／／用户提出服务请求

Function（All Web Service）＝＝＞C1＝ ｛S1，S2，…，Sn｝； ／／进行Web服务功能发现得到侯选服务集一

Create（User＿database）；／／创建用户数据库

C1.Si.history＿user＆＆current＿user＝＝＞ User＿database； ／／将当前用户信息与侯选服务集一中所有服务的历史用户信息同时加入用户数据库中

Create（User＿InvertedIndexList）； ／／依据用户数据库创建用户倒排索引表，包括用户和服务及使用频率

Cluster（User＿database.UserContext）； ／／对用户数据库，采用算法1对用户进行聚类

Select （User＿InvertedIndexList.CurrentUserClass）；／／筛选出当前用户所在类的用户倒排索引表

Add （Ui.Si.UseFrequency）； ／／统计当前用户所在类的所有服务的使用频率

Sort（Si.UseFrequency）＝＝＞C2＝ ｛…，Si，…，｝；／／按使用频率降序排序，得到侯选服务集二

Return（C2）； ／／将服务发现结果返回给用户

End

4 实例分析

下面通过一个实例来说明如何利用本文方法进行服务发现。我们采用SQL Server 2005存储200个Web服务，其中包括10个天气预报Web服务。假设有一个山西晋中的用户，他想使用一个Web服务来查询天气情况。

采用文献 ［1－3］的语义聚类 Web服务发现方法，服务发现结果仅局限于能够快速发现10个天气预报服务，即侯选服务集：（S1，S2，S3，S4，S5，S6，S7，S8，S9，S10）。

采用本文方法的服务发现过程如下：

步骤1：山西晋中的用户提出查询天气情况的请求。

步骤2：进行天气预报的Web服务发现，得到侯选服务集一：（S1，S2，S3，S4，S5，S6，S7，S8，S9，S10）。

步骤3：创建用户数据库，并将当前用户情境信息与侯选服务集一中所有服务的历史用户情境信息同时加入用户数据库中 （如表1所示）。由于天气预报服务提供者给出用户位置信息是关键因素，因此为了减少用户情境信息的复杂度，表1中用户情境信息只列出了位置信息，其中Ui（i＝1，…，10）代表历史用户，U代表当前用户。

表1 用户数据库

步骤4：依据表1建立用户倒排索引表 （如表2所示）。

步骤5：利用算法1，对表1中的用户进行聚类 （设置K＝3）。

初始化聚类：（U1） （U2） （U3） （U4） （U5） （U6）（U7）（U8）（U9）（U10）（U）；

第一次聚类：（U1，U9）（U2，U5）（U3）（U4，U8）（U6）（U7，U）（U10）；

第二次聚类：（U1，U9，U10）（U2，U5）（U3，U4，U8）（U6）（U7，U）；

第 三次聚类：（U 1，U 9，U 1 0）（U 2，U 5，U 7，U）（U3，U4，U8）（U6）。

表2 用户倒排索引表

步骤6：按当前用户所在类进行筛选，得到当前用户所在类的倒排索引表 （如表3所示）。

表3 当前用户所在类的倒排索引表

步骤7：统计当前用户所在类的所有服务的使用频率：S2 ［3］，S4 ［5］，S8 ［1］。

步骤8：按使用频率降序排序，得到侯选服务集二：S4，S2，S8。

步骤9：将侯选服务集二返回给用户。

最终，山西晋中的用户可以优先使用S4，其次是S2。与文献 ［1－3］的方法相比，本文的方法有效提升了服务发现结果对用户的适合度。

5 实验分析

为了验证本文方法在服务发现时间方面的优越性，将本文方法与文献 ［4］的情境推理方法进行比较，分别测试它们的花费时间。最初选取了20个服务作为测试样本，然后每次递增20个服务，共选取了10个样本集。进行了10组实验，记录了每次实验所花费的时间，分别得到了采用两种方法的测试样本服务数量与花费时间之间的关系，如图3和图4所示。

实验结果表明，两种服务发现方法所花费的时间都随测试样本服务数量的增加呈线性增长，而本文的方法在时间花费方面明显优于文献 ［4］的情境推理方法。这说明本文的方法有效提升了服务发现的时间效率。

6 结束语

本文提出了一种基于用户情境聚类的Web服务发现方法。该方法在功能发现的基础上，构建了用户情境本体模型，通过对情境相似的用户进行聚类，将服务查找范围局限于当前用户所在的类，并利用倒排索引将该类中历史使用频率较高的Web服务提供给当前用户。实例分析和实验结果表明，使用该方法可以快速得到用户适合度较高的Web服务。但是，本文的方法是基于用户的角度进行了服务发现，没有考虑服务本身的特性，在一定程度上影响了服务发现的效率。这将是我们下一步所要研究的问题。

［1］HE Chaobo，CHEN Qimai.Fast approach for semantic web service discovery ［J］.Computer Engineering and Design，2010，31 （12）：2936－2939 （in Chinese）. ［贺超波，陈启买.快速语义Web服务发现方法 ［J］.计算机工程与设计，2010，31 （12）：2936－2939.］

［2］SUN Ping，JIANG Changjun. Using service clustering to facilitate process－oriented semantic web service discovery ［J］.Chinese Journal of Computers，2008，31 （8）：1340－1353 （in Chinese）.［孙萍，蒋昌俊.利用服务聚类优化面向过程模型的语义 Web服务发现 ［J］.计算机学报，2008，31 （8）：1340－1353.］

［3］LIU Xingwei，YAO Shuhuai.A DHCS－based discovery mechanism of semantic web services ［J］.Computer Applications andSoftware，2007，24 （7）：173－177 （in Chinese）. ［刘兴伟，姚书怀.基于层次聚类的语义 Web服务发现算法 ［J］.计算机应用与软件，2007，24 （7）：173－177.］

［4］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.］

［5］NIU Wenjia，CHANG Hang，WANG Xiaofeng，et al.Semantic web service discovery based on context and action reasoning［J］.Pattern Recognition and Artificial Intelligence，2010，23（1）：65－71 （in Chinese）.［牛温佳，常亮，王晓峰，等.基于语境和动作推理的语义 Web服务发现 ［J］.模式识别与人工智能，2010，23 （1）：65－71.］

［6］JIN Zhi，LIU Lin.Web service retrieval：An approach based on context ontology ［C］.Chicago，USA：Proceedings of the 30th Annual International Computer Software and Applications Conference，2006：513－520.

［7］Aimrudee Jongtaveesataporn，Twittie Senivongse.A context type model for context＿aware discovery of web services ［C］.The Third IASTED International Conference on Advances in Computer Science and Technology.Anaheim，CA，USA：ACTA Press，2007：96－101.

［8］YANG Stephen J H，ZHANG Jia，CHEN Irene Y L.A JESS－enabled context elicitation system for providing context－aware web services ［J］.Expert Systems with Applications，2008，34 （4）：2254－2266.

［9］Christos Doulkeridis，Nikos Loutas，Michalis Vazirgiannis.A system architecture for context－aware service discovery ［J］.Electronic Notes in Theoretical Computer Science，2006，146（1）：101－116.

［10］HAN Weili，SHI Xingdong，CHEN Ronghua.Process－context aware matchmaking for web service composition ［J］.Journal of Network and Computer Applications，2008，31（4）：559－576.

［11］HONG Jongyi，Suh Euiho，KIM Junyoung，et al.Contextaware system for proactive personalized service based on context history ［J］.Expert Systems with Applications，2009，36 （4）：7448－7457.

［12］Alessandra Toninelli，Antonio Corradi，Rebecca Montanari.Semantic－based discovery to support mobile context－aware service access ［J］.Computer Communications，2008，31（5）：935－949.

［13］LI Li，LIU Dongxi，Athman Bouguettaya.Semantic based aspectoriented programming for context－aware web service composition［J］.Information Systems，2011，36 （3）：551－564.

［14］Christos Doulkeridis，Michalis Vazirgiannis.CASD：Management of a context－aware service directory ［J］.Pervasive and Mobile Computing，2008，4 （5）：737－754.

［15］KUANG Li，DENG Shuiguang，LI Ying，et al.Using inverted indexing to facilitate composition－oriented semantic service discovery ［J］.Journal of Software，2007，18 （8）：1911－1921（in Chinese）. ［邝砾，邓水光，李莹，等.使用倒排索引优化面向组合的语义服务发现 ［J］.软件学报，2007，18 （8）：1911－1921.］

［16］WANG Gang，QIU Yuhui.Study on text clustering based on ontology and similarity ［J］.Application Research of Computers，2010，27 （7）：2494－2497 （in Chinese）.［王刚，邱玉辉.基于本体及相似度的文本聚类研究 ［J］.计算机应用研究，2010，27 （7）：2494－2497.］

［17］XU Dezhi，WANG Huaimin.Concept semantic similarity research based on ontology ［J］.Computer Engineering and Applications，2007，43 （8）：154－156 （in Chinese）. ［徐德智，王怀民.基于本体的概念间语义相似度计算方法研究 ［J］.计算机工程与应用，2007，43 （8）：154－156.］

［18］ZHANG Gongjie，ZHAO Xiangjun，CHEN Kejian.Ontology oriented semantic similarity calculation and application in retrieval［J］.Computer Engineering and Applications，2010，46 （29）：131－133 （in Chinese）.［张功杰，赵向军，陈克建.面向本体的语义相似度计算及在检索中的应用 ［J］.计算机工程与应用，2010，46 （29）：131－133.］