基于语义相似度的Web服务分类算法研究

来源:用户上传      作者:

　　【摘 要】现有的Web服务分类语义信息获取方法大多基于预先定义的类别信息、或者基于人工指定服务社区的方式实现，其中专家知识具有一定的主观性、片面性和随意性。有效避免专家知识的主观性、片面性和随意性，本文以基于本身的描述信息为基础、以统计计算为基本手段、以机器学习中的分类算法为依据，提出了不同粒度的Web服务对象之间的语义相似度度量方法，采用已有的语义相似度度量的方法及K-NN分类算法的思想，并使用对K-NN算法进行改进后而得到的WS-KNN算法，对Web服务进行分类。本文提出和实现的服务分类方法能很好地避免已有的服务分类工作的各种不足，服务之间的语义相关性基于大量的历史数据学习而得到，有自动分类的效果，同时分类的方法简单可行、实现方便，可为服务社区的自动构建和服务的自动发现奠定一定的理论和工程化基础。
　　【关键词】语义相似度;分类;K-NN算法;WS-KNN算法
　　中图分类号： TP393.09 文献标识码： A 文章编号： 2095-2457（2019）14-0053-004
　　DOI：10.19694/j.cnki.issn2095-2457.2019.14.024
　　0 引言
　　学术界从以下几个不同的侧面对Web服务有不同的描述：从功能的角度描述Web服务，文献[1-8]认为Web服务基于TCP/IP、HTTP、XML等规范而定义，具有以下功能：Web上链接文档的浏览，事务的自动调用，服务的动态发现和发布。文献[5-9]从语义的角度描述了基于语义Web的服务，认为Web服务是语义Web的一种应用，由于考虑了语义信息的描述及表示，Web服务能够更准确地被执行，服务组合（service composition）能够按所期望的目标进行。
　　本文对Web服务做分类，每个Web服务都包含一个与之相对应的WSDL文档，因此对Web服务做分类就是对WSDL文档做分类，而从WSDL文档的定义当中，文档当中所包含的操作能够度量一个WSDL文档的性质，因此选择其操作之间的相似度来度量WSDL文档之间的相似度，然后通过分类算法对其做分类。
　　分类的概念：分类分析的目的是在给定其他变量的条件下对感兴趣的未知变量值作出预测。数据分类的目的在于根据新数据对象的属性，将其分配到一个正确的类别当中。为进行数据的分类，首先需要建立一个分类模型，用以描述预定的数据集，常用的分类模型包括判别分类及决策边界模型、概率模型以及数模型，当所建立的模型经测试后达到了所要求的准确率，便可以用其对未知目标号的数据对象进行分类。分类分析中的待分类数据称为样本、实例或对象，为建立模型而被分析的数据构成训练数据集，其中的单个数据称为训练样本[2]。
　　目前已有的分类算法很多，以下介绍几个常用的算法[2]：基于距离的分类：首先是最短距离分类，它的原理是欧氏距离公式，设c1，…，cm代表了n维空间Rn中的m个类，如果类ci能够由其中某一代表向量（一个n维向量xi）来表示，xi描述了类ci的中心，那么对于输入向量y的分类问题可以根据y到xi（i=1，2，…，m）的距离来判断。欧氏距离在分类分析中被广泛采用作为距离的尺度，其特点是简单容易被人接受。其次是最近邻分类算法：设c1，…，cm代表了n维空间Rn中的m个类，给定包含了N个数据样本的集合{x1，…，xn}，已知该集合中各样本的先验分类信息。对于任意输入向量y，最近邻分类器将y划分到y的最近邻样本所在的类中。与最短距离分类器相比，最近邻分类器并不考虑各类的代表向量，而是在已知先验分类信息的数据样本中考查与输入向量y之间具有最短距离的邻居样本，直接将最近邻居样本的分类信息作为y的分类信息。在基于距离的分类之中还包括了k-最近邻分类，其算法如下：
　　输入：
　　N：已知分类信息的样本个数
　　n：向量空间的维数
　　m：Rn中类的个数
　　（si，sj）1≤i≤N：N個序偶对，其中si为第i个事先已知分类信息的样本，ji为si所属的类（1≤ji≤m）
　　K：最近邻样本的个数，也称为k-最近邻分类算法的阶
　　y：待分类的输入量
　　输出：
　　L：y的分类信息。
　　步骤1令S={（si，sj）}，1≤i≤N
　　步骤2找到（x，j0），使得||x-y||=min||z-y||，（z，j）∈S
　　步骤3果k=1，则令l=j0，算法结束;
　　否则，初始化n维向量IC：IC（i’）=0，i’≠j0;IC（j0）=1，S=S-{（x，j0）}
　　步骤4FOR DO
　　（1）找到，（x，j0）∈S使得||x-y||=min||z-y||，（z，j）∈S
　　（2）令IC（j0）=IC（j0）+1，S=S-{（x，j0）}
　　END FOR
　　步骤5令l=max{IC（i）}，1≤i≤m，算法结束
　　在上述算法中，欧式距离被作为定义“靠近”的尺度，而k选取不同的值，分类的结果将会不同。最简单的形式是取k=1，但是这样得到的分类器相当不稳定，即变化性大，对数据过于敏感，因此很多时候通过提高k值以使预测更加一致，但是可能增大分类的偏差。事实上，增大k值意味着“小胞体”可能并不小，被包含近来的样本数据未必和输入向量非常靠近。K-最近邻分类方法容易编程实现，并且不需要优化和训练;对于某些问题，其分类具有很高的精确度，可以和基于神经网络的方法相比;它可以直接扩展到多分类的情况，也是可以处理被分类向量中残缺值的情况，K-最近邻分类方法并不建立模型，而是依赖于把所有训练数据集中的样本数据全部保存下来，基于此，把这种分类方法称为“消极学习方法（或懒散学习方法）”。 　　本文主要采用基于距离的分类方法中的K-最近邻分类算法来Web服务做分类，使用该算法来衡量两个WSDL文档之间的相似度，首先使用相似度的度量方法计算出两个文档当中操作的相似度，之后采用该算法来计算两个文档之间的“距离”，当两个文档之间的“距离”大于或等于某一个特定值的时候就说它们相似，同时将其们归为一类。
　　1 Web服务描述信息的抽取和服务间的语义相似度
　　1.1 Web服务描述信息的抽取
　　定义Web服务的WSDL文档主要包括下列元素：
　　·Types：数据类型定义的容器，它使用某种类型系统（一般地使用XML Schema中的类型系统）。
　　·Message：通信消息的数据结构的抽象类型化定义。使用Types所定义的类型来定义整个消息的数据结构。
　　·Operation：对服务中所支持的操作的抽象描述，一般单个Operation描述了一个访问入口的请求/响应消息对。
　　·PortType：对于某个访问入口点类型所支持的操作的抽象集合，这些操作可以由一个或多个服务访问点来支持。
　　·Binding：特定端口类型的具体协议和数据格式规范的绑定。
　　·Port：定义为协议/数据格式绑定与具体Web访问地址组合的单个服务访问点。
　　·Service：相关服务访问点的集合。
　　WSDL文档中包含了这些元素，本文抽取WSDL文档中的操作（Operation）作为原子服务，因为每个WSDL文档中包含了大量的操作。在WSDL文档定义好之后，我们将对操作中的输入输出等各项操作进行抽取，例如在第2章的实例中，我们抽取input、output这两个操作。因此通过先对WSDL文档之间的操作分类，用这个分类的结果来衡量WSDL的相似度[10]，从而为Web服务的分类奠定基础[3-7]。
　　1.2 Web服务组件之间的语义相似度
　　要实现Web服务的自动分类，首先要对WSDL文档中的操作进行分类，这是实现Web服务分类的前提条件，也是实现服务分类的基础，同时也是实现服务分类必不可少的。已有的相似度度量的方法中具有代表性的一个是文献[3]，其描述如下：对一个文本文档来说，文档当中的相同文字出现的频率是衡量文档相似度最直观的因素，在此我们不妨将文本文档看成是语义包，同时将文档当中的文字看作语义元素。下面是几个相关的定义：
　　定义1.直接引起人们关注的语义实体我们称作为语义包，记做Pi，语义的最小组织单位我们称之为语义元素，记为Ej。
　　根据实际应用中的各种不同的情况，不同的语义实体都能够被选作为语义包。比如，Web站点能够被选作语义包，同时Web页面则是Web站点的语义元素。在一个更好的粒度下，Web页面是语义包，而文字是Web页面的语义元素。通过包里语义元素的不同的情况，我们需要弄清语义元素之间的语义关系。我们用P={P1，P2，…，Pm}来表示一个语义包，用E={E1，E2，…，En}来表示包含在语义包P中的语义元素。Ei对Ej的支持我们用Ei→Ej来表示，其中i与j不相等;Ei对Ej的支持度我们用φ（Ei→Ej）来表示：
　　φ（Ei→Ej）=N（Ei∩Ej）/N（Ej）（1）
　　N（Ej）表示選取包含Ej语义包的概率，N（Ei∩Ej）表示选取中包含Ei又包含Ej的语义包的概率。很显然，φ（Ei→Ej）不一定与φ（Ej→Ei）相等。
　　定义2.φ（Ei，Ej）叫做语义包P中语义元素Ei与Ej之间的亲和度，其中：
　　φ（Ei，Ej）=N（Ei∩Ej）/N（Ei∪Ej）（2）
　　φ（Ei，Ej）称为Ei与Ej之间的语义距离。
　　定义3.为了实现Web服务组件之间的相似度的度量，首先进行下列符号意义的说明：
　　（1）OPi：这表示某一个WSDL文档中的第i个操作;
　　（2）OPi∩OPj：表示对某两个WSDL文档中的操作取交集，也即是求两个文档中相同的操作（i=1，2，3…）;
　　（3）OPi∪OPj：表示对某两个WSDL文档中的操作取并集，也即是求两个文档中所有的操作数（j=1，2，3…）;
　　（4）N（OPi∩OPj）：表示求取某两个WSDL文档中所有语义相同或相似的操作总数;
　　（5）N（OPi∪OPj）：表示求取某两个WSDL文档中所有的操作数;
　　（6）Sim（OPi，OPj）：表示包含i个操作的WSDL文档与包含j个操作的WSDL文档之中操作的语义相似度。
　　下面定义WSDL文档中操作之间的语义相似度的度量标准。
　　定义4.WSDL文档中操作之间的语义相似度的度量标准定义为
　　Sim（WSi，WSj）=N（OPi∩OPj）/N（OPi∪OPj）（3）
　　通过定义3明确算法中的各个符号所表示的具体意思，定义4中的算法中输入的是不同的WSDL文档中相同的操作数，以及两个WSDL文档中所有的操作数目，通过它们的比值，将得到操作之间的相似度。
　　再给出定义4中的公式（3）一些性质：
　　（1）Sim（OPi，OPi）=1;
　　（2）Sim（OPi，OPj）=Sim（OPj，OPi）。
　　在本文中将采取这种方法度量WSDL中操作的相似度，基于WSDL操作之间相似度度量方法，进一步可对WSDL文档进行分类，是本文中研究Web服务分类的关键问题和核心技术。
　　1.3 Web服务之间的语义贴近度
　　第3.2节中，介绍了Web服务组建（操作）之间的语义贴近度，下面介绍WSDL文档之间的语义相似度。WSDL之间的相似度用来度量两个WSDL文档之间的相似程度，第3.2节主要讲述了对从WSDL文档中抽取的操作的语义相似度，本节以第3.2节为基础，第3.2节主要介绍了WSDL文档中组件（操作）之间的语义相似度，但是只有操作之间的语义相似度是不能解决WSDL文档之间相似度的度量的，本节主要是在第3.2节已有的工作基础之上来进行Web服务之间的语义相似度的度量工作。为了讨论的方便，首先定义度量WSDL文档之间相似度工作的相关符号。 　　定义5.
　　（1）WSi：表示第i个Web服务文档（即WSDL文档），在该文档中包含了n个操作，这其中的操作依然用OP来表示，同样操作之间的相似度用Sim（OPi，OPj）来表示，操作之间的相似度已知;
　　（2）S（WSi，WSj）：表示第i个文档与第j个文档之间的相似度;
　　（3）Counti-j：表示一个初值为一的计数器，它记录了第i个文档与第j个文档当中所包含的操作之间进行的相似度度量所计算的次数。
　　下面我们给出计算的公式：
　　S（WSi，WSj）={∑Sim（OPi，OPj）}/Counti-j（4）
　　当Sim（OPi，OPj）≥ε（ε的值给定）时，如果S（WSi，WSj）≥ε’（ε’的值也是给定），那么我们就说WSi与WSj相关（也就是相似）。
　　在该算法当中，OPi∈WSi，OPj∈WSj;i与j都是正整数，都从1开始计数。Counti-j的初始值置为1，操作之间的相似度度量算法每进行一次，计数器自加一次。
　　2 基于Web服务间语义相似度的服务分类
　　2.1 基于Web服务语义相似度的Web服务分类算法
　　计算出Web服务WSi与WSj之间的相似度是本章研究的核心，本章将用到K-最近邻分类算法的改进算法，称之为WS-KNN算法，该算法吸取了KNN分类算法的思想，但是在WS-KNN算法中，用待分类的WS文档与已知分类信息的WS文档之间的相似度与从实验中学习出来的度量值作比较，该算法的基本思想如下：
　　用已知分类信息的WS文档及待分类的WS文档作为算法的输入，要求输出待分类的WS文档的分类信息。在WS-KNN算法中，首先将已知分类信息的WS文档和该文档的类别分别对应起来并以一个序偶对的方式存放在数组S中，然后使用一个两重循环将已知的待分类文档和样本文档之间相似度的值S（WSj，WSi）存放在一个二维数组Sji中，在Sji大于等于已知的度量值ε的基础上，分别把待分类的文档WSj归为与之进行相似度计算的WSi文档所属的类别Cn中，如果Cn相同，也就是这些WSi属于同一个类别，理所当然将WSj归到类Cn中;如果Cn不尽相同，那么取大多数WSi所属的类别Cr作为WSj所属的类，分类算法结束。
　　对WS-KNN算法的描述如下：
　　算法1
　　输入：
　　N：已知分类信息的样本个数
　　WSi：已知分类信息的WS文档
　　WSj：待分类的WS文档
　　C：已知分类信息文档所属类别的集合
　　m：已知类的数量
　　ε：从实验中所得出的分类信息度量值
　　K：输入的待分类的WS文档的个数
　　S（WSj，WSi）：已知的待分类文档和样本文档之间相似度的值
　　输出：
　　WSj在C中所属的类别
　　步骤如下：
　　步驟1 令S={（WSi，Cn）}，（1≤i≤N，1≤n≤m）
　　步骤2 FOR j=1，2，…，K-1
　　FOR i=1，2，…，N-1
　　 Sji=S（WSj，WSi）
　　 END FOR
　　 END FOR
　　 IF Sji≥ε
　　 （WSj，WSi）∈Cn
　　IF Cn=Cr（r为一个定值）
　　WSj∈Cr
　　 ELSE WSj∈Cr（Cr为大多数WSi所属的类别）
　　END IF 算法结束
　　对输入的待分类的WS文档，使用第3章中的相似度度量方法与已知分类信息的WSi进行相似度度量，可以得出S（WSi，WSj）的值（1≤i≤K，1≤j≤N），然后与已知的分类信息的度量值ε做比较，如果S（WSi，WSj）≥ε，则称WSi与WSj相似，我们将WSi与WSj中大多数相似的文档的类别作为WSi的类。
　　2.2 应用实例
　　下面使用一个实例来综合说明一下我们工作的正确性和可行性。
　　例5：现有旅游服务和销售代理两个类别，分别记为Ctravel和Csale。
　　（1）在Ctravel中有样本文档WS1、WS2，分别包含了操作{buy gift，book ticket，search travel information }和{buy gift，book ticket，search travel information，select guide，sale house}。
　　（2）在Csale中有样本WS3，WS3中包含了操作{search travel information，sale house，sale computer}，现有待分类的WS文档WS4={search travel information，select guide，sale house}，度量值ε=0.400。
　　为了计算的方便，分别记buy gift，book ticket，search travel information，select guide，sale house，sale computer为OP1，OP2，OP3，OP4，OP5，OP6。
　　根据定义3得到：
　　N（OP1∩OP2）=2，N（OP1∩OP3）=2，N（OP1∩OP4）=1，N（OP1∩OP5）=1，
　　N（OP1∩OP6）=0，
　　N（OP2∩OP3）=2，N（OP2∩OP4）=1，N（OP2∩OP5）=2，N（OP2∩OP6）=1，
　　N（OP3∩OP4）=2，N（OP3∩OP5）=2，N（OP3∩OP6）=0，N（OP4∩OP5）=2， 　　N（OP5∩OP6）=1;
　　N（OP1∪OP2）=3，N（OP1∪OP3）=3，N（OP1∪OP4）=4，N（OP1∪OP5）=4，
　　N（OP1∪OP6）=3，
　　N（OP2∪OP3）=4，N（OP2∪OP4）=4，N（OP2∪OP5）=4，N（OP2∪OP6）=3，
　　N（OP3∪OP4）=3，N（OP3∪OP5）=4，N（OP3∪OP6）=4，
　　N（OP4∪OP5）=3，N（OP4∪OP6）=3，
　　N（OP5∪OP6）=3，
　　根据定义4中的公式（3）可以得到：
　　Sim（OP1，OP2）=N（OP1∩OP2）/N（OP1∪OP2）=2/3，
　　Sim（OP1，OP3）=N（OP1∩OP3）/N（OP1∪OP3）=2/3，
　　Sim（OP1，OP4）=N（OP1∩OP4）/N（OP1∪OP4）=1/4，
　　Sim（OP1，OP5）=N（OP1∩OP5）/N（OP1∪OP5）=1/4，
　　Sim（OP1，OP6）=N（OP1∩OP6）/N（OP1∪OP6）=0，
　　Sim（OP2，OP3）=N（OP2∩OP3）/N（OP2∪OP3）=2/4，
　　Sim（OP2，OP4）=N（OP2∩OP4）/N（OP2∪OP4）=1/4，
　　Sim（OP2，OP5）=N（OP2∩OP5）/N（OP2∪OP5）=2/4，
　　Sim（OP2，OP6）=N（OP2∩OP6）/N（OP2∪OP6）=1/3，
　　Sim（OP3，OP4）=N（OP3∩OP4）/N（OP3∪OP4）=2/3，
　　Sim（OP3，OP5）=N（OP3∩OP5）/N（OP3∪OP5）=2/4，
　　Sim（OP3，OP6）=N（OP3∩OP6）/N（OP3∪OP6）=0，
　　Sim（OP4，OP5）=N（OP4∩OP5）/N（OP4∪OP5）=2/3，
　　Sim（OP4，OP6）=N（OP4∩OP6）/N（OP4∪OP6）=0，
　　Sim（OP5，OP6）=N（OP5∩OP6）/N（OP5∪OP6）=1/3;
　　进而，根据算法1可以得到：
　　WS1与WS4的相似度度量值为：S（WS1，WS4）=13/27≈0.481≥0.400
　　WS2与WS4的相似度度量值为：S（WS2，WS4）=27/60≈0.450≥0.400
　　WS2与WS4的相似度度量值为：S（WS3，WS4）=14/45≈0.311≤0.400。
　　已知WS1、WS2都是类Ctravel中的样本，WS3是Csale中的样本，而容易看出，WS4与WS1、WS2最相似，故而将WS4归为Ctravel中。
　　首先利用定义4中的公式（3）计算出了WSDL文档之间操作的相似度，基于此利用公式（4）计算出了待分类的WSDL文档与已知分类信息之间的相似度，然后利用算法1得到了待分类的WSDL文档的分类信息。通过实例，能看出，本文提出的方法能够有效地实现Web服务的分类。
　　即使已知分类信息的文档很多、待分类的文档的数量也很大的时候，本文中算法1只要2个嵌套循环就能实现Web服务的分类，算法的时间复杂度为O（n2），这与“人以类聚、物以群分”的分类思想一致，也具有较高的效率。
　　3 总结
　　本文着重介绍了KNN算法的改進算法WS-KNN算法，基于这些现有的方法、遵循已有的Web服务标准协议，以WSDL中的服务描述信息为载体，讨论基于语义的Web服务相似度度量标准及响应的服务分类算法，最终实现Web服务的分类。
　　本文提出和实现的服务分类方法能很好的避免已有的服务分类工作的各种不足，服务之间的语义相关性基于大量的历史数据学习而得到，有自动分类的效果，同时分类的方法简单可行、实现方便、效率较高。本文的分类方法以传统的K-NN分类算法为基础，而基于所提出的语义相似度对其进行无缝的改进，具有一定的实用价值。
　　【参考文献】
　　[1]岳昆，王晓玲，周傲英.Web服务核心支撑技术：研究综述，软件学报，2004，15（3）：428-442.
　　[2]刘惟一，李维华，岳昆.智能数据分析，科学出版社，2007.
　　[3]K. Yue， W. Y. Liu. Semantic-Field Model for Information Retrieval. Technical report， 2007.
　　[4]B. Benatallah， M.Dumas， Q. Z. Sheng， A. Ngu. Declarative Composition and Peer-to-Peer Provisioning of Dynamic Web Services. ICDE，2002，297-308.
　　[5]A. Heb，N.Kushmerick.Learning to Attach Semantic Metadata to Web Services.ISWC，2003，258-273.
　　[6]U. Küster， M. Stern， B. K？觟nig-Ries.A Classification of Issues and Approaches in Automatic Service Composition. Intl. Workshop WESC 05，2005.
　　[7]A.Heb，N.Kushmerick.Machine Learning for Annotating Semantic Web Services.WESC，2004.
　　[8]F. Curbera，W.A Nagy，S. Weerawarana. Web Services： Why and how. In： Hailpern B， etal， eds.Pric. of the OOPSLA 2001 Workshop on Object-Oriented Web Services.Tampa：ACM. 2001.
　　[9]Y.L Shi，G.Huang，W.Ye， L.Zhang， B.L Shi. Automatic Composition of Web Services Based on Task Dependency Specification.Journal of Computer Research and Development. 2006：2110-2116.
　　[10]J.L Sun，L.Q Gong. A Study on the Technology Standards of Web Services Composition. Shi jia zhuang 2005.
转载注明来源:https://www.xzbu.com/8/view-14907600.htm