（管理科学与工程专业论文）联机分析挖掘技术及其在现代物流管理中的应用研究.pdf

摘要 无线射频识别( r f i d ) 的应用已经在物品跟踪和供应链管理系统中发挥重要作用。 r f i d 系统中每个独立物品在不同位置移动将会留下一条数据痕迹，将产生巨大的海量 数据。联机分析挖掘( o l a m ) 可以在海量数据上进行即时( a dh o c ) 的复杂聚集查询， 及时向用户提供分析数据，用以辅助决策。这种使用方式对查询响应速度提出了很高的 要求，使得提高o l a m 查询和分析操作效率成为数据仓库应用中的关键问题之一。 本文着重对基于r f i d 的现代物流数据仓库、基于层次编码的r f i d 数据压缩存储 技术、现代物流的分布式序列模式挖掘、基于路径编码的频繁路径挖掘等物流数据仓库 和数据联机分析挖掘技术进行了系统深入的研究。本文的主要研究工作及其所取得的创 造性成果有： 1 ) 提出了一种新型的r f i d 数据仓库模型以建立物流数据立方体，在多维空间中有 效地灵活地进行高层次分析。这一数据仓库模型为分析r f i d 应用中产生的路径提供了有 效工具，容易在不同粒度层次发现物品迁移的趋势。 2 ) 提出了基于层次编码的一种新型预分组聚集算法d h e g a ( g r o u p i n ga g g r e g a t i o n b a s e do nt h ed i m e n s i o nh i e r a r c h i c a le n c o d i n g ) 。利用层次编码技术来生成基于r f i d 的 物品e p c 位图层次编码，采用基于b + 树的维层次树对这些e p c 位图编码结构进行快 速有效地存取，以此进行有效的零售商店货架分析、物品退回和资产管理等基于r f i d 的物品追踪应用。d h e g a 算法充分利用了长度较小的维层次编码及其前缀来快速检索 出与查询关键字相匹配的维层次编码，求得维层次属性的查询范围，减少了i o 开销， 提高了o l a p 查询效率。 3 ) 提出了一种基于分布式环境下的快速挖掘全局序列模式算法d m g s p 。d m g s p 算法将分布式环境下的各站点得到的局部序列模式压缩到一种语法序列树上，避免了重 复的序列前缀传输。采用合并树中结点序列规则和项序扩展策略，对非频繁序列进行剪 枝，有效地约简了候选序列，减少了网络传输量，从而快速生成全局序列模式。并结合 现代物流管理实际进行了基于路径序列挖掘的货物流向分析。 4 ) 在路径编码的基础上，提出了p i d g s p 和p i d p r e f i x s p a n 两种基于路径编码的 频繁路径挖掘算法，通过挖掘频繁路径编码来挖掘频繁路径，可以有效降低存储空间大 小，提高挖掘算法的速度，并有效地挖掘记录移动物品的数据立方体中的频繁路径信息。 关键词：联机分析挖掘；现代物流；d h e g a 聚集算法；序列模式挖掘；频繁路径挖掘 a b s t r a c t t h ea p p l i c a t i o n so fr 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 ) a r es e tt op l a ya l le s s e n t i a l r o l ei no b j e c tt r a c k i n ga n ds u p p l yc h a i nm a n a g e m e n ts y s t e m s t h ev o l u m eo fi n f o r m a t i o n g e n e r a t e db ys u c hs y s t e m sc a nb ee n o r m o u sa se a c hi n d i v i d u a li t e mw i l ll e a v eat r a i lo fd a t a a si jm o v e st h r o u g hd i f f e r e n tl o c a t i o n s o n l i n ea n a l y t i c a lm i n i n g ( o l a m ) q u e r i e sa r ea dh o e ， c o m p l e xa g g r e g a t i o nq u e r i e so nt h em a s s i v ed a t as e t o l a mq u e r i e sa r ec o m p l e xa n dv o l u m e o fd a t ai n l a r g es u c ht h a tt h e ym a k eq u e r yr e s p o n s et i m ea n da n a l y t i c a le f f i c i e n c ya s i m p o r t a n ti s s u e si nd a t aw a r e h o u s e t h ee f f i c i e n tm o d e ml o g i s t i cd a t aw a r e h o u s i n ga n do n l i n ea n a l y t i c a lm i n i n gh a v eb e e n f o c u s e d ，i n c l u d i n gm o d e ml o g i s t i cd a t aw a r e h o u s eo fr f i dd a t a , d a t ac o m p r e s s i n g t e c h n o l o g yb a s e do nh i e r a r c h i c a le n c o d i n g ，d i s t r i b u t e dm i n i n go fg l o b a ls e q u e n t i a lp a t t e r n , a n dm i n i n gf r e q u e n c yp a t ha l g o r i t h m sb a s eo np a t he n c o d i n gp i d t h em a i nc o n t r i b u t i o n sa n d i 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 sf o l l o w s ： 1 ) an o v e lm o d e lf o rw a r e h o u s i n gr f i dd a t ai sp r o p o s e d i tc a nc o n s t r u c tal o g i s t i c c u b et h a ta l l o w s h i g h - l e v e la n a l y s i s t ob e p e r f o r m e de f f i c i e n t l y a n d f l e x i b l y i n m u l t i d i m e n s i o n a ls p a c e i ti sav e r yu s e f u lt o o li np r o v i d i n gg u i d a n c et ou s e r si nt h e i ra n a l y s i s p r o c e s s t h el o g i s t i cc u b ei sd a t ac u b em o d e lu s e f u li na n a l y z i n gi t e mf l o w si na l lr f i d a p p l i c a t i o n i tf a c i l i t a t e st h ed i s c o v e r yo ft r e n d si nt h em o v e m e n to fi t e m sa td i f f e r e n t 2 ) an o v e lg r o u p i n ga g g r e g a t i o na l g o r i t h m d h e g a ( g r o u p i n ga g g r e g a t i o nb a s e do n t h ed i m e n s i o nh i e r a r c h i c a le n c o d i n g ) i sp r o p o s e d b yu s i n gt h o s ed i m e n s i o nh i e r a r c h i c a l e n c o d i n g ，w ec a ng e n e r a t et h eb i t m a ph i e r a r c h i c a le n c o d i n gf o ri t e me p ca n dc a nr a p i d l y r e t r i e v et h ee p ce n c o d i n gb yu s i n gt h ed i m e n s i o nh i e r a r c h i c a lt r e eb a s e do nb + 一t r e e s ow e c a l lt r a c kt h ei t e mb a s e do nr f i ds u c ha ss h e l fa n a l y t i c si nar e t a i ls t o r e ，i t e mr e t u r n sa n d a s s e tm a n a g e m e n t d h e g au t i l i z e st h ef a i r l ys h o r td i m e n s i o nh i e r a r c h i c a le n c o d i n ga n di t s h i e r a r c h i c a lp r e f i xp a t h ，r e t r i e v e st h em a t c h i n gd i m e n s i o nh i e r a r c h i c a le n c o d i n ga n de v a l u a t e s t h es e to fq u e r yr a n g e sf o re a c hd i m e n s i o nr a p i d l y a sar e s u l t ，o u ra l g o r i t h ms i g n i f i c a n t l y r e d u c e st h ed i s ki o sa n di m p r o v e st h ee f f i c i e n c yo fo l a p q u e r i e s 3 ) a ne f f i c i e n ta l g o r i t h m d m g s p ( d i s t r i b u t e dm i n i n go fg l o b a ls e q u e n t i a lp a t t e r n ) o f m i n i n gg l o b a ls e q u e n t i a lp a a e mo nd i s t r i b u t e ds y s t e mi sp r o p o s e d d m g s pa l g o r i t h m c o m p r e s s e sl o c a lf r e q u e n ts e q u e n t i a lp a t t e r n si n t oal e x i c o g r a p h i cs e q u e n c et r e e ，a n da v o i d s t r a n s l m i o no fr e p e a t e dp r e f i x e s b yu s i n gt h es e q u e n c e sr e g u l a ro fm e r g e dt r e e sa n de f f i c i e n t i t e ma n ds e q u e n c ee x t e n s i o np r u n i n g ，n o n - f r e q u e n ts u b s e q u e n c ei sp r u n ea n dc a n d i d a t e s e q u e n c e sr e d u c ee f f e c t u a l l y t h e r e f o r e ，c o m m u n i c a t i o no v e r h e a di sr e d u c e d ，a n dg l o b a l s e q u e n t i a lp a t t e r n sa r ee f f e c t i v e l yg e n e r a t e d w ec a na n a l y s i st h et r e n do fp r o d u c tf l o wb a s e d o nt h ep a t hs e q u e n c em i n i n ga c c o r d i n gt ot h ef a c to ft h em o d e ml o g i s t i cm a n a g e m e n t 4 ) t w oe f f i c i e n tm i n i n gf r e q u e n c yp a t ha l g o r i t h m s - p i d - g s pa n dp i d p r e f i x s p a nb a s eo n p a t he n c o d i n gp i da r ep r o p o s e d b yu s i n gm i n i n gf r e q u e n c yp i d ，w ec a nm i n ef r e q u e n c yp a t h ， d e c r e a s et h es t o r a g es p a c e ，a n di n c r e a s et h es p e e do fm i n i n ga l g o r i t h m t h i sm e t h o dc a nb e u s e di nm i n i n gf r e q u e n c yp a t hi nt h ec u b ew h i c hu s e di nm o v i n go b j e c t sa p p l i c a t i o n s k e y w o r d s ：o n l i n ea n a l y t i c a lm i n i n g ；m o d e ml o g i s t i cm a n a g e m e n t ；d h e g aa g g r e g a t i o n a l g o r i t h m ；s e q u e n t i a lp a t t e r n sm i n i n g ；m i n i n gf r e q u e n c yp a t h 表格索引 表2 1 未清理的原始r f i d 记录1 2 表2 2 清理后的r f i d 数据库1 3 表2 32 0 0 5 年各部门各季度销售数据 表2 42 0 0 5 年各部门销售数据。 表2 5 按时间旋转前的多维数据 表2 6 按时间旋转后的多维数据 1 9 1 9 1 9 ：! o 表4 1 简单位图索引4 7 表4 2 编码位图索引 表4 3 时间维各层次编码及其编码表 4 8 表4 4 物品e p c 编码表一5 3 表4 5 物品库存目录表。 表4 6 物品库存目录层次编码表5 4 表4 7 货架物品目录表s h e l f _ i n v e n t o r y 5 8 表4 8 货架物品目录表d e p t _ l n v e n t o r y 表4 9 图书目录表p r o p e r y _ i n v e n t o r y 表5 1 物流活动数据库f 表5 2 路径序列数据库d 表5 3 候选1 序列c ，l 。 表5 4 频繁1 序列l i 。 表5 5 过度候选2 序列c ，2 = 表5 6 候选2 序列c 2 表5 7 频繁2 序列l 2 。 表5 8 过度候选3 序列c ， 表5 9 候选3 序列c 3 。 表6 1 s t a g e 表。 5 9 7 4 7 4 。7 5 7 6 。7 6 7 6 。7 6 8 0 表6 2 e p c _ p i d 表 。8 0 表6 3 聚集后的路径编码数据库二k 8 2 表6 4 表6 5 表6 6 表6 7 表6 8 1 - s t a g ep r o b a b i l i t y 8 3 s t a g e _ p r o b a b i l i t y 的后3 个子表 求编码长度为1 的频繁路径编码的过程。8 4 编码长度为1 的频繁路径编码前缀及其频繁路径编码后缀数据库。8 5 编码长度为2 的频繁路径编码前缀及其频繁路径编码后缀数据库。8 6 i i 图2 1 图2 2 图2 3 图2 - 4 图2 5 图2 - 6 图2 7 图2 8 图2 - 9 图3 1 图3 2 图3 - 3 图3 4 图3 5 图3 - 6 图3 7 图4 - 1 图4 2 图4 - 3 图4 - 4 图4 5 图4 石 图5 - 1 图5 - 2 图5 - 3 图5 - 4 插图索引 基于r f i d 的现代物流系统l o r f i d 数据管理系统结构。 星形模式： 雪花模式 数据立方体( d a t ac u b e ) 1 7 在数据仓库中进行的数据挖掘。 层次概念树。o 。2 5 数据挖掘主要过程 一个集成的o l a m 结构 r f i d 系统的动态关系e r 模型 r f i d 系统的d r e r 图。3 5 基于p a t h 的路径图。 r f i d 数据仓库存储模式 一个物品视图事例 一条路径视图事例 一条路径行程的地点维的概念层次。 3 7 带有层次编码的星形模式。 时间维层次树。 ：1 9 e p c 层次编码的b + 树存储结构 层次编码与简单位图索引的压缩性能。 层次编码与整数编码的压缩性能比较。 d h e g a 算法查询性能 5 1 。5 3 语法序列树及其合并树。 不同平均序列长度i c i t 的算法运行时间 不同最小支持度下的算法运行时间 不同序列数i d l 下的算法运行时间 6 l 6 l 6 2 7 0 7 2 l i i 图6 1 图6 - 2 存储空间比较。 运行时间比较。 8 6 i v 8 7 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意。 研究生签 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名 签名： 第一章绪论 1 1 选题依据 第一章绪论 当今的物流管理技术，不仅是企业战略的“物流 ，而且是向整个社会实现物资供 给的“社会物流”，进而在全球化市场的激烈竞争中形成多元化网络所必需的“全球物 流”。物流是继“降低资源消耗 和“提高劳动生产率 两大利润源泉之后的“第三利 润源泉 ，它是经营实体组成的网络中控制的关键，这个网络负责把原材料转化成产品， 并且把这些产品送到顾客手中。 但是目前的物流管理水平还处于完成货物仓储、配送运输阶段，尽管利用网络传输 信息，但面对大量的数据信息，知识挖掘运用尚欠缺。其它地区和部门的垄断和地域间 的阻隔，使得企业只盯着眼前利益，信息反馈滞后，各环节管理困难，相互推诿，即使 有的部门使用计算机也只是实现数据的录入、查询、统计等基本功能，无法发现隐藏在 数据背后的知识，表现为“数据爆炸但知识贫乏”，企业的决策者只能依据一些滞后的 数据来了解、监控和调整市场供求状况，不能为企业的决策系统提供支持，各部门、各 系统之间缺乏统一的规划和协调，导致整个物流系统相互隔离、结构各异。企业的决策 者很难对数据进行复杂分析处理，更谈不上实时处理。所有这些情况都给现代物流企业 集团的管理提出了新的要求。现代企业内部需要利用最先进的信息技术、最好的物流管 理方法、最少的库存和最优的调度等运行机制，来建立现代物流系统。 现代物流系统是从供应、采购、生产、运输、仓储、销售到消费的供应链，它涉及 人、财、物、事四大要素，其中，“人 是指物流各环节的操作人员，如生产商、运输 商、销售商、消费者等，操作者信息、角色设置和权限控制是关键；“财是指各环节 之间的资金往来，r f i d 系统与财务系统、e d i 集成，物品价格和成本控制是关键；“物 是指供应链中的物品及物质资源的流动，物品信息和时空特性( 时问、地点) 是关键。 如物品的生产日期、保质期、入库时间、售出时间等，物品的产地、供应地和接收地等； “事指物流环节的业务活动，如生产、销售、仓储、配送、消费等，跟踪信息、资源 优化和协同处理是关键。随着全球经济一体化进程的推进，调度、管理和平衡供应链各 环节( 跨区、跨国) 之间的资源变得日益迫切，以产品电子代码( e p c 码) 和无线射频 东南大学博士学位论文 识别( r f i d ) 为核心在互联网之上构造“物联网”，将在全球范围从根本上改变对产 品生产、运输、仓储、销售各环节物品流动监控和动态协调的管理水平。 另外，现代物流管理决策的关键技术联机分析与数据挖掘技术营运而生。正如 p i a t e t s k y s h a p i r og 等人提出的数据挖掘的定义：是一个利用各种分析工具从大量的、 不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的，人们事先 不知道的，但又是潜在有用的信息和知识的过程。从物流角度来看数据挖掘是一种新的 物流信息处理技术，其主要特点是对物流企业中的大量业务数据进行抽取、转换、分析 和其他模型化处理，从中提取辅助物流决策的关键性数据。因此，从物流业领域来看数 据挖掘可描述为：按企业既定业务目标，对大量数据进行探索和分析，揭示隐藏的、未 知的或者验证已知的规律性，并进一步将其模型化的先进有效的方法。数据挖掘技术利 用人工智能( a i ) 和统计分析等技术，常用的方法有传统统计方法，如抽样技术、多元 统计分析、统计预测方法、时间序列分析等，其中关联规则挖掘算法、序列模式发现算 法、决策树、神经网络、可视化技术等在数据挖掘中经常使用。因此在物流管理系统中 使用数据挖掘技术能够在海量数据中发现模型和数据间关系，自动地帮助决策者分析历 史数据及当前数据，做出归纳性的推理，从中挖掘出潜在的模式预测客户的行为，帮助 企业的决策者调整市场策略，减少风险，做出正确的决策。 本论文结合国家自然科学基金项目网络环境下电子类产品逆向物流系统结构 的研究( 编号：7 0 4 7 2 0 3 3 ) 、江苏省科技发展计划江苏省半导体照明工程技术研究 中心( 编号：b m 2 0 0 6 8 2 4 ) 等课题，结合现代物流管理，着重在基于r f i d 的数据仓库 技术、基于层次编码的r f i d 数据压缩存储技术、现代物流分布式序列模式挖掘和频繁 序列挖掘等主要技术进行深入地研究。 1 2 国内外研究现状 1 2 1 基于r f i d 的现代物流技术 r f i d ( 无线射频识别) 1 1 , 2 1 技术利用射频波在阅读器和可移动标签物品之间传输数 据，因此它能创造一个物理相连的世界，其中每一个对象进行编号、编目，并进行跟踪。 r f i d 是自动的、快速的，而且不需要连接阅读器和贴有标签的物品。 r f i d 最早发明于1 9 4 8 年，并首先应用于第二次世界大战。当时飞机上安装着r f i d 标签和阅读器，通过发送和接受无线射频信号来分辨敌我双方飞机。2 0 世纪5 0 年代， 2 第一章绪论 研究者开始进行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 技术大规模转为民用，并大量应用在动物跟踪管理上【l 】。 从9 0 年代开始，r f i d 正逐步在国防军事【3 1 、邮包跟踪 4 1 、航空工业【5 1 、健康护理【6 】 和机场行李及乘客跟踪【7 l 、供应链管理【8 - 1 2 1 、零售【1 3 】、防伪1 4 1 、安全等领域应用。随 着技术的进步，r f i d 设备的体积越来越小，成本也越来越低，应用领域则更为广泛。 r f i d 的广泛应用将展现“物联网 场景：在这样的一个世界中，数十亿的对象将通过 无线连接报告它们的位置、身份和历史【l6 1 。然而，由带标签的物品组成的巨大网络所创 造的如此庞大的数据量将带来许多亟待解决的数据管理问题和挑战。 在过去的几年内人们已经对零售业方面的话题有着极大的兴趣。大多数领先制造商 声称至少提供一些r f i d 系统。r f i d 可以帮助公司利用r f i d 采集到的实时信息，来更 好地进行物流和供应链管理【1 。7 】： 1 ) 自动控制：r f i d 的最大益处是条形码的自动翻译。实用r f i d 可以节约大量的 劳动力，因为我们不需要实用人力去扫描组织的不同部位。 2 ) 降低存货：供应商的货物供应是基于保存在存货系统中正确的存货信息。然而， 有时存货系统中的数量因为降低或者库存损失而不能反映实际存货中物品的数量。处理 这类问题往往要花费很大的代价，因为常常需要进行人工去盘点统计存货库存数量。 r f i d 技术可以很容易地完成库存数量统计，将大大减少存货统计计算的代价。 3 ) 存货补给：货架存货管理对物流或零售业务来说是至关重要的。经常是商店中 货架上的商品已经脱销了，而仓库中依然还有足够的可用的库存商品。这是因为没有自 动处理机制，即检测外部仓库存货和一旦货架空就重新摆上。用r f i d 技术可以自动跟 踪货架存货。例如，如果一个顾客买的物品使货架上的数量低于最低库存限制时，就立 即发送给商店管理者一条命令要求再补充货架上的商品。 4 ) 物流中库存的可见性：r f i d 技术提供了贯穿整个物流的库存的全面可见性。每 个产品都被贴上标签，所以在业务中移动的物品从供应商仓库到货架过程中都被监视 着。这种全面看待物流使企业降低库存，精简物流，优化劳动力的效率，为他们获得竞 争优势。 射频识别( r f i d ) 技术通过自动识别和捕获数据来大幅度改善业务流程，改变了 现有的商业应用。这一技术对目i j 的数据管理系统提出了许多新的挑战1 8 2 1 1 。r f i d 数 3 东南大学博上学位论文 据是时间相关的、连续变化的、大数据量的，且具有隐性语义的。针对这些数据特点， r f i d 数据管理系统必须能够有效支持这种r f i d 大型数据，且这些系统需要有一个明 确的关于r f i d 数据的时序数据模型，以支持和跟踪查询。h a r r i s o n 等人总结r f i d 数 据的特点，并提供一些r f i d 数据表达的模型中【2 2 2 3 1 ，将r f i d 数据模拟成事件，这隐 藏了状态历史和业务处理的时态语义。且该数据模型不能有效支持复杂查询如r f i d 对 象跟踪和监控。此外，还要能够将原始数据转换成r f i d 应用的目标数据。通过自动数 据采集，r f i d 射频识别技术能达到更好的效果。例如，能更有效地管理整个供应链， 更好地管理存货产品，有效地跟踪和监控产品，降低产品仿冒和盗窃，并且大大地降低 劳动成本等。这些读数信息需要加以自动解释和语义转化，才能成为商业逻辑数据，然 后集成到e r p 和w m s 等企业应用系统中。 国际上成立了一个中立、非盈利的标准化组织e p c g l o b a l 2 4 1 ，主要在全球范围内对 各个行业建立和维护e p c 网络，保证供应链各个环节信息的自动、事实识别采用全球 统一标准。各个大型供应商也提供了r f i d 平台，主要典型的有太阳e p c 网络【2 5 】、s a p 一 自动识别基础设施【2 6 1 、o r a c l e 传感服务器【2 7 1 、i b mw e b s p h e r e 服务器【2 8 1 、s y b a s er f i d 解决方案2 9 1 、微软的r f i d 中间件p o l 。这些平台充当r f i d 物理世界和其他软件基础设 施之间的桥梁。r f i d 数据通过平台获取、过滤和归档，然后到应用。 1 2 2 联机分析挖掘技术 信息技术迅猛发展，特别是网络技术的发展，为物流发展提供了强有力的支撑。物 流管理信息系统是企业信息系统的基础，是企业信息化的基础，利用信息技术对物流中 的各种信息进行实时、集中、统一管理。其中数据仓库技术 3 1 , 3 2 , 3 3 1 是信息技术领域的一 门新技术，其主要特点是面向主题性、集成性、时变性、非易失性。采用数据仓库技术， 可以充分利用企业内部的海量数据，从中挖掘出有价值的规则和知识，使企业能够更好 地认识到数据的价值，并且支持企业决策 3 4 , 3 5 , 3 6 】，将客观详实的数据经验和决策者自身 的宝贵经验结合起来，提高企业的市场竞争力。 物流企业为了降低物流成本，优化物流活动，必须依赖于决策的准确性，而大量数 据是实现决策分析的前提，特别是历史数据。决策的准确性依赖于数据仓库中大量数据 的分析整理【3 ，从中取得有规律性的结论。但是目前我国除了银行、电信、保险等少数 行业，其他行业的数据积累都不够充分。数据仓库是新技术、新概念，国内数据仓库项 目的典型范例还不多【3 8 】。因此，企业领导对数据仓库技术的认可还有一段时间，数据仓 4 第一章绪论 库市场还要进一步培育。对物流管理来说，企业在物流运输管理方面，已经开发的一些 针对具体业务的小型数据库，如仓库管理系统、汽车调度系纠3 9 1 ，物流管理信息系统h o ，4 1 】 等，在一定程度上提高了工作效率，降低了成本。但是这些系统都是小型系统，而且局 限于某一个具体的业务，不能把所获得的单独的数据信息进行整体的分析、宏观的调控， 以供决策者做出正确的决策 4 2 , 4 3 。数据仓库技术的使用可以改变这样的现状。它通过对 大量的历史数据的抽取，净化、集成大量的随机查询，再利用联机分析处理( o l a p ) 阻1 和数据挖掘技术【4 5 】发现数据间隐含的信息，从而辅助决策者进行决策。 联机数据挖掘在庞大的物流数据中所能发现如下的知识：广义型知识，即反映同类 事物共同性质的知识；特征型知识，即反映事物各方面的特征知识；差异型知识，即反 映不同事物之间属性差别的知识；关联型知识，即反映事物之间依赖或关联的知识；预 测型知识，即根据历史的和当前的数据推测未来数据；偏离型知识，即揭示事物偏离常 规的异常现象。在现代物流管理中常用到的数据挖掘技术主要有序列模式发现技术、关 联规则挖掘算法、决策树、分类、聚类等。数据挖掘技术将为企业物流管理决策提供越 来越强大的支持功能，尤其对“第三方物流m 】，。“第三方物流 是指物流服务的供给方 和需求方以外的第三方去提供物流配送业务的运作方式，第三方式专业化的物流企业或 者配送中心，通过提供一套物流活动来服务于供应链。 关联规则挖掘【4 7 , 4 8 1 是现代物流管理【伽中的一个关键的联机分析挖掘技术，用于发现 大量物流数据之间有趣的关联或相关联系，比如根据物流企业上季度的商品销售情况或 者运输工具的数量等等来找出关联规则，“下几个季度可能会有大量的客户需要我们的 物流服务，应该为此准备多少运输能力和仓储能力、分布地点和数量 等类似的问题。 其中规则挖掘一种最有影响的算法是a p r i o r i 5 0 】算法，而后来发展的a p r i o r i 算法的变形， 包括使用h a s h 表提高关联规则挖掘效率刚、选样技术圈等，更是进一步提供了效率。 但a p r i o r i 类的算法有两个较大的缺陷：一是因候选集数目很大，处理候选集代价很高； 二是重复扫描数据库。可以预见如果数据量很大时，a p r i o r i 类似的算法将捉襟见肘。 基于这样的情况，h a nj 等人中提出了不产生候选集f p g r o w t h 5 3 1 算法。f p g r o w t h 算法 大大节省了时间和空问，对大规模数据采用分而治之的办法以避免数据规模巨大难以接 受的情况，它主要通过一种新式紧缩的数据结构f p t r e e 来产生频繁集。通过合适的算 法能够找出物流数据中的关联网，进而生成具有可信度的规则。 序列模式挖掘是现代物流管理中的一个关键的联机分析挖掘技术，对物流管理有着 特别的意义。利用各种序列模式挖掘算法可以找到这些购买序列之间的关系，提供决策 东南大学博士学位论文 者更有意义的数据。进一步地，考虑到供应链成员所关心的数据可以是分层的，那么在 最原始的数据库中对各层次概念进行提升研究则对高层的供应链管理者更有意义。对于 每层上数据挖掘要用到序列模式发现算法，关于序列模式发现问题s f i k a n tr 和a g r a w a l r 对序列规定了时间限制、滑动时间窗口和用户规定的分类，并在该文中总结了序列模 式的定义，提出了一种基于a p f i o d 的改进算法g s p ( g e n e r a l i z e ds e q u e n t i a lp a t t e m s ) 算 法【5 训。以上这些都是基于a p d o d 的水平格式的序列模式挖掘或者与时间相关的频繁模 式挖掘，后来z a k im t 5 5 1 等人提出了一种基于垂直格式存储的序列模式挖掘方法s p a d e 算法，这个算法是由基于垂直格式的频繁项挖掘演化而来。近几年h a nj 和p e ij 等人 又提出了一种基于投影的模式增长的算法f r e e s p a n 算法【5 6 】，这个算法改进后为 p r e f i x s p a n 算法【5 7 】，性能进一步提高。m a n n i l ah 等人提出了挖掘频繁序列片段网的问 题，以及g a r o f a l a k i smn 【5 9 】等人在文中提到的基于规则表达式约束的序列模式挖掘等 等。还有后来关于序列模式挖掘研究的一些扩展，比如序列模式分布式挖掘、多维度序 列模式挖掘和近似序列模式挖掘等等。基于这些序列模式发现算法，采用多层次序列模 式挖掘技术来挖掘物流数据之间的关系，提供决策者有意义的数据。 但是随着无线射频识别( r f i d ) 在现代物流等领域的广泛应用，将产生巨大的海量 数据，需要处理的信息量迅速增加，用传统的数据仓库和数据挖掘技术，不能解决基于 路径的海量数据联机分析处理与挖掘。尽管数据压缩技术在有效减小数据仓库所需的数 据空间和提高数据处理性能方面的作用越来越明显，但是在单处理机上无论采用哪种数 据压缩和优化技术，都不能从根本解决海量数据的存储问题和挖掘问题。为此本文借鉴 国内外在数据联机分析和数据挖掘处理方面的已有成果，对基于r f i d 的现代物流管理系 统海量和路径聚集数据的联机分析挖掘技术进行研究，着重对基于r f i d 的现代物流数据 仓库、基于层次编码的r f i d 数据压缩存储技术、现代物流的分布式序列模式挖掘、基于 路径编码的频繁路径挖掘等r f i d 物流数据仓库和数据联机分析挖掘技术进行了系统深 入地研究。 1 3 主要研究目标 随着现代信息化物流网络体系的应用使原来数据库的规模不断扩大，产生巨大的数 据流。使企业很难对这些数据进行准确、高效的收集和及时处理。为此，使用数据联机 分析挖掘技术能够有效的帮助决策者做出快速、准确的决策，实现对物流过程的控制， 6 第一章绪论 降低整个过程的物流成本。挖掘过程中使用序列模式技术和关联规则技术能反映一个事 件和其他事件之间依赖或关联，找出数据库中隐藏的关联关系，提供有价值的预测和决 策。主要实现以下目标： 1 ) 利用物流信息的特性构建物流数据仓库，对数据进行清理和压缩，利用p a t h 表保 留类似路径的特征。 2 ) 将联机分析挖掘技术运用在物流管理决策中，更好地为领导进行物流与供应链 管理中微观和宏观决策提供支持。 3 ) 使用序列模式挖掘和关联规则挖掘算法来寻找物流数据之间的关系规律，来分 析历史物流数据，预测未来结果。 1 4 本文主要研究内容 第一章，绪论。从现代物流管理技术、无线射频识别( i u i d ) 、数据仓库与数据挖 掘等方面，说明了选题的依据和意义；然后对基于r f i d 的现代物流技术和联机分析挖掘 等技术的国内外研究现状进行了分析；最后，概述了本文的主要研究内容和创新点。 第二章，基本概念。简要地介绍基于无线射频识别技术( r f i d ) 、联机分析处理 ( o l a p ) 以及数据挖掘技术等基本概念与理论。 第三章，基于r f i d 的现代物流数据仓库。随着无线射频识别( r f i d ) 在现代物流 等领域的广泛应用，将产生巨大的海量数据。对基于r f i d 的现代物流系统进行调查分 析，针对r f i d 的数据特点，在传统数据仓库的基础上，我们提出了一种能在提供大量 压缩和基于路径聚集的新型数据仓库结构模式，建立基于r f i d 的现代物流数据仓库， 构造现代物流数据立方体l o g i s t i cc u b e 。接着描述了r f i d 数据仓库中的上卷、下钻、 切片和切块等o l a p 操作，以及与物品移动的路径相关的路径选择等物流多维联机分析 操作。 第四章，基于层次编码的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 的物品e p c 位图层次编码；然后提 出一种基于层次编码的新型预分组聚集算法( d h e g a 算法) ；接着给出基于层次编码 7 东南大学博士学位论文 的零售商店货架分析、产品召回、物品退回和资产管理等基于r f i d 的物品追踪应用的 多维联机分析操作。 第五章，基于现代物流的分布式序列模式挖掘算法d m g s p 。现代物流数据仓库中 存储了海量数据，这样单机系统环境下的序列模式挖掘就不能很好地实现，尤其是在功 能和性能上己不能够满足数据处理能力的需求，这需要通过并行分布式挖掘算法来解决 这一问题。本章在简述序列挖掘基本概念基础上，提出了一种基于分布式环境下的快速 挖掘全局序列模式挖掘算法d m g s p ，将局部序列模式压缩到一种语法序列树上，避免 了前缀的重复出现，而且利用项序扩展剪枝策略有效地约简了候选序列；然后通过算法 实验验证和性能分析证明，随着模式的增长，该剪枝操作越来越有效，d m g s p 算法性 能优越，能够有效的挖掘全局序列模式；最后并结合现代物流管理实际进行