MFAPIOTDL：一種挖掘物聯(lián)網(wǎng)頻繁訪問節(jié)點路徑的新方法

馮佳音，崔 莉

(河北科技師范學(xué)院 數(shù)學(xué)與信息科技學(xué)院，秦皇島，066004)

?

MFAPIOTDL：一種挖掘物聯(lián)網(wǎng)頻繁訪問節(jié)點路徑的新方法

馮佳音，崔 莉

(河北科技師范學(xué)院 數(shù)學(xué)與信息科技學(xué)院，秦皇島，066004)

針對界標(biāo)模式的概要結(jié)構(gòu)，提出一種挖掘物聯(lián)網(wǎng)傳感器頻繁訪問節(jié)點路徑數(shù)據(jù)的新方法MFAPIOTDL，通過在內(nèi)存中構(gòu)建Bit表，使算法可以單遍掃描數(shù)據(jù)集以獲得有用模式。最后通過理論和實踐測試算法的有效性。關(guān)鍵詞： 物聯(lián)網(wǎng)；數(shù)據(jù)挖掘；頻繁訪問路徑

物聯(lián)網(wǎng)是指通過各種信息傳感設(shè)備，實時采集需要監(jiān)控、連接、互動的物體或過程的信息，與互聯(lián)網(wǎng)結(jié)合形成的一個巨大網(wǎng)絡(luò)[1]。物聯(lián)網(wǎng)通過收集人們在網(wǎng)絡(luò)上留下的痕跡和腳印等海量數(shù)據(jù)。物聯(lián)網(wǎng)產(chǎn)生的大數(shù)據(jù)與一般的大數(shù)據(jù)有不同的特點。物聯(lián)網(wǎng)的數(shù)據(jù)是異構(gòu)的、多樣性的、非結(jié)構(gòu)和有噪聲的，更大的不同是它的高增長率[2]。物聯(lián)網(wǎng)的數(shù)據(jù)有明顯的顆粒性，其數(shù)據(jù)通常帶有時間、位置、環(huán)境和行為等信息。物聯(lián)網(wǎng)數(shù)據(jù)可以說也是社交數(shù)據(jù)，但不是人與人的交往信息，而是物與物、物與人的社會合作信息[3]。物聯(lián)網(wǎng)數(shù)據(jù)挖掘不可能對所有數(shù)據(jù)進(jìn)行挖掘，只能通過挖掘近期數(shù)據(jù)的關(guān)鍵信息，從實物虛擬物獲取存儲，找出數(shù)據(jù)摘要[4]。對現(xiàn)有數(shù)據(jù)頻繁模式挖掘情況分析可知，以往的頻繁模式挖掘算法在內(nèi)存使用、執(zhí)行時間以及挖掘結(jié)果的精確性上還存在著不足，例如，Hua-Fu Li[5]提出的DSM-PLW算法和Daesu Lee[6]設(shè)計的estDec+算法都是使用樹形結(jié)構(gòu)作為其數(shù)據(jù)存儲結(jié)構(gòu)，當(dāng)數(shù)據(jù)量劇增時不利于內(nèi)存存儲。結(jié)合頻繁模式挖掘與物聯(lián)網(wǎng)數(shù)據(jù)，在大數(shù)據(jù)中進(jìn)行頻繁模式挖掘?qū)ρ芯课锫?lián)網(wǎng)大數(shù)據(jù)的可用性和可分析性具有重要的意義。

針對挖掘最大頻繁模式在物聯(lián)網(wǎng)各個傳感節(jié)點監(jiān)控網(wǎng)絡(luò)中不同作用，筆者提出基于界標(biāo)模式的物聯(lián)網(wǎng)數(shù)據(jù)頻繁訪問路徑挖掘算法MFAPIOTDL(Mining Frequent Access Path in IOT Data Landmark)的設(shè)計，MFAPIOTDL算法改進(jìn)自算法DSM-PLW，MFAPIOTDL算法應(yīng)用界標(biāo)作為其概要結(jié)構(gòu)。并應(yīng)用Bit表作用基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)來存儲到來的訪問模式。最后，驗證算法的效率。

1 問題描述及Bit表IOT_BT結(jié)構(gòu)的設(shè)計

設(shè)SND(Sensor node data)為物聯(lián)網(wǎng)中各個傳感器節(jié)點網(wǎng)絡(luò)數(shù)據(jù)的無限序列。單個數(shù)據(jù)項SNI(sensor node itemsets)由bi-tuple(Id, pr)組成。其中Id是各個節(jié)點用戶識別符，pr是表達(dá)用戶節(jié)點路徑的參數(shù)。設(shè)SNDP是一個傳感器節(jié)點數(shù)據(jù)序列，它由前參數(shù)和后參數(shù)的序列組成。前參數(shù)指傳感器首次通路路徑參數(shù)，后參數(shù)意思是再次訪問之前通路路徑參數(shù)。當(dāng)后參數(shù)發(fā)生時，前參數(shù)終止，最大前參數(shù)MFR(maximal forward reference)產(chǎn)生。MFR是由分割SNDP中的后參數(shù)產(chǎn)生的。例如{A,B,C,D,C,G,H,K}可以被分割成兩個MFR——{A,B,C,D}和{ C,G,H,K }。另外，算法應(yīng)用界標(biāo)模型作為概要結(jié)構(gòu)，界標(biāo)模型是利用特定時間點和當(dāng)前時間之間完整的歷史數(shù)據(jù)進(jìn)行挖掘。它的起始時間為1。

定義1：最大頻繁子項CN-MFR 設(shè)CN-MFR是最大前參數(shù)MFR的子串(CN-MFR?MFR)，CN-MFR.esup表示CN-MFR的估計支持度。一個CN-MFR是最大頻繁CN-MFR，當(dāng)且僅當(dāng)CN-MFR.esup ≥ minsup*|MFR|，minsup∈[0,1]，其中minsup∈[0,1]是用戶定義的最小支持度閾值。|MFR|是迄今為止的MFR的長度；它不是任何其它CN-MFR的子串。

定義2：后綴參數(shù) 對于每個分割的MFR(R)={a1, a2, …,am}，它可以被映射為后綴suffix-references{(a1, a2, …am), (a2, a3, …am), …, (am-1, am), (am)}。所有R的后綴suffix-references都可以被認(rèn)為是獨(dú)立的MFR的子串。

定義3：IOT_BT (IOT Binary Table)存儲結(jié)構(gòu) 一個IOT_BT包含2個表，頭表HT(Head Table)和Bit表BT(Binary Table)，這2個表可以如下定義：

(1)頭表HT包含2個域，HT_data和HT_count。其中HT_data記錄不同CN-MFR參數(shù)的標(biāo)識，HT_count記錄迄今為止到來的參數(shù)量。

(2) BT由3個域組成，BT_flag，BT_count 和BT_code。其中BT_flag記錄BT_code中第一個不為零的參數(shù)，BT_count記錄CN-MFR的數(shù)量，BT_code記錄用二進(jìn)制向量表示的CN-MFR。

IOT_BT存儲結(jié)構(gòu)的構(gòu)建過程描述如下：算法IOT_BT首先映射最大前參數(shù)MFR為后綴參數(shù)集，然后插入這些后綴參數(shù)進(jìn)入表HT和BT中。

算法1 構(gòu)建IOT_BT (MFR)。

輸入：最大前參數(shù)MFR。

輸出：IOT_BT結(jié)構(gòu)。

initialize BT; // BT_flag=null, BT_count=0, BT_code=0

for each MFRi do{

Msr=mapsuffix-reference(ri, MFRi); //把MFRi映射為后綴子參數(shù)Msr1,Msr2…Msrn

for each H_data do{

if ri=H_data then

H_count=H_count+1;

else

insert ri into HT; // ri 為Msri中第一個參數(shù)

end if }

for each Msri do{

BT_flag i= ri;

BT_count=BT_count+1;

BT_code i =mapbitcode(Msri); //把Msr映射為二進(jìn)制碼

for each BT(BT_code) do{

if | BT_codei |<>1 then //把單個參數(shù)記入HT

if BT_codei=BTi(BT_code) then

BTi(BT_count)=BTi(BT_count)+1;

else

Bi=combination(BT_flag i, BT_count, BT_code i);

end if

end if

insert Bi into BT

} } }

通過構(gòu)建頭表HT和Bit表BT，使界標(biāo)模式中的最大前參數(shù)被快速映射為單獨(dú)的后綴集后轉(zhuǎn)變?yōu)槎M(jìn)制形式并存入二進(jìn)制向量表BT中，建立二進(jìn)制向量表的過程將在MFAPIOTDL算法實例中給出。

Bit表IOT_BT中的剪除優(yōu)化方法

根據(jù)apriori原理[7]，只有頻繁前參數(shù)可以被用來構(gòu)建下一層的候選前參數(shù)。所以對于IOT_BT結(jié)構(gòu)：

{JP(1)如果HT_count小于最小支持度閾值sup，這個項將從頭表中刪除，然后所有包括這一項的行清零，且列從BT中刪除。

(2)把剪除后具有相同BT_code和BT_flag的列合并，并檢查是否有列的|BT_code|值為1。

挖掘物聯(lián)網(wǎng)中各個傳感器節(jié)點網(wǎng)絡(luò)頻繁訪問節(jié)點路徑數(shù)據(jù)的算法MFAPIOTDL。

算法MFAPIOTDL根據(jù)BT中不同的BT_flag值把二進(jìn)制數(shù)分為不同的組。即，如果BT中的不同后綴參數(shù)有同樣的BT_flag，它們會分成一組進(jìn)行操作。不同的后綴suffix-reference和其它的子串在同一組中執(zhí)行邏輯與操作。然后，根據(jù)定義1把所有滿足條件的CN-MFRs存儲到臨時表TT中。之后，算法MFAPIOTDL在用戶指定時輸出所有CN-MFR。最后，清空臨時表TT。

挖掘最大頻繁CN-MFR的算法MFAPIOTDL如下所示。

算法2 挖掘動態(tài)頻繁訪問節(jié)點路徑算法MFAPIOTDL。

輸入：HT，BT，|MFR|，minsup。

輸出：頻繁路徑模式(最大頻繁CN-MFR)。

initialize temporary table TT = null; TTrow =0

for each HT_data do{

for each BT_flag= HT_datai do{

if TT=null then

{add BT_codej into TT;

TTrow=1;}

else

call compare (BT_codej, TT, |MFR|, minsup);

end if } }

output the reference in T;

Compare(BT_codej, TT, |MFR|, minsup)

{

if BT_countj≥minsup*|MFR| then

{TTrow= TTrow+1;

add BT_codej and BT_countj in TT;}

else

for each TT.codei do{

if TT.count≤minsup*|MFR| then

{ if TT.codei AND BT_codej =TT.code then

TT.count=TT.count+1;

else

{TTrow = TTrow +1

TTrow.code =BT_codej AND TT.codei

TTrow.count=TT.count+BT_count;}

end if

end if }

end if }

Delete TTrow.count≤minsup*|MFR| in TT; }

由以上算法可以看出，MFAPIOTDL把前參數(shù)的后綴集變?yōu)槎M(jìn)制數(shù)后存入BT表中，然后通過邏輯與操作進(jìn)行數(shù)據(jù)的比較，當(dāng)數(shù)據(jù)相應(yīng)位的邏輯與操作值為真，則說明2個數(shù)據(jù)在相同的位具有同樣的項，當(dāng)邏輯與操作值為假說明相應(yīng)位具有的值不同。通過這樣的操作保證了挖掘出的頻繁路徑的正確性。并且所有的挖掘過程都是在頭表HT和二進(jìn)制向量表BT中進(jìn)行的。因而比較節(jié)省操作時間。

2 MFAPIOTDL算法應(yīng)用實例

問題說明：對于傳感器動態(tài)訪問數(shù)據(jù)，一個動態(tài)數(shù)據(jù)的片斷是從t到t+t0的序列。它可以分為傳感器動態(tài)數(shù)據(jù)的集合。TS={(1,A),(1,B),(2,A),(2,B),(1,C),(3,B),(1,D),(3,C),(2,D),(2,E),(1,B),(3,D),(1,D),(2,A),(3,A),(2,B),(2,E),(3,D)}，其中1，2，3表示傳感器標(biāo)識，A，B，C，D，E表示傳感器傳遞的參數(shù)。其傳感器傳輸路徑的序列為{(1,ABCDBC), (2,ABDECDE), (3,BCDACD)}，最大前參數(shù)為ABCD，ABDE，BD，ABE，BCD，AD，minsup=4，|MFR|=6。

在這一部分，首先通過例子來說明IOT_BT存儲結(jié)構(gòu)。然后，說明剪除的具體方法。最后，說明MFAPIOTDL挖掘算法的過程。

(1)IOT_BT存儲結(jié)構(gòu)。

首先，第一個最大前參數(shù)ABDE可以被映射成為后綴suffix-reference ((A,ABCD),(B,BCD),(C,CD)和(D,D))。對于(A,ABCD)，r1=A，Sr1=ABCD。IOT_BT要把r1和Sr1兩個值插入HT和BT，H_data=A，H_count=1，BT_flag1=A，BT_count1=1， BT_code1=1111。(B,BCD),(C,CD)與(A,ABCD)應(yīng)用同樣的方法轉(zhuǎn)換。然后，由于|BT_code4|=|0001|=1，所以只把(D,D)插入HT。

然后，算法IOT_BT映射下一個最大前參數(shù)ABDE成為后綴suffix-reference。由于E是新的參數(shù)，算法IOT_BT添加E進(jìn)入HT和BT中，如果新的后參數(shù)不同于已經(jīng)存在的參數(shù)，這個新參數(shù)將插入到BT中。如果新的后參數(shù)與已經(jīng)存在的參數(shù)相同，則只把相應(yīng)的BT_count的值增加1。所有6個最大前參數(shù)被加入后Bit表的結(jié)果如表1所示。

(2)算法的剪除合并過程。

首先，C，E的計數(shù)小于閾值，所以從HT中刪除E。然后，把C，E的所有BT_code清零，刪除|BT_code|=1和BT_flag是B或者是E的列。例如，首先刪除列3和標(biāo)識E行。又由于列6和列9的|BT_code|=1，所以刪除列6和列9。然后合并列1和列3；合并列2，列5和列7。

(3) MFAPIOTDL算法過程。

根據(jù)表2中的二進(jìn)制數(shù)值，MFAPIOTDL首先初始化臨時表TT，添加{A, 2, 11010}入TT。由于{A, 1, 11000}和{A, 1, 10010}的BT_flag=A，所以它們被分成一組。然后{A, 2, 10110}在組中和其它列作邏輯與操作。由于{A, 2, 11010}的BT_count是2 <0.4*6，所以不把{A, 2, 11010}記入TT。下一步，{B, 4, 01100}進(jìn)入TT。所以，頻繁訪問模式，即最大頻繁sub-MFR是BD，IOT中傳感器頻繁訪問網(wǎng)絡(luò)路徑為BD，可以通過檢測這條路徑觀察各種突發(fā)情況。

表1 插入所有MFR生成表

表2 剪枝合并表

3 算法性能分析

從基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)上看，MMFI_DSSW算法應(yīng)用MFI_BT作為其基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，MFI_BT是BIT表的形式，訪問表的時間復(fù)雜度為O(N)。又因為表中只存儲二進(jìn)制數(shù)，所以每個表項的空間復(fù)雜度為O(1)。而estDec+算法采用前綴樹結(jié)構(gòu)作為基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，遍歷前綴樹需要的時間復(fù)雜度為O(N)(N為樹的層數(shù))，而每個結(jié)點都需要有數(shù)據(jù)域和指針域，所以其空間復(fù)雜度要遠(yuǎn)遠(yuǎn)大于MFI_BT結(jié)構(gòu)的空間復(fù)雜度。

挖掘IOT中頻繁訪問傳感節(jié)點路徑的算法DSM-PLW應(yīng)用森林結(jié)構(gòu)存儲到來的項集。遍歷每棵樹需要的時間復(fù)雜度同樣為K*O(N)。而MFAPIOTDL算法則應(yīng)用IOT_BT作為其基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，訪問表中每一項的時間為O(N)，從內(nèi)存使用情況上看，MFAPIOTDL采用的Bit表只需要O(1)的空間存儲N個到來的項集，節(jié)省了內(nèi)存空間。所以，從理論分析上可以得出，算法MFAPIOTDL在內(nèi)存使用和訪問時間上優(yōu)于算法estDec+和算法DSM-PLW。

4 結(jié) 論

本次研究針對目前物聯(lián)網(wǎng)大數(shù)據(jù)挖掘算法中使用的基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)的占用空間過多的問題，提出了Bit表BT形式的基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)。并把這種結(jié)構(gòu)應(yīng)用于挖掘物聯(lián)網(wǎng)傳感器節(jié)點頻繁訪問路徑問題。通過分析可知，應(yīng)用Bit表形式的挖掘算法在內(nèi)存空間的占用上要少于目前存在的以樹作為存儲結(jié)構(gòu)的算法。

[1] 陳海明，崔莉，謝開斌.物聯(lián)網(wǎng)體系結(jié)構(gòu)與實現(xiàn)方法的比較研究[J].計算機(jī)學(xué)報，2013，36(1):68-188.

[2] 國脈物聯(lián)網(wǎng).物聯(lián)網(wǎng)產(chǎn)生大數(shù)據(jù) 大數(shù)據(jù)助力物聯(lián)網(wǎng)[EB/OL].(2013-04-24)[2015-04-10].http://news.xinhuanet.com/info/2013-04/24/c_132335246.htm.

[3] Georg Krempl, Indre ˇZliobaite，Dariusz Brzeziński,et al.Open Challenges for Data Stream Mining Research[C]//Conference on Knowledge Discovery and Data Mining (KDD).SIGKDD Explorations，2014，16(1)：1-10.

[4] Oshini Goonetilleke,Timos Sellis,Xiuzhen Zhang,et al.Twitter Analytics:A Big Data Management Perspective[C]//Conference on Knowledge Discovery and Data Mining (KDD).SIGKDD Explorations，2014，16(1)：11-20.

[5] Li Hua-fei，Lee S Y，Shan M K．DSM-PLW:single-pass mining of path traversal patterns over streaming Web click-sequences[J]．Computer Networks:Special Issue on Web Dynamics，2006，50(10):1 474-1 487．

[6] Lee D,Lee W.Finding maximal frequent itemsets over online data streams adaptively[C]//Proceedings of the 5th IEEE International Conference on Data Mining.Houston USA：IEEE Press,2005:266-273.

[7] Agrawal R，Srikant R．Fast algorithm for mining association rules in Large Databases[C]//Jorge B Bocca,Matthias Jarke,Carlo Zaniolo.Proceedings of 20th International Conference on Very Large Data Bases.San Francisco CA USA:Morgan Kaufmann Publishers Inc，1994:487-499．

(責(zé)任編輯：朱寶昌)

MFAPIOTDL: Mining Frequent Access Path in IOT Data Landmark

FENG Jia-yin,CUI Li

(School of Mathematics and Information Science & Technology,Hebei Normal University of Science & Technology,Qinhuangdao Hebei,066004,China)

MFAPIOTDL, a new method to mine the set of frequent path traversal pattern over IOT sensor node data is proposed for the general structure of landmark model through building Bit table in the RAM so that the algorithm can scan data set single pass to gain the useful structure. The efficiency of the algorithm was proved by theory and practice at last.

IOT; data mining; frequent traversal path

10.3969/J.ISSN.1672-7983.2015.02.011

秦皇島市科學(xué)技術(shù)局科技計劃項目(項目編號：201401A047 )。

2015-04-28; 修改稿收到日期: 2015-06-03

TP311.13

A

1672-7983(2015)02-0052-05

馮佳音(1983-)，女，講師，碩士。主要研究方向：大數(shù)據(jù)挖掘和算法。