（计算机应用技术专业论文）基于孤立点检测的rfid数据流清洗技术研究.pdf

基于孤立点检测的r f l d 数据流清洗技术研究 摘要 近年来，r f i d 技术已广泛应用于生产、物流、交通、运输、医疗、防伪、图书 管理、设备跟踪和资产管理等领域。但由于外部环境干扰和射频信号的不稳定性， i 疆i d 阅读器所产生的数据有时是不可靠且有噪声的，因此需对i 强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 数据流清洗。 针对集中式单数据流，结合孤立点检测技术设计了一种基于核密度的数据清洗 机制。该机制将交错读视为孤立点，采用核密度估计方法计算标签对象的空间密度 分布，并据此判断标记对象的真实位置，即位于具有最高密度值的阅读器探测范围。 该机制的优点是不需事先了解任何先验知识，是完全数据驱动技术。为减少核密度 计算量，该机制根据阅读器在前后两个滑动窗口中实际观测到标签的观测次数，运 用二次规划模型和“动态”马尔科夫链方法计算标记对象位置发生移动的概率。在前 后两个滑动窗口中，若标签对象被前一窗口所在阅读器观察到的观测次数未发生显 著变化时，则认为对象位置未发生变，可省略后一窗口的核密度计算。为了进一步 优化数据流处理速度，还设计了滑动窗口自适应调整策略，它根据对象位置发生变 化频率的高低，动态调整滑动窗口的大小，在对象位置变化不频繁情况下，可跳过 一个窗口计算概率或核密度，进一步减少计算量。 针对分布式多数据流，设计了一个基于距离的数据清洗机制。该机制由局部流 孤立点检测算法l s o d 和全局流孤立点检测算法g s o d 两部分组成。j _ , s o d 算法充 分利用安全内点的特性，以增量处理的方式在各个局部节点上检测孤立点，即交错 读数据。另外，由于全局孤立点集合是所有局部孤立点集合的子集，因此g s o d 算 法采用抽样方法进行全局孤立点的近似估计，以减少中心节点的通信量及计算负荷。 总之，该文对r f i d 数据流清洗技术进行了有益的探讨。通过理论分析和实验验 证，表明本文所设计的策略和算法能够有效地解决交错读问题，并具有运行时间短、 占用内存小、准确率高等特点。 关键词：r f i d ：数据流；数据流清洗；孤立点检测；核密度 a b s t r a c t r e c e n t l y , r f i dt e c b a l o l o g i e sh a v eb e e nw i d e l yu s e d i nm a n yf i e l d s ，s u c ha sp r o d u c t i o n ， l o g i s t i c s t r a f f i ca n dt r a n s p o r t a t i o n ，m e d i c a lc a r e ，a n t i c o u n t e r f e i t i n g ，l i b r a r ym a n a g e m e n t ， e q u i p m e n tt r a c k i n ga n da s s e tm a n a g e m e n t h o w e v e r , d u et ot h ei n t e r f e r e n c eo f v a r i o u s e n v i r o m e n t a lf a c t o r sa n di n s t a b i l i t yo fr a d i of r e q u e n c ys i g n a l ，t h ed a t ac o l l e c t e db yt h e r f i dr e a d e r sa r eo f t e nn o i s ya n du n r e l i a b l e t h u s ，i ti su r g e n t l yt od e v e l o p e f f e c t i v ef i l t e r a n dc l e a n i n gm e t h o d so v e rr f i dd a t as t r e a mt oc o n v e r ti ti n t oa c l e a na n da c c u r a t ed a t a s t r e 锄f o re n t e r p r i s ea p p l i c a t i o n s t h e r e f o r e ，h o wt or e m o v en o i s yd a t af r o mh u g er f i d d a t as t r e a ma r ec o n s i d e r e da sa l li m p o r t a n ti s s u ei nr f i dm i d d l e w a r e a tf i r s t ，w ea n a l y z et h ec h a r a c t e r i s t i c so fr f i dd a t as t r e a ma n dt h er e l a t e dw o r ki n d e t a i l s t h e n ，a f t e ra n a l y z i n gt h ef u n c t i o n a lr e q u i r e m e n t so fr f i d r e a l - t i m em i d d l e w a r e ， w ed e s i g nas y s t e ma r c h i t e c t u r ef o rt h er f i dm i d d l e w a r e b a s e do nt h e s e ，w ef o c u so n t h ec l e a n i n gi s s u e sf o rs i n g l ed a t as t r e a mi nc e n t r a l i z e de n v i r o n m e n ta n dm u l t i p l ed a t a 妣锄si nd i s t r i b u t i o ne n v i r o n m e n tr e s p e c t i v e l y , u s i n go u t l i e rd e t e c t i o nt e c h n o l o g i e s f o rt h ec e n t r a l i z e ds i n g l ed a t as t r e a m ，w ed e s i g n ak e r n e ld e n s i t y b a s e dc l e a n m e c h 觚i s mc o m b i n i n gw i t ho u t l i e r - d e t e c t i o nt e c h n o l o g y t h i sm e c h a n i s mu s e s k e r n e l d e n s i t ye s t i m a t ea p p r o a c h t oc a l c u l a t et h ed e n s i t y d i s t r i b u t i o nf o r + , t a g g e do b j e c t s a c c o r d i n gt ot h i sd i s t r i b u t i o n ，w ec a l ld e t e r m i n et h et r u ep o s i t i o n so f t h et a g g e do b j e c t s a n dr e m o v ec r o s s r e a d i n g s t h ea d v a n t a g e t h em e t h o dt ok n o wa n yp r i o rk n o w l e d g e o ft h i st e c h n o l o g yi st h a ti ti sn o tn e c c e s a r yf o r a n di ti sc o m p l e t e l yad a t a - d r i v e nt e c h n o l o g y f o rt h ep u r p o s eo fr e d u c i n gt h ec o m p u t a t i o n a lc o m p l e x i t yo fd a t as t r e a mp r o c e s s l n g ，、e a p p l yq u a d r a t i cp r o g r a m m i n gm o d e la n dd y n a m i c a l l ym a r k o v c h a i nt h e o r yb a s e do nt h e r e a l lo b s e r v a t i o nd a t aw i t h i np r ea n dp o s ts l i d i n gw i n d o wt oc a l c u l a t et h ep r o b a b i l i t yt h a t t h et a g g e do b j e c tc h a n g e sr e a l l yi t sp o s i t i o n i ft h en u m b e r s o fo b s e r v a t i o n sb e t w e e np r e a n dp o s tt w os l i d i n gw i n d o w sd o n th a v es t a t i s t i c a l l y s i g n i f i c a n tc h a n g e ，w ec a n c o n s i d e r t h a tt h ep o s i t i o no ft h et a gi sn o tc h a n g e d t h u s ，w ec a ni g n o r et h ec o m p u t a t i o n o fk e r n e l d e n s i t ye s t i m a t ei nt h ew i n d o w i no r d e rt of u r t h e ro p t i m i z et h ep r o c e s s i n gs p e e d o fd a t a s t r e a m w ed e s i g na na d a p t i v es l i d i n gw i n d o wa d j u s t m e n ts t r a t e g y , w h i c h c a r ld y n a m i c a 儿y a d j u s tt h ew i n d o ws i z ea c c o r d i n gt ot h ep o s i t i o nc h a n g ef r e q u e n c yo ft a g g e do b j e c t st o r e d u c et h ec o m p u t a t i o nl o a df u r t h e r f o rt h ed i s t r i b u t e dm u l t i p l ed a t as t r e a m s ，w ed e s i g nad i s t a n c e - b a s e dd a t ac l e a n i n g m e t h o d 。w h i c hi sc o m p o s e do fal o c a ls t r e a mo u t l i e rd e t e c t i o na l g o r i t h m ( l s o d ) a n d a g l o b a ls t r e a mo u t l i e rd e t e c t i o na l g o r i t h m ( g s o d ) l s o dt a k e sf u l lo ft h ec h a r a c t e r i s t i c s o fs a f ei n l i e r st od e t e c tt h el o c a lo u t l i e r s ，a n dg s o du s e sas a m p l e - b a s e dm e t h o dt o v l - 基于孤立点检测的r f d 数据流清洗技术研究 a p p r o x i m a t e l ye s t i m a t et h eg l o b a lo u t l i e r s t h em a i na d v a n t a g eo ft h em e t h o di si tc a l l r e d u c ec o m m u n i c a t i o na n dt h ec o m p u t a t i o nl o a di nt h ec e n t r a ln o d e i ns h o r t ，w eh a v es t u d yt h ec l e a n i n gi s s u e so v e rr f i dd a t as t r e a m t h et h e o r e t i c a l a n a l y s i sa n de x p e r i m e n t a lr e s u l t ss h o wt h a tt h em e t h o dp r o p o s e di n t h i sp a p e rc a n e f f i c i e n t l ys o l v et h ec r o s s r e a d i n gi s s u e ，a n dh a v et h ea d v a n t a g e ss u c ha ss h o r tr u n n i n g t i m e ，s m a l lm e m o r yo c c u p a n c y ，h i g hp r e c i s i o ne t c k e y w o r d ：r f i d ；d a t as t r e a m ；d a t as t r e a mc l e a n i n g ；o u t l i e rd e t e c t i o n ；k e m e ld e n s i t y v l l - 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得江西财经大学或其他教育机构的学位或证书所使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 签名：左趁日期：之丑：垒：丝： 关于论文使用授权的说明 本人完全了解江西财经大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其 他复制手段保存论文 ( 保密的论文在解密后遵守此规定) 签名：么巳l 导师签名：j 手堡! 垂一日期：础 基于孤立点检测的r f i d 数据流清洗技术研究 1 1 研究背景及意义 第1 章绪论 射频识另l j ( 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 ) 技术是_ 种利用射频通信实现的 非接触式自动识别技术，其最早应用可追溯到第二次世界大战中飞机的敌我目标识 别。r f i d 的基本原理是利用射频信号和空间耦合( 电感或电磁耦合) 传输特性，实现 对被识别物品的自动识别及交换数据。在r f i d 的实际应用中，r f i d 标签附着在被 识别的物体上( 表面或内部) ，当带有i u i d 标签的物品经过阅读器的识别范围时，阅 读器自动以无接触的方式读取r f i d 标签中的约定识别信息，从而实现自动识别物品 或者自动收集物品标志信息的功能。r f i d 标签具有体积小、容量大、寿命长、可重 复使用等特点，可支持快速读写、非接触识别、移动识别、多目标识别、定位及长 期跟踪管理等。但是由于技术和成本原因，一直没有得到广泛应用。 近年来，随着大规模集成电路、网络通信、信息安全等技术的发展，r f i d 技术 已开始进入商业化应用阶段。r f i d 技术正显示出巨大的发展潜力与应用空间，被认 为是2 l 世纪最有发展前途的信息技术之一，现已广泛应用于物流、制造、交通、运 输、医疗、防伪、跟踪、设备和资产管理等众多公共信息服务行业。随着r f i d 相关 技术的不断完善和成熟，r f i d 产业将成为一个新兴的高技术产业群，成为国民经济 新的增长点。因此，研究r f i d 技术，发展r f i d 产业对提升社会信息化水平、促进 经济可持续发展、提高人民生活质量、增强公共安全与国防安全等方面将产生深远 影响，具有重大战略意义。 e p c g i o b a l 出台的第二代r f i d 阅读器标准对阅读器的阅读速率重新做出了规 定：阅读器每秒钟可读取1 8 0 0 个电子标签【l j ，这比第一代标准提高了约1 0 倍。也就 是说，一个拥有2 0 台阅读器的配送中心在高峰期一秒钟可以产生3 6 0 0 0 个事件，而 这些事件通常是以流的形式出现的。为此，人们在i 江i d 系统的应用支撑软件中，除 了设计运行在标签和阅读器上的软件之外，还专门设计了介于阅读器与企业应用之 间的中间件( m i d d l e w a r e ) ，用于分析和处理大容量r f i d 数据流，并将其作为r f i d 系统中的一个重要组成部分，也称之为r f i d 系统的“神经中枢”1 2 】。 尽管r f i d 中间件能处理r f i d 数据流，但要让其真正发挥作用，提高r f i d 数 据流的质量却是一个不容小视的问题。众所周知，由于外部环境的干扰和射频信号 的不稳定性，阅读器所产生的数据通常是不可靠和有噪声的，如果r f i d 中i 白j 件不能 有效地对具有噪声的数据流进行清洗，那么无论其它构件设计得如何完美，其提供 给上层应用的信息都是不可靠的，并最终影响商业决策的制定。因此，r f l 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 技 术应用即将迎来巨大增长时期，r f i d 芯片、读写设备、软件、技术和服务等全球市 场总额从2 0 0 2 年的1 0 亿美元增长到2 0 0 9 年的5 8 7 亿美元。我国相关政府部门也非 常重视r f i d 产业发展。国家8 6 3 计划已经将“射频识j i j ( r f i d ) 技术与应用 作为先 进制造业技术领域的重大项目进行立项。2 0 0 6 年6 月，以科技部牵头，联合国家1 5 个部委制定的中国r f i d 技术政策白皮书予以公布，为中国r f i d 技术与产业未 来的发展提供了系统性指南，这无疑将推动r f i d 技术应用进入一个新的阶段。在未 来的发展中，射频识别技术将结合其他高新技术，如g p s 、生物识别技术、现代通 信及计算机技术等，由单一识别向多功能识别方向发展的同时，实现跨地区、跨行 业应用。 本项目将研究r f i d 实时数据流清洗技术，为r f i d 未来广泛应用提供有力的理 论支持和技术支撑。因此，本项目的研制具有十分重要的理论研究意义和经济价值。 1 2r f i d 数据流特征 相对于传统数据库中的静态数据，数据流具有以下特点p j ： ( 1 ) 在线性：数据流中的数据通常是以在线方式输入到系统中，且数据输入次序 是系统不可以控制的； ( 2 ) 无界性：从理论上说，数据流的长度是无限的。相对于有限的存储空间而言， 数据流应用中产生的数据不仅长度，而且数据值域几乎是无界的，远远超过数据库 系统能够持久存储、精确计算和反复访问的能力； ( 3 ) 不可预测性：数据产生的次序和间隔等统计特性事先不可预测； ( 4 ) 一次性：除非显式地存储数据，否则对“流过 的数据不可以再次访问，或 者访问的代价是高昂的。 上述界定既包含数据流本身的特点，也包含了对数据流处理算法的要求。但是， 由于r f i d 系统具有自身的特点，使得其所产生的数据流与一般的数据流相比有着本 质的区别，其独特特性如下： ( 1 ) 时态性、动态性和关联性。r f i d 阅读器会动态产生关于标签对象状态变化 的观察数据，这些数据通常包含观察时刻以及该时刻的对象位置和状态等信息，如 产品的上架、售出、被盗等状态。这些数据往往不是相互独立的，而是相互关联的， 主要表现为时态关联和空间关联：时态关联表达事件之间的时序关系；空间关联表 达事件发展的历史轨迹；时空关联共同表达了与对象有关事件的变化过程。 基于孤立点检测的r f i d 数据流清洗技术研究 ( 2 ) 批量性和海量性。r f i d 数据流具有批量特点，即将多个对象集中进行观察。 例如，当阅读器识别一个集装箱的同时，也会读到大批箱内所装物品的标签数据。 同时，r f i d 设备的大规模部署也会产生空前的海量数据。据统计，沃尔玛三天之内 就会产生超过美国国家图书馆所包含的全部数据量【4 】。即使是部署适量r f i d 设备的 公司一天之内也会产生十几亿字节的数据。 ( 3 ) 不准确性。现有的r f i d 阅读器在读取标签时会产生误差，如漏读、多读和 脏数据等。据统计，现实世界中部署的r f i d 阅读器的漏读率达到3 0 - 4 0 1 5 儿6 j 。 由于不准确数据会引起高层应用作出错误的决策，因此，在数据进入系统高层应用 之前需对其进行清洗。 ( 4 ) 异构性。一个阅读器可以识别出各式各样的标签对象，即r _ f i d 数据流中可 能包含有多种不同性质的观察值。例如，在一个安检入口，既可以识别进出的人员， 也可以识别进出的物品。而它们是具有不同性质的对象，因此所对应事件的语义也 不相同。 ( 5 ) 语义丰富性。r f i d 原始数据是一种低层的基础数据，必须上升为高层业务 逻辑数据，并与现有应用相集成才能真正地发挥作用。r f i d 阅读器观察到的对象通 常携带有与上下文状态和背景知识有关的隐含信息，且与上层应用逻辑存在密切关 系。这些相关信息可用于进一步推导出衍生信息。例如，从产品的e p c 码可查出它 的型号、价格、产地等；从阅读器的位置可得知物品所在的位置，等等。 ( 6 ) 随机性。外界环境变化对射频信号的干扰存在很大的随机性，如金属物品的 突然出现、管理人员检查物品时突然靠近等，都会导致信号反射而出现多读数据。 这种多读数据的产生是随机的，没有变化规律。 ( 7 ) 隐蔽性。多读数据与真实数据的表现形式一样，两者在表面上没有任何区别， 基本都是以 的形式出现。若不及时地对多读数据进行 过滤，它们就会隐没在海量的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 3 国内外研究现状分析 1 r f l l ) 中间件研究 r f i d 中间件在国际上仍是一个较新的研究领域。a u t o i d 中心提出的e p c 网络， 包括了e p c 编码、s a v a n t 、对象名字服务( o b j e c tn a m es e r v i c e ，o n s ) 、e p c 信息服 务( i n f o r m a t i o ns e r v i c e s ) 、物理标示语言( p h y s i c a lm a r k u pl a n g u a g e ，p m l ) 等关键技术， 得到了部分大学和许多企业的支持。e p c 组织还提出了r f i d 中间件在软件方面的 第l 章绪论 标准a l e ( a p p l i c a t i o nl e v e le v e n t s ) 。s u nj a v as y s t e mr f i d 中间件是基于以上所提出 的e p c 网络基本构架设计的，并支持e p c g l o b a la l e 软件标准，可以过滤、聚集与 处理大量来自r f i d 网络边缘的数据，为企业的各类应用提供流式商务信息。 m i c r o s o f t 所提出的r f i d 系统层次结构包括设备层、数据收集和管理层、事件和工 作流管理层、基于开放标准的服务接口层和应用与解决方案层等。i b m 应需解决方 案中心提出了一种轻型r f i d 中间件架构，它主要是通过一条信息总线( r f i db u s ) 来代替复杂的层次结构。o r a c l e 设计了内嵌在其应用服务器1 0 9 中的传感器边缘服 务器，具有数据收集、分组、规则过滤、数据打包发送等功能。s y b a s e 公司也推出 了建立在s y b a s e 核心产品上的r f i d 中间件，包含了物理设备层、r f i d 网络层、处 理层、维持层、整合层、表示层和一些建模和工具组件集，而且还包含一些探查、 警报、通告和管理的部分组件。c a m b r i d g e 大学的a u t o i d 中心对r f i d 时间特性进 行了研究，其成果主要用于生产自动化控制领域和时间数据库的事件操作上。西门 子公司的r f i d 中间件由r f i d 阅读器、事件管理器和r f i d 数据服务器组成。该中 间件基于动态关系e r 数据模型设计，并提出了基于规则的事件过滤、转换和聚合机 制1 7 j 。s t a n f o r d 大学的d a v i dl u c k h a m 教授领导并开创了复杂事件处理( c e p ) 技术。 c e p 的主要任务是“消费”基于事件的数据，并实时地将一些规则应用于这些事件 上，将未加工的原始事件数据转换成有价值的商业信息网。u c l a w i n m e cr f i d 实 验室所设计的r f i d 中间件是在分布式架构上构建的w e b 服务，包含了简单的捕获、 平滑、过滤、路由、聚合等功能，主要应用在一些试验性演示系统上1 9 】。i b mh a i f a 实验室设计了s i t u a t i o nm a n a g e r ，其中s i t u a t i o n 本身是对复合事件概念的表现力、灵 活性和可用性的扩展，其基本内容包含一种语言和一套有效的运行机制，其理论基 础来自对基于规则系统的研究i 1 0 1 。 在国内，由于r f i d 技术进入时间较短，各方面的工作还处于起始阶段。虽然我 国政府在国家“十一五”规划和8 6 3 计划中，对r f i d 应用提供了政策、项目和资 金的支持，但与国际技术的发展相比，在很多方面还存在明显的差距。依托国家8 6 3 计划“无线射频关键技术研究与开发”课题，中科院自动化所开发了r f i d 公共服务 体系基础架构软件和血液、食品、药品可追溯管理中间件；华中科技大学开发了支 持多通信平台的r f l d 中间件产品s m a r t i ；上海交通大学开发了面向商业物流的数据 管理与集成中间件平台。此外，国内产品还包括东方励格公司的l y n k o a l e 中间 件、清华同方的e z r f i d 中间件、e z o n e e z f r a m e w o r k 基础应用套件等。虽然目前已 经有了一些初具规模的r f i d 中间件产品，但大多没有在企业进行实际应用测试，与 国外的r f i d 中间件产品相比，还处于实验室阶段i 】。 虽然上述研究机构和公司都开始了r f i d 中间件设计与研究，但是，这些研究还 都存在着或多或少的不足和限制。如s u n 中间件的功能单薄、过滤规则简单、缺少 复杂事件定义和处理能力；m i c r o s o f t 、i b m 、o r a c l e 、s y b a s e 等厂商所提的i 疆i d 中 基于孤立点检测的r f i d 数据流清洗技术研究 间件的设计大多是基于自己目前所研发的核心产品或技术的应用，有太大的依赖性 和较小的扩展性。 2 r f i d 数据流清洗技术研究 在i 强i d 系统中，由于射频信号干扰和标签周围环境等诸多原因的影响，i 球f d 阅读器产生的数据流通常是不可靠、不确定的，这严重地影响了r f i d 技术的广泛应 用。因此，系统必须增加对r f i d 数据流的清洗环节，消除不确定数据流中的噪声数 据，使阅读器读取到的数据，无论从时间上还是从数值上，尽可能地接近真实数据。 在数据仓库中，针对少量预定义的任务，通常采用离线、集中、循环及交互式 处理方式清洗数据l l2 1 。但是，由于r f i d 数据具有时序的，其处理方式只能采用在 线方式。r f i d 数据流的清洗过滤主要是针对漏读、多读和冗余数据进行。 针对漏读和多读情况，大部分中间件都采用平滑窗口方法进行数据清洗，即设 定一个大小固定的窗口来填补漏读数据。但由于窗口大小固定不变，致使窗口过小 会产生拒真数据，窗口过大会产生纳伪数据。因此，大小固定的窗口并不能根据数 据的特点精确地填补数据。 文献 1 1 】提出了基于概率模型的s m u r f 自适应数据清洗方法。它考虑了标签的 完整性和动态变化性，将r f i d 数据流看作统计学中的随机事件，然后依据概率来自 适应调整窗口大小，有效地保证了数据的准确性。但该方法所研究的纳伪是由过长 的阅读( 抽样) 窗口所产生的，并不是由反射或其它环境因素所产生。另外，它只解决 了单个阅读器检测问题，不能用于多个阅读器情形。文献 1 3 1 采用基于抽样的方法恢 复丢失信息，但它不能处理多读情形。文献 1 4 1 利用概率推理的方法提出了一种推断 移动环境下标签位置的方法，但该技术需要事先知道标签和阅读器的运动规律等先 验知识，因此不能应用于没有规律可遵循的监控环。数据熔炉技术讨论了概率r f i d 处理架构，但没有给出具体实现策略【l5 1 。z h a n g ，e ta 1 定义了不确定性数据流上求解 频繁元素问题，并基于可能世界语义识别所有的频繁元素1 1 6 1 。文献【1 7 】能够处理概率 数据流上的查询分析，但其工作主要集中在查询上，如选择、映射和聚集查询等。 l a h a r 系统能够处理不精确数据流，特别适用于r f i d 环境【i 引。文献【1 9 】基于统计信 息提出了针对传感器数据中脏数据清洗的贝叶斯方法( b a y e s i a n a p p r o a c h ) ，其清沈结 果是属性值的概率密度函数，但该方法需要大量先验知识。文献【2 0 】建立了基于历史 信息的不确定信息自适应处理模型，但由于该模型较复杂( 由四部分组成：历史数据 模块、错误数扼模块，数据预测模块和数据纠正模块) 限制了其广泛应用。文献【2 1 】 建立了完整的传感器噪声数据查询处理模块，并综合利用卡尔曼过滤器、回归算法 和知识库等方法建立了一种自学习模型。文献 2 2 1 基于s q l 查询模型提出了一种 e s p ( e x t e n s i b l es e n s o rs t r e a mp r o c e s s i n g ) 机制，它根据数据的时间相关性和空间相关 性特点进行清沈，且能针对各种不同类型的错误数据进行清洗。文献【2 3 】提出了以机 第1 章绪论 器学习为背景的清洗算法，它针对大规模r f i d 数据集，设计了一系列数据清洗策略 及优化算法。文献 2 4 针对不同类型的数据提出了相应的清洗方案：针对漏读现象， 可采用提高阅读器频率方法；针对多读现象，预先设定一窗口大小，统计在该段时 间内每个标签被读到的次数，如果一标签的统计次数小于某阈值，则认为其相关数 据是多读数据；针对重复数据，对时间相隔太短的相同进行消重，只需留下一个数 据项；针对时间戳乱序问题，将接收到的数据进行缓存排序并预先设定一个最大延 迟时间，将在此时间到达后的数据删除。该算法的缺陷是处理延迟较大，效率低， 而且只考虑了单个阅读器情形。文献【2 2 2 5 】提出了基于s q l 的数据清洗方法( 预处 理方法) ，即对原始数据进行s e l c e t 等操作，选出符合条件的数据。针对数据冗余， 文献【2 6 】提出了一个随机、分散、局部近似的r r e 算法，可消除冗余，但该算法假 设阅读器固定不动，而该假设在实际应用中有时是不能保证的。如在供应链环境中， 为了优化商业处理，阅读器的位置通常是不断变化的。 综上所述，已有r f i d 数据清洗方法在深度和广度都存在一定缺陷，包括： ( 1 ) 需要具备大量统计信息和先验知识； ( 2 ) 清洗功能在阅读器节点或基站完成，对硬件要求较高、成本较大： ( 3 ) 不能处理r f i d 数据的不确定性。 本文将采用数据挖掘中常用的孤立点检测方法进行数据清洗。孤立点检测技术 主要有两类：基于距离的方法和基于密度的方法。 3 孤立点检测技术研究 ( 1 ) 基于距离的方法 k n o r r 和n g ( 1 9 9 8 ) 提出了基于距离的孤立点检测方法【2 7 1 ，它把记录看作高维空 间中的点，并根据某个距离函数计算对象相互之间的距离。孤立点则是数据集中与 大多数点之间的距离都大于某个阈值的点，通常被描述为d b ( p c t ，d m i n ) ，即如果数 据集r 中的对象至少有p c t 部分与对象0 的距离大于d m i n ，则对象d 称为d b ( p c t ， 咖扬) 孤立点。该方法认为，如果一个对象是孤立点，那么该点必远离大部分对象。 换句话说，我们可以将基于距离的孤立点看作是那些没有“足够多 邻居的对象。 目前已经研制了许多高效的基于距离的孤立点检测算法，主要有i n d e x b a s e d 算 法【2 8 1 、n e s t e d 1 0 0 p 算法和c e l l b a s e d 算法1 3 0 。这些算法的缺陷是需要事先确定参 数p c t 和d m i n ，而这通常是比较困难的。特别是对不同聚类密度的数据集而言，d m i n 差异可能很大且无规律可循。因此，对于给定不同参数d m i n ，孤立点检测结果通常 具有很大的不稳定性。文献【3 1 】采用基于距离的方法数据流中的孤立点进行检测，但 该技术所处理的流数据是确定性的。 ( 2 ) 基于密度的方法 基于距离的方法是从全局的角度来研究孤立点，而真实世界中的数据集往往是 复杂且分布不均匀的。基于距离的孤立点挖掘算法就很难正确而有效地处理此类数 基于孤谚点榆测的r f l d 数据流济洗技术研究 据集。m b r e u n i g l 3 2 j 等首先提出了基于密度的方法处理异常数据。该方法认为：具有 高密度邻居的数据点不是孤立点，具有低密度邻居的数据对象可能是孤立点。该观 点摈弃了以前所有的异常定义中非此即彼的绝对异常观念，这更加符合现实生活中 的应用。近年来，许多研究者提出了“局部孤立点”的方法，l o f l 3 3 】，l o c l l 3 4 1 和 l s c l 3 5 1 1 3 6 j 就是其中三个主要的算法。这些算法的主要思想是为数据集中的每个对象 计算局部稀疏率和局部稀疏系数。尽管算法很有效，但它们不适用于大规模的数据 集。由于为每个对象计算局部稀疏率和局部稀疏系数会耗费很大的计算量，文献 3 7 3 8 提出了不同的密度定义方法以提高算法效率。文献【3 9 】讨论了基于核密度的 不确定数据孤立点检测方法，但该方法不能处理流数据。 另外，随着空间数据挖掘的兴起，s h e k h a r 等提出了一种用于检测空间孤立点的 图元素集【4 0 】。该方法是将空间点邻居的平均属性值与某一空间点的属性值进行比较， 以判断该空间点是否为孤立点。已有基于统计技术的空间孤立点检测方法可分为图 论方法和定量测试两类。 1 4 本文所做工作及论文组织 本研究得到江西省教育厅重点项目i 心i d 实时数据处理中间件关键技术研究 ( g j j 0 8 3 4 3 ) 和国家自然科学基金项目嵌入式移动计算环境下实时数据库自适应及动 态恢复策略( 6 0 8 6 3 0 1 6 ) 的支持，主要研究r f i d 数据流清洗技术，以提高r f i d 数 据流质量，为高层数据流查询处理提供干净、准确的数据。全文拟开展的主要工作 如下： ( 1 ) 建立r f i d 实时中间件处理框架； ( 2 ) 针对集中式单数据流，结合孤立点检测技术，设计基于核密度的数据清洗机 制。要求该机制既能保证准确率，又能实时处理海量数据。 ( 3 ) 针对分布式环境下的多数据流，设计基于距离的分布式r f i d 数据流清洗机 制，包括局部流孤立点检测算法和全局流孤立点检测算法。 全文共分五章，各章组织如下： 第一章是绪论，主要介绍研究背景、研究目的意义、r f i d 数据流特征及研究现 状分析； 第二章是r f i d 实时中间件功能分析和体系结构设计； 第三章探讨了基于核密度的集中式r f i d 数据流清洗算法及其优化技术； 第四章讨论了分布式环境下基于距离的r f i d 数据流清洗算法； 第五章对全文工作进行总结，并指出下一步研究方向。 第2 章r f i d 实时中间件功能及系统结构 第2 章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 实时中间件功能需求及体系结构。 2 1r m 实时中间件功能需求 通过对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 数据流中的事务在读取时空数据时，通常要求所得到的数据值要能够反映 现实世界的当前状态。因此，需采用一致性机制来保证数据的时间一致性。 3 提供基于优先级的r f i d 事件处理技术 对事件进行实时处理是r f i d 实时软件平台的核心。r f i d 事件的实时处理技术 包括数据过滤及清洗、事件处理模型、基于优先级的事件调度、复杂事件的实时检 测方法等。 ( 1 ) 数据过滤及清洗策略 数据过滤和清洗是在输入的巨量数据中发现有用的和重要的数据，过滤冗余、 无关的数据，其目标在于减小无效事件的数量，设计有效的过滤清洗算法是系统的 关键，包括分组、计数、冗余删除等操作。 ( 2 ) r f i d 事件处理模型 r f i d 事件可从多个方面进行分类：根据事件语义的聚合程度，可分为简单事件 和复杂事件；根据事件层次，可分为底层事件和高层事件，其中底层事件是系统产 生的实际事件，高层事件是由用户自定义的事件；根据系统响应方式，可分为常规 事件和异常事件等。目前，基于复杂事件处理模型在r f i d 领域已得到较多应用。 基于孤立点检测的r f i d 数据流清洗技术研究 ( 3 ) 基于优先级的事件调度机制 已有的r f i d 事件处理器可以处理大量事件，为高层应用提供有意义的复杂事 件。但在已有r f i d 事件器没有考虑到r f i d 事件的实时性，即不能及时响应那些时 间紧迫的事件，致使引发一些灾难性的后果。因此，事件处理器应该具备对不同优 先级事件进行调度处理的能力，以保证尽可能多的事件能在其截止期内处理完成。 ( 4 ) 复杂事件的实时检测方法 虽然传统的e c a 事件检测可以发现事件，但是它却不支持时序约束，也没有考 虑到事件检测的实时性，复杂事件处理技术则可有效地解决事件间的时序问题。因 此，开发基于复杂事件处理的r f i d 检测引擎是必不可少的。 4 提供面向海量r f i d 数掘的事件压缩查询技术 r f i d 应用会动态产生大量事件，因此事件数据( 动态数据) 通常是海量级的。 r f i d 中间件应采用结合数据压缩技术和事件语义进行事件压缩，并保证高效的查询 能力。 5 提供支持实时数据和历史数据查询的混合存储引擎 r f i d 系统应