基于語(yǔ)義相似度的Web服務(wù)分類(lèi)算法研究

田杰

【摘 要】現(xiàn)有的Web服務(wù)分類(lèi)語(yǔ)義信息獲取方法大多基于預(yù)先定義的類(lèi)別信息、或者基于人工指定服務(wù)社區(qū)的方式實(shí)現(xiàn)，其中專(zhuān)家知識(shí)具有一定的主觀性、片面性和隨意性。有效避免專(zhuān)家知識(shí)的主觀性、片面性和隨意性，本文以基于本身的描述信息為基礎(chǔ)、以統(tǒng)計(jì)計(jì)算為基本手段、以機(jī)器學(xué)習(xí)中的分類(lèi)算法為依據(jù)，提出了不同粒度的Web服務(wù)對(duì)象之間的語(yǔ)義相似度度量方法，采用已有的語(yǔ)義相似度度量的方法及K-NN分類(lèi)算法的思想，并使用對(duì)K-NN算法進(jìn)行改進(jìn)后而得到的WS-KNN算法，對(duì)Web服務(wù)進(jìn)行分類(lèi)。本文提出和實(shí)現(xiàn)的服務(wù)分類(lèi)方法能很好地避免已有的服務(wù)分類(lèi)工作的各種不足，服務(wù)之間的語(yǔ)義相關(guān)性基于大量的歷史數(shù)據(jù)學(xué)習(xí)而得到，有自動(dòng)分類(lèi)的效果，同時(shí)分類(lèi)的方法簡(jiǎn)單可行、實(shí)現(xiàn)方便，可為服務(wù)社區(qū)的自動(dòng)構(gòu)建和服務(wù)的自動(dòng)發(fā)現(xiàn)奠定一定的理論和工程化基礎(chǔ)。

【關(guān)鍵詞】語(yǔ)義相似度;分類(lèi);K-NN算法;WS-KNN算法

中圖分類(lèi)號(hào)： TP393.09文獻(xiàn)標(biāo)識(shí)碼： A文章編號(hào)： 2095-2457（2019）14-0053-004

DOI：10.19694/j.cnki.issn2095-2457.2019.14.024

0 引言

學(xué)術(shù)界從以下幾個(gè)不同的側(cè)面對(duì)Web服務(wù)有不同的描述：從功能的角度描述Web服務(wù)，文獻(xiàn)[1-8]認(rèn)為Web服務(wù)基于TCP/IP、HTTP、XML等規(guī)范而定義，具有以下功能：Web上鏈接文檔的瀏覽，事務(wù)的自動(dòng)調(diào)用，服務(wù)的動(dòng)態(tài)發(fā)現(xiàn)和發(fā)布。文獻(xiàn)[5-9]從語(yǔ)義的角度描述了基于語(yǔ)義Web的服務(wù)，認(rèn)為Web服務(wù)是語(yǔ)義Web的一種應(yīng)用，由于考慮了語(yǔ)義信息的描述及表示，Web服務(wù)能夠更準(zhǔn)確地被執(zhí)行，服務(wù)組合（service composition）能夠按所期望的目標(biāo)進(jìn)行。

本文對(duì)Web服務(wù)做分類(lèi)，每個(gè)Web服務(wù)都包含一個(gè)與之相對(duì)應(yīng)的WSDL文檔，因此對(duì)Web服務(wù)做分類(lèi)就是對(duì)WSDL文檔做分類(lèi)，而從WSDL文檔的定義當(dāng)中，文檔當(dāng)中所包含的操作能夠度量一個(gè)WSDL文檔的性質(zhì)，因此選擇其操作之間的相似度來(lái)度量WSDL文檔之間的相似度，然后通過(guò)分類(lèi)算法對(duì)其做分類(lèi)。

分類(lèi)的概念：分類(lèi)分析的目的是在給定其他變量的條件下對(duì)感興趣的未知變量值作出預(yù)測(cè)。數(shù)據(jù)分類(lèi)的目的在于根據(jù)新數(shù)據(jù)對(duì)象的屬性，將其分配到一個(gè)正確的類(lèi)別當(dāng)中。為進(jìn)行數(shù)據(jù)的分類(lèi)，首先需要建立一個(gè)分類(lèi)模型，用以描述預(yù)定的數(shù)據(jù)集，常用的分類(lèi)模型包括判別分類(lèi)及決策邊界模型、概率模型以及數(shù)模型，當(dāng)所建立的模型經(jīng)測(cè)試后達(dá)到了所要求的準(zhǔn)確率，便可以用其對(duì)未知目標(biāo)號(hào)的數(shù)據(jù)對(duì)象進(jìn)行分類(lèi)。分類(lèi)分析中的待分類(lèi)數(shù)據(jù)稱(chēng)為樣本、實(shí)例或?qū)ο?，為建立模型而被分析的?shù)據(jù)構(gòu)成訓(xùn)練數(shù)據(jù)集，其中的單個(gè)數(shù)據(jù)稱(chēng)為訓(xùn)練樣本[2]。

目前已有的分類(lèi)算法很多，以下介紹幾個(gè)常用的算法[2]：基于距離的分類(lèi)：首先是最短距離分類(lèi)，它的原理是歐氏距離公式，設(shè)c1，…，cm代表了n維空間Rn中的m個(gè)類(lèi)，如果類(lèi)ci能夠由其中某一代表向量（一個(gè)n維向量xi）來(lái)表示，xi描述了類(lèi)ci的中心，那么對(duì)于輸入向量y的分類(lèi)問(wèn)題可以根據(jù)y到xi（i=1，2，…，m）的距離來(lái)判斷。歐氏距離在分類(lèi)分析中被廣泛采用作為距離的尺度，其特點(diǎn)是簡(jiǎn)單容易被人接受。其次是最近鄰分類(lèi)算法：設(shè)c1，…，cm代表了n維空間Rn中的m個(gè)類(lèi)，給定包含了N個(gè)數(shù)據(jù)樣本的集合{x1，…，xn}，已知該集合中各樣本的先驗(yàn)分類(lèi)信息。對(duì)于任意輸入向量y，最近鄰分類(lèi)器將y劃分到y(tǒng)的最近鄰樣本所在的類(lèi)中。與最短距離分類(lèi)器相比，最近鄰分類(lèi)器并不考慮各類(lèi)的代表向量，而是在已知先驗(yàn)分類(lèi)信息的數(shù)據(jù)樣本中考查與輸入向量y之間具有最短距離的鄰居樣本，直接將最近鄰居樣本的分類(lèi)信息作為y的分類(lèi)信息。在基于距離的分類(lèi)之中還包括了k-最近鄰分類(lèi)，其算法如下：

輸入：

N：已知分類(lèi)信息的樣本個(gè)數(shù)

n：向量空間的維數(shù)

m：Rn中類(lèi)的個(gè)數(shù)

（si，sj）1≤i≤N：N個(gè)序偶對(duì)，其中si為第i個(gè)事先已知分類(lèi)信息的樣本，ji為si所屬的類(lèi)（1≤ji≤m）

K：最近鄰樣本的個(gè)數(shù)，也稱(chēng)為k-最近鄰分類(lèi)算法的階

y：待分類(lèi)的輸入量

輸出：

L：y的分類(lèi)信息。

步驟1令S={（si，sj）}，1≤i≤N

步驟2找到（x，j0），使得||x-y||=min||z-y||，（z，j）∈S

步驟3果k=1，則令l=j0，算法結(jié)束;

否則，初始化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）令I(lǐng)C（j0）=IC（j0）+1，S=S-{（x，j0）}

END FOR

步驟5令l=max{IC（i）}，1≤i≤m，算法結(jié)束

在上述算法中，歐式距離被作為定義“靠近”的尺度，而k選取不同的值，分類(lèi)的結(jié)果將會(huì)不同。最簡(jiǎn)單的形式是取k=1，但是這樣得到的分類(lèi)器相當(dāng)不穩(wěn)定，即變化性大，對(duì)數(shù)據(jù)過(guò)于敏感，因此很多時(shí)候通過(guò)提高k值以使預(yù)測(cè)更加一致，但是可能增大分類(lèi)的偏差。事實(shí)上，增大k值意味著“小胞體”可能并不小，被包含近來(lái)的樣本數(shù)據(jù)未必和輸入向量非?？拷?。K-最近鄰分類(lèi)方法容易編程實(shí)現(xiàn)，并且不需要優(yōu)化和訓(xùn)練;對(duì)于某些問(wèn)題，其分類(lèi)具有很高的精確度，可以和基于神經(jīng)網(wǎng)絡(luò)的方法相比;它可以直接擴(kuò)展到多分類(lèi)的情況，也是可以處理被分類(lèi)向量中殘缺值的情況，K-最近鄰分類(lèi)方法并不建立模型，而是依賴(lài)于把所有訓(xùn)練數(shù)據(jù)集中的樣本數(shù)據(jù)全部保存下來(lái)，基于此，把這種分類(lèi)方法稱(chēng)為“消極學(xué)習(xí)方法（或懶散學(xué)習(xí)方法）”。

本文主要采用基于距離的分類(lèi)方法中的K-最近鄰分類(lèi)算法來(lái)Web服務(wù)做分類(lèi)，使用該算法來(lái)衡量?jī)蓚€(gè)WSDL文檔之間的相似度，首先使用相似度的度量方法計(jì)算出兩個(gè)文檔當(dāng)中操作的相似度，之后采用該算法來(lái)計(jì)算兩個(gè)文檔之間的“距離”，當(dāng)兩個(gè)文檔之間的“距離”大于或等于某一個(gè)特定值的時(shí)候就說(shuō)它們相似，同時(shí)將其們歸為一類(lèi)。

1 Web服務(wù)描述信息的抽取和服務(wù)間的語(yǔ)義相似度

1.1 Web服務(wù)描述信息的抽取

定義Web服務(wù)的WSDL文檔主要包括下列元素：

·Types：數(shù)據(jù)類(lèi)型定義的容器，它使用某種類(lèi)型系統(tǒng)（一般地使用XML Schema中的類(lèi)型系統(tǒng)）。

·Message：通信消息的數(shù)據(jù)結(jié)構(gòu)的抽象類(lèi)型化定義。使用Types所定義的類(lèi)型來(lái)定義整個(gè)消息的數(shù)據(jù)結(jié)構(gòu)。

·Operation：對(duì)服務(wù)中所支持的操作的抽象描述，一般單個(gè)Operation描述了一個(gè)訪(fǎng)問(wèn)入口的請(qǐng)求/響應(yīng)消息對(duì)。

·PortType：對(duì)于某個(gè)訪(fǎng)問(wèn)入口點(diǎn)類(lèi)型所支持的操作的抽象集合，這些操作可以由一個(gè)或多個(gè)服務(wù)訪(fǎng)問(wèn)點(diǎn)來(lái)支持。

·Binding：特定端口類(lèi)型的具體協(xié)議和數(shù)據(jù)格式規(guī)范的綁定。

·Port：定義為協(xié)議/數(shù)據(jù)格式綁定與具體Web訪(fǎng)問(wèn)地址組合的單個(gè)服務(wù)訪(fǎng)問(wèn)點(diǎn)。

·Service：相關(guān)服務(wù)訪(fǎng)問(wèn)點(diǎn)的集合。

WSDL文檔中包含了這些元素，本文抽取WSDL文檔中的操作（Operation）作為原子服務(wù)，因?yàn)槊總€(gè)WSDL文檔中包含了大量的操作。在WSDL文檔定義好之后，我們將對(duì)操作中的輸入輸出等各項(xiàng)操作進(jìn)行抽取，例如在第2章的實(shí)例中，我們抽取input、output這兩個(gè)操作。因此通過(guò)先對(duì)WSDL文檔之間的操作分類(lèi)，用這個(gè)分類(lèi)的結(jié)果來(lái)衡量WSDL的相似度[10]，從而為Web服務(wù)的分類(lèi)奠定基礎(chǔ)[3-7]。

1.2 Web服務(wù)組件之間的語(yǔ)義相似度

要實(shí)現(xiàn)Web服務(wù)的自動(dòng)分類(lèi)，首先要對(duì)WSDL文檔中的操作進(jìn)行分類(lèi)，這是實(shí)現(xiàn)Web服務(wù)分類(lèi)的前提條件，也是實(shí)現(xiàn)服務(wù)分類(lèi)的基礎(chǔ)，同時(shí)也是實(shí)現(xiàn)服務(wù)分類(lèi)必不可少的。已有的相似度度量的方法中具有代表性的一個(gè)是文獻(xiàn)[3]，其描述如下：對(duì)一個(gè)文本文檔來(lái)說(shuō)，文檔當(dāng)中的相同文字出現(xiàn)的頻率是衡量文檔相似度最直觀的因素，在此我們不妨將文本文檔看成是語(yǔ)義包，同時(shí)將文檔當(dāng)中的文字看作語(yǔ)義元素。下面是幾個(gè)相關(guān)的定義：

定義1.直接引起人們關(guān)注的語(yǔ)義實(shí)體我們稱(chēng)作為語(yǔ)義包，記做Pi，語(yǔ)義的最小組織單位我們稱(chēng)之為語(yǔ)義元素，記為Ej。

根據(jù)實(shí)際應(yīng)用中的各種不同的情況，不同的語(yǔ)義實(shí)體都能夠被選作為語(yǔ)義包。比如，Web站點(diǎn)能夠被選作語(yǔ)義包，同時(shí)Web頁(yè)面則是Web站點(diǎn)的語(yǔ)義元素。在一個(gè)更好的粒度下，Web頁(yè)面是語(yǔ)義包，而文字是Web頁(yè)面的語(yǔ)義元素。通過(guò)包里語(yǔ)義元素的不同的情況，我們需要弄清語(yǔ)義元素之間的語(yǔ)義關(guān)系。我們用P={P1，P2，…，Pm}來(lái)表示一個(gè)語(yǔ)義包，用E={E1，E2，…，En}來(lái)表示包含在語(yǔ)義包P中的語(yǔ)義元素。Ei對(duì)Ej的支持我們用Ei→Ej來(lái)表示，其中i與j不相等;Ei對(duì)Ej的支持度我們用φ（Ei→Ej）來(lái)表示：

φ（Ei→Ej）=N（Ei∩Ej）/N（Ej）（1）

N（Ej）表示選取包含Ej語(yǔ)義包的概率，N（Ei∩Ej）表示選取中包含Ei又包含Ej的語(yǔ)義包的概率。很顯然，φ（Ei→Ej）不一定與φ（Ej→Ei）相等。

定義2.φ（Ei，Ej）叫做語(yǔ)義包P中語(yǔ)義元素Ei與Ej之間的親和度，其中：

φ（Ei，Ej）=N（Ei∩Ej）/N（Ei∪Ej）（2）

φ（Ei，Ej）稱(chēng)為Ei與Ej之間的語(yǔ)義距離。

定義3.為了實(shí)現(xiàn)Web服務(wù)組件之間的相似度的度量，首先進(jìn)行下列符號(hào)意義的說(shuō)明：

（1）OPi：這表示某一個(gè)WSDL文檔中的第i個(gè)操作;

（2）OPi∩OPj：表示對(duì)某兩個(gè)WSDL文檔中的操作取交集，也即是求兩個(gè)文檔中相同的操作（i=1，2，3…）;

（3）OPi∪OPj：表示對(duì)某兩個(gè)WSDL文檔中的操作取并集，也即是求兩個(gè)文檔中所有的操作數(shù)（j=1，2，3…）;

（4）N（OPi∩OPj）：表示求取某兩個(gè)WSDL文檔中所有語(yǔ)義相同或相似的操作總數(shù);

（5）N（OPi∪OPj）：表示求取某兩個(gè)WSDL文檔中所有的操作數(shù);

（6）Sim（OPi，OPj）：表示包含i個(gè)操作的WSDL文檔與包含j個(gè)操作的WSDL文檔之中操作的語(yǔ)義相似度。

下面定義WSDL文檔中操作之間的語(yǔ)義相似度的度量標(biāo)準(zhǔn)。

定義4.WSDL文檔中操作之間的語(yǔ)義相似度的度量標(biāo)準(zhǔn)定義為

Sim（WSi，WSj）=N（OPi∩OPj）/N（OPi∪OPj）（3）

通過(guò)定義3明確算法中的各個(gè)符號(hào)所表示的具體意思，定義4中的算法中輸入的是不同的WSDL文檔中相同的操作數(shù)，以及兩個(gè)WSDL文檔中所有的操作數(shù)目，通過(guò)它們的比值，將得到操作之間的相似度。

再給出定義4中的公式（3）一些性質(zhì)：

（1）Sim（OPi，OPi）=1;

（2）Sim（OPi，OPj）=Sim（OPj，OPi）。

在本文中將采取這種方法度量WSDL中操作的相似度，基于WSDL操作之間相似度度量方法，進(jìn)一步可對(duì)WSDL文檔進(jìn)行分類(lèi)，是本文中研究Web服務(wù)分類(lèi)的關(guān)鍵問(wèn)題和核心技術(shù)。

1.3 Web服務(wù)之間的語(yǔ)義貼近度

第3.2節(jié)中，介紹了Web服務(wù)組建（操作）之間的語(yǔ)義貼近度，下面介紹WSDL文檔之間的語(yǔ)義相似度。WSDL之間的相似度用來(lái)度量?jī)蓚€(gè)WSDL文檔之間的相似程度，第3.2節(jié)主要講述了對(duì)從WSDL文檔中抽取的操作的語(yǔ)義相似度，本節(jié)以第3.2節(jié)為基礎(chǔ)，第3.2節(jié)主要介紹了WSDL文檔中組件（操作）之間的語(yǔ)義相似度，但是只有操作之間的語(yǔ)義相似度是不能解決WSDL文檔之間相似度的度量的，本節(jié)主要是在第3.2節(jié)已有的工作基礎(chǔ)之上來(lái)進(jìn)行Web服務(wù)之間的語(yǔ)義相似度的度量工作。為了討論的方便，首先定義度量WSDL文檔之間相似度工作的相關(guān)符號(hào)。

定義5.

（1）WSi：表示第i個(gè)Web服務(wù)文檔（即WSDL文檔），在該文檔中包含了n個(gè)操作，這其中的操作依然用OP來(lái)表示，同樣操作之間的相似度用Sim（OPi，OPj）來(lái)表示，操作之間的相似度已知;

（2）S（WSi，WSj）：表示第i個(gè)文檔與第j個(gè)文檔之間的相似度;

（3）Counti-j：表示一個(gè)初值為一的計(jì)數(shù)器，它記錄了第i個(gè)文檔與第j個(gè)文檔當(dāng)中所包含的操作之間進(jìn)行的相似度度量所計(jì)算的次數(shù)。

下面我們給出計(jì)算的公式：

S（WSi，WSj）={∑Sim（OPi，OPj）}/Counti-j（4）

當(dāng)Sim（OPi，OPj）≥ε（ε的值給定）時(shí)，如果S（WSi，WSj）≥ε（ε的值也是給定），那么我們就說(shuō)WSi與WSj相關(guān)（也就是相似）。

在該算法當(dāng)中，OPi∈WSi，OPj∈WSj;i與j都是正整數(shù)，都從1開(kāi)始計(jì)數(shù)。Counti-j的初始值置為1，操作之間的相似度度量算法每進(jìn)行一次，計(jì)數(shù)器自加一次。

2 基于Web服務(wù)間語(yǔ)義相似度的服務(wù)分類(lèi)

2.1 基于Web服務(wù)語(yǔ)義相似度的Web服務(wù)分類(lèi)算法

計(jì)算出Web服務(wù)WSi與WSj之間的相似度是本章研究的核心，本章將用到K-最近鄰分類(lèi)算法的改進(jìn)算法，稱(chēng)之為WS-KNN算法，該算法吸取了KNN分類(lèi)算法的思想，但是在WS-KNN算法中，用待分類(lèi)的WS文檔與已知分類(lèi)信息的WS文檔之間的相似度與從實(shí)驗(yàn)中學(xué)習(xí)出來(lái)的度量值作比較，該算法的基本思想如下：

用已知分類(lèi)信息的WS文檔及待分類(lèi)的WS文檔作為算法的輸入，要求輸出待分類(lèi)的WS文檔的分類(lèi)信息。在WS-KNN算法中，首先將已知分類(lèi)信息的WS文檔和該文檔的類(lèi)別分別對(duì)應(yīng)起來(lái)并以一個(gè)序偶對(duì)的方式存放在數(shù)組S中，然后使用一個(gè)兩重循環(huán)將已知的待分類(lèi)文檔和樣本文檔之間相似度的值S（WSj，WSi）存放在一個(gè)二維數(shù)組Sji中，在Sji大于等于已知的度量值ε的基礎(chǔ)上，分別把待分類(lèi)的文檔WSj歸為與之進(jìn)行相似度計(jì)算的WSi文檔所屬的類(lèi)別Cn中，如果Cn相同，也就是這些WSi屬于同一個(gè)類(lèi)別，理所當(dāng)然將WSj歸到類(lèi)Cn中;如果Cn不盡相同，那么取大多數(shù)WSi所屬的類(lèi)別Cr作為WSj所屬的類(lèi)，分類(lèi)算法結(jié)束。

對(duì)WS-KNN算法的描述如下：

算法1

輸入：

N：已知分類(lèi)信息的樣本個(gè)數(shù)

WSi：已知分類(lèi)信息的WS文檔

WSj：待分類(lèi)的WS文檔

C：已知分類(lèi)信息文檔所屬類(lèi)別的集合

m：已知類(lèi)的數(shù)量

ε：從實(shí)驗(yàn)中所得出的分類(lèi)信息度量值

K：輸入的待分類(lèi)的WS文檔的個(gè)數(shù)

S（WSj，WSi）：已知的待分類(lèi)文檔和樣本文檔之間相似度的值

輸出：

WSj在C中所屬的類(lèi)別

步驟如下：

步驟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為一個(gè)定值）

WSj∈Cr

ELSE WSj∈Cr（Cr為大多數(shù)WSi所屬的類(lèi)別）

END IF 算法結(jié)束

對(duì)輸入的待分類(lèi)的WS文檔，使用第3章中的相似度度量方法與已知分類(lèi)信息的WSi進(jìn)行相似度度量，可以得出S（WSi，WSj）的值（1≤i≤K，1≤j≤N），然后與已知的分類(lèi)信息的度量值ε做比較，如果S（WSi，WSj）≥ε，則稱(chēng)WSi與WSj相似，我們將WSi與WSj中大多數(shù)相似的文檔的類(lèi)別作為WSi的類(lèi)。

2.2 應(yīng)用實(shí)例

下面使用一個(gè)實(shí)例來(lái)綜合說(shuō)明一下我們工作的正確性和可行性。

例5：現(xiàn)有旅游服務(wù)和銷(xiāo)售代理兩個(gè)類(lèi)別，分別記為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中有樣本W(wǎng)S3，WS3中包含了操作{search travel information，sale house，sale computer}，現(xiàn)有待分類(lèi)的WS文檔WS4={search travel information，select guide，sale house}，度量值ε=0.400。

為了計(jì)算的方便，分別記buy gift，book ticket，search travel information，select guide，sale house，sale computer為OP1，OP2，OP3，OP4，OP5，OP6。

根據(jù)定義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，

根據(jù)定義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;

進(jìn)而，根據(jù)算法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都是類(lèi)Ctravel中的樣本，WS3是Csale中的樣本，而容易看出，WS4與WS1、WS2最相似，故而將WS4歸為Ctravel中。

首先利用定義4中的公式（3）計(jì)算出了WSDL文檔之間操作的相似度，基于此利用公式（4）計(jì)算出了待分類(lèi)的WSDL文檔與已知分類(lèi)信息之間的相似度，然后利用算法1得到了待分類(lèi)的WSDL文檔的分類(lèi)信息。通過(guò)實(shí)例，能看出，本文提出的方法能夠有效地實(shí)現(xiàn)Web服務(wù)的分類(lèi)。

即使已知分類(lèi)信息的文檔很多、待分類(lèi)的文檔的數(shù)量也很大的時(shí)候，本文中算法1只要2個(gè)嵌套循環(huán)就能實(shí)現(xiàn)Web服務(wù)的分類(lèi)，算法的時(shí)間復(fù)雜度為O（n2），這與“人以類(lèi)聚、物以群分”的分類(lèi)思想一致，也具有較高的效率。

3 總結(jié)

本文著重介紹了KNN算法的改進(jìn)算法WS-KNN算法，基于這些現(xiàn)有的方法、遵循已有的Web服務(wù)標(biāo)準(zhǔn)協(xié)議，以WSDL中的服務(wù)描述信息為載體，討論基于語(yǔ)義的Web服務(wù)相似度度量標(biāo)準(zhǔn)及響應(yīng)的服務(wù)分類(lèi)算法，最終實(shí)現(xiàn)Web服務(wù)的分類(lèi)。

本文提出和實(shí)現(xiàn)的服務(wù)分類(lèi)方法能很好的避免已有的服務(wù)分類(lèi)工作的各種不足，服務(wù)之間的語(yǔ)義相關(guān)性基于大量的歷史數(shù)據(jù)學(xué)習(xí)而得到，有自動(dòng)分類(lèi)的效果，同時(shí)分類(lèi)的方法簡(jiǎn)單可行、實(shí)現(xiàn)方便、效率較高。本文的分類(lèi)方法以傳統(tǒng)的K-NN分類(lèi)算法為基礎(chǔ)，而基于所提出的語(yǔ)義相似度對(duì)其進(jìn)行無(wú)縫的改進(jìn)，具有一定的實(shí)用價(jià)值。

【參考文獻(xiàn)】

[1]岳昆，王曉玲，周傲英.Web服務(wù)核心支撐技術(shù)：研究綜述，軟件學(xué)報(bào)，2004，15（3）：428-442.

[2]劉惟一，李維華，岳昆.智能數(shù)據(jù)分析，科學(xué)出版社，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.