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

程志偉

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

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

中圖分類號：TP301文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044（2012）33-8006-04

1概述

隨著計(jì)算機(jī)軟硬件技術(shù)的不斷發(fā)展，新的計(jì)算模式相繼涌現(xiàn)，IBM公司于2007年底宣布了云計(jì)算計(jì)劃[1]，云計(jì)算開始被業(yè)界關(guān)注。云計(jì)算是一種全新的模式，它可以將相對集中互聯(lián)的大規(guī)模資源進(jìn)行整合并以服務(wù)的形式提供給用戶，既方便了用戶，又提高了資源的利用率。但對于硬件服務(wù)提供商來說，為了滿足用戶的需求，保證服務(wù)的質(zhì)量，在云計(jì)算環(huán)境中應(yīng)投入多少資源來應(yīng)對可能出項(xiàng)的短暫峰值成為一個亟待解決的問題，因?yàn)閺慕?jīng)濟(jì)學(xué)的觀點(diǎn)來看，如果需求沒有較大的增長而不斷加大硬件資源的投入，純利潤會降低，甚至變成負(fù)值。因此行之有效的方法是將互聯(lián)的空閑硬件資源進(jìn)行整合，組成更大的邏輯資源池并以租賃的方式對外提供，硬件服務(wù)商僅需支付少量的費(fèi)用租賃應(yīng)對短暫的峰值，實(shí)現(xiàn)商家和用戶的利益雙贏。關(guān)于云計(jì)算環(huán)境中集群資源模糊聚類劃分的問題，國內(nèi)處于起步階段，出現(xiàn)了一些研究成果：文獻(xiàn)[2]和文獻(xiàn)[3]通過引進(jìn)誤差容忍向量和資源需求向量機(jī)制來獲得邏輯資源池，文獻(xiàn)[3]對集群中的節(jié)點(diǎn)進(jìn)行了規(guī)范化和量化，二者均沒有考慮到資源的商業(yè)特性，同時傳統(tǒng)模糊聚類算法對噪聲數(shù)據(jù)敏感，收斂速度慢。針對以上問題，該文充分考慮資源運(yùn)行成本屬性，改進(jìn)聚類算法，放寬了規(guī)約條件同時提出了新的目標(biāo)函數(shù)，并構(gòu)建數(shù)據(jù)集，通過仿真實(shí)驗(yàn)和評價函數(shù)來驗(yàn)證算法的可行性。

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

2.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ū)號來表示。

2.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｝。

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

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

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

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

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

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

圖中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)的歸屬程度，其公式如下：

隸屬度為：

2.3.3算法描述

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

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

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

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

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

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

3實(shí)驗(yàn)仿真及結(jié)果分析

3.1實(shí)驗(yàn)數(shù)據(jù)與結(jié)果

為驗(yàn)證算法的有效性，故構(gòu)建100臺計(jì)算機(jī)且滿足條件r，每臺機(jī)器的屬性如表1（僅列出20臺機(jī)器）所示：

表中數(shù)據(jù)均為原始數(shù)據(jù)，若直接用于聚類處理，恐影響聚類結(jié)果，故需對數(shù)據(jù)進(jìn)行預(yù)處理。數(shù)據(jù)的預(yù)處理分兩步：一是對GeLoc進(jìn)行數(shù)值化，我們可以按各地市區(qū)號的升序排，排好后從0開始賦值實(shí)現(xiàn)數(shù)字化。二是標(biāo)準(zhǔn)化，除GeLoc外把其余四個屬性數(shù)值按下列公式[5]規(guī)劃到區(qū)間[0，1]上：

數(shù)據(jù)標(biāo)準(zhǔn)化之后，應(yīng)用改進(jìn)的聚類算法進(jìn)行分類，結(jié)果見圖2所示；采用經(jīng)典的C-均值算法分類見圖3所示：

對比兩圖可發(fā)現(xiàn)圖2中的數(shù)據(jù)點(diǎn)更集中，并經(jīng)常有數(shù)據(jù)點(diǎn)與類中心重合的現(xiàn)象，類與類之間的界限也很明顯，出現(xiàn)此現(xiàn)象主要是因?yà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)，使得聚類效果更好。

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

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

表2中改進(jìn)聚類算法的均方誤差ESSE值偏小，更好地反映出改進(jìn)聚類算法在聚攏效果上的高效性和穩(wěn)定性。

4結(jié)束語

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

參考文獻(xiàn)：

[1]SimsK.IBMintroducesready-to-usecloudcomputingcollaborationservicesgetclientsstartedwithcloudcomputing.2007.http：//www-03.ibm.com/press/us/en/pressrelease/22613.wss

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

[3]那麗春.集群資源模糊聚類劃分模型[J].計(jì)算機(jī)工程，2012，38（6）.

[4]JamesCBezdek.PatternRecognitionwithFuzzyObjectiveFunctionAlgorithms[M].NewYork：Plenum，1981：128-132.

[5]陳健美，宋順林，陸虎，等.改進(jìn)模糊聚類算法及其在入侵檢測中的應(yīng)用[J].東南大學(xué)學(xué)報，2007，37（4）.

[6]LiuYuan-chao，WangXiao-long，XuZhi-ming，etal.Asurveyofdocumentclustering[J].JournalofChineseInformationProcessing，2006.

[7]王飛，張德賢，韓金淑，等.蟻群優(yōu)化與模糊聚類結(jié)合的文本聚類研究[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（32）.