一种改进K-Means算法的服务聚类方法

黄 媛

(长江工程职业技术学院，武汉 430212)

一种改进K-Means算法的服务聚类方法

黄 媛

(长江工程职业技术学院，武汉 430212)

聚类方法能够提高Web服务检索的能力，针对传统的K-Means聚类算法聚类时间长的缺陷，文中提出了一种改进的K-Means服务聚类方法，并进行了有效性验证，在利用API服务数据集上进行实验 ，其结果表明：改进的K-Means服务聚类的方法降低了服务聚类的时间复杂度。

改进的K-Means;服务；聚类；时间复杂度

随着Web2.0技术的飞速发展，Mashup和API服务在Web开发者社区中广为流行，并且应用在许多开放的Web网站中。大量的API服务每天都在涌现，所以我们需要一个平台来浏览这些API服务。一些在线的平台，例如雅虎，ProgrammableWeb.com等都允许用户发布各种API服务。即使一些非专业人士也能通过组合Web API服务或其他的Web资源创建一些新的Web页面，当前ProgrammableWeb是一个很流行的社区，它吸引了大批研究者对社区用户行为进行研究。

1 Web服务聚类的相关研究文献

近年来，Web服务聚类作为一种服务发现方法是一种新颖的服务发现方法。Khalid等人从Web服务的WSDL文档中提取特征，如内容，服务名，主机名，进行Web服务聚类[1]，把聚类过程看作是发现的预处理阶段，希望帮助建立一个搜索引擎来爬取和聚类非语义的Web服务。一种个性化的交互式的标签推荐算法在文献[2]中提出，提供了一种特殊的依赖标签共享的数据标注方式。标签可以用图的方式来呈现，其中每个节点是标签，而节点之间的边反映的是同一个文档的共享情况。Harald等人[3]提出一种利用用户和其查询的Web页之间对应的主题的相似性进行排序的方法。一些文章也讨论过Web服务的标注。使用标签语义的方式来注释Web服务[4],使用结构化协同标签匹配Web服务。Liu等人[5]从WSDL文档中提取参数名，并将它们以概念来聚类，聚类结果能用来改进Web服务搜索结果的质量。

2 改进的K-Means聚类算法

K-Means是数据挖掘中一个经典的聚类算法，在大型数据集的聚类中该算法非常普及。由于标准的K-Means算法在每次迭代时需要计算每个数据对象到K个聚类中心的距离，所以在大型数据集上执行算法时会消耗大量执行时间。这是K-Means算法的缺点，下面提出一种改进的K-Means算法。

该算法主要思想是:首先设置两个数据集，分开保存聚类中心的标记以及在每次迭代中所有数据对象到最近聚类的距离，这些距离还能在下次迭代中继续使用，然后继续计算当前数据对象和新的聚类中心的距离，如果计算的距离小于或等于到之前聚类的距离，那么数据对象就被放到上一次迭代中的聚类中。因此无需计算该数据对象到其他k-1个聚类中心的距离，节省了计算到其余k-1个聚类中心的距离的时间。

改进的K-Means算法描述如下：

步骤1.从数据集D中随机选取k个数据作为初始聚类中心；

步骤2.计算每个数据di(1≤i≤n)和所有k个聚类中心cj(1≤j≤k)的欧式距离d(di,cj)，并将数据di放到最近的聚类中。

步骤3.对每个数据di，找到最近的聚类中心cj，同时将di的值赋给聚类中心j；

步骤4.将数据对象di所在的聚类中心标记以及存储数据对象di和最近的聚类之间的距离分别存储在数组Cluster[ ]和Dist[ ]中，设Cluster[i] =j, j是最近聚类的标记，又设Dist[i]=d(di,cj)，d(di,cj)是和最近的聚类中心的距离。

步骤5.对每个聚类j(1≤j≤k)，重新计算聚类中心；

步骤6.重复操作

步骤7.对每一个数据di，计算它和当前最近的聚类之间的距离；

步骤7.1.如果它的距离小于或等于Dist[i]，数据对象就存在初始的聚类中；

步骤7.2.否则对每个聚类中心cj(1≤j≤k)来说，计算每个数据对象和所有聚类中心的距离d(di,cj)，将数据对象di的值赋给最近的聚类中心cj，设Cluster[i]=j;Dist[i]=d(di,cj);

步骤8. 对每个聚类j(1≤j≤k)，重新计算聚类中心；

步骤9.直到满足收敛条件；

步骤10.输出聚类结果；

这个改进的K-Means算法需要两个数组Cluster [ ]和Dist [ ]存储每次迭代过程产生的信息，以便用于下一次迭代当中。数组Cluster[ ]存储最近聚类中心的标记，数组Dist [ ]存储数据对象和最近聚类中心的距离。这些数组中的信息减少了重复计算数据对象和最近聚类中心的距离(利用公式(1))的次数，这就使得改进的K-Means算法比标准的K-Means算法执行速度更快，数据集越大时，算法效果愈明显。

3 改进K-Means算法的实证

3.1 文档预处理

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

(1)提取词语。将句子拆分成词，然后提取名词作为词语特征词。

(2)移除停用词。使用到包括要排除的词的停用词列表。这个列表作用是移除不能区分主题的普通词，如“的，地，得”等。

(3)处理词干。使用已有的词干算法将一个词转化为它的词干或词根的形式。

(4)选择关键词。应用TF-IDF阈值方法来选择文档集的关键词。

TF-IDF(term frequency-inverse document frequency)是一种用于检索中常用的加权技术。TF-IDF是一种统计方法，用以评估某一个字或词对于语料库中的某个文件的重要程度。相应的字或词在文中出现得越多其重要性越高，但与其在语料库中出现越多重要性越低。搜索引擎常应用TF-IDF加权的各类形式度量文件与用户查询之间相关程度。

3.2 API服务相似性

(1)

3.3 评价指标

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

(2)

式中，succ(ci)是正确聚类到类ci中正确的服务的数目，mispl(ci)是划分到聚类ci中错误的服务的数目。

3.4 结 果

为了评价改进后算法的聚类性能，在3.1中的API数据集上进行试验，结果如图1、图2所示，从图1中看到改进的K-Means聚类算法和标准K-Means聚类算法都将API服务被分成了5类，分别是关于艺术，交通，地图，通信，网站的服务。但是每个类中的服务数目有所不同，两算法的执行时间也不同，前者聚类时间不到10 s，后者执行时间超过60 s。

为了验证本方法的有效性，我们选择人工分类的方法，手动对这200个服务进行分类，将分类结果作为聚类结果的基线，聚类结果精度如图2所示，从图中可以看到改进的K-Means聚类算法聚类平均精度为53.8%，标准K-Means聚类算法聚类平均精度为41.8%，这表明改进的K-Means聚类算法比标准的K-Means聚类算法更好地改进了聚类的性能。

图1 改进和标准的K-Means聚类算法聚类结果比较

图2 改进和标准的K-Means聚类算法聚类精度比较

4 小 结

为了提高Web服务聚类的性能，文中提出了一种改进的K-Means聚类算法，改进服务聚类的性能。为了评价API服务的聚类性能，从ProgrammableWeb网站上爬取了200个真实的API服务进行试验，实验结果表明改进的K-Means聚类算法聚类精度较高，聚类时间较短，聚类效果较好。

[1] Khalid Elgazzar, Ahmed E. Hassan, Patrick Martin. Clustering WSDL documents to bootstrap the discovery of web services[A]. In Proceeding of Conference on Web Services[C]. 2009:147-154.

[2] Shengliang Xu, Shenghua Bao, Ben Fei, Zhong Su, Yong Yu. Exploring folksonomy for personalized search[A]. In Proceeding of 31st Annual International ACM SIGIR Conference on research and development in information retrieval[C]. 2008:155-162.

[3] Harald Meyer, Mathias Weske. Light-Weight Semantic Service Annotations through Tagging[A]. In Proceeding of 4thinternational conference on service-oriented computing-ICSOC[C]. 2006:465-470.

[4] Shengliang Xu, Shenghua Bao, Ben Fei, Zhong Su, Yong Yu. Exploring folksonomy for personalized search[A]. In Proceeding of 31st Annual International ACM SIGIR Conference on research and development in information retrieval[C]. 2008:155-162.

[5] Fangfang Liu, Lei Wang, Jie Yu. Context-aware similarity search of web service[A]. In Proceedings of 2012 IEEE International Conference on Information Science and Technology[C].2012:596-602.

Service Clustering Method to Improve K-Means Algorithm

HUANG Yuan

(Changjiang Institute of Technology, Wuhan 430212, China)

The clustering method can improve the retrieval ability of Web service. To the defects of long clustering time of the traditional K-Means clustering algorithm, an improved method has been introduced and verified. The experiments based on the date sets of API services show that the improved K-Means method can reduce the time complexity of the clustering service.

improved K-Means method; service; clustering; time complexity

2017-01-11

黄 媛(1983-)，女，武汉人，讲师，博士，研究方向：数据挖掘、服务计算。

TP39

A

1673-0496(2017)02-0035-03

10.14079/j.cnki.cn42-1745/tv.2017.02.012