基于元數(shù)據(jù)關(guān)聯(lián)特征的交互式數(shù)據(jù)快速查詢

鄧 斌，陳會平，李凱勇

(1. 四川工業(yè)科技學(xué)院電子信息與計算機(jī)工程學(xué)院，四川 德陽 618500；2. 青海民族大學(xué)物理與電子信息工程學(xué)院，青海 西寧 810007)

1 引言

網(wǎng)絡(luò)通信技術(shù)的成熟讓數(shù)據(jù)傳輸技術(shù)獲得較大提升，現(xiàn)階段數(shù)據(jù)傳輸容量與速率均有明顯改進(jìn)，但人們對數(shù)據(jù)傳輸準(zhǔn)確度和效率也有了更高要求[1]。在數(shù)據(jù)傳輸方面呈現(xiàn)出的絕對優(yōu)勢，逐步得到市場青睞，在大數(shù)據(jù)領(lǐng)域中同樣得到有效的應(yīng)用。當(dāng)前生活的諸多方面都依賴實時應(yīng)用，如利用社交軟件更新動態(tài)、在線購物等，所以提升大數(shù)據(jù)分析和查詢效果、加強(qiáng)查詢性能與速率相當(dāng)重要。在服務(wù)器軟件和數(shù)據(jù)庫配置等條件固定狀況下，傳統(tǒng)查詢模式伴隨數(shù)據(jù)量持續(xù)增多，查詢效率不容樂觀，響應(yīng)時間也越來越長[2]，設(shè)計一種對不同數(shù)據(jù)源處理大數(shù)據(jù)且交互式關(guān)聯(lián)查詢數(shù)據(jù)方法是十分必要的。

關(guān)于數(shù)據(jù)查詢問題，文獻(xiàn)[3]提出一種數(shù)據(jù)統(tǒng)計查詢自適應(yīng)加權(quán)方法。在數(shù)據(jù)集特征二值化前得到統(tǒng)計信息，采用查詢向量的哈希特征替代二值編碼計算權(quán)重值。利用數(shù)據(jù)集統(tǒng)計信息、查詢向量和數(shù)據(jù)庫二值編碼計算權(quán)重值，防止由二值化引發(fā)的原始數(shù)據(jù)信息大量丟失，保留查詢圖像差異。但該方法計算權(quán)重值消耗時間較長，無法完成高效率查詢?nèi)蝿?wù)。文獻(xiàn)[4]設(shè)計一種海量數(shù)據(jù)上有效的top-k Skyline查詢方法。首先對表執(zhí)行預(yù)排序操作，保證預(yù)排序表的元組按照對有序列表的round-robin掃描的順序排列，并利用對預(yù)排序表的順序掃描來獲得候選元組，最后計算候選元組的支配分?jǐn)?shù)并返回結(jié)果，完成數(shù)據(jù)查詢。但該方法在數(shù)據(jù)查詢時沒有充分考慮數(shù)據(jù)庫中的異常數(shù)據(jù)，導(dǎo)致計算結(jié)果精度較低，降低了查準(zhǔn)率。

以上方面均存在不同程度缺陷，為此本文提出一種基于元數(shù)據(jù)關(guān)聯(lián)特征的交互式數(shù)據(jù)快速查詢方法。在探究大數(shù)據(jù)交互式過程前提下，運用并行抽樣算法分析元數(shù)據(jù)關(guān)聯(lián)性，采用差分累積函數(shù)在相空間重構(gòu)中組建高維相空間，得到元數(shù)據(jù)關(guān)聯(lián)差分累積函數(shù)特征，實現(xiàn)精準(zhǔn)有效的交互式數(shù)據(jù)快速查詢。

2 交互式數(shù)據(jù)預(yù)處理過程

大數(shù)據(jù)條件下，人們總是面臨信息過載的難題，數(shù)據(jù)挖掘是在海量數(shù)據(jù)內(nèi)獲得所需知識的有效途徑，但傳統(tǒng)數(shù)據(jù)挖掘架構(gòu)是將機(jī)器當(dāng)作中心，知識經(jīng)驗豐富的數(shù)據(jù)科學(xué)家僅能局限地加入模型建立過程[5]。另外，傳統(tǒng)方法的數(shù)據(jù)挖掘模式不能快速回饋中間結(jié)果給用戶，參變量調(diào)整速率較慢，造成不必要的資源耗費。傳統(tǒng)數(shù)據(jù)挖掘架構(gòu)如圖1所示。

圖1 傳統(tǒng)數(shù)據(jù)挖掘架構(gòu)圖

為了讓用戶可以更為方便高效的參加數(shù)據(jù)挖掘過程，增強(qiáng)良好使用體驗，設(shè)計一種交互式數(shù)據(jù)挖掘架構(gòu)，具體參見圖2。所提方案在數(shù)據(jù)預(yù)處理、模型訓(xùn)練和結(jié)果獲取三個階段都提供了交互支持。用戶能夠根據(jù)自身需求選擇是否加入數(shù)據(jù)挖掘過程，如果用戶選擇不加入，此架構(gòu)和傳統(tǒng)數(shù)據(jù)挖掘過程是相同的。

圖2 交互式數(shù)據(jù)挖掘架構(gòu)圖

交互式數(shù)據(jù)挖掘使用分布式設(shè)計理念，把數(shù)據(jù)集分割成多個小數(shù)據(jù)片，按照用戶設(shè)置的數(shù)據(jù)處理行為，對各個數(shù)據(jù)片都裝載處理邏輯，以便很好的完成處理任務(wù)。為提升交互式數(shù)據(jù)處理速率，并節(jié)約計算資源，在程序碰到不能處理的異常數(shù)據(jù)時，處理節(jié)點會把異常數(shù)據(jù)傳輸?shù)疆惓?shù)據(jù)收集節(jié)點中，再繼續(xù)處理后續(xù)數(shù)據(jù)。在真實操作中，按照業(yè)務(wù)需求差異[6]，異常數(shù)據(jù)有可能被丟棄或修改，架構(gòu)會產(chǎn)生兩個結(jié)果集：只包含正常交互式數(shù)據(jù)的結(jié)果集和異常數(shù)據(jù)被修改后的結(jié)果集，如圖3所示。

圖3 異常數(shù)據(jù)預(yù)處理結(jié)構(gòu)

交互式數(shù)據(jù)完成預(yù)處理后可獲得特征矢量集合，用戶選擇待運行算法同時設(shè)定模型觀測點。架構(gòu)把用戶設(shè)定變換成代碼片引入算法內(nèi)，將整理后的算法文件傳輸?shù)矫總€節(jié)點。當(dāng)節(jié)點運行到觀測點時，將中間結(jié)果進(jìn)行抽樣得到的觀測集展現(xiàn)于用戶界面中。在大數(shù)據(jù)背景下，儲存算法各個步驟的中間結(jié)果會耗費大量資源，架構(gòu)使用按需規(guī)劃方法，在用戶無法設(shè)置觀測點的狀況下，架構(gòu)不會保存中間結(jié)果。

初始數(shù)據(jù)屬性是按照用戶對業(yè)務(wù)的理解獲得的，是用戶比較熟悉的架構(gòu)，算法內(nèi)的數(shù)據(jù)集是對初始數(shù)據(jù)采取一系列處理所組建的，其數(shù)據(jù)維度要遠(yuǎn)高于初始數(shù)據(jù)屬性，是用戶無法觀測的架構(gòu)。在算法生成的結(jié)果集合內(nèi)，對用戶興趣結(jié)果進(jìn)行溯源，便于用戶明確初始數(shù)據(jù)和結(jié)果的相對關(guān)聯(lián)，對數(shù)據(jù)理解更加透徹。為完成此類溯源模式，要保存記錄級別的依附關(guān)聯(lián)[7]。操作數(shù)據(jù)過程中，將操作輸入與輸出依次當(dāng)作唯一標(biāo)記，同時儲存成輸入輸出標(biāo)識表。溯源僅需把每個階段的標(biāo)識表連接即能得到初始數(shù)據(jù)。

3 基于并行抽樣的元數(shù)據(jù)關(guān)聯(lián)性分析

以上交互式數(shù)據(jù)預(yù)處理過程可提供給用戶良好操作體驗，同時獲得準(zhǔn)確的元數(shù)據(jù)關(guān)聯(lián)分析結(jié)果，首先使用Map Reduce編程模型對元數(shù)據(jù)進(jìn)行操作處理，明確元數(shù)據(jù)間隱含關(guān)系。

Map Reduce編程模型利用分布式思路，將元數(shù)據(jù)集分發(fā)至一個主節(jié)點管理下的每個分節(jié)點內(nèi)，令其一起完成處理任務(wù)，合并每個分節(jié)點的中間結(jié)果，獲取最終處理結(jié)果[8]，具體處理結(jié)構(gòu)如圖4所示。

圖4 Map Reduce處理元數(shù)據(jù)集

該模型具備兩個關(guān)鍵函數(shù)，通過用戶進(jìn)行編寫，也就是map與reduce。map可以把任務(wù)化解為多個任務(wù)，reduce將每個任務(wù)處理成果進(jìn)行融合。關(guān)于并行編程內(nèi)的其余問題，例如分布式儲存、工作調(diào)度、負(fù)載均衡等，都是通過Map Reduce架構(gòu)進(jìn)行實現(xiàn)。

利用傳統(tǒng)方法處理元數(shù)據(jù)過程中，由于內(nèi)存問題，不能容納元數(shù)據(jù)對某個規(guī)模項集合進(jìn)行計數(shù)需要的空間，如若要算出全部集合就要進(jìn)行k次掃描，可使用元數(shù)據(jù)抽樣樣本替代全部集合進(jìn)行運算。但在真實操作中，預(yù)先明確所需處理的元數(shù)據(jù)涵蓋的記錄個數(shù)是比較困難的，當(dāng)元數(shù)據(jù)量較大時，掃描一次的代碼代價十分高昂。本文提出一種在不了解元數(shù)據(jù)記錄個數(shù)的情況下，單次掃描就能完成隨機(jī)抽樣，同時獲得樣本數(shù)據(jù)記錄個數(shù)的并行算法，很好地解決以上難題，確保后續(xù)關(guān)聯(lián)性分析支持度的結(jié)果精度。設(shè)計過程為：

預(yù)先存儲前k個因子(k即為樣本記錄個數(shù))，將第k+1個因子當(dāng)作初始點，用1/i的幾率挑選第i個因子，同時任意替換一個已經(jīng)存儲的記錄，那么遍歷一個就能獲得k個因子，保障隨機(jī)選擇完整性。

在n=k的狀況下，將前k個因子安置在蓄水池中可知，各個樣本取出概率都是相同的，表示為k/k=1。若此刻樣本編號是n，各個取出樣本的概率都相同，即k/n，就要驗證此類狀況同樣適用于n+1，驗證過程如下：

用k/(n+1)判斷是否將n+1放在蓄水池內(nèi)。n+1出現(xiàn)于蓄水池內(nèi)的幾率是k/(n+1)，設(shè)定前n個因子內(nèi)的隨機(jī)因子為m(k+1≤m≤n)，則m在蓄水池內(nèi)出現(xiàn)的幾率是

(1)

從式(1)中可知，關(guān)于n+1各個樣本取出幾率均相同，也就得到k/(n+1)。想要完成上述并行抽樣計算，僅需在Map Reduce架構(gòu)內(nèi)編寫mapper即可。在map函數(shù)內(nèi)，用戶描述一個數(shù)組保存選擇的k個元素，等掃描全部因子之后，在析構(gòu)函數(shù)內(nèi)把數(shù)組元數(shù)據(jù)傳輸至磁盤內(nèi)部。

通過并行抽樣法算法，在得到的樣本內(nèi)挖掘頻繁項集，即元數(shù)據(jù)間的關(guān)聯(lián)性結(jié)果。使用基于Map Reduce編程架構(gòu)完成的并行頻繁項集，能夠找出大數(shù)據(jù)內(nèi)相互關(guān)聯(lián)的元數(shù)據(jù)。

把并行抽樣算法內(nèi)獲取的結(jié)果放置于分布式文件系統(tǒng)內(nèi)，這里使用Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System，HDFS)。采用Map Reduce架構(gòu)能達(dá)到樣本自主分塊目標(biāo)，也就是HDFS的block是一個map任務(wù)輸入，完成多個map并行運行。Map函數(shù)輸入是一條記錄，輸出是{key：項集，value：1}。因為在map內(nèi)會生成數(shù)量眾多的項集key-value，致使reduce任務(wù)通信負(fù)載過重。

為提升元數(shù)據(jù)關(guān)聯(lián)分析效率，在map流程中加入combine流程，預(yù)先對各個map任務(wù)采取相等key的value值融合，降低通信負(fù)載數(shù)量。在reduce內(nèi)規(guī)范約束此類鍵值，輸出支持度需高于最小支持度臨界值項集，也就是頻繁項集。

處理reduce輸出結(jié)果，獲得k+1項集，并將其當(dāng)作下一次Map Reduce中map任務(wù)的樣本數(shù)據(jù)，輸入至map內(nèi)持續(xù)推算頻繁k+1項集，最終得到準(zhǔn)確的元數(shù)據(jù)關(guān)聯(lián)結(jié)果。具體過程如圖5所示。

圖5 元數(shù)據(jù)并行關(guān)聯(lián)計算過程

4 基于元數(shù)據(jù)關(guān)聯(lián)特征的交互式數(shù)據(jù)快速查詢

對交互式數(shù)據(jù)快速查詢的第一步是構(gòu)建關(guān)聯(lián)元數(shù)據(jù)模型，使用分布式激振模式將元數(shù)據(jù)保存在數(shù)據(jù)庫內(nèi)，要對元數(shù)據(jù)關(guān)聯(lián)進(jìn)行狀態(tài)評估，就要獲得數(shù)據(jù)庫訪問輸出

(2)

使用相空間重構(gòu)與非線性時間序列分析手段研究數(shù)據(jù)庫內(nèi)元數(shù)據(jù)關(guān)聯(lián)特征，如果數(shù)據(jù)庫振動信號時間序列是{x1，x2，…，xN}，嵌入維數(shù)是b，元數(shù)據(jù)關(guān)聯(lián)后驗概率估計是p(x0)，由此獲得以下公式

(3)

其中，lj(k)是編號j的第k個元數(shù)據(jù)的關(guān)聯(lián)概率，ηij(k)表示均衡概率。

考慮數(shù)據(jù)庫中元數(shù)據(jù)關(guān)聯(lián)特征參變量，得到

(4)

使用軌跡協(xié)方差矩陣XTX特征值當(dāng)作觀察時間序列的特征值，利用預(yù)先得到的數(shù)據(jù)庫信息，計算出實體關(guān)聯(lián)知識庫，并使用表征關(guān)聯(lián)知識完成交互式大數(shù)據(jù)資源整合，獲得元數(shù)據(jù)關(guān)聯(lián)提取解析式為

(5)

其中，Yq×u是關(guān)聯(lián)維度矩陣，Wu×u是關(guān)聯(lián)均衡概率。通過上式可知，數(shù)據(jù)庫中元數(shù)據(jù)關(guān)聯(lián)特征個數(shù)較多，運算復(fù)雜度很高，不能對數(shù)據(jù)庫關(guān)聯(lián)元數(shù)據(jù)采取及時挖掘。要剔除大數(shù)據(jù)內(nèi)冗余元數(shù)據(jù)與非關(guān)聯(lián)元數(shù)據(jù)干擾，減少查詢計算難度。

xn=[xn，xn-τ，…，xn-(b-1)τ]

(6)

其中，τ是對變量序列數(shù)。

將元數(shù)據(jù)關(guān)聯(lián)的相空間重構(gòu)軌跡定義為

X=[x(t0)，x(t0+Δt)，…，x(t0+(K-1)Δt)]

(7)

其中，x(t)是元數(shù)據(jù)關(guān)聯(lián)嵌入在相空間內(nèi)的一組空間形態(tài)向量，Δt是抽樣時間間隔。

在高維相空間內(nèi)，計算元數(shù)據(jù)關(guān)聯(lián)差分累計函數(shù)特征，即能獲取數(shù)據(jù)庫差分累積函數(shù)特征，記作

(8)

其中，a0，a1，…，aM是差分累積矢量，ai、ci均為差分累積函數(shù)特征指數(shù)。

運用差分累積函數(shù)特征與相空間重構(gòu)，完成交互式關(guān)聯(lián)查詢，將元數(shù)據(jù)關(guān)聯(lián)特征矩陣X實施奇異值分解

X=UDVT

(9)

其中，U∈Rm×n為正交矩陣，V∈RM×N，并保證UT=U-1。

元數(shù)據(jù)關(guān)聯(lián)特征提取過程為

(10)

其中，yl為關(guān)聯(lián)特征系數(shù)。

求解出l個特征值λ1，λ2，…，λl及特征矢量矩陣Y=[y1，y2，…，yl]，并將元數(shù)據(jù)關(guān)聯(lián)特征估計描述成

(11)

其中，Xk是元數(shù)據(jù)關(guān)聯(lián)統(tǒng)計數(shù)值，oi是元數(shù)據(jù)關(guān)聯(lián)特征最高值。

在交互式關(guān)聯(lián)查詢中，查詢追蹤軌跡對角線位置線段關(guān)聯(lián)近似點的確定性特征是

(12)

其中，l是追蹤軌跡對角線位置線段長度，Rij表示查詢中的特征值，Nl是涵蓋在和查詢追蹤軌跡對角線平行線段內(nèi)的關(guān)聯(lián)近似點數(shù)量。將元數(shù)據(jù)關(guān)聯(lián)路徑定義為

(13)

經(jīng)過以上分析，獲得元數(shù)據(jù)關(guān)聯(lián)查詢查準(zhǔn)系數(shù)的表達(dá)式為：

(14)

根據(jù)上述過程，完成交互式數(shù)據(jù)快速查詢，在最大限度滿足用戶使用需求的同時，節(jié)省用戶搜索數(shù)據(jù)的時間與精力，令其及時快速獲得所需信息。

5 仿真結(jié)果與分析

為了驗證基于元數(shù)據(jù)關(guān)聯(lián)特征的交互式數(shù)據(jù)快速查詢方法在實際應(yīng)用中的性能，進(jìn)行一次仿真。仿真中，創(chuàng)建一組涵蓋1300組搜尋數(shù)據(jù)屬性分布集的交互式關(guān)聯(lián)查詢模型，探究數(shù)據(jù)關(guān)聯(lián)查詢精度與抗干擾性。特征數(shù)據(jù)查詢節(jié)點數(shù)量是53個，數(shù)據(jù)采集容量是15Git，數(shù)據(jù)初始采樣頻度是130kHz，數(shù)據(jù)庫內(nèi)保存了120TB的資源信息，每個分割間隔是2MB。

依據(jù)以上仿真環(huán)境與參變量設(shè)定，完成交互式數(shù)據(jù)快速查詢驗證。初始數(shù)據(jù)采樣時長為0～60ms，采用本文提出的基于元數(shù)據(jù)關(guān)聯(lián)特征的交互式數(shù)據(jù)快速查詢方法、文獻(xiàn)[3]方法和文獻(xiàn)[4]方法，測驗三種方法下關(guān)聯(lián)查詢的查準(zhǔn)率，比較結(jié)果如圖6所示。

圖6 查準(zhǔn)率結(jié)果示意圖

從圖6中可知，本文提出的基于元數(shù)據(jù)關(guān)聯(lián)特征的交互式數(shù)據(jù)快速查詢方法的查準(zhǔn)率和文獻(xiàn)[3]方法相差不多，但略高于文獻(xiàn)[3]方法，卻遠(yuǎn)遠(yuǎn)優(yōu)于文獻(xiàn)[4]方法。出現(xiàn)此種現(xiàn)象的原因在于本文方法采用交互式理論，充分融合用戶喜好需求，讓用戶切實參與關(guān)聯(lián)查詢過程，關(guān)聯(lián)查詢結(jié)果更貼合用戶實際需求，查準(zhǔn)率隨之提高。

為了進(jìn)一步驗證本文方法的有效性，對本文提出的基于元數(shù)據(jù)關(guān)聯(lián)特征的交互式數(shù)據(jù)快速查詢方法、文獻(xiàn)[3]方法和文獻(xiàn)[4]方法的關(guān)聯(lián)查詢時間開銷進(jìn)行對比分析，對比結(jié)果如圖7所示。

圖7 時間開銷結(jié)果示意圖

分析圖7可以看出，伴隨待查詢數(shù)據(jù)規(guī)模的增多，計算時間開銷均呈現(xiàn)上升態(tài)勢，但本文方法總時間開銷均低于兩種文獻(xiàn)方法。這是因為本文方法使用并行抽樣算法，得到精準(zhǔn)的數(shù)據(jù)關(guān)聯(lián)性結(jié)果，能夠增強(qiáng)數(shù)據(jù)關(guān)聯(lián)查詢效率，有效縮短查詢時間。

6 結(jié)論

為提升大數(shù)據(jù)查詢性能，提出一種基于元數(shù)據(jù)關(guān)聯(lián)特征的交互式數(shù)據(jù)快速查詢方法。所提方法能夠快速有效完成數(shù)據(jù)關(guān)聯(lián)查詢，并且為用戶提供優(yōu)質(zhì)的交互體驗。但該方法在關(guān)聯(lián)性分析方面，僅在元數(shù)據(jù)集內(nèi)完成關(guān)聯(lián)計算，并不能確保會生成全部數(shù)據(jù)頻繁項集，或許會影響查詢時效性，后續(xù)工作會對此方面進(jìn)行深入探究。