自適應(yīng)云資源大塊數(shù)據(jù)對(duì)象并行存取方法

楊 建，劉述木

(1.四川省裝備制造業(yè)機(jī)器人應(yīng)用技術(shù)工程實(shí)驗(yàn)室，四川 德陽(yáng) 618000；2.四川大學(xué)軟件學(xué)院，四川 成都 610065)

1 引言

網(wǎng)絡(luò)上的海量數(shù)據(jù)文件格式不同、復(fù)雜程度不同，如何在海量的數(shù)據(jù)文件中自由存取自己需要的數(shù)據(jù)，逐漸成為人們的焦點(diǎn)[1]。在傳統(tǒng)的方法滿足不了人們對(duì)云資源大塊數(shù)據(jù)處理需求時(shí)，提出一種新型的大數(shù)據(jù)塊對(duì)象的并行存取方法尤為迫切[2]。

李良[3]等提出基于NET的自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的存取方法。該方法首先在ASENET平臺(tái)上使用C#對(duì)大數(shù)據(jù)塊中的數(shù)據(jù)進(jìn)行編程，再通過(guò)ADO-NET對(duì)數(shù)據(jù)庫(kù)的后臺(tái)進(jìn)行訪問(wèn)，利用內(nèi)存流對(duì)大數(shù)據(jù)塊對(duì)象中的數(shù)據(jù)進(jìn)行讀取，最后啟用通用自定義HTTP請(qǐng)求對(duì)大數(shù)據(jù)塊對(duì)象中的數(shù)據(jù)進(jìn)行處理，以此實(shí)現(xiàn)對(duì)自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取。該方法由于在對(duì)大數(shù)據(jù)對(duì)象進(jìn)行并行存取時(shí)沒(méi)有利用數(shù)據(jù)挖掘理論構(gòu)建自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取模型，所以導(dǎo)致并行存取的存取時(shí)間長(zhǎng)、存取效率低。索劍[4]等提出基于傳統(tǒng)關(guān)系型數(shù)據(jù)，對(duì)大數(shù)據(jù)塊對(duì)象中的數(shù)據(jù)進(jìn)行結(jié)構(gòu)處理，并將其分為模式與無(wú)模式兩個(gè)部分，再分別對(duì)其進(jìn)行預(yù)處理從而解決數(shù)據(jù)一致性與高效存取的矛盾。最后在同一數(shù)據(jù)庫(kù)中對(duì)相同數(shù)據(jù)分別進(jìn)行模式與無(wú)模式環(huán)境下的數(shù)據(jù)插入，查詢等操作，以此完成自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取。該方法由于在并行存取時(shí)沒(méi)有對(duì)大數(shù)據(jù)對(duì)象的數(shù)據(jù)采樣梯度函數(shù)進(jìn)行計(jì)算，獲取大數(shù)據(jù)塊對(duì)象的輸出密度導(dǎo)致并行存取的正確率低，內(nèi)存占比高。雷曉勇[5]等提出基于HWS的大數(shù)據(jù)塊對(duì)象并行存取方法。該方法首先對(duì)常見的存儲(chǔ)格式進(jìn)行分析，并以分析結(jié)果為基礎(chǔ)構(gòu)建一個(gè)分級(jí)的數(shù)據(jù)存儲(chǔ)格式，再利用高級(jí)的波形數(shù)據(jù)存儲(chǔ)函數(shù)對(duì)大數(shù)據(jù)塊對(duì)象中的數(shù)據(jù)進(jìn)行計(jì)算，獲取雙精度的浮點(diǎn)數(shù)據(jù)。最后將其放入HWS中讀取，以此完成自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取。該方法由于在并行存取時(shí)未能利用數(shù)據(jù)挖掘理論對(duì)數(shù)據(jù)的自適應(yīng)調(diào)度加權(quán)系數(shù)進(jìn)行計(jì)算，獲取系數(shù)中的最低負(fù)載遷移量，所以導(dǎo)致并行存取的時(shí)間長(zhǎng)、效率低。

為解決上述并行存取方法中存在的問(wèn)題，提出基于數(shù)據(jù)挖掘的自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取方法，其創(chuàng)新之處在于利用聚類算法對(duì)大數(shù)據(jù)塊對(duì)象中的數(shù)據(jù)進(jìn)行缺失值填充后，將完整數(shù)據(jù)放入模型中進(jìn)行自適應(yīng)尋優(yōu)處理，保證并行存取的完整度的同時(shí)，優(yōu)化存取時(shí)間和正確率。

2 數(shù)據(jù)預(yù)處理

利用聚類算法對(duì)大數(shù)據(jù)塊進(jìn)行數(shù)據(jù)預(yù)處理，獲取新的數(shù)據(jù)集。

2.1 DBSCAN算法

基于聚類算法(DBSCAN)對(duì)數(shù)據(jù)中的缺失值進(jìn)行填充，過(guò)程如圖1所示。

圖1 數(shù)據(jù)填充過(guò)程

自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的原始數(shù)據(jù)中會(huì)存在部分的不完整數(shù)據(jù)，包括數(shù)據(jù)屬性不完整、缺失值較大等問(wèn)題。一般情況下，若缺失的屬性值占屬性記錄的大半，那么就要將其從記錄中刪除。若某數(shù)據(jù)的屬性值占比較小，也將其屬性刪除(其中若有數(shù)據(jù)的屬性是獨(dú)立的則可以保留)，不然會(huì)對(duì)大數(shù)據(jù)對(duì)象的并行存取產(chǎn)生影響。利用刪除屬性策略對(duì)大數(shù)據(jù)集中的不完整數(shù)據(jù)進(jìn)行刪除，輸出數(shù)據(jù)集S以及完整的子集Sc、缺失的數(shù)據(jù)集Si。

將原始數(shù)據(jù)集分為兩個(gè)子集后，利用DBSCAN算法對(duì)自適應(yīng)云資源大數(shù)據(jù)塊進(jìn)行聚類，產(chǎn)生k個(gè)簇。

基于產(chǎn)生每個(gè)簇的重心，計(jì)算缺失數(shù)據(jù)子集中每個(gè)屬性記錄與k個(gè)簇重心之間的相似度，并將記錄值賦予給它相鄰的簇，利用這個(gè)簇的屬性均值填充該記錄的缺失值。若缺失數(shù)據(jù)集中某一記錄的缺失值無(wú)法填充就可以刪除此條記錄。填充過(guò)后，輸出最終的清洗結(jié)果S′，S′則是由自適應(yīng)云資源大數(shù)據(jù)塊中完整的數(shù)據(jù)子集Sc以及經(jīng)過(guò)填充處理的子集Si組成的。

自適應(yīng)云資源大數(shù)據(jù)塊中同類數(shù)據(jù)之間存在很多的相似屬性[6]，所以要通過(guò)對(duì)屬性的計(jì)算獲取聚類結(jié)果。再基于DBSCAN的缺失清洗算法對(duì)聚類結(jié)果進(jìn)行計(jì)算，過(guò)程如下：

首先輸入一個(gè)給點(diǎn)對(duì)象的半徑b以及b區(qū)間(-b鄰域)內(nèi)的若干數(shù)據(jù)個(gè)數(shù)。

1)將自適應(yīng)云資源大數(shù)據(jù)塊中的數(shù)據(jù)集S分為兩個(gè)子集，完整的記錄子集為Sc(無(wú)任何屬性含缺失值)及缺失的數(shù)據(jù)集Si(屬性中有一個(gè)或多個(gè)缺失值)。

2)利用DBSCAN算法計(jì)算完整的數(shù)據(jù)子集Sc，選取自適應(yīng)云資源大數(shù)據(jù)塊的核心對(duì)象以及-b鄰域，依據(jù)直接密度可達(dá)、密度可達(dá)、密度相連的方法對(duì)數(shù)據(jù)子集中的對(duì)象進(jìn)行聚類并在聚類后計(jì)算每個(gè)簇中對(duì)象的均值，以此使目標(biāo)函數(shù)值達(dá)到最小。

3)從自適應(yīng)云資源大數(shù)據(jù)塊的非完整數(shù)據(jù)子集Si中按順序提取屬性記錄，計(jì)算記錄與Sc的幾個(gè)類中任一類的相似度，選出相似值為最大的記錄，把該記錄標(biāo)記為Xi(i=0，1，2，…，k)類，重復(fù)上述過(guò)程一直持續(xù)到數(shù)據(jù)子集為空。

4)依據(jù)非完整數(shù)據(jù)子集的記錄分配k簇，利用下式對(duì)記錄缺失值進(jìn)行處理

(1)

由于不完全數(shù)據(jù)子集Si中的每條記錄都被賦予了最接近它的簇，而且不完全數(shù)據(jù)子集中的每條記錄和被賦予的簇都有許多相似的屬性，因此要使被賦予的簇具有完整的屬性，就需要用它的平均值來(lái)填充[7]。式中，Ai代表數(shù)據(jù)集中缺失值被分配的第i個(gè)完整記錄的數(shù)據(jù)值，n為屬性的記錄總數(shù)。

根據(jù)聚類算法可知，DBSCAN的缺失值填充算法對(duì)空間的需求不是很大，這主要是因?yàn)榍逑磾?shù)據(jù)時(shí)只需要存儲(chǔ)數(shù)據(jù)集，其空間的復(fù)雜度為O(n-m+k)，n為自適應(yīng)云資源大數(shù)據(jù)塊數(shù)據(jù)集中的記錄數(shù)目[8]，m為缺失值的記錄個(gè)數(shù)，k為簇的數(shù)目。由于本算法在時(shí)間上同樣沒(méi)有什么需求，所以其時(shí)間的復(fù)雜度為O((n-m)kt1)，(n-m)是自適應(yīng)云資源大數(shù)據(jù)塊數(shù)據(jù)集中的完整記錄數(shù)目，t是需要進(jìn)行迭代的次數(shù)。

根據(jù)上述過(guò)程，完成自適應(yīng)云資源大數(shù)據(jù)塊內(nèi)的數(shù)據(jù)屬性缺失值的填充。

2.2 數(shù)據(jù)分割

基于填充過(guò)缺失值的自適應(yīng)云資源大數(shù)據(jù)塊的完整數(shù)據(jù)集，采用均值聚類算法對(duì)數(shù)據(jù)集進(jìn)行數(shù)據(jù)分割。

首先，設(shè)定數(shù)據(jù)集的給定聚類數(shù)為k，再基于算法的初值敏感問(wèn)題優(yōu)化初始中心的k-均值算法，分割過(guò)程如下所示：

1)確定分割區(qū)域

在填充過(guò)缺失值的數(shù)據(jù)集中設(shè)定一個(gè)半徑R，再以此為基礎(chǔ)為每個(gè)數(shù)據(jù)確認(rèn)一個(gè)球形鄰域，計(jì)算落在鄰域內(nèi)的數(shù)據(jù)個(gè)數(shù)。若鄰域內(nèi)的體積與鄰域內(nèi)數(shù)據(jù)個(gè)數(shù)的商不小于空間總體積與數(shù)據(jù)總個(gè)數(shù)的商，就可以認(rèn)定該數(shù)據(jù)在高密度區(qū)域內(nèi)。

2)選取初始聚類中心

設(shè)高密度區(qū)域內(nèi)有m*個(gè)數(shù)據(jù)，首先隨機(jī)選定一個(gè)數(shù)據(jù)作為第一中心y1；再選定距離y1最遠(yuǎn)的數(shù)據(jù)作為第二中心y2；選定一個(gè)數(shù)據(jù)yj作為第三中心，這時(shí)yj要滿足下式

(2)

根據(jù)上述標(biāo)準(zhǔn)，繼續(xù)選定m4，…，mk，找出高密度區(qū)域內(nèi)的k個(gè)中心m1，m2，…，mk。

依據(jù)設(shè)定的P指標(biāo)計(jì)算下式

(3)

式中

(4)

其中，m為自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象中數(shù)據(jù)集的樣本個(gè)數(shù)[9-10]，數(shù)據(jù)的劃分矩陣為U(X)=[uij]k×m，這時(shí)若xj∈Ci，uij=1，若不是uij則為0，mi是聚類Ci的中心，q=2。

依據(jù)選定的k范圍，重復(fù)上述計(jì)算獲取最終的P指標(biāo)。

最后利用下式，對(duì)數(shù)據(jù)進(jìn)行最終分割

koptimal=arg maxkP(k)

(5)

3 基于數(shù)據(jù)挖掘理論的并行存取方法

基于關(guān)聯(lián)規(guī)則項(xiàng)的引導(dǎo)將分割后自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象進(jìn)行并行存取。過(guò)程如圖2所示。

圖2 并行存取過(guò)程

3.1 引入關(guān)聯(lián)規(guī)則

依據(jù)隨機(jī)概率的密度分布[11-12]，對(duì)自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的數(shù)據(jù)實(shí)體節(jié)點(diǎn)與Sink節(jié)點(diǎn)進(jìn)行均衡控制，并對(duì)其關(guān)系進(jìn)行偏導(dǎo)函數(shù)求解，過(guò)程如下式所示

gk+akkoptimal=0

(6)

建立基于數(shù)據(jù)挖掘理論的自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取模型，首先要獲取存取輸入層神經(jīng)元，如下式所示

(7)

大數(shù)據(jù)塊對(duì)象中的數(shù)量小的端口節(jié)點(diǎn)負(fù)載神經(jīng)元狀態(tài)為下式所示

uni(k)=netni(k)

(8)

大數(shù)據(jù)塊對(duì)象數(shù)據(jù)存取的輸入層神經(jīng)元輸出如下式所示

(9)

式中，uni(k)為自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象數(shù)據(jù)流量負(fù)載的邊節(jié)點(diǎn)向量，采用控制律構(gòu)建自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的數(shù)據(jù)調(diào)度控制模型。

把大數(shù)據(jù)塊對(duì)象中最大或最小的數(shù)據(jù)神經(jīng)元、，映射成隨機(jī)生成的T個(gè)初始解，求解自適應(yīng)云資源大數(shù)據(jù)對(duì)象的數(shù)據(jù)采樣梯度函數(shù)，下式表示

xij=xmin，j+rand(0，1)(xmax，j-xmin，j)

(10)

利用關(guān)聯(lián)規(guī)則對(duì)自適應(yīng)云資源大數(shù)據(jù)對(duì)象進(jìn)行并行存取，獲取的輸出密度如下式所示

opij=k*(minj+maxj)-xij

(11)

以輸出密度為約束條件，即可得到數(shù)據(jù)的最佳尋優(yōu)軌跡。

3.2 并行存取

采用模糊約束法對(duì)數(shù)據(jù)存儲(chǔ)路徑進(jìn)行尋優(yōu)，在自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取中，利用柯西的不等式理論計(jì)算數(shù)據(jù)塊對(duì)象的二階梯度，獲取Δ2F(x)，再利用多個(gè)非線性成分的聯(lián)合統(tǒng)計(jì)法對(duì)大數(shù)據(jù)塊對(duì)象中的數(shù)據(jù)進(jìn)行高維空間重構(gòu)，最后結(jié)合模糊聚類對(duì)大數(shù)據(jù)塊內(nèi)的數(shù)據(jù)進(jìn)行自適應(yīng)分類處理，獲取數(shù)據(jù)存取的負(fù)載，如下式所示：

(12)

式中，自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的數(shù)據(jù)預(yù)測(cè)控制目標(biāo)函數(shù)為F(x)，數(shù)據(jù)塊對(duì)象中的神經(jīng)元三層前向神經(jīng)元網(wǎng)格輸入為νi(x)。最后運(yùn)用模糊指向性聚類構(gòu)建大數(shù)據(jù)塊對(duì)象內(nèi)的數(shù)據(jù)庫(kù)及控制系統(tǒng)，最終獲取數(shù)據(jù)挖掘的存儲(chǔ)模型如下式所示

(13)

依據(jù)模糊約束進(jìn)化論，建立基于數(shù)據(jù)挖掘理論的自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取模型，過(guò)程如下式所示：

(14)

通過(guò)對(duì)上式的計(jì)算，獲取自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的自適應(yīng)調(diào)度加權(quán)系數(shù)，系數(shù)中最低的負(fù)載遷移量則如下式所示

(15)

以上，利用上述模型對(duì)模糊約束進(jìn)化的數(shù)據(jù)進(jìn)行自適應(yīng)尋優(yōu)，再基于關(guān)聯(lián)規(guī)則項(xiàng)的引導(dǎo)性融合法來(lái)實(shí)現(xiàn)自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取。

4 仿真研究

為了驗(yàn)證上述存取方法的整體有效性，需對(duì)此方法進(jìn)行仿真測(cè)試。

4.1 仿真環(huán)境與數(shù)據(jù)來(lái)源

采用的操作系統(tǒng)為WindowsXP、程序Visual Studio、平臺(tái)為Eclipse、內(nèi)存為4G、硬盤為120G，仿真軟件為MATLAB。

在Googledatasets(https:∥cloud.google.com/bigquery/public-data/)中，隨機(jī)選取20，000個(gè)應(yīng)用程序的相關(guān)信息，并抽樣選取數(shù)據(jù)樣本。為了使移動(dòng)應(yīng)用程序樣本信息更加均勻分布，在樣本的訓(xùn)練過(guò)程中，使用某個(gè)數(shù)據(jù)集中的移動(dòng)應(yīng)用程序標(biāo)簽，進(jìn)行大塊數(shù)據(jù)屬性的自定義，包括音頻、圖片、視頻、表格、文檔類型，其中圖片數(shù)據(jù)集由10個(gè)大塊數(shù)據(jù)對(duì)象組成，大小為10 MB；視頻數(shù)據(jù)集由10個(gè)大塊數(shù)據(jù)對(duì)象組成，大小為150 MB；表格數(shù)據(jù)集由10個(gè)大塊數(shù)據(jù)對(duì)象組成，大小為160 MB；文檔數(shù)據(jù)集由10個(gè)大塊數(shù)據(jù)對(duì)象組成，大小為60 MB；其它則使用模型默認(rèn)參數(shù)值。

4.2 實(shí)驗(yàn)結(jié)果與分析

分別采用基于數(shù)據(jù)挖掘的方法(方法1)、基于NET的方法(方法2)以及基于傳統(tǒng)關(guān)系型數(shù)據(jù)的方法(方法3)進(jìn)行測(cè)試；

1)在相同的實(shí)驗(yàn)環(huán)境下對(duì)方法1、方法2以及方法3的自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取時(shí)間進(jìn)行測(cè)試，測(cè)試結(jié)果如圖3所示。

圖3 并行存取的存取時(shí)間測(cè)試結(jié)果

分析圖3可知，方法1的大數(shù)據(jù)對(duì)象并行存取時(shí)間要低于方法2和方法3，且能夠?qū)?shù)據(jù)的并行存取時(shí)間維持在20秒左右，與方法2和方法3相比，本文方法較為穩(wěn)定。這主要是因?yàn)榉椒?在對(duì)大數(shù)據(jù)塊對(duì)象進(jìn)行并行存取時(shí)利用數(shù)據(jù)挖掘理論構(gòu)建了自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取模型，并通過(guò)計(jì)算獲取了并行存取的輸入層神經(jīng)元，所以在運(yùn)用該方法對(duì)大數(shù)據(jù)塊對(duì)象進(jìn)行并行存取時(shí)，存取時(shí)間短、并行存取的效率高。

2)在相同的實(shí)驗(yàn)環(huán)境中，對(duì)方法1、方法2以及方法3的自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象并行存取的內(nèi)存占比率進(jìn)行測(cè)試，測(cè)試結(jié)果如圖4所示。

圖4 大數(shù)據(jù)對(duì)象并行存取的內(nèi)存占比率測(cè)試結(jié)果

分析圖4可知，在大數(shù)據(jù)塊對(duì)象的并行存取時(shí)，方法1的內(nèi)存占比率要優(yōu)于方法2以及方法3，雖然方法3在測(cè)試初期的內(nèi)存占比率一度低于方法1，但隨著檢測(cè)次數(shù)的增加，方法3的內(nèi)存占比率呈急速上升趨勢(shì)。這主要是因?yàn)榉椒?在對(duì)自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象進(jìn)行并行存取時(shí)，利用模糊指向性聚類構(gòu)建大數(shù)據(jù)塊對(duì)象內(nèi)的數(shù)據(jù)庫(kù)及控制系統(tǒng)，獲取數(shù)據(jù)挖掘的存儲(chǔ)模型，并將自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象放入模型中進(jìn)行自適應(yīng)尋優(yōu)處理，以此完成自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取，這樣就可以縮短并行存取所用的時(shí)間，降低并行存取的內(nèi)存占比率。

3)根據(jù)上述兩個(gè)測(cè)試結(jié)果對(duì)方法1、方法2及方法3的并行存取正確率進(jìn)行測(cè)試，測(cè)試結(jié)果如圖5所示。

圖5 大數(shù)據(jù)塊對(duì)象并行存取正確率測(cè)試結(jié)果

分析圖5可知，方法1的并行存取正確率要高于方法2和方法3，方法2雖然在測(cè)試初期正確率與方法1基本持平，但隨著測(cè)試次數(shù)的增加，方法2的正確率急速下降，呈現(xiàn)出不穩(wěn)定趨勢(shì)。這主要是因?yàn)榉椒?在進(jìn)行大數(shù)據(jù)塊對(duì)象的并行存取時(shí)，利用數(shù)據(jù)挖掘理論對(duì)數(shù)據(jù)的自適應(yīng)調(diào)度加權(quán)系數(shù)進(jìn)行計(jì)算，獲取系數(shù)中的最低負(fù)載遷移量。運(yùn)用該方法對(duì)大數(shù)據(jù)對(duì)象進(jìn)行并行存取能夠提高存取的正確率，縮短存取時(shí)間。

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

1)針對(duì)傳統(tǒng)方法在對(duì)大數(shù)據(jù)塊對(duì)象進(jìn)行并行存取時(shí)出現(xiàn)的存取時(shí)間長(zhǎng)、內(nèi)存占比高、存取正確低的問(wèn)題，提出基于數(shù)據(jù)挖掘理論的自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取方法。

2)利用聚類算法與數(shù)據(jù)挖掘算法對(duì)大數(shù)據(jù)塊對(duì)象中的數(shù)據(jù)進(jìn)行數(shù)據(jù)缺失值填充以及數(shù)據(jù)分割處理。再利用數(shù)據(jù)挖掘理論計(jì)算偏導(dǎo)函數(shù)，構(gòu)建并行存取模型，其并行存取時(shí)間維持在20秒左右。

3)將自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象放入模型中進(jìn)行自適應(yīng)尋優(yōu)處理，以此完成自適應(yīng)云資源大數(shù)據(jù)塊對(duì)象的并行存取，內(nèi)存占比率最高僅為39%。