DOI: 10.11817/j.issn.1672-7207.2018.12.012
基于LDA和模糊C均值的Web服务多功能聚类
张祥平，刘建勋，肖巧翔，石敏，曹步清
(湖南科技大学 计算机科学与工程学院，
知识处理与网络化制造湖南省普通高校重点实验室，湖南 湘潭，411201)
摘要：基于Web服务发现方法通常是将Web服务聚在某一个固定的功能类中，导致该Web服务的其余功能特性被忽略，Web服务的资源利用率降低的问题，提出一种基于LDA和模糊C均值的Web服务多功能聚类方法。首先，从ProgrammableWeb.com网站上爬取Web服务数据，并抽取Web服务描述文档；其次，使用LDA主题模型对Web服务描述文档进行建模，获得包含不同功能信息的文档主题矩阵；最后，在文档主题矩阵上使用模糊C均值算法将Web服务聚类到不同的功能类中，完成Web服务的多功能聚类。研究结果表明：Web服务的多功能特性切实提高了服务发现的精度。
关键词：Web服务；模糊C均值算法；LDA主题模型；Web服务发现
中图分类号：TP301 文献标志码：A 文章编号：1672-7207(2018)12-2986-07
Web services clustering with multi-functionality based on LDA and fuzzy C-means algorithm
ZHAGN Xiangping, LIU Jianxun, XIAO Qiaoxiang, SHI Min, CAO Buqing
(Key Laboratory of Knowledge Processing & Networked Manufacturing of Hunan Province,
School of Computer Science and Engineering, Hunan University of Science & Technology, Xiangtan 411201, China)
Abstract: Considering that Web service discovery usually classifies Web service into one fixed cluster, which neglects other important function attributions of the Web service, a Web services clustering method with multi-functionality was proposed based on LDA and fuzzy c-means algorithm. The method firstly crawled Web services from ProgrammableWeb.com and extracted the description document of them. Then LDA was used to model the description documents of Web services, and the document-topic matrix which contained different functional information was obtained. Finally, they were clustered into various clusters with similar functionality by exploiting fuzzy C-means algorithm. The results show that the multifunctionality of Web services effectively improve the accuracy of Web services discovery.
Key words: Web services; fuzzy C-means algorithm; LDA topic model; Web services discover
Web服务是一种依赖于互联网的应用系统，是由组织机构发布的完成一定功能的在线应用服务，其他使用者能够通过Internet来访问并使用[1]。随着Web服务数量的快速增大，通过基于Web服务的应用，如服务发现[2-3]、服务组合[4-5]等来管理Web服务就显得十分必要。对Web服务进行聚类是一种促进Web服务发现的有效手段，能够有效地提高Web服务搜索引擎的搜索能力[6-7]。在用户搜索Web服务时，通常是键入自己需要的功能名称，搜索引擎通过用户请求的多个功能，在具有与这些功能相似的功能簇中选择满足用户功能需求的Web服务，在功能簇中进行查找将有效地降低Web服务的搜索空间。已有研究表明，Web服务的标签是Web服务功能的概括说明[8],可以利用标签对Web服务进行功能划分。API结构如图1所示，该API具有5个标签，这表明该API具有5种不同的功能。若按照传统的聚类方法，则只能发现该API的1个功能“Tools”，而其余的如“3D”和“Visualizations”等功能就无法被发现，无法被利用。在Web服务聚类及发现中，这将造成很大的资源浪费。
图1 API结构图
Fig. 1 The structure of API
目前关于Web服务聚类的研究可以归纳为3类：基于功能属性的Web服务聚类研究[9]；基于非功能属性的Web聚类研究[10-11]；对于现有的Web服务聚类算法进行改进的研究[12-13]。其中，基于功能属性的Web服务聚类能够提高Web服务搜索引擎的能力。基于功能相似度的Web服务聚类方法[6-7]，首先从WSDL文档中抽取Web服务的关键特征，通过计算Web服务之间的余弦相似度等方法计算Web服务之间的相似性。LIU等[14]提出从Web服务描述文本中提取出内容、上下文、主机名和服务名这4个特征实现Web服务聚类。POP等[15]提出使用基于蚁群的方法，用于基于语义相似度的Web服务聚类；黄兴等[16]结合Mashup服务的描述文档和相应标签，提出一种基于Mashup服务相似性的K-Means算法进行服务聚类。此外，基于非功能属性的Web服务聚类研究主要考虑Web服务的质量(QoS，即quality of service)，通常使用到的QoS包括吞吐量、可用性、执行时间等。但是，这些工作没有利用到Web服务的多个标签，而仅仅是将Web服务固定地分到1个功能类中，忽略了Web服务的多功能特性。实际上，Web服务的标签就体现了它的功能属性，而多个标签正好表征了Web服务的多功能特性。基于此，本文提出一种Web服务多功能聚类方法，通过将LDA模型与模糊C均值算法进行结合，实现对Web服务的多功能划分。
1 方法介绍
1.1 LDA主题模型
LDA由BLEI等[17]提出的一种主题生成模型，是一种非监督的机器学习算法。LDA可以将每篇文档属于的主题以概率分布的形式给出，能够用于识别大规模文本中隐含的主题信息。它是1个多层的概率模型，包含词、文档和主题3层结构。LDA假设词由1个主题混合产生，同时，每个主题是在固定词表上的一个多项式分布，这些主题由集合中的所有文档共享。
图2所示为LDA主题模型的生成过程。假设文档集D中，M为文档总数，Nm为第m个文档的单词总数，k为主题个数，Zm,n为第m个文档中第n个词的主题，wm,n为第m个文档中的第n个词。
为服从β为参数的Dirichlet分布(它表示第k个主题下的词分布)，
为服从以α为参数的Dirichlet分布(它表示第m个文档下的主题分布)。给定1个文档集，wm,n为可以观察到的已知变量，β和α为根据经验给定的先验参数，Zm,n，和都是未知的隐含变量[18]。本文采用吉布斯采样(Gibbs Sampling)方法求得和，所有变量的联合分布为：
图2 LDA主题模型的盘子表示法
Fig. 2 Plate Notation of LDA Model
(1)
LDA的主要作用是推断出每一个Web服务描述文档的主题分布，所有Web服务描述文档的主题分布矩阵可以被用于Web服务聚类。
1.2 模糊C聚类
模糊聚类是监督机器学习的一种，它来源于模糊理论。在经典集合论中，论域X中的某一元素x，要么完全属于某集合A，要么完全不属于A[19]，两者必居其一，元素之间的分类有清晰的分界，但这并不能很好地反映数据点与类中心的实际关系。这是因为在现实世界，1个对象只是在某一个程度上属于某一个簇[20]。比如1个Web服务就会有多个功能标签，固定地把1个Web服务分到某一个功能标签中，则会忽略其他功能标签所表征的Web服务多功能特性，因此，采用模糊C均值聚类算法来计算得到每个Web服务属于某个功能标签的程度。模糊C均值聚类能够把n个向量xi(i=1，2，…，n)划分到人为指定的C个模糊簇中，并且生成隶属度矩阵。隶属度矩阵用于表示每一个向量属于某个簇的概率。模糊C均值的主要思想是使得类间的数据差别尽可能的大，类内之间的数据差别尽可能小。模糊C均值聚类算法在目标函数中增加了模糊因子m，用于控制模糊类间的分享程度，当m=1时，模糊聚类就退化成k-means聚类。其目标函数[21]为
(2)
其中：d(xk，vi)为xk与vi之间的距离，本文采用余弦距离作为每个Web服务到聚类中心服务的距离。通过使目标函数值达到最小来满足其主要思想，下面给出聚类中心和隶属度更新规则：
(3)
(4)
其中：V={v1，v2，v3，…，vc}，表示聚类中心点集；U=[uij]c×n，为隶属度矩阵。
模糊聚类算法流程如下。
第1步：随机初始隶属度矩阵U，初始化聚类中心V，初始化点间距离。
第2步：计算聚类中心V。
第3步：更新隶属度矩阵U。
第4步：检查是否满足迭代结束条件，若满足，则结束迭代，否则转到第2步。
通过上述算法流程，可以获得隶属度矩阵用于Web服务的多标签分类。
2 实验步骤
本文提出的方法总体框架如图3所示。从ProgrammableWeb.com网站上爬取的数据包含了Web服务的描述文档以及它们的标签信息。首先，对获得的Web服务的描述文档进行预处理，得到预处理后的描述文档。接着，采用LDA主题模型训练得到每一个Web服务预处理描述文档的文档主题分布向量。将获得的向量进行模糊聚类，进而完成对Web服务的多功能聚类。
图3 本文方法总体框架
Fig. 3 The overall framework of this approach
2.1 文本预处理
Web服务的开发者在上传该Web服务时会添加对该服务的功能描述文档。Web服务的描述文本描述了该Web服务的全部功能。根据Web服务的描述文档，对Web服务进行多功能分类。由于有些词条含有大量的无用信息，为了提高文本聚类的精确度，首先对描述文档进行预处理。
预处理主要包含以下几个步骤。
1) 文本数据的获取与整理：从ProgramableWeb.com上爬取了12 919个Web服务以及它们的描述文档。对这些文档进行切割，使得每个文本文件只包含1个Web服务的描述文档。
2) 文本令牌化(tokenize)：将单词按照空格进行分词，并且将标点符号与单词分开。这里使用的是python中的自然语言处理工具包NLTK(Natural Language Toolkit)进行处理[22]。
3) 过滤停用词(stop words)：英文中有很多无效的词以及标点符号，如“a”，“to”和“，”，这些没有实际意义的词或符号被称为停用词。本文使用NLTK中自带的停用词表用于去除停用词。
4) 词干化处理(stemming)：在英文中，同一个单词会因为时态、人称的不同而有不同的表现形式，如“provide”，“providing”和“provides”，它们实际上都是同一个单词“provide”，若将这些单词看作是不同的单词，那么之后的实验结果准确度将会降低。故需要进行词干化处理。
通过以上4个步骤，可获得WSDL文档中有意义的词语，之后对这些处理过的文档使用LDA模型进行主题建模。
2.2 LDA(latent dirichlet allocation)主题建模
假设所爬取得到Web服务的描述文档的集合D={d1，d2，d3，…，d|D|}，其中，|D|表示Web服务描述文档的数目。使用LDA主题训练模型训练得到的主题集合为T={t1，t2，t3，…，tK}，其中，ti为该集合的主题，用该集合中出现次数最多的标签来表示，K为模型训练之前人为规定的主题个数，则每一个文档di都在主题集合T上有1个概率分布
。因此，所有的Web服务的主题分布向量可以表示为1个二维矩阵的形式
。根据矩阵G来对Web服务进行功能分类。
2.3 主题向量隶属度矩阵计算
使用模糊C均值聚类算法来对LDA建模得到的主题分布向量矩阵G进行处理，得到隶属度矩阵U。采用C={c1，c2，c3，…，cM}表示每一个簇的主题，用该簇中出现次数最多的标签来表示，M为聚类之前人为规定的簇的个数。根据隶属度矩阵来进行Web服务的分类得到每个Web服务的主题分布向量。用
表示第i个Web服务属于每个簇的概率。
若只给第1个Web服务打上2个标签，那么需要在隶属度矩阵中找到该Web服务所属概率最大的前两个簇。由图4可以知道：第1个Web服务有0.4的概率属于第2个簇，有0.12的概率属于第1个簇，有0.04的概率属于第M个簇。这个Web服务的标签就是簇c2和c3的隐含主题。
图4 隶属度矩阵
Fig. 4 Membership degree matrix
3 实验评估
3.1 数据集描述
为了评估提出的方法，于2016-10—2016-11，从ProgrammableWeb.com网站上供爬取12 919个Web服务的信息。包括Web服务名称、描述文档、拥有标签类型等信息。详细的统计信息见表1。
表1 API统计信息
Table 1 Statistical information of API
在爬取的数据中，标签为“Tools”的API就有790个，而标签为“Law”仅仅包含了1个API。因此，选取了标签数量最多的前十类Web服务，共计4 351个Web服务用于实验，详细的API分布情况见表2。
表2 数量最多的前十类Web服务标签分布
Table 2 The distribution of web services in top 10 categories
3.2 评估标准
采用准确率、召回率以及F(准确率与召回率的调和平均值)评估所提出的方法。假设，
表示第k个Web服务实际分类标签集合，
表示对第k个Web服务预测的分类标签集合。∩表示预测正确的标签集合。|∩|表示预测正确的标签个数。那么第k个Web服务的预测准确率pk与召回率rk分别为：
(5)
(6)
所有描述文档的平均准确率P与平均召回率R为：
(7)
(8)
采用F来反映方法的综合性能：
(9)
3.3 对比方法
本文采用LDA主题模型与本文方法进行比较。
LDA方法：对Web服务的描述文本进行建模，得到每个Web服务描述文本的文档主题分布向量，根据最大的前N个主题概率将Web服务进行主题划分。
LDA-FCM方法：即本文所提方法。对LDA生成的每个文档的文档-主题向量使用FCM算法，计算出其隶属度矩阵。根据隶属度矩阵对Web服务进行划分主题。
在实验中，首先进行2种方法的聚类性能比较；之后，在LDA-FCM方法中，通过调整模糊因子m来找到其最优值用于Web服务聚类。
3.4 实验结果
3.4.1 模糊因子m对Web服务聚类的影响
在LDA-FCM方法中，为了找出最佳的模糊因子m[23]，设置了一组实验，在主题数k=100的情况下，获得m对Web服务聚类的影响。这里取间隔为0.1。图5表示在不同m时LDA-FCM方法的F分布情况。从图5可以看出：当m=2.0时，F最高；随着m远离2.0，F大致呈逐渐降低的趋势。因此，在LDA-FCM方法中，取m=2.0，以期获得较好的实验效果。
图5 在k=100的情况下，m对实验结果的影响
Fig. 5 Impact of m on experimental result when k=100
3.4.2 聚类性能比较
将LDA预先设定的主题数k设置为20，40，60，80和100，迭代次数N=1 000。同时，LDA模型中的先验参数α和β根据主题数K来设定，α=50/K，β=0.1。模糊聚类中的模糊因子，取之前获得最佳值m=2，聚类簇个数M=K。对于每一个K值，进行了100次模糊聚类实验，以降低初始点选取对聚类结果的影响。
图6所示为2种方法的准确率。从图6可以看出：LDA-FCM在同一主题数下的准确率比LDA方法的高。这是因为本方法考虑了Web服务的多功能性，较好地识别出Web服务的多种功能。并且随着主题数增加，每种方法的准确率都会上升。这是因为主题数越多，划分出的簇类包含的领域就越精确。聚类召回率随主题数的变化见图7。从图7可见：在同一主题下LDA-FCM方法的召回率也比LDA方法的高，这说明LDA-FCM方法比LDA方法能够发现出更多的有用的Web服务标签并达到更精准的聚类效果。
图6 聚类准确率随主题数的变化
Fig. 6 Precision with the change in the number of topics
图7 聚类召回率随主题数的变化
Fig. 7 Recall with the change in the number of topics
F随主题数的变化见图8。从图8可以看出：在同一主题数下，LDA-FCM方法的综合效果也要优于LDA方法的综合效果。
图8 F随主题数的变化
Fig. 8 F-score with the change in the number of topics
4 结论
1) 针对当前Web服务聚类算法不能实现Web服务的多功能聚类问题，提出一种基于LDA模型和模糊C均值算法的Web服务多功能聚类方法。该方法首先使用LDA模型对Web服务文档进行主题建模；然后，计算Web服务与各个功能之间的隶属度矩阵，并根据隶属度矩阵对其功能进行划分。
2) 本文方法能够更有效地发现Web服务的多种功能特性，提高Web服务发现的精度。
在下一步工作中，拟将Word2Vec与LSTM神经网络模型相结合，对Web服务文档进行建模，以进一步提高Web服务多功能分类的准确性。
参考文献：
[1] STANCULEA L. Service Oriented Architecture[J]. Wiley Interdisciplinary Reviews: Computational Statistics, 2009, 1(1): 101-105.
[2] NAYAK R, LEE B. Web service discovery with additional semantics and clustering[C]//IEEE/WIC/ACM International Conference on Web Intelligence. Fremont, CA: IEEE, 2007: 555-558.
[3] ZHANG Xizhe, YIN Ying, ZHANG Mingwei, et al. Web service community discovery based on spectrum clustering[C]//International Conference on Computational Intelligence and Security. Beijing, China: IEEE Computer Society, 2009: 187-191.
[4] ZHANG Liangjie, LI Bing. Requirements driven dynamic services composition for Web services and grid solutions[J]. Journal of Grid Computing, 2004, 2(2): 121-140.
[5] DUSTDAR S, SCHREINER W. A survey on web services composition[J]. International Journal of Web & Grid Services, 2005, 1(1): 1-30.
[6] CHEN Liang, HU Liukai, ZHENG Zibin, et al. WTCluster: Utilizing Tags for Web Services Clustering[C]// International Conference on Service-Oriented Computing. Paphos, Cyprus: Springer-Verlag, 2011: 204-218.
[7] ELGAZZAR K, HASSAN A E, MARTIN P. Clustering WSDL Documents to Bootstrap the Discovery of Web Services. IEEE International Conference on Web Services. Washington D C, USA: IEEE Computer Society, 2010: 147-154.
[8] 石磊, 谢涛, 曹仰杰. 基于语义相似度与信息量的Web服务标签优化[J]. 小型微型计算机系统, 2015, 36(6): 1153-1157.
SHI Lei, XIE Tao, CAO Yangjie. Web service tags optimization based on semantic similarity and quantity of information[J]. Journal of Chinese Computer Systems, 2015, 36(6): 1153-1157.
[9] CAO Buqing, LIU Xiaoqing, LI Bing, et al. Mashup service clustering based on an integration of service content and network via exploiting a two-level topic model[J]. IEEE International Conference on Web Services. San Francisco, USA: IEEE, 2016: 212-219.
[10] ZHANG Meng, LIU Xudong, ZHANG Richong, et al. A Web service recommendation approach based on QoS prediction using fuzzy clustering[C]//IEEE Ninth International Conference on Services Computing. Honolulu, USA: IEEE Computer Society, 2012: 138-145.
[11] ZHU Jieming, KANG Yu, ZHENG Zibin, et al. A Clustering-based QoS prediction approach for Web service recommendation. international symposium on object/component/ service-oriented real-time distributed computing workshops[J]. Shenzhen, China: IEEE Computer Society, 2012: 93-98.
[12] PLATZER C, ROSENBERG F, DUSTDAR S. Web service clustering using multidimensional angles as proximity measures[M]. New York, USA: ACM, 2009: 1-11.
[13] SUKUMAR A S S, LOGANATHAN J, GEETHA T. Clustering web services based on multi-criteria service dominance relationship using Peano Space filling curve[C]//International Conference on Data Science & Engineering. Washington D C, USA: IEEE, 2012: 13-18.
[14] LIU W, WONG W. Web service clustering using text mining techniques[J]. International Journal of Agent-Oriented Software Engineering, 2009, 3(1): 6-26.
[15] POP C B, CHIFU V R, SALOMIE I, et al. Semantic Web service clustering for efficient discovery using an ant-based method[M]. Intelligent Distributed Computing IV. Berlin, Heidecberg: Springer, 2010: 23-33.
[16] 黄兴, 刘小青, 曹步清, 等. 融合K-Means与Agnes的Mashup服务聚类方法[J]. 小型微型计算机系统, 2015, 36(11): 2492-2497.
HUANG Xing, LIU Xiaoqing, CAO Buqing, et al. MSCA: Mashup service clustering approach integrating K-means and agnes algorithms[J]. Journal of Chinese Computer Systems, 2015, 36(11): 2492-2497.
[17] BLEI D M, NG A Y, JORDAN M I.Latent dirichlet allocation[J]. Journal of Machine Learning Reserach, 2003, 3(3): 993-1022.
[18] AZNAG M, QUAFAFOU M, ROCHD E M, et al. Probabilistic topic models for web services clustering and discovery[C]// ESOCC. Berlin, Heidelberg: Springer-Verlag, 2013: 19-33.
[19] 张敏, 于剑. 基于划分的模糊聚类算法[J]. 软件学报, 2004, 15(6): 858-868.
ZHANG Min, YU Jian. Fuzzy partitional clustering algorithms[J]. Journal of Software, 2004, 15(6): 858-868.
[20] HASAN M H, JAAFAR J, HASSAN M F. Development of web services fuzzy quality models using data clustering approach[J]. Lecture Notes in Electrical Engineering, 2014, 285: 631-640.
[21] GHOLAMZADEH N, TAGHIYAREH F, SHAKERY A. Fuzzy clustering for semantic web services discovery based on ontology[J]. International Journal of Information & Communication Technology, 2010, 2(3): 1-8.
[22] LOPER E, BIRD S. NLTK: the natural language toolkit[C]//Proceedings of the ACL Workshop on Effective Tools and Methodologies for Teaching Natural Language Processing and Computational Linguistics. Philadelphia, USA, 2002: 17-21.
[23] 高新波, 裴继红, 谢维信. 模糊c-均值聚类算法中加权指数m的研究[J]. 电子学报, 2000, 28(4): 80-83.
GAO Xinbo, PEI Jihong, XIE weixin. A study of weighting exponent m in a fuzzy c-means algorithm[J]. Chinese Journal of Electronics, 2000, 28(4): 80-83.
(编辑 陈灿华)
收稿日期：2018-01-12；修回日期：2018-03-21
基金项目(Foundation item)：国家自然科学基金资助项目(61872139，61873316，61572187，61702181)；湖南省自然科学基金资助项目(2017JJ2098，2018JJ2136)(Projects(61872139, 61873316, 61572187, 61702181) supported by the National Natural Science Foundation of China; Projects(2017JJ2098, 2018JJ2136) supported by the Natural Science Foundation of Hunan Province)
通信作者：刘建勋，教授，博士生导师，从事服务计算与云计算、工作流管理的理论与应用的研究；E-mail：ljx529@gmail.com
