基于特征向量的物聯(lián)網(wǎng)大數(shù)據(jù)壓縮算法*

郭雷勇

0 引 言

目前，無線射頻技術(shù)已經(jīng)廣泛應(yīng)用于倉儲(chǔ)管理、供應(yīng)鏈管理、醫(yī)療、圖書管理中。然而，這些過程中將會(huì)產(chǎn)生龐大的數(shù)據(jù)集。通過深入挖掘研究這些數(shù)據(jù)集，可以從中發(fā)現(xiàn)一些業(yè)務(wù)趨勢變化，有利于加深理解并改善商業(yè)流程。如果在使用這些數(shù)據(jù)前對其進(jìn)行預(yù)處理（如先對其壓縮），將會(huì)更有效地深入挖掘。本文以設(shè)計(jì)無線射頻物流倉儲(chǔ)中間件項(xiàng)目的過程為例進(jìn)行分析。

1 無線射頻特征選取及數(shù)據(jù)壓縮

如何確定特征向量表示一個(gè)標(biāo)簽在讀取過程中的性質(zhì)，在目前的研究領(lǐng)域缺乏統(tǒng)一認(rèn)識(shí)。不同的應(yīng)用選取的特性對結(jié)果影響很大。因此，對無線射頻數(shù)據(jù)進(jìn)行分析檢測前，需要找到最能體現(xiàn)標(biāo)簽讀取過程的特征。此外，原始標(biāo)簽數(shù)據(jù)集中包含多條重復(fù)記錄，數(shù)據(jù)規(guī)模達(dá)到成百吉字節(jié)，甚至達(dá)到太字節(jié)，處理壓力非常大。為了提高數(shù)據(jù)的處理效率，分析前一般都需要對無線射頻數(shù)據(jù)進(jìn)行預(yù)處理[1]。

在無線射頻的生命周期中，通過對業(yè)務(wù)流程進(jìn)行梳理，發(fā)現(xiàn)很多物品往往都是一整批運(yùn)輸?shù)摹Ｔ诠?yīng)鏈中，越往上游，貨物量越大，數(shù)據(jù)越集中，而下游階段的數(shù)據(jù)則呈現(xiàn)分散趨勢。在無線射頻數(shù)據(jù)集中，很多貨物的地點(diǎn)（Location）、時(shí)間（Time）屬性是一致的，即這些貨物以同樣的時(shí)間進(jìn)入同樣的地點(diǎn)，最后再一起離開該地點(diǎn)。

另外，由于無線射頻技術(shù)對環(huán)境的敏感性，在考慮標(biāo)簽在整個(gè)供應(yīng)鏈的生命周期中，各地的倉庫環(huán)境、閱讀器的廠商等因素差異，其閱讀器的位置、擺放角度等不同，都可能影響無線射頻數(shù)據(jù)讀取的特性。因此，基于全局?jǐn)?shù)據(jù)的無線射頻孤立點(diǎn)所受影響太多，準(zhǔn)確性將大大降低，且難以準(zhǔn)確表示孤立點(diǎn)的本質(zhì)，不具有實(shí)際應(yīng)用的意義。另外，如果直接對全局?jǐn)?shù)據(jù)集進(jìn)行孤立點(diǎn)挖掘，數(shù)據(jù)量龐大，也無法提供實(shí)時(shí)的數(shù)據(jù)挖掘[2-3]。借鑒文獻(xiàn)[4-5]數(shù)據(jù)立方的思想，本文希望可以對海量數(shù)據(jù)根據(jù)某種特性進(jìn)行壓縮，以更快的方式檢測其中的有效數(shù)據(jù)，以更準(zhǔn)確地挖掘出孤立點(diǎn)所象征的意義，同時(shí)大大減少數(shù)據(jù)計(jì)算的規(guī)模。

本文對數(shù)據(jù)進(jìn)行壓縮，根據(jù)無線射頻的業(yè)務(wù)時(shí)間段進(jìn)行操作，只記錄標(biāo)簽首次讀取的時(shí)間Time_in、最后離開的時(shí)間Time_out以及在這段時(shí)間內(nèi)的讀取次數(shù)。通過這種方式減少了大量的重復(fù)數(shù)據(jù)，而又保證信息不丟失。標(biāo)簽的讀取強(qiáng)度是一個(gè)能體現(xiàn)標(biāo)簽讀取過程的特征，本文用SS表示，其取值范圍為（0～100）。SS值越大，表明信號越強(qiáng)。由于無線射頻技術(shù)本身的內(nèi)在敏感性，信號強(qiáng)度往往與貨物的性質(zhì)（金屬非金屬、液體等）、標(biāo)簽所貼的商品位置及與閱讀器所處的位置相關(guān)。越貼近閱讀器，信號越強(qiáng)；而與閱讀器距離越遠(yuǎn)，信號越弱。

2 算法思路

基于以上原因，本文提出按照每個(gè)標(biāo)簽的讀取的實(shí)際間隔Time_duration、在該段時(shí)間內(nèi)讀取次數(shù)tagCnt以及標(biāo)簽讀取時(shí)的平均信號強(qiáng)度SSavg作為無線射頻標(biāo)簽的特征。本文以三元組＜Time_duration,tagCnt,SSavg＞代表標(biāo)簽在讀取過程中的特征向量空間，其中讀取時(shí)間間隔Time_duration=Time_in-Time_out，標(biāo)簽在讀取過程中的平均信號強(qiáng)度為SSavg：

特征選取如圖1所示。

圖1 數(shù)據(jù)集選取

tagCnt表示該段時(shí)間內(nèi)標(biāo)簽的讀取次數(shù)，SSi表示第i次讀取的信號強(qiáng)度。

通過數(shù)據(jù)按照上述特征過濾壓縮后，形成X={x1,x2…xn-1,xn}數(shù)據(jù)集，其中x代表一個(gè)標(biāo)簽。下面將具體講述如何對原始標(biāo)簽數(shù)據(jù)進(jìn)行壓縮。

具體方法如下：

（1）假設(shè)在無線射頻中間件獲取的標(biāo)簽數(shù)據(jù)流均以四元組方式存在 ＜ EPC,L ocation,T ime,SS＞，其原始標(biāo)簽記錄如下：

（2）給定閱讀器的位置信息Location，根據(jù)業(yè)務(wù)時(shí)段，選取間隔的起始時(shí)間T_Start和結(jié)束時(shí)間T_End。根據(jù)三個(gè)特性對數(shù)據(jù)進(jìn)行過濾，即只有滿足閱讀器位置信息Location一致，讀取時(shí)間T_Start≤Time≤T_End的標(biāo)簽記錄才會(huì)被聚合到同以個(gè)集合中。因此，會(huì)形成多個(gè)數(shù)據(jù)集聚類Cluster。經(jīng)過聚集分類并壓縮后的數(shù)據(jù)集，可以以四元組 ＜ EPC,T ime _ Duration,t a gCnt,S Savg＞ 形式表示每個(gè)標(biāo)簽的壓縮結(jié)果。聚類后的標(biāo)簽數(shù)據(jù)集如表1所示。

表1 聚集分類后的標(biāo)簽數(shù)據(jù)集

至此，通過對標(biāo)簽數(shù)據(jù)的壓縮處理，大大減少了數(shù)據(jù)處理的規(guī)模。對于每個(gè)標(biāo)簽ID，均可用＜Time_duration,tagCnt,SSavg＞三元組表征標(biāo)簽讀取過程的特征。每個(gè)聚類作為一個(gè)局部數(shù)據(jù)集，單獨(dú)進(jìn)行孤立點(diǎn)的數(shù)據(jù)挖掘。

3 算法實(shí)現(xiàn)

下面將具體介紹海里無線射頻數(shù)據(jù)壓縮算法的實(shí)現(xiàn)流程和偽代碼。

首先給出數(shù)據(jù)壓縮處理的算法實(shí)現(xiàn)，數(shù)據(jù)均以＜EPC,Location,Time,SS＞的形式存在。根據(jù)給定的Location、起始時(shí)間T_Start和結(jié)束時(shí)間T_End 3個(gè)屬性，將數(shù)據(jù)聚類處理。最后，按照＜EPC,Time_duration,tagCnt,SSavg＞格式輸出數(shù)據(jù)集。

算法實(shí)現(xiàn)流程，如圖2所示。根據(jù)標(biāo)簽三元組進(jìn)行聚類，為每個(gè)聚類單獨(dú)創(chuàng)建哈希表，然后獲取標(biāo)簽記錄，再判斷原始數(shù)據(jù)是否讀取完成；如果數(shù)據(jù)讀取完成，則將每個(gè)哈希表作為一個(gè)聚類輸出，作為檢測的數(shù)據(jù)集；否則，繼續(xù)讀取下一條數(shù)據(jù)。讀取數(shù)據(jù)后需要判斷在哈希表是否已有該數(shù)據(jù)，如果已經(jīng)存在，只需要記錄讀取次數(shù)和時(shí)間；否則，不僅需要記錄讀取次數(shù)和時(shí)間，還需要把新的數(shù)據(jù)插入到哈希表。

圖2 無線射頻數(shù)據(jù)壓縮算法流程

下面給出數(shù)據(jù)壓縮算法的偽代碼實(shí)現(xiàn)：

輸入：原始數(shù)據(jù)集RawDataSet(EPC, Location,Time,SS)，設(shè)定的閱讀器Location，有效的讀取的時(shí)間間隔Time_Start和Time_End

輸出：經(jīng)過數(shù)據(jù)壓縮后cleanDataSet(EPC,Time_duration,tagCnt,SSavg)

方法：

//用哈希表儲(chǔ)存每個(gè)標(biāo)簽數(shù)據(jù)TagNode的記錄

Table←Empty HashTable;

for each item in Raw DataSet

if(item.Location！=Location||item.currentTime＜Time_Start||item.currentTime＞Time_End)//如果標(biāo)簽的數(shù)據(jù)流

//不在指定的位置及有效時(shí)間間隔內(nèi)，則丟棄

drop item;

continue;

endif

if item.epc exists in HashTable

then//更新標(biāo)簽的平均信號強(qiáng)度

HashTable[epc].SS=(HashTable[epc].

tagCnt*SS+item.SS)/tagCnt+1

HashTable[epc].tagCnt+= 1;

HashTable[epc].tLastRead=

item.currentTime;

else//首次讀到標(biāo)簽TagNode.epc=item.epc;TagNode.tFirstRead=TagNode.tLastRead=item.currentTime;

TagNode.tagCnt=1;

Add TagNode to HashTable

endif

endfor

for each Record in Table//將哈希表中的每條記錄輸出

Time_duration=Record.tLastRead-Record.tfirstRead;

Add (EPC, Time_Duration, tagCnt,SSavg) to Clean DataSet;

endfor

4 實(shí)驗(yàn)仿真與分析

針對本文設(shè)計(jì)的壓縮算法，特設(shè)計(jì)如下實(shí)驗(yàn)。主要的實(shí)驗(yàn)工具是Visual Studio 2005與Matlab 7.70。

4.1 實(shí)驗(yàn)數(shù)據(jù)集來源

本實(shí)驗(yàn)壓縮實(shí)驗(yàn)的數(shù)據(jù)集是按照＜EPC,Location,Time,SS＞四元組生成的數(shù)據(jù)集，其中EPC、Location兩個(gè)屬性按照均勻分布生成數(shù)據(jù)，標(biāo)簽到達(dá)時(shí)間Time服從泊松分布，平均讀寫強(qiáng)度則按照均值μ=0.75、方差σ=0.05的高斯分布生成數(shù)據(jù)。按照一定的比例，重復(fù)生成該數(shù)據(jù)。

4.2 數(shù)據(jù)集壓縮實(shí)驗(yàn)

本實(shí)驗(yàn)按照500、1 000、5 000、20 000、50 000、100 000生成6組原始的無線射頻數(shù)據(jù)集，得到數(shù)據(jù)壓縮前后的數(shù)據(jù)對比，如表2、圖3所示。

表2 原始數(shù)據(jù)集與壓縮后數(shù)據(jù)對比

從表3、圖3的實(shí)驗(yàn)結(jié)果來看，當(dāng)原始數(shù)據(jù)集數(shù)據(jù)規(guī)模較小時(shí)，數(shù)據(jù)的壓縮效果并不明顯；當(dāng)數(shù)據(jù)規(guī)模不斷增大時(shí)，壓縮效果開始顯現(xiàn)；當(dāng)數(shù)據(jù)到達(dá)100 000時(shí)，大概可獲得5倍的壓縮率。從實(shí)驗(yàn)結(jié)果來看，本算法對海量無線射頻數(shù)據(jù)的壓縮處理是有效的，符合預(yù)想結(jié)果。另外，需要注意的是，本算法的數(shù)據(jù)集使用隨機(jī)函數(shù)生成，所以實(shí)際的壓縮效果取決于重復(fù)數(shù)據(jù)的個(gè)數(shù)。經(jīng)過反復(fù)測試，它的壓縮效果仍然比較理想。

圖3 在不同數(shù)據(jù)規(guī)模下數(shù)據(jù)集的壓縮效果

5 結(jié) 語

本文主要討論在海量無線射頻數(shù)據(jù)中挖掘孤立點(diǎn)的難點(diǎn)及意義，針對海量的標(biāo)簽數(shù)據(jù)，按照標(biāo)簽的位置信息、讀取時(shí)間進(jìn)行數(shù)據(jù)聚類，大大減少了數(shù)據(jù)處理量；通過對無線射頻數(shù)據(jù)讀取過程特性的研究，提出了以標(biāo)簽在讀寫時(shí)間段、在該段時(shí)間內(nèi)的讀寫次數(shù)以及標(biāo)簽平均讀取信號強(qiáng)度作為標(biāo)簽的特征向量。仿真結(jié)果與算法分析表明，隨著數(shù)據(jù)量的增加，提出的壓縮算法的壓縮效果越來越好。

[1] Yunsik S,MyoungHwan J,Yong-W,et al.Tag Localization in a Two-dimensional RFID Tag Matrix[J].Future Generation Computer Systems,2017,76(11):384-390.

[2] PENG Zi-ran,WANG Guo-jun,JIANG Hua-bin,et al.Research and Improvement of ECG Compression Algorithm Based on EZW[J].Computer Methods and Programs in Biomedicine,2017,145(07):157-166.

[3] Seyed N A,Suriyaprakash N, Shobha V.A Novel Test Compression Algorithm for Analog Circuits to Decrease Production Costs[J].Integration,the VLSI Journal,2017,58(06):538-548.

[4] HAN Jia-wei,Hector G.Warehousing and Mining Massive RFID Data Sets[C].ADMA,2006:1-18.

[5] Arun K B,Mamata J,Sri K K.Warehouse Efficiency Improvement Using RFID in a Humanitarian Supply Chain:Implications for Indian Food Security System[J].Transportation Research Part E: Logistics and Transportation Review,2018,109(01):205-224.