多维频繁路径算法在RFID图书馆的应用

雷赟

（江西理工大学图书馆 赣州 341000）

多维频繁路径算法在RFID图书馆的应用

雷赟

（江西理工大学图书馆 赣州 341000）

深入研究了应用于图书馆的RFID数据集，使用RFID多维频繁路径挖掘算法，按照不同的阈值、不同的尺度以及不同的维度，将图书馆的RFID数据划分为两部分，即多维模式与序列模式。经过实验验证可以看出，顺序处理非路径维数据算法和顺序处理路径数据算法两者都可以有效地挖掘出RFID多维频繁路径，并且两个算法都可以记录不同类型读者借阅图书的详细情况。通过快速有效挖掘出的射频识别图书馆管理系统中所获得信息的相关数据，方便更加合理有效地进行图书分配，以及需要购买图书分类的趋势目录，基于资源的分配依据，为图书馆管理者作出正确的决定。

RFID 多维频繁路径挖掘 图书馆管理

RFID技术在图书馆应用得越来越广泛，它所产生的路径信息也变得越来越多，研究和管理RFID系统所产生的海量数据也变得越来越重要，充分发掘其价值内涵是实现和推动RFID应用的关键因素。

一、图书馆RFID数据

图书馆RFID数据的内涵：图书馆RFID数据可以表示成一个三元组集合（EPC,Location,Time）。EPC是唯一的，用来识别一本书的电子代码。Location则为图书所在的位置，Time则是扫描图书的时间。由于在RFID数据库中加上了路径数据以及EPC标识，要想快速从RFID数据库获取数据，最关键的技术就是要挖掘移动趋势的频繁路径数据信息。

二、RFID多维数据结构

RFID多维数据结构的内涵：对RFID数据仓库的结构进行详细解析，主要包括：（1）信息表，包括图书名称、作者、出版社、图书类别等；（2）停驻表，储存在相同地点存放的所有图书的信息；（3）路径表，存放停留记录的路径信息，根据停驻表中的关联信息来生成一条路径记录。以上三个抽象的信息就成为一个RFID多维数据结构。

三、RFID多维频繁路径挖掘算法

多维路径的定义：将形如二元组的结构形式称为多维路径[1]125。

本文提出了Dim-path（顺序处理非路径维数据）与Path—dim（顺序处理路径数据）两种算法。

算法l：Dim-path算法

IN：即RFID数据库以及最小支持数阈值

OUT：封闭多维路径集合（CMP）

具体算法描述：

Step1：根据非路径维数据，选用BUC-1ike算法，对其进行挖掘封闭多维模式；

Step2：由上一步挖掘的数据建立多维模式投影数据库；

Step3：选用MCP算法，挖掘封闭多维模式的路径投影数据库；

Step4：得到准封闭多维路径，并将其加入到集合CMP；

Step5：检测CMP集合是否封闭，把所有非封闭的多维路径都删除，最后输出CMP集合。

算法2：Path-dim算法

IN：即RFID数据库以及最小支持数阈值

OUT：封闭多维路径集合（CMP）

具体算法描述：

Step1：选用MCP算法，对路径数据进行挖掘封闭路径；

Step2：为第一步得到的封闭路径建立路径投影数据库；

Step3：选用BUC-like算法，挖掘封闭多维模式的路径投影数据库；

Step4：得到的准封闭多维路径，并将其加入到集合CMP；

Step5：检测CMP集合是否封闭，把所有非封闭多维路径都删除，最后输出CMP集合。

这两种算法同样都是使用MCP算法挖掘封闭的多维路径[2]55。首先，从查找位置数据开始，建立位置数据库序列，然后挖掘封闭位置序列，建立一个停留时间投影数据库。合并之后生成准封闭路径，最后检测封闭性，把非封闭多维路径全部删除，获得封闭路径[3]105。

Dim-path算法在挖掘封闭多维模式时，选择的是BUC-1ike算法，图1的BUC树显示的是多维模式的挖掘过程。

对表1的数据执行Dim-path算法，进行封闭频繁多维路径挖掘。

Step1：根据非路径维数据，选用BUC-1ike算法，对其进行挖掘封闭多维模式；

设置min=2。根据图3.1，按照顺序，进行挖掘，得到集合CMD={（高级程序设计C++）（*）:4;（高级程序设计C++）（西安电子科技大学出版社）:2;（高级程序设计C++）（北京理工大学出版社）:2}。

Step2:构建多维模式投影数据库；

PDB（高级程序设计C++.*）={（f1,1）（f2,3）（f4,5）（f5, 9）,（f1,1）（f2,3）（f4,5）（f5,6）,（f1,2）（f2,3）（f4,5）（f5,6）,（f1,2）（f2,3）（f3,5）（f4,5）}；

PDB（高级程序设计C++.西安电子科技大学出版社）={（f1,1）（f2,3）（f4,5）（f5,9）,（f1,1）（f2,3）（f4,5）（f5,6）}；

PDB（高级程序设计C++.北京理工大学出版社）={（f1,2）（f2,3）（f4,5）（f5,6）,（f1,2）（f2,3）（f3,5）（f4,5）}；

Step3：选用MCP算法，挖掘封闭多维模式的路径投影数据库；

CP（高级程序设计C++.*）={（f1,*）（f4,*）:4;（f1,2）（f4, *）:3;（f1,*）（f2,3）（f4,5）（f5,*）:3;（f1,2）（f2,3）（f4,3）（f5,*）:3;（f1,*）（f2,3）（f4,5）（f5,6）:2}；

CP（高级程序设计C++.西安电子科技大学出版社）= {（f1,*）（f2,3）（f4,5）（f5,*）:2}；

CP（高级程序设计C++.北京理工大学出版社）={（f1, 2）（f2,3）（f4,*）:2}；

Step4：合并封闭多维模式和封闭路径，得到CMP集合；

CMP={（高级程序设计C++）（*）（f1,*）（f4,*）:4;（高级程序设计C++）（*）（f1,*）（f2,3）（f4,5）（f5,*）:3;（高级程序设计C++）（*）（f1,2）（f2,3）（f4,5）（f5,*）:2;（高级程序设计C++）（*）（f1,*）（f2,3）（f4,5）（f5,6）:2;（高级程序设计C++）（西安电子科技大学出版社）（f1,*）（f2,3）（f4,5）（f5,*）:2;（高级程序设计C++）（北京理工大学出版社）（f1,2）（f2,3）（f4,*）:2}。

Step5：检测封闭性，删除非封闭多维路径；

最后（f1,2）（f4,*）:2;不是封闭多维路径，被删除，执行完毕。

对表1的数据执行Path-dim算法，进行封闭频繁多维路径挖掘。

Step1：选用MCP算法，对路径数据进行挖掘封闭路径；

设置min=2。选用MCP算法，挖掘封闭路径CP={（f1, *）（f4,*）:3;（f1,2）（f4,*）:2;（f1,*）（f2,3）（f4,5）（f5,*）:3;（f1,2）（f2,3）（f4,5）（f5,*）:2;（f1,*）（f2,3）（f4,5）（f5,6）:2}；

Step2：构建路径投影数据库；

PDF（f1,*）（f4,*）={（高级程序设计C++）（西安电子科技大学出版社）;（高级程序设计C++）（西安电子科技大学出版社）;（高级程序设计C++）（北京理工大学出版社）;（高级程序设计C++）（北京理工大学出版社）}；

PDF（f1,2）（f4,*）={（高级程序设计C++）（西安电子科技大学出版社）;（高级程序设计C++）（北京理工大学出版社）;（高级程序设计C++）（北京理工大学出版社）}；

PDF（f1,*）（f2,3）（f4,5）（f5,*）={（高级程序设计C++）（西安电子科技大学出版社）;（高级程序设计C++）（西安电子科技大学出版社）;（高级程序设计C++）（北京理工大学出版社）}；

PDF（f1,2）（f2,3）（f4,5）（f5,*）={（高级程序设计C++）（西安电子科技大学出版社）;（高级程序设计C++）（北京理工大学出版社）}；

PDF（f1,*）（f2,3）（f4,5）（f5,6）={（高级程序设计C++）（西安电子科技大学出版社）;（高级程序设计C++）（北京理工大学出版社）}；

Step3：选择利用BUC-like算法，挖掘封闭多维模式；

CMD（f1,*）（f4,*）={（高级程序设计C++）（*）:3;（高级程序设计C++）（西安电子科技大学出版社）:2;（高级程序设计C++）（北京理工大学出版社）:1}；

CMD（f1,2）（f4,*）={（高级程序设计C++）（*）:2;（高级程序设计C++）（西安电子科技大学出版社）:1;（高级程序设计C++）（北京理工大学出版社）:1}；

CMD（f1,*）（f2,3）（f4,5）（f5,*）={（高级程序设计C++）（*）:3;（高级程序设计C++）（西安电子科技大学出版社）: 2;（高级程序设计C++）（北京理工大学出版社）:1}；

CMD（f1,2）（f2,3）（f4,5）（f5,*）={（高级程序设计C++）（*）:2}；

CMD（f1,*）（f2,3）（f4,5）（f5,6）={（高级程序设计C++）（*）:2}；

Step4：得到的准封闭多维路径，并将其加入到集合CMP；

图1 树

图2 不同最小支持度阈值下算法执行时间比较

图3 在不同维度下比较算法的执行时间

图4 尺度不同时比较算法时间

图5 不同密度算法的操作比较

CMP={（高级程序设计C++）（*）（f1,*）（f4,*）:3;（高级程序设计C++）（*）（f1,*）（f2,3）（f4,5）（f5,*）:3;（高级程序设计C++）（*）（f1,2）（f2,3）（f4,5）（f5,*）:2;（高级程序设计C++）（*）（f1,*）（f2,3）（f4,5）（f5,6）:2;（高级程序设计C++）（西安电子科技大学出版社）（f1,*）（f2,3）（f4,5）（f5,*）:2;（高级程序设计C++）（北京理工大学出版社）（f1,2）（f2,3）（f4,*）:1}。

Step5：最后删除非封闭多维路径。

四、在图书馆中应用的实验结果分析

本文将通过以下几个实验的比较来进一步验证Dim-Path和Path-Dim算法的可行性和准确性。

实验环境是CPUIntelCorei5，4G内存，2TB硬盘；Microsoft Windows XP；Microsoft Visual C++6.0。

实验使用的数据是模拟数据。支持度用支持数与数据库记录数的比值来表示。

表1 RFID数据库示例

实验1：取最小支持度阈值（a）若干，非路径维维度为3，RFID图书馆数据库中存有6万条数据。实验得出的结果如图2所示。

由图2可知，随着a的增大，执行算法所需要的时间逐渐降低[4]89。同样的，Path-dim算法最终算法的运行所需时间明显缩短了。

实验2：取若干个非路径维度，RFID图书馆数据库中存有6万条数据，最小支持度阈值为0.01。实验得出的结果如图3所示。

分别进行了路径维数和非路径维度的挖掘，并分离出驻留时间序列和位置序列的数据，该方法明显降低了算法的执行时间。在Dim-Path算法执行后可能会出现封闭频繁路径模式的空集合；同样的，Path-Dim算法也可能会出现封闭频繁多维模式的空集合。Dim-Path算法的复杂度要高于Path-Dim算法。因此Dim-path算法花费的时间比Path-dim算法花费的时间长。

实验3：RFID图书馆数据库存储从6万条数据增加到10万条，最小支持度阈值为0.01。实验得出的结果如图4所示。

由图4可以看出,数据库记录的次数越多，实现这两种算法的时间越长，不同的是，非路径维算法的时间增加明显大于路径算法。

实验4：以RFID图书馆数据库中存储了6万条记录为例，设置非路径维维度为3，并且设置最小支持度阈值为0.01。实验得出的结果如图5所示。从图5可以看出，随着密度的降低，非路径维属性的值将逐渐分散，而封闭的尺寸模式的数量将逐渐变小。

从图5可以看出，非路径维密度大，则Dim-Path算法挖掘所得到的封闭频繁多维模式更多，效率低，Path-Dim算法要挖掘的多维停留时间序列更少，效率高。密度减少后，Dim-Path算法的工作量变小。Path-Dim算法在密度降低后，工作量增大。

实验得出：当封闭多维模式数量较多的时候，选择Path-dim算法，则效率相对更高。当封闭多维模式数量较少的时候，选择Dim-path算法，则效率相对更高[5]15。Dim-path算法对数据进行了多次扫描，所以效率低。依据数据库，来选择合适的算法，可以取得较为理想的挖掘效果。

本文深入研究了多维频繁路径挖掘算法，针对RFID技术所生成的海量路径数据集，提出了两种算法，即Dim—path与Path-dim挖掘算法实验结果表明，本文所提出的算法可以高效准确的对RFID图书馆数据有效地进行多维频繁路径挖掘。本文算法能高效挖掘RFID图书馆管理系统中的相关数据所获取的信息，方便更加合理有效的图书分配，以及需要购买图书分类的趋势目录，基于资源的分配依据，为图书馆管理者作出正确的决定。

[1]宗莹.分析RFID技术在图书馆中的应用[J].电子技术与软件工程.2016（12）.

[2]江波.基于RFID的图书馆馆藏管理方法研究[J].计算机集成制造系统.2015（5）.

[3]陈嘉懿,曲建峰,李鲍.高校图书馆超高频RFID数据模型规范研究[J].大学图书馆学报.2014（5）.

[4]王莉.图书馆RFID标签应用比较研究[J].图书馆理论与实践. 2013（3）.

[5]向琼.基于UFHRFID的图书馆智能管理系统分析与实现[D].厦门大学，2014.

★作者雷赟，江西理工大学图书馆副研究馆员，研究方向维图书馆数字化自动化。

2014年江西省艺术科学规划项目（YG2014093）。

G201

A

2016-09-08