MFAPIOTDL：一种挖掘物联网频繁访问节点路径的新方法

冯佳音，崔 莉

(河北科技师范学院 数学与信息科技学院，秦皇岛，066004)



MFAPIOTDL：一种挖掘物联网频繁访问节点路径的新方法

冯佳音，崔 莉

(河北科技师范学院 数学与信息科技学院，秦皇岛，066004)

针对界标模式的概要结构，提出一种挖掘物联网传感器频繁访问节点路径数据的新方法MFAPIOTDL，通过在内存中构建Bit表，使算法可以单遍扫描数据集以获得有用模式。最后通过理论和实践测试算法的有效性。关键词： 物联网；数据挖掘；频繁访问路径

物联网是指通过各种信息传感设备，实时采集需要监控、连接、互动的物体或过程的信息，与互联网结合形成的一个巨大网络[1]。物联网通过收集人们在网络上留下的痕迹和脚印等海量数据。物联网产生的大数据与一般的大数据有不同的特点。物联网的数据是异构的、多样性的、非结构和有噪声的，更大的不同是它的高增长率[2]。物联网的数据有明显的颗粒性，其数据通常带有时间、位置、环境和行为等信息。物联网数据可以说也是社交数据，但不是人与人的交往信息，而是物与物、物与人的社会合作信息[3]。物联网数据挖掘不可能对所有数据进行挖掘，只能通过挖掘近期数据的关键信息，从实物虚拟物获取存储，找出数据摘要[4]。对现有数据频繁模式挖掘情况分析可知，以往的频繁模式挖掘算法在内存使用、执行时间以及挖掘结果的精确性上还存在着不足，例如，Hua-Fu Li[5]提出的DSM-PLW算法和Daesu Lee[6]设计的estDec+算法都是使用树形结构作为其数据存储结构，当数据量剧增时不利于内存存储。结合频繁模式挖掘与物联网数据，在大数据中进行频繁模式挖掘对研究物联网大数据的可用性和可分析性具有重要的意义。

针对挖掘最大频繁模式在物联网各个传感节点监控网络中不同作用，笔者提出基于界标模式的物联网数据频繁访问路径挖掘算法MFAPIOTDL(Mining Frequent Access Path in IOT Data Landmark)的设计，MFAPIOTDL算法改进自算法DSM-PLW，MFAPIOTDL算法应用界标作为其概要结构。并应用Bit表作用基于内存的数据结构来存储到来的访问模式。最后，验证算法的效率。

1 问题描述及Bit表IOT_BT结构的设计

设SND(Sensor node data)为物联网中各个传感器节点网络数据的无限序列。单个数据项SNI(sensor node itemsets)由bi-tuple(Id, pr)组成。其中Id是各个节点用户识别符，pr是表达用户节点路径的参数。设SNDP是一个传感器节点数据序列，它由前参数和后参数的序列组成。前参数指传感器首次通路路径参数，后参数意思是再次访问之前通路路径参数。当后参数发生时，前参数终止，最大前参数MFR(maximal forward reference)产生。MFR是由分割SNDP中的后参数产生的。例如{A,B,C,D,C,G,H,K}可以被分割成两个MFR——{A,B,C,D}和{ C,G,H,K }。另外，算法应用界标模型作为概要结构，界标模型是利用特定时间点和当前时间之间完整的历史数据进行挖掘。它的起始时间为1。

定义1：最大频繁子项CN-MFR 设CN-MFR是最大前参数MFR的子串(CN-MFR⊆MFR)，CN-MFR.esup表示CN-MFR的估计支持度。一个CN-MFR是最大频繁CN-MFR，当且仅当CN-MFR.esup ≥ minsup*|MFR|，minsup∈[0,1]，其中minsup∈[0,1]是用户定义的最小支持度阈值。|MFR|是迄今为止的MFR的长度；它不是任何其它CN-MFR的子串。

定义2：后缀参数 对于每个分割的MFR(R)={a1, a2, …,am}，它可以被映射为后缀suffix-references{(a1, a2, …am), (a2, a3, …am), …, (am-1, am), (am)}。所有R的后缀suffix-references都可以被认为是独立的MFR的子串。

定义3：IOT_BT (IOT Binary Table)存储结构 一个IOT_BT包含2个表，头表HT(Head Table)和Bit表BT(Binary Table)，这2个表可以如下定义：

(1)头表HT包含2个域，HT_data和HT_count。其中HT_data记录不同CN-MFR参数的标识，HT_count记录迄今为止到来的参数量。

(2) BT由3个域组成，BT_flag，BT_count 和BT_code。其中BT_flag记录BT_code中第一个不为零的参数，BT_count记录CN-MFR的数量，BT_code记录用二进制向量表示的CN-MFR。

IOT_BT存储结构的构建过程描述如下：算法IOT_BT首先映射最大前参数MFR为后缀参数集，然后插入这些后缀参数进入表HT和BT中。

算法1 构建IOT_BT (MFR)。

输入：最大前参数MFR。

输出：IOT_BT结构。

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

for each MFRi do{

Msr=mapsuffix-reference(ri, MFRi); //把MFRi映射为后缀子参数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中第一个参数

end if }

for each Msri do{

BT_flag i= ri;

BT_count=BT_count+1;

BT_code i =mapbitcode(Msri); //把Msr映射为二进制码

for each BT(BT_code) do{

if | BT_codei |<>1 then //把单个参数记入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

} } }

通过构建头表HT和Bit表BT，使界标模式中的最大前参数被快速映射为单独的后缀集后转变为二进制形式并存入二进制向量表BT中，建立二进制向量表的过程将在MFAPIOTDL算法实例中给出。

Bit表IOT_BT中的剪除优化方法

根据apriori原理[7]，只有频繁前参数可以被用来构建下一层的候选前参数。所以对于IOT_BT结构：

{JP(1)如果HT_count小于最小支持度阈值sup，这个项将从头表中删除，然后所有包括这一项的行清零，且列从BT中删除。

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

挖掘物联网中各个传感器节点网络频繁访问节点路径数据的算法MFAPIOTDL。

算法MFAPIOTDL根据BT中不同的BT_flag值把二进制数分为不同的组。即，如果BT中的不同后缀参数有同样的BT_flag，它们会分成一组进行操作。不同的后缀suffix-reference和其它的子串在同一组中执行逻辑与操作。然后，根据定义1把所有满足条件的CN-MFRs存储到临时表TT中。之后，算法MFAPIOTDL在用户指定时输出所有CN-MFR。最后，清空临时表TT。

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

算法2 挖掘动态频繁访问节点路径算法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把前参数的后缀集变为二进制数后存入BT表中，然后通过逻辑与操作进行数据的比较，当数据相应位的逻辑与操作值为真，则说明2个数据在相同的位具有同样的项，当逻辑与操作值为假说明相应位具有的值不同。通过这样的操作保证了挖掘出的频繁路径的正确性。并且所有的挖掘过程都是在头表HT和二进制向量表BT中进行的。因而比较节省操作时间。

2 MFAPIOTDL算法应用实例

问题说明：对于传感器动态访问数据，一个动态数据的片断是从t到t+t0的序列。它可以分为传感器动态数据的集合。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表示传感器标识，A，B，C，D，E表示传感器传递的参数。其传感器传输路径的序列为{(1,ABCDBC), (2,ABDECDE), (3,BCDACD)}，最大前参数为ABCD，ABDE，BD，ABE，BCD，AD，minsup=4，|MFR|=6。

在这一部分，首先通过例子来说明IOT_BT存储结构。然后，说明剪除的具体方法。最后，说明MFAPIOTDL挖掘算法的过程。

(1)IOT_BT存储结构。

首先，第一个最大前参数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)应用同样的方法转换。然后，由于|BT_code4|=|0001|=1，所以只把(D,D)插入HT。

然后，算法IOT_BT映射下一个最大前参数ABDE成为后缀suffix-reference。由于E是新的参数，算法IOT_BT添加E进入HT和BT中，如果新的后参数不同于已经存在的参数，这个新参数将插入到BT中。如果新的后参数与已经存在的参数相同，则只把相应的BT_count的值增加1。所有6个最大前参数被加入后Bit表的结果如表1所示。

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

首先，C，E的计数小于阈值，所以从HT中删除E。然后，把C，E的所有BT_code清零，删除|BT_code|=1和BT_flag是B或者是E的列。例如，首先删除列3和标识E行。又由于列6和列9的|BT_code|=1，所以删除列6和列9。然后合并列1和列3；合并列2，列5和列7。

(3) MFAPIOTDL算法过程。

根据表2中的二进制数值，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}进入TT。所以，频繁访问模式，即最大频繁sub-MFR是BD，IOT中传感器频繁访问网络路径为BD，可以通过检测这条路径观察各种突发情况。

表1 插入所有MFR生成表

表2 剪枝合并表

3 算法性能分析

从基于内存的数据结构上看，MMFI_DSSW算法应用MFI_BT作为其基于内存的数据结构，MFI_BT是BIT表的形式，访问表的时间复杂度为O(N)。又因为表中只存储二进制数，所以每个表项的空间复杂度为O(1)。而estDec+算法采用前缀树结构作为基于内存的数据结构，遍历前缀树需要的时间复杂度为O(N)(N为树的层数)，而每个结点都需要有数据域和指针域，所以其空间复杂度要远远大于MFI_BT结构的空间复杂度。

挖掘IOT中频繁访问传感节点路径的算法DSM-PLW应用森林结构存储到来的项集。遍历每棵树需要的时间复杂度同样为K*O(N)。而MFAPIOTDL算法则应用IOT_BT作为其基于内存的数据结构，访问表中每一项的时间为O(N)，从内存使用情况上看，MFAPIOTDL采用的Bit表只需要O(1)的空间存储N个到来的项集，节省了内存空间。所以，从理论分析上可以得出，算法MFAPIOTDL在内存使用和访问时间上优于算法estDec+和算法DSM-PLW。

4 结 论

本次研究针对目前物联网大数据挖掘算法中使用的基于内存的数据结构的占用空间过多的问题，提出了Bit表BT形式的基于内存的数据结构。并把这种结构应用于挖掘物联网传感器节点频繁访问路径问题。通过分析可知，应用Bit表形式的挖掘算法在内存空间的占用上要少于目前存在的以树作为存储结构的算法。

[1] 陈海明，崔莉，谢开斌.物联网体系结构与实现方法的比较研究[J].计算机学报，2013，36(1):68-188.

[2] 国脉物联网.物联网产生大数据 大数据助力物联网[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．

(责任编辑：朱宝昌)

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

秦皇岛市科学技术局科技计划项目(项目编号：201401A047 )。

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

TP311.13

A

1672-7983(2015)02-0052-05

冯佳音(1983-)，女，讲师，硕士。主要研究方向：大数据挖掘和算法。