一种基于标签的层次Web服务聚类方法

李蓉+叶俊民+杨艳

摘 要： 提出一种基于Fuzzy c-means聚类方法的模糊服务聚类方法SGCom，该方法首先标注服务的名称、功能和使用对象，再用改进的FCM算法对服务的名称聚类，用比较相似度的方法对服务的其他元素聚类，并综合得出聚类结果。由于该方法基于服务的注册信息，不局限于单一的服务描述语言，得到的结果是服务属于某个类别的比率，在服务发现时可以根据用户设定的阈值推荐服务类别，避免了靠近类簇边界上的服务难以被准确分类的问题。

关键词： FCM算法； Web服务； 服务聚类； 服务相似度

中图分类号：TP3-0 文献标志码：A 文章编号：1006-8228（2017）11-30-05

A tag based hierarchical Web service clustering method

Li Rong， Ye Junmin， Yang Yan

（Computer Science Department， Central China Normal University， Wuhan， Hubei 430079， China）

Abstract： In this paper， a Fuzzy c-means based fuzzy service clustering method SGCom is proposed. When using this method， the names， functions， and goals of the Web services are tagged， the improved FCM algorithm is used to cluster the names of services， and similarity of other Web service elements is calculated to cluster them. Comprehensive cluster results can be obtained through these steps. The SGCom method is bases on service registration information and is not limited to a single service description language， so the result obtained is the membership degree of service that belongs to a category， and the category of a service can be recommended according to the threshold set by the user when the service is found， which solves the problem that the services close to the cluster boundaries are difficult to be classified accurately by the hard clustering methods.

Key words： FCM algorithm； Web service； service clustering； service similarity

0 引言

隨着网络的快速发展，网络服务资源的数量飞速增长。ProgrammableWeb （PWeb）是一个著名的网络服务发布网站，在2012年其上发布的Web服务有6400多个[1]，而在2017年初，服务数量已经达到15700多个，不到五年时间服务数量增加超过一倍。大量增长的服务给使用者提供了更多更好的选择，但是也对服务选择和推荐造成了更大困难，特别是对服务选择和推荐的速度提出了更高的要求。

服务聚类是服务选择和推荐的一种有效的支持手段[2]，按照一定的规则对大量的服务聚类，服务选择时在相关的服务类别中选择合适的服务，这样缩小了服务查找的范围，加快了查找速度，提高了查找的正确率。现在已经有很多服务聚类方法。文献[3]提出了一种基于网络图的服务聚类算法SNTClus。文献[4]提出一种根据服务描述的词语相似度聚类服务的办法CAS。文献[5]提出一种使用加权的模糊c-means （FCM）方法WFCM聚类服务的方法。

这些聚类方法都从服务的特点出发，应用基本的数据聚类的方法，并做了一定改进，提高了聚类效果，但仍然存在以下问题。

⑴ 多数服务聚类的方法只能支持某一种服务文档。文献[6-7]等支持用WSDL描述的服务聚类，文献[8-9]等支持用OWL-S描述的服务聚类，现在有很多RESTful服务用自然语言描述，对这类服务的聚类方法研究的不多。

⑵ 多数服务聚类方法服务聚类后只能属于某一个服务类别，没有考虑概念的模糊性问题。很多服务可能属于多个类型，比如天气预报服务，因为旅游出行需要了解天气信息，因此该服务可以属于“出行”类别，同时因为社会生活中人们经常关注天气情况，该服务也可以分类在“社会生活”类别。在PWeb中的很多服务都有多个标签，可以把服务归为不同的类别。因此只把服务归为某种类别的硬聚类的方式有所欠缺。

本文提出了一种基于Fuzzy c-means聚类方法的模糊服务聚类方法SGCom，该方法首先标注服务的名称、功能和使用对象，再用改进的FCM算法对服务标签聚类。该方法基于服务的注册信息，不局限于单一的服务描述语言，得到的结果是服务属于某个类别的比率，在服务发现时可以根据用户设定的阈值推荐服务类别。

1 数据准备

数据准备的结果如图1所示。在进行服务聚类之前首先要获得服务的名称、功能等信息，在PWeb中注册的服务使用短文本标注的方式提供服务的描述信息，也有部分用户标签信息。endprint

由于服务标注使用自然语言，需要对其内容进行一定的约束和处理，本文用自然语言处理工具包NLTK实现这些功能。NLTK是主流的自然语言处理工具包，能非常方便地在Python中调用，能方便地使用包括WordNet在内的多种词典。最后得到服务的定义如下。

⑴

其中，SName表示服务的名称，SRole表示服务针对的对象，SGoal表示该服务的功能目标。

⑵

其中GOperation说明完成功能目标需要的操作，GObject说明操作的对象，GManner说明操作的方式。每个功能性目标定义的操作必须要有一个操作对象，但可以不定义操作的方式。

2 服务的相似度计算方法

本文对服务的聚类关注于对服务的名称SName的聚类和对服务的功能性目标SGoal的聚类。SName说明服务的主要功能，用动宾短语表示，因此在计算相似度前需要先分词，得到单独的动词和名词，见公式⑶，再根据公式⑷计算其相似度。

⑶

简单的用英文表示的名词和动词的语义相似度可以用WordNet来计算。WordNet是常用的英语检索词典[10]，其中的名词和动词具有层次关系，可以方便地计算词语间的相似度。本文使用常用的基于WordNet的词语相似度的计算方法Resnik算法计算相似度[11]。

定义1 SName相似度。

SName相似度表示服务的名称的相似程度，可表示为：

⑷

其中s1和s2为需要比较的服务，表示使用Resnik算法计算的动词之间和的相似度值，ωsp和ωso为用户定义的权重，以区别操作和操作对象对服务相似度的贡献程度，ωsp和ωso在0到1之间，即ωsp，ωso∈[0，1]。

每个服务s有一组功能性目标描述的集合SGoal={sg1，sg2，…，sgn}，求取两个服务的相似度需要比较两个服务的所有sgi的相似度，再求其最大值，见公式⑸。

定义2 SGoal相似度。

SGoal相似度表示服务的目标模型中的功能性目标属性的相似程度，可表示为：

⑸

其中n和m分别代表服务s1和s2中功能性目标描述的个数，由公式⑹给出。

⑹

公式⑹求出sg中三个分量的相似度的平均值。

定义3 服务相似度。

服务相似度表示两个服务的相似程度，可表示为：

⑺

其中α和β是调整系数，调整SNameSim和SGoalSim在计算结果中所占的权重，α+β=1。

3 聚类中心的计算方法

在FCM算法中，每次迭代时都需要调整k个类簇的聚类中心，在基本FCM定义中考虑参与聚类的样本点是数字，因此采用求取归入同一类簇的所有样本点的平均数来计算新的聚类中心[12]。但是在本文的应用中参与聚类的是词语，很难求取词语的平均数，因此本文考虑求取同一类簇的所有样本点的到老聚类中心的平均距离，再找到在本类中和老聚类中心的距离接近平均距离的那个样本点，即可得到新的聚类中心。

定义4 模糊平均语义距离。

模糊平均语义距离表示在一定范围内，所有其他元素到某一个元素的平均的模糊语义距离。给定样本点的集合和隶属度的集合，给定一个聚类中心xi，xi∈S，集合中的所有元素到的模糊平均距离可以定义为：

⑻

定义5 模糊元素可替。

模糊元素可替表示一个样本点可以被另一个样本点替换。给定样本点的集合和隶属度的集合，给定一个样本点xi，xi∈S，有样本点xj，xi≠xj，满足公式⑻，则xi和xj模糊元素可替，记为。

⑼

其中ε为一个给定的阈值，在0到1之间，可以根据集合S中服务的粒度设定。

由以上定义，传统FCM算法中聚类中心pi的计算公式可以变换成：

⑽

公式⑽表示当原来的聚类中心p和服务xj满足模糊元素可替时，xj可以作为新的模糊聚类中心。

4 Web服务聚类方法

本文的层次聚类方法先用FCM算法对服务的SName属性聚类，得到初始的k个聚类中心和服务的隶属度矩阵。因为SGoal信息是对服务功能的细化描述，为了提高聚类准确度，以上面算出的k个聚类中心为中心，比较服务的SGoal相似度，重新聚类服务，然后综合以上两种聚类方法的结果，得到所需服务聚类中心和隶属度矩阵。

4.1 计算聚类中心

算法1 FCM聚類中心计算算法

FCMCenter（S， U， p， th）

输入：S={s1，s2，…，sn}，表示所有服务的集合；

U={u1，u2，…，un}，表示所有服务对应的隶属度的集合；

p表示聚类中心；

th表示阈值。

输出：p表示计算后的聚类中心。

1. for i=1 to n

2. d=SNameSim（u1*si，p）；

3. fdist=d/（n-1）；

4. for i=1 to n

5. if （SNameSim（u1*si，p）-fdist）6. p=si；

7. return p；

FCMCenter算法计算服务集合S的新的聚类中心，新的聚类中心要求变化距离小于th，可以取th为0.01，如果找不到新的使变化距离小于th的服务，则现在的聚类中心是最优的。

4.2 使用FCM算法对SName聚类

算法2 SName聚类算法endprint

SNAMEC（S， k， n， th）

输入：S={s1，s2，…，sn}，表示所有服务的集合；

k表示k个聚类中心；

n表示服务的数量；

th表示用户定义的阈值；

输出：U表示服务隶属度矩阵；

p={p1，p2，…，pk}，表示最后得到的聚类中心；

1. m=0；

2. 随机选取k×n个在[0，1]之间的数，初始化隶属矩阵。

3. Do

4. z=0；

5. for i=1 to k

6. uk=U中的第k列；

7. pi=FCMCenter（S，uk，pi，0.01）；

8. for i=1 to k

9. for j=1 to n

10. for t=1 to n

11. z=；

12. uij=1/z；

13. 更新隶属度矩阵；

14. m=m+1；

15. Until （<=th）

16. Return ；

17. Return {p1，p2，…，pk}；

算法迭代更新隶属度矩阵U和聚类中心，直到聚类中心的变化小于th时停止，th一般设置成0.01。算法中uij代表隶属度矩阵U中的每一个元素，代表第m次迭代得到的k×n的隶属度矩阵。

4.3 使用相似度计算的方法对SGoal聚类

算法3 SGoal聚类算法

SGoalC（S， P， k， n）

输入：S={s1，s2，…，sn}，表示所有服务的集合

p={p1，p2，…，pk}，表示SNAMEC算法得到的聚类中心；

k表示k个聚类中心；

n表示服务的数量；

输出：U表示最后得到的服务隶属度矩阵。

1. for i=1 to k

2. for j=1 to n

3. uij=SGoalSim（sj，pi）；

4. 更新隶属度矩阵U；

5. Return U；

算法以前面得到的聚类中心为基础，比较每个服务和每个聚类中心的相似度，把结果写到新的隶属度矩阵U中。

4.4 整合聚类结果

算法4 聚类组合算法

SGCom（U， U'， P， k， n， α， β）

输入：U表示SNAMEC算法得到的服务隶属度矩阵；

U'表示SGoalC算法得到的服务隶属度矩阵；

P={p1，p2，…，pk}，表示SNAMEC算法得到的聚类中心；

k表示k个聚类中心；

n表示服务的数量；

α和β分别表示U和U'的权重；

输出：UNew表示最后得到的服务隶属度矩阵。

1. for i=1 to k

2. for j=1 to n

3. unewij=α*uij+β*u'ij；

4. 更新隶属度矩阵UNew；

5. Return UNew；

算法综合SNAMEC和SGoalC算法得到的服务隶属度矩阵，得到隶属度矩阵UNew。U和对结果的贡献由权重标记，具体权值可以根据实验确定。

5 实验

5.1 實验准备

为了检验本文提出的服务聚类方法SGCom，我们做了模拟实验。实验环境包括Intel Core I5 1.7GHz CPU，4GB内存，Windows 7操作系统，MySQL 5.5数据库服务器，Apache 2.4应用服务器，开发语言采用Java，使用JDK 6.0 Java虚拟机。

服务资源网站PWeb上提供了15000多个服务，已经有132000多个注册会员。我们利用网站提供的API，使用爬虫软件爬取了大量的服务，通过数据分析，选取服务数量最多的前6个应用领域作为测试的基础，这6个服务类别和它们中的服务数量如表1所示。我们从每类服务中选取功能比较复杂、描述信息比较详细的100个服务，人工建立服务的标签。

5.2 实验分析

本文先通过人工判断对300个服务分类，再把通过算法得到的聚类结果与人工聚类结果比较。评价标准采用常用的熵、F值和聚类纯度，这些都是信息检索领域的常用评价指标[13]。通常用几个指标综合评价聚类效果，一个聚类的F值越高、纯度越高、熵越低，则聚类效果越好。

我们使用上面提出的聚类组合算法SGCom与其他算法比较。参与比较的算法包括第一节中提到的SNTClus算法、CAS算法和WFCM算法。

因为SGCom算法中有两个参数，分别表示用SNAMEC算法聚类的结果和用SGoalC算法聚类的结果的权重。本文也设计了实验讨论的选取对聚类效果的影响。

实验1 SGCom算法参数讨论

参数α和β满足：α，β∈（0，1）且α+β=1。

分别选取α的值为0.2到0.8，对应的β取值从0.8到0.2，针对我们准备的6个不同领域共600个服务，得到聚类的F值、纯度和熵，如表2所示。

从实验结果可知α=0.4，β=0.6时，针对我们的数据集，聚类效果比较好。这是因为数据集中的服务都经过人工标注，服务的功能性目标描述非常完整，能很好地补充服务信息。如果是服务功能性目标描述不完整的服务，可能SGoalC算法的聚类结果对服务聚类的贡献不大，应该增大α的取值。endprint

實验2 聚类效果分析

SGCom算法与其他算法的聚类性能比较如图2所示。

从实验结果可知SGCom算法的F值和纯度最高，熵最低。SGCom算法和同样使用模糊聚类的WFCM算法比较，F值和纯度分别提升了0.66和0.61，熵降低了0.55，说明增加服务的描述信息，并引入RGPS模型有效地组织这些信息，可以提高服务聚类的效果。

6 结束语

本文提出了一种基于标签的服务聚类方法，首先通过对服务描述分析，将Web服务按照名称、角色和目标标注，然后使用混合的FCM方法对服务聚类，为以后的服务选择和推荐提供基础。在下一步工作中，将继续深入研究服务的半自动建模方式及服务聚类结果和给定的初始类簇数k之间的关系。由于文中现在使用的服务来自PWeb中的一些类别，已经分好了类，因此本文没有考虑k值设定的问题，但是对于不知道分类的服务，k值是否合理决定着服务聚类的效果尚不清楚。k值的选择对本文提出的聚类算法的影响值得深入研究。

参考文献（References）：

[1] 李征，王健，张能等.一种面向主题的领域服务聚类方法[J].计

算机研究与发展，2014.51（2）：408-419

[2] Elgazzar K， Hassan A E， Martin P. Clustering WSDL

Documents to Bootstrap the Discovery of Web Services[C]. 2010 IEEE International Conference on Web Services. IEEE Computer Society，2010：147-154

[3] Li P， Wen J， Li X. SNTClus： A Novel Service Clustering

Algorithm based on Network Analysis and Service Tags[J]. Wydawnictwo SIGMA-NOT， 2013.

[4] 大橋宏輝. Calculating Word Similarity for Context Aware

Web Service Clustering[J]. Ieice Technical Report Sc Services Computing，2013.112：29-31

[5] Dorn C， Dustdar S. Weighted fuzzy clustering for

capability-driven service aggregation[C].Service-Oriented Computing and Applications （SOCA）， 2010 IEEE International Conference on. IEEE，2010：1-8

[6] 张秀伟.RGPS驱动的个性化Web服务推荐方法研究[D].武

汉大学硕士学位论文，2014.

[7] Q. Yu and M. Rege. On service community learning： A

co-clustering approach[C]. In Proc of Web Services （ICWS）， 2015 IEEE International Conference on Web Services，2015：283-290

[8] C.B. Pop， V.R. Chifu， I. Salomie， M. Dins Q. Yu and M.

Rege. On service community learning： A co-clustering approach[C]. In Proc of Web Services （ICWS）， 2016 IEEE International Conference on，2016：283-290

[9] Pop C B， Chifu V R， Salomie I， et al. Semantic Web

Service Clustering for Efficient Discovery Using an Ant-Based Method[C]. Intelligent Distributed Computing IV-Proceedings of the International Symposium on Intelligent Distributed Computing-IDC 2010， Tangier， Morocco， September，2010：23-33

[10] Fellbaum C， Miller G. WordNet： an electronic lexical

database[J]. Cognition Brain & Behavior，1998.

[11] Ahsaee M G， Naghibzadeh M， Naeini S E Y. Semantic

similarity assessment of words using weighted WordNet[J]. International Journal of Machine Learning & Cybernetics，2014.5（3）：479-490

[12] Bezdek J C， Ehrlich R， Full W. FCM： The fuzzy c-means

clustering algorithm[J]. Computers & Geosciences，1984.10（2-3）：191-203

[13] Wang B B， Mckay R I B， Abbass H A， et al.

AComparative Study for Domain Ontology Guided Feature[C]. Proceedings of the 26th Australasian computer science conference-Volume 16. Australian Computer Society，Inc.，2003：69-78endprint