一种基于序列模式的RFID 数据挖掘算法
2015-07-13张长海
张长海
摘要：随着大数据海量增长和物联网技术快速发展，RFID（射频识别技术）数据挖掘技术已成为当前研究的热点.为此，该文重点研究了RFID移动数据特点，并根据数据特性提出一种高效的基于序列模式的RFID移动数据挖掘算法。该算法将RFID移动数据库分为两部分进行挖掘，首先采用高效的序列模式挖掘算法挖掘LOCATION序列数据，然后对挖掘LOCATION序列数据集进行TIME序列数据挖掘，进而组合LOCATION序列集和TIME序列集产生有效的RFID移动数据。实验结果表明该算法能够有效地挖掘RFID移动序列数据，处理时间短，效率高。
关键词： RFID移动数据； 序列模式技术； 数据挖掘技术
中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）13-0259-02
Abstract： With the Internet of Things technology， RFID （radio frequency identification technology） data mining technology has become a hot research. focus on the logistics and transport characteristics of RFID data path， proposed an efficient path for RFID-based sequential pattern data mining algorithms the algorithm uses divide and conquer technique， place the RFID data into sequence data and time series data mining， respectively， and thus the effective combination of location data and time series data sequence to generate a valid path to RFID data. Case analysis shows that through the algorithm： in the RFID path database， this method can efficiently tap the RFID path data.
Key words： RFID data； sequential patterns； data mining
随着信息化社会推进，物联网技术越来越受到关注，国家政府大力支持物联网产业发展，其中RFID技术产业更是成为社会热点。RFID技术产业主要包含射频识别收发端、短距离无线传输端和后台数据处理端，其中数据处理端尤为重要。现在社会RFID技术已经应用到各行各业，有图书馆图书信息管理、零售商商品信息管理、物流仓储管理、信息化物流运输等。近几年来，随着物联网技术产业快速发展，RFID产业产生大量RFID数据。那么，如何能够有效地挖掘到有价值的RFID数据，能够为企事业单位提供更加有效的决策支持尤为重要，因此，RFID数据挖掘逐渐成为社会研究热点。
世界上很多零售商都已经开始使用RFID技术，尤其是在零售产业的仓储和物流环节。随着电子信息技术推进，电子标签价格逐步下降，各大零售商开始在大量物品商品包装上黏贴RFID电子标签，以能够有效地跟踪监控商品。商品上部署的RFID系统生成移动轨迹，对于供应链管理等有很大价值，同时RFID系统会产生大量的RFID数据，面对这种海量式、数据爆炸式的RFID数据，如何挖掘出有意义的数据尤为重要。目前社会上存在一些RFID数据挖掘方法：如采用传统的序列模式挖掘方法，这种方法没有考虑RFID数据特性，把RFID数据看做一个整体数据集进行挖掘，因此，挖掘效率低，挖掘结果不够精确。为了能够有效地挖掘RFID移动数据，本文提出一种RFID移动数据挖掘算法，该算法该算法将RFID移动数据库分为两部分进行挖掘，首先采用高效的序列模式挖掘算法挖掘LOCATION序列数据，然后对挖掘LOCATION序列数据集进行TIME序列数据挖掘，进而组合LOCATION序列集和TIME序列集产生有效的RFID移动数据。实验结果表明该算法能够有效地挖掘RFID移动序列数据，处理时间短，效率高。
1 基于序列模式的RFID数据挖掘算法
1.1 RFID数据挖掘基本概念
RFID序列数据库如图表1所示，该数据库内有4条RFID数据记录，如何从这四条数据记录挖掘出有价值的信息数据至关重要。首先，4条数据记录中的（潍坊）、（青岛）、（济南）、（泰安）表示RFID移动数据中的地点数据，可称之为地点序列数据；数据记录中的（1）、（1）、（1）、（2）表示RFID移动数据中的时间数据，可称之为时间序列数据。因此，有如下定义：
定义1 如果RFID数据库中有一条记录：p=（s1， l1）（s2， l2）...（sn， ln），那么，该记录中的tl=（s1）（s2）...（sn）称之为该记录的RFID地点序列，其为该数据库的主要数据参数。
定义2 如果RFID数据库中有一条记录：p=（s1， l1）（s2， l2）...（sn， ln），那么，该记录中的ql=（l1）（l2）...（ln）称之为该记录的RFID时间序列，其为该数据库的次要数据参数。
上表四条记录中，第一条记录和第三条记录中的地点序列数据{（潍坊）、（青岛）、（济南）、（泰安）}出现过2次，假设设置该数据库支持数阈值为2，那么该地点序列不存在长度更长的序列，因此，称之为频繁地点序列。有如下定义：
定义3假如存在一条路径序列数据T，且不存在路径序列数据S，使得T
例1 表1所示的数据库中，第一条序列数据（潍坊， 1）（青岛， 1）（济南， 1）（泰安， 2）中的{（潍坊）、（青岛）、（济南）、（泰安）}为地点序列数据，{（1）、（1）、（1）、（2）}为时间序列数据。
例2表1所示的数据库中，前四条序列数据的地点序列数据分别是{（潍坊）、（青岛）、（济南）、（泰安）}、{（潍坊）、（青岛）、（泰安）}、{（潍坊）、（青岛）、（济南）、（泰安）}、{（潍坊）、（青岛）、（泰安）}。如果该RFID序列数据库支持数阈值为2，那么地点序列数据{（潍坊）、（青岛）、（济南）、（泰安）}满足最小支持数2，即满足在RFID数据库记录中出现2次条件，同时该地点序列数据{（潍坊）、（青岛）、（济南）、（泰安）}又不存在超序列， 因此，称之为频繁地点序列数据。
1.2基于序列模式的RFID数据挖掘算法描述
本文中将采用分治策略，即将RFID数据库中的序列数据分为地点序列数据和时间序列数据进行处理，从地点序列数据库中挖掘出频繁的地点序列，然后对频繁地点序列进行映射，形成候选时间序列集合，然后采用数据库挖掘方法挖掘候选时间序列集合，该方法简单有效，挖掘数据完整。
基于序列模式的RFID数据挖掘算法描述如下：
输入： RFID sequential_DB， Min_Support.
输出： The full frequent RFID data for CD.
1： 投影RFID序列数据库，构造RFID地点序列数据库集合DataB=L_sequence（RFID sequential DB）。
2： 按照给定最小支持度阈值计算该RFID序列数据库的最小支持数值为Min_count=|DataB|*Min_Support。
3： 调用经典序列数据挖掘算法APRIORI算法，生成频繁地点序列数据集。
4： 投影频繁地点序列数据集，生成与频繁地点序列数据集对应的候选时间序列数据集。
5： 调用经典序列数据挖掘算法APRIORI算法，生成频繁时间序列数据集。
6： 将频繁地点序列数据集和频繁时间序列数据集进行组合，依据APRIORI性质检测组合数据集的封闭性，同时删除非封闭数据集。
7： 返回生成CD。
2 RFID数据挖掘算法实例分析
物联网系统下层采集数据，经过数据清洗等组成RFID路径序列数据库。本文举例如表1所示。假设该RFID路径序列数据库最小支持数阈值Min_support=0.5，那么挖掘整个RFID频繁数据序列过程如下：
第一步，投影RFID路径序列数据库，生成RFID地点序列数据库集合，如表2所示。
3 结束语
随着物联网技术高速发展，将产生海量式数据。为此，本文提出一种挖掘RFID路径序列数据的算法。该算法将RFID移动数据库分为两部分进行挖掘，首先采用高效的序列模式挖掘算法挖掘LOCATION序列数据，然后对挖掘LOCATION序列数据集进行TIME序列数据挖掘，进而组合LOCATION序列集和TIME序列集产生有效的RFID移动数据。通过实例测试分析，该算法能够有效挖掘RFID价值数据，为企业提供智能决策支持。今后我们将重点研究对该RFID挖掘算法的优化及更新。
参考文献：
[1] 马传香， 余啸， 李伟亮， 等. MR-GSP： 基于Map-Reduce的序列模式挖掘算法[J]. 计算机应用研究，2015（11）.
[2] 邓广彪. 规范化序列模式在读者借阅行为模式挖掘的应用研究[J]. 计算机时代， 2014（4）.
[3] 冯丽芸. 数据挖掘在我国医保方面应用综述[J]. 电脑知识与技术， 2014（3）.
[4] 胡孔法， 陈竹西. 现代物流系统中的频繁封闭路径挖掘算法[J]. 计算机集成制造系统， 2009（4）： 229-235.
[5] Zhang Changhai， Hu Kongfa. FMGSP： An Efficient Method of Mining Global Sequential Patterns[C]. Hainan， China： FSKD，2007 ： 761-765.
