茹 蓓， 李 虹(. 新鄉(xiāng)學(xué)院 計(jì)算機(jī)與信息工程學(xué)院， 河南 新鄉(xiāng) 453003； . 吉林省質(zhì)監(jiān)檢測(cè)基地 吉林省纖維檢驗(yàn)處， 長(zhǎng)春 3003)

控制工程

海量數(shù)據(jù)干擾下冗余數(shù)據(jù)高性能消除方法*

茹 蓓1， 李 虹2
(1. 新鄉(xiāng)學(xué)院 計(jì)算機(jī)與信息工程學(xué)院， 河南 新鄉(xiāng) 453003； 2. 吉林省質(zhì)監(jiān)檢測(cè)基地 吉林省纖維檢驗(yàn)處， 長(zhǎng)春 130103)

針對(duì)海量數(shù)據(jù)處理過(guò)程中大量相似特征會(huì)給數(shù)據(jù)分類(lèi)造成冗余干擾，在分類(lèi)中心確定時(shí)出現(xiàn)多次校驗(yàn)、重復(fù)等弊端，提出一種海量數(shù)據(jù)干擾下冗余數(shù)據(jù)高性能消除方法.采用主動(dòng)采樣方法提取海量數(shù)據(jù)干擾下冗余數(shù)據(jù)特征，并對(duì)其進(jìn)行分類(lèi).引入均值漂移傳遞函數(shù)對(duì)冗余數(shù)據(jù)進(jìn)行分類(lèi)處理，獲取冗余數(shù)據(jù)活躍程度，實(shí)現(xiàn)冗余數(shù)據(jù)的高性能消除.結(jié)果表明，相比傳統(tǒng)的消除方法，高效消除方法性能良好，所需時(shí)間短，具有一定的優(yōu)越性.

海量數(shù)據(jù)； 干擾； 冗余數(shù)據(jù)； 高性能； 消除方法； 改進(jìn)； 均值； 傳遞函數(shù)

隨著計(jì)算機(jī)技術(shù)與信息處理技術(shù)的快速發(fā)展，許多領(lǐng)域的信息被儲(chǔ)存在計(jì)算機(jī)系統(tǒng)中，形成海量數(shù)據(jù)，使得其存儲(chǔ)和管理成為相當(dāng)棘手的問(wèn)題[1-2].雖然如今存儲(chǔ)設(shè)備容量越來(lái)越大，但也無(wú)法滿足處理數(shù)據(jù)量的增長(zhǎng)需要[3-4]，形成了大量的冗余數(shù)據(jù).而對(duì)冗余數(shù)據(jù)進(jìn)行高效消除、減輕數(shù)據(jù)存儲(chǔ)負(fù)擔(dān)、提高數(shù)據(jù)存儲(chǔ)效率成為了近年來(lái)信息處理技術(shù)的研究熱點(diǎn)，受到廣大學(xué)者的廣泛關(guān)注，也出現(xiàn)了很多有效方法[5-7].

文獻(xiàn)[8]提出局部均值分解的消除方法，采用數(shù)值模擬把線性、多項(xiàng)式及指數(shù)趨勢(shì)項(xiàng)融入至要消除的數(shù)據(jù)中進(jìn)行消除，該方法可對(duì)冗余數(shù)據(jù)進(jìn)行消除，但消除過(guò)程需要一定約束條件；文獻(xiàn)[9]提出規(guī)則分段技術(shù)法，把多個(gè)冗余數(shù)據(jù)進(jìn)行消除，但該方法只能應(yīng)用到小聚類(lèi)環(huán)境中；文獻(xiàn)[10]提出一種基于均值分解的消除方法，在CPU里設(shè)定一個(gè)特別的任務(wù)切換專(zhuān)用數(shù)據(jù)鏈路，實(shí)現(xiàn)在CPU硬件資源限制狀態(tài)時(shí)進(jìn)行數(shù)據(jù)存儲(chǔ)，引入Hyper-Scheduling法對(duì)冗余數(shù)據(jù)進(jìn)行消除，但是該方法誤差較大.

針對(duì)上述問(wèn)題的產(chǎn)生，本文提出一種新的海量數(shù)據(jù)干擾下冗余數(shù)據(jù)高性能消除方法，采用主動(dòng)采樣方法提取數(shù)據(jù)特征，并引入均值漂移傳遞函數(shù)對(duì)冗余數(shù)據(jù)進(jìn)行分類(lèi)，相比傳統(tǒng)的消除方法具有一定的優(yōu)越性.

1 海量數(shù)據(jù)干擾下冗余數(shù)據(jù)分類(lèi)

由于海量數(shù)據(jù)的相似特征容易造成循環(huán)分類(lèi)、多次處理等問(wèn)題，因此，需要專(zhuān)門(mén)針對(duì)相似性干擾提取冗余數(shù)據(jù)特征，并根據(jù)特征對(duì)冗余數(shù)據(jù)進(jìn)行分類(lèi)，加快消除速率.

1.1 冗余數(shù)據(jù)特征獲取

海量數(shù)據(jù)在特征相似的環(huán)境下，會(huì)形成冗余干擾，在進(jìn)行冗余數(shù)據(jù)分類(lèi)之前，采用主動(dòng)采樣方法提取海量數(shù)據(jù)冗余數(shù)據(jù)特征.

假設(shè)最初訓(xùn)練數(shù)據(jù)集的全部樣本數(shù)是N，大類(lèi)樣本數(shù)為Nmax，小類(lèi)樣本數(shù)為Nmin，則當(dāng)大類(lèi)樣本數(shù)大于小類(lèi)樣本數(shù)據(jù)，即Nmax>Nmin，對(duì)小類(lèi)中每個(gè)樣本的分類(lèi)密度ρl定義為

ρl=Ml/K(l=1，2，…，Nmin)

(1)

式中：K為空間中基于歐式距離的最近鄰數(shù)目；Ml為K個(gè)最近鄰數(shù)目中屬于大類(lèi)的樣本數(shù).很明顯，ρl∈[0，1]，其密度分布表達(dá)式為

(2)

假設(shè)對(duì)p個(gè)樣本的第j個(gè)輸出值和目標(biāo)值分別是ypj(τ)和dpj，則特征提取約束條件為

(3)

式中：τ為迭代數(shù)目；n為輸出數(shù)據(jù)量；m為最后訓(xùn)練數(shù)據(jù)集的數(shù)量.分類(lèi)迭代次數(shù)表達(dá)式為

w(τ+1)=w(τ)+ηΔw(τ)+α(w(τ)-

w(τ-1))

(4)

式中：η為迭代速率；α為動(dòng)量因子.此時(shí)提取過(guò)程收縮量為

(5)

式中：φpj(τ)為輸入量總和；o(τ)為冗余數(shù)據(jù)輸出量.在此基礎(chǔ)上，提取海量數(shù)據(jù)干擾下冗余數(shù)據(jù)特征.

假設(shè)有一個(gè)標(biāo)準(zhǔn)的樣本數(shù)據(jù)集Nh，激勵(lì)函數(shù)為g(x)，采集的樣本數(shù)為Ns，樣本為(xq，tq)，其中xq=[xq1，xq2，…，xqn]T∈Rn且tq=[tq1，tq2，…，tqm]T∈Rm，則建立的冗余數(shù)據(jù)提取模型為

(6)

式中，bq為冗余數(shù)據(jù)偏置.

1.2 冗余數(shù)據(jù)特征分類(lèi)

在獲取冗余數(shù)據(jù)特征的基礎(chǔ)上，采用線性頻譜分析法，對(duì)海量數(shù)據(jù)干擾下的冗余數(shù)據(jù)特征進(jìn)行分類(lèi)，為改進(jìn)冗余數(shù)據(jù)消除方法提供基礎(chǔ)依據(jù).

在海量數(shù)據(jù)干擾下，冗余數(shù)據(jù)特征通常在時(shí)間及空間上的標(biāo)點(diǎn)為離散狀態(tài)，所以冗余數(shù)據(jù)分類(lèi)過(guò)程及有關(guān)理論也應(yīng)建立在離散狀態(tài)下.當(dāng)在采集面z=z0處時(shí)，其分類(lèi)分量表示為

S+(zm)=W+(zm，z0)S+(z0)

(7)

式中：W+(zm，z0)為從z0到zm的分類(lèi)算子；S+(z0)為分類(lèi)集合.在進(jìn)行冗余數(shù)據(jù)分類(lèi)時(shí)，往往只需要去除M階多次分類(lèi)，故提取的前M項(xiàng)分類(lèi)結(jié)果表示為

p(z0)S+(z0)

(8)

式中：p(z0)為記錄的原始數(shù)據(jù)；t(z0)為數(shù)據(jù)特征.

假設(shè)初始樣本冗余數(shù)據(jù)采樣頻率為f0，計(jì)算確定冗余數(shù)據(jù)提取結(jié)果為

(9)

采用線性頻譜分析法得到冗余數(shù)據(jù)的適應(yīng)值函數(shù)，對(duì)海量數(shù)據(jù)干擾下的冗余數(shù)據(jù)進(jìn)行分類(lèi)，則其冗余數(shù)據(jù)的分類(lèi)約束函數(shù)為

F=XmaxA+(1-Xmax)B

(10)

式中：A為分類(lèi)準(zhǔn)確率；B為消減百分比.對(duì)異常數(shù)據(jù)的類(lèi)內(nèi)離散度集合進(jìn)行加權(quán)處理，得到分類(lèi)結(jié)果為

COVmin)]

(11)

式中，COVmax、COVmin分別為樣本的最大協(xié)方差和最小協(xié)方差.

2 海量數(shù)據(jù)干擾下冗余數(shù)據(jù)消除

在對(duì)冗余數(shù)據(jù)進(jìn)行分類(lèi)的基礎(chǔ)上，假設(shè)LU為U時(shí)刻采集分類(lèi)后的冗余數(shù)據(jù)，LV為V時(shí)刻采集分類(lèi)后的冗余數(shù)據(jù)，則其冗余數(shù)據(jù)采集速度可表示為

Smin(LU，LV))

(12)

式中，Smax，Savg，Smin分別為最大速度、平均速度、最小速度差異程度的絕對(duì)值.此時(shí)LU與LV間的位置距離獲取表達(dá)式為

D=V(LU，LV)dist(LU，LV)

(13)

式中，dist()為冗余數(shù)據(jù)間的歐氏距離.

為了進(jìn)一步對(duì)冗余過(guò)程進(jìn)行改進(jìn)，引入相似度概念，根據(jù)冗余數(shù)據(jù)的突出特征獲取整體相似度.對(duì)于任意第i個(gè)冗余數(shù)據(jù)，其整體相似度可表示為

(14)

式中：Ci為相關(guān)度系數(shù)；βi為冗余數(shù)據(jù)的突出特征.

對(duì)于單個(gè)冗余數(shù)據(jù)來(lái)說(shuō)，它包括γi個(gè)冗余數(shù)據(jù)特征.冗余數(shù)據(jù)整體相似度可表示成突出特征βi的結(jié)構(gòu)相似度.對(duì)整體相似度進(jìn)行加權(quán)處理，則其加權(quán)平均數(shù)表達(dá)式為

(15)

式中：si為i個(gè)冗余數(shù)據(jù)的加權(quán)平均數(shù)；I為冗余數(shù)據(jù)集上的特征數(shù)量.顯然整體速度大，冗余數(shù)據(jù)特征越明顯，進(jìn)行消除越徹底；反之，冗余數(shù)據(jù)特征越不顯著，消除效果越差.為了能在冗余數(shù)據(jù)特征不顯著的情況下，也能對(duì)冗余數(shù)據(jù)進(jìn)行消除，引入了均值漂移傳遞函數(shù)對(duì)冗余數(shù)據(jù)進(jìn)行處理，提高了方法的消除性能.

假設(shè)數(shù)據(jù)集O中存在Hi個(gè)冗余數(shù)據(jù)，則均值漂移傳遞函數(shù)可表示為

(16)

(17)

式中：tmin為冗余數(shù)據(jù)最短活躍時(shí)間；tmax為冗余數(shù)據(jù)最長(zhǎng)活躍時(shí)間；t為總活躍時(shí)間.由此可知，Y越大，說(shuō)明冗余數(shù)據(jù)越活躍，消除效果越好；反之，Y越小，說(shuō)明冗余數(shù)據(jù)不活躍，消除效果越差.

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

為了驗(yàn)證本文所設(shè)計(jì)的冗余數(shù)據(jù)消除方法的性能，進(jìn)行了實(shí)驗(yàn)對(duì)比分析.實(shí)驗(yàn)電腦的硬件設(shè)置為：16 Gbit內(nèi)存，Xeon E5606處理器，主頻2.13 GHz、14 Tbit RAID6磁盤(pán)陣列(16個(gè)1 Tbit磁盤(pán)，其中2個(gè)是校驗(yàn)盤(pán))以及120 Gbit的閃存(SVP200S37A120G)，配置的操作系統(tǒng)為Ubuntn12.04，測(cè)試數(shù)據(jù)集為GCC、SciLab、Linux，數(shù)據(jù)集的數(shù)據(jù)特征設(shè)置如表1所示.

測(cè)試數(shù)據(jù)集合將3種數(shù)據(jù)集結(jié)合在一起，由于3種數(shù)據(jù)集合中存在大量的相似數(shù)據(jù)，這種數(shù)據(jù)的相似性會(huì)形成實(shí)驗(yàn)環(huán)境中的冗余干擾，符合干擾環(huán)境條件.

3.1 準(zhǔn)確率實(shí)驗(yàn)分析

為了驗(yàn)證本文方法的有效性，在數(shù)據(jù)量一定的情況下，采用文獻(xiàn)[8]局部均值分解的消除方法、文獻(xiàn)[9]規(guī)則分段技術(shù)法與改進(jìn)方法進(jìn)行消除準(zhǔn)確率方面的對(duì)比.在固定數(shù)據(jù)量情況下，采用不同方法進(jìn)行冗余數(shù)據(jù)消除試驗(yàn)，實(shí)驗(yàn)準(zhǔn)確率用消除數(shù)據(jù)量與原始數(shù)據(jù)量的比值表示，取10次結(jié)果平均值進(jìn)行統(tǒng)計(jì).實(shí)驗(yàn)在GCC數(shù)據(jù)集中進(jìn)行，其三維數(shù)據(jù)冗余環(huán)境模擬如圖1所示(x、y、z軸表示數(shù)據(jù)空間的存儲(chǔ)位置).

圖1 GCC冗余環(huán)境模擬Fig.1 GCC redundant environment simulation

在圖1冗余環(huán)境中進(jìn)行不同方法的準(zhǔn)確率對(duì)比研究，統(tǒng)計(jì)結(jié)果如圖2所示.

由圖2可知，在GCC數(shù)據(jù)集中，采用局部均值分解法其準(zhǔn)確率可達(dá)到49.3%；采用規(guī)則分段技術(shù)法時(shí)，其消除準(zhǔn)確率約為68.1%，兩種算法隨著數(shù)據(jù)量的增加，均出現(xiàn)準(zhǔn)確率下降的趨勢(shì)，不適合大量數(shù)據(jù)應(yīng)用；采用改進(jìn)方法時(shí)，其消除準(zhǔn)確率約為79.7%，其整體要比局部均值分解法、規(guī)則分段技術(shù)法的準(zhǔn)確率提高了約30.4%、11.6%，具有一定的優(yōu)越性.在冗余干擾的環(huán)境下，本文方法可以運(yùn)用有限次數(shù)的分類(lèi)使得冗余數(shù)據(jù)被迅速排除在聚類(lèi)中心之外；而其他方法都需要進(jìn)行多次的對(duì)比和聚類(lèi)中心校驗(yàn)操作，大幅度降低了聚類(lèi)的效率，使得干擾數(shù)據(jù)無(wú)法被有效排除.

圖2 GCC數(shù)據(jù)集冗余數(shù)據(jù)消除準(zhǔn)確率對(duì)比Fig.2 Comparison in elimination accuracyof redundant data in GCC dataset

3.2 效率對(duì)比分析

采用文獻(xiàn)[8]局部均值分解的消除方法、文獻(xiàn)[9]規(guī)則分段技術(shù)法與改進(jìn)方法進(jìn)行消除效率方面的對(duì)比，實(shí)驗(yàn)在SciLab和Linux數(shù)據(jù)集中進(jìn)行，其三維數(shù)據(jù)冗余環(huán)境模擬如圖3所示.

圖3 SciLab和Linux冗余環(huán)境模擬Fig.3 SciLab and Linux redundantenvironment simulation

在圖3冗余環(huán)境中進(jìn)行不同方法效率方面的對(duì)比研究，統(tǒng)計(jì)結(jié)果如圖4所示.

由圖4可以看出，在數(shù)據(jù)量一定的情況下，采用局部均值分解法時(shí)，其消除平均時(shí)間約為7.23 s；采用規(guī)則分段技術(shù)法時(shí)，其消除所需時(shí)間約為5.53 s，且隨著數(shù)據(jù)量的增加，消除時(shí)間存在多處波動(dòng)，穩(wěn)定性較差；采用改進(jìn)消除方法時(shí)，其消除所需時(shí)間約為3.42 s，相比傳統(tǒng)的方法，本文方法耗時(shí)降低明顯，具有一定的優(yōu)勢(shì).耗時(shí)是最能反映算法優(yōu)劣性的參考數(shù)據(jù)，在數(shù)據(jù)流增加的環(huán)境下，冗余干擾強(qiáng)度勢(shì)必成倍增加，本算法雖然在后期冗余去除過(guò)程中耗時(shí)略有增加，但是優(yōu)化效果明顯.

圖4 不同算法下消除所需時(shí)間對(duì)比Fig.4 Comparison in elimination timewith different algorithms

4 結(jié) 論

針對(duì)傳統(tǒng)冗余數(shù)據(jù)消除方法一直存在消除時(shí)間長(zhǎng)、性能差的問(wèn)題，本文提出一種冗余數(shù)據(jù)高性能消除方法.采用主動(dòng)采樣方法提取海量數(shù)據(jù)干擾下冗余數(shù)據(jù)特征，通過(guò)線性頻譜分析法對(duì)海量數(shù)據(jù)干擾下的冗余數(shù)據(jù)進(jìn)行分類(lèi)，并以此為基礎(chǔ)計(jì)算出冗余數(shù)據(jù)的相似度，引入均值漂移傳遞函數(shù)對(duì)冗余數(shù)據(jù)進(jìn)行處理，獲取冗余數(shù)據(jù)活躍程度，實(shí)現(xiàn)海量數(shù)據(jù)干擾下冗余數(shù)據(jù)的高性能消除.仿真實(shí)驗(yàn)結(jié)果表明，相比傳統(tǒng)的消除方法，改進(jìn)方法的準(zhǔn)確率及效率均有所提高，具有一定的優(yōu)越性.

[1] 宛婉，周?chē)?guó)祥.Hadoop平臺(tái)的海量數(shù)據(jù)并行隨機(jī)抽樣 [J].計(jì)算機(jī)工程與應(yīng)用，2014，50(20)：115-118.

(WAN Wan，ZHOU Guo-xiang.Massive data parallel random sampling based on Hadoop [J].Computer Engineering and Applications，2014，50(20)：115-118.)

[2] 李志虹.基于遺傳迭代優(yōu)化的云計(jì)算下海量數(shù)據(jù)分類(lèi)查詢(xún) [J].科技通報(bào)，2015，31(6)：34-36.

(LI Zhi-hong.Classification query of huge amounts of data in cloud computing environment based on genetic optimization [J].Bulletin of Science and Technology，2015，31(6)：34-36.)

[3] 錢(qián)勤，張瑊，張坤，等.用于入侵檢測(cè)及取證的冗余數(shù)據(jù)刪減技術(shù)研究 [J].計(jì)算機(jī)科學(xué)，2014，41(增刊2)：252-258.

(QIAN Qin，ZHANG Jian，ZHANG Kun，et al.Technical study of reducing redundant data for intrusion detection and intrusion forensics [J].Computer Science，2014，41(Sup2)：252-258.)

[4] 王永利，王川，蔣效會(huì)，等.基于時(shí)空布隆過(guò)濾器的RFID冗余數(shù)據(jù)清洗算法 [J].南京理工大學(xué)學(xué)報(bào)，2015，39(3)：253-259.

(WANG Yong-li，WANG Chuan，JIANG Xiao-hui，et al.RFID duplicate removing algorithm based on temporal-spatial Bloom filter [J].Journal of Nanjing University of Science and Technology，2015，39(3)：253-259.)

[5] 孟慶娟，曹青媚，馬占飛.海量冗余數(shù)據(jù)干擾下的網(wǎng)絡(luò)數(shù)據(jù)捕獲和分析系統(tǒng)研究 [J].現(xiàn)代電子技術(shù)，2016，39(16)：27-30.

(MENG Qing-juan，CAO Qing-mei，MA Zhan-fei.Research on network data capture system and analysis system under interference of massive redundant data [J].Modern Electronics Technique，2016，39(16)：27-30.)

[6] 王樂(lè)，王芳.網(wǎng)絡(luò)數(shù)據(jù)庫(kù)中冗余環(huán)境下的高效數(shù)據(jù)定位仿真 [J].計(jì)算機(jī)仿真，2016，33(4)：364-367.

(WANG Le，WANG Fang.Simulation of efficient data localization in network database under redundant environment [J].Computer Simulation，2016，33(4)：364-367.)

[7] 聶軍.基于 K-L 特征壓縮的云計(jì)算冗余數(shù)據(jù)降維算法 [J].微電子學(xué)與計(jì)算機(jī)，2016(2)：125-129.

(NIE Jun.A data reduction algorithm based on K-L feature compression for cloud computing [J].Microelectronics & Computer，2016(2)：125-129.)

[8] 韓曉慧，杜松懷，蘇娟，等.基于局部均值分解的觸電故障信號(hào)瞬時(shí)參數(shù)提取 [J].農(nóng)業(yè)工程學(xué)報(bào)，2015，31(17)：221-227.

(HAN Xiao-hui，DU Song-huai，SU Juan.Extraction of biological electric shock signal instantaneous amplitude and frequency based on local mean decomposition [J].Transactions of the Chinese Society of Agricultural Engineering，2015，31(17)：221-227.)

[9] 刁愛(ài)軍.基于壓縮特征編碼的混合云冗余數(shù)據(jù)刪除算法 [J].科技通報(bào)，2015，31(8)：42-44.

(DIAO Ai-jun.Hybrid cloud redundant data delete algorithm based on feature code compression [J].Bulletin of Science and Technology，2015，31(8)：42-44.)

[10]趙志科，張曉光，王新.基于局部均值分解的機(jī)械振動(dòng)信號(hào)趨勢(shì)項(xiàng)消除方法 [J].鄭州大學(xué)學(xué)報(bào)(工學(xué)版)，2014，35(5)：100-104.

(ZHAO Zhi-ke，ZHANG Xiao-guang，WANG Xin.Trend elimination method of mechanical vibration signal based on local mean decomposition [J].Journal of Zhengzhou University(Engineering Science)，2014，35(5)：100-104.)

Highperformanceeliminationmethodforredundantdataundermassivedatainterference

RU Bei1, LI Hong2

(1. School of Computer and Information Engineering, Xinxiang University, Xinxiang 453003, China; 2. Office of Fiber Inspection of Jilin Province, Quality Supervision and Inspection Base of Jilin Province, Changchun 130103, China)

Aiming at the problem that in the data treatment process of massive data, a lot of similar characteristics can bring the redundant interference to the data classification, and cause such drawbacks as multiple check and repetition during the determination with the classification center, a high performance elimination method for redundant data under the massive data interference was proposed. With the active sampling method, the redundancy data feature under the massive data interference was extracted and classified. In addition, the mean shift transfer function was introduced to perform the classification of redundant data, obtain the redundant data activity and realize the high performance elimination of redundancy data. The results show that compared with the traditional method, the high performance elimination method has good properties, short processed time and certain superiority.

massive data; interference; redundant data; high performance; elimination method; improvement; mean value; transfer function

2016-11-21.

河南省科技廳科技攻關(guān)資助項(xiàng)目(172102210445)； 河南省科技廳軟科學(xué)研究資助項(xiàng)目(152400410345)； 河南省教育廳資助項(xiàng)目(15A520093).

茹 蓓(1977-)，女，河南新鄉(xiāng)人，副教授，碩士，主要從事軟件開(kāi)發(fā)、信息安全等方面的研究.

* 本文已于2017-10-25 21∶13在中國(guó)知網(wǎng)優(yōu)先數(shù)字出版. 網(wǎng)絡(luò)出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20171025.2113.068.html

10.7688/j.issn.1000-1646.2017.06.16

TP 311

A

1000-1646(2017)06-0686-05

(責(zé)任編輯：景 勇 英文審校：尹淑英)