試論基于模糊聚類算法的資源整合

【摘 要】為解決云計算環(huán)境中硬件資源整合問題，分析了云中互聯(lián)資源的屬性，提出一種改進(jìn)模糊聚類算法。該算法放寬規(guī)約條件，考慮到矩陣中數(shù)據(jù)點(diǎn)的關(guān)系無法比較，定義加權(quán)因子并構(gòu)建新的目標(biāo)函數(shù)，先隨機(jī)選取硬件作為初始聚類中心，然后不斷計算隸屬度確定聚類中心，重復(fù)迭代改進(jìn)目標(biāo)函數(shù)優(yōu)化數(shù)據(jù)集的劃分，最后獲取屬性相似的邏輯資源池。實驗結(jié)果表明改進(jìn)算法收斂速度較快，得到的聚類結(jié)果較好，適合云環(huán)境中具有相似屬性的資源整合。

【關(guān)鍵詞】資源屬性；加權(quán)因子；目標(biāo)函數(shù)；模糊聚類；評價函數(shù)

0.引言

隨著計算機(jī)軟硬件技術(shù)的不斷發(fā)展，新的計算模式相繼涌現(xiàn)，IBM公司于2007年底宣布了云計算計劃[1]，云計算開始被業(yè)界關(guān)注。云計算是一種全新的模式，它可以將相對集中互聯(lián)的大規(guī)模資源進(jìn)行整合并以服務(wù)的形式提供給用戶，既方便了用戶，又提高了資源的利用率。但對于硬件服務(wù)提供商來說，為了滿足用戶的需求，保證服務(wù)的質(zhì)量，在云計算環(huán)境中應(yīng)投入多少資源來應(yīng)對可能出項的短暫峰值成為一個亟待解決的問題，因為從經(jīng)濟(jì)學(xué)的觀點(diǎn)來看，如果需求沒有較大的增長而不斷加大硬件資源的投入，純利潤會降低，甚至變成負(fù)值。因此行之有效的方法是將互聯(lián)的空閑硬件資源進(jìn)行整合，組成更大的邏輯資源池并以租賃的方式對外提供，硬件服務(wù)商僅需支付少量的費(fèi)用租賃應(yīng)對短暫的峰值，實現(xiàn)商家和用戶的利益雙贏。

1.基于改進(jìn)模糊聚類算法的硬件資源整合

1.1資源描述

云環(huán)境中硬件資源有多重屬性，本文僅從以下五方面來考慮，任一資源HVi的資源屬性可描述為：

HVi={CPU，Memeory，BandWidth，Cost，GeLoc}

其中，CPU表示運(yùn)行速度，用Ghz來衡量；Memeory表示內(nèi)存大小，用容量來衡量；BandWidth表示網(wǎng)絡(luò)帶寬，用Mbps.s-1來度量；Cost表示每秒運(yùn)行資源的成本，用￥.s-1；GeLoc表示資源所在的地理位置，我們可以采用地區(qū)號來表示。

1.2聚類中心的選取

資源有其固有的地理位置，硬件服務(wù)商如需租賃資源，考慮到運(yùn)行成本、速度等因素，應(yīng)選擇本地區(qū)或周圍地區(qū)的邏輯資源池。在此引入變量r，若GeLoc值相同，則r=0，認(rèn)定是本地區(qū)的邏輯資源池；若0

本研究的聚類個數(shù)c由租賃者指定，任選本地區(qū)或周圍地區(qū)的c個硬件資源構(gòu)成的初始聚類中心為{ω1，ω2…，ωc}。

1.3數(shù)據(jù)矩陣與目標(biāo)函數(shù)

1.3.1構(gòu)建數(shù)據(jù)矩陣

設(shè)互聯(lián)的硬件資源數(shù)目為n，集合X= {X1，X2，…，Xn}表示，其中每個資源Xi有m個屬性，用向量Xi=（xi1，xi2，…，xim）表示，則得到的數(shù)據(jù)空間為：

X={Xi|Xi=（xi1，xi2，…，xim），1≤i≤n}

1.3.2目標(biāo)函數(shù)的改進(jìn)

模糊C-均值聚類算法的目標(biāo)函數(shù)J及其約束條件如下：

J（U，c1，…，cc）=■Ji=■■u■■d■■ （1）

■uij=1，？坌j=1，…，n （2）

在公式（1）中，uij為隸屬度，表示數(shù)據(jù)點(diǎn)與類中心的關(guān)系；公式（2）為約束條件，要求每個數(shù)據(jù)點(diǎn)xj與c個聚類中心的總和為1。正式由于這個條件的限制，使得聚類中心不能獨(dú)立，對噪聲數(shù)據(jù)比較敏感，因此對隸屬度函數(shù)的約束條件（2）修改為：

■uij>0，？坌j=1，…，n （3）

數(shù)據(jù)與聚類中心的關(guān)系由uij表示，但相對于同一聚類中心，不同數(shù)據(jù)點(diǎn)的關(guān)系無法描述。

圖中A，B，C為三個數(shù)據(jù)點(diǎn)，x，y，z為聚類中心。點(diǎn)C對三個聚類中心的隸屬度分別為0.2，0.5，0.3，經(jīng)比較可知點(diǎn)C屬于類中心y的可能性較大。但對于類中心y來說，數(shù)據(jù)點(diǎn)A，B，C的關(guān)系無法比較，因此，提出一個加權(quán)因子。

定義1 加權(quán)因子Mij，表示相對于同一聚類中心ci各數(shù)據(jù)點(diǎn)的歸屬程度，其公式如下：

Mij=uij*（Mi）-1 （4）

其中，Mi=■uij>0，？坌j=1，…，n （5）

改進(jìn)的新目標(biāo)函數(shù)為：

J（U，ω1，…，ωc）=■Ji=■■u■■M■■*（xj-ωi）■ （6）

應(yīng)用Lagrange乘數(shù)法求解出聚類中心為：

ci=■，？坌i=1，…，n （7）

隸屬度為：

uij=■■■ （8）

1.3.3算法描述

集合X = { X1，X2，…，Xn}為需要整合的硬件資源，輸入聚類個數(shù)c和最大迭代次數(shù)k，誤差ε，參數(shù)m=2，執(zhí)行下列步驟：

Step1 確定初始聚類中心{ω1，ω2…，ωc}，并令k=1；

Step2 根據(jù)公式（8）計算隸屬度；

Step3 根據(jù)公式（7）更新聚類中心；

Step4 計算誤差e=■ci（k）-ci（k-1）■，若e<ε，則輸出劃分的矩陣和聚類中心ω，否則轉(zhuǎn)向step2，重復(fù)執(zhí)行step2～step4；

基于加權(quán)因子的模糊聚類算法，不僅考慮了數(shù)據(jù)點(diǎn)對各聚類中心的距離，還考慮了相對同一類中心各數(shù)據(jù)點(diǎn)的關(guān)系，有效地克服了基于歐式距離的算法特點(diǎn)。

2.實驗仿真及結(jié)果分析

2.1實驗數(shù)據(jù)與結(jié)果

為驗證算法的有效性，故構(gòu)建100臺計算機(jī)且滿足條件r，需對數(shù)據(jù)進(jìn)行預(yù)處理。數(shù)據(jù)的預(yù)處理分兩步：一是對GeLoc進(jìn)行數(shù)值化，我們可以按各地市區(qū)號的升序排，排好后從0開始賦值實現(xiàn)數(shù)字化。二是標(biāo)準(zhǔn)化，除GeLoc外把其余四個屬性數(shù)值按下列公式規(guī)劃到區(qū)間[0，1]上：

x'ik=■（i=1，2，…，n；k=1，2，…，m） （9）

其中：

■=■■xik，sk=■ （10）

數(shù)據(jù)標(biāo)準(zhǔn)化之后，分別應(yīng)用改進(jìn)的聚類算法進(jìn)行分類，以及采用經(jīng)典的C-均值算法分類。對比發(fā)現(xiàn)前者數(shù)據(jù)點(diǎn)更集中，并經(jīng)常有數(shù)據(jù)點(diǎn)與類中心重合的現(xiàn)象，類與類之間的界限也很明顯，出現(xiàn)此現(xiàn)象主要是因為加權(quán)因子Mij，Mij-1類似于一個放大鏡，它將所有的距離進(jìn)行放大，但尺度不同；距離近的點(diǎn)放大的尺度小，而距離遠(yuǎn)的點(diǎn)放大的尺度要大一些，于是導(dǎo)致兩極分化，距離近的數(shù)據(jù)點(diǎn)變得更近，距離遠(yuǎn)的點(diǎn)也就變得更遠(yuǎn)，使得聚類效果更好。

2.2評價標(biāo)準(zhǔn)

從圖中我們可以直觀地看出改進(jìn)聚類算法的效果，但聚類算法還須通過評價函數(shù)進(jìn)一步來驗證。聚類結(jié)果的評價一般采用兩種方式，內(nèi)部評價和外部評價，本文采用內(nèi)部評價函數(shù)ESSE來作為評價標(biāo)準(zhǔn)，見公式（11）。

ESSE=■■（d（xi，cj））2 （11）

其中，nj表示第j個聚類中的元素數(shù)；d（xi，cj）為數(shù)據(jù)xi與聚類中心cj的距離；ESSE值越小，表示聚類效果越好。

測試時，聚類數(shù)目c分別等于2，3，4，迭代10次，取平均值為最終結(jié)果。改進(jìn)聚類算法的均方誤差ESSE值偏小，更好地反映出改進(jìn)聚類算法在聚攏效果上的高效性和穩(wěn)定性。

3.結(jié)束語

云環(huán)境下的資源種類繁多、功能各異，通過本文提出的基于加權(quán)因子的改進(jìn)模糊聚類算法可以獲得若干個邏輯池，而每個邏輯池中的資源屬性特征相近，適合運(yùn)行同一類計算任務(wù)，使用成本為資源池中每個資源的Cost總和，提高了資源的利用率。實驗結(jié)果表明，改進(jìn)算法加快了收斂速度，降低了算法的時間復(fù)雜度，得到較好的聚類劃分。但算法中參數(shù)m只能根據(jù)經(jīng)驗給出，聚類數(shù)目c只能通過反復(fù)試驗得出，缺乏理論支持，需進(jìn)一步研究改進(jìn)。

【參考文獻(xiàn)】

[1]Sims K.IBM introduces ready-to-use cloud computing collaboration services get clients started with cloud computing.2007.http：//www-03.ibm.com/press/us/en/pressrelease/22613.wss.

[2]劉伯成，陳慶奎.云計算中的集群資源模糊聚類劃分模型[J].計算機(jī)科學(xué)，2011，38（s1）.