一種改進(jìn)的動態(tài)數(shù)據(jù)聚集算法及仿真

蘇嬌嬈

(北京軍區(qū)總醫(yī)院 信息科,北京 100700)

一種改進(jìn)的動態(tài)數(shù)據(jù)聚集算法及仿真

蘇嬌嬈

(北京軍區(qū)總醫(yī)院 信息科,北京 100700)

針對當(dāng)前計算數(shù)據(jù)中心中的動態(tài)數(shù)據(jù)分配方法中存在局限性強(qiáng)、公式復(fù)雜、算法運行效率低等問題,提出了動態(tài)數(shù)據(jù)聚集算法,結(jié)合計算數(shù)據(jù)中心實際情況進(jìn)行改進(jìn),分析了動態(tài)數(shù)據(jù)聚集算法在計算數(shù)據(jù)中心的應(yīng)用。仿真結(jié)果表明,與常規(guī)數(shù)據(jù)分配方法相比,改進(jìn)后的基于動態(tài)數(shù)據(jù)聚集算法的數(shù)據(jù)分配方法,數(shù)據(jù)分配準(zhǔn)確率可達(dá)到98.2%,相比常規(guī)方法有效地提升了結(jié)果的準(zhǔn)確率。

動態(tài)數(shù)據(jù)聚集算法;數(shù)據(jù)分配;計算數(shù)據(jù)中心;仿真研究

隨著當(dāng)前計算機(jī)軟硬件升級,人們對數(shù)據(jù)獲取能力的要求也越來越高?；谟嬎銠C(jī)數(shù)據(jù)中心數(shù)據(jù)分配中,在數(shù)據(jù)中心網(wǎng)絡(luò)技術(shù)基礎(chǔ)上,由于數(shù)據(jù)節(jié)點可自由移動,這樣將會降低數(shù)據(jù)分配進(jìn)度,從而降低系統(tǒng)性能,導(dǎo)致計算機(jī)數(shù)據(jù)中心網(wǎng)絡(luò)維護(hù)開銷過高;故此,在計算機(jī)數(shù)據(jù)中心數(shù)據(jù)分配中,應(yīng)該改進(jìn)傳統(tǒng)靜態(tài)數(shù)據(jù)流數(shù)據(jù)方法,實現(xiàn)動態(tài)數(shù)據(jù)聚集,減少信息冗余,提升數(shù)據(jù)計算效率及安全性。

1 動態(tài)數(shù)據(jù)聚集算法

動態(tài)數(shù)據(jù)聚集算法中,聚類是數(shù)據(jù)挖掘中一類重要的問題,在許多領(lǐng)域有其應(yīng)用之處。聚類的定義就是給定一個有諸多數(shù)據(jù)元素組成的集合,文中將其分為不同的組(類、簇),使得組內(nèi)的元素盡可能相似,不同組之間的元素盡可能不同[1]。在動態(tài)數(shù)據(jù)聚集算法中,其數(shù)據(jù)流具有以下特點:數(shù)據(jù)實時達(dá)到,數(shù)據(jù)到達(dá)次序獨立,不受系統(tǒng)控制;數(shù)據(jù)量較大,不能預(yù)知其大小;單次掃描,數(shù)據(jù)一經(jīng)處理,除非特意保存,否則不能再次被處理。由于計算機(jī)數(shù)據(jù)中心數(shù)據(jù)流的特點,要求數(shù)據(jù)壓縮表達(dá);并可迅速、增量地處理新到達(dá)的數(shù)據(jù),要求該算法可快速、清晰地識別離群點。

2 應(yīng)用動態(tài)數(shù)據(jù)聚集算法的優(yōu)勢

計算機(jī)數(shù)據(jù)中心應(yīng)用的動態(tài)聚類算法,應(yīng)該具備可伸縮性,動態(tài)聚類算法還要具有處理不同類型的數(shù)據(jù)屬性的能力,能夠發(fā)現(xiàn)數(shù)據(jù)中心數(shù)據(jù)分配中的任意形狀聚類,對于輸入?yún)?shù)的領(lǐng)域知識具備弱依賴性,且對于動態(tài)聚類算法中或數(shù)據(jù)中心的輸入記錄順序也不敏感,具有處理計算數(shù)據(jù)中心高維數(shù)據(jù)能力,具備處理數(shù)據(jù)中心數(shù)據(jù)噪聲能力[2]。對計算數(shù)據(jù)中心可能的各種數(shù)據(jù)組合,均可滿足其估算聚類結(jié)果質(zhì)量。同時,對于一個對象Oi,也可被另外的對象代替;對于在數(shù)據(jù)中心一次迭代中產(chǎn)生的最佳對象集合,也可成為下次數(shù)據(jù)迭代中的中心點。且在計算數(shù)據(jù)中心數(shù)據(jù)聚集以及節(jié)點聚集后,可動態(tài)分配計算數(shù)據(jù)中心數(shù)據(jù),降低部分區(qū)域的工作負(fù)荷及能耗。在計算數(shù)據(jù)中心數(shù)據(jù)動態(tài)聚集后,可提高計算數(shù)據(jù)中心資源的利用率,提升計算數(shù)據(jù)中心硬件設(shè)備運行穩(wěn)定性。

3 應(yīng)用動態(tài)數(shù)據(jù)聚集算法實現(xiàn)

對動態(tài)聚類算法中的數(shù)據(jù)流,在每一個時刻,動態(tài)聚類算法的在線部分連續(xù)第讀入一個新的記錄,將多維的數(shù)據(jù)放置到對應(yīng)多維空間中的離散密度網(wǎng)格,在第一個gap時間內(nèi)產(chǎn)生了初始簇[3]。然后,算法周期性地移除松散的網(wǎng)格及調(diào)整簇。由于不可能保留原始數(shù)據(jù),D-Stream將多維數(shù)據(jù)空間分為較多密度網(wǎng)格,然后由這些網(wǎng)格形成簇。如圖1所示。

圖1 動態(tài)聚類算法網(wǎng)格

文本中,假設(shè)輸入的數(shù)據(jù)有d維。并在計算機(jī)數(shù)據(jù)中心空間中定義數(shù)據(jù)

S=S1×S2×…×Sd

(1)

在動態(tài)數(shù)據(jù)聚集中,可將d維的空間S劃分成密度網(wǎng)格。假設(shè)對于每一維,其空間是Si,i=1,…,d被分為pi個部分。

Si=Si,1∪Si,2∪…∪Si,Pi

(2)

g=(j1,j2,…,jd)

(3)

一個數(shù)據(jù)記錄X=(x1,x2,…,xd)可映射到下面一個密度網(wǎng)格

g(x)=(j1,j2,…,jd)whereXi∈Si,ji

(4)

根據(jù)網(wǎng)格密度變動,更新網(wǎng)格密度,當(dāng)一個新的計算機(jī)中心數(shù)據(jù)到網(wǎng)格,接收記錄數(shù)據(jù)記錄,設(shè)一個網(wǎng)格g在時刻tn接收到一個新的數(shù)據(jù)記錄,假設(shè)g接收到最后的數(shù)據(jù)記錄是在時刻tl(tn>tl),則g的密度可按下面的方式更新。

計算數(shù)據(jù)中心動態(tài)數(shù)據(jù)聚集算法的實現(xiàn)中,其最基本的計算思想是,在聚集數(shù)據(jù)的最中心對象,對n個對象給予k個劃分區(qū)域;并且此代表對象也可以被稱為是中心點,而其他的對象為非代表對象[4],反復(fù)使用非代表對象替換代表對象,從而動態(tài)找出數(shù)據(jù)中心更好的中心點,改進(jìn)數(shù)據(jù)中心聚類質(zhì)量。

4 動態(tài)數(shù)據(jù)聚集算法仿真

4.1 仿真試驗環(huán)境搭建

對于計算數(shù)據(jù)中心動態(tài)數(shù)據(jù)聚集算法,針對動態(tài)數(shù)據(jù)聚集算法實施仿真試驗,在一個臺PC上進(jìn)行,用VC++6.0以及Matlab圖形接口實現(xiàn)了動態(tài)聚類算法仿真[5]。研究其算法性能及結(jié)果準(zhǔn)確性,數(shù)據(jù)中心將10個節(jié)點存放于一個機(jī)架上。環(huán)境參數(shù)如表1所示。

表1 環(huán)境參數(shù)表

在動態(tài)數(shù)據(jù)聚集算法仿真試驗中,可設(shè)置Cm=3.0,Cl=0.8,λ=0.998,以及β=0.3。使用兩個測試集[6]。第一個就是測試數(shù)據(jù)集,也是一個真實的數(shù)據(jù)集合KDD CUP-99,其包含由MIT林肯實驗室收集的網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)流。也使用人工數(shù)據(jù)集測試動態(tài)聚類算法的伸縮性。這個人工數(shù)據(jù)集包含的數(shù)據(jù)數(shù)量從35～85 kB不等,簇的數(shù)目設(shè)定為4,維度的數(shù)目范圍從2～40[7]。在動態(tài)數(shù)據(jù)聚集算法仿真試驗中,將數(shù)據(jù)集的所有屬性規(guī)格化為[0,1]。每個維度被均勻地分為多個數(shù)據(jù)段,每個段的長度為len。

4.2 仿真結(jié)果評估

評估計算數(shù)據(jù)中心的動態(tài)聚類質(zhì)量與效率,其與傳統(tǒng)計算數(shù)據(jù)中心的算法進(jìn)行比較。提高算法時間、空間效率,對于計算中心高速的數(shù)據(jù)流不損失聚類質(zhì)量,有獨特的優(yōu)勢,準(zhǔn)確地識別實時數(shù)據(jù)流,并實施演化行為。計算數(shù)據(jù)中心動態(tài)聚類算法與傳統(tǒng)數(shù)據(jù)分配算法相比,數(shù)據(jù)準(zhǔn)確性得到提升,為98.2%,常規(guī)數(shù)據(jù)分配準(zhǔn)確率83.6%,有明顯優(yōu)勢(P<0.05)。計算數(shù)據(jù)中心動態(tài)聚類算法的應(yīng)用,可提升計算數(shù)據(jù)中心系統(tǒng)穩(wěn)定性。

5 結(jié)束語

綜上所述,在目前計算數(shù)據(jù)中心,設(shè)計動態(tài)數(shù)據(jù)聚集算法,通過仿真實驗進(jìn)行驗證分析,表明動態(tài)數(shù)據(jù)聚集算法,能夠保障計算數(shù)據(jù)中心的服務(wù)質(zhì)量,提高計算機(jī)設(shè)備穩(wěn)定性,還可以提升計算機(jī)數(shù)據(jù)中心服務(wù)質(zhì)量,可在不同時段動態(tài)分配數(shù)據(jù)使用,實現(xiàn)有效的聚集數(shù)據(jù)分配模式,從而確保系統(tǒng)計算存儲節(jié)點可以輪流運轉(zhuǎn),提升計算機(jī)數(shù)據(jù)中心區(qū)域溫控設(shè)備精度,充分利用計算數(shù)據(jù)中心資源,滿足用戶的實際服務(wù)需求,降低計算數(shù)據(jù)中心系統(tǒng)動態(tài)數(shù)據(jù)分配能耗。

[1] 亓開元,韓燕波,趙卓峰,等.支持高并發(fā)數(shù)據(jù)流處理的MapReduce中間結(jié)果緩存[J].計算機(jī)研究與發(fā)展,2013,50(1):111-121.

[2] 王立,樂嘉錦.基于度量波動時間框架的流立方體研究[J].計算機(jī)應(yīng)用與軟件,2011(3):169-172.

[3] 侯東風(fēng),劉青寶,張維明,等.一種適應(yīng)性的流式數(shù)據(jù)聚集計算方法[J].計算機(jī)科學(xué),2010,37(3):152-155,169.

[4] 劉青寶,侯東風(fēng).基于查詢索引樹的多維連續(xù)查詢計算方法[J].信息工程大學(xué)學(xué)報,2012,13(1):100-104,114.

[5] 陳偉,陳璟,孫俊,等.一種量子行為粒子群優(yōu)化動態(tài)聚類算法[J].計算機(jī)應(yīng)用研究,2011(7):2432-2435.

[6] 侯東風(fēng).流式數(shù)據(jù)多維建模與查詢關(guān)鍵技術(shù)研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2010.

[7] 劉青寶.模糊、動態(tài)多維數(shù)據(jù)建模理論與方法研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2010.

Algorithm for Dynamic Data Aggregation and its Simulation

SU Jiaorao

(Department of Information,Military General Hospital of Beijing PL,Beijing 100700,China)

The dynamic data distribution algorithm used by the computing data center has the disadvantages of strong limitations,complex formulas,and low algorithm running efficiency.This paper proposes an algorithm for dynamic data aggregation,which is further improved on the basis of the actual situation of the computing data center.Its application in the computing data center is analyzed.Simulation results show that the improved data distribution method based on the dynamic data aggregation algorithm can achieve a data distribution accuracy rate of as high as 98.2%,as compared with the conventional data distribution accuracy rate of 83.6%.

dynamic data aggregation algorithm;data distribution;computing data center;simulation research

2015- 03- 19

蘇嬌嬈(1976—),女,工程師。研究方向:計算機(jī)通信與網(wǎng)絡(luò)。E-mail:Sjrr881@sohu.com

10.16180/j.cnki.issn1007-7820.2015.05.009

TP301.6

A

1007-7820(2015)05-030-03