利用关联规则挖掘的Web API组合模式发现

夏艳敏,唐 兵,唐明董,2,曹步清,乔 帅

1(湖南科技大学 计算机科学与工程学院,湖南 湘潭 411201) 2(广东外语外贸大学 信息科学与技术学院,广州 510006)E-mail:btang@hnust.edu.cn

1 引 言

在API经济模式[1]的推动下,越来越多的企业纷纷以Web API的形式在互联网上发布数据或服务以实现商业增值.通过有效组合不同功能的Web API,可以开发出功能强大、有创意的Web应用,这成为了一种非常流行的软件开发方式[2].然而,尽管现实中通过组合Web API开发软件的方式越来越普遍,但是对于API组合中所蕴含的规律和模式仍然缺乏认识.如何根据API组合模式和API之间的关联关系帮助开发者快速地从众多的Web API中挑选合适的API去构建新的应用成为了一种重要的研究问题.目前,尽管有些工作已经调研了Web API之间的关系,但对于Web API 组合模式的研究还很少见.

近年来,标签在对网络资源进行管理和检索方面取得了巨大的发展,互联网上的各种内容都被标注了标签[3,4].这些标签体现了对标注资源的功能概括和描述,能够方便用户更好地理解、分类和检索相关资源.由于Web API的标签代表着它自身的功能、用途等属性,因此,可以将Web API的标签类比成关联规则挖掘技术[5]的“购物篮分析”中的商品并结合Mashup中的Web API组合关系来发现API之间的关联关系即API的标签关联规则.这些标签关联规则可以体现出哪些功能属性的Web API经常被组合在一起构成Web应用,能够在一定程度上反映出Web API的组合模式.

挖掘标签关联规则能够更好地发现标签之间的潜在关系[6-8].Fernandez等人[9]基于标签云之间的相似性来建立Web服务之间的关联规则.Wang等人[10]结合Web API和标签发现了Mashup用户的行为模式.Goarany等人[11]得到了Web API的二项集标签关联规则,并用这些规则来预测有趣的Mashup模式.聂规划等人[12]运用Apriori算法挖掘出了基于用户行为的Web服务组合关联规则.Ni等人[13]使用RuleTree算法得到Web API之间的正负标签关联规则为Mashup推荐Web API.Tang等人[14]基于Web服务的关联关系和它们的标签共现关系构建了一个三层的Web服务网络视图模型.但是上述工作都没有考虑标签用词的不规范,形式不统一和同义词问题带来的影响,部分工作只考虑了标签的二项集,并且缺少对挖掘结果的真实评估.

本文提出了一种基于关联规则挖掘的WACP方法来发现Web API的组合模式.该方法利用了Web API上代表功能属性的标签以及历史的Web API组合关系,先将Web API的标签结合Stanford CoreNLP(1)Stanford CoreNLP, https://stanfordnlp.github.io/CoreNLP/进行词形还原,再结合WordNet(2)WordNet, https://wordnet.princeton.edu/对标签进行了同义词统一等处理,然后使用基于FP-growth[15]的Web API标签关联规则挖掘算法对Web API之间的标签进行挖掘得到了具有强关联性的Web API标签关联规则.这些具有强关联性的Web API标签关联规则在一定程度上反映了Web API的组合模式.这些API组合模式可以帮助开发者快速、准确地从众多的Web API中选择合适的Web API组合构成新的Web应用以满足多样化的功能需求.WACP方法不仅可以挖掘频繁二项集,并且能够得到所有项集的Web API组合模式.通过使用ProgrammableWeb(3)ProgrammableWeb, https://www.programmableweb.com/的真实数据集进行实验比较与分析,结果表明WACP方法相比于其它方法在查准率、查全率和F值等指标上都有所提高.

本文的组织结构如下:第1节介绍Web API组合模式的背景和相关工作;第2节详细讲述Web API组合模式挖掘过程及相关算法;第3节为实验结果与分析;第4节对全文内容进行总结,并展望了下一步的工作.

2 Web API组合模式挖掘

本文提出了一种WACP方法来挖掘Web API组合模式,WACP的功能结构如图1所示,它主要包括4个功能模块:

1)数据提取:从ProgrammableWeb上爬取数据集,从数据集中提取实验所需要的Web API名称、标签和Mashup名称、Web API组合记录等信息.

2)Web API标签处理:将Web API标签进行去除无意义词、词形还原、同义词统一等处理,提高标签的无异义性和准确性.结合API标签以及Mashup中的API组合记录生成Web API组合标签集.

3)Web API标签关联规则挖掘:根据Web API组合的标签集,结合基于FP-growth的Web API标签关联规则挖掘算法来挖掘具有强关联性的Web API标签关联规则.

图1 WACP的功能结构Fig.1 Framework of WACP

4)获取Web API组合模式:将具有强关联性的Web API标签关联规则中的无意义规则进行过滤得到Web API组合模式,这些模式能够准确反映出Web API之间的功能关联关系.

2.1 数据提取

该过程主要是从ProgrammableWeb中提取实验所需要的Web API的标签、历史Web API组合记录等信息.Web API、Mashup和tag的关联关系如图2所示.

2.2 数据预处理

为了获得高质量的数据,减少实验误差,提高Web API组合模式的准确性,本文将Web API的标签进行了以下处理:

1)去除无意义词.在数据处理过程中发现Web API的标签中存在一些无实际意义的单词,例如不规则长字符串(如 referencemusicmusicbrainz).因此,本文定义了一个动态无意义词表,用于去掉数据集中无实际意义的词.

图2 Mashup,Web API,Tag元素关联图Fig.2 Relationships among web APIs,mashups and tags

2)词形还原.Web API的标签单词存在许多不同的形态,如ing、ed等.这些单词的不同形态会造成挖掘出现仅词性不同的、具有完全相同意义的标签关联规则,如“blog→media”和“blogging→media”.为了使挖掘所得的标签关联规则结果更为准确,需要将标签单词还原成一般形式并去重.本文结合Stanford CoreNLP工具实现对标签的词形还原.

3)同义词统一.在数据分析过程中发现Web API标签中存在许多意思相同或相近的标签,如bike和bicycle、phone和telephone等.由于不同开发者有不同的描述习惯,对同一事物的描述也有可能采用不同的单词,从而会导致开发者在定义Web API时可能使用不同标签来表达同一含义.而这种同义词情况会产生许多功能类似的标签关联规则,如“telephone→webhook”和“phone→webhook”、“place→bicycle”和“place→bike”.Web API标签中的同义词会影响Web API组合模式的准确度和可靠性.本文结合WordNet对数据集中的标签进行了同义词统一处理,更能提升Web API组合模式的可靠性.

将处理后的Web API标签以及历史API组合信息相结合,得到所有Web API组合的标签集,以进行接下来的Web API标签关联规则的挖掘.

2.3 Web API标签关联规则挖掘

关联规则挖掘技术[5]通常用于描述两个或多个事物之间存在的某种潜在的关联关系,下面是它的相关定义:

定义1.设L={l1,l2,…,lm}是项的集合,I是数据库事务的集合,每个事务T是一个非空项集,T⊆L.设X是一个项集,事务T包含X,X⊂L,Y⊂L,X≠∅,Y≠∅,X∩Y=∅.关联规则是在I中成立的形如X→Y的蕴涵式.

定义2.令num(I)表示数据库事务I的总数,num(X∪Y)表示I中包含X∪Y事务的个数,关联规则X→Y的支持度的计算公式为:

(1)

定义3.关联规则X→Y的置信度指事务集中包含X事务中包含Y事务所占的百分比,计算公式为:

(2)

判断一个关联规则是否有用和准确,即看它的支持度、置信度是否满足最小支持度、最小置信度阈值,如果大于阈值则为有用的、正确的规则,否则为无用的规则.

本文提出一种“基于FP-growth的Web API标签关联规则挖掘算法”用于挖掘形如“[tagi1,tagi2,…,tagin]→tagx”且具有强关联性的Web API标签关联规则,其中{tagi1,tagi2,…,tagin,tagx}⊆Tapi,Tapi为Web API组合的标签集合.该算法一共分为3个步骤:1、构建FP-tree;2、挖掘FP-tree得到标签频繁项集;3、挖掘Web API标签强关联规则.

1)构建FP-tree.根据Web API组合标签事务集,构建Web API组合标签的FP-tree.该过程算法如下:

步骤1.构建FP-tree

Imput:Web API 组合标签事务集W.

Output:FP-tree.

1)扫描W一次,收集标签频繁项的集合B,将B按照支持度计数降序排序得到频繁项列表Lfreq.

2)创建FP-tree的根节点“Null”,将W中的每个事务Trans执行以下2个步骤:

a)得到Trans中的所有标签频繁项,并按照Lfreq进行排序.

b)设排序后Trans的频繁项列表为[t|T],其中,t是频繁项中的第一个标签,T是频繁项中剩余的标签.如果存在结点F有子结点M,使得结点M的标签等于t标签,那么结点M的数目加1;否则创建一个新结点N并计数为1,链接到它的父结点F.

3)递归操作第2步,直到将W中的所有事务都添加到FP-tree中.

2)挖掘FP-tree得到标签频繁项集.根据构建的FP-tree,调用FP-growth函数得到Web API标签频繁项集.该过程算法如下:

步骤2.挖掘FP-tree得到标签频繁项集

Imput:FP-tree,最小支持度计数min_sup.

Output:Web API标签频繁项集.

1)挖掘FP-tree通过调用FP-growth(FP-tree,Null)实现.

1.ProcedureFP-growth(Tree,α):

2.ifTree包含路径Pthen

3.for路径P中结点的每个组合(记作β)do

4. 产生项集β∪α,支持度计数等于β中结点的min_sup

5.endfor

6.else

7.forFP-tree的头表中的每个标签aido

8. 产生项集β=ai∪α,支持度计数等于ai的支持度计数

9. 构造β的条件FP-treeTreeβ

10. ifTreeβ≠∅then

11. 调用FP-growth(Treeβ,β)

12.endif

13.endfor

14.endif

2)根据FP-tree得到所有的Web API标签频繁项集以及这些项集对应的支持度计数.

3)挖掘Web API标签强关联规则.由Web API标签频繁项集生成Web API标签强关联规则.该过程算法如下:

步骤3.挖掘Web API标签强关联规则

Imput:Web API标签频繁项集,最小置信度min_sup.

Output:Web API标签关联规则.

1)定义标签关联规则组成元素,关联规则前项用“condition”表示,后项用“result”表示,关联规则的形式为“condition→result”.

2)对于每个满足min_sup的标签频繁项集Item生成对应的标签关联规则,过程如下:

1.FunctionListTagRuleMining(Item):

2.tagrules←∅,i←0

3.ifItem≠∅then

4.whilei

5.result←Item.get(i)

6.condition←condition∪Item.subList(0,i)

7.condition←condition∪Item.subList(i+1,Item.size)

8. 产生规则 “condition→result”并将该规则放入tagrules中

9.i++

10.endwhile

11.endif

12.返回的tagrules即为由标签频繁项集Item生成的标签关联规则.

3)得到所有形如“condition→result”的Web API标签关联规则.

通过设置min_conf阈值,得到满足min_conf即具有强关联性的所有Web API标签关联规则.

2.4 获取Web API组合模式

在得到的形如[tagi1,tagi2,…,tagin]→tagx的所有Web API标签强关联规则中,如果tagi1,tagi2,…,tagin和tagx是属于同一个Web API中的标签,则需要过滤掉这类规则.因为这样的规则并不能反映Web API之间的功能关联关系,这些来自于同一个Web API的标签仅仅只是一种相同或相似概念来描述相同的API资源.获取Web API组合模式的过程如下所示:

1.得到所有Web API的自身标签集,并新建Web API标签关联规则过滤列表filterRule.

2.将Web API的自身标签集结合FP-growth算法生成需要过滤掉的Web API标签关联规则并放入filterRule中,这些规则的前项和后项都来自于相同的Web API.

3.将2.3中得到的所有Web API标签关联规则与filterRule中的规则进行匹配,如果规则存在于filterRule中,那么删除该规则,如果不存在则保留该规则.

4.最终保留的Web API标签关联规则即为得到的Web API组合模式.

经过上述步骤得到的Web API组合模式正确反映了Web API之间的功能关联关系,能够体现什么功能属性的Web API常被组合在一起开发新应用.

3 实验结果及分析

3.1 数据集

本实验使用的数据集是从ProgrammableWeb上爬取的9135条Web API记录以及6875条Mashup记录.其中,Web API记录包括API名称、标签、类别、网址、描述文档等信息.Mashup记录包括Mashup名称、标签、使用的Web API组合等信息.

3.2 实验结果

3.2.1 Web API标签处理

将Web API的标签进行词形还原、同义词统一等处理,表1展示了部分处理后的Web API标签数据.

表1 Web API标签处理结果举例Table 1 Examples of Web API tag processing

3.2.2 Web API标签频繁项集

将处理后的Web API标签集作为基于FP-growth的Web API标签关联规则挖掘算法的输入,得到了Web API标签的频繁项集.表2展示了部分Web API标签频繁项集以及它们的频数.

表2 Web API标签频繁项集结果举例Table 2 Examples of tag frequent itemsets

3.2.3 Web API标签关联规则挖掘

通过训练Web API之间的标签频繁项集得到了Web API之间的标签关联规则,通过设置最小支持度、最小置信度阈值来获得具有强关联性的规则.其中,最小支持度阈值设置为0.007(50/6875),即在6875条Mashup记录中,规则出现的个数不少于50;最小置信度阈值设置为0.6.表3为2项集Web API标签关联规则前10个最优规则.

3.2.4 获取Web API组合模式

去除Web API标签强关联规则中不能反映出API之间的组合关系的规则得到Web API组合模式,这些Web API组合模式能够准确反映出API之间的功能组合关系.表4展示了2、3、4项集的前5个最优的Web API组合模式.

这15条记录是从Web API组合模式中选择的二项集、三项集、四项集支持度、置信度最高的前5条组合模式以及它们的支持度、置信度.这些Web API组合模式是由代表功能属性的API的标签训练得到的标签关联规则,并且通过了规则的筛选过滤,它们能够准确反映出API之间在功能上的关联关系以及API之间的组合模式.当然,Web API最优组合模式也可以根据其他指标来选择,如设置不同的模式长度、支持度阈值、置信度阈值等.

表3 2项集Web API标签关联规则前10个最优规则Table 3 Top 10 Web API tag association rules for 2-itemsets

表4 多项集Web API组合模式中前5个最优模式Table 4 Top 5 Web API tag association rules for multi-itemsets

以表4的第6条组合模式为例,“[display,video]→map”表示“display”、“video”标签通常与“map”标签存在于不同API中,并且这些不同的API能够通过组合形成Web应用.从“bigsity”Mashup的API组合关系中发现,该mashup中的“yahoo local search”API包含“display”标签,“youtube”API包含“video”标签,“google maps”API包含“map”标签,这三个标签同时存在于Web API组合中并且“display,video”和“map”来自于不同的API,说明“[display,video]→map”反映出了API在功能上的关联关系且为正确的Web API的组合模式.

结合Web API的组合模式,开发者可以更加准确、快捷地构建最合理的Web 服务.例如,当开发者已拥有包含“geolocation”标签属性的Web API并需要结合新的API组成Mashup时,这时可以根据“[geolocation]→display”组合模式推荐包含“display”标签的Web API组成新的Mashup.

3.3 方法比较

1)WACP:该方法首先去除Web API标签中的无意义词,再对标签进行词形还原和同义词统一等处理得到Web API组合标签事务集,通过使用基于FP-growth的Web API标签关联规则挖掘算法得到所有项集的Web API标签强关联规则,过滤掉不能准确反映Web API之间功能关联关系的规则得到Web API组合模式.

2)Goarany等方法[11]:该方法直接使用Web API的标签以及API之间的历史组合关系得到形如“(tagm,tagn)”的二项集Web API标签对,将每个标签对中的两个标签共同历史调用次数进行统计得到支持度和置信度,过滤掉两个标签同时存在于相同Web API的标签对,每个标签对可以生成两条形如“tagm→tagn”和“tagn→tagm”的规则,对所有标签对进行该操作得到所有Web API二项集标签关联规则.

3.4 评价指标

由于Web API组合模式个数较多,本文选取Web API的所有二项集组合模式进行实验评价.实验采用了数据挖掘中常用的评估指标:查准率(Precision)、查全率(Recall)和二者综合评价的F值(F-measure).

Mashup的标签描述了Web API组合和Mashup两者的功能情况,它能从一定程度上反映出Web API之间的关系[11].在本实验中,假定根据Mashup自身标签挖掘出的标签关联规则为正确规则,若Web API组合模式存在于Mashup标签关联规则中,那么认为这条Web API组合模式为正确模式,反之则为不正确模式.以下为查准率、查全率、F值的公式:

查准率公式:

(3)

查全率公式:

(4)

F值公式:

(5)

其中,findtrue为检索到的Web API组合模式中的正确模式数目,findfalse为检索到的Web API组合模式中的不正确模式数目,unfindtrue为未检索到但却是正确的Web API组合模式数目.

3.5 评价结果

图3为本文所提出的WACP方法与Goarany等提出的方法在支持度阈值下的Web API组合模式的查准率、查全率、F值性能对比图.图4为本文所提出的WACP方法与Goarany等提出的方法在置信度阈值下的Web API组合模式的查准率、查全率、F值性能对比图.

从图中可以看出,对于本实验使用的3种评估标准,不管是从支持度阈值还是置信度阈值的角度去评估,WACP方法都要优于Goarany等提出的方法.当支持度阈值从0.0002到0.0012时,WACP方法的F值分别高于对比方法 1.6%、1.7%、1.5%、1.3%、1.4%、1%,当置信度阈值从0.005到0.03时,WACP方法的F值分别高于对比方法 1.6%、1.6%、1.7%、1.6%、1.5%、1.6%.

由于Web API的标签存在无意义词、词性不统一和同义词等现象,Web API标签质量并不是特别高,在这些情况下容易产生不正确的Web API组合模式和能够表达相同API功能关联关系的许多重复模式,使得Web API组合模式的准确性并不高.另外,Web API标签关联规则中存在许多不能反映出API之间功能关联关系的规则,这也会影响到Web API组合模式的准确性.

本文提出的WACP方法考虑到了对Web API标签进行词形还原、同义词统一等处理,提高了标签的质量.另外,将Web API标签关联规则中的不合理规则的进行了过滤,使得每个Web API组合模式都能够准确地反映API之间的功能关联关系.相比于Goarany等提出的方法只得到了API之间的二项集关联规则,本文使用的基于FP-growth的Web API标签关联规则挖掘算法挖掘得到了所有项集的Web API组合模式,另外,该算法在性能上也优于Goarany等提出的方法和Apriori等.因此,使用WACP方法得到的Web API组合模式更加准确,Precision、recall和F-measure值也有明显提高.

图3 不同支持度阈值下的实验结果Fig.3 Experiment results in different support threshold

图4 不同置信度阈值下的实验结果Fig.4 Experiment results in different confidence threshold

4 总结与讨论

本文为发现Web API生态系统中的API组合模式,提出了一种基于关联规则挖掘的方法—WACP.该方法通过结合Web API的标签以及历史的API组合关系,先将API标签进行了词形还原、同义词统一等处理,再使用基于FP-growth的标签关联规则挖掘算法得到了Web API之间的标签强关联规则,最后对规则进行过滤得到了Web API组合模式.Web API组合模式的发现可以为开发者从众多的Web API中挑选合适的Web API组合提供支持.实验结果表明了WACP方法的有效性.

许多Web API上标注的标签数很少甚至没有,这种数据稀疏性可能会影响Web API组合模式发现的效果.未来工作将考虑Web API的标签扩展,如从Web API的描述文档中提取关键字推荐新的标签,以进一步提高标签关联挖掘和Web API组合模式发现的性能.