基于隨機矩陣分解的大數(shù)據(jù)無向壓縮算法設(shè)計

高 勇,李恒武,王辰陽

(信息工程大學(xué),河南 鄭州 450001)

1 引言

伴隨科學(xué)技術(shù)的發(fā)展及網(wǎng)絡(luò)的現(xiàn)實需求,各類網(wǎng)絡(luò)系統(tǒng)數(shù)據(jù)量呈直線增長,儲存空間占比不斷增加[1],對后續(xù)網(wǎng)絡(luò)建設(shè)與運行維護(hù)產(chǎn)生很大影響。數(shù)據(jù)庫較大、備份耗時較長,即便數(shù)據(jù)庫磁盤空間得到提升,但依舊無法匹配數(shù)據(jù)增長速率,嚴(yán)重影響系統(tǒng)運行平穩(wěn)性,數(shù)據(jù)的查詢與儲存效率也面臨嚴(yán)峻考驗[2]。

數(shù)據(jù)壓縮技術(shù)的目標(biāo)是降低文件所占儲存空間的同時不損失重要數(shù)據(jù),相關(guān)領(lǐng)域也從不同層面研究,例如,文獻(xiàn)[3]運用相鄰軌跡點經(jīng)緯度更改走向確定行駛特征點,保存時序信息并壓縮停滯點,利用采樣法保留軌跡點,完成軌跡信息壓縮。但壓縮過程中沒有消除冗余信息干擾,極易產(chǎn)生壓縮失效問題;文獻(xiàn)[4]利用空間變換技術(shù)分析數(shù)據(jù)相關(guān)性,通過時間相關(guān)性感知算法壓縮處理空間系數(shù),降低無用數(shù)據(jù)的空間占用率。但方法運算時間過長,無法保障數(shù)據(jù)壓縮的即時性。

為解決當(dāng)前數(shù)據(jù)壓縮方法的不足,引入無向壓縮概念,將數(shù)據(jù)設(shè)置為對稱結(jié)構(gòu),有效提升數(shù)據(jù)壓縮與解壓精度,提出一種基于隨機矩陣分解的大數(shù)據(jù)無向壓縮算法。通過創(chuàng)建隨機矩陣分解模型,有效剔除大數(shù)據(jù)中不相關(guān)的冗余信息,利用數(shù)據(jù)歸約技術(shù)明確數(shù)據(jù)屬性,通過無向旋轉(zhuǎn)門算法完成數(shù)據(jù)無向壓縮目標(biāo)。與傳統(tǒng)方法相比,本文方法具備更優(yōu)的壓縮效率與準(zhǔn)確性。

2 隨機矩陣分解下大數(shù)據(jù)可靠挖掘

網(wǎng)絡(luò)大數(shù)據(jù)種類繁多,包含大量不相干數(shù)據(jù),利用隨機矩陣分解模型,挖掘海量大數(shù)據(jù)內(nèi)被隱藏的可靠信息[5,6],剔除冗余數(shù)據(jù),增強數(shù)據(jù)無向壓縮整體質(zhì)量。若在網(wǎng)絡(luò)系統(tǒng)內(nèi)擁有N個用戶與M個項目,組成用戶集U={u1,u2,…,un}和項目集I={i1,i2,…,im}。

隨機矩陣分解模型給予用戶與項目一種隱含特征矢量,分別記作

(1)

(2)

將已觀測到的可靠數(shù)據(jù)條件概率計算過程記作

(3)

在隨機概率矩陣分解模型內(nèi)引入用戶相鄰數(shù)據(jù),用戶u的特征矢量用來描述其相鄰矢量的加權(quán)和,Nu為用戶u的相鄰用戶,Sui為用戶u和用戶i的項目偏好相似度,歸一化處理Sui,挖掘網(wǎng)絡(luò)中隱含可靠數(shù)據(jù),過程為

(4)

3 基于無向旋轉(zhuǎn)門的大數(shù)據(jù)無向壓縮算法設(shè)計

利用以上過程消除冗余數(shù)據(jù)后,采用無向圖即對稱稀疏矩陣,定義數(shù)據(jù)為對稱型結(jié)構(gòu),降低數(shù)據(jù)壓縮難度,獲得更為簡單快捷的壓縮方式。在此基礎(chǔ)上,提出基于無向旋轉(zhuǎn)門的大數(shù)據(jù)無向壓縮算法,下面為方法詳細(xì)推理過程。

3.1 大數(shù)據(jù)歸約處理

數(shù)據(jù)歸約為在數(shù)據(jù)自身含義前提下,探尋目標(biāo)特性,確保數(shù)據(jù)原始面貌的同時減小數(shù)據(jù)規(guī)模。假設(shè)大數(shù)據(jù)集C內(nèi)包含n個樣本,各個樣本中具備k項變量,將初始數(shù)據(jù)矩陣記作:

(5)

主成分分析法為一種應(yīng)用較多的特征歸約算法,利用不同變量的線性組合頂替初始變量,產(chǎn)生的線性組合間互相獨立、數(shù)量小于初始變量,同時涵蓋大量初始變量信息[7],完成恰當(dāng)?shù)臄?shù)據(jù)歸約處理。算法共分為以下五個步驟:

第一,標(biāo)準(zhǔn)化大數(shù)據(jù)樣本,便于統(tǒng)一量綱;

第二,計算變量協(xié)方差矩陣D

(6)

(7)

式中,x′為線性變換后的變量,T是變換指數(shù)。

第三,推算以上協(xié)方差矩陣Dk×k的特征參變量λ1,λ2,…,λk,及其相應(yīng)的正交化單位特征矢量ζ1,ζ2,…,ζk。矩陣Dk×k內(nèi)和前m個最大特征值相對的m個特征矢量,可描述初始大數(shù)據(jù)從k維空間變換至的m維空間,且變換后的m維空間內(nèi)特征兩兩之間互不相等;

第四,推導(dǎo)最大特征值和與全部特征值和的比值,如式(8)所示。比值結(jié)果采用百分比形式,命名為累積方差貢獻(xiàn)率。該值展現(xiàn)出前m個主成分在方差總和內(nèi)的投影。若投影比率較高,則涵蓋m個特征的子集是k維空間的初步估計。

(8)

第五,計算上述特征矢量作為系數(shù)的m個主成分解析式

Yi=ζ1Xj

(9)

其中,Y為主成分元素,i、j均為數(shù)據(jù)集個數(shù),ζ1表示正交化單位特征矢量。

通過式(9)的主成分解析式獲得各個樣本在每個主成分上的得分,獲得全新的數(shù)據(jù)歸約矩陣。

3.2 大數(shù)據(jù)的無向壓縮

無向旋轉(zhuǎn)門算法作為利用直線擬合的數(shù)據(jù)壓縮方法,其中的最高準(zhǔn)許偏差可獲得最長的直線趨勢[8-10],優(yōu)化數(shù)據(jù)壓縮性能與修復(fù)能力。無向旋轉(zhuǎn)門算法的壓縮過程如圖1所示。橫坐標(biāo)表示數(shù)據(jù)點時間坐標(biāo),縱坐標(biāo)是數(shù)據(jù)點的數(shù)值。若ΔE是壓縮誤差,將數(shù)據(jù)點Y0看作初始點,將距離數(shù)據(jù)點Y0的上下兩個點作為支撐點[11],構(gòu)建一個虛擬門。伴隨數(shù)據(jù)點的增多,門會自動旋轉(zhuǎn)開啟,其長度也可無向無限延伸,門開啟后會無法閉合。若兩扇門的內(nèi)角總和低于180°,繼續(xù)旋轉(zhuǎn)動作,內(nèi)角總和高于180°,終止操作,儲存前一個數(shù)據(jù)點,從該數(shù)據(jù)點開始重新壓縮數(shù)據(jù),圖1內(nèi)的儲存點為Y0、Y3和Y4。

圖1 無向旋轉(zhuǎn)門算法壓縮過程

兩扇門平行時數(shù)據(jù)的精度取決于無向旋轉(zhuǎn)門算法的壓縮誤差ΔE范圍,壓縮誤差ΔE設(shè)定的越高,原數(shù)據(jù)點個數(shù)越少,壓縮的數(shù)據(jù)量隨之減少[12],壓縮性能越優(yōu)秀,反之壓縮效果越差。

(10)

(11)

(12)

(13)

壓縮比用來衡量壓縮算法對數(shù)據(jù)的壓縮性能,壓縮比數(shù)值越高,表明壓縮成效越優(yōu),是一種硬性壓縮評估標(biāo)準(zhǔn)[13]。其它三種解壓縮誤差均不同層面地展現(xiàn)了數(shù)據(jù)的失真度,也就是數(shù)據(jù)解壓縮后的數(shù)據(jù)精度,誤差值越小,表明算法無向壓縮準(zhǔn)確性越高[14]。均方誤差的計算最簡便且計算量小,將其設(shè)定為本文的壓縮評估指標(biāo),在描述數(shù)據(jù)壓縮能力時節(jié)約運算開銷。

網(wǎng)絡(luò)正常運行時,把數(shù)據(jù)實際值和解壓縮值之間的期望偏差δ看作輸入值[15],真實平均絕對誤差是輸出值,二者相減獲得的差值ε為反饋值,利用負(fù)反饋調(diào)節(jié)壓縮誤差。參變量ΔE為一個可以隨機改變的值,僅需設(shè)定上、下臨界值,就能按照真實壓縮狀況完成動態(tài)調(diào)節(jié)。

如果Emax、Emin依次為壓縮誤差ΔE的上、下臨界值,D是壓縮誤差調(diào)節(jié)參變量,τ表示數(shù)據(jù)解壓縮真實偏差和期望偏差的誤差容差,y1～yn是待壓縮數(shù)據(jù)集,壓縮過程如下:

①壓縮y1～yn數(shù)據(jù)前,初始化壓縮參變量。Emax、Emin可自主設(shè)置,D、τ需要提前設(shè)置;

②假設(shè)T為大數(shù)據(jù)無向壓縮算法容許的最大時間間隔,從待壓縮數(shù)據(jù)內(nèi)提取數(shù)據(jù)點yi,若此點和上個儲存點的時間間隔大于等于T,直接儲存上個數(shù)據(jù)點yi-1,無需使用無向旋轉(zhuǎn)門分析,反之采取無向旋轉(zhuǎn)門壓縮;

③推算數(shù)據(jù)點yi位置無向旋轉(zhuǎn)門兩扇門的斜率kup、kdown,若兩扇門為平行狀態(tài),那么儲存數(shù)據(jù)點yi-1,同時將該點看作全新的壓縮初始點,反之舍掉數(shù)據(jù)點yi;

⑤按照差值ε的狀況,調(diào)節(jié)壓縮誤差ΔE。如果0≤ε<δ·t,證明偏差處于容許偏差范圍,無需實施調(diào)節(jié);若ε≥δ·t,證明數(shù)據(jù)誤差值偏高,計算得到的平均壓縮誤差偏小,ΔE值偏小,要在Emax取值范圍內(nèi)擴(kuò)大ΔE,過程為

(14)

⑥若-δ·t<ε<0,證明數(shù)據(jù)誤差偏小,平均壓縮偏差較大,ΔE值較大,丟棄了很多初始數(shù)據(jù),要在Emin范圍中縮小ΔE值,記作

(15)

假設(shè)ε沒發(fā)生以上狀況,證明解壓縮數(shù)據(jù)失真度高,返回第一步重新計算。

⑦動態(tài)調(diào)節(jié)壓縮誤差后,折回第二步使用全新的ΔE值完成壓縮任務(wù),持續(xù)迭代直至誤差ε在可接受范圍,實現(xiàn)大數(shù)據(jù)無向壓縮。

4 仿真研究

4.1 仿真設(shè)置

利用仿真驗證本文壓縮算法可靠性,實驗平臺是面向?qū)ο蟮拈_源仿真平臺OMNeT++3.3,在一個500×500網(wǎng)絡(luò)監(jiān)測區(qū)域任意部署400個數(shù)據(jù)節(jié)點,節(jié)點采集的各數(shù)據(jù)長度是3byte。局域網(wǎng)絡(luò)包括一個基站、3個分簇和各分簇中的7個采集節(jié)點,如表1所示。將文獻(xiàn)[3]滑動窗口法與文獻(xiàn)[4]時空相關(guān)法作為對比方法,比較三者壓縮性能優(yōu)劣。

表1 簇頭與分簇采集節(jié)點編號

4.2 不同算法壓縮比情況

圖2為三種算法相同實驗環(huán)境下的壓縮比情況。

圖2 三種方法數(shù)據(jù)壓縮比分析

從圖2看出,本文算法的壓縮比要顯著高于兩個對比方法,壓縮能力更好。這是由于本文采用隨機矩陣分解策略最大限度剔除不相關(guān)信息,保證海量大數(shù)據(jù)信息準(zhǔn)確性,伴隨節(jié)點采集數(shù)據(jù)量的增多,數(shù)據(jù)之間的時間相關(guān)性越來越大,本文方法可描述較多初始數(shù)據(jù),壓縮比也隨之提高,最終趨于穩(wěn)定,展現(xiàn)出較強的數(shù)據(jù)壓縮實用性。

4.3 不同算法數(shù)據(jù)壓縮節(jié)點能耗情況

數(shù)據(jù)壓縮時會產(chǎn)生額外的節(jié)點計算能耗,將節(jié)點能耗當(dāng)作衡量大數(shù)據(jù)壓縮算法優(yōu)劣的指標(biāo)。實驗前預(yù)先設(shè)置節(jié)點的初始能量、收發(fā)功率、數(shù)據(jù)收發(fā)速度等參數(shù),按照數(shù)據(jù)分組長度獲得節(jié)點剩余能量。另外,按照節(jié)點原始能量和總節(jié)點數(shù)量推算網(wǎng)絡(luò)原始總能量,原始總能量和網(wǎng)絡(luò)剩余能量的差就是網(wǎng)絡(luò)數(shù)據(jù)壓縮總能耗,總能耗和網(wǎng)絡(luò)節(jié)點數(shù)量相除就是節(jié)點的平均能耗。

仿真中節(jié)點總數(shù)是150,節(jié)點初始能量為2J,發(fā)射功率是0.07W,接收功率為0.09W。三種算法數(shù)據(jù)壓縮節(jié)點平均能耗對比結(jié)果如圖3所示。

圖3 三種算法節(jié)點平均能耗分析

從圖3可知,節(jié)點數(shù)據(jù)采集量增多時,網(wǎng)絡(luò)傳輸數(shù)據(jù)量也慢慢變多,因此三種方法的節(jié)點平均能耗都展現(xiàn)出逐漸上升趨勢,但是本文算法節(jié)點平均能耗小于兩個文獻(xiàn)方法,可在實現(xiàn)數(shù)據(jù)無向壓縮的同時,大幅降低網(wǎng)絡(luò)數(shù)據(jù)傳輸與壓縮能耗,延長網(wǎng)絡(luò)生命周期。

4.4 不同算法的均方誤差情況

相關(guān)度值呈現(xiàn)出矢量變化規(guī)律的相似性,數(shù)據(jù)流相關(guān)度越大,變化概率越相近。即便是無向壓縮模式,若系數(shù)低于臨界值采取壓縮處理,就會產(chǎn)生壓縮誤差。以式(11)的均方誤差為例,分析三種方法數(shù)據(jù)壓縮誤差情況,結(jié)果如圖4所示。

圖4 數(shù)據(jù)壓縮均方誤差對比

由此看出,滑動串口法的均方誤差值最高,時空相關(guān)法次之,本文方法均方差最小。這是因為本文方法利用無向旋轉(zhuǎn)門算法改進(jìn)數(shù)據(jù)壓縮與修復(fù)能力,降低了壓縮時產(chǎn)生的數(shù)據(jù)偏差。

4.5 數(shù)據(jù)壓縮效率對比

圖5的數(shù)據(jù)壓縮時間對比中,三種方法的壓縮時長伴隨節(jié)點數(shù)量的增多而變大,本文方法較比兩個文獻(xiàn)方法壓縮時間最短,且節(jié)點量越多壓縮時間的優(yōu)勢越明顯,極大增強數(shù)據(jù)壓縮時效性,擁有更好的數(shù)據(jù)壓縮能力。

圖5 數(shù)據(jù)壓縮時間對比

5 結(jié)論

計算機網(wǎng)絡(luò)中的大數(shù)據(jù)擁有較多時間與空間冗余信息,怎樣有效改進(jìn)網(wǎng)絡(luò)資源受限現(xiàn)狀,增強網(wǎng)絡(luò)帶寬與生命周期是當(dāng)前互聯(lián)網(wǎng)研究的重要問題。本文提出的基于隨機矩陣分解的大數(shù)據(jù)無向壓縮算法,能夠在不丟失可靠數(shù)據(jù)前提下有效去除大數(shù)據(jù)多余信息,提升網(wǎng)絡(luò)數(shù)據(jù)傳輸、存儲和處理效率,降低節(jié)點功耗,具有極高實用性。