白吉光,蔡鸿明,步丰林

(上海交通大学 软件学院,上海 200240)

面向开放服务环境的服务推荐方法研究及实现

白吉光,蔡鸿明,步丰林

(上海交通大学 软件学院,上海 200240)

开放服务环境下,服务缺乏结构化描述信息难以进行精确内容匹配,同时面向服务功能的推荐具有强上下文约束,目前已有的推荐方法在此应用场景下难以实施.针对这一问题,研究并提出一种针对服务的功能性需求,混合了语义分析和协同过滤的服务推荐方法.该方法可以为应用开发者的功能性需求进行精准推荐,具有应用价值.

服务推荐;协同过滤;语义分析

随着网络环境的飞速发展,大多开发者逐步转向基于云环境的开发模式.基于云环境的应用开发部署和维护正成为发展的趋势,但合适的开放服务查找是一项很有挑战性的工作.过去开发者们通过在线搜索引擎、服务注册中心等方式去寻找服务,但都存在结果噪声大、无个性化优化等缺点,因此,研究能够精准推荐开放服务的服务推荐方法,具有较大应用意义和研究价值.

在服务推荐领域已经有大量研究,这些方法可分为基于内容策略的推荐方法、基于协同过滤的推荐方法以及基于社交网络的服务推荐方法等.

基于内容策略的推荐方法通过分析学习服务自有属性如服务功能描述、输入输出规范等信息,在预设规则下进行推荐.这类方法一般作为补充与其他方法混合,如文献[1]提出的混合协同过滤和内容特性方法.另外在开放环境下,服务往往没有统一标准的服务描述信息,难以对服务的非结构化描述进行匹配分析,推荐效果并不理想.

基于协同过滤的推荐方法则利用历史偏好信息推断出潜在的推荐,主要分为以用户为中心和以项为中心的推荐[2]等.协同过滤方法具有模型直观、能发现潜在推荐等特点.许多研究以服务的QoS(quality of services)为指标,提出基于协同过滤的服务推荐方法[3],这类方法适合在已知满足需求的服务备选池时,从中选取最为稳定的服务,但不适用于筛选出满足需求的服务.

基于社交网络的推荐方法利用社交关系反映出潜在的兴趣偏好传播性.文献[4]基于Programm-ableWeb.com的Mashup记录提出了一种基于社交的服务组合方法;文献[5]提出了引入社交影响因素的组合推荐方法;文献[6]针对创建Mashup提出一种基于社交网络的推荐方法.此类方法特点是面向最终用户,认为用户对服务的兴趣偏好反映他们的实际使用需要,特征较为稳定.但开发者对服务的兴趣偏好取决于应用的需求,变化大难以从社交网络和历史数据中挖掘,因此，此类方法与传统的协同过滤并不适合为开发者进行推荐的应用场景.

针对大多推荐方法难以精确地进行功能性服务推荐的问题,本文提出一种面向开放服务环境的服务推荐方法,结合语义分析优化协同过滤对历史数据的使用,实现针对功能性需要的精准推荐,并充分利用云环境带来的便利,提高推荐结果的准确度,减少推荐与查询的时间,以帮助开发者快速得到满足其开发需要的服务.

1 研究框架

面向开发者的开放服务推荐是建立从服务功能需求到满足该需求服务间联系的过程.因此可以参考与当前需求相类似的历史需求,其中包含开发者的服务选择,这些信息可用于筛选排序相关服务,为当前查询进行推荐.虽然难以得到开发者需求的结构化描述,但可以由开发者用自然语言详细描述其需求,系统通过语义分析等一系列方法得到历史需求的模型,为在线推荐提供数据支持.本文针对开发者使用开放服务进行应用开发的需求,设计了以功能性需求为中心的服务推荐方法,并设计了在线离线相结合的服务推荐框架,如图1所示.

图1 服务推荐系统框架Fig.1 Service recommendation system framework

系统的外界输入有WordNet、可用服务的信息和开发者的需求查询.其中开发者查询通过积累形成历史推荐纪录,与WordNet一起作为离线引擎的输入数据.离线模型引擎得到的需求概念特征和功能分类作为在线推荐的输入，通过计算得到推荐结果.

离线模型引擎对开发者的历史查询记录进行分析及学习,为在线推荐提供离线模型,过程主要分为以下3个步骤:

(1) 功能描述语义分析,获取并处理所有历史推荐查询的功能需求自然语言描述,并且根据WordNet的语义数据抽取其中的语义概念,形成查询-概念矩阵；

(2) 特征学习,分析并学习上述查询-概念矩阵,得到潜在特征模型,包括需求概念特征模型和功能描述特征模型；

(3) 功能分类学习模块,根据功能描述的特征模型,通过建立功能相似图,学习得到功能分类模型.

在线服务推荐则分析开发者通过系统交互界面输入的应用需求模型,得到需要使用开放服务开发的功能模块,以及各个功能模块的具体功能需求描述.之后抽取各个需求描述中的需求语义概念,利用它和需求概念特征模型得到当前查询的需求特征,最后在功能分类模型中进行分类匹配并得到服务推荐列表.

2 功能需求为中心的服务推荐方法

本文提出的服务推荐方法分为4部分: 功能描述语义分析、特征学习、功能分类学习和在线服务推荐及优化.功能描述语义分析部分处理开发需求中的功能描述,包括在线查询和历史查询;分析结果由特征学习部分处理得到查询特征和需求概念特征;查询特征经由功能分类学习部分得到功能分类;在线推荐部分根据在线查询输入、需求概念特征和功能分类给出推荐结果.

2.1 功能描述语义分析

系统要求开发者在向系统提交查询时，为每个功能模块均用一段自然语言描述这个模块需要实现哪些功能,每个描述中都会有一些关键词表达最核心的意义和概念.将这些功能描述拆解为一个个的语义概念,就可以将模块的描述从计算机难以理解的自然语言转化为计算机可以理解和处理的数据结构.选择从WordNet的object和activity类别中选取词语并合并同义词,形成一个概念集合.构建这样的概念集合是因为通过研究ProgrammableWeb.com上所有服务的关键字和标签,发现所有服务均与数据实体或操作相关,因此开发者的每次查询操作中,功能需求描述里与数据实体和操作相关的概念最能够体现实际的功能需求.

设系统中开发者集合为U,查询历史集合为Q,定义功能描述概念集合C={c1,c2,…,cm}.以概念集合为基础,通过语义分析,可以抽取U中所有开发者u的历史查询q所对应的所有功能描述概念.定义Iq为历史查询q的语义概念向量,如式(1)所示.

Iq=(iq1,iq2,…,iqm)T

(1)

其中:iqj代表历史查询q中概念cj是否出现,0代表未出现,1代表出现.由此将所有查询的概念向量合并可以得到查询-概念相关性矩阵Y,如表1所示.

表1 查询-概念相关性矩阵Table 1 Query-concept relation matrix

2.2 特征学习

根据矩阵Ym×n可以计算任意两个查询之间的相似性,因为二者是在m维概念空间中用概念向量进行表示,共有的概念比例越高意味着查询相似性越高.理论上是可以直接进行计算的,但存在的实际问题是概念集合C维度太高,进行计算所需资源过高,不具备实现可行性,因此需要利用其他方法进行问题的转化.

在矩阵理论中,矩阵Y可以分解为两个矩阵的乘积,如式(2)所示.

(2)

LFM(latent factor model)方法认为,矩阵分解后得到的中间维度t是意义不明确的特征.在Y分解的矩阵中,代表历史查询功能描述和功能描述概念有t个共有的抽象特性,或者如果将所有服务的功能分为t个特性维度进行分析,则St×m是所有的语义概念在这t维特性空间中的向量表示所形成的矩阵,类似的Vt×n是所有的历史查询在这t维特性空间中的向量表示所形成的矩阵.不同的分解得到不同的维度t,但在一次矩阵分解后维度t的特性空间所隐含表达意义是固定的,因此，用这种方法可以将维度过高的m维概念空间降低为较低且具有实际计算可行性的t维特性空间.其中St×m作为离线引擎的需求概念特征模型提供给在线推荐.

在实际的矩阵分解中,由于矩阵Y是一个稀疏的高维矩阵,其基本的矩阵分解方法计算复杂度过高,不具备可行性.因此采用随机梯度下降法得到近似的矩阵分解结果,通过使用已有的矩阵数据计算预期误差,进而不断迭代调整参数使得误差最小化.预测得到的查询语义概念相关性可用式(3)表示.

(3)

使用随机梯度下降法的最小化误差函数即可得到近似矩阵分解.其中所使用的误差函数如式(4)所示,使用early-stop方法学习合适的步长以得到较优的结果.

(4)

矩阵分解后得到的Vt×n中即包含任意历史查询的特性向量:vq,q∈Q,因此可以根据这个矩阵得到任意两个历史查询所需功能的相似性.

2.3 功能分类学习

与m维概念空间中的概念矩阵Ym×n相似,Vt×n是所有的历史查询在t维特性空间中的特性矩阵,由所有历史查询的特性向量组成,因此，同样可以用一些方法计算任意两个历史记录的特性相似性.事实上特性相似程度也体现着它们的功能需求相似程度,即有相似的功能性需求.由于历史记录数据量不确定,功能需求的分类数量更不可知,具有不确定性,k-means等确定分类数量的分类方法效果不佳,因此,系统采用非监督的LPA(label propagation algorithm)进行分类学习. LPA的基本思想是每个节点应当与其他多数邻居处在同一类别,因此,初始化每个节点并为其分配唯一类别,不断随机遍历所有节点将其类别更新为多数邻居的类别,收敛条件为没有节点需要更新其类别,这种方法能够快速进行网络节点分类处理.

系统首先用cos相似度计算方法得到任意两个历史查询间的相似度,如式(5)所示,其中vi表示查询i的特性向量.

(5)

但是将LPA算法应用在稠密的查询相似度矩阵上会导致收敛缓慢，同时较低相似度的查询对于分类的影响很小.因此为每个历史查询保留其相似度最高的K个查询，形成稀疏的历史查询相似度矩阵，这样能够保证LPA算法快速收敛，提高计算效率.

采用LPA对历史查询进行功能性需求分类,形成离线引擎的功能分类模型.至此，系统完成了从历史查询的功能性描述分析到历史查询的功能特性分类离线模型的建立.

2.4 在线服务推荐及优化

当开发者在线请求为其推荐服务时,系统会分析开发者输入的描述其功能需求的自然语言,用离线模型引擎反馈的功能特性分类模型辅助计算,得到满足开发者需求的服务推荐.

(6)

将查询q′的特性向量与通过学习得到的功能分类模型的各个分类平均向量进行相似性比较,找出最为接近的功能分类,根据该分类的历史选择排序对用户进行服务推荐.

2.5 算法描述

根据上述分析,得到混合了语义分析和以功能需求为中心的协同过滤服务推荐算法,描述如下:

算法1: 功能需求为中心的协同过滤服务推荐算法FCF(functional requirements oriented collaborative filtering service recommendation algorithm)

输入:W: =WordNet中的概念单词,Q: =历史推荐请求集合,R: =当前开发者的推荐请求t: =特征维度

输出: REC: =系统得出的推荐结果

FCF (W,Q,R,t)

Y: =Matrix[W.size][Q.size] // 初始化查询-概念相关性矩阵

forqinQ:

forwinW:

ifwinq. Description WordArray: // 设置查询q与概念w的相关性

Y[w][q]: =1

S: = Matrix[W.size][t] // 需求概念特性矩阵

V: = Matrix[Q.size][t] // 功能描述特性矩阵

MatrixFactorization(Y,S,V) // 分解矩阵Y,得到Y=SVT

P: = Matrix[Q.size][Q.size]

forifrom 0 toQ.size -1:

forjfrom 0 toQ.size -1:

P[i][j]: =sim(V[i],V[j]) // 根据两个历史请求的特性向量计算相似度

KeepTopKInEachRow(P) //为每个历史请求保留与其最接近的K个服务

L: =Matrix[Q.size]{0…Q.size -1} // 所有节点的标签,默认独立标签

do:

count: = 0 // 每次Label Propagation迭代更新的节点数

forifrom 0 toQ.size -1:

l: = MostInNeighbor(i,P,L) // 当前节点多数邻居的分类

ifl<>L[i]: // 需要更新分类

L[i]: =l

count: =count+1

while count >0

G: =Dict // 历史推荐记录按功能需求的分类字典

forifrom 0 to Q.size -1:

Dict[L[i]]. AddRecord(Q[i].RecordArray) // 分类统计历史服务选择

g: =MostSimilar(R,G) // 找到与当前请求最接近的分类

returng. Records.Sort().Top(k) // 返回分类中被选择次数最多的服务

在实际的应用中,开发者利用开放服务构建应用,往往需要得到多个功能需求的推荐.如果存在一个用户已经选择的服务同样可以满足另外一个功能,则应当为另一个功能着重推荐这个服务,因为这样可以减少开发者的开发时间.另外如果存在一个服务A,历史上很多开发者选择将它和另一个服务B用在同一个应用中,且B还可满足一个未选择服务的功能,则应当着重推荐服务B.

3 系统实现与案例分析

3.1 系统实现及案例分析

以本文提出的服务推荐方法为核心,设计并实现了基于web面向开发者的服务推荐系统.开发者在网页上用建模的方式描述其开发需求,提交后系统将根据历史记录找到合适的服务进行推荐,用户在得到推荐结果后可进行初步选择,系统会根据用户的选择进行动态的推荐优化,从应用整体开发角度出发为开发者进行组合推荐.

为验证系统方法的可行性,选取一个企业内部差旅管理系统的应用需求案例: 某企业日常有大量的出差交流安排,需要实施一个差旅管理系统.从功能角度分析,系统需要为后勤人员提供酒店预订、飞机票预订、火车票预订以及日程安排等功能,为出行人员提供日程查询管理、外出导航以及本地信息服务,为节约开发成本和时间,部分功能考虑使用开放服务实现.

(1) 应用需求分析. 根据以上分析,在本文实现推荐系统的在线可视化建模中,建立这个差旅管理系统的部分功能模型,如图2所示.功能模型包含了后勤人员和出行人员所需功能的建模描述,包括描述后勤人员的3种预订功能,以及出行人员的4种信息查询需要,并区分了内部开发与外部开放服务实现， Booking System和Personal Assistant为系统内部实现功能,其他为需要利用开放服务实现的功能.

(2) 系统推荐. 系统根据建立的功能模型为各个功能需求进行服务推荐.

第一步进行需求语义分析. 从一个源自WordNet的概念集合中统计得到每个功能需求描述包含的概念,具体到本例中的需求概念统计结果如表2所示,其中大部分服务有多个概念对应其需求,可以较好地代表功能.从这一步也可以看出,服务功能描述越长越精确,抽取得到的概念越多效果也越好.

图2 功能模块建模Fig.2 Functional modeling

表2 需求描述所含概念Table 2 Concepts in functional description

第二步利用离线模型计算推荐结果. 由于离线模型的建立需要有功能描述的历史推荐记录,而系统建立初期没有这样的记录,因此使用了ProgrammableWeb.com上已存在的mashup记录模拟历史推荐数据.总共选取了最近5年内的5 000条mashup记录,这些记录包含有实现功能的描述以及所选服务,与系统实际产生的推荐记录形式基本一致.根据本文所述方法建立历史记录的概念矩阵,选取特性空间维度t为300,分解矩阵降维后运用LPA分类得到共约450个功能分类.实际在线推荐时运用离线引擎建立的功能分类模型进行计算匹配,找到最接近的分类后按照历史服务选择次数排序推荐. 本例的最终服务推荐结果如图3所示.

图3 服务推荐结果Fig.3 Service recommendation result

图3中，每一列是推荐系统为开发者提出的每一个功能需求得出的推荐结果列表.同时还根据开发者的选择动态调整推荐: 开发者为第一列Hotel Booking功能选择了第三个服务,这个服务同时也可以实现第二列Airline Booking所需的功能,使用这个服务实现两个功能可以减少工作量,因此系统着重向开发者推荐它用于实现第二个功能并说明原因；开发者为第三列Map Service选择了Google Maps,推荐系统发现在历史中有很多开发者在应用内同时使用了Google Maps和Yahoo Weather,表明这两个服务存在一定的配合应用合理性,因此为开发者推荐使用Yahoo Weather实现天气信息功能.

(3) 实例验证. 最后,在系统推荐的列表中选取了部分较为合适的服务用于开发这个差旅管理系统,为出行人员提供了每日天气信息和日程安排记录,每个日程都有基本指导、地点和地图导航,部分日程还有详细安排信息.利用开放服务提供的便利,应用能够快速开发出来并且完成基本功能帮助出行人员管理每日行程.

在开发过程中,发现系统推荐的服务可以很好地满足差旅管理系统的功能需求,并且开发所需工作量合理.但同时也存在一些不足,如系统推荐的默认排序主要考虑服务的功能性,却没有考虑开发者的开发语言等实际开发问题,仍然需要开发者就这些约束进行二次筛选；另外，各个服务在数据格式一致性上存在一些不足,需要在实现时进行数据转换.总体而言,本文实现的推荐系统能够较好地满足开发人员对于开放服务的查询和推荐需要,并在一定程度上为开发者进行整体推荐优化.

3.2 比较和讨论

在服务推荐领域,很多学者都做了大量工作,如文献[4]提出的一种基于社交的服务组合推荐方法,以及文献[7]提出的一种利用用户社交网络为用户进行精准服务推荐的方法.这些方法都以服务组合推荐为目标,其与本文提出的服务推荐方法FCF的一些比较如表3所示.

表3 3种服务推荐方法的比较Table 3 Comparison of three service recommendation methods

(续 表)

通过比较可以发现，本文的方法主要面向开发者需求,向开发者提供完整描述其需求的可能，针对开发者的选择进行动态推荐反馈，实际开发应用难度较低.

4 结 语

本文针对在开放服务环境中服务精确描述信息缺失,以及传统协同过滤方法在以功能性需求为中心的服务推荐中存在强上下文约束的问题,提出一种混合语义分析以功能性需求为中心的协同过滤服务推荐方法.通过提取历史推荐请求的功能性需求特征对历史请求进行功能性分类形成功能分类模型,在线实时推荐系统使用该功能分类模型给出满足开发者需求的服务推荐,同时根据用户的动态选择实时调整组合推荐结果.通过推荐系统实现及实际案例验证,表明该方法能够有效地在开放服务环境下为开发者推荐满足其功能开发需要的服务.但目前该方法对开发者的实际开发约束条件考虑较少,同时在应用内组合推荐时仍然有继续优化的可能.

[1] YAO L,SHENG Q Z,SEGEV A,et al. Recommending web services via combining collaborative filtering with content-based features[C]//IEEE International Conference on Web Services. Santa Clara,United States,2013: 42-49.

[2] SU X,TAGHI M K. A survey of collaborative filtering techniques[J]. Advances in Artificial Intelligence,2009.http: //dx.doi.org/10.1155/2009/421425.

[3] CHEN X,ZHENG Z,LIU X,et al. Personalized QoS-aware web service recommendation and visualization[J]. IEEE Transactions on Service Computing,2011,6(1): 35-47.

[4] BORIS T,ROMINA T,HERNAN A. Simplifying mashup component selection with a combined similarity and

social-basedtechnique[C]//Proceedings of the 5th International Workshop on Web APIs and Service Mashups. Lugano,Switzerland,2011: 1-8.

[5] CHEN W,INCHEON P,TANAKA T,et al. Awareness of social influence for service recommendation[C]//IEEE International Conference on Service Computing. Santa Clara,United States,2013: 767-768.

[6] XU W,CAO J,HU L,et al. A social-aware service recom-mendation approach for mashup creation[C]//IEEE International Conference on Web Services. Santa Clara,United States,2013: 107-114.

[7] CAO B,LIU J,TANG M,et al. Mashup service recom-mendation based on user interest and social network[C]//IEEE International Conference on Web Services. Santa Clara,United States,2013: 99-106.

Research and Implementation of Service Recommendation Method in the Open Service Environment

BAIJi-guang,CAIHong-ming,BUFeng-lin

(School of Software,Shanghai Jiao Tong University,Shanghai 200240,China)

In the open service environment,it’s hard to achieve the precise content matching for services because of the lack of structural description information. Furthermore service recommendation based on service functional requirements,which have strong contextual constraints,makes existing service recommendation methods not applicable in this scene. To deal with this problem,a method focus on service functional requirements is studied,which mixes semantic analysis and collaborative filtering. This method can make precise service recommendation meet the functional requirements of developers,as well as the requirements of their actual work.

service recommendation;collaborative filtering;semantic analysis

1671-0444 (2016)05-0718-07

2015-12-03

国家自然科学基金资助项目(71171132,61373030);上海市自然科学基金资助项目(13ZR1419800)

白吉光(1989—),男,陕西渭南人,硕士研究生,研究方向为信息系统. E-mail: bjggzxb@sjtu.edu.cn 蔡鸿明(联系人),男,副教授， E-mail: hmcai@sjtu.edu.cn

TP 315

A