一種領(lǐng)域自適應(yīng)的Web服務(wù)分類(lèi)方法?

彭密 趙恒

（武漢數(shù)字工程研究所 武漢 430000）

1 引言

經(jīng)典的基于機(jī)器學(xué)習(xí)的分類(lèi)應(yīng)用過(guò)程，通過(guò)使用某個(gè)領(lǐng)域（源域，Source Domain）的數(shù)據(jù)集訓(xùn)練模型，再對(duì)目標(biāo)域（Target Domain）分類(lèi)［1］。該分類(lèi)方法有效的前提是目標(biāo)域數(shù)據(jù)集分布與源數(shù)據(jù)集分布相似。如果實(shí)際應(yīng)用中目標(biāo)域數(shù)據(jù)集與源域數(shù)據(jù)集的分布差異較大時(shí)，分類(lèi)準(zhǔn)確性就會(huì)下降［2～3］。針對(duì)上述問(wèn)題，本文結(jié)合KNN（K-NearestNeighbor）算法惰性學(xué)習(xí)的特點(diǎn)［4］，設(shè)計(jì)和實(shí)現(xiàn)了一種Web服務(wù)分類(lèi)方法，能夠在運(yùn)行時(shí)對(duì)輸入數(shù)據(jù)進(jìn)行篩選復(fù)用，使分類(lèi)結(jié)果反饋到下一次分類(lèi)計(jì)算，通過(guò)不斷累積樣本，動(dòng)態(tài)調(diào)整源域數(shù)據(jù)分布，從而達(dá)到領(lǐng)域服務(wù)自適應(yīng)分類(lèi)和提高分類(lèi)準(zhǔn)確性的目的。

2 相關(guān)研究工作

2.1 Web服務(wù)分類(lèi)

目前Web服務(wù)的實(shí)現(xiàn)方式一般有兩種，一種基于SOAP的Web服務(wù)，采用WSDL結(jié)構(gòu)化文檔描述，提供的信息豐富；一種是基于HTTP的輕量級(jí)服務(wù)，一般被稱為Web API，通常沒(méi)有或者只有簡(jiǎn)單的描述信息，如REST API，至今沒(méi)有標(biāo)準(zhǔn)的接口描述文檔［5］，有研究提出過(guò) WADL［6］等用于基于RESTful的Web API接口描述的規(guī)范，但未能推廣［7］?，F(xiàn)在對(duì)RESTful的描述由提供者自已定義，比如ProgrammableWeb網(wǎng)站收錄的服務(wù)描述就由自然語(yǔ)言短文本組成。

由于輕量級(jí)RESTful服務(wù)在互聯(lián)網(wǎng)行業(yè)的大規(guī)模應(yīng)用，具有很高的實(shí)用價(jià)值，因此RESTful的服務(wù)分類(lèi)是現(xiàn)在服務(wù)分類(lèi)研究的熱點(diǎn)。目前最常見(jiàn)的分類(lèi)是根據(jù)服務(wù)描述文檔進(jìn)行分類(lèi)，由于部分RESTful服務(wù)使用簡(jiǎn)單文本描述，因此，這一類(lèi)RESTful服務(wù)分類(lèi)問(wèn)題，通常直接轉(zhuǎn)化為簡(jiǎn)單文本分類(lèi)問(wèn)題處理。

2.2 基于機(jī)器學(xué)習(xí)的文本分類(lèi)算法比較

目前常用的基于機(jī)器學(xué)習(xí)的文本分類(lèi)算法有樸素貝葉斯、SVM（Support Vector Machine）和KNN算法等［8］。這三種經(jīng)典的分類(lèi)算法各自具有不同的特點(diǎn)，如表1。

表1 三種算法的優(yōu)缺點(diǎn)

由于基于KNN的文本算法基于實(shí)例分類(lèi)的特點(diǎn)使基于樣本的自適應(yīng)更易實(shí)現(xiàn)，所以本文的研究基于KNN進(jìn)行。

2.3 KNN算法

KNN算法基于距離相似度分類(lèi)。KNN算法過(guò)程如下:首先，對(duì)于一個(gè)待分類(lèi)文本，計(jì)算其與已標(biāo)記實(shí)例數(shù)據(jù)集中每個(gè)文本的距離，找出K個(gè)距離最近的已標(biāo)記訓(xùn)練文本，然后在這個(gè)基礎(chǔ)上對(duì)每一個(gè)待分類(lèi)文本投票；投票過(guò)程為，有K個(gè)訓(xùn)練文本中，如果屬于A類(lèi)的訓(xùn)練文本最多，就認(rèn)為分類(lèi)結(jié)果為A類(lèi)。KNN利用距離/相似度分類(lèi)的形式化表示為

其中c是訓(xùn)練集中的類(lèi)別，di，Sim(dx，di)為dx和di之間的相似度［10］；knndoc是指在訓(xùn)練集K個(gè)最相似（近鄰）訓(xùn)練文本所組成的訓(xùn)練文本子集；di∈knndoc表示di為訓(xùn)練文本子集中的一個(gè)訓(xùn)練文本；g(di，cj)的取值為1或者0，代表di是否屬于cj類(lèi)，當(dāng)訓(xùn)練文本di屬于cj類(lèi)時(shí)取1，否則取0。為如果在dx與最相似的k文本中屬于cj類(lèi)的訓(xùn)練文本最多，則認(rèn)為dx屬于cj類(lèi)，此時(shí)f(dx，cj)等于1，否則不屬于，f(dx，cj)等于0。

KNN算法近鄰計(jì)算方法通?；诳臻g坐標(biāo)系的距離計(jì)算?，F(xiàn)有的KNN距離計(jì)算有很多種，常用的有歐式矩離（Eucledian Distance）和曼哈頓距離（Manhattan Distance），余弦相似度（Cosine Similarity）等［11］。

3 自適應(yīng)Web服務(wù)分類(lèi)方法設(shè)計(jì)

在KNN算法中，首先將待分類(lèi)文本dx與訓(xùn)練集所有文本分別計(jì)算，計(jì)算結(jié)果相似度數(shù)組使用similarity［］表示，得到相似度排序之后選取其中的K個(gè)對(duì)應(yīng)的文本做投票分類(lèi)［12］，如果dx屬于cj類(lèi)，結(jié)果表示為f(dx，cj)值為1，否則為0。如果待分類(lèi)文本與訓(xùn)練集文本詞頻、詞組的差別較大，相似度計(jì)算可能不準(zhǔn)確，投票也可能不準(zhǔn)確。解決方法是在樣本上做出反饋和調(diào)整:由于KNN采用惰性學(xué)習(xí)，KNN每一次運(yùn)行時(shí)對(duì)目標(biāo)與測(cè)試樣本的相似度計(jì)算，如果在每一次計(jì)算時(shí)通過(guò)不斷對(duì)KNN的訓(xùn)練樣本調(diào)整，可以從樣本上實(shí)現(xiàn)自適應(yīng)。

調(diào)整訓(xùn)練集的目的是將測(cè)試集與訓(xùn)練集的數(shù)據(jù)分布、特征盡量靠近，這樣在分類(lèi)計(jì)算的時(shí)候，相似度最高的K個(gè)樣本就會(huì)更準(zhǔn)確。

為保證訓(xùn)練集在加入新樣本后的準(zhǔn)確性，在分類(lèi)的基礎(chǔ)上，需要對(duì)加入樣本的分類(lèi)的效果進(jìn)行評(píng)估，評(píng)估標(biāo)準(zhǔn)為最大得票數(shù)的數(shù)量是否大于某個(gè)預(yù)設(shè)值。在dx已分類(lèi)為cj類(lèi)的前提下，分類(lèi)票數(shù)為統(tǒng)計(jì)cj類(lèi)得到的票數(shù)。di屬于K個(gè)最相似文本Knndoc中的一個(gè)樣本，Sim(dx，di)表示dx與di的相似度值；g(di，cj)解釋為di如果屬于cj類(lèi)則值為1， 否 則 為 0， 所 以 票 數(shù) 表 示 為閾值使用 threshold 表示，如果得票數(shù)大于這個(gè)閾值，則認(rèn)為這是一個(gè)可復(fù)用的樣本，此時(shí)h(dx)值為1，否則，就不將其作為可復(fù)用樣本，h(dx)值為0。

由此，本文對(duì)普通的基于KNN的文本分類(lèi)方法進(jìn)行了改進(jìn)，通過(guò)在KNN分類(lèi)的基礎(chǔ)上，增加數(shù)據(jù)篩選和復(fù)用的過(guò)程。在基于式（1）的基礎(chǔ)上改進(jìn)，分類(lèi)和復(fù)用算法形式化表示為式（2）:

分類(lèi)流程如圖1分類(lèi)流程圖所示。

未分類(lèi)服務(wù)文本dx作為輸入開(kāi)始，預(yù)處理得到此服務(wù)文本的詞頻向量，并與所有訓(xùn)練集文本的詞頻向量作1∶1相似度計(jì)算，得到相似度數(shù)組Similarity［］；從Similarity數(shù)組中找到K個(gè)最大的相似度值，并找到這K個(gè)相似度所對(duì)應(yīng)的訓(xùn)練服務(wù)文本；K個(gè)文本中，統(tǒng)計(jì)K個(gè)文本屬于每一個(gè)類(lèi)別的數(shù)量，dx的分類(lèi)為統(tǒng)計(jì)量最高的類(lèi)cj。服務(wù)文本dx分類(lèi)確定以后，判斷dx是否滿足可復(fù)用的條件，條件為dx的分類(lèi)票數(shù)是否大于設(shè)定的閾值threshold，如果大于，則可以復(fù)用，將dx插入到訓(xùn)練樣本集中；否則不可復(fù)用。最后無(wú)論結(jié)果如何，都要輸出分類(lèi)的結(jié)果cj，此時(shí)分類(lèi)過(guò)程結(jié)束。

圖1 分類(lèi)流程圖

3.1 獲取文本間相似度

計(jì)算文本間相似度是基于KNN分類(lèi)的第一步。本文對(duì)于文本間相似度的計(jì)算采用百度短文本相似度計(jì)算處理。所以，調(diào)用百度短文本相似度計(jì)算接口，將描述服務(wù)的兩個(gè)短文本作為輸入，就可以得到返回值為兩個(gè)短文本的相似度。

基于KNN的分類(lèi)中，待分類(lèi)文本需要與訓(xùn)練集中每一項(xiàng)樣本數(shù)據(jù)進(jìn)行相似度計(jì)算，得到一個(gè)相似度數(shù)組:如果訓(xùn)練集有N個(gè)文本樣本，就要調(diào)用N次接口，得到一個(gè)長(zhǎng)度為N相似度數(shù)組。

3.2 根據(jù)文本相似度的投票與分類(lèi)

待分類(lèi)數(shù)據(jù)分別與所有已標(biāo)記訓(xùn)練集中數(shù)據(jù)計(jì)算后，相似度計(jì)算結(jié)果分別保存在數(shù)組中。投票即從這些保存有相似度的數(shù)組中找到K個(gè)最大相似度的過(guò)程。

具體投票過(guò)程如下:假設(shè)有已標(biāo)記訓(xùn)練數(shù)據(jù)集合為 A∪B ，有待分類(lèi)數(shù)據(jù)集 D；Ai∈A，Bj∈B，dx∈D ；dx分別與 Ai，Bj計(jì)算相似度（1≤i≤N，1≤i≤M ，N為A的數(shù)據(jù)量，M為B的數(shù)據(jù)量）；計(jì)算結(jié)果存放在數(shù)組Similarity［N+M］中。在Similarity［N+M］取出K個(gè)最大的相似度形成數(shù)組maxSimilarity［K］，結(jié)合式（1），式中knndoc就是這K個(gè)最大值對(duì)應(yīng)的數(shù)據(jù)組成的集合，也就是maxSimilarity［K］中數(shù)據(jù)對(duì)應(yīng)的A和B的子集合；knndoc中數(shù)據(jù)項(xiàng)對(duì)應(yīng)的與 dx的相似度maxSimilarity［K］為式（1）中的 Sim(dx，di)；di∈knndoc表示 di為訓(xùn)練文本子集knndoc中的一個(gè)訓(xùn)練文本；g(di，ci)的取值為1或者0，當(dāng)訓(xùn)練文本di屬于cj類(lèi)時(shí)取1，否則取0。最后找出這K個(gè)最大相似度子集對(duì)應(yīng)的訓(xùn)練文本中屬于最多的一個(gè)類(lèi)別，比如maxSimilarity［K］中，對(duì)應(yīng)的訓(xùn)練文本屬于A類(lèi)的數(shù)量為a，屬于B類(lèi)的數(shù)量為b（a+b=k）。如果a＞b，則 dx∈cA表示為dx屬于A類(lèi)，否則dx∈cb，表示dx屬于B類(lèi)。

對(duì)于K值的取值方法，本文采用最常用的多次驗(yàn)證求值法［13］。具體為，K取值從1開(kāi)始取單數(shù)，K值不斷的增加，比如K分別取1、3、5、7…，驗(yàn)證K取不同值時(shí)分類(lèi)性能，取分類(lèi)穩(wěn)定之后的第一個(gè)值。

3.3 樣本篩選復(fù)用

經(jīng)過(guò)投票，確定了具體的分類(lèi)，隨后需要對(duì)已分類(lèi)文本篩選。篩選即選取具有超過(guò)設(shè)定閾值的測(cè)試樣本插入到訓(xùn)練樣本，所以需要定義閾值。

閾值定義為得票率，得票率超過(guò)80%則認(rèn)為分類(lèi)是正確的，所以閾值設(shè)定為分類(lèi)得到超過(guò)80%的投票。計(jì)算分類(lèi)正確可能性可直接統(tǒng)計(jì)票數(shù)比率，如分類(lèi)結(jié)果dx∈A，當(dāng)K取7時(shí)，得到的票數(shù)分別是A=5，B=2，此時(shí)結(jié)果得票率為5/7≈71%。

經(jīng)過(guò)得票率計(jì)算，如果dx∈A的得票率為71%，結(jié)果不符合本文對(duì)閾值的定義就不對(duì)這種數(shù)據(jù)進(jìn)行任何額外操作；而如果當(dāng)K取7時(shí)，得到的票數(shù)分別是A=6，B=1，那么得票率為6/7≈85%，超過(guò)閾值，則將Ck插入A集合中，形成新的集合，表示為A=AUCk，A的數(shù)據(jù)量由N變?yōu)镹+1。

由于訓(xùn)練集A已經(jīng)更新，在接下來(lái)的一次對(duì)dx+1的分類(lèi)計(jì)算時(shí)，對(duì)實(shí)例比對(duì)的時(shí)候，就不再是對(duì)原來(lái)A中的N個(gè)數(shù)據(jù)進(jìn)行對(duì)比，而是對(duì)N+1個(gè)數(shù)據(jù)對(duì)比。對(duì)數(shù)據(jù)集D的數(shù)據(jù)di，(i=1，2…I)進(jìn)行和上述dx相同的篩選和復(fù)用過(guò)程為完整的分類(lèi)過(guò)程。

隨著 di，i∈[1，I]增量的輸入，A集合的數(shù)據(jù)持續(xù)增加。由于目標(biāo)域數(shù)據(jù)的擴(kuò)充，源域A，B分布與目標(biāo)域D的分布會(huì)越來(lái)越接近，正確找到的K個(gè)最相似的樣本可能性更高，投票的正確性就越高，分類(lèi)的準(zhǔn)確率就有可能更高。

4 實(shí)驗(yàn)與驗(yàn)證

實(shí)驗(yàn)數(shù)據(jù)以https://www.programmableweb.com/網(wǎng)站上的REST服務(wù)描述文本作為數(shù)據(jù)源。從數(shù)據(jù)中隨機(jī)選取了其中的兩大類(lèi)，一共180個(gè)不同的服務(wù)接口作為數(shù)據(jù)，其中作為訓(xùn)練集的每一個(gè)大類(lèi)包括60個(gè)服務(wù)，一共有120個(gè)服務(wù)；剩下的60個(gè)服務(wù)作為服務(wù)測(cè)試集，具體如表2所示。

表2 數(shù)據(jù)統(tǒng)計(jì)列表

通過(guò)使用兩種不同分類(lèi)方法在基于以上得到的相似度的情況下對(duì)REST服務(wù)分類(lèi)；兩種方法分別是基于普通KNN的服務(wù)分類(lèi)和本文提出的自適應(yīng)KNN服務(wù)分類(lèi)方法。

實(shí)驗(yàn)以分類(lèi)正確率和查全率作為判斷依據(jù)。預(yù)期的結(jié)果為相同條件下，采用本文方法的Web服務(wù)分類(lèi)正確率和查全率高于或等于作為對(duì)比組的普通服務(wù)分類(lèi)方法。

在正式開(kāi)始實(shí)驗(yàn)之前，應(yīng)首先找到最優(yōu)K值，實(shí)驗(yàn)中K值由多次驗(yàn)證求值法找到最優(yōu)K值。測(cè)試數(shù)據(jù)為表2中的數(shù)據(jù)測(cè)試Mapping分類(lèi)查全率，基于普通KNN算法。選擇過(guò)程如表3所示。

表3 K值與性能統(tǒng)計(jì)

根據(jù)表3統(tǒng)計(jì)結(jié)果，K取7時(shí)具有穩(wěn)定的分類(lèi)效果，所以認(rèn)為本實(shí)驗(yàn)中，K是最優(yōu)的K值，所以接下來(lái)的實(shí)驗(yàn)K值取7。

以測(cè)試服務(wù)集中屬于Map類(lèi)的測(cè)試服務(wù)“Air-Map Status API”為例，實(shí)驗(yàn)具體過(guò)程如下。

1）本示例目標(biāo)是要對(duì)AirMap Status API分類(lèi)，判斷是Map服務(wù)還是Music服務(wù)。

本例中AirMap Status API的服務(wù)描述為自然語(yǔ)言短文本形如:The AirMap Pilot REST API allows developers to access and integrate…

2）以AirMap Status API服務(wù)為例，把服務(wù)文檔進(jìn)行清洗，主要是刪除多余符號(hào)，比如空格、換行符，標(biāo)點(diǎn)符號(hào)，介詞，不標(biāo)準(zhǔn)的符號(hào)等。

3）調(diào)用百度AI提供的接口（http://ai.baidu.com/tech/nlp/simnet）計(jì)算百度相似度，輸入為＜Air-Map Status API描述文本，測(cè)試訓(xùn)練文本 i＞，i為訓(xùn)練文本在訓(xùn)練集中的序號(hào)。

通過(guò)對(duì)生成的AirMap詞頻向量＜AirMap，airspace，API，developers，pilots，retrieving，access…＞，＜4，2，2，2，2，2，1…＞與訓(xùn)練集的詞頻向量作相似度計(jì)算。得到的相似度作為返回結(jié)果存放在總長(zhǎng)度為240的相似度數(shù)組Similarity［M+N］中。

4）取出以上相似度數(shù)組Similarity［M+N］中，相似度最高的7個(gè)（K=7）數(shù)據(jù)maxSimilarity［K］，分別為｛0.9614，0.9501，0.9454，0.9012，0.9011，0.8721，0.8620｝，而相似度與文檔分類(lèi)分別對(duì)應(yīng)的集合為｛＜19，Map＞，＜42，Map＞，＜5，Map＞，＜17，Map＞，＜60，Map＞，＜51，Map＞，＜94，Music＞｝，所以，根據(jù)投票結(jié)果，其中6票為Map，1票為Music，根據(jù)多數(shù)票的結(jié)果，AirMap Status API屬于Map類(lèi)。

5）最后判斷是否復(fù)用:AirMap Status API已經(jīng)正確分類(lèi)為Map類(lèi)，投票數(shù)為6:1，根據(jù)復(fù)用閾值（本文取80%）的計(jì)算，6/7＞80%，所以將AirMap Status API插入到訓(xùn)練集中的Map類(lèi)中。

6）此時(shí)訓(xùn)練集由原來(lái)的120個(gè)變?yōu)榱?21個(gè)，新增了AirMap Status API服務(wù)作為訓(xùn)練集，在下一次的對(duì)其他服務(wù)的計(jì)算中，新的訓(xùn)練集就可能發(fā)揮作用。

對(duì)本文60個(gè)測(cè)試服務(wù)執(zhí)行上述2）～5）同樣的過(guò)程，得到結(jié)果如下:

從數(shù)據(jù)可以看出，本次實(shí)驗(yàn)針對(duì)的是二分類(lèi)問(wèn)題。分類(lèi)結(jié)果只有兩種，Mapping類(lèi)或者M(jìn)usic類(lèi)。其中Mapping和Music的訓(xùn)練數(shù)據(jù)各60條，總共120條。而測(cè)試數(shù)據(jù)分別包含Mapping類(lèi)數(shù)據(jù)30條和Music數(shù)據(jù)30條，測(cè)試數(shù)據(jù)總共60條。

結(jié)果統(tǒng)計(jì)如表4、表5。

表4 普通方法測(cè)試結(jié)果

表5 本文方法測(cè)試結(jié)果

對(duì)比組為基于普通KNN的服務(wù)分類(lèi)方法，實(shí)驗(yàn)組為基于本文方法的服務(wù)分類(lèi)方法。兩種方法唯一區(qū)別在于本文第3節(jié)中提到的投票與分類(lèi)中，樣本篩選復(fù)用的過(guò)程實(shí)現(xiàn)不同。

實(shí)驗(yàn)結(jié)果表4為基于普通KNN方法的服務(wù)分類(lèi)統(tǒng)計(jì)，表5為采用本方法的服務(wù)分類(lèi)統(tǒng)計(jì)。通過(guò)兩表對(duì)比，首先是對(duì)于Mapping和Music類(lèi)的平均正確率有所提高，提高大約3%；然后對(duì)于這兩種類(lèi)的平均查全率也提高了大約3%。

通過(guò)結(jié)果來(lái)看，針對(duì)同樣的數(shù)據(jù)，使用本文方法比使用普通KNN方法分類(lèi)的準(zhǔn)確率更高，兩種方法唯一的不同是計(jì)算的時(shí)候樣本集是否變化，如果沒(méi)有變化，準(zhǔn)確率和查全率應(yīng)該完全一樣，顯然條件相同的情況下動(dòng)態(tài)調(diào)整樣本影響到了分類(lèi)準(zhǔn)確率。

本次實(shí)驗(yàn)結(jié)果符合預(yù)期，同時(shí)結(jié)合本文3.2節(jié)中關(guān)于領(lǐng)域自適應(yīng)的分析，本文通過(guò)將樣本篩選復(fù)用，實(shí)現(xiàn)了自適應(yīng)服務(wù)分類(lèi)，達(dá)到提高服務(wù)分類(lèi)性能的目的。

5 結(jié)語(yǔ)

本文將KNN算法與Web服務(wù)分類(lèi)結(jié)合，通過(guò)動(dòng)態(tài)復(fù)用目標(biāo)域數(shù)據(jù)到源域數(shù)據(jù)集，調(diào)整源域數(shù)據(jù)分布，解決了由于源域和目標(biāo)域分布差異過(guò)大而導(dǎo)致的服務(wù)分類(lèi)準(zhǔn)確性下降的問(wèn)題。本文基于樸素KNN實(shí)現(xiàn)，計(jì)算復(fù)雜度上仍存在改進(jìn)空間，后續(xù)工作可以從減少計(jì)算復(fù)雜度方面改進(jìn):結(jié)合G-Tree［14］、V-Tree等優(yōu)化算法，對(duì)詞頻向量建立搜索樹(shù)，減少搜索計(jì)算量，以改善服務(wù)分類(lèi)計(jì)算過(guò)多的問(wèn)題。