基于元數據關聯特征的交互式數據快速查詢

鄧 斌，陳會平，李凱勇

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

1 引言

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

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

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

2 交互式數據預處理過程

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

圖1 傳統數據挖掘架構圖

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

圖2 交互式數據挖掘架構圖

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

圖3 異常數據預處理結構

交互式數據完成預處理后可獲得特征矢量集合，用戶選擇待運行算法同時設定模型觀測點。架構把用戶設定變換成代碼片引入算法內，將整理后的算法文件傳輸到每個節點。當節點運行到觀測點時，將中間結果進行抽樣得到的觀測集展現于用戶界面中。在大數據背景下，儲存算法各個步驟的中間結果會耗費大量資源，架構使用按需規劃方法，在用戶無法設置觀測點的狀況下，架構不會保存中間結果。

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

3 基于并行抽樣的元數據關聯性分析

以上交互式數據預處理過程可提供給用戶良好操作體驗，同時獲得準確的元數據關聯分析結果，首先使用Map Reduce編程模型對元數據進行操作處理，明確元數據間隱含關系。

Map Reduce編程模型利用分布式思路，將元數據集分發至一個主節點管理下的每個分節點內，令其一起完成處理任務，合并每個分節點的中間結果，獲取最終處理結果[8]，具體處理結構如圖4所示。

圖4 Map Reduce處理元數據集

該模型具備兩個關鍵函數，通過用戶進行編寫，也就是map與reduce。map可以把任務化解為多個任務，reduce將每個任務處理成果進行融合。關于并行編程內的其余問題，例如分布式儲存、工作調度、負載均衡等，都是通過Map Reduce架構進行實現。

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

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

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

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

(1)

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

通過并行抽樣法算法，在得到的樣本內挖掘頻繁項集，即元數據間的關聯性結果。使用基于Map Reduce編程架構完成的并行頻繁項集，能夠找出大數據內相互關聯的元數據。

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

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

處理reduce輸出結果，獲得k+1項集，并將其當作下一次Map Reduce中map任務的樣本數據，輸入至map內持續推算頻繁k+1項集，最終得到準確的元數據關聯結果。具體過程如圖5所示。

圖5 元數據并行關聯計算過程

4 基于元數據關聯特征的交互式數據快速查詢

對交互式數據快速查詢的第一步是構建關聯元數據模型，使用分布式激振模式將元數據保存在數據庫內，要對元數據關聯進行狀態評估，就要獲得數據庫訪問輸出

(2)

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

(3)

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

考慮數據庫中元數據關聯特征參變量，得到

(4)

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

(5)

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

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

(6)

其中，τ是對變量序列數。

將元數據關聯的相空間重構軌跡定義為

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

(7)

其中，x(t)是元數據關聯嵌入在相空間內的一組空間形態向量，Δt是抽樣時間間隔。

在高維相空間內，計算元數據關聯差分累計函數特征，即能獲取數據庫差分累積函數特征，記作

(8)

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

運用差分累積函數特征與相空間重構，完成交互式關聯查詢，將元數據關聯特征矩陣X實施奇異值分解

X=UDVT

(9)

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

元數據關聯特征提取過程為

(10)

其中，yl為關聯特征系數。

求解出l個特征值λ1，λ2，…，λl及特征矢量矩陣Y=[y1，y2，…，yl]，并將元數據關聯特征估計描述成

(11)

其中，Xk是元數據關聯統計數值，oi是元數據關聯特征最高值。

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

(12)

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

(13)

經過以上分析，獲得元數據關聯查詢查準系數的表達式為：

(14)

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

5 仿真結果與分析

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

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

圖6 查準率結果示意圖

從圖6中可知，本文提出的基于元數據關聯特征的交互式數據快速查詢方法的查準率和文獻[3]方法相差不多，但略高于文獻[3]方法，卻遠遠優于文獻[4]方法。出現此種現象的原因在于本文方法采用交互式理論，充分融合用戶喜好需求，讓用戶切實參與關聯查詢過程，關聯查詢結果更貼合用戶實際需求，查準率隨之提高。

為了進一步驗證本文方法的有效性，對本文提出的基于元數據關聯特征的交互式數據快速查詢方法、文獻[3]方法和文獻[4]方法的關聯查詢時間開銷進行對比分析，對比結果如圖7所示。

圖7 時間開銷結果示意圖

分析圖7可以看出，伴隨待查詢數據規模的增多，計算時間開銷均呈現上升態勢，但本文方法總時間開銷均低于兩種文獻方法。這是因為本文方法使用并行抽樣算法，得到精準的數據關聯性結果，能夠增強數據關聯查詢效率，有效縮短查詢時間。

6 結論

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