楊 建,劉述木
(1.四川省裝備制造業(yè)機器人應用技術工程實驗室,四川 德陽 618000;2.四川大學軟件學院,四川 成都 610065)
網(wǎng)絡上的海量數(shù)據(jù)文件格式不同、復雜程度不同,如何在海量的數(shù)據(jù)文件中自由存取自己需要的數(shù)據(jù),逐漸成為人們的焦點[1]。在傳統(tǒng)的方法滿足不了人們對云資源大塊數(shù)據(jù)處理需求時,提出一種新型的大數(shù)據(jù)塊對象的并行存取方法尤為迫切[2]。
李良[3]等提出基于NET的自適應云資源大數(shù)據(jù)塊對象的存取方法。該方法首先在ASENET平臺上使用C#對大數(shù)據(jù)塊中的數(shù)據(jù)進行編程,再通過ADO-NET對數(shù)據(jù)庫的后臺進行訪問,利用內(nèi)存流對大數(shù)據(jù)塊對象中的數(shù)據(jù)進行讀取,最后啟用通用自定義HTTP請求對大數(shù)據(jù)塊對象中的數(shù)據(jù)進行處理,以此實現(xiàn)對自適應云資源大數(shù)據(jù)塊對象的并行存取。該方法由于在對大數(shù)據(jù)對象進行并行存取時沒有利用數(shù)據(jù)挖掘理論構建自適應云資源大數(shù)據(jù)塊對象的并行存取模型,所以導致并行存取的存取時間長、存取效率低。索劍[4]等提出基于傳統(tǒng)關系型數(shù)據(jù),對大數(shù)據(jù)塊對象中的數(shù)據(jù)進行結(jié)構處理,并將其分為模式與無模式兩個部分,再分別對其進行預處理從而解決數(shù)據(jù)一致性與高效存取的矛盾。最后在同一數(shù)據(jù)庫中對相同數(shù)據(jù)分別進行模式與無模式環(huán)境下的數(shù)據(jù)插入,查詢等操作,以此完成自適應云資源大數(shù)據(jù)塊對象的并行存取。該方法由于在并行存取時沒有對大數(shù)據(jù)對象的數(shù)據(jù)采樣梯度函數(shù)進行計算,獲取大數(shù)據(jù)塊對象的輸出密度導致并行存取的正確率低,內(nèi)存占比高。雷曉勇[5]等提出基于HWS的大數(shù)據(jù)塊對象并行存取方法。該方法首先對常見的存儲格式進行分析,并以分析結(jié)果為基礎構建一個分級的數(shù)據(jù)存儲格式,再利用高級的波形數(shù)據(jù)存儲函數(shù)對大數(shù)據(jù)塊對象中的數(shù)據(jù)進行計算,獲取雙精度的浮點數(shù)據(jù)。最后將其放入HWS中讀取,以此完成自適應云資源大數(shù)據(jù)塊對象的并行存取。該方法由于在并行存取時未能利用數(shù)據(jù)挖掘理論對數(shù)據(jù)的自適應調(diào)度加權系數(shù)進行計算,獲取系數(shù)中的最低負載遷移量,所以導致并行存取的時間長、效率低。
為解決上述并行存取方法中存在的問題,提出基于數(shù)據(jù)挖掘的自適應云資源大數(shù)據(jù)塊對象的并行存取方法,其創(chuàng)新之處在于利用聚類算法對大數(shù)據(jù)塊對象中的數(shù)據(jù)進行缺失值填充后,將完整數(shù)據(jù)放入模型中進行自適應尋優(yōu)處理,保證并行存取的完整度的同時,優(yōu)化存取時間和正確率。
利用聚類算法對大數(shù)據(jù)塊進行數(shù)據(jù)預處理,獲取新的數(shù)據(jù)集。
基于聚類算法(DBSCAN)對數(shù)據(jù)中的缺失值進行填充,過程如圖1所示。
圖1 數(shù)據(jù)填充過程
自適應云資源大數(shù)據(jù)塊對象的原始數(shù)據(jù)中會存在部分的不完整數(shù)據(jù),包括數(shù)據(jù)屬性不完整、缺失值較大等問題。一般情況下,若缺失的屬性值占屬性記錄的大半,那么就要將其從記錄中刪除。若某數(shù)據(jù)的屬性值占比較小,也將其屬性刪除(其中若有數(shù)據(jù)的屬性是獨立的則可以保留),不然會對大數(shù)據(jù)對象的并行存取產(chǎn)生影響。利用刪除屬性策略對大數(shù)據(jù)集中的不完整數(shù)據(jù)進行刪除,輸出數(shù)據(jù)集S以及完整的子集Sc、缺失的數(shù)據(jù)集Si。
將原始數(shù)據(jù)集分為兩個子集后,利用DBSCAN算法對自適應云資源大數(shù)據(jù)塊進行聚類,產(chǎn)生k個簇。
基于產(chǎn)生每個簇的重心,計算缺失數(shù)據(jù)子集中每個屬性記錄與k個簇重心之間的相似度,并將記錄值賦予給它相鄰的簇,利用這個簇的屬性均值填充該記錄的缺失值。若缺失數(shù)據(jù)集中某一記錄的缺失值無法填充就可以刪除此條記錄。填充過后,輸出最終的清洗結(jié)果S′,S′則是由自適應云資源大數(shù)據(jù)塊中完整的數(shù)據(jù)子集Sc以及經(jīng)過填充處理的子集Si組成的。
自適應云資源大數(shù)據(jù)塊中同類數(shù)據(jù)之間存在很多的相似屬性[6],所以要通過對屬性的計算獲取聚類結(jié)果。再基于DBSCAN的缺失清洗算法對聚類結(jié)果進行計算,過程如下:
首先輸入一個給點對象的半徑b以及b區(qū)間(-b鄰域)內(nèi)的若干數(shù)據(jù)個數(shù)。
1)將自適應云資源大數(shù)據(jù)塊中的數(shù)據(jù)集S分為兩個子集,完整的記錄子集為Sc(無任何屬性含缺失值)及缺失的數(shù)據(jù)集Si(屬性中有一個或多個缺失值)。
2)利用DBSCAN算法計算完整的數(shù)據(jù)子集Sc,選取自適應云資源大數(shù)據(jù)塊的核心對象以及-b鄰域,依據(jù)直接密度可達、密度可達、密度相連的方法對數(shù)據(jù)子集中的對象進行聚類并在聚類后計算每個簇中對象的均值,以此使目標函數(shù)值達到最小。
3)從自適應云資源大數(shù)據(jù)塊的非完整數(shù)據(jù)子集Si中按順序提取屬性記錄,計算記錄與Sc的幾個類中任一類的相似度,選出相似值為最大的記錄,把該記錄標記為Xi(i=0,1,2,…,k)類,重復上述過程一直持續(xù)到數(shù)據(jù)子集為空。
4)依據(jù)非完整數(shù)據(jù)子集的記錄分配k簇,利用下式對記錄缺失值進行處理
(1)
由于不完全數(shù)據(jù)子集Si中的每條記錄都被賦予了最接近它的簇,而且不完全數(shù)據(jù)子集中的每條記錄和被賦予的簇都有許多相似的屬性,因此要使被賦予的簇具有完整的屬性,就需要用它的平均值來填充[7]。式中,Ai代表數(shù)據(jù)集中缺失值被分配的第i個完整記錄的數(shù)據(jù)值,n為屬性的記錄總數(shù)。
根據(jù)聚類算法可知,DBSCAN的缺失值填充算法對空間的需求不是很大,這主要是因為清洗數(shù)據(jù)時只需要存儲數(shù)據(jù)集,其空間的復雜度為O(n-m+k),n為自適應云資源大數(shù)據(jù)塊數(shù)據(jù)集中的記錄數(shù)目[8],m為缺失值的記錄個數(shù),k為簇的數(shù)目。由于本算法在時間上同樣沒有什么需求,所以其時間的復雜度為O((n-m)kt1),(n-m)是自適應云資源大數(shù)據(jù)塊數(shù)據(jù)集中的完整記錄數(shù)目,t是需要進行迭代的次數(shù)。
根據(jù)上述過程,完成自適應云資源大數(shù)據(jù)塊內(nèi)的數(shù)據(jù)屬性缺失值的填充。
基于填充過缺失值的自適應云資源大數(shù)據(jù)塊的完整數(shù)據(jù)集,采用均值聚類算法對數(shù)據(jù)集進行數(shù)據(jù)分割。
首先,設定數(shù)據(jù)集的給定聚類數(shù)為k,再基于算法的初值敏感問題優(yōu)化初始中心的k-均值算法,分割過程如下所示:
1)確定分割區(qū)域
在填充過缺失值的數(shù)據(jù)集中設定一個半徑R,再以此為基礎為每個數(shù)據(jù)確認一個球形鄰域,計算落在鄰域內(nèi)的數(shù)據(jù)個數(shù)。若鄰域內(nèi)的體積與鄰域內(nèi)數(shù)據(jù)個數(shù)的商不小于空間總體積與數(shù)據(jù)總個數(shù)的商,就可以認定該數(shù)據(jù)在高密度區(qū)域內(nèi)。
2)選取初始聚類中心
設高密度區(qū)域內(nèi)有m*個數(shù)據(jù),首先隨機選定一個數(shù)據(jù)作為第一中心y1;再選定距離y1最遠的數(shù)據(jù)作為第二中心y2;選定一個數(shù)據(jù)yj作為第三中心,這時yj要滿足下式
(2)
根據(jù)上述標準,繼續(xù)選定m4,…,mk,找出高密度區(qū)域內(nèi)的k個中心m1,m2,…,mk。
依據(jù)設定的P指標計算下式
(3)
式中
(4)
其中,m為自適應云資源大數(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范圍,重復上述計算獲取最終的P指標。
最后利用下式,對數(shù)據(jù)進行最終分割
koptimal=arg maxkP(k)
(5)
基于關聯(lián)規(guī)則項的引導將分割后自適應云資源大數(shù)據(jù)塊對象進行并行存取。過程如圖2所示。
圖2 并行存取過程
依據(jù)隨機概率的密度分布[11-12],對自適應云資源大數(shù)據(jù)塊對象的數(shù)據(jù)實體節(jié)點與Sink節(jié)點進行均衡控制,并對其關系進行偏導函數(shù)求解,過程如下式所示
gk+akkoptimal=0
(6)
建立基于數(shù)據(jù)挖掘理論的自適應云資源大數(shù)據(jù)塊對象的并行存取模型,首先要獲取存取輸入層神經(jīng)元,如下式所示
(7)
大數(shù)據(jù)塊對象中的數(shù)量小的端口節(jié)點負載神經(jīng)元狀態(tài)為下式所示
uni(k)=netni(k)
(8)
大數(shù)據(jù)塊對象數(shù)據(jù)存取的輸入層神經(jīng)元輸出如下式所示
(9)
式中,uni(k)為自適應云資源大數(shù)據(jù)塊對象數(shù)據(jù)流量負載的邊節(jié)點向量,采用控制律構建自適應云資源大數(shù)據(jù)塊對象的數(shù)據(jù)調(diào)度控制模型。
把大數(shù)據(jù)塊對象中最大或最小的數(shù)據(jù)神經(jīng)元、,映射成隨機生成的T個初始解,求解自適應云資源大數(shù)據(jù)對象的數(shù)據(jù)采樣梯度函數(shù),下式表示
xij=xmin,j+rand(0,1)(xmax,j-xmin,j)
(10)
利用關聯(lián)規(guī)則對自適應云資源大數(shù)據(jù)對象進行并行存取,獲取的輸出密度如下式所示
opij=k*(minj+maxj)-xij
(11)
以輸出密度為約束條件,即可得到數(shù)據(jù)的最佳尋優(yōu)軌跡。
采用模糊約束法對數(shù)據(jù)存儲路徑進行尋優(yōu),在自適應云資源大數(shù)據(jù)塊對象的并行存取中,利用柯西的不等式理論計算數(shù)據(jù)塊對象的二階梯度,獲取Δ2F(x),再利用多個非線性成分的聯(lián)合統(tǒng)計法對大數(shù)據(jù)塊對象中的數(shù)據(jù)進行高維空間重構,最后結(jié)合模糊聚類對大數(shù)據(jù)塊內(nèi)的數(shù)據(jù)進行自適應分類處理,獲取數(shù)據(jù)存取的負載,如下式所示:
(12)
式中,自適應云資源大數(shù)據(jù)塊對象的數(shù)據(jù)預測控制目標函數(shù)為F(x),數(shù)據(jù)塊對象中的神經(jīng)元三層前向神經(jīng)元網(wǎng)格輸入為νi(x)。最后運用模糊指向性聚類構建大數(shù)據(jù)塊對象內(nèi)的數(shù)據(jù)庫及控制系統(tǒng),最終獲取數(shù)據(jù)挖掘的存儲模型如下式所示
(13)
依據(jù)模糊約束進化論,建立基于數(shù)據(jù)挖掘理論的自適應云資源大數(shù)據(jù)塊對象的并行存取模型,過程如下式所示:
(14)
通過對上式的計算,獲取自適應云資源大數(shù)據(jù)塊對象的自適應調(diào)度加權系數(shù),系數(shù)中最低的負載遷移量則如下式所示
(15)
以上,利用上述模型對模糊約束進化的數(shù)據(jù)進行自適應尋優(yōu),再基于關聯(lián)規(guī)則項的引導性融合法來實現(xiàn)自適應云資源大數(shù)據(jù)塊對象的并行存取。
為了驗證上述存取方法的整體有效性,需對此方法進行仿真測試。
采用的操作系統(tǒng)為WindowsXP、程序Visual Studio、平臺為Eclipse、內(nèi)存為4G、硬盤為120G,仿真軟件為MATLAB。
在Googledatasets(https:∥cloud.google.com/bigquery/public-data/)中,隨機選取20,000個應用程序的相關信息,并抽樣選取數(shù)據(jù)樣本。為了使移動應用程序樣本信息更加均勻分布,在樣本的訓練過程中,使用某個數(shù)據(jù)集中的移動應用程序標簽,進行大塊數(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;其它則使用模型默認參數(shù)值。
分別采用基于數(shù)據(jù)挖掘的方法(方法1)、基于NET的方法(方法2)以及基于傳統(tǒng)關系型數(shù)據(jù)的方法(方法3)進行測試;
1)在相同的實驗環(huán)境下對方法1、方法2以及方法3的自適應云資源大數(shù)據(jù)塊對象的并行存取時間進行測試,測試結(jié)果如圖3所示。
圖3 并行存取的存取時間測試結(jié)果
分析圖3可知,方法1的大數(shù)據(jù)對象并行存取時間要低于方法2和方法3,且能夠?qū)?shù)據(jù)的并行存取時間維持在20秒左右,與方法2和方法3相比,本文方法較為穩(wěn)定。這主要是因為方法1在對大數(shù)據(jù)塊對象進行并行存取時利用數(shù)據(jù)挖掘理論構建了自適應云資源大數(shù)據(jù)塊對象的并行存取模型,并通過計算獲取了并行存取的輸入層神經(jīng)元,所以在運用該方法對大數(shù)據(jù)塊對象進行并行存取時,存取時間短、并行存取的效率高。
2)在相同的實驗環(huán)境中,對方法1、方法2以及方法3的自適應云資源大數(shù)據(jù)塊對象并行存取的內(nèi)存占比率進行測試,測試結(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在對自適應云資源大數(shù)據(jù)塊對象進行并行存取時,利用模糊指向性聚類構建大數(shù)據(jù)塊對象內(nèi)的數(shù)據(jù)庫及控制系統(tǒng),獲取數(shù)據(jù)挖掘的存儲模型,并將自適應云資源大數(shù)據(jù)塊對象放入模型中進行自適應尋優(yōu)處理,以此完成自適應云資源大數(shù)據(jù)塊對象的并行存取,這樣就可以縮短并行存取所用的時間,降低并行存取的內(nèi)存占比率。
3)根據(jù)上述兩個測試結(jié)果對方法1、方法2及方法3的并行存取正確率進行測試,測試結(jié)果如圖5所示。
圖5 大數(shù)據(jù)塊對象并行存取正確率測試結(jié)果
分析圖5可知,方法1的并行存取正確率要高于方法2和方法3,方法2雖然在測試初期正確率與方法1基本持平,但隨著測試次數(shù)的增加,方法2的正確率急速下降,呈現(xiàn)出不穩(wěn)定趨勢。這主要是因為方法1在進行大數(shù)據(jù)塊對象的并行存取時,利用數(shù)據(jù)挖掘理論對數(shù)據(jù)的自適應調(diào)度加權系數(shù)進行計算,獲取系數(shù)中的最低負載遷移量。運用該方法對大數(shù)據(jù)對象進行并行存取能夠提高存取的正確率,縮短存取時間。
1)針對傳統(tǒng)方法在對大數(shù)據(jù)塊對象進行并行存取時出現(xiàn)的存取時間長、內(nèi)存占比高、存取正確低的問題,提出基于數(shù)據(jù)挖掘理論的自適應云資源大數(shù)據(jù)塊對象的并行存取方法。
2)利用聚類算法與數(shù)據(jù)挖掘算法對大數(shù)據(jù)塊對象中的數(shù)據(jù)進行數(shù)據(jù)缺失值填充以及數(shù)據(jù)分割處理。再利用數(shù)據(jù)挖掘理論計算偏導函數(shù),構建并行存取模型,其并行存取時間維持在20秒左右。
3)將自適應云資源大數(shù)據(jù)塊對象放入模型中進行自適應尋優(yōu)處理,以此完成自適應云資源大數(shù)據(jù)塊對象的并行存取,內(nèi)存占比率最高僅為39%。