蘇嬌嬈

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

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

蘇嬌嬈

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

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

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

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

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

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

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

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

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

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

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

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

S=S1×S2×…×Sd

(1)

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

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

(2)

g=(j1,j2,…,jd)

(3)

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

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

(4)

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

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

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

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

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

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

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

4.2 仿真結(jié)果評(píng)估

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

[7] 劉青寶.模糊、動(dòng)態(tài)多維數(shù)據(jù)建模理論與方法研究[D].長(zhǎng)沙:國(guó)防科學(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ì)算機(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