（计算机应用技术专业论文）面向rfid海量数据的若干数据挖掘技术研究.pdf

陈竹西：面向r f i d 海量数据的若干数据挖掘技术研究 摘要 近年来，射频识别限a d i of r e q u e n c yi d e n t i f i c a t i o n , r f i d ) 技术快速发展，阅读器与 标签成本不断下降，标签识别的准确率不断提高。随着r f i d 技术的发展，生产商、 分销商、零售商能够对供应链中的单个物品的移动进行跟踪。大型零售商如w a l m a r t 、 t a r g e t 和a l b e r t s o n s 已经开始在它们的仓库和物流中心部署r f i d 系统，并要求供应商 在商品的小包装上粘贴r f i d 标签。r f i d 标签价格进一步下降，人们可以在单个商品 上粘贴标签，跟踪供应链中单个物品的移动轨迹，如何管理和组织r f i d 系统收集的 海量数据将成为研究利用r f i d 技术管理供应链的重点。这些海量数据存储在数据库 或者数据仓库中，面对这种“数据爆炸 的现实，如何从海量数据中提取有价值的信 息已显得尤为重要。数据挖掘技术的出现和发展为人们解决了这一难题，通过数据挖 掘技术及其分析工具可以从大量的、不完全的、有噪声的、模糊的、随机的实际应用 数据中，提取潜在有用的信息和知识。 r f i d 技术用来跟踪供应链中的移动物品，r f i d 数据中最重要的部分就是物品的 移动数据，又称路径数据或者痕迹数据，r f i d 数据挖掘主要工作就是路径数据挖掘。 我们对路径数据挖掘技术作了深入的研究，挖掘出现频率较高的路径，为用户了解物 品的移动规律和趋势，优化供应链，发现异常移动等提供有用的信息。在研究现有r f i d 数据挖掘方法的基础上，本文主要在单机环境下r f i d 频繁路径挖掘、r f i d 多维频繁 路径挖掘、分布环境下的r f i d 频繁路径挖掘等几方面做了深入的研究。主要创新点 如下： 1 ) 基于传统的频繁模式挖掘和序列模式挖掘方法不能有效解决r f i d 频繁路径挖 掘的问题，本文在充分研究r f i d 路径数据特点的情况下，将r f i d 路径数据分成若干 序列数据，在现有的频繁模式和序列模式挖掘方法基础上，提出了面向r f i d 的高效 频繁路径挖掘算法。 2 ) 以本文的r f i d 频繁路径挖掘算法为基础，结合多维序列模式挖掘思想，提出 两类r f i d 多维路径挖掘算法。一类是将多维数据与路径数据合并整体挖掘；另一类 是分别挖掘多维数据和路径数据。这两类算法适用于不同的数据集，可以有效提高 r f i d 多维路径挖掘的性能。 3 ) 提出了一种分布环境下的r f i d 频繁路径挖掘算法。因为供应链是分布的，所 以r f d 系统也是分布的。若将所有的数据集中到单个站点再用单机环境下的算法挖 2 扬州大学硕士学位论文 掘，将会造成大量数据传输和站点资源浪费。本文利用各个站点挖掘频繁路径，再将 结果存储在路径语法树中，在站点之间传输路径语法树来合并全局频繁路径。这样， 不仅可以减少网络数据传输量，也可以充分利用所有站点的计算能力，提高全局的挖 掘速度。 4 ) r f i d 系统不断收集移动物品的数据，需要先对数据库更新后，再挖掘用户需 要的准确信息。为了解决这一问题，本文提出了更新挖掘算法。由于不断加入数据， 会造成存储空间消耗过大，本文研究利用路径编码的方法，来压缩路径数据。 关键词：射频识别，数据仓库，数据挖掘，频繁路径，多维路径，分布频繁路径， 数据更新，数据压缩 陈竹西：面向r f i d 海量数据的若干数据挖掘技术研究 3 a b s t r a c t r e c e n t l y , t h er a d i of r e q u e n c yi d e n t i f i c a t i o nt e c h n o l o g yi sd e v e l o p i n gf a s t ，t h ep r i c e s o fr e a d e r sa n dt a g sa r ed e c r e a s i n gg r e a t l y , a n dt h ea c c u r a c yo fr e a d i n gi si n c r e a s i n g o b v i o u s l y w i t ht h ea d v e n to fr f i dt e c h n o l o g y , m a n u f a c t u r e s ，d i s t r i b u t o r s ，a n dr e t a i l e r s w i l lb ea b l et ot r a c kt h em o v e m e n to fi n d i v i d u a lo b j e c tt h r o u g h o u tt h es u p p l yc h a i n l a r g e r e t a i l e r sl i k ew a l - m a r t ，t a r g e la n da l b e r t s o n sh a v ea l r e a d yb e g u ni m p l e m e n t i n gr f i d s y s t e m si nt h e i rw a r e h o u s e sa n dd i s t r i b u t i o nc e n t e r s ，a n dt h e ya r er e q u i t i n gt h e i rs u p p l i e r s t oa t t a c hr f i dt a g st op r o d u c t sa tt h ep a l l e ta n dc a s el e v e l s w i t ht h ep r i c el e v e lg o i n gd o w n , p e o p l ec a ne x p e c tt a g st ob ep l a c e da tt h ei n d i v i d u a li t e ml e v e lf o rm a n yp r o d u c t s t h em a i n c h a l l e n g et h e nb e c o m e sh o wc a l lc o m p a n i e sh a n d l ea n di n t e r p r e tt h ee n o r l t l o u sv o l u m eo f d a t at h a ta l lr f i da p p l i c a t i o nw i l lg e n e r a t e t h em a s sd a t ah a v eb e e ns t o r e di nt h ed a t a b a s e o rd a t aw a r e h o u s e i nt h ef a c eo ft h i s ”d a t ae x p l o s i o n ”s i t u a t i o n ，h o wt oe x t r a c tv a l u a b l e i n f o r m a t i o nf r o mm a s s i v ed a t ah a sb e c o m e p a r t i c u l a r l yi m p o r t a n t w i t ht h ee m e r g e n c ea n d d e v e l o p m e n to fd a t am i n i n gt e c h n i q u e s ，t h i sp r o b l e mh a sb e e ns o l v e db yp e o p l e t h e p o t e n t i a la n du s e f u li n f o r m a t i o na n dk n o w l e d g ea r ee x t r a c t e df r o mt h em a s s i v e ，i n c o m p l e t e ， n o i s e ，f u z z ya n dr a n d o mp r a c t i c a ld a t ab y d a t am i n i n gt e c h n i q u e sa n dt h e i ra n a l y t i c a lt o o l s t h er f i dt e c h n o l o g yi su s e df o rt a c k i n gt h em o v i n gi t e m si ns u p p l yc h a i n ，s ot h em o s t i m p o r t a n td a t ai nr f i ds y s t e mi st h ed a t ao fm o v i n g ，c a l l e dp a t hd a t ao rt r a c kd a t a t h e m a i nt a s kf o rr f i dd a t am i n i n gi sm i n i n gf r e q u e n c yp a t h s i nt h i sp a p e r , w er e s e a r c ht h e p a t hd a t a , a n dp r o p o s es o m em e t h o d sf o rm i n i n gh i g hf r e q u e n c yp a t hi nd a t a b a s e b a s eo n t h e s ef r e q u e n c yp a t h s ，t h eu s e r sc a l lu n d e r s t a n dt h em o v i n gt r e n d s ，o p t i m i z et h es u p p l y c h a i i l ，a n df i n do u ta b n o r m a lm o v i n g t h em a i nr e s e a r c hc o n t e n ti n c l u d e s ：f r e q u e n c yp a t h s m i n i n g ，f r e q u e n c ym u l t i - d i m e n s i o n a lp a t h sm i n i n g ，a n dd i s t r i b u t e df r e q u e n c yp a t h sm i n i n g t h em a i nc o n t r i b u t i o n sa n di n n o v a t i o n so ft h i sd i s s e r t a t i o na r e 嬲f o l l o w s ： 1 ) t h em e t h o d sf o rm i n i n gf r e q u e n c yp a t t e r n sa n ds e q u e n t i a lp a t t e r n sc a n t m i n e f r e q u e n c yp a t h s 谢ml l i g he f f i c i e n c y i nt h i sp a p e r , w ed i v i d et h ep a t hd a t ai n t o s e v e r a l s e q u e n c e sa n db a s e do ne x i s t i n gf r e q u e n c yp a t t e r n sa n ds e q u e n t i a lp a t t e r n sm i n i n gm e t h o d s ， w ep r o p o s eh i 曲p e r f o r m a n c em e t h o d sm i n i n gf r e q u e n c yp a t h s 2 ) b a s e o n f r e q u e n c yp a t h sm i n i n g m e t h o d s p r o p o s e d i nt h i s p a p e r a n d 4 扬州大学硕士学位论文 m u l t i d i m e n s i o n a ls e q u e n t i a lp a t t e r n sm i n i n gm e t h o d s ，w ep r o p o s et w os t r a t e g i e s ，o n ei s e m b e dm u l t i d i m e n s i o n a li n f o r m a t i o ni n t op a t ht h e nm i n et h e m 嬲aw h o l e ；t h eo t h e ri s c o m b i n ei c e b e r gc u b i n ga n df r e q u e n c yp a t h sm i n i n g t h e s et w os t r a t e g i e sc a nb eu s e di n d i f f e r e n ts i t u a t i o n s 3 ) w ep r o p o s e dd i s t r i b u t e df r e q u e n c yp a t h sm i n i n gm e t h o d t h es u p p l yc h a i ni s d i s t r i b u t e di nd i f f e r e n tp l a c e s ，s ot h er f i ds y s t e mi sa l s od i s t r i b u t e d i ft h es y s t e mg a t h e r s d a t ai n t oo n es e r v ea n dm i n e s ，t h ev o l u m eo fd a t at r a n s m i tt h r o u g hn e t w o r ki sm a s s i v ea n d t h ec a p a b i l i t i e so fo t h e rs e r v e sa r ew a s t e d i nt h i sp a p e r , w eu s ea l ls e r v e sm i n ef r e q u e n c y p a t h sa n ds t o r et h er e s u l ti nl e x i c o g r a p h i cp a t ht r e e ，a n dt r a n s m i tt h e s et r e e sa m o n g d i f f e r e n t s e r v e s b a s i n go nt h er e g u l a ra n ds i m p l es e q u e n c e so fm e r g e dt r e e s ，w ew i l lh a v eg l o b a l f r e q u e n c yp a t h s t h i sm e t h o dn o to n l yd e c r e a s e st h et r a n s m i tv o l u m eo fd a t a , b u ta l s ou s e s a l ls e r v ec a p a b i l i t i e s 4 ) t h er f i ds y s t e mk e e p so ng e n e r a t i n gd a t a , a n dg i v e st r u ed a t am i n i n gr e s u l t st o u s e r s ，t h es y s t e mm u s tu p d a t ei t sd a t am i n i n gr e s u l t s w ep r o p o s ea nu p d a t em e t h o dt os o l v e t h i st a s k t h ev o l u m eo fp a t h sd a t aa r em a s s i v e ，w eu s ep a t hc o d i n gt oc o m p r e s st h ed a t a k e yw o r d s ：r a d i of r e q u e n c yi d e n t i f i c a t i o n , d a t aw a r e h o u s e ，d a t am i n i n g ，f r e q u e n c y p a t h s ，m u l t i - d i m e n s i o n a lp a t h s ，d i s t r i b u t e df r e q u e n c yp a t h s ，d a t au p d a t e ， d a t ac o m p r e s s e d 陈竹西：面向r f i d 海量数据的若干数据挖掘技术研究 9 9 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研究成果。除文中 已经标明引用的内容外，本论文不包含其他个人或集体已经发表的研究成果。对本文的研究做出 贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。 学位论文作者签名：甬呱c f 吁面、 签字日期砂7 年歹月“日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或 机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。本人授权扬州大学可以将学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据 库，并通过网络向社会公众提供信息服务。 学位论文作者签名：_ 际b 面 导师签名； 学位论文作者签名：侮l f 百面 导师签名； 签字日期- 川年f 月旱 柳飙叫西彬日 陈竹西：面向r f i d 海量数据的若干数据挖掘技术研究 第一章引言 数据挖掘【l - 5 】就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取 隐含在其中的、人们事先不知道但又是潜在有用信息和知识的过程，是一种从大型数 据库或数据仓库中提取隐藏预测性信息的新技术。它能开采出潜在模式，找出最有价 值的信息，从而辅助决策。 r f i d m 4 0 技术引入供应链管理，可以跟踪物流网络中移动物品的运动轨迹。通过 挖掘物品路径数据，找出频繁路径信息，能够帮助用户进一步了解商品的移动趋势， 预测商品的移动，找出异常的移动商品，优化物流环节降低物流成本，为用户决策提 供有力支持。 本文主要结合r f i d 系统与供应链管理，提出一种较为通用的供应链移动物品数 据管理理论模型，为进一步研究如何更有效地在供应链管理中应用r f i d 技术提供理 论基础。在本章中，首先介绍数据仓库与数据挖掘技术发展，射频识别技术特点以及 发展；接着介绍本文的主要工作，包括如何为供应链中移动物品建立数据仓库，建立 适用于移动物品数据的挖掘算法，建立网络环境下基于海量路径数据的分布数据存储 和查询分析系统，数据的更新和数据的压缩等。最后列出了文章的组织结构。 1 1 研究背景 在信息技术主导的时代，随着数据库技术的不断发展和数据库管理系统的广泛应 用，人们积累的数据越来越多。数据的丰富带来了对强有力的数据分析工具的需求， 大量的数据被描述为“数据丰富，但信息贫乏 。快速增长的海量数据收集、存放在 大型和大量数据库中，没有强有力的工具，结果收集在大型数据库中的数据变成了“数 据坟墓 。于是数据挖掘技术应运而生，并得以蓬勃发展。数据挖掘工具进行数据分 析，可以发现重要的数据模式，对商务决策、知识库、科学和医学研究做出了巨大贡 献。数据和信息之间的鸿沟要求系统地开发数据挖掘工具，将数据坟墓转换成知识： “金块 。在信息时代来临、互联网高速发展的今天，随着科技的不断创新，各式各 样的数据库系统得到了研究与开发，如一些空间数据库、时态数据库、多媒体数据库 等等。尽管目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但由 于数据量庞大以及数据库系统中分析方法的严重缺乏，使得它无法发现数据中隐藏的 6 扬州大学硕士学位论文 相互联系，更无法根据当前的数据去预测未来的发展趋势。因此，迫切需要一种从大 量数据中提取出隐藏在其中的有用信息，正是为了这种满足，将机器学习应用于大型 数据库中的数据挖掘技术得到了长足的发展。数据挖掘( d a t am i n i n g ，简称d m ) ， 又称数据库中的知识发现( k n o w l e d g ed i s c o v e r yd a t a b a s e ，简称k d d ) 是指从大型数 据库或者数据仓库【l l , 1 2 k 9 提取隐含的、未知的、非平凡的及有潜在应用价值的信息或 者模式。例如，某零售业可能积累了大量的原始数据，运用数据挖掘技术可以从这些 看似无用的数据中发现规律，找到商机。零售业的利润和风险是共存的，为了保证利 润的最大化和风险的最小化，必须对有关顾客的数据进行科学的整理、分析和归纳。 采取相应的游魂措施来留住能给商家带来较大经济效益的顾客群，或者根据顾客的消 费模式预测何时为顾客提供何种服务或商品。通过挖掘商家的历史数据：商品、销售 时间、销售地点及商品摆放地点等，对这些数据进行分析，发现其数据模式及其特征， 然后可能发现某类顾客、消费群体的消费兴趣和习惯以及预测消费市场的变化趋势。 r f i d 是一种非接触式的自动识别技术( a u t o m a t i ci d e n t i f i c a t i o nt e c h n o l o g y ，简称 趾t ) ，这项技术利用射频电磁波在阅读器和贴有标签的移动物品之间传输数据，达到 识别和跟踪物品等目的。r f i d 最早发明于1 9 4 8 年，在飞机上安装r f i d 标签与阅读 器用来敌我识别。2 0 世纪5 0 年代，研究者开始进行r f i d 技术原理的探索，做了大量 的理论研究和实验。6 0 年代，出现了多个r f i d 原型系统，并首次使用在零售商店， 防止贵重物品的丢失，这是r f i d 第一次广泛的商业应用。到了7 0 年代。美国政府通 过洛斯阿拉莫斯( l o sa l a m o s ) 科学实验室，将r f i d 技术大规模转为民用，并大量 用于动物跟踪管理。9 0 年代，r f i d 应用扩展到电子收费、铁路应用和进场管制等领 域。2 0 0 0 年以后，随着技术的进步，r f i d 设备体积变小、成本降低、可靠性提高， r f i d 技术被用于仓库信息采集【1 3 。1 5 】，跟踪仓库中的物品移动【1 6 ，1 7 1 。进一步，有学者提 出了将r f i d 应用到供应链管理【1 8 - 2 0 】，对海量移动物品跟踪这一新应用。该应用的重 点在于，从海量移动物品的路径数据中，快速、准确地挖掘处物品的移动趋势【z 1 , 2 2 1 ， 找出异常的物品移动以及对重点物品的移动进行跟踪与预测。如此一来，通过挖掘移 动数据，用户可以掌握供应链中各类物品的移动趋势，预测物品的流动方式，提高物 流管理的效率 2 3 j 4 ，减少物流环节的时间和工作人员，降低物流成本。因此，如何快 速、准确挖掘路径数据，及时返回用户的查询请求是r f i d 数据管理中的重要工作。 1 2 课题引出 r f i d 技术与条形码技术都是用于识别跟踪目标物品，但是，r f i d 技术在通信距 陈竹西：面向r f i d 海量数据的若干数据挖掘技术研究 离、批量读取、数据信息修改、环境适用性、安全性和自动性等方面更具优势。r f i d 技术与互联网、通信等技术相结合，可实现全球范围内物品的编号、识别、编目、跟 踪和信息的共享，就可以创建一个物理连接的世界，即所谓的“物联网”。有观点认为， r f i d 是继p c 、互联网和无线通信之后的第四次信息技术革命。由于r f i d 具有重大 的科学意义与应用价值，已引起国际学术界与工业界的极大关注。 最基本的r f i d 系统由以下三部分组成：( 1 ) 标签( t a g ) 由耦合元件及芯片组成， 每个标签具有唯一的电子编码嘲( e l e c t r o n i cp r o d u c tc o d e , e p c ) ，附着在物品上识别 目标对象；( 2 ) 阅读器( r e a d e r ) 读取( 有时还可以写入) 标签信息的设备，分为手 持式和固定式；( 3 ) 天线( a n t e n n a ) 在标签和阅读器问传递射频信号。 娜呻- m h 呷- - p 村 1 0 h 。l a ，h m ，p i 憾z b m q “i m _ 拼 l ：q l b n w 妇j o r 州d ：e r 4 r 嘲_ _ 帆” _ p o 呲毗，h d n q _ ， l j h q - # - n 蝌十e d 口。一一： j m ”m f k i 州”p 一i 啦 一 图1 1r f i d 标签 “1 冬 ；_ 爹口 图12 各类r f l d 阅读器 霈 扬州大学硕士学位论文 r f i d 工作原理较为简单，标签进入阅读器磁场后，接收阅读器发出的射频信号； 标签可以返回或者发射自己的e p c ；解读器读取e p c 编码，传送到信息系统进行相关 的数据处理。r f i d 阅读器可以同时读出自身磁场范围内的多个标签的e p c 数据。 际面讷 就雠糟f 蹦描汰e ：c p a c k e d m i ；o t 2 ：p j i l o t b a 曲d 舯b t r u c k 3 p ae i h 岬l o a 曲d br e b d o m 4c a s a sc h “ 叫o l d a t m gj $ b r lo ： 7 1 季 - ；射i 哥荆i - j 高= ；c ：= 。 “= # m l 五巍量越j _ 1 _ i 篇 銎纠凼蛰崮 c 一同露习r 昭一 k 皇鲤副u 苣篁划 图13 应用于供应链管理的r f i d 系统示例 r f i d 数据与传统关系数据和其它数据流相比，具有以下特征： 1 ) 原始数据元组结构简单 r f 数据单元形如( e p c , l o c ，t i m e ) ，其结构简单，元维组成元素的语义明确。 其中，e p c 为物品或包装容器等的电子产品编码；l o c 为阅读器的地点；t i m e 为本 次记录读取的时间。 2 ) 时态性和空问性 r f i d 相关数据会随时间和空间而不断变化，例如动态采集所产生的观察数据中， 带有状态改变的信息，物品的地点及物品间包含关系也会随着时间而变化。同时，在 实际应用中阅读器和标签可被内置于个人数字助理、手机或其他移动物品中，贴有标 签的物品和阅读器都是运动的。 3 ) 数据不准确性 r f i d 阅读器存在错误多读或者错误祸读等问题，这要求在将这些数据传递给下一 个更高级别处理或业务应用之前，需要数据清理口。冽。 归下；沼o一 | | - - - - | | o 陈竹西：面向r f i d 海量数据的若干数据挖掘技术研究 9 4 ) 连续流产生巨量数据【2 9 】 若一个贴有r f i d 标签的物品在同一个地点停留，则阅读器会在每一个时间间隔 周期记录读数，并向数据库插入一个数据元组。一个中等规模的r f i d 应用每天将产 生1 0 亿字节数量级的r f i d 数据。 5 ) 粒度 r f i d 数据集的粒度层级可包括时间、空间地点、其他物品描述等，这些需要基于 实施r f i d 系统的具体应用业务来确定。 6 ) 并发与分布【3 叼1 】 r f i d 实际应用场景中将部署多个r f i d 阅读器，并且每个r f i d 阅读器对应一个 r f i d 数据流。对特定物品的跟踪和分析，需要整合多个物理上分布的数据流。 因此，针对r f i d 上述特征来有效管理和应用r f i d 数据，是r f i d 数据管理研究 的共同目标。现有的r f i d 数据管理方面的研究，主要是对应于特定的问题，提出特 定的解决方案，例如，将r f i d 技术用于汽车的装配管理、水产品运输管理等，缺少 针对r f i d 数据管理本身的理论研究。很多问题还没有得到解决，需要大量的研究工 作。 文献【3 2 】提出了流立方体( f l o w c u b e ) 和流图( f l o w g r a p h ) 这两个重要的概念， 为r f i d 数据管理建立了重要的流立方体模型。通过该模型，将数据立方体( c u b e ) 技术【3 3 】引入到r f d 数据管理中来，解决了r f i d 数据中的粒度和多维度挖掘的问题。 以此为基础，可以将数据仓库( d a t aw a r e h o u s e ，d w ) 技术【列和联机分析处理( o n l i n e a n a l y t i c a lp r o c e s s i n g ，o l a p ) 技术【3 5 】引入r f i d 数据管理中来，利用d w 技术和o l a p 技术中提出的多种有用的工具，解决r f i d 数据管理所面对的问题。 r f i d 数据与传统的关系数据最大的区别在于r f i d 数据具有路径数据，而路径数 据是无法利用传统数据库技术来处理的。这就要求我们建立专门的方法，对路径数据 进行处理，在路径数据中挖掘有用的知识，充分发挥r f i d 技术对移动物品跟踪的优 势。 1 3 论文的主要工作 在论文中，首先介绍r f i d 数据的相关概念和特点，比较其与传统关系数据库的 区别，为r f i d 数据建立数据模型。在借鉴国内外研究成果的基础上，提出r f i d 路径 挖掘算法以及多维路径挖掘算法，处理集中式的r f i d 海量数据。进一步，根据实际 应用中r f i d 数据分布的特点，在吸收国内外分布数据挖掘技术的基础上，提出分布 1 0 扬州大学硕士学位论文 r f i d 数据挖掘算法。针对实际应用中r f i d 数据更新的要求，建立相应的r f i d 数据 更新算法。最后，探讨r f i d 数据的压缩问题。 本文的主要研究工作及成果如下： 1 ) r f i d 数据管理最关键的工作在于路径数据的管理。用户使用r f i d 技术管理 供应链中的移动物品是为了发现这些移动物品的移动趋势，找出异常移动，跟踪特定 物品的运动轨迹等，其中发现物品的移动趋势是最重要的目的。显然，r f i d 技术自身 特点( 将标签贴在单个移动物品上，随着物品在不同的阅读器范围内移动，产生路径 数据，物流网络中存在数以百万计的贴有标签的移动物品) ，能够产生极大的路径数据。 若不进行r f i d 数据挖掘而仅仅是查询，可以得到少数物品的移动趋势，也可以知道 某个地点有哪些物品。但是就像查询海量数据库一样，这样的查询是极费时间，同时 也是极耗资源的。虽然数据库中记录了移动物品的路径信息，但是仅仅依靠简单的查 询是无法得到得到整个供应链物品移动趋势。普通的数据库查询返回的结果是大量的 物品路径数据，用户无法直接使用这样的结果，需要进行路径数据的挖掘工作。如此， 首先在r f i d 数据库中挖掘频繁路径信息，用户查询时，直接返回挖掘好的频繁路径， 提高用户查询的响应速度和信息的准确性。在海量的移动路径中挖掘出物品的移动趋 势，就需要针对路径数据建立挖掘算法。而路径数据实际上是路径段的一种序列，可 以参考序列挖掘的方法建立路径挖掘算法。现有的序列模式挖掘算法 3 6 , 3 7 】分为三大类： 基于a p f i o f i 的改进算法，如g s p 3 羽、s p a d e 3 9 1 等；基于模式增长的算法，如f r e e s p a n l 4 0 1 、 p r e f i x s p a n 4 1 】等；基于位图表示的算法，如s p a m l 4 2 、l a p i n s p a m l 4 3 1 、l a p i n 4 4 1 、 h v s m 4 5 1 等，之后又提出了挖掘封闭序列模式的方法【4 6 4 8 1 。本文以这些方法为基础， 提出了路径挖掘算法，挖掘r f i d 数据集中的封闭频繁路径。 2 ) r f i d 的系统结构具有天然的分布性。因为供应链是在地理上分布的，那么部 署在供应链中各个地点的阅读器也是分布的。为了加快数据存储的速度，减少网络数 据的传输量，这些阅读器将数据就近传送到不同的数据服务器，所以整个r f i d 系统 的数据分布存储，需要利用分布式或并行思想加以解决 4 9 - 5 1 1 。本文借用现有的分布序 列模式挖掘算法【5 2 - 6 0 l 的思想，以单机环境下的路径挖掘算法为基础进行改进，提出分 布路径挖掘算法，解决r f i d 数据分布问题。 3 ) r f i d 数据不仅仅只有路径数据，同时也有非路径数据。在实际的应用中，不 同种类的物品移动趋势是不同的。食品类的移动更加快速，因为购买者更加在乎新鲜 度；电子设备需要安全移动，因为销售价格往往很高。这样一来，如果不考虑物品自 身的属性挖掘移动趋势，得到的结果不能十分准确地反应出实际的物品移动情况。所 陈竹西：面向r f i d 海量数据的若干数据挖掘技术研究 1 1 以，需要在挖掘路径信息的同时，考虑非路径维属性，挖掘多维路径数据。这些非路 径数据管理可以利用i c e b e r gc u b e 6 l 】、c o n d e n s e dc u b e 6 2 】、d w a r f t 6 3 】等c u b e 压缩技术 或者进一步借助于并行处理技术 6 4 1 来解决这一问题。同时，现有的多维序列模式挖掘 6 5 6 8 的思想也可以加以应用。本文在这些方法的基础上，提出挖掘多维路径的算法， 将路径数据和非路径数据一起处理，充分发挥r f i d 技术跟踪移动物品的能力。 4 ) r f i d 数据具有“流数据 的部分特点，即不断有新的数据加入。这就要求在 管理r f i d 数据时，需要不断进行数据的更新，在新的数据中挖掘出有用的信息。本 文借鉴序列模式更新算法，建立频繁路径更新算法 6 9 - 7 ，解决数据更新的问题。 5 ) r f i d 数据特点是数据量很大，在应用中每天都会产生大量的数据。而路径数 据因为其自身特点，会占用很大的存储空间。论文的最后会讨论如何利用路径编码来 压缩路径数据的大小，达到减少存储空间的目的。 1 4 论文组织 念。 本文后续章节内容组织如下： 第二章主要介绍r f i d 数据特点、路径数据的组织以及论文将要涉及到的基本概 第三章介绍单机环境的封闭频繁路径挖掘算法m c p 和d i v i d e 。 第四章介绍多维路径挖掘算法。 第五章介绍分布式r f i d 数据的管理方法。 第六章介绍r f i d 数据更新的处理方法和数据压缩的方法。 最后，第七章是论文的总结和研究工作的展望。 1 2 扬州大学硕士学位论文 第二章基本理论 本章首先介绍r f i d 数据的基本特点，比较r f i d 数据库与传统的关系数据库之间 的联系和区别。在此基础上，介绍频繁路径、封闭频繁路径的概念，以及挖掘封闭频 繁路径的大体思路；再介绍封闭多维频繁路径的概念和挖掘思路，以及分布环境下 r f i d 数据的挖掘的基本思想；最后介绍数据更新与数据压缩方面的基本思想。 2 1r fid 数据的特点 2 1 1 传统关系数据库的局限 传统的关系数据库【7 2 】( 以下简称r d b m s ) 是由具有 形式的 元组所组成的集合。其中，( 口l ，锄) 是甩个属性维的属性值，如产地、品种、品质等， a f e a f u 幸 ，a f 表示该属性的取值范围，“ 表示任意值，卢1 ，2 ，刀；( m l ，m k ) 表示k 个度量值，如数量、价格、重量等。r d b m s 有以下4 方面的弱点，使其不再适用于 r f i d 数据的管理： 1 ) 有限的数据类型 r d b m s 所能支持的数据类型限于r d b m s 所定义的有限几种基本数据类型，如 整数型、浮点数型、时间型等。而r f i d 应用中的路径数据无法由r d b m s 支持的数 据类型直接表示。 2 ) 缺少全局惟一、不依赖于属性值、类似于o i d 的标识符 o i d 是由系统生成的、不依赖于属性值、全系统惟一的对象标识符。o i d 可以用 作对象替身来访问，甚至可以区别两个属性值完全相同的对象。供应链中有许多物品 的属性值完全相同、路径数据不同，r d b m s 将无法区别这些物品。若使用e p c 作为 系统的o i d ，就能够避免上述问题。 3 ) 不支持用户可定义的或系统可扩充的函数或运算 一般的r d b m s 只支持常用的算术、逻辑、字符串、位串、时间等的运算和一些 比较运算以及少许聚集函数，超出此范围，只能交给应用程序去处理。r f i d 数据库中 最重要的运算是路径数据的聚集、分类、合并等运算，不能被r d b m s 支持。 4 ) 不能清晰表示和有效处理复杂对象 陈竹西：面向r f i d 海量数据的若干数据挖掘技术研究 1 3 r d b m s 的属性必须是原子的，而在实际应用中，常常要求属性是非原子的，即 要求某些属性是由某些类型构造的。供应链管理中，某些物品是由多个含有不同标签 的子物品组成，如笔记本电脑，本身具有标签，其内部的主板、c p u 、内存等都有不 同的标签，r d b m s 处理起来就会很复杂，需要多个表来记录。 2 1 2r f id 数据 r f i d 数据库是具有 形式的r f i d 数据元组组成 的集合。其中，e p c 表示电子产品编码( e l e c t r o n i cp r o d u c tc o d e ，e p c ) ，具有全球唯一 性，由相关国际组织提供；( 口l ，硝、l ，m k ) 含义与传统数据库相同，名称分别变 为非路径维属性值和非路径度量值；p a t h 表示路径信息。r f i d 数据库与传统的多维数 据库相比，多出了路径数据，且具有全局惟一标识符e p c ，r f i d 数据可以存放于对 象关系数据库1 7 3 j 中。 i 江i d 系统中的阅读器( r e a d e r ) 每隔一定的时间间隔扫描一次自身探测范围内所有 物品的标签。物品标签包含e p c 信息，能够自动应答阅读器的探测。阅读器将在每一 次扫描中产生一组形如( e p c ，l o c a t i o n ，t i m e ) 的元组，其中l o c a t i o n 表示阅读器的地点； t i m e 表示扫描发生的时间。物品停留于某个阅读器作用范围内会产生多个( e p c ， l o c a t i o n ，t i m e ) 的记录，物品离开后，系统自动将这些记录压缩为单个形如( e p c ，l o c a t i o n ， d u r a t i o n ) 的记录，其中d u r a t i o n 表示物品停留持续的时间。将具有相同e p c 的一系列 ( e p c ，l o c a t i o n ，d u r a t i o n ) 记录按照产生的先后次序组合起来，就能够得到路径( p a t h ) ， 路径的形式为( 1 l ，h ) ( 2 ，t 2 ) ( 厶，曲，其中元组( 厶，d ， 卢1 ，2 ，n 表示路径段( s t a g e ) ；l i 表示地点，必须是具体值；t i 表示停留时间，可以是具体值，也可以是“护，表示任意 值。路径中路径段的数量为路径的长度。 例2 1表2 1 就是一个r f i d 数据库的示例。包括2 个非路径属性维：产品种类 维、产地维。一个非路径度量值：销售价格。路径数据中各个地点的含义为：，工厂； d ，物流中心；w ，仓库；t ，卡车；s ，商店。停留时间单位为“天”。 1 4 扬州大学硕士学位论文 表2 1 r f id 示例数据库 e p c产品种类产地 销售价格移动路径 e p e l 跑鞋 山东 1 2 0 o o 饼1 ) ( 幺1 ) ( f ，1 ) o ，2 ) e p c 2 足球鞋山东 2 0 0 o o 所2 ) ( 面1 ) 似1 ) ( w ，2 ) o ，4 ) e p c 3 篮球鞋福建 2 2 0 o o 何2 ) 似1 ) ( 厶1 ) o ，4 ) e p c 4 篮球鞋 福建 2 2 0 0 0 职3 ) 2 ) ( 1 ) o ，2 ) 应用r f i d 技术管理供应链时，一般都会产生海量的移动物品数据。海量数据处 理需要通过商业智能( b u s i n e s si n t e l l i g e n c e ，b i ) 技术的引入来解决。商业智能的技术体 系主要由数据仓库( d a t aw a r e ) 、联机分析处理( o l a p ) 和数据挖掘( d a t am i n i n g ) _ - - = 部分 组成，从而实现对海量数据的整合、加工、分析和展现。 2 1 3 数据仓库与o l a p 数据仓库之父w h i n 1 1 0 n 在( ( b u i l d i n gt h ed a t aw a r e h o