一种基于MP－tree的频繁路径挖掘算法

赵 利，徐永成，胡孔法，陈 崚

（扬州大学 信息工程学院，江苏 扬州 225127）

射频识别［1－3］（radio frequency identification，RFID）是一种非接触式的自动识别技术，目前已广泛应用于制造业、医疗护理和交通运输等多个领域.RFID标签可以贴在一包物品、一箱物品甚至单个物品上，当标签进入磁场时会发送自身的EPC（electronic product code）编码等信息，部署在不同位置的RFID阅读器通过天线发送一定频率的射频信号，读取标签中的信息并解码后将数据送至RFID中间件［4－5］进行相关处理，RFID中间件对数据进行简单的过滤、清洗和融合等处理后再传送给网络上的其他用户.分析物品在供应链中的移动可以得到物品的路径痕迹信息，了解这些路径信息可以极大地提高商业运转的效率；但是直接对这些路径数据进行分析必然带来数据的爆炸，因此必须运用有效的方法对数据进行预处理.然而，到目前为止，针对RFID数据管理技术的研究还不是很多，很多问题还有待解决.由于RFID路径信息的特殊性和分析的复杂性，因此有关挖掘频繁路径［6－8］的算法并不多，而且效率很低.如果应用传统的Apriori算法［9－10］，则效率非常低，也不切实际，因为将Apriori算法应用于RFID移动路径数据，产生的候选项将是不可估计的.本文就是在这些工作的基础上，引入挖掘频繁路径的思想，提出了挖掘频繁路径的算法MP（movement path）－mine.

1 相关概念和定义

RFID数据一般由三元组组成，形如（EPC，location，time），其中EPC是对每个物品进行唯一标识的电子产品编码，location表示阅读器读取发生的位置，time表示阅读器读取发生的时间.用数对pi＝（li，ti）表示对象在时间ti访问了li，规定如果p1＝p2，则必须使t1＝t2并且l1＝l2，这样将一系列记录集成起来就能得到物品的移动路径信息，形如〈（l1，t1），（l2，t2），…，（li，ti），…，（lm，tm）〉.令T＝〈（l1，t1），（l2，t2），…，（lm，tm）〉，称T 是一个长度为m 的模式，即m－pattern.

定义1 假设有路径p1＝（a1），（a2），…，（ai），…，（am），p2＝（b1），（b2），…，（bj），…，（bn），其中ai和bj都是形如（li，ti）的路径段，i＝1，2，…，m；j＝1，2，…，n.若存在一组整数1≤j1≤j2≤…≤jm≤n，有a1⊆bj1，a2⊆bj2，…，am⊆bjn成立，则称p1是p2的子路径，记为p1⊆p2.

定义2 设置一个支持数阈值δ，令support p为路径p的支持数，表示RFID数据库中包含路径p的RFID数据元组的数量.若support p≥δ，则称路径p为频繁路径（frequency－path）.

2 挖掘频繁路径算法：MP－mine

2.1 构建 MP－tree（移动路径树）

构建MP－tree可以带来两方面好处：①只须扫描数据库一次就可以挖掘出所有的频繁移动路径；②MP－tree属于压缩状态，便于加载到存储器中进行有效处理.

在MP－tree构建过程中，用一个节点表来记录所有不同标签第一次出现的地址和总共的计数，MP－tree中的每个节点（用 MR－node表示）都采用以下的结构存储：MR－node：＝｛label，parent－link，next－link，children table｝，其中label用来表示这个节点，parent－link和next－link是两个指针，分别指向该节点的父节点和下一个节点，children table用来存储该节点的所有孩子节点.对于每一个TR－tree，可用一个头表来记录时间序列的层次结构，表中每个元素都设一个指针，表中的第n个元素就指向TR－tree中第n层的第1个节点.在TR－tree中每个节点都设一个指针，用于指向它的兄弟节点，TR－tree中每个节点都采用以下结构存储：TR－node：＝｛label，parent－link，peer－link，children table｝.

算法1：MP－tree构建算法

输入：物品的RFID移动路径信息库D；输出：MP－tree.

第1步：从D中选取一条有序的移动路径序列p，从p中分别提取路径序列和时间序列；

第2步：MP－tree的插入，①从根节点开始将路径序列插入MP－tree中；②用一个节点表记录路径中出现的节点的计数；③设置每个节点的parent－link和next－link；

第3步：TR－tree的插入，①在路径序列的尾节点插入对应的时间序列；②如果TR－tree是新构建的，则用一个头表来记录时间序列的层次结构，表中每个元素都设一个指针，表中的第n个元素就指向TR－tree中第n层的第1个节点；③设置TR－tree中每个插入节点的parent－link和peerlink；

第4步：如果在D中有更多的移动路径序列，则回到第1步，否则返回当前的MP－tree.

2.2 MP－mine算法

算法2：MP－mine算法

输入：一个MP－tree（MT），最小支持度阈值δ；输出：所有频繁的移动路径序列.

第1步：浏览节点表中的每个标签，将节点计数大于最小支持度阈值δ的节点存储在集合M－L中；

第2步：如果M－L为空，则输出MT的前缀模式并返回；

第3步：对集合M－L中的每个标签l进行如下处理：①将每个标签l对应TR－tree中的所有不同节点以及计数存储到集合L－T中，然后将L－T中计数大于δ的标签存储到集合TR－L中；②如果TR－L为空，则输出MT的前缀模式并返回；③对TR－L中每个标签t，以（l，t）作为前缀，重新构造一个MP－tree MP′；④ 对于MP′，递归调用以上方法进行频繁移动路径挖掘.

整个挖掘过程采用深度优先搜索（DFS）的方法，构建MP－tree和挖掘频繁的移动路径采用递归的方法.

3 实验与结果分析

为了进一步说明本文MP－mine算法的有效性，现将其与Apriori算法进行比较.本文通过对同一RFID路径数据库采用不同的支持度以及不同的路径长度进行了实验对比.实验环境基于Windows XP SP3，内存为2GB，CPU为AMD，2.0GHz，实验环节使用Visual C＋＋6.0编写，采用的实验数据为基于某RFID物流管理系统中的人工合成数据.

实验1比较了两种挖掘算法的运行时间.通过同一路径数据库下不同的最小支持度来比较两种算法的效果，实验结果如图1所示.实验1的路径数据库所具有的路径数目为100 000，最小支持度阈值为0.1% ～0.5%.

由图1可见，当最小支持度阈值较小时，MP－mine算法的优势比较明显，因为最小支持度阈值较小时，相应频繁路径的最大长度较大；随着最小支持度阈值的不断增大，Apriori算法的优势越发明显.因为随着最小支持度阈值的不断增大，频繁路径的最大长度不断减小，相应的Apriori算法扫描数据库次数减少.对于MP－mine自身，因为无论频繁路径长度如何变化，算法扫描数据库的次数均为1，所以算法的运行时间较少.

实验2通过不同大小的路径数据库比较了两种挖掘算法的运行时间.该实验采用的minSup为0.5，路径数据库大小从包含100 000条路径到包含500 000条路径，实验结果如图2所示.

图1 不同最小支持度阈值下的运行时间比较Fig.1 Execution time for different support thresholds

图2 不同路径计数下的运行时间Fig.2 Execution time for different paths

由图2可见，随着数据库中路径数的不断增大，两种算法的运行时间都相应增加，因为路径数越大，扫描数据库的时间越长；路径数越大，MP－mine算法的优势越发明显，这是因为随着路径数的不断增大，Apriori算法将产生大量的候选项，同时扫描数据库的时间也不断增加，因此算法花费时间增加的速度越来越快.对于MP－mine自身，因为无论频繁路径长度如何变化，算法扫描数据库的次数均为1，所以时间相应增加的趋势不是十分明显.

［1］陈竹西，孙艳，胡孔法，等.基于路径编码的RFID数据压缩技术研究［J］.扬州大学学报：自然科学版，2008，11（2）：53－56.

［2］GONZALEZ H，HAN Jia－wei，LI Xiao－lei，et al.Warehousing and analyzing massive RFID data sets［C］／／Proceedings of the 22nd International Conference on Data Engineering.Washington，DC：IEEE Computer Society，2006：83.

［3］CHAWATHE S S，KRISHNAMURTHY V，RAMACHANDRAN S，et al.Managing RFID data［C］／／Proceedings of the 30th International Conference on Very Large Data Bases.Toronto：Morgan Kaufmann，2004：1189－1195.

［4］PARK Sung－mee，SONG Jeong－hwan，KIM Chae－soo，et al.Load balancing method using connection pool in RFID middle ware［C］／／Proceedings of the Fifth ACIS International Conference on Software Engineering Research，Management and Applications.Busan：［s.n.］，2007：132－137.

［5］AL－JAROODI J，AZIZ J，MOHAMED N.Middle ware for RFID systems：an overview［C］／／Proceedings of the 2009 33rd Annual IEEE International Computer Software and Applications Conference.Washington，DC：IEEE Computer Society，2009：154－159.

［6］WANG Jian－yong，HAN Jia－wei.BIDE：efficient mining of frequent closed sequences［C］／／Proceedings of 20th International Conference on Data Engineering.Boston：IEEE Computer Society，2004：79－90.

［7］ZHANG Hong－jiang，YANG Qiang，SU Zhong.What Next：a prediction system for web requests using N－gram sequence models［C］／／Proceedings of the First International Conference on web Information Systems and Engineering.Washington，DC：IEEE Computer Society，2000：200－207.

［8］HAN Jia－wei，PEI Jian，YIN Yi－wen.Mining frequent patterns without candidate generation［C］／／Proceedings of the ACM SIGMOD International Conference on Management of Data.New York，NY：ACM，2000：1－12.

［9］PORKODI R，BHUVANESWARI V，RAJESH R，et al.An improved association rule mining technique for XML data using XQUERY and apriori algorithm ［C］／／Proceedings of the 2009IEEE International Advance Computing Conference.Patiala：［s.n.］，2009：1510－1514.

［10］SHI Yong－ge，ZHOU Yi－qun.An improved apriori algorithm ［C］／／Proceedings of 2010IEEE International Conference on Granular Computing.Washington，DC：IEEE Computer Society，2010：759－762.?