文/黃麗達(dá)

1 引言

為了達(dá)到監(jiān)測(cè)與數(shù)據(jù)挖掘的要求，人們?cè)趯?duì)數(shù)據(jù)采集時(shí)會(huì)面臨因設(shè)備故障等造成數(shù)據(jù)出現(xiàn)碎片，遺漏有效數(shù)據(jù)的問題，形成海量碎片化網(wǎng)絡(luò)。通常情況下，碎片化網(wǎng)絡(luò)大數(shù)據(jù)中的部分碎片數(shù)據(jù)為有效數(shù)據(jù)，在很大程度上會(huì)攜帶對(duì)數(shù)據(jù)分析和處理方面的關(guān)鍵信息。本文提出一種新的海量碎片化網(wǎng)絡(luò)大數(shù)據(jù)中有效數(shù)據(jù)快速提取方法。實(shí)驗(yàn)結(jié)果表明，采用所提方法對(duì)海量碎片化網(wǎng)絡(luò)大數(shù)據(jù)中有效數(shù)據(jù)進(jìn)行提取精度和效率均較高。

2 海量碎片化網(wǎng)絡(luò)大數(shù)據(jù)中有效數(shù)據(jù)快速提取

2.1 問題描述

本節(jié)引入有效數(shù)據(jù)單元概念，假設(shè)海量碎片化網(wǎng)絡(luò)中共有m 條輸入數(shù)據(jù)流，數(shù)據(jù)流Si是通過部分?jǐn)?shù)據(jù)單元q 構(gòu)成的序列，用于描述已知數(shù)據(jù)單元取值集合。針對(duì)海量碎片化網(wǎng)絡(luò)，數(shù)據(jù)流Si對(duì)網(wǎng)絡(luò)的重要程度可用wi進(jìn)行描述，數(shù)據(jù)流Si通過海量碎片化網(wǎng)絡(luò)中節(jié)點(diǎn)Mi進(jìn)入網(wǎng)絡(luò)中。

假設(shè)數(shù)據(jù)單元di在數(shù)據(jù)流Sj中出現(xiàn)的次數(shù)用lij進(jìn)行描述，則d'i 就是數(shù)據(jù)單元di在海量碎片化網(wǎng)絡(luò)中的加權(quán)頻數(shù)：

數(shù)據(jù)流Sj的加權(quán)頻數(shù)Nj可通過下式求出：

海量碎片化網(wǎng)絡(luò)大數(shù)據(jù)中數(shù)據(jù)流的總加權(quán)頻數(shù)可通過下式求出：

設(shè)置閾值 ，若 ，則di即為有效數(shù)據(jù)單元。經(jīng)提取后，輸出所有在δ 值較高的情況下，數(shù)據(jù)單元估計(jì)加權(quán)頻數(shù)和實(shí)際值之間的誤差必須低于ε。

2.2 有效數(shù)據(jù)快速提取

本節(jié)通過兩個(gè)過程實(shí)現(xiàn)海量碎片化網(wǎng)絡(luò)大數(shù)據(jù)中有效數(shù)據(jù)快速提取。

通過Hash 表完成對(duì)多個(gè)單數(shù)據(jù)流統(tǒng)計(jì)結(jié)果的處理。假設(shè)統(tǒng)計(jì)表中共有t 個(gè)Hash 函數(shù)，所有Hash 表的長(zhǎng)度都是b。用TSk描述數(shù)據(jù)流Sk的統(tǒng)計(jì)表，通過TSk(i，j)對(duì)TSk中第i 行第j 列的統(tǒng)計(jì)值進(jìn)行描述，本節(jié)通過建立的統(tǒng)計(jì)表給出有效數(shù)據(jù)提取方法，實(shí)現(xiàn)過程如下：

（1）針對(duì)所有新出現(xiàn)的數(shù)據(jù)，求出一次數(shù)據(jù)流的加權(quán)頻數(shù)；

（2）完成對(duì)新數(shù)據(jù)的k 次哈希計(jì)算，依據(jù)和計(jì)算結(jié)果相應(yīng)的數(shù)據(jù)單元的統(tǒng)計(jì)值增加wk。

接著完成對(duì)各統(tǒng)計(jì)結(jié)果的綜合處理，獲取S 中數(shù)據(jù)單元的統(tǒng)計(jì)結(jié)果，詳細(xì)實(shí)現(xiàn)過程如下：

（1）產(chǎn)生空白表格；

（2）將k 個(gè)子孫統(tǒng)計(jì)表格對(duì)應(yīng)單元累加至空白表的對(duì)應(yīng)單元；

（3）綜合節(jié)點(diǎn)處理結(jié)果，在根節(jié)點(diǎn)獲取全部數(shù)據(jù)的統(tǒng)計(jì)結(jié)果，提取滿足有效數(shù)據(jù)要求的數(shù)據(jù)。

3 實(shí)驗(yàn)結(jié)果分析

本節(jié)將計(jì)數(shù)器方法和遺傳方法作為對(duì)比，將有效數(shù)據(jù)提取精度作為衡量標(biāo)準(zhǔn)進(jìn)行實(shí)驗(yàn)測(cè)試。

假設(shè)通過數(shù)據(jù)提取方法獲取的輸出結(jié)果用Dout進(jìn)行描述，實(shí)際符合條件的數(shù)據(jù)集合用Dreal進(jìn)行描述，數(shù)據(jù) 的估計(jì)加權(quán)頻數(shù)用ei進(jìn)行描述，數(shù)據(jù) 的實(shí)際加權(quán)頻數(shù)用ri進(jìn)行描述，則有效數(shù)據(jù)提取精度計(jì)算公式為：

圖1描述的是采用本文方法、計(jì)數(shù)器方法和遺傳方法對(duì)有效數(shù)據(jù)進(jìn)行提取的精度比較結(jié)果。

圖1可知，隨著數(shù)據(jù)量的逐漸增加，本文方法、計(jì)數(shù)器方法和遺傳方法的有效數(shù)據(jù)提取精度均趨于穩(wěn)定，而本文方法精度曲線一直高于計(jì)數(shù)器方法和遺傳方法。

圖1：三種方法提取精度測(cè)試

4 結(jié)論

本文提出一種新的海量碎片化網(wǎng)絡(luò)大數(shù)據(jù)中有效數(shù)據(jù)快速提取與恢復(fù)方法，通過Hash 表對(duì)海量碎片化網(wǎng)絡(luò)大數(shù)據(jù)中有效數(shù)據(jù)進(jìn)行快速提取。實(shí)驗(yàn)結(jié)果表明，所提方法精度和效率均較高。