馮佳音，崔 莉

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

?

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

馮佳音，崔 莉

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

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

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

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

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

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

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

定義2：后綴參數(shù) 對(duì)于每個(gè)分割的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)存儲(chǔ)結(jié)構(gòu) 一個(gè)IOT_BT包含2個(gè)表，頭表HT(Head Table)和Bit表BT(Binary Table)，這2個(gè)表可以如下定義：

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

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

IOT_BT存儲(chǔ)結(jié)構(gòu)的構(gòu)建過(guò)程描述如下：算法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中第一個(gè)參數(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 //把單個(gè)參數(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

} } }

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

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

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

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

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

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

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

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

算法2 挖掘動(dòng)態(tài)頻繁訪問(wèn)節(jié)點(diǎn)路徑算法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表中，然后通過(guò)邏輯與操作進(jìn)行數(shù)據(jù)的比較，當(dāng)數(shù)據(jù)相應(yīng)位的邏輯與操作值為真，則說(shuō)明2個(gè)數(shù)據(jù)在相同的位具有同樣的項(xiàng)，當(dāng)邏輯與操作值為假說(shuō)明相應(yīng)位具有的值不同。通過(guò)這樣的操作保證了挖掘出的頻繁路徑的正確性。并且所有的挖掘過(guò)程都是在頭表HT和二進(jìn)制向量表BT中進(jìn)行的。因而比較節(jié)省操作時(shí)間。

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

問(wèn)題說(shuō)明：對(duì)于傳感器動(dòng)態(tài)訪問(wèn)數(shù)據(jù)，一個(gè)動(dòng)態(tài)數(shù)據(jù)的片斷是從t到t+t0的序列。它可以分為傳感器動(dòng)態(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)識(shí)，A，B，C，D，E表示傳感器傳遞的參數(shù)。其傳感器傳輸路徑的序列為{(1,ABCDBC), (2,ABDECDE), (3,BCDACD)}，最大前參數(shù)為ABCD，ABDE，BD，ABE，BCD，AD，minsup=4，|MFR|=6。

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

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

首先，第一個(gè)最大前參數(shù)ABDE可以被映射成為后綴suffix-reference ((A,ABCD),(B,BCD),(C,CD)和(D,D))。對(duì)于(A,ABCD)，r1=A，Sr1=ABCD。IOT_BT要把r1和Sr1兩個(gè)值插入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映射下一個(gè)最大前參數(shù)ABDE成為后綴suffix-reference。由于E是新的參數(shù)，算法IOT_BT添加E進(jìn)入HT和BT中，如果新的后參數(shù)不同于已經(jīng)存在的參數(shù)，這個(gè)新參數(shù)將插入到BT中。如果新的后參數(shù)與已經(jīng)存在的參數(shù)相同，則只把相應(yīng)的BT_count的值增加1。所有6個(gè)最大前參數(shù)被加入后Bit表的結(jié)果如表1所示。

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

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

(3) MFAPIOTDL算法過(guò)程。

根據(jù)表2中的二進(jìn)制數(shù)值，MFAPIOTDL首先初始化臨時(shí)表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。所以，頻繁訪問(wèn)模式，即最大頻繁sub-MFR是BD，IOT中傳感器頻繁訪問(wèn)網(wǎng)絡(luò)路徑為BD，可以通過(guò)檢測(cè)這條路徑觀察各種突發(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表的形式，訪問(wèn)表的時(shí)間復(fù)雜度為O(N)。又因?yàn)楸碇兄淮鎯?chǔ)二進(jìn)制數(shù)，所以每個(gè)表項(xiàng)的空間復(fù)雜度為O(1)。而estDec+算法采用前綴樹(shù)結(jié)構(gòu)作為基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，遍歷前綴樹(shù)需要的時(shí)間復(fù)雜度為O(N)(N為樹(shù)的層數(shù))，而每個(gè)結(jié)點(diǎn)都需要有數(shù)據(jù)域和指針域，所以其空間復(fù)雜度要遠(yuǎn)遠(yuǎn)大于MFI_BT結(jié)構(gòu)的空間復(fù)雜度。

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

4 結(jié) 論

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

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

[2] 國(guó)脈物聯(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ù)局科技計(jì)劃項(xiàng)目(項(xiàng)目編號(hào)：201401A047 )。

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

TP311.13

A

1672-7983(2015)02-0052-05

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