（计算机应用技术专业论文）基于rfid数据的若干联机分析挖掘方法研究.pdf

摘要 近年来，射频识另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 y 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 数据管 理和挖掘方法的基础上，本文主要对r f i d 数据立方体的构建、r f i d 立方体内异 常发现、单层r f i d 位置序列挖掘以及多层r f i d 位置序列挖掘等几个方面做了深 入的研究。本文的主要创新点如下： 1 ) 针对传统的数据库不能满足对海量r f i d 数据查询的快速响应问题，结合 现有的数据仓库及o l a p 技术，本文提出一种r f i d 数据立方体的构建方法，根据 用户兴趣度确定兴趣层，在兴趣层上选择部分立方体单元进行部分物化，保证在 快速构建立方体的同时还能够快速响应用户查询。 2 ) 以本文构建的r f i d 立方体为基础，提出了阈值异常和区间异常两种基于 回归分析的异常发现方法，根据回归系数帮助用户快速地找出数据单元内的异常 数据。阈值异常方法通过比较数据的规格化残差和用户给定的偏差阈值来发现异 常数据。区间异常方法在不需要用户给出阂值情况下，通过比较残差绝对值和每 个点的置信区间自动发现异常数据。 3 ) 鉴于传统的频繁模式挖掘和序列模式挖掘方法不能有效解决r f i d 频繁路 径挖掘的问题，本文在充分研究r f i d 路径数据特点的情况下，重点考虑其中包含 的位置序列，在现有的序列模式挖掘方法基础上，提出一种挖掘r f i d 位置序列的 方法。 4 ) 考虑到r f i d 数据中地点维具有自然的层次特征，且不同用户的兴趣层次 也各不相同，需要挖掘多层的位置序列。为了解决这一问题，本文集成现有的序 列模式挖掘方法以及多层序列模式挖掘方法，提出挖掘频繁多层和交叉层r f i d 位 置序列的方法。 列 关键词：射频识别，数据挖掘，数据立方体，异常，位置序列，多层位置序 a b s t r a c t i nr e c e n t y e a r s ，t h e r a d i of r e q u e n c y i d e n t i f i c a t i o n ( r f i d ) t e c h n o l o g y i s d e v e l o p i n gf a s t ，t h ed e t e c t i n gd i s t a n c eo fr e a d e rb e c o m e sl a r g e ra n dr e a d i n ga c c u r a c yo f r e a d e ri n c r e a s e s ，t h ep r i c eo fv a r i o u st a g sd r o p s ，w h i c hf a c i l i t a t er f i db ea p p l i e di n m o r ea n dm o r e a p p l i c a t i o n s ，a n db e u s e di nn o to n l y e x p e n s i v eb u l kc o m m o d i t yb u ta l s o c o m m o ns i n g l ep r o d u c t l a r g er e t a i l e r sl i k ew a l m a r t ，t a r g e t ，a n da l b e r t s o n sh a v e a l r e a d yb e g u ni m p l e m e n t i n gr f i ds 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 r i n gt h e i rs u p p l i e r st 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 d c a s el e v e l s b e c a u s et h ed e v e l o p m e n to ft e c h n o l o g ya n dt h em a s sd e m a n d ，t h ep r i c eo f t a g sd r o p sf u r t h e r , a n ds t i c k i n gt a g so ni n d i v i d u a li t e m si nas u p p l yc h a i nc o m e st ob e p r a c t i c a l w i t ht h ew i d ea p p l i c a t i o no fr f i d ，h o wt oo r g a n i z ea n dm a n a g et h e e n o r m o u sv o l u m eo fd a t ac o l l e c t e di nr f i ds y s t e mi st h em a i nc h a l l e n g e t h em a s s d a t a s t o r e di nd a t a b a s eo rd a t aw a r e h o u s e ，w i l ll e a d st od a n g e r ss u c ha s “d a t a e x p l o s i o n a n d d a t ag r a v e s ”，i fi tc a n n o tb es u i t a b l ed e a l tw i t h t h e r e f o r e ，h o wt o e x t r a c ti n t e r e s t i n gi n f o r m a t i o nf r o mm a s sr f i dd a t ai s e s p e c i a l l yi m p o r t a n t d a t a m i n i n gt e c h n o l o g yw a sp r o p o s e dt o s o l v et h i s i s s u e ，w h i c hc a ne x t r a c tp o t e n t i a l i n t e r e s t i n gi n f o r m a t i o na n dk n o w l e d g ef 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 d r a n d o mp r a c t i c a ld a t a w h e nt h er f i dt e c h n o l o g yi su s e df o rt r 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 , w ew i l lf a c et w os e r i o u sp r o b l e m s ：h o wt om a n a g et h em a s sr f i dd a t at or e s p o n d u s e r s q u e r i e si nt i m e ；a n dh o wt oa n a l y z et h em a s sr f i dd a t at of i n dt h ep o t e n t i a l i n t e r e s t i n gr u l e sa n dt r e n d sf o ra s s i s t i n gd e c i s i o n - m a k i n g t h em o s ti m p o r t a n tp o r t i o no f r f i dd a t ai st h ep a t ho fm o v i n g p r o d u c t s ，a l s oc a l l e dt r a c ed a t a , a n dm i n i n gr f i dd a t a i sv i r t u a l l ym i n i n gp a t h s m a n a g i n gr f i dd a t ar e f e r st oh o wt oo r g a n i z et h em a s sr f i d d a t aa n dh o wt of i n dt h ea b n o r m a ld a t a ；w h i l ea n a l y z i n gr f i dd a t ad e a l sw i t lt h ep a t h s 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 ：b u i l d i n gr f i dd a t ac u b e ，e x c e p t i o nf i n d i n gi n r f i dd a t ac u b e , m i n i n gr f i dl o c a t i o ns e q u e n c e s ，a n dm i n i n gm u l t i - l e v e lr f i d l o c a t i o ns e q u e n c e s 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 ea s f o l l o w s ： 1 ) c o n s i d e r i n gt h ep r o b l e mt h a tt r a d i t i o nd a t a b a s ec a n n o tr e s p o n du s e r s q u e r i e so n m a s sr f i di nt i m e ，w ep r o p o s eam e t h o do fb u i l d i n gr f i dd a t ac u b eb a s e do np r e s e n t d a t aw a r e h o u s ea n do l a p t e c h n o l o g i e s o u rp r o p o s e dm e t h o dn e e d sl e s ss t o r a g es p a c e b ys p e c i f y i n gt h ei n t e r e s tl a y e r sa n dc h o o s i n gp a r to fc u b o i d so ni n t e r e s tl a y e r st o m a t e r i a l i z e 2 ) b a s e do nt h er f i dd a t ac u b eb u i l ti nt h i sp a p e r , w ef u r t h e ri n t r o d u c et w on e w d e f i n i t i o n so fr e g r e s s i o n - b a s e de x c e p t i o n s ，t h r e s h o l de x c e p t i o na n di n t e r v a le x c e p t i o n , b a s e do nw h i c ht w oa l g o r i t h m sa r ep r o p o s e dt oh e l pu s e r sf i n dt h ee x c e p t i o n si nt h e d a t ac e l l sf a s t w ec o n s i d e rd a t aa sa ne x c e p t i o nb yc o m p a r i n gi t sn o r m a lr e s i d u a lt ot h e t h r e s h o l du s e rg i v e ni nt h ep r o c e s so ft h r e s h o l de x c e p t i o n ，w h i l ec o m p a r i n gt h ea b s o l u t e v a l u eo fr e s i d u a lt ot h er e f e r e n c er a n g ei nt h ep r o c e s so fi n t e r v a le x c e p t i o n 3 ) s i n c et h et r a d i t i o n a lf r e q u e n tp a t t e r n sm i n i n ga n ds e q u e n t i a lp a t t e r n sm i n i n g m e t h o d sc a n n o tb eu s e dt om i n ef r e q u e n tr f i dp a t h se f f i c i e n t l y , w et a k et h ef e a t u r e so f r f i dp a t h ，e s p e c i a l l yt h el o c a t i o ns e q u e n c e si n t oa c c o u n t t h e nw ep r o p o s ea n a l g o r i t h mo fm i n i n gr f i dl o c a t i o ns e q u e n c e si nt h i sp a p e rb a s e do nt h ee x i s t i n g m e t h o d so fs e q u e n t i a lp a t t e r n sm i n i n g 4 ) t h ed i m e n s i o n “l o c a t i o n ”h a st h ec h a r a c t e r i s t i co fm u l t i p l eh i e r a r c h i e s ，a n d d i f f e r e n tu s e r sh a v ed i f f e r e n ti n t e r e s tl a y e r s s om u l t i 1 e v e l l o c a t i o ns e q u e n c e ss h o u l db e m i n e di nr f i da p p l i c a t i o n s t os o l v et h i si s s u e ，w ep r o p o s eo i la l g o r i t h mo fm u l t i l e v e l a n dc r o s s l e v e lr f i dl o c a t i o ns e q u e n c e sm i n i n gi nt h i sp a p e r , b a s e do nt h et r a d i t i o n a l m e t h o d so fs e q u e n t i a lp a t t e r n sm i n i n ga n dm u l t i - l e v e ls e q u e n t i a lp a t t e r n sm i n i n g 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 ，d a t ac u b e ， e x c e p t i o n ，l o c a t i o ns e q u e n c e ，m u l t i - l e v e ll o c a t i o ns e q u e n c e 扬州大学硕士学位论文 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 学位论文作者签名：丁有侈 签字日期：弘，口年f 月切日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。 本人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学 技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向 社会公众提供信息服务。 学位论文作者签名：丁有钐导师签名： 签字日期：五，口年岁月，口日 签字日期：p 年f 月o 日 ( 本页为学位论文末页。如论文为密件可不授权，但论文原创必须声明。) 丁有伟：基于r f i d 数据的若干联机分析挖掘方法研究 第一章引言 联机分析处理【m 】是使分析人员、管理人员或执行人员能够从多角度对信息进 行快速、一致、交互地存取，从而获得对数据的更深入了解的一类软件技术，是 数据仓库系统的主要应用，支持复杂的分析操作，提供直观易懂的查询结果，侧 重于决策支持。它的主要目标是满足决策支持或者满足在多维环境下特定的查询 和报表需求。 数据挖掘o 】就是从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取出隐含在其中的、人们事先不知道但又是潜在有用的信息和知识的过程，是 一种从大型数据库或数据仓库中提取隐藏预测性信息的新技术。它旨在从繁杂不 清的数据中发现潜在模式，找出最有价值的信息，辅助用户决策。 r f i d 1 1 1 2 】技术引入供应链管理，可以跟踪物流网络中移动物品的运动轨迹。 通过挖掘物品路径数据，找出频繁路径信息，能够帮助用户进一步了解商品的移 动趋势，预测商品的移动，找出异常的移动商品，优化物流环节降低物流成本， 为用户决策提供有力支持。 本文主要结合数据仓库、数据挖掘、r f i d 系统及供应链管理，提出一种有效 的供应链中移动物品数据组织存储和管理分析的理论模型，为进一步研究如何将 r f i d 技术全面高效地应用于供应链管理提供理论基础。在本章中，首先介绍数据 仓库与o l a p 技术以及数据挖掘技术的发展，射频识别技术的特点及发展：接着 介绍本文的主要研究内容，包括如何为供应链中物品移动数据构建立方体存储结 构，设计立方体结构中异常发现算法，设计移动物品的位置信息的挖掘算法。最 后介绍文章的组织结构。 1 1 研究背景 随着社会信息化程度的深入，数据库技术的不断发展及数据库管理系统的广 泛应用，不论是个人还是企业所积累的数据越来越多。快速增长的数据存储在大 型数据库中，数据量的多少直接影响数据查询操作的响应速度。为了提高查询响 应速度，数据仓库与o l a p 技术应用而生。数据仓库( d a t aw a r e h o u s e ，简称d w ) 是一个面向主题的、集成的、相对稳定的、反映历史变化的数据集合，用于支持 2 扬州大学硕士学位论文 管理决策。联机分析处理( o n l i n ea n a l y t i c a lp r o c e s s i n g ，简称o l a p ) 技术是数 据仓库的重要应用，是针对某个特定的主题进行联机数据访问、处理和分析，通 过直观的方式从多个维度、多种数据综合程度将系统的运营情况展现给使用者。 多维性是o l a p 应用的重要特点，o l a p 应用所需的基本数据操作都具有多维特 征，如c u b e 操作。在o l a p 中往往需在这些海量数据上进行即席( a dh o c ) 的复 杂聚集查询，并要求及时向用户提供分析结果数据用以辅助决策。 数据量的快速增长以及应用领域的扩展和应用要求的细化促使数据库系统的 发展，如时间序列数据库、空间数据库、多媒体数据库等新型数据库的提出和发 展。尽管目前的数据库系统可以高效地实现数据的存储、查询、统计等功能，但 是由于数据量庞大以及数据库系统中分析工具的匮乏，使其只能对既有数据进行 管理而无法发现数据之间的隐藏联系，更无法根据现有数据预测未来的发展趋势。 因此，迫切需要一种解决如何有效地从大规模( 或者海量) 数据中发现隐藏的有 用信息，甚至是根据已有的数据信息对未来的趋势做出预测，以便为正确决策提 供支持的方法。数据挖掘( 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 ) 是指从大型数据库或者数据仓库中 提取隐含的、未知的、非平凡的及有潜在应用价值的信息或者模式。数据挖掘其 实是一种决策支持的过程，它融合了数据库、人工智能、数理统计等多个领域的 理论和技术，高度自动化的分析企业原始数据，做出归纳性的推理，从中挖掘出 潜在的规律，帮助企业做出正确的决策。例如，对某零售企业而言，利用数据挖 掘技术可以从积累的大量原始数据中发现规律。挖掘历史交易信息、商品信息及 客户基本信息等，可以发现不同消费群体的消费习惯与不同商品的销售规律。根 据挖掘得到的信息进行正确的决策，及时调整经营策略，可以最大可能地保障商 家的利益。 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 ， 简称a i t ) ，这项技术利用射频信号在阅读器和贴有电子标签的移动物品之间传输 数据，达到识别和跟踪物品等目的。r f i d 技术是继承了雷达技术发展而成，在二 战期间首次应用，用来识别敌我飞机。1 9 4 8 年哈里斯托克曼( h a r r ys t o c k m a n ) 在 无线电工程师协会( i n s t i t u t eo f r a d i oe n g i n e e r s ) 学报上发表的“利用能量反射进行通 讯( c o m m u n i c a t i o nb ym e a n so fr e f l e c t e dp o w e r ) ”奠定了r f i d 技术的理论基础。 2 0 世纪5 0 年代，r f i d 技术处于早期的探索阶段，主要是实验室的实验研究。6 0 年代，r f i d 的理论得到发展，开始尝试实际应用，首次使用在零售商店，防止贵 重物品的丢失，这是r f i d 第一次广泛的商业应用。7 0 年代，r f i d 技术继续吸引 丁有伟：基于r f i d 数据的若干联机分析挖掘方法研究 3 人们的广泛关注，出现了一些早期的应用，如r a y t h e o n 公司于1 9 7 3 年推出了 “r a y t a g ”，r c a 公司的r i c h a r dk l e n s c h 于1 9 7 5 年开发了“电子识别系统 等。 8 0 年代，r f i d 技术全面开花，在不同地域和应用方向上焕发生机，如交通管理、 人员控制、动物管理等，挪威在1 9 8 7 年建成了全球第一个商业化公路电子收费系 统。9 0 年代，电子收费系统大规模应用，r f i d 技术标准化问题日趋得到重视。2 0 0 0 年以后，r f i d 产品种类更加丰富，有源电子标签、无源电子标签及半无源电子标 签均得到发展，电子标签成本不断降低，规模应用行业扩大。供应链管理是r f i d 应用的又一新的应用领域，主要用于对供应链中移动物品进行跟踪。该应用的关 键在于，如何组织阅读器产生的大量原始数据以便能够快速响应用户的查询操作， 以及如何从海量物品移动信息中，快速准确地发现物品的移动趋势，为用户正确 决策提供强有力的保障。 目前r f i d 技术的研究主要集中在一下几个方面：( 1 ) 对r f i d 硬件的研究 1 3 q7 1 ，包括不同频率的阅读器、标签和天线的设计制造；( 2 ) r f i d 系统的私密性 和安全性1 8 趣l ；( 3 ) 对不同标准【2 3 之7 1 下的r f i d 数据采集、过滤、组织以及响应标 签查询的软件结构；( 4 ) 对r f i d 噪声数据的清理1 2 8 - 3 1 ；( 5 ) 关于r f i d 数据流的 事件处理【3 2 。3 6 】；( 6 ) 对海量r f i d 数据集的存储、数据仓库以及数据挖掘【3 7 。4 1 1 。 1 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 是继p c 、 互联网和无线通信之后的第四次信息技术革命。r f i d 技术在长时间以来一直是国 际学术界与工业界的重点研究研发对象。 基本的r f i d 系统由三部分组成：( 1 ) 标签( t a g ) ：由耦合元件及芯片组成， 每个标签具有唯一的电子编码1 4 2 ( 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 ) 在标签和阅读器间传递射频信号。 扬卅大学硕士学位论文 图1 1 r f i d 标签 刚1 2 r f i d i 列读器 射频识别技术是一项利用射频信号通过空间耦合( 交变磁场或电磁场) 实现无接触信息传递并通过所传递的信息达到识别目的的技术。其工作原理 比较简单：标签进入阅读器磁场后，接收阅读器发出的射频信号；标签可以返回 或者发射自己的e p c ；阅读器读取e p c 编码，传送到信息系统进行相关的数据处 理。目前r f i d 产品的工作频率有低频、高频和超高频三种，新型的标签中也可以 存储e p c 编码以外的其他信息，阅读器可以同时读出自身磁场范围内的多个标签 的e p c 数据，有些阅读器甚至还可以实现向标签写数据、给标签内数据加密等功 能。 有伟：基于r f i o 数据的若干联机分析挖掘方法研究 、一f ； ：i ； 簟； _ i w j 嘣晒i s e 谟产婶铸学肖掺鼍冀脯 图1 3 应用丁_ 供应链管理的r f i d 系统示例 i l f i d 数据与传统关系数据及其它数据流相比，具有以下特征： 1 ) 原始数据结构简单 原始r f i d 数据记录形如( e p e l o c a t i o n ，t i m e ) ，其结构简单，组成元素的语义 明确。其中，e p c 为附着在物品上的标签的电子产品编码；l o c a t i o n 为本次读取发 生的地点，即阅读器所在地点；l i m e 为本次读取发生的时间。 2 ) 时态性和空间性 r f i d 相关数据会随时问和空问而不断变化，例如动态采集所产生的观察数据 中，带有状态改变的信息，物品的地点及物品之间的关系也会髓着时间而变化。 同时，在实际应用中阅读器和附有标签的物品都可能是处于运动状态。 3 ) 数据不准确性 r f i d 阅读器在工作过程中，经常会由丁环境影响、噪卢_ t 扰等因素而造成错 误多读或者错误漏读等问题，这要求在将这些数据传递给下一个更高级别处理或 业务应用之前，需要进行数据清理。 4 ) 连续流产牛海量数据【4 ” r f i d 阅读器在每一个时问间隔内读取在其读取范围内的所有物品的e p c ，若 某物品停留在一个位置不动，阅读器将会一直读取该物品的信息，然后插入数据 库中，一个中等规模的r f l d 应用每天将产生l o 亿字节数量级的r f i d 数据。 eosa _ - _ _ _ _ 陆 ， 岍石 里型 6 扬州大学硕士学位论文 5 ) 粒度 r f i d 数据集中时间、空间地点、其他物品描述等都可能包含粒度层次的意义， 这与r f i d 系统的实际应用有关。 6 ) 并发与分布【4 4 ，4 5 】 限于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 数据以便用户能够快速高效地对其进行分析。 r f i d 数据与传统的关系数据的最大区别在于r f i d 数据包含路径信息，而路 径信息是无法利用传统数据库技术进行分析处理的。这就要求我们设计专门的方 法，对路径数据进行处理，在路径数据中挖掘有用的知识，充分发挥r f i d 技术对 移动物品跟踪的优势。 1 3 论文的主要工作 在论文中，首先介绍r f i d 数据的相关概念和特点，比较其与传统关系数据库 的区别，将原始r f i d 数据表示为精简的压缩形式。在借鉴国内外数据仓库与o l a p 技术的研究成果，提出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 数据的时间维、地点维以及某些非路径维都有多 个概念层次，产生的立方体规模( 即立方体单元c u b o i d 的数量) 随着数据维度和 各维的层数急剧增长( 立方体规模与维数呈指数增长，与各维的层数呈正比增长) ， 使得在实际应用中不能够完全物化所有立方体单元。同时，具体的r f i d 应用系统 中，原始数据的粒度最细，而通常用户查询所涉及的各维的粒度相对较高，这是 选择立方体单元物化原则的重要依据。现有的数据立方体1 4 6 , 4 7 的研究主要集中在 立方体压缩【4 8 - 5 、立方体物化【5 2 】、异常发现例等；而将立方体技术引入r f i d 数 据管理的研究主要有立方体的仓储与分析 3 9 , 4 0 、流立方体( f l o w c u b e ) 1 3 7 】、基于 移动图( m o v e m e n tg r a p h ) 的立方体【5 4 】等。本文以现有的这些方法为基础，提出一 种新的r f i d 立方体构建方法，在限制立方体物化规模的基础上尽可能地提高查询 响应速度。 2 ) r f i d 立方体中异常数据。r f i d 数据集中，除了大多数的j 下常数据，还有 由于各种原因引起的异常数据。在具体的r f i d 应用系统中，用户不仅对j 下常的数 据感兴趣，有时也需要了解异常数据信息，用来辅助决策。如在零售系统中，销 售量异常高的商品可能是时新或促销商品，销售量异常低的商品可能摆放的位置 偏僻或者临近保质期等。在数据立方体内发现异常，目前的研究主要有基于部分 物化的异常发现【5 5 】和完全物化的异常发现【5 6 】。本文借鉴已有的立方体内发现异常 的方法，在新构建的r f i d 立方体基础上，提出r f i d 立方体内异常发现算法，解 决r f i d 异常数据问题。 3 ) r f i d 数据管理的进一步研究是数据分析，主要分析对象是路径信息。在 实际应用中，移动物品的跟踪就是记录该物品在整个系统中的所有状态，将这些 记录按时间先后排序即可分析物品的移动路径。路径由路径段组成，若将路径段 作为元素，则路径即可看做序列来处理。路径序列包含时间序列和位置序列，压 缩表示后的时间序列可能仅仅是一个数量值，不再具备时间的先后性质，因此很 多时候位置序列的重要性对决策制定更有意义。现有的序列模式挖掘算法 5 7 , 5 8 1 分 为三大类：基于a p r i o r i 的改进算法，如g s p 5 9 1 、s p a d e t 6 0 i 等；基于模式增长的算 法，如f r e e s p a n 6 1 1 、p r e f i x s p a n 6 2 】等；基于位图表示的算法，如s p a m 6 3 1 、i - s p a m 6 4 1 、 l a p i n s p a m 6 ”、l a p i n 硎、h v s m 6 7 】等。本文以这些方法的基础，提出了( 单 层) 位置序列挖掘算法，挖掘无概念层次的r f i d 数据集中的频繁位置序列。 4 ) r f i d 数据集中地点维具有多概念层次的自然特征。实际的r f i d 应用系统 覆盖范围很广，而单一的阅读器侦测范围较小，此时系统必须对地点维划分概念 层次，系统覆盖范围越大概念层次越多，如“国家省份城市县区等。同时系 8 扬州大学硕十学位论文 统用户的权限也各不相同，不同用户感兴趣的概念层次也不尽相同，如省级负责 人可能关心“城市”的层次，而市级负责人可能关心“县区”或更进一步的“乡 镇 层次。这要求在分析r f i d 位置序列时，需要分析不同层次的位置序列。现有 的多层位置序列挖掘 6 8 , 6 9 1 算法主要有h y p e l 7 0 l ，f m s m l 7 1 】，f p m b 【7 2 】，f p m t 【7 2 1 ， d c f m s m 7 3 】等。本文在这些方法的基础上，提出多层r f i d 位置序列挖掘方法， 挖掘满足不同用户需求的多层频繁位置序列。 1 4 论文组织 本文后续章节内容组织如下： 第二章主要介绍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 数据的若干联机分析挖掘方法研究 9 第二章基本理论 本章首先介绍传统的关系数据库的局限性，以及r f i d 数据区别于传统的关系 数据的特殊性；接着介绍数据仓库与o l a p 的相关知识，以及构建r f i d 数据立方 体的大体思路；再介绍线性回归的基本理论，以及基于回归的在r f i d 立方体内发 现异常的方法；最后介绍频繁位置序列以及多层频繁位置序列的挖掘方法。 2 1 关系数据库的局限 传统的关系数据库 7 4 1 ( 简称r d b ) 是由形如 的元组所 组成的记录集合。其中，( 口l ，) 是m 个属性维的属性值，如( 张三，3 0 ，教师) 分别表示属性维姓名、年龄、职业的属性值，a ，c a f u ) ，a f 表示该属性的取值范 围，“ 表示任意值，i = 1 ，2 ，刀；( m l ，m o 表示k 个度量值，如度量值( 5 ，6 3 0 0 0 ) 表示工作年限5 年、年薪6 3 0 0 0 元。关系数据库管理系统( 简称i m b m s ) 的局限 主要表现在以下4 个方面，使其不再适用于r f i d 数据的管理： 1 ) 有限的数据类型 r d b m s 所能支持的数据类型限于系统自身所定义的有限几种基本数据类型， 如字符类型、整数类型、时间类型等。而r f i d 应用中的路径数据由多种数据类型 复合表示，无法由r d b m s 支持的数据类型直接表示。 2 ) 缺少类似于o l d 的标识符 o l d ( o b j e c ti d e n t i f i e r ) 是由系统生成的、不依赖于属性值的、全系统惟一的 对象标识符。o l d 可以用来代替对象本身被访问，甚至可以区别两个属性值完全 相同的对象。实际供应链中有许多物品的属性值完全相同、路径数据不同( 即相 同物品的移动路径不同) ，r d b m s 将无法区别这些物品。若使用e p c 编码作为系 统的o l d ，就能够避免上述问题。 3 ) 不支持自定义的函数或运算 一般的r d b m s 只支持常用的算术、逻辑、字符串、位串、时间等的运算和 一些比较运算以及少许聚集函数，若需要进行其他运算或聚集函数，只能用户自 己编写程序实现。r f i d 数据库中最重要的运算是路径数据的聚集、分类、合并等 运算，r d b m s 并不支持。 l o 扬州大学硕士学位论文 4 ) 不能清晰表示和有效处理复杂对象 r d b m s 的属性必须是原子的，而在实际应用中，常常有属性是非原子的，即 属性是由某些类型构造而成。供应链管理中，某些物品是由多个含有不同标签的 零件组成，如个人计算机，本身具有标签，其内部的主板、c p u 、内存等也都有 各自不同的标签。对于这种情况的处理，r d b m s 会很复杂，需要多个表来记录。 2 2r fld 数据的特点 r f i d 应用系统中，阅读器工作方式为每隔一定的时间间隔自动扫描自身侦测 范围内所有帖标签的物品。物品上附有的标签能够自动应答阅读器的探测，将自 身包含的e p c 信息发送给阅读器。阅读器将在每一次扫描中为每个应答标签产生 一条形如( e p c ，l o c a t i o n ，t i m e ) 的记录，其中e p c 表示该标签的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 ，t i m e ) 的记录，直到物品离开。通常将这些记录压缩为一条形j 啦i ( e p c ，l o c a t i o n ，t i m ei n , t i m eo u t ) 的记录，其中t i m ei n 表示该物品进入该阅读器作用范围的时间，t i m eo u t 表示该物品离开阅读器作用范围的时间。如果不考虑具体的时间点，可以将记录 ( e p c ，l o c a t i o n ，t i m e 玩t i m eo u t ) 压缩表示为