大數據環(huán)境下基于K中心點優(yōu)化算法的Web服務組合

劉 鋒，鄒臣嵩，崔 煒

(1.廣東松山職業(yè)技術學院電氣工程學院,廣東 韶關 512126；2.廣東松山職業(yè)技術學院信息與現代教育技術中心,廣東 韶關 512126)

0 引 言

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

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

1 相關技術

1.1 服務選擇的概述

為方便查詢服務及組合服務，現對服務選擇的具體過程表示如下。

定義1服務。

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

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

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

定義2服務請求。

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

1)QoS=(q1,q2,…,qn)，表示服務使用者對組合服務質量，主要體現在可用性、價格、可靠性和響應時間等方面，qi為QoS里的一個具體參數。

定義3服務請求Request的最大權匹配。

最大權匹配可定義為：

(1)

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

定義4服務間匹配相似度描述。

服務間匹配相似度描述可定義為：

(2)

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

定義5目標函數。

目標函數可定義為：

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

(3)

其中，T(WS)表示服務組合的響應時間，C(WS)表示服務質量的體現形式，由式(3)可知F(WS)中函數值大小與向量取值大小成正比，且向量最小時函數值也最小。

定義6最佳匹配選擇。

在一個服務的操作過程中，當且僅當?pi∈S.P，simPR=max _simPR時，操作P才是服務S對服務請求R的最佳匹配[3]。

1.2 Web服務組合概述

定義7用戶需求模型。

具體公式為：

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

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

定義8Web服務的描述模型。

具體公式為：

W={S,Q}

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

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

定義9待選服務。

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

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

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

2.1 快速K中心點算法

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

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

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

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

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

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

2.3 基于CK算法的Web服務選擇方法

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

定義11空間任意2點間的歐氏距離。

空間任意2點間的歐氏距離定義為：

(4)

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

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

具體公式為：

(5)

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

具體公式為：

(6)

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

具體公式為：

α(xi)=DistMean/Dist(xi)

(7)

定義15xi與其對應簇的各數據對象的距離之和。

xi與其對應簇的各數據對象的距離之和可定義為：

(8)

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

定義16簇Ct的簇內距離和矩陣。

簇Ct的簇內距離和矩陣為：

(9)

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

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

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

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

(10)

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

定義18聚類誤差平方和。

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

(11)

其中,xij表示t簇的第t個數據對象，第t簇的中心是vt。

2.4 基于CK算法的Web服務組合過程

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

Step1初始化聚類中心。

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

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

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

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

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

Step2簇中心迭代更新。

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

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

Step3分配數據。

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

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

3 實驗研究

3.1 實驗環(huán)境描述

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

表1 實驗數據描述

3.2 實驗結果分析與對比

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

1)算法的有效性分析。

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

圖1 不同算法選擇準確度

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

圖2 不同算法簇中心迭代更新次數

2)算法的可行性分析。

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

圖3 不同算法選候選集的時間

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

圖4 不同算法選擇總耗時

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

4 結束語

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