面向RFID海量数据的若干数据挖掘技术研究

摘要

近年来，射频识别(Radio Frequency Identification，RFID)技术快速发展，阅读器与标签成本不断下降，标签识别的准确率不断提高。随着RFID技术的发展，生产商、分销商、零售商能够对供应链中的单个物品的移动进行跟踪。大型零售商如Wal-mart、Target和Albertsons已经开始在它们的仓库和物流中心部署RFID系统，并要求供应商在商品的小包装上粘贴RFID标签。RFID标签价格进一步下降，人们可以在单个商品上粘贴标签，跟踪供应链中单个物品的移动轨迹，如何管理和组织RFID系统收集的海量数据将成为研究利用RFID技术管理供应链的重点。这些海量数据存储在数据库或者数据仓库中，面对这种“数据爆炸”的现实，如何从海量数据中提取有价值的信息已显得尤为重要。数据挖掘技术的出现和发展为人们解决了这一难题，通过数据挖掘技术及其分析工具可以从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取潜在有用的信息和知识。 RFID技术用来跟踪供应链中的移动物品，RFID数据中最重要的部分就是物品的移动数据，又称路径数据或者痕迹数据，RFID数据挖掘主要工作就是路径数据挖掘。我们对路径数据挖掘技术作了深入的研究，挖掘出现频率较高的路径，为用户了解物品的移动规律和趋势，优化供应链，发现异常移动等提供有用的信息。在研究现有RFID数据挖掘方法的基础上，本文主要在单机环境下RFID频繁路径挖掘、RFID多维频繁路径挖掘、分布环境下的RFID频繁路径挖掘等几方面做了深入的研究。主要创新点如下： 1)基于传统的频繁模式挖掘和序列模式挖掘方法不能有效解决RFID频繁路径挖掘的问题，本文在充分研究RFID路径数据特点的情况下，将RFID路径数据分成若干序列数据，在现有的频繁模式和序列模式挖掘方法基础上，提出了面向RFID的高效频繁路径挖掘算法。 2)以本文的RFID频繁路径挖掘算法为基础，结合多维序列模式挖掘思想，提出两类RFID多维路径挖掘算法。一类是将多维数据与路径数据合并整体挖掘；另一类是分别挖掘多维数据和路径数据。这两类算法适用于不同的数据集，可以有效提高RFID多维路径挖掘的性能。 3)提出了一种分布环境下的RFID频繁路径挖掘算法。因为供应链是分布的，所以RFID系统也是分布的。若将所有的数据集中到单个站点再用单机环境下的算法挖掘，将会造成大量数据传输和站点资源浪费。本文利用各个站点挖掘频繁路径，再将结果存储在路径语法树中，在站点之间传输路径语法树来合并全局频繁路径。这样，不仅可以减少网络数据传输量，也可以充分利用所有站点的计算能力，提高全局的挖掘速度。 4) RFID系统不断收集移动物品的数据，需要先对数据库更新后，再挖掘用户需要的准确信息。为了解决这一问题，本文提出了更新挖掘算法。由于不断加入数据，会造成存储空间消耗过大，本文研究利用路径编码的方法，来压缩路径数据。

目录

文摘

英文文摘

声明

第一章引言

1.1研究背景

1.2课题引出

1.3论文的主要工作

1.4论文组织

第二章基本理论

2.1 RFID数据的特点

2.1.1传统关系数据库的局限

2.1.2 RFID数据

2.1.3数据仓库与OLAP

2.1.4 RFID数据仓库

2.1.5 RFID数据挖掘

2.2频繁路径挖掘

2.3多维路径挖掘

2.4分布RFID数据挖掘

2.5 RFID数据更新与数据压缩

2.6本章小结

第三章RFID频繁路径挖掘算法

3.1频繁路径定义

3.2基于Apriori思想的频繁路径挖掘算法

3.3地点序列和时间序列

3.4封闭频繁路径挖掘算法MCP(Mining Closed Paths)

3.5频繁分布路径挖掘算法divide

3.6算法性能分析

3.7本章小结

第四章RFID多维路径挖掘

4.1挖掘多维路径问题定义

4.2现有的多维路径挖掘方法

4.2.1 Shared算法的执行过程

4.2.2 Cubing算法的执行过程

4.3封闭频繁多维路径挖掘——混合挖掘

4.3.1属性值与地点序列合并的Mixed-Is算法

4.3.2属性值与时间序列合并的Mixed-ts算法

4.3.3算法性能分析

4.4封闭频繁多维路径挖掘——分开挖掘

4.4.1先属性值后路径数据的Dim-Path算法

4.4.2先路径数据后属性值的Path-Dim算法

4.4.3算法性能分析

4.5高维度多概念层数据处理

4.5.1高维度数据处理

4.5.2多概念层次数据处理

4.6本章小结

第五章RFID分布路径挖掘

5.1分布式计算

5.2分布RFID系统

5.3分布路径挖掘算法FDMFP(Fast Distributed Mining of Frequency Paths)

5.3.1分布路径挖掘的问题定义

5.3.2路径语法树

5.3.3 FDMFP算法

5.3.4算法示例

5.4算法性能分析

5.5本章小结

第六章RFID数据更新与压缩

6.1 RFID数据更新

6.1.1挖掘多个更新周期的频繁路径

6.1.2增量更新

6.2 RFID数据压缩

6.2.1路径编码

6.2.2实验结果

6.3本章小结

第七章总结与展望

7.1本文的主要研究成果

7.2未来的研究方向

参考文献

致谢

攻读学位期间发表的学术论文

攻读学位期间参加的研究工作