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

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

【關鍵詞】資源屬性；加權因子；目標函數；模糊聚類；評價函數

0.引言

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

1.基于改進模糊聚類算法的硬件資源整合

1.1資源描述

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

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

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

1.2聚類中心的選取

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

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

1.3數據矩陣與目標函數

1.3.1構建數據矩陣

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

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

1.3.2目標函數的改進

模糊C-均值聚類算法的目標函數J及其約束條件如下：

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

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

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

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

數據與聚類中心的關系由uij表示，但相對于同一聚類中心，不同數據點的關系無法描述。

圖中A，B，C為三個數據點，x，y，z為聚類中心。點C對三個聚類中心的隸屬度分別為0.2，0.5，0.3，經比較可知點C屬于類中心y的可能性較大。但對于類中心y來說，數據點A，B，C的關系無法比較，因此，提出一個加權因子。

定義1 加權因子Mij，表示相對于同一聚類中心ci各數據點的歸屬程度，其公式如下：

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

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

改進的新目標函數為：

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

應用Lagrange乘數法求解出聚類中心為：

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

隸屬度為：

uij=■■■ （8）

1.3.3算法描述

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

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

Step2 根據公式（8）計算隸屬度；

Step3 根據公式（7）更新聚類中心；

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

基于加權因子的模糊聚類算法，不僅考慮了數據點對各聚類中心的距離，還考慮了相對同一類中心各數據點的關系，有效地克服了基于歐式距離的算法特點。

2.實驗仿真及結果分析

2.1實驗數據與結果

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

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

其中：

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

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

2.2評價標準

從圖中我們可以直觀地看出改進聚類算法的效果，但聚類算法還須通過評價函數進一步來驗證。聚類結果的評價一般采用兩種方式，內部評價和外部評價，本文采用內部評價函數ESSE來作為評價標準，見公式（11）。

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

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

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

3.結束語

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

【參考文獻】

[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].計算機科學，2011，38（s1）.