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

楊 建，劉述木

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

1 引言

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

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

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

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

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

2.1 DBSCAN算法

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

2)選取初始聚類中心

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

(2)

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

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

(3)

式中

(4)

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

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

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

koptimal=arg maxkP(k)

(5)

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

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

圖2 并行存取過程

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

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

gk+akkoptimal=0

(6)

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

(7)

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

uni(k)=netni(k)

(8)

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

(9)

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

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

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

(10)

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

opij=k*(minj+maxj)-xij

(11)

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

3.2 并行存取

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

(12)

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

(13)

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

(14)

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

(15)

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

4 仿真研究

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

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

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

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

4.2 實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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