（计算机软件与理论专业论文）rfid复杂应用中数据预处理技术的研究.pdf

at h e s i si nc o m p u t e rs o f t w a r ea n dt h e o r y s t u d y o nd a t ap r e p r o c e s s i n gt e c h n i q u e si n r f i d c o m p l e xa p p l i c a t i o n s b yl ix i a o j i n g s u p e r v i s o r ：p r o f e s s o ry ug e n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 l k 独创性l 声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 音 思0 学位论文作者签名：套酋知新 日期： 渺8 千b 日i o 日 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： ， 半年日一年口一年半口两年口 学位论文作者签名：吞如荟辱 签字日期：h “6 i o 纠以， ” 导师签名：于戈 签字日期：2 0 03 6 fo 。i ， f ， 一j l k _ i ， 东北大学硕士学位论文摘要 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 应用中“脏”数据的主要类型漏读数据，在数据抽象的 基础上，提出三种填补算法，即贪婪算法，最小船相似算法和全相似算法。它们对已经 发生的事件进行统计学习，并结合逻辑区域本身的漏读情况建立起动态概率事件模型， 在此基础上，根据不同的搜索策略查找可能发生漏读事件的最相似事件，据此对漏读数 据进行填补，这三种算法大大提高数据的准确率，消除漏读数据对查询质量的影响。理 论分析和大量实验证明该数据填补算法的有效性和高效性。 最后，本文增加对时间因素的考虑，对上面提出的填补算法进行改进。它主要对概 率事件模型进行扩展，引入时间模型，由此提出两种清洗算法的改进策略，即p 改进 算法和+ 改进算法。改进算法是通过直方图分布对时间进行估计，而+ 改进算法 是通过欧氏距离对时间进行估计，在不同的条件下，两种算法有各自的优势。实验证明 改进策略在填补数据准确率方面有一定的优越性。 关键词：r f i d 应用；数据预处理技术；数据填补策略：概率事件模型：数据漏读 p 矿， 7 ， l ， s t u d yo nd a t ap r e p r o c e s s i n gt e c h n i q u e si nr f i dc o m p l e x a p p l i c a t i o n s a b s t r a c t a san e wt e c h n o l o g yi n t e g r a t e dw i t h s i g n a lp r o c e s s i n g ，w i r e l e s s c o m m u n i c a t i o n ， e m b e d d e dc a l c u l a t i o na n dd a t am a n a g e m e n t ，r f i dt e c h n o l o g yi sb e i n gw i d e l yu s e di nm o r e a n dm o r ea r e a s ，s u c ha ss u p p l yc h a i nm a n a g e m e n t ，o b je c tt r a c k i n g ，q u i c kd i s b u r s e m e n ta n ds o o n h o w e v e r ，r f i dt e c h n o l o g ya d o p t sw i r e l e s sr a d i of r e q u e n c ys i g n a lt oc o m m u n i c a t e ，w h i c h i se a s i l yi n t e f f e r e dw i t he n v i r o n m e n t ，s ot h e r ea r em a n ym i s s e dr e a d i n g s ，e r r o n e o u sr e a d i n g s ， d u p l i c a t e sa n dd a t ao u to fo r d e ri nt i m ew h e nc o l l e c t i n gd a t ai nr f i da p p l i c a t i o n s ，w h i c h i n f l u e n c e st h ea c c u r a c yo fq u e r yr e s u l t sf o re v e n td e t e c t i o nb a d l ya n dl i m i t st h ed e v e l o p m e n t o fr f i da p p l i c a t i o n s t h e r e f o r e ，t h ep r e p r o c e s s i n go v e rr f i dd a t ai st h ep r e r e q u i s i t eo f a s s u r i n gh i g hq u a l i t yo fq u e r yr e s u l t s f o rt h eg o a lo fs o l v i n gt h ei s s u e sp r o p o s e da b o v e ，t h i sp a p e rf o c u s e st h ep r e p r o c e s s i n g s t r a t e g yo v e r “d i r t y ”d a t ag e n e r a t e di nr f i da p p l i c a t i o n s f i r s t l y , o nt h eb a s i so ft r i p i et u p l eo v e rr f i dd a t a ，t h ep a p e rp r o p o s e sad a t aa b s t r a c t i o n a l g o r i t h mw h i c ht r a n s f o r m sr f i dd a t af r o md a t al e v e lt ol o g i ca r e al e v e l t h i sa l g o r i t h m i s u s e dt oc o m p r e s sd a t aw h e r el o t so fr e d u n d a n td a t aa r ed e l e t e da n ds o m em i s s e dr e a d i n g sa r e c o n s i d e r e d a f t e rt h a t ，at u p l em a yb ec o n s i d e r e da sas i m p l ee v e n t e x p e r i m e n t a lr e s u l t s s h o wt h a tt h r o u g ha b s t r a c t i o nt h ea m o u n to fd a t ai se x t r e m e l yc u td o w n i nt h i sw a y , s y s t e m r e s o u r c ei sg r e a t l ys a v e df o rf u r t h e rd a t ac l e a n i n g s e c o n d l y , i no r d e rt os o l v et h em i s s e dr e a d i n gp r o b l e m - - t h em a i nt y p eo f d i r t y d a t ai n r f i da p p l i c a t i o n s ，t h i st h e s i sp r o p o s e st h r e ei n t e r p o l a t i n ga l g o r i t h m sb a s e d o nd a t a a b s t r a c t i o n ，n a m e l yr a p a c i t ya l g o r i t h m ，m i n k - s i m i l a ra l g o r i t h ma n da l l k - s i m i l a ra l g o r i t h m a b o v ea l l ，ad y n a m i cp r o b a b i l i s t i ce v e n tm o d e li se s t a b l i s h e db ys t a t i s t i c a l l ys t u d y i n ga r r i v i n g e v e n t sa n dc o m p u t i n gt h em i s s i n gr a t eo fe a c hl o g i ca r e a t h e n ，o nt h eb a s i so ft h i sm o d e l ， m i s s e de v e n t sa r ei n t e r p o l a t e db ys e a r c h i n gt h e i rm o s ts i m i l a re v e n t su s i n gd i f f e r e n ts e a r c h i n g s t r a t e g i e s t h e s et h r e ea l g o r i t h m si n c r e a s ed a t aa c c u r a c yl a r g e l y , a n de l i m i n a t et h ei n f l u e n c e o fe r r o n e o u sd a t at oq u e r yq u a l i t y t h e o r e t i c a la n a l y s i sa n da b u n d a n te x p e r i m e n t sp r o v et h e e f f e c t i v e n e s sa n de f f i c i e n c yo fp r o p o s e dd a t ai n t e r p o l a t i n ga l g o r i t h m s l a s t l y , t h i st h e s i si m p r o v e st h ea b o v ei n t e r p o l a t i n ga l g o r i t h m sb ya d d i n gt h e f a c t o ro f t i m e i tm a i n l yd e v e l o p sp r o b a b i l i s t i ce v e n tm o d e lb yi n t r o d u c i n gt e m p o r a lm o d e l ，a n dt h u s t w oi m p r o v e ds t r a t e g i e so fo r i g i n a l i n t e r p o l a t i n ga l g o r i t h m sa r ep r o p o s e d ，n a m e l y i m p r o v e da l g o r i t h ma n d9 + i m p r o v e da l g o r i t h m 。p 噜i m p r o v e da l g o r i t h ma d o p t sh i s t o g r a m i i i i ， 东北大学硕士学位论文 a b s t r a c t g r a p hd i s t r i b u t i o nt oe s t i m a t et i m e ，a n dp + i m p r o v e da l g o r i t h ma d o p t se u c l i d e a nd i s t a n c e t oe s t i m a t et i m e i nd i f f e r e n tc a s e s ，t h e s et w oa l g o r i t h m sb e h a v ew e l ls e p a r a t e l y e x p e r i m e n t s s h o wt h a t i m p r o v e dd a t ai n t e r p o l a t i n ga l g o r i t h m sh a v et h es u p e r i o r i t y o na c c u r a c yo f p r o c e s s i n gr e s u l t s k e yw o r d s ：r f i da p p l i c a t i o n ；d a t ap r e p r o c e s s i n gt e c h n i q u e ；d a t ai n t e r p o l a t i n gs t r a t e g y ； p r o b a b i l i s t i ce v e n tm o d e l ；m i s s e dr e a d i n g i v ， f 1 p 东北大学硕士学位论文 目录 目录 独创性声明i 摘要- i i a b s t r a c t i i i 第1 章引言1 1 1 研究背景1 1 2r f i d 数据管理系统2 1 2 1r f i d 数据的特点2 1 2 2r f i d 数据管理系统3 1 3 问题提出4 1 4 本文贡献6 1 5 组织结构6 第2 章相关工作9 2 1 “脏 数据类型9 2 2 一般性数据清洗策略1o 2 2 1 基于时空关联的数据清洗策略1 0 2 2 2 基于阅读器调度的数据清洗策略1 3 2 2 3 基于机器学 - - - j 的数据清洗策略1 4 2 3 与应用相关的数据清洗策略15 ，2 3 1 概率性数据清洗策略1 6 2 3 2 基于查询语义的数据清洗策略1 6 2 4 本章小结1 7 第3 章数据抽象1 9 3 1 数据抽象机制1 9 3 2 数据抽象算法2 0 3 3 算法复杂度分析2 1 v 东北大学硕士学位论文 目 录 3 4 实验评估2 2 3 4 1 实验设置：j 。j 2 2 3 4 2 结果分析2 3 3 5 小结2 6 第4 章基于动态概率事件模型的数据填补算法2 7 4 1 问题描述2 7 4 1 1 概率事件模型2 7 4 1 2 相似事件模型2 9 4 1 3 评价模型3 0 4 2 理论依据3 0 4 2 1 引理与假设3 0 4 2 2 最相似事件定理31 4 2 3 少漏读事件定理3 2 4 3 基于动态概率事件模型的数据填补算法3 2 4 3 1 数据填补机制3 3 4 3 2 贪婪算法3 3 4 3 3 相似度算法3 4 4 4 算法分析3 6 4 4 1 算法准确率分析3 6 4 4 2 算法实时性分析3 6 4 4 3 算法复杂度分析3 7 4 5 实验评估3 8 4 5 1 实验设置3 8 4 5 2 结果分析3 8 4 6 本章小结4 4 第5 章基于扩展概率事件模型的数据填补算法4 5 5 1 问题描述4 5 5 1 1 扩展概率事件模型4 5 5 1 2 扩展相似事件模型4 7 ， q 东北大学硕士学位论文 目录 5 2 理论依据4 7 5 2 1 假设条件4 7 5 2 2 扩展最相似事件定理4 7 5 3 基于扩展概率事件模型的填补算法4 8 5 3 1 扩展数据填补机制4 8 5 3 2 i 改进算法4 9 5 3 3 + 改进算法5 0 5 4 算法分析5 2 5 4 1 算法精确率分析5 2 5 4 2 算法复杂度分析5 3 5 5 实验评估5 3 5 5 1 实验设置j 5 3 5 5 2 结果分析5 4 5 6 本章小结5 7 第6 章结论5 9 6 1 总结。5 9 6 2 未来工作6 0 参考文献6 1 致谢6 5 攻读硕士学位期间的论文项目情况6 7 v i i l 0 东北大学硕士学位论文第1 章引 言 第1 章引言 本章是全文开篇，阐明本文的研究目的并且概述全文内容。首先介绍r f i d 技术的 研究背景，然后对r f i d 数据及其相应的管理系统进行详细说明，接着提出本文要解决 的问题以及相应的解决策略，最后给出文章的组织结构。 1 1 研究背景 - 无线射频识别( 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 ，简称r f i d ) 技术是一种非接触式的 自动识别和数据获取技术【1 1 1 2 。r f i d 技术的基本工作原理是：阅读器广播式的向其周围 发送能量，感应到能量的标签立即向阅读器返回自身携带的数据，阅读器对收到的数据 进行解码，然后将数据传给主机进行处理，如图1 1 所示。 标签对象阅读器服务器应用程序 图1 1i 讧i d 应用系统体系结构 f i g 1 1r f i da p p l i c a t i o ns y s t e ma r c h i t e c t u r e r f i d 技术最早应用在雷达监测系统中，对物体进行跟踪探测【3 】【4 1 ，但随着无线通讯 技术和数据管理技术 5 - 7 1 的发展，r f i d 技术的应用8 】【9 】范围越来越广，下面介绍几个典 型的r f i d 应用例子。 供应链管理 在供给链管理应用中【l o 】【l l 】，从存储货品仓库到货品销售地，对所有物品一直进行跟 踪管理，避免货品丢失，遗漏等造成的损失。在所有货品，集装箱，货车上都贴有标签， 并在主要地点安放读卡器，周期性的进行数据读取并将数据传送到查询层进行处理，实 时返回结果，以做到对每件物品能够进行有效的管理。 医疗看护 在医疗看护应用中【1 2 】，探测系统通过使用传感器和r f i d 技术，监测和记录病人每 天的活动状况，当发现病人陷入困难时，实时探测病人此时所处的位置，并提供语音或 视频帮助。此应用对实时性和结果正确性要求很高。 1 舅舅 r、璺一皿伊 东北大学硕士学位论文第1 章引 言 超市商品管理 在超市商品管理系统中【l3 1 ，所有的商品都需要帖上标签，并且在超市的主要地点安 放读卡器，如入口和出口等，用以实时监测商品的销售情况并能跟踪商品在未出售前的 位置情况，如有异常事件发生，像商品被盗等，则会实时的进行报警。在此应用中，r f i d 能够高效的对商品进行管理，会大大减少超市在时间，人力等方面的开销。 不停车收费系统 射频自动识别不停车收费系统( e t c ) 是目前世界上最先进的路桥收费方式，主要实 现方案是通过安装在车辆挡风玻璃上的电子标签与在收费站e t c 车道上的微波天线之 间的专用短程通讯，利用计算机联网技术与银行进行后台结算处理，从而达到车辆通过 路桥收费站不需停车就能交纳费用的目的。这不仅能够缓解日益剧增的交通堵塞问题， 更大大节省了人们的时间。 温室花卉栽培自动管理 该系统主要对花卉在各个不同生产期进行自动管理，直至其长成被运送至仓库并做 好订购准备。盆栽被放在帖有标签的托盘上，传送带下面安放读写器，并在温室里安装 数码相机，周期性的对各植物进行拍照，并与其i d 号一起送到高层服务器，对照片特 性进行分析，比如大小，形状及颜色，判断植物是否健康，若此植物需要更多营养，系 统就会自动将其运送给施肥部进行施肥等等。 由上面的具体应用可以看出，r f i d 技术在现实生活中的运用不仅大大节省了人工 成本，而且还提高了工作效率，给人们的生活带来了极大的改善。由此可见，随着r f i d 技术的日趋成熟，它对人们生活的影响越来越大，r f i d 技术会有着无限广阔的应用前 景。目前，各大高校和研究机构已经开始了对r f i d 数据管理系统的研究与开发，虽然 取得了阶段性成果，但还有许多问题亟待解决。 本课题来源于关于面向r f i d 复杂应用的事件流处理技术的研究的国家自然科学基 金项目( 6 0 7 7 3 2 2 0 ) 。对于r f i d 技术的研究主要包括数据预处理，复合事件检测【l 4 。，规 则探测，数据存储，实时查询处理及q o s 调度等方面，需要研究新的模型，语言，操作 和算法，并设计和编写相关的系统来解决实际的基于r f i d 的应用问题。 1 2i u i d 数据管理系统 r f i d 数据不同于传统数据库中静态存储的数据，也不同于无线传感器网络【l 孓 j 中 传感器节点采集的数据，r f i d 数据具有其本身的特点，这一小节将对r f i d 数据特点 进行分析，并介绍现有的几个r f i d 数据管理的原型系统。 1 2 1r f i d 数据的特点 由上一小节列举的几个r f i d 技术典型应用，可以看出r f i d 数据具有如下特点： 东北大学硕士学位论文第1 章引 言 ( 1 ) 时态性、动态性和关联性。r f i d 应用动态地产生关于标签对象状态变化的观察 数据，这些数据包含观察时刻、以及对应此时刻的对象位置和对象状态等数据。例如， 物品的入库、出库等状态。一个r f i d 数据不是独立存在的，而是相互关联的，由时态 性和动态性衍生出关联性。时态关联表达了事件之间的时序关系，空间关联表达了事件 发展的轨迹，时空关联共同表达了与对象有关的事件的变化过程。 ( 2 ) 语义丰富性。被观察的对象携带有背景上下文信息，这些信息是隐含的，且与 上层应用逻辑之间存在密切的关系。利用这些相关信息可进一步导出衍生信息。例如， 从产品的i d 可查出它的型号、价格、产地等，从阅读器的位置可得知物品的存放货架 位置等。r f i d 数据是一种低级的基础数据，必须上升为高级的业务逻辑数据，与现有 的应用相集成，才能真正地发挥作用。 ( 3 ) 不精确性和异构性。现有的r f i d 阅读器还存在误差问题，如重复读数、缺失读 数等。另一方面，一个阅读器可以识别出多种不同的对象，即r f i d 数据流中可能包含 有多种不同性质的观察值。例如，在一个安检入口，既可以识别进出的人员，也可以识 别进出的物品，它们是具有不同性质的对象，所对应的事件语义也不相同。 昏 ( 4 ) 流特性、批量性和海量性。r f i d 数据是以流的形式快速、自动地产生的，需要 ? 积累起来以支持跟踪和监控应用。并且，有时具有批量的特点，即多个对象会被集中地 观察，例如，当对一个集装箱登记时，同时会读到大批数据。大规模的r f i d 设备的部 署将产生空前的海量数据。目前，阅读器每秒可捕获1 2 0 个到4 0 0 个标签数据。对于一 个部署有1 0 0 个阅读器的中型仓储，每秒可产生1 2 4 万条数据，若每条数据占2 0 字节， 则每天产生1 6 - 6 0 g b 。因此，需要处理的数据量非常庞大。 聋 1 2 2r f i d 数据管理系统 从1 2 1 节介绍的i 讧i d 数据特点可知，r f i d 数据是一种特殊的数据流，借鉴于数 据库理论和现已开发的数据流管理系统【1 8 捌】，人们开始了r f i d 数据管理系统的研究与 开发。 在早期的r f i d 应用开发中，将r f i d 数据直接传送给应用程序，由应用程序解释 这些原始数据，处理成业务逻辑数据。这种方式导致r f i d 数据处理部分非常复杂，软 件的可重用性、可伸缩性和可适应性都非常低。当前的发展趋势是为r f i d 应用提供基 于中间件的平台，在r f i d 代表的物理世界与应用软件之间建立桥梁 2 2 】。目前，对r f i d 数据管理系统的研究主要分为两类，即以数据为中一心的系统和以事件为中心的系统，下 面进行概要介绍。 以数据为中心的r f i d 处理系统是最早采用的对r f i d 数据进行管理的方法，采用 传统的数据库技术，对r f i d 数据进行建模，并将数据保存在数据库管理系统中，在数 据基础上支持事件处理，代表性的系统有s i m e n sr f i dm i d d l e w o r e l 23 ，i b mw e b s p h e r e 3 东北大学硕士学位论文第1 章引 言 r f i dp r e m i s e ss e r v e r 【2 4 】，0 r a c l es e n s o re d g es e r v e r 2 5 1 ，m i c r o s o f tr f i dm i d d l e w a r e 2 6 】 等等。类似的系统还有美国力n j f i 大学伯克利分校开发的h i f i 系统【2 ，在数据流系统 t e l e g r a p h c q 之上增加了事件检测器，具有连续进行事件检测的功能。但是，这些系统 由于性能限制，只适合于进行历史数据的a d h o c 查询或在线监控低速的事件，不适合 于针对高速的、海量的事件进行连续查询。 以事件为中心的系统是一种新型的r f i d 处理技术，基于数据源而不是基于数据库 对事件进行建模，对事件直接进行处理，以获得高的效率，处理更复杂的事件。目前， 已经有一些原型系统被开发出来，例如美国加州大学伯克利分校开发的原型系统 s a s e 2 8 1 1 2 9 1 ，该系统提供扩展的事件语言、事件查询处理器和操作优化策略等，实现了 从r f i d 设备的数据采集和清洗、基本事件生成、复合事件处理、事件归档，以及对事 件的查询。美国c o m e l l 大学开发的c a y u g a 系统【3 0 】【3 l 】，该系统提出了扩展的查询语言， 并通过自定义的自动机模型和内部命名方法来高效的探测复合事件，并讨论了相关的系 统实现的技术细节。美国t e x a s 大学a r l i n g t o n 分校开发的e s t r e a m 系统【3 引，该系统在数 据流查询器的基础上，集成了连续事件查询器，利用规则检测数据流上的复合事件，考 虑了高效的增量维护算法。美国d a r t m o u t h 学院开发的p q s 系统【3 3 1 ，采用非确定性有限 自动机、隐型马尔科夫过程h m m 等方法对动态过程建模，以事件流为输入参数，通过 对模型求解，从而发现产生这些事件的过程，实现过程查询和检测。在国内，中科院计 算所率先开展了r f i d 事件检测方面的研究，研究和开发了基于r f i d 技术的物品跟踪 系统，提供对r f i d 事件的过滤、模式挖掘和事件聚合等多种操作1 3 引。 1 3 问题提出 r f i d 技术采集数据的一个特点就是数据量大，而信息量少。例如在超市管理系统 1 3 中，一个贴着标签的商品一直放在某个货架上，没有被人移动过，那么在一天之内， 探测到该标签的数据可达数万、甚至数十万个，而对于应用来说，有价值的可能就是该 商品被放在货架时和被拿走时阅读器读到的数据，而在这期间读到的数据虽然多，却对 应用没有实际意义，我们称这样的数据为冗余数据。如何将原始的大量冗余数据转化为 精简的有语义的数据是本文研究的一个问题。 众所周知，r f i d 技术采用无线射频信号进行数据通信，由于无线射频信号极易受 环境影响，而且相互间干扰很大，尤其当标签和阅读器数量增多时，信号干扰加强，导 致r f i d 数据的不可靠性很高，以至于大大影响了应用查询的准确性。 在一个基于r f i d 技术的超市管理系统中，通常会包括这样的查询，阅读器探测贴 有标签的商品时，当某类商品的数量小于设定阈值时，需要发出报警信号，提醒工作人 员对缺少的商品进行补充。如果将探测到的数据直接进行查询处理，则可能会出现商品 数量充足时，发出报警信号的错误现象，原因是当超市环境嘈杂时，由于信号干扰等因 4 东北大学硕士学位论文第1 章引 言 素，阅读器探测不到它阅读范围之内的标签。如果超市噪声很高，那么这种错误报警现 象可能会频频发生，这样不但没有减少人力开销，反而增加了超市的成本。还有一种查 询用于监测商品是否被盗的情况，如果某种商品没有先在结账1 ：3 被探测到，就直接在超 市出口被探测到，则认为该商品被盗，立刻发出报警信号，提醒保安对丢失商品进行追 回。在这个查询中，如果探测数据丢失情况严重，则会对超市造成很坏的影响。如果某 个商品在结账口被漏读掉，而在出口被读到，保安会对携带该商品的顾客进行盘查，这 样必然会造成顾客对超市的不满；而某个真正被盗的商品在出口处也没有被探测到的 话，会直接造成超市的经济损失。 由上面的查询应用可见，r f i d 数据的不可靠性主要是数据漏读现象，当该问题严 重时，查询结果的准确性急剧下降，这样会大大阻碍r f i d 技术的广泛推广，因此，对 r f i d 数据进行填补是保证查询质量的必要条件，是r f i d 数据管理系统中不可缺少的 环节。目前已有许多数据填补算法针对上面提出的问题进行了研究，但是这些数据填补 算法没有与应用结合在一起考虑，有可能填补的数据是冗余数据，没有任何实用价值， 这样反而大大浪费了系统资源。而本文则提出了以逻辑区域为填补粒度的填补算法，不 会对冗余数据进行填补。 甲叩! 一j ，7 图1 2 公园逻辑区域示意图 f i g 1 2l o g i ca r e a sg r a p ho fp a r k 具体问题可以描述如下，图1 2 为某个公园的逻辑区域示意图，三l ，2 ，三3 ，4 表 示逻辑区域，每个逻辑区域都布置一个或多个阅读器进行标签探测。如果某个带有标签 的游客连续在逻辑区域l 和4 被探测到，那么说明这位游客在经过三2 或3 时出现了数 据漏读现象，实际游玩路线是l 三2 4 或l i l 止4 ；如果该游客连续在三i 和2 被探测到， 那么该游客实际游玩路径可能是i l z ，l 扛4 ，或者l i l r l , , l 3 ，可能没有发生漏读现象， 也可能在一个或多个逻辑区域发生漏读现象，如何区分这些情况并对数据进行填补将是 本文研究的主要问题。 东北大学硕士学位论文第1 章引 言 1 4 本文贡献 针对上面提出的问题，本文进行深入的研究，并提出相应的解决办法。本文的主要 贡献如下： ( 1 ) 在对r f i d 数据进行三元组模型的基础上，提出一个数据抽象算法，即将r f i d 数据从数据层抽象到逻辑区域层。它主要是对数据进行重新建模，去除大量冗余数据， 并且对数据漏读有一定的容忍度。建模后，数据可被看成简单事件，为下面提出的数据 填补算法做好准备。理论分析与实验结果均表明，r f i d 数据经过抽象后，数据量极度 减少，大大节省系统的开销，为数据下一步清洗提供条件。 ( 2 ) 针对r f i d 应用中数据不可靠性的主要类型漏读数据，在数据抽象的基础 上，提出三种数据填补算法，即贪婪算法，最小缸相似算法和全相似算法。它们对已经 发生的事件进行统计学习，并结合逻辑区域本身的漏读情况建立动态概率事件模型，在 此基础上，根据不同的搜索策略查找可能发生的漏读事件的最相似事件，据此对漏读数 据进行填补，这三种算法大大提高原始数据的准确率，消除漏读数据对查询质量的影响。 大量实验证明该数据清洗算法的有效性和高效性。 ( 3 ) 在贡献2 的基础上，增加时间因素的考虑，改进上面提出的填补算法。它主要 是对动态概率事件模型进行扩展，通过直方图概要和欧氏距离两种方法对时间进行估 计，重新对最相似事件进行定义，由此提出两种改进的填补算法，即事改进算法和+ 改进算法，在不同的应用条件下，两种改进算法各有各的优势。实验证明改进策略在填 补数据准确率方面有一定的优越性。 1 5 组织结构 全文共分为六章，组织结构如下： 第一章是引言部分，首先介绍本文内容的研究背景，课题来源，然后概述r f i d 数 据特点以及r f i d 数据管理系统的研究现状，最后详细的描述本文要解决的问题并提出 相应的解决策略。 第二章是相关工作，首先归纳总结r f i d 应用中“脏”数据的主要类型，然后针对 “脏”数据类型，系统的介绍一些现有的经典r f i d 数据清洗算法，并分析算法中存在 的一些不足。 第三章是数据抽象，主要提出一个数据抽象算法的改进算法，对数据漏读现象有一 定的容忍度，在此基础上给出实验评测比较改进算法与原算法的性能情况。 第四章提出三种基于概率事件模型的数据填补算法，即贪婪算法，最小缸相似算法 和全相似算法。首先给出与算法相关的三个模型定义，然后论述该填补算法的理论依据， 接着详细描述这三个填补算法，给出具体的算法理论分析过程，最后进行实验评估。 东北大学硕士学位论文第1 章引 言 第五章是第四章的扩展，在第四章的基础上，增加对时间因素的考虑，提出两种改 进的数据填补算法，即改进算法和+ 改进算法。首先给出扩展概率事件模型和扩展 最相似事件的定义，然后在不同的应用条件下，提出两种相应的改进策略，并给出算法 的理论分析过程，最后通过实验对改进算法的性能进行验证。 第六章是全文总结和对未来工作的展望。 东北大学硕士学位论文第1 章引 言 东北大学硕士学位论文 第2 章相关工作 第2 章相关工作 目前，各大高校和科研机构已经开始了对r f i d 数据管理系统的研究与开发，针对 r f i d 的不精确性特点，尤其对如何清洗r f i d 数据进行了深入的研究。 最初，人们是对数据仓库中不准确的数据进行清洗技术的研究，主要是如何规范从 网页或系统中获得的数据【3 6 1 ，接着开始对通信设备采集的数据进行清洗操作，如在无 线传感器网络中，会产生许多噪声数据，需要对这种数据进行清洗，由此提出了许多针 对传感器网络中脏数据的数据清洗策略【3 7 】【3 8 】。而r f i d 数据虽也是用通信设备接收数据， 但脏数据类型与传感器网络中的脏数据类型有着本质区别，所以对应的清洗策略也大不 相同。 本章首先对r f i d 应用中的“脏 数据类型进行概括，然后从不同层面提出清洗这 些脏数据的算法，系统地介绍r f i d 应用中已提出的几种经典的数据清洗算法【3 9 4 9 1 。 2 1 “脏”数据类型 r f i d 应用中，“脏 数据类型大体上分为两种，即物理脏数据和逻辑脏数据。 物理脏数据主要由无线射频信号之间的干扰，传播信道质量以及标签读取结构等诸 多因素造成，使得数据读取的可信度很低，物理脏数据主要包括下面几种情况： 数据冗余：当一个阅读器在短时间内对一个标签反复进行读数时，会产生大量冗余 数据。这主要与阅读器的读速率，标签个数和状态有关。数据冗余会浪费系统资源，影 响查询速度，应在数据预处理阶段给予简化。 数据漏读( f a l s en e g a t i v e ) ：当一个标签在一个阅读器阅读范围之内时，该阅读器没 有读到该标签。这种情况可能发生在同一时间段内，某个阅读器同时读多个标签时，标 签被遗漏。经调查表明，通常情况下，阅读器只能读到在它感应范围内6 0 - - 7 0 的标 签数据【9 1 【5 0 1 ，即至少有3 0 的标签数据读取时被遗漏。由此可见，在r f i d 应用中，数 据漏读现象比较严重，应给予重点解决。 数据多读( f a l s ep o s i t i v e ) ：当一个标签不在一个阅读器阅读范围之内时，该阅读器仍 然读到该标签。这种情况原因比较复杂，随机性很大，可能导致同一个标签被阅读范围 不重合的多个阅读器同时读到，如超市整理乱放