劉 鋒，鄒臣嵩，崔 煒

(1.廣東松山職業(yè)技術(shù)學(xué)院電氣工程學(xué)院,廣東 韶關(guān) 512126；2.廣東松山職業(yè)技術(shù)學(xué)院信息與現(xiàn)代教育技術(shù)中心,廣東 韶關(guān) 512126)

0 引 言

隨著當(dāng)前社會云計(jì)算與大數(shù)據(jù)技術(shù)的飛速發(fā)展，越來越多的企業(yè)和組織將大數(shù)據(jù)應(yīng)用部署到云平臺以供調(diào)用。由于大數(shù)據(jù)的服務(wù)選擇是長期的、海量的、瞬息變化的，但傳統(tǒng)服務(wù)選擇大多只考慮服務(wù)選擇執(zhí)行階段的性能，即選擇服務(wù)的瞬時(shí)性能，而忽略了大數(shù)據(jù)環(huán)境的的不穩(wěn)定性，顯然傳統(tǒng)方法已經(jīng)無法滿足現(xiàn)階段的服務(wù)選擇需求。

目前，許多國內(nèi)外專家在大數(shù)據(jù)環(huán)境下從事各種選擇算法優(yōu)化并將其優(yōu)化算法與企業(yè)應(yīng)用相整合的研究，且取得了相應(yīng)的成果，但還存在一定的不足。為解決現(xiàn)階段大數(shù)據(jù)環(huán)境下的服務(wù)選擇問題，考慮到服務(wù)選擇是一個(gè)長期優(yōu)化的過程，在這過程中，由于大數(shù)據(jù)環(huán)境的高動(dòng)態(tài)性，服務(wù)質(zhì)量時(shí)刻在發(fā)生變化，即需要在服務(wù)選擇過程中，保障其性能最優(yōu)，用戶粘合度最高。但在服務(wù)選擇過程中，由于各方面因素的制約，用戶不能調(diào)用所有服務(wù)，且在規(guī)定時(shí)間內(nèi)用戶對服務(wù)的選擇次數(shù)也受限制。基于服務(wù)選擇過程中用戶對服務(wù)的不確定性與片面性，本文提出一種大數(shù)據(jù)環(huán)境下基于優(yōu)化初始聚類中心的K中心點(diǎn)算法(CK算法)應(yīng)用在不確定QoS感知的Web服務(wù)選擇中，該算法在保持?jǐn)?shù)據(jù)的多樣性、加快收斂速度、減少迭代次數(shù)和總耗時(shí)間的同時(shí)，又能保證其準(zhǔn)確度。

1 相關(guān)技術(shù)

1.1 服務(wù)選擇的概述

為方便查詢服務(wù)及組合服務(wù)，現(xiàn)對服務(wù)選擇的具體過程表示如下。

定義1服務(wù)。

用一個(gè)五元組S={ns,ds,I,O,Ps}來代表一個(gè)服務(wù)Service，其中：

1)ns表示服務(wù)的代號；ds表示服務(wù)的詳細(xì)信息；服務(wù)中所有操作的集合用Ps表示[1]。

2)I={i1,i2,…,in}是該服務(wù)的輸入集；O={O1,O2,…,On}表示該服務(wù)的輸出集：I∪O就構(gòu)成了該服務(wù)的接口集，?e∈I∪O均與某一服務(wù)相關(guān)[2]。

定義2服務(wù)請求。

一個(gè)服務(wù)請求Request可形式化為一個(gè)四元組R={I,O,QoS,ε}，其中：

1)QoS=(q1,q2,…,qn)，表示服務(wù)使用者對組合服務(wù)質(zhì)量，主要體現(xiàn)在可用性、價(jià)格、可靠性和響應(yīng)時(shí)間等方面，qi為QoS里的一個(gè)具體參數(shù)。

定義3服務(wù)請求Request的最大權(quán)匹配。

最大權(quán)匹配可定義為：

(1)

其中，wi,j為i與j的匹配值，且0

定義4服務(wù)間匹配相似度描述。

服務(wù)間匹配相似度描述可定義為：

(2)

其中，R為服務(wù)發(fā)現(xiàn)中服務(wù)與需求的相似度和用戶需求的概念數(shù)。

定義5目標(biāo)函數(shù)。

目標(biāo)函數(shù)可定義為：

miny=F(WS)=(T(WS),C(WS))

(3)

其中，T(WS)表示服務(wù)組合的響應(yīng)時(shí)間，C(WS)表示服務(wù)質(zhì)量的體現(xiàn)形式，由式(3)可知F(WS)中函數(shù)值大小與向量取值大小成正比，且向量最小時(shí)函數(shù)值也最小。

定義6最佳匹配選擇。

在一個(gè)服務(wù)的操作過程中，當(dāng)且僅當(dāng)?pi∈S.P，simPR=max _simPR時(shí)，操作P才是服務(wù)S對服務(wù)請求R的最佳匹配[3]。

1.2 Web服務(wù)組合概述

定義7用戶需求模型。

具體公式為：

R=(In,Out,postulate,result,QoS)

在整個(gè)用戶需求的描述里，In與Out分別表示它的輸入與輸出函數(shù)[6-7]；postulate對應(yīng)它的必備條件；result表示組合服務(wù)選擇的效果，將用戶需求模型中的4個(gè)參數(shù)統(tǒng)稱為IOPR。

定義8Web服務(wù)的描述模型。

具體公式為：

W={S,Q}

（4）實(shí)驗(yàn)只運(yùn)用酸雨配置、種子萌發(fā)、實(shí)驗(yàn)記錄等簡單的知識和技能，沒有充分利用已有的知識和實(shí)驗(yàn)技能——“細(xì)胞是生物體結(jié)構(gòu)和功能的基本單位”和“制作并用顯微鏡觀察植物細(xì)胞的臨時(shí)裝片”，引導(dǎo)學(xué)生從微觀層面（細(xì)胞這個(gè)結(jié)構(gòu)層次）探究酸雨對生物的影響。

依照S來判斷服務(wù)請求是否符合用戶條件，并參照QoS屬性值將服務(wù)集中的候選服務(wù)選出[8-9]。

定義9待選服務(wù)。

定義10可執(zhí)行相同操作但QoS不同的較優(yōu)服務(wù)集組成服務(wù)集Wi。

服務(wù)動(dòng)態(tài)組合是指在進(jìn)行服務(wù)選擇時(shí)，會有許多符合用戶需求但QoS屬性相異的服務(wù)集合，如何將服務(wù)間接口和服務(wù)索引整合，并將這些相異的符合條件的Web服務(wù)按照用戶的需求進(jìn)行再分配，組合成一個(gè)最佳服務(wù)的工作路徑，最終實(shí)現(xiàn)服務(wù)的最優(yōu)選擇集合。

2 基于K中心點(diǎn)優(yōu)化算法的Web服務(wù)選擇研究

2.1 快速K中心點(diǎn)算法

快速K中心點(diǎn)算法[12]給出了新的樣本密度計(jì)算方法，算法將2個(gè)樣本a、b的距離之和同樣本b與全部樣本的距離之和的比值作為樣本a的密度(在實(shí)際計(jì)算中，樣本b代表全部樣本點(diǎn))，比值越小，說明樣本a的密度越大，該算法從樣本分布最密集的區(qū)域中選擇數(shù)據(jù)對象作為聚類中心，算法流程如下：

1)測量所選樣本的密度，篩查出前K個(gè)密度最大的樣本作為初始聚類中心，再把樣本派發(fā)到與其最近的簇中，計(jì)算聚類誤差平方和。

2)在最新組成的簇中篩查出與簇內(nèi)剩余樣本間距值最小的數(shù)據(jù)元素，并將其指定為初始聚類的新中心。

3)重新測量所有樣本到各初始聚類新中心的路程，且根據(jù)最小距離將它們重新分配到簇中，再算出聚類誤差平方和是否與上次一樣，如果求出的值一樣則完成該過程，如果不一樣則再次執(zhí)行步驟2。

2.2 大數(shù)據(jù)環(huán)境下基于優(yōu)化初始聚類中心的K中心點(diǎn)算法(CK算法)

針對單一的K中心點(diǎn)算法在聚類中心應(yīng)用過程中的缺陷，本文利用大數(shù)據(jù)技術(shù)將樣本集的空間距離特征和密度的屬性進(jìn)行分析，再增加中心點(diǎn)所屬區(qū)域的樣本數(shù)量，并保證它們各自的獨(dú)立性。本文利用文獻(xiàn)[12-17]的現(xiàn)有研究成果結(jié)合文獻(xiàn)[18]的研究方法，將被其它海量樣本包圍且相對獨(dú)立的個(gè)體對象作為初始聚類的中心。它的主要實(shí)現(xiàn)方法為：先將特定的算法在樣本集內(nèi)求出各樣本間的距離，再求出樣本集的距離矩陣[19]；其次再求出樣本集與各樣本平均距離的比值α作為該樣本密度，該樣本被其他樣本圍繞的精密度越高則α值越大，相對密度則越高，通過并行計(jì)算對α進(jìn)行降序排列，選擇k2個(gè)高密度點(diǎn)組合為高密度集合H={h1,h2,…,hk2}；再基于大數(shù)據(jù)環(huán)境通過極值距離乘積法在H內(nèi)篩查獨(dú)立且密度較高的初始中心分配到V={v1，v2，…，vm}內(nèi)，其中m表示其擁有的個(gè)數(shù)；最后再將得到的各備選樣本按樣本間最小距離的條件重新組合并分配至相對應(yīng)的簇內(nèi)，多次執(zhí)行上面步驟，只有當(dāng)準(zhǔn)則函數(shù)收斂時(shí)才結(jié)束此次聚類。

2.3 基于CK算法的Web服務(wù)選擇方法

設(shè)X={x1,x2,…,xi,…,xn}是表示為n個(gè)數(shù)據(jù)對象的樣本集合，并且樣本的特征數(shù)用p表示，該樣本集包含k個(gè)簇，用x={C1,C2,…,Ck}表示，其C內(nèi)又包含m個(gè)簇中心，具體表達(dá)式為V={v1，v2，…，vm}(m

定義11空間任意2點(diǎn)間的歐氏距離。

空間任意2點(diǎn)間的歐氏距離定義為：

(4)

其中，i=1,2,…,n;j=1,2,…,n。

定義12用數(shù)據(jù)對象xi間的距離和跟樣本集的總個(gè)數(shù)來表示xi的平均距離Dist(xi)。

具體公式為：

(5)

定義13用xi間的距離和與樣本集中任意對象間的所有排列次數(shù)的比值來表示樣本集的平均距離。

具體公式為：

(6)

定義14用樣本集的平均距離與Dist(xi)的比值來表示數(shù)據(jù)對象xi的密度。

具體公式為：

α(xi)=DistMean/Dist(xi)

(7)

定義15xi與其對應(yīng)簇的各數(shù)據(jù)對象的距離之和。

xi與其對應(yīng)簇的各數(shù)據(jù)對象的距離之和可定義為：

(8)

其中，xi,xj∈Ct，t=1,2,…k。

定義16簇Ct的簇內(nèi)距離和矩陣。

簇Ct的簇內(nèi)距離和矩陣為：

(9)

其中,t=1,2,…,k。

定義17數(shù)據(jù)對象xi在簇更新過程中被視為簇中心的條件。

數(shù)據(jù)對象xi在簇更新過程中被視為簇中心的條件為：

DistSum(xi)=min (DistSum(Ct))

(10)

其中,xi∈Ct,t=1,2,…,k

定義18聚類誤差平方和。

聚類誤差平方和E可定義為：

(11)

其中,xij表示t簇的第t個(gè)數(shù)據(jù)對象，第t簇的中心是vt。

2.4 基于CK算法的Web服務(wù)組合過程

針對大數(shù)據(jù)環(huán)境下的Web服務(wù)組合研究方法，本文把CK算法原理應(yīng)用至Web服務(wù)選擇及組合上，將一個(gè)樣本集表示為一個(gè)Web服務(wù)集，樣本的特征簇?cái)?shù)代表該路徑下Web服務(wù)所包含的子服務(wù)的數(shù)量，而每一個(gè)簇的中心點(diǎn)則代表該樣本集所對應(yīng)的候選服務(wù)，中心點(diǎn)的個(gè)數(shù)代表該樣本集所對應(yīng)的候選服務(wù)的個(gè)數(shù)，高密度集合對應(yīng)Web服務(wù)候選服務(wù)集，簇中心集對應(yīng)Web服務(wù)組合的較優(yōu)解集。具體步驟為：

Step1初始化聚類中心。

Step1.1通過式(4)計(jì)算樣本集X中各數(shù)據(jù)對象之間的距離。

Step1.2通過式(5)～式(7)求出xi對應(yīng)的密度值，再按密度值從大到小的排序選出前k2個(gè)樣本存放至高密度點(diǎn)集合H內(nèi)。

Step1.3通過式(4)從H中求出距離最大的2個(gè)xi作為備選的2個(gè)初始聚類中心v1、v2加入V內(nèi)[21]。

Step1.4求出符合max(d(hi，v1)×d(hi，v2))條件的數(shù)據(jù)對象hi作為前一個(gè)初始聚類中心v3并加到V內(nèi)[22]。

Step1.5多次重復(fù)Step1.4，直到V中的初始聚類中心個(gè)數(shù)為k，即V={v1,v2,v3,…，vk}。

Step2簇中心迭代更新。

Step2.1通過式(4)計(jì)算xi到V的歐氏距離，再將其存放至各自的簇內(nèi)[4]。

Step2.2通過式(8)、式(9)求出簇內(nèi)距離和的值，篩查符合式(10)的數(shù)據(jù)對象(簇內(nèi)距離和最小)代替之前的原簇中心，并存入新的V′中。

Step3分配數(shù)據(jù)。

Step3.1求出xi到集合V′內(nèi)各簇中心的距離，再把得到的值按最小距離從小到大進(jìn)行排列[23]。

Step3.2最后再求出聚類誤差平方和的值，如果沒有發(fā)生改變，則完成此次選擇的全過程，否則該操作跳轉(zhuǎn)至Step2重新運(yùn)行。

3 實(shí)驗(yàn)研究

3.1 實(shí)驗(yàn)環(huán)境描述

本文實(shí)驗(yàn)環(huán)境在4個(gè)服務(wù)器組成的集群系統(tǒng)中完成，每一個(gè)服務(wù)是戴爾刀片式服務(wù)器至強(qiáng)處理器E5-2600,并借助Matlab2011b實(shí)驗(yàn)平臺。為便于實(shí)驗(yàn)研究，實(shí)驗(yàn)數(shù)據(jù)選用表1中的Iris等5個(gè)常用UCI數(shù)據(jù)集，分別使用本文算法(CK算法)、快速K中心點(diǎn)算法(KK算法))、基于密度與最大距離乘積算法(PK算法)與傳統(tǒng)K中心點(diǎn)算法(K算法)對實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析處理，并完成實(shí)驗(yàn)比較[24]。

表1 實(shí)驗(yàn)數(shù)據(jù)描述

3.2 實(shí)驗(yàn)結(jié)果分析與對比

為分析在大數(shù)據(jù)環(huán)境下基于K中心點(diǎn)優(yōu)化算法的Web服務(wù)選擇算法的有效性和可行性，通過測試不同算法在同一變量環(huán)境下運(yùn)行40次取其平均值再進(jìn)行比較分析。

1)算法的有效性分析。

由圖1可知，在硬件環(huán)境和UCI數(shù)據(jù)集一樣的條件下，CK算法的選擇準(zhǔn)確度明顯都高于K算法、KK算法及PK算法的準(zhǔn)確度，并且針對不同的數(shù)據(jù)集所對應(yīng)的準(zhǔn)確度也各不相同，從而保證了本文算法的精確度和有效性。

圖1 不同算法選擇準(zhǔn)確度

由圖2可得，在硬件環(huán)境和UCI數(shù)據(jù)集一樣的條件下，CK算法的簇中心迭代更新次數(shù)均低于使用K算法、KK算法及PK算法的次數(shù)，并且針對不同的數(shù)據(jù)集所對應(yīng)的迭代次數(shù)也各不相同，從而驗(yàn)證了本文算法的迭代次數(shù)的合理性和該算法的有效性。

圖2 不同算法簇中心迭代更新次數(shù)

2)算法的可行性分析。

由圖3可知，在硬件環(huán)境和UCI數(shù)據(jù)集一樣的條件下，CK算法對候選服務(wù)集的選擇時(shí)間基本都要低于KK算法及PK算法對候選服務(wù)集的選擇時(shí)間，從而減少了對候選集的選擇時(shí)間及驗(yàn)證了本文算法的可行性和時(shí)效性。

圖3 不同算法選候選集的時(shí)間

由圖4可知，在硬件情況和UCI數(shù)據(jù)集不變的前提下，CK算法在服務(wù)選擇及組合應(yīng)用中的總耗時(shí)均要低于K算法、KK算法及PK算法的選擇總時(shí)間，使得本文算法在服務(wù)選擇時(shí)的總耗時(shí)降低，加快服務(wù)選擇及組合的實(shí)現(xiàn)過程，從而驗(yàn)證了本文算法的執(zhí)行時(shí)間更少和該算法的可行性。

圖4 不同算法選擇總耗時(shí)

根據(jù)上述相同UCI數(shù)據(jù)集的條件下針對不同算法的對比分析實(shí)驗(yàn)結(jié)果可知：CK算法不僅在選擇準(zhǔn)確度高于其他3種算法，而且它的選擇時(shí)間和迭代更新次數(shù)都要優(yōu)于其他3種算法，從而驗(yàn)證了本文算法的有效性和可行性。

4 結(jié)束語

本文主要研究了大數(shù)據(jù)環(huán)境下基于優(yōu)化初始聚類的K中心點(diǎn)算法的Web服務(wù)組合方法。該方法應(yīng)用了QoS參數(shù)的最優(yōu)解進(jìn)行Web服務(wù)的動(dòng)態(tài)組合，將大數(shù)據(jù)環(huán)境下基于優(yōu)化初始聚類的K中心點(diǎn)的優(yōu)化算法和Web服務(wù)選擇相結(jié)合，并針對不同用戶需求基于QoS選擇最優(yōu)的Web服務(wù)組合。同時(shí)在實(shí)驗(yàn)平臺上同一環(huán)境下針對不同的選擇方法對服務(wù)動(dòng)態(tài)選擇及組合的準(zhǔn)確度、迭代更新次數(shù)、候選集選擇時(shí)間及選擇總時(shí)間進(jìn)行實(shí)驗(yàn)分析，驗(yàn)證了本文研究方法的有效性和可靠性。