聚类技术在Web服务中的应用研究

黄媛

摘 要：通过对ProgrammableWeb在线社区进行研究，发现网站上的API服务数量庞大且含有丰富的数据信息。讨论了网页采集、数据预处理等相关技术，利用K-Means和凝聚层次聚类技术在API服务数据集上进行实验，实验结果表明，K-Means算法具有更好的聚类效果。

关键词：聚类；Web服务；K-Means；API服务数据

DOIDOI：10.11907/rjdk.171075

中图分类号：TP319

文献标识码：A 文章编号：1672-7800（2017）007-0149-03

0 引言

随着Web2.0技术的飞速发展，Mashup和API服务在Web开发者社区广为流行，并应用在许多开放的Web网站中。企业Web应用中Mashup与其它应用区别很大，常常不能重复使用或者没有Web API，人们不得不为这些应用去创建大量Web API。每天涌现的大量API服务需要一个平台来浏览 [1]。一些在线平台，例如雅虎、ProgrammableWeb.com等都允许用户发布各种API服务，一些非专业人士也能通过组合Web API服务或其它Web资源创建新的Web页面。ProgrammableWeb现在很流行，吸引了研究者的关注，推动了社区用户行为的研究[2]。目前网站已经有6 730个Mashup和6 783个开放的API服务，开发者不用测试就能将API服务结合起来。和传统的Web开发相比，Mashup越来越简单和流行，因为开发者不用测试和移植内部的Web应用就能使用这些数据，非技术人员也能通过在线社区快速集成已有的应用。

1 API服务聚类

1.1 描述相似性

API服务经过文档预处理[3]后，使用词语向量集表示。向量之间的相似性表示两个文本之间的相似性，可用向量之间的夹角余弦值表示，也叫作余弦相似性，这是目前在信息检索和聚类方法中度量文本相似性的最常用方法。设定文档ta→和tb→，文档间的余弦相似性计算公式如下：

ta→和tb→是词集T={t1，...，tm}上的m维向量，每一维都代表一个詞在文档中的权重，且为非负，余弦相似度非负并且属于[0，1]。

1.2 标签相似性

API服务的标注数据能起到描述API服务或是提供文本或语义信息的作用。本文根据标注数据的相似性，提出了改进API服务聚类性能的方法。给定一个包含3个标签t1，t2，t3的API服务，si的标签集Ti={t1，t2，t3}。通过Jaccard系数方法计算标签之间的相似性：

Simtag（si，sj）=|Ti∩Tj||Ti∪Tj|（2）其中|Ti∩Tj|是同时标注和标签数目，|Ti∪Tj|是Ti和Tj的并集。

根据以上公式，API服务si和sj的相似性sim（si，sj）计算如下：

sim（si，sj）=βsimdes（si，sj）+（1-β）simtag（si，sj）（3）其中，β是描述层相似性权值，1-β是标签层相似性权值，simdes（si，sj）是描述层相似性，simtag（si，sj）是标签层相似性，β取值范围是[0，1]，如果两个服务的描述和标签相同即是1，如果两个服务的描述和标签完全不同则是0。

2 聚类算法

2.1 K-Means聚类算法

K-Means是数据挖掘中的经典聚类算法[4]，在做大型数据集聚类时广泛使用。基本的K-Means算法中，每一次迭代计算每个数据集合对象到K个聚类中心的距离。

K-Means算法步骤如下：①从数据集D中，随机抽取其中的k个对象作为初始聚类中心；②计算每个数据对象di（1≤i≤n）和所有k个聚类中心cj（1≤j≤k）的欧式距离d（di，cj），并将数据对象di放到最近的聚类中；③对每个数据对象di找到最近的聚类中心cj，同时将di的值赋给聚类中心j；④将数据对象di所在的聚类中心标记以及存储数据对象di和最近的聚类之间的距离分别存储在数组Cluster[ ]和Dist[ ]中，设Cluster[i] =j， j是最近聚类标记，设Dist[i]=d（di，cj），d（di，cj）是最近的聚类中心距离；⑤对每个聚类j（1≤j≤k），重新计算聚类中心；⑥重复操作；⑦对每个数据对象di计算它和当前最近的聚类之间的距离。如果距离小于或等于Dist[i]，数据对象就存在初始的聚类中，否则对每个聚类中心cj（1≤j≤k）计算每个数据对象和所有聚类中心的距离d（di，cj），将数据对象di值赋给最近的聚类中心cj，设Cluster[i]=j，Dist[i]=d（di，cj）；⑧对每个聚类j（1≤j≤k）重新计算聚类中心；⑨直到满足收敛条件；B10输出聚类结果。

2.2 凝聚层次聚类算法

本文采用凝聚层次聚类算法[5] （以下简称Hierarchical算法）和基本的K-Means算法相比较。API服务用权值向量用R表示，相似性阈值初始值设为1，经过多次迭代后阈值慢慢减小直到为0。如果相似性指标满足阈值，标签就聚合在一起。在Hierarchical算法中，划分系数起着至关重要的作用，它定义了层次结构被划分成单个簇的层次数目。算法输出为API服务聚类的集合。

算法步骤：①将每个API服务单独作为一个聚类，将这些API服务作为聚类的种子；②将所有API服务放在一个层次簇中。基于服务之间的相似性，见公式（3），API服务簇集聚在一起，首先是相似度最高的API服务聚集在一起，然后是相似度略低的聚集在一起，结果是一个包含所有API服务的树形结构。聚合簇：满足当前相似性阈值的簇放在一起，有许多方式决定簇之间的距离：单连接、最大连接、平均连接等。文中采用簇的质心计算簇之间的距离。降低相似性：相似性阈值逐渐降低，重复上个步骤直到所有簇聚合在一起。将树剪成簇：层次树通过剪枝分割为多个簇；③调整参数，控制层次聚类的粒度，决定层次树的层次数目，参数最优时能将API服务慢慢聚合，同时捕捉到单个簇之间的概念关系。聚合速度太快会失去重要的API服务依赖性。endprint

3 实验

3.1 文档预处理

为了评估API服务聚类的性能，利用爬虫软件从ProgrammableWeb网站上爬取200个API服务构成实验数据集，同时获得每个API服务的名称、描述、标签等信息。在这个过程中对API服务作一些预处理操作，例如移除停用词、使用词干分析器等。

（1）提取词语。将语句拆分成词语，构建词语集合，然后从中提取名词作为词语的特征词。

（2）移除停用词。根据已经构建好的停用词列表移除停用词。列表作用是移除不能区分主题的普通词，如的、地、得等。

（3）处理词干。使用词干算法将一个词以词干或词根的形式表现。

（4）选择关键词。根据TF-IDF阈值方法获取能表示文档集的关键词。

TF-IDF（term frequency-inverse document frequency）是检索中常用的加权技术，是一种统计方法，用以评估某一个字或词对于语料库中的某个文件的重要程度。相应的字或词在文中出现越多其重要性越高，但其在语料库中出现越多重要性越低。搜索引擎常应用TF-IDF加权方法搜索文档。

3.2 评价指标

在信息检索中广泛使用精度作为评价聚类性能的一个主要指标，本文选择精度（precision）作为度量指标。

precisionci=succ（ci）succ（ci）+mispl（ci）（4）式（4）中，succ（ci） 是正确聚类到类ci中正确服务的数目，mispl（ci） 是划分到聚类ci中错误的服务数目。

3.3 结果

本文对照两种计算API相似性方法：

（1）D（description）：API服务的相似性根据API服务的描述文本相似性来计算。

（2）DAT（description and tag）：根据API服务描述文本的相似性和标签之间的相似性，组合计算API 服务的相似性（利用公式（3））。

本文分别用K-Means聚类方法和Hierarchical方法，比较两种计算API服务相似性的方法。从图1、图2可以看出，利用K-Means和Hierarchical方法聚类结果为5类，分别是关于艺术、交通、地图、通信、网站的服务，但是每个类中的服务数目有所不同。实验中K-Means算法的聚类时间较短，约为10秒，而Hierarchical方法聚类时间约为1分钟，使用K-Means算法的聚类时间较短。

从图3可以看出，K-Means算法利用D方法的聚类平均精度为59%，而利用DAT方法的聚类平均精度为79%，高于D方法的聚类平均精度。Hierarchical算法中利用D方法的聚类平均精度为52%，而利用DAT方法的聚类平均精度为73%，同样高于D方法的聚类平均精度。结果表明K-Means算法的聚类精度高于Hierarchical算法的聚类精度，利用DAT方法对API服务聚类效果更好。

4 结语

本文提出一种利用标注数据改进服务聚类性能的方法。在DAT方法中，计算了API服务间描述层和标签层相似性，然后利用描述层和标签层的组合相似性对API服务进行聚类。为了评价API服务的聚类性能，从ProgrammableWeb网站抓取了200个真实的API服务数据，采用K-Means和hierarchical算法进行聚类，实验结果表明DAT方法更好地改进了聚类性能。

参考文献：

[1]MALIHE DANESH， HOSSEIN SHIRGAHI. Text document clustering using semantic neighbors[J]. Journal of software Engineering， 2011， 5（4）：136-144.

[2]G ZHENG， A BOUGUETTAYA.Service mining on the web[J]. IEEE Transactions on Services Computing，2009， 2（1）：65-78.

[3]黃媛，李兵. 基于标签推荐的Mashup服务聚类[J].计算机科学，2013，40（2）：167-171.

[4]SU TING， DY J. A deterministic method for initializing K-means clustering[C].Tools with Artificial Intelligence， ICTAI，2004.

[5]HELENA AIDOS ， ANA FRED. Hierarchical clustering with high order dissimilarities[J]. Machine Learning and Data Mining in Pattern Recognition，2001.endprint