Web服务是一种以服务为导向的架构技术, 该技术常被用来完成分布式和异构系统之间的自动化交互或链接业务流程.然而, 功能单一的Web服务很难满足一些复杂多变的需求.为解决这一问题, 一种区别于传统资源集成方案的新企业级应用开发技术Mashup被提出.该技术能够集成单一功能的服务(Web API服务:使用REST风格、HTTP协议、JSON数据格式; 可通过互联网使用的应用程序接口; 具有易访问、可扩展、易开发与组合等诸多优点), 构建多功能服务应用以适应用户的复杂请求.随着Mashup技术的广泛使用, 出现了许多Mashup服务平台(如ProgrammableWeb, IBM Mashup Center, Yahoo Pipe等)以提供种类繁多的Web API.在平台上, 用户可以根据自身的需求选择性地调用Web API来创建满足相应需求的Mashup应用.然而, 网络上发布的Web API服务越来越多(以ProgrammableWeb平台为例, 截止2016年12月, 已发布超过15 500个Web API服务接口), 加之Web API描述文档非结构化, 许多Web API功能相似但性能差异较大等一系列问题, 使得从Web API服务库中选取开发者感兴趣的、适合的、高质量的Web API来构建Mashup应用变得越来越困难.

因此, 如何根据Mashup构建者的自然语言表述的需求自动生成或推荐一个解决该问题的完整方案, 是研究者自然而然的理想.但是在目前的人工智能的水平之下, 想要完全实现这一目标有很大难度.一个可行的次优方案是“根据自然语言需求描述推荐可行的或者推荐可用于解决该问题的Web API任务集合以辅助用户构建Mashup”.该解决思路目前倍受服务计算与业务过程管理领域研究人员的关注.

图 1分别展示了开发者1所采用的传统的服务搜索方式以及开发者2所采用的“推荐可用于解决该问题的任务集合”方案下的Mashup创建的流程.开发者1根据需求描述, 利用Mashup平台检索满足需求的特定功能的Web API来组建Mashup应用, 然而Mashup平台上的检索功能仅仅是对用户需求的关键词的简单匹配, 这会造成检索结果过于庞杂, 包含大量符合功能需求的Web APIs和一些不符合功能需求的Web APIs, 缺少部分符合功能需求的Web APIs, 例如, 检索的关键词为“image”, 检索结果多达1 121个Web APIs, 一些具有该功能但描述为“picture”“photo”“album”的Web APIs没有被检索到, 致使需要耗费大量的精力筛选服务质量高且具有组合关系的Web APIs.而开发者2利用Web API推荐系统来获取解决问题的Web API服务集合, 该系统能够利用除关键词以外的多维信息来理解Mashup需求文档, 进而自动获取开发者感兴趣的、适合的、高质量的Top-N Web API服务集合, 这一方案简化了Mashup构建流程, 降低了Mashup开发难度.

本文以此为动机, 聚焦于“推荐用于解决问题的Web API服务集合以构建Mashup”, 提出一种融合多维信息的主题自适应Web API推荐方法HDP-FM.该方法首先利用Hierarchical Dirichlet Processes(HDP)模型挖掘Web API描述文本的隐含主题; 接着, 利用已训练好的HDP模型预测Mashup描述文本的主题分布向量, 用于相似度计算; 最后, 将Mashup与Mashup的相似度、Web API与Web API的相似度、Web API的流行度、Web API的共现性作为因子分解模型的输入, 来推荐Top-N Web APIs列表供目标Mashup创建者使用.

本文的主要创新点有如下几点.

(1)   利用HDP模型对Web API描述文档进行训练, 获得隐含主题分布向量, 并利用已生成的HDP模型预测Mashup主题分布向量;

(2)   采用因子分解模型, 融合相似度、流行度、共现性等多维信息特征, 实现Web API的Top-N评分推荐;

(3)   本文实验数据集使用从ProgrammableWeb平台上爬取的真实数据, 一系列的实验结果表明, 我们的方法具有较好的效用和效率.

本文第1节分析Web API推荐领域的相关工作.第2节对HDP模型进行介绍.第3节详细阐述融合多维信息的主题自适应Web API推荐方法.第4节介绍对比方法, 给出实验结果, 并对实验结果进行分析.最后一节对全文进行总结.

1 相关工作

随着应用Web API构建企业级Mashup应用愈来愈受到重视, 目前Web服务领域已引入了许多推荐方法, 并已经显示出其能够帮助用户找到有用的信息.纵观Web服务推荐研究领域中的方法, 总体来说可分为如下3类:基于功能特性的Web服务推荐、基于非功能特性的Web服务推荐、混合特性的Web服务推荐.

(1) 基于功能特性的Web服务推荐.

该类型的推荐方法主要通过测量Web服务描述文档之间的相似度, 以此来推荐最相似的Web服务来满足用户的需求^[1-4].在我们以前的工作中^[1], 通过使用Term Frequency-Inverse Document Frequency(TF-IDF)技术分析服务文本(WSDL或Web API功能描述)以提高推荐的精度, 该方法通过计算文本在词向量空间上的距离来测量文本之间的相似度.主题模型技术能够获取Web服务描述文档的潜在主题分布向量, 进而挖掘Mashup描述文档与Web API描述文档之间的潜在语义关系.因此, 一些研究者探索使用主题模型(如latent Dirichlet allocation, 简称LDA^[2])来进一步提高服务推荐的精度^{[3, 4]}.Li等人^[3]利用LDA主题模型从Web服务的WSDL描述文档中获取Web服务隐含的功能特征.Chen等人^[4]利用LDA主题模型聚合标签数据与WSDL描述文档来提高服务发现的精确度.上述方法均利用相似度计算方法来计算用户需求与服务文档之间的匹配度(常用的相似度计算方法有Jaccard公式、余弦相似度公式等).然而传统的主题模型均存在这样一个限制, 即, 在训练生成描述文档的隐含主题向量分布前需要预先指定主题的个数.更重要的是, 主题数会严重的影响最终的服务推荐的效果.通常的做法是不断调节主题数以寻找最佳的主题数, 而这一过程需要反复多次训练主题模型.为了消除这一限制, 本文探索使用HDP模型来获取Web服务的主题分布向量以推荐Web APIs集合给目标Mashup.由Teh等人在2004年提出的HDP模型^[5]是LDA模型的非参数模型推广, 其为实现多文档之间共享无限多个聚类提供了解决途径.与传统的参数模型相比, HDP模型的使用更加灵活, 特别是应用于聚类问题时, 该模型能够自动确定聚类数目和生成聚类中心的分布.正是由于HDP模型具有以上特点, 使得该模型能够根据语料库自动确定相应的最优的潜在主题数目, 并能很好地对新进的Web服务的主题分布做出预测.

(2) 基于非功能特性的Web服务推荐.

以非功能特性为基础的Web推荐方法主要关注于Web服务的质量或历史调用规律, 采用协同过滤、矩阵分解等技术来预测Web服务的服务质量(QoS)或出现概率, 推荐Top-K高质量的Web服务给用户^[6-9].基于协同过滤的Web服务推荐^{[6, 7]}, 简单来说是利用兴趣相投或拥有共同经验的群体的喜好来推荐用户感兴趣的信息. Zheng等人^[6]利用协同过滤技术进行QoS预测, 提出了一种用户协同机制, 该机制能够从不同服务的用户行为中搜集有用的服务的QoS信息.在此基础上, Chen等人^[7]将位置信息和QoS信息结合, 来构建区域模型.基于矩阵分解的Web服务推荐进一步提高Web服务推荐的精度^{[8, 9]}, 它是将Web服务的历史调用矩阵拆解为两个低维矩阵, 并利用这些子矩阵推荐Web服务.Lo等人^[8]使用基于位置规则的矩阵分解技术预测Web服务的QoS.He^[9]提出了一种基于位置的多层次矩阵分解模型来推荐Web服务.然而, 不管是协同过滤还是矩阵分解, 都不可避免地会出现矩阵稀疏性问题, 且其输入的数据类型不具普遍性(过于单一), 从而影响推荐的精度.Rendle等人^{[10, 11]}提出了因子分解模型, 就很好地解决了这一问题, 该模型将任意长度、任意数量的特征向量作为输入, 这就使得其能处理多维度的信息输入.即使矩阵稀疏, 也不会影响推荐精度.因此, 本文使用该模型来融合多维度信息, 继而进一步提高服务发现质量.

(3) 混合特性的Web服务推荐.

由于混合特性的Web服务推荐方法能够结合功能特性和非功能特性以提高服务发现的精度, 使得其成为时下的研究热点^[12-17].Yao等人^[12]提出了一种新颖的混合Web服务的功能特征和QoS信息Web服务推荐方法. Cao等人^[13]探索出一种两层主题模型, 该模型聚合了服务的文本信息和服务的网络信息去增强服务聚类的效果, 进而提高Web API的推荐精度.Gao等人^[14]提出了一种基于“多样学习”的API推荐方法, 紧接着, 他们又提出了集合用户模型、服务、Mashup和主题的服务推荐方法^[15].针对Mashup的自动创建, Xia等人^[16]提出了一种具有分类意识的API聚类和分布式推荐方法, 该方法使用一种扩展的K-Means聚类方法来对API进行聚类, 接着开发了一种分布式的机器学习框架用来预测服务排序.Liu和Fulia^[17]通过聚合用户、主题和服务潜在特征关系来提升服务推荐的质量.同样, 本文的HDP-FM方法也是一种混合服务推荐法, 既考虑了Web服务的功能特性又考虑了非功能特性(包括功能特性“Mashups之间的相似度、Web APIs之间的相似度”和非功能特性“Web APIs的流行性和Web APIs的共线性”).

2 概率主题模型

概率主题模型是一系列旨在发现隐藏在大规模文档中的主题结构的算法, 其中, LDA是最为传统的概率主题模型, 它能够提取文档的隐含主题, 将文档从高维的词向量空间映射到低维的主题向量空间中.LDA^[2]模型基于3点假设.

●  假设1(词袋模型):一篇文档是由一组词构成的一个集合, 词与词之间不考虑先后顺序关系;

●  假设2:用于训练的文档集中文档不考虑顺序先后顺序;

●  假设3:参数化的贝叶斯模型在训练时需预先指定聚类数目(主题数K).

在LDA模型中, 一篇文档可以包含多个主题, 文档中的每个词都由其中的一个主题生成.给定特定的文档集和主题数K, LDA假设文档集中所有文档共享这K个主题, 但每篇文档具有不同的主题分布.因此, 整个模型的训练就是估计文档集中“文档-主题”分布H和“主题-词”分布F.虽然使用LDA可以成功地学习语料库以生成主题, 但是与大多数主题模型类似, 其主题数K需要事先给定.更重要的是, 主题数K的选取很大程度上会影响模型的训练效果.通常情况下, 为了寻找最优主题数, 需要不断调节主题数F, 反复训练多个LDA主题模型, 至使模型的训练变得越发繁琐.为解决这一问题, 我们探索HDP主题模型来获得文档主题分布.该模型为非参数贝叶斯模型, 能够根据训练的语料库自动获取相应语料库的最佳主题数K.该过程能够有效避免LDA模型的假设3所带来的限制.本文利用HDP模型对Web APIs的描述文档训练生成主题分布向量.例如$W{S^{{a_i}}} = (t_1^{({a_i})}, t_2^{({a_i})}, ..., t_K^{({a_i})}), $其中, $W{S^{{a_i}}}$表示Web API “a_i”的主题分布向量, $t_2^{({a_i})}$表示Web API “a_i”在第2个主题下的分布率.为了介绍HDP模型的工作原理, 需要先引入一个重要概念“Dirichlet过程模型(DP)”^[18].DP模型是非参数贝叶斯统计模型中的一种随机过程模型, 且被广泛应用于文本相似度计算.在此给出DP模型定义.

定义1(DP模型)^[18]. 假设H₀是测度空间Θ上的随机概率分布, 参数δ是正实数, 测度空间Θ上的概率分布H满足如下条件:对于测度空间Θ的任何划分(有限的或无线的)R₁, R₂, …, R_i, 都有公式(1)成立:

$ \{ H({R_1}), H({R_2}), \ldots , H({R_i})\} \sim Dirichlet\{ \delta {H_0}({R_1}), \delta {H_0}({R_2}), \ldots , \delta {H_0}({R_i})\} $

(1)

则称H服从由基分布H₀和参数δ组成的Dirichlet过程H~(δ, H₀); 反之, 如果H是一个根据DP得到的可测量的随机分布, 则称H₀为H的基分布.

HDP模型假设主题个数是无穷的, 利用两层DP模型来获取服务描述文档主题分布向量.现在我们详细介绍HDP模型的实现过程, 图 2为HDP模型生成服务描述文档主题分布向量的图模型, 表 1对HDP图模型中的符号进行了详细说明.

HDP模型的实现过程具体描述如下:

(1)   初始化无限的主题分布向量θ_k, 即允许k值为无穷大.例如θ_k~Dirichlet(η), 该公式指对任意的k∈{1, 2, 3, …}均有θ_k满足以η为参数的Dirichlet分布, 这一过程类似于LDA模型中的主题采样过程.

(2)   在整个文档集, 抽样生成主题在语料库层的分布率G_k, 该过程的实现依赖于Bate分布以及参数γ.例如G_k~Beta(1, γ), 同样k∈{1, 2, 3, …}, 实现这一过程依赖于HDP的Stick-breaking构造方法(Stick- breaking构造方法是HDP模型采样的实现方法, 用于指定主题概率的分布)^[18], 即

$ {\sigma _k}(G) = {G_k} \times \prod\nolimits_{j = 1}^{k - 1} {(1 - {G_k})} , {\rm{其中}}, \sum\nolimits_{k = 1}^\infty {{\sigma _k}(G)} = 1 $

(3) 对每一个服务描述文档m.

➢  第1步, 利用Multinomial分布函数抽样生成服务层主题索引, 即S_{m, i}~Multinomial(σ(G))公式中的i∈{1, 2, 3, …}, 该步骤指根据语料库层的分布率抽样生成服务描述文档主题.需要注意的是, 一个特定的服务描述文档抽样至一个特定的语料库子集, 并不是整个文档集.

➢  第2步, 利用一个带有参数α的Beta分布函数来抽样生成服务描述文档的Stick-breaking概率, 即G_{m, i}~Beta(1, α)^[19], 同样i∈{1, 2, 3, …}.第2步是对第1步选取的主题进一步分配概率比例的过程.类似于LDA模型的主题分布抽样, 不同的是, 在LDA模型中, 每一个主题至少会在一个描述文档中出现; 但在HDP模型中, 只有经过第1步选取的主题才会出现在描述文档中.

(4) 对每一个来至服务描述文档的词n.

➢  第3步, 为每一个词分配主题T_{m, n}~Multinomial(σ(D_{m, i})), 该过程指抽样生成服务描述文档m中的第i个词的主题.

➢  第4步:使用第3步获取的主题, 抽样生成词w_{m, n}, 即${w_{m, n}} \sim Multinomial({\theta _{m, {T_{m, n}}}}).$

潜在主题存在相互依赖与潜在主题个数允许无限, 使得利用HDP模型推断(计算)覆盖全部潜在主题的先验概率分布变得越发困难.为解决这一问题, HDP模型利用变分推断方法^[20]来近似计算真实后验概率分布.其首先利用变分分布来分解潜在的主题, 接着设置语料库级别的最大的主题数K_max与服务描述文档级别的最大主题数lI来进一步控制条件分布范围.其变分分布的计算公式如下:

$q(\theta , G, m, D, T) = (\prod\nolimits_{k = 1}^{{K_{\max }}} {q({\theta _k}|{\lambda _k})q({G_k}|{\vartheta _k})} )\\(\prod\nolimits_{m = 1}^M {\prod\nolimits_{i = 1}^I {q({S_k}|{\psi _k})q({D_k}|{\gamma _k})} \prod\nolimits_{n = 1}^N {({T_{m, n}}|{\phi _{m, n}})} } )$

(2)

$ q(\theta , G, m, D, T) = q(\theta )q(G)q(m)q(D)q(T) $

(3)

通过利用变分推断的正则化结果^[20], 我们可以获得最优的特征分布:

$\ln q_j^ * = {\Delta _{i \ne j}}[\ln p(W, Z)] + const$

(4)

${\Delta _{i \ne j}}[\ln p(W, Z)] = \int {\ln p(W, Z)\prod\nolimits_{i \ne j} {{q_i}} {\text{d}}{Z_i}} $

(5)

其中, Z=(θ, G, m, D, T)表示整个特征集合.变分推断是一个实时交互的过程, 其利用公式(3)一次仅计算一个变分分布率, 直到迭代收敛为止.综上可得:HDP模型主要依据词频共现来聚类分组数据, 且不依赖于参数K(主题数); HDP模型是具有两层DP模型的非参数贝叶斯模型, 相比于基于简单概率分布的参数贝叶斯模型LDA来说具有较高的时间复杂度和空间复杂度.

3 方法概述

图 3给出了HDP-FM方法的Web API推荐框架, 此框架包括分为两个部分.

(1)   多维信息的构建.针对Web API和Mashup的描述文档, 利用HDP模型以获得Web API和Mashup的主题分布, 进一步利用增强余弦相识度公式^[1]度量Mashup与Mashup之间的相似度、Web API与Web API之间的相似度; 针对Web API的category与历史调用次数, 利用增强流行度公式计算Web API的流行度; 针对Web API的组合关系, 结合Jaccard相似系数公式, 衡量Web API的共线性;

(2)   多维信息的融合.将第1部分获取的Top-A相似的Web API、Top-M相似的Mashup、Web API的流行度和Co-occurrence(共现性)注入因子分解机模型, 为目标Mashup的创建推荐Top-N Web APIs.

3.1 相似度度量

相似度的度量是本文需要解决的核心问题, 本文采用增强余弦相似度公式^[1](6).HDP-FM方法将Web APIs的描述文档作为HDP模型的输入, 通过迭代抽样生成每一个Web API描述文档的主题分布向量; 然后, 利用已训练好的HDP模型为每个Mashup描述文档分配主题, 以获得Mashup描述文档的主题向量; 最后, 通过公式(6)计算Web API与Mashup之间的相似度, 同理可获取Web API与Web API之间的相似度以及Mashup与Mashup之间的相似度:

$S(W{S^{{a_i}}}, W{S^{{m_j}}}) = \frac{{\sum\nolimits_{i = 1}^K {\xi \left( {\frac{1}{{{e^{\mu \left| {WS_l^{{a_i}} - WS_l^{{m_j}}} \right|}}}}} \right)WS_l^{{a_i}} \cdot WS_l^{{m_j}}} }}{{\sqrt {{{(t_1^{({a_i})})}^2} + ... + {{(t_K^{({a_i})})}^2}} \sqrt {{{(t_1^{({m_j})})}^2} + ... + {{(t_K^{({m_j})})}^2}} }}$

(6)

其中, $W{S^{{a_i}}} = (t_1^{({a_i})}, t_2^{({a_i})}, ..., t_K^{({a_i})})$与$W{S^{{m_j}}} = (t_1^{({m_j})}, t_2^{({m_j})}, ..., t_K^{({a_j})})$分别为Web API “a_i”和Mashup “m_j”的主题分布向量; ξ(·)为惩罚值, 用于对不相似的Web API进行惩罚, 即主题向量之间对应位置元素差值越大, 惩罚越强.当μ=0时, 该公式将退变为一般的余弦相似度公式.

3.2 Web API的流行度与共现性

如仅仅使用HDP模型来计算描述文本之间的相似度, 其推荐精度不高.为了进一步提高推荐精度, 我们引入Web API的流行度与共现性.Web API的流行度能够很好地反映Web API的QoS信息, 本文确定的Web API流行度计算公式如式(7)所示:

$pop({a_i}) = \frac{{Fre({a_i}) - {\text{Min}}Fre(Category({a_i}))}}{{{\text{Max}}Fre(Category({a_i})) - {\text{Min}}Fre(Category({a_i}))}}$

(7)

其中, Fre(a_i)为Web API “a_i”被历史Mashup调用的次数, Category(a_i)表示与Web API “a_i”具有相同领域属性的全部Web API, MinFre(·)为历史上Web API被Mashup历史上最小的调用次数, MaxFre(·)为历史上Web API被Mashup历史上最大的调用次数.

Web API的共现性实际上是Web API组合关系的外在表现, HDP-FM方法采用经典的Jaccard相似系数方法来计算Web API的共现性:

$Co({a_i}, {a_j}) = \frac{{|{a_i} \cap {a_j}|}}{{|{a_i} \cup {a_j}|}}$

(8)

其中, |a_i∩a_j|表示Web API “a_i”和Web API “a_j”被同一个Mashup调用的总次数, |a_i∪a_j|表示Web API “a_i”和Web API “a_j”被历史Mashup调用的Mashup的总个数.

3.3 Top-N Web APIs推荐

因子分解机模型^{[10, 11]}吸取了支持向量机和矩阵分解模型的优点, 其核心思想是:通过矩阵分解的方式将用户和物品的关联矩阵映射到同一个隐因子空间上, 得到用户和物品在隐因子空间上的特征向量, 通过计算用户特征向量和物品特征向量的内积, 预测出用户对物品的评价.由于因子分解机模型能够在其模型中加入各种补充信息, 从而能有效降低传统协同过滤算法中矩阵的稀疏性, 进而优化特征组合的方式.此外, 因子分解机模型理论基础坚实, 参数优化方法完备.因此, 本文利用该模型来融合多维度的信息, 并预测Mashup与Web API的之间的链接关系或缺省值.

于是, 一个二阶的因子分解模型被定义如下:

$Y(X): = {w_0} + \sum\nolimits_{i = 1}^n {{w_i}{x_i}} + \sum\nolimits_{i = 1}^n {\sum\nolimits_{j = i + 1}^n {\langle {v_i}, {v_j}\rangle {x_i}{x_j}} } $

(9)

利用模型参数w₀∈R, w∈Rⁿ和V∈R^n*k, 公式(9)可以被化简为

$Y(X): = {w_0} + \sum\nolimits_{i = 1}^n {{w_i}{x_i}} + \frac{1}{2}\sum\nolimits_{f = 1}^k {({{(\sum\nolimits_{i = 1}^n {{v_{i, f}}{x_i}} )}^2} - \sum\nolimits_{i = 1}^n {v_{i, f}^2x_i^2} )} $

(10)

其中, n表示特征的长度(个数), w₀表示初始偏移量, w_i表示第i个特征的权重, x_ix_j是指成对的特征变量之间的相互作用, 〈v_i, v_j〉表示在因子分解模型中Mashup x_i与Web API x_j之间的相互影响, k为因子分解矩阵维度.

利用上述的二阶因子分解模型, 可以预测每一个Web API相对于目标Mashup的评分值, 对评分值进行排序, 便可获得最终的推荐列表.图 4是利用因子分解模型为目标Mashup预测Web API评分的实例, 训练数据集中的数据被分成两个部分:第1部分为输入特征向量集(feature vector X), 第2部分是输出目标集(target Y).每一行为一个特征向量x_i以及相应的目标评分值y_i.图 4中, 每一行从左到右依次为:

●  第1个矩阵(Box1)代表活动的Web API(例如, x_i行的Box1中的第1个值为1, 表示A₁为活动的Web API);

●  第2个矩阵(Box2)代表活动的Mashup(例如, x_i行的Box2中的第2个值为1, 表示活动的Web API A₁历史上被M₂调用过);

●  第3个矩阵(Box3)表示与活动的Web API的最相似的Top-A个Web API(例如, x_i行的Box3中的第2个值为0.3, 表示活动的Web API A₁与Web API A₁的相似度为0.3, 且在活动的Web API A₁最相似的Top-A个Web API之中);

●  第4个矩阵(Box4)表示与活动的Mashup的最相似的Top-M个Mashup(例如, x_i行的Box4中的第3个值为0.7, 表示活动的Mashup M₂与Mashup M₃的相似度为0.7, 且在活动的Mashup M₂最相似的Top-M个Mashup之中);

●  第5个矩阵(Box5)表示与活动的Web API共现的Web API的共现值(例如, x_i行的Box5中的第3个值为0.5, 表示活动的Web API A₁与Web API A₃的共现值);

●  第6个矩阵(Box6)表示活动的Web API流行度值.

●  最后, 在训练集中向量Y中的值为1, 表示活动的Web API历史上被活动的Mashup调用过; 0表示未被调用过.在测试集中, 向量Y中的值表示活动的Web API相对于活动的Mashup的预测评分.最终的推荐Web API集合是通过对预测评分的排序获得的.

在应用因子分解模型对预测Web API评分之前, 需要对观测数据集中的每一对(x_i, y_i)求出真实值与预测值之间误差之和, 使其最小化, 以求得最佳的参数Θ=(w_i, w, V)集合, 其中V∈R^n*k为低秩矩阵, 用于表示变量间的相互作用).为了寻找最优的模型参数, 需要设计合适的损失函数l:

$ Opt(S,\lambda )=\underset{\mathit{\Theta }}{\mathop{\arg \min }}\,\sum\nolimits_{i=1}^{N}{l(Y({{x}_{i}}),{{Y}^{'}})+\sum\nolimits_{\theta \in \mathit{{\mathit{\Theta }} }}{{{\lambda }_{(\theta )}}{{\theta }^{2}}}} $

(11)

其中, N是训练集中实例的数量, λ_(θ)∈R₊为正则化项的系数, $\sum\nolimits_{\theta \in {\mathit{\Theta }} } {{\theta ^2}} $表示参数集合的二范数.由于本文为Binary

分类问题, 因此, 本文选取Binary分类问题常使用的Logic优化函数来优化损失函数.

$ l(Y, Y\prime ) = {\rm{log}}(1 + {\rm{exp}}( - YY\prime )) $

(12)

对损失函数优化后, 便需要选择合适的参数求解方法, 常用的参数求解方法有:随机梯度下降(SGD)、马尔科夫裴特卡罗法(MCMC)、交替最小二乘法(ALS).其中, SGD最为常用且具有较快的训练速度, 本文的参数求解也使用该方法.

4 实验设计 4.1 数据集选取与实验设置

数据集采用从ProgrammableWeb平台上爬取的真实数据, 包含6 673个Mashup, 9 121个Web APIs以及13 613个Web API和Mashup之间的链接.由于HDP模型主要依据词频共现来聚类分组数据, 为了导出最相关的主题, 我们对Web APIs和Mashup的描述文档做预处理.图 5给出了名称为“Earthmine Flash Viewer”的Web API描述文档预处理的详细过程.

●  实验环境设置:利用Java语言实现HDP算法, 运行在一台60G内存的服务器;

●  实验中参数设置:HDP算法迭代次数Iter为3 000, HDP模型参数α=1, η=0.1, γ=1.5.实验中, Top-A个APIs和Top-M个Mashup在因子分解机模型中分别设置为10和20.实验中, Mashup数据集被随机平均分成5个部分, 其中一个部分为测试集, 而另外4个部分边为训练集.

4.2 实验的评测指标

本文采用召回率、准确率、F-measure和NDCG@N指标来评价以上6种方法性能的优劣, 分别定义如下.

●  召回率反映的是推荐的相关Web APIs占所有相关Web APIs的比率, 计算如公式(13)所示.

$ {\rm{召回率}} = \frac{{|R({A_i}) \cap RM({A_i})|}}{{RM({A_i})}} $

(13)

●  准确率反映推荐的Web APIs集合中相关Web APIs所占的比例, 计算如公式(14)所示.

$ 准确率 = \frac{{|R({A_i}) \cap RM({A_i})|}}{{R({A_i})}} $

(14)

●  F-measure是召回率与准确率的调和平均值, 即

$ F{\rm{ - measure}} = \frac{{2 \times {\rm{召回率}} \times {\rm{准确率}}}}{{{\rm{召回率}} + {\rm{准确率}}}} $

(15)

其中, R(A_i)表示相关的Web APIs(被目标Mashup真实调用的Web APIs), RM(A_i)表示推荐的Web APIs.

●  NDCG@N(normalized discounted cumulative gain:归一化折损累积增益).在信息检索领域中, 该方法是一种流行的的衡量排序质量的指标.本文用来衡量推荐列表中推荐Web APIs排名的优劣.NDCG@N的值越高, 说明Web APIs的推荐列表排序结果越好.即

$DCG@N = \sum\nolimits_1^N {\frac{{{2^{re{l_i}}} - 1}}{{{{\log }_2}(1 + i)}}} $

(16)

$NDCG@N = \frac{{DCG@N}}{{IDCG}}$

(17)

其中,

●  N表示Web APIs的推荐个数;

●  rel_i表示第i个推荐的Web API的相关性得分:如果推荐的第i个Web API就是真实数据集中Mashup调用的Web APIs, 此时rel_i=1;否则, rel_i=0;

●  IDCG(ideal DCG@N), 就是最大的DCG@N值(DCG@N可以通过公式(16)计算得到), 即为最优的推荐情况.

4.3 比较方法

●  TF-IDF^[1]:

利用词向量空间模型推荐与目标Mashup描述文档相似的Web APIs.假设目标Mashup m的词向量空间为V^(m), 第i个Web API的词向量空间为${V^{({a_i})}}$, 则目标Mashup m与第i个Web API的文本相似度计算如公式(18)所示.

$Sim(m, {a_i}) = \frac{{{V^{(m)}}{V^{({a_i})}}}}{{||{V^{(m)}}||||{V^{({a_i})}}||}}$

(18)

最后, 该Web API预测评分通过公式(19)计算得出.

$ Score(m, {a_i}) = pop({a_i})Sim(m, {a_i}) $

(19)

其中, pop(a_i)为第i个Web API的流行度, 可通过第3.2节中的公式(7)计算.

●  E-LDA^[3]

该方法使用LDA模型分别导出的Mashup和Web API的主题分布向量; 接着, 利用增强余弦相似度公式(6)来度量Mashup与Web APIs之间的文本相似度S(m, a_i); 最后, 将相似度高且流行的Top-N个Web APIs推荐给目标Mashup.Web API预测评分如公式(20)所示.

$ Score(m, {a_i}) = pop({a_i})S(m, {a_i}) $

(20)

●  E-HDP

类似于E-LDA推荐方法, 该方法推荐相似度高且流行的Top-N个Web APIs给目标Mashup.不同的是, 该方法获取服务描述文档主题分布向量是由HDP模型导出.

●  LDA-CF^[6]

利用LDA模型与协同过滤方法共同获取候选的Web API集合, 推荐候选集合中最流行的Top-N个Web APIs供Mashup创建使用.公式(21)给出了相应的推荐Web APIs的获取.

$RecommendAPI = pop{\text{Ma}}{{\text{x}}_N}\{ Cond_{i = i}^I(m, {a_i})\} $

(21)

其中, $Cond_{i = i}^I(m, {a_i})$为Mashup m的候选Web API集合, poppMax_N{·}表示取流行度最高的前N个Web APIs.

●  HDP-CF

类似于LDA-MF推荐方法的实现过程, 在此基础上, 使用HDP模型代替LDA模型训练服务描述文档的主题分布向量.

●  LDA-FM

利用因子分解模型的优势, 同时考虑文本相似度、Web API的流行度与Web API的共线性, 预测评分推荐Top-N个得分最高的Web APIs辅助Mashup创建.

●  HDP-FM

利用因子分解模型融合文本相似度、Web API的流行度、Web API的共线性, 预测评分推荐Top-N个得分最高的Web APIs辅助Mashup创建.与LDA-FM方法唯一的不同是, 服务描述文本的主题分布向量由HDP模型训练获得.

4.4 实验评估

本小节我们首先对HDP模型的训练过程进行观测, 接着探讨了主题K的选取对实验结果的影响, 最后选取准确率、召回率、F-measure和NDCG@N这4种评价指标对多种方法进行比较.

(1) HDP模型训练观测

HDP模型在训练结束后会获得训练语料库的最优主题个数、每个主题下的词分布以及每一个Mashup和Web API的主题分布概率.表 2展示了利用HDP模型获取的部分“主题-词”分布的情况, 如, sport game score player等词被分配到Topic 14中.表 3展示了部分Web API描述文档在表 3所给出的主题下的分布情况.如, Web API “FishingBuddy”在Topic 14上的分布率为0.324059.表 4给出了HDP模型的α, η, γ参数与主题数K随迭代次数变化的部分记录情况, 不难发现, 当迭代次数约达到2 172次时, 主题个数不再发生变化, 迭代过程趋于稳定, 此时获取最优主题数K=76.

(2) 主题数K的影响

本组实验分别将E-LDA方法中的主题数K设置为20, 40, 60, 80, 100与E-HDP方法进行比较, E-HDP方法的主题数K=76由HDP模型自动生成.图 6中的纵坐标表示相应的评价指标(准确率、召回率、F-measure及NDCG@N)的值, 横坐标为推荐Web API的数目, 分别设置为1, 2, 5, 8, 10.从图 6中可以观察到:当主题数K在20至80之间时, E-LDA的性能(准确率、召回率、F-measure及NDCG@N的值)随着主题数K的增加而上升; 当主题数K在80~100之间时, E-LDA的性能呈现下降趋势.这说明当主题数KK为80时, E-LDA方法具有最优的性能.从图 6中还可以发现, E-HDP方法与主题数K为80时的E-LDA方法性能基本相同(准确率、召回率、F-measure及NDCG@N的曲线相互缠绕近似重叠), 证明HDP模型能够自动生成最优主题数.

(3) 推荐方法比较分析

本组实验将HDP-FM与第4.3节中介绍的方法进行比较, 以此来说明HDP-FM具有良好的性能.与第4.4节情形(2)中的设置方式类似, 图 7中的纵坐标表示相应的评价指标的值, 横坐标为推荐Web API的数目.在图 7中我们不难发现, TF-IDF方法的性能最差, 因为TF-IDF方法仅仅利用词向量空间模型度量Web APIs与目标Mashup之间的相似度, 该方法忽略了文档与文档之间的语义信息; 其次, E-LDA及E-HDP方法分别引入LDA模型和HDP模型, 这两类主题模型均能挖掘描述文档的潜在语义信息(主题), 因此其性能较之TF-IDF在相似度的计算上更为精确; 再其次, LDA-CF与HDP-CF方法利用协同过滤算法来增强LDA及HDP算法, 以挖掘Web API与Mashup之间更深层次的链接关系, 性能相比仅仅使用LDA及HDP模型又有所提升.但是LDA-CF与HDP-CF方法由于协同过滤算法的局限性, 无法实现多维度信息的建模, FM方法能够将多维度的信息作为输入且避免稀疏性带来的影响, 因此, LDA-FM及HDP-FM方法在准确率、召回率、F-measure、NDCG@N上表现最优.值得注意的是, 实验中, 凡是使用到LDA模型的方法均通过手动调节选取最优主题数, 而涉及HDP模型的方法的最优主题数均由HDP模型自动生成.从图 7中我们可以看出, HDP-FM与LDA-FM、HDP-CF与LDA-CF、E-HDP与E-LDA均具有相似的性能, 这进一步说明了HDP-FM方法的优越性.

5 总结与展望

本文着眼于“根据用户的自然语言描述需求推荐可行的或者推荐可用于解决问题的任务集合”, 提出了HDP-FM方法用于推荐解决Mashup构建问题的Web APIs服务集合.HDP-FM方法通过多维信息处理与多维信息融合两个阶段, 将Mashups之间的相似度、Web APIs之间的相似度、Web API的共现性及流行度输入因子分解机模型, 利用评分排序结果, 为Mashup的创建推荐Top-N Web APIs作为推荐集合.本文的核心在于“利用HDP模型解决最优主题选取问题, 利用因子分解机模型解决多维信息融合问题”.为了验证HDP-FM方法的有效性, 本文分别采用了4种评价指标, 比较了多种Web APIs推荐方法.一系列的实验结果均表明, HDP-FM算法能够自动确定最优主题, 且具有较高的推荐准确性.在未来的工作中, 我们将继续探索机器学习技术来进一步提高Web API推荐的精度, 如, 可利用LSTM(long short-term memory, 长短期记忆网络)神经网络算法结合协同过滤、矩阵分解、因子分解机模型进一步提高服务发现的精度.