《云计算环境下物流路径数据挖掘研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
云计算环境下物流路径数据挖掘研究DataMiningofLogisticalPathundertheCloudComputing1n●EnVlrOnment2013年4月 合肥工业大学本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕士学位论文质量要求。答辩委员会签名：(工作单位、职称)主席：j；沙中(日哳极乞}翻缸殷委贝[c：zl：书域吴铤兮肥L业大孚酬数枥爱晖导师：铆巴础戈皆引杈掘明∥0 独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得金目曼王些太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签字：何袖襄签字日期：加圬年甲月刁日学位论文版权使用授权书本学位论文作者完全了解金g巴王些太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金月曼王些厶堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文作者签名l何栩烫签字日期：2。7；年十fiJ刁日学位论文作者毕业后去向：工作单位：通讯地址：⋯名：印丑记签字日期．≯f；年。月刁日电话：邮编： 云计算环境下物流路径数据挖掘研究摘要随着企业物流信息化水平不断提高，互联网的普遍运用，产生了海量的物流数据，大量的数据中隐藏着重要的信息。为了提高企业的核心竞争力，给客户提供更优质的物流服务，物流企业需要不断提高决策效率，因此如何从大量的物流数据中获取有价值的信息，辅助企业日常经营活动中的决策，成为企业面临的一个重要问题。通过对物流的路径数据进行数据挖掘分析，发现频繁移动的路径模式，从而获取关于货物流向的知识，预测货物的移动信息，找出异常的移动货物。通过频繁的路径模式，还可以深入了解物品在移动过程中的详细情况，以及这些频繁的路径隐含着的一些移动趋势信息。通过发现的频繁路径模式，可以为企业物流业务经营提供有力的决策支持，从而优化物流环节，从而降低整个物流成本。本文在系统的介绍了数据挖掘、云计算和物流路径相关理论基础上，阐述了物流路径频繁模式挖掘理论知识，并针对物流路径数据特点，采用云计算的MapReduce模型对数据挖掘的序列模式基本算法进行并行化改进，最后用改进的算法对物流路径进行挖掘分析，发现频繁路径模式。在相关研究理论的基础上，本文首先对物流路径频繁模式挖掘进行了相关研究。先阐述了物流路径频繁模式应用，接着，由于物流路径是一种序列数据，参考序列模式的相关定义，定义了物流路径频繁模式挖掘的相关概念，并采用序列模式挖掘算法中的基于Apriori思想的算法发现物流路径频繁模式。接着针对物流路径数据的特点，采用了MapReduce并行计算模型，对序列模式挖掘的基本算法AprioriAll进行改进。由于基于Apriori思想的序列模式挖掘算法对物流路径数据进行分析时，需要多次扫描数据库，并且会产生大量无用的候选序列，当数据量很大时，会占用大量的计算资源。MapReduce是云计算环境的并行计算模型，本文将序列模式挖掘的算进进行并行化改进，使之能适用于MapReduce计算模型。最后将改进的算法用于物流路径频繁模式发现，研究结果表明本文的研究思想是可行的。关键词：物流路径；云计算；数据挖掘；序列模式 DataMiningofLogisticalPathundertheCloudComputingEnvironmentABSTRACTWiththeimprovementoftheenterprise’slogisticsinformationtechnologyandthewidespreaduseoftheInternet，amassivelogisticsdatahasbeenproduced，andthereisimportantinformationhiddeninthedata．Inordertoimprovethecorecompetitivenessandtoprovidecustomerswithmorequalitylogisticsservices，thelogisticsenterpriseneedtoconstantlyimprovetheefficiencyofdecision‘making，SOhowtoobtainvaluableinformationfromalargenumberoflogisticsdatatosupportthedailydecision—makingbecomesanimportantissue·Miningthelogisticspathdatatofindthefrequentlymovingpathpattern，youcangainknowledgeabouttheflowofgoods，predictthemovementinformationofgoodsandidentifyunusualmovinggoods．Withthefrequentpathpattern，youcandeeplyunderstandthedetailinformationabouttheproductsduringthemovementandtheimpliedmovingtrendinformation．Thefoundfrequentpathpatterncanbepowerfultoprovideapowerfuldecisionsupportforenterpriselogisticsbusiness，thentooptimizethelogisticschain，toreducetheoveralllogisticscosts，andtoimprovethecorecompetitivenessforlogisticenterprise．BaseonthesystematicintroductiontoMining，CloudComputingandLogisticspaththeory,thepaperelaboratesthetheoryabouttheminingoflogisticsfrequentpath．Consideringthepathdata’Scharacteristics，anparallelizationofsequentialpatternofMinghasbeengivenbytheuseofCloudComputing‘SMapReducemodel，andtominetheLogisticalpathtofindthefrequentpathpattern．Basedonsomerelevanttheory,thepaperfirstlyresearchestheproblemoflogisticalpath’Sfrequentpattern．Theapplicationoflogisticalpath’Sfrequentpattemisintroducedatthefirst，then，forlogisticalpathisakindofsequentialdata，therelevantdefinitionsoflogisticalpath’Sfrequentpatternaregivenbythereferencetothesequentialpattern，andakindofsequentialpatternminingaIgorithmbasedonAprioriideasisusedtofindthefrequentpatternoflogisticalpath．Secondly,consideringthepathdata’Scharacteristics，anparallelizationimprovementofAprioriAll，whichisthefundamentalalgorithmofsequentialpattern，isgivenbyadoptingtheCloudComputing‘SMapReducemodel．ItneedsIl toscanthedatabasemanytimesusealgorithmbasedonAprioriAllanalysisthelogisticalpathdata，andalotofunusefulcandidateSequencesareproduced，SOwhenrequireddealwithalargeamountofdate．itwilltakeupa10tofcomputingresources．MapReduceisaparallelcomputingmodeloftheCloudComputingenvironment，anparallelizationimprovementofsequentialpatternmininghasbeengiven，SOthatitcanapplytheMapReducecomputationmodel．Finally,theimprovedalgorithmisusedfindthelogisticspath’Sfrequentpatternfound，anttheresultsshowsthattheideaiSfeasible．Keywords：logisticalpath；datamining；cloudcomputing；sequentialpatternIII 致谢三年的研究生生活，转瞬即逝。三年来的收获远非文字和语言所能表达的，然而毕业论文毕竟是一种很好的总结。在本文即将完成之际，我衷心的感谢研究生的三年学习生活中给予我帮助的各位老师和同学们。当我完成毕业论文时，最先想到的是，同时也是最想感谢的是我的导师胡小建教授。三年来，胡老师在学业上给予不倦的教诲，论文从选题、构思、查阅文献、修改、定稿，每一步都熔铸着导师的殷切期望和精心指导。胡老师以他求实的科学态度、渊博的学术知识对新领域研究的敏锐性启迪奠定了我的开发思维和工作信心，以他丰富的实践经验、周密细致的工作安排以及在这一领域的造诣，对指导我最终能完成学业起了巨大作用，为我的学业发展创造了良好的条件，提供了广阔的发展空间。使得我对研究方向上的前沿技术有了进一步的了解和认识，最终能够完成毕业论文的写作。在此衷心感谢我的导师胡小建教授!衷心感谢曾经指导过我学业的管理学院学院的各位老师，他们严谨的治学态度，敏锐的思维方式，勤勉的务实开拓进取精神以及对管理学科的热爱，让我更加坚定了作为学生的信心和决心。在此向所有给我授过课和帮助过我的教授、老师们表示我最衷心的感谢。由衷地感谢物流与物联网研究所的各位老师，他们治学严谨、平易近人，在论文写作时给了我最贴切的建议和意见，使我在课题研究中受益匪浅，并感谢他们一直以来对我的勉励。还要感谢我同门的师兄弟们，大家在研究课题时相互交流、相互帮助，塑造了一个良好的学术环境。我们平时的关系也非常融洽，体现了师门情谊，希望以后的师弟师妹们能相处的更好。在学习和工作的研究生生活中，还要感谢寝室里和班级里的其他同学，使他们的热情帮助给我营造了良好的学习科研的氛围和愉快的生活环境，在这里我向他们表示感谢。感谢我的家人和亲戚，是他们在物质上给我帮助，使我能拥有读书的机会，并且一路支持我的选择。感谢默默为我付出、给予我帮助的亲戚朋友们，在我困难的时候总是能得到他们的帮助。感谢评阅本论文的专家学者，感谢你们在百忙之中审阅了本论文并提出建议和指导。作者：铜麴靶日期：乃D7又多少．27IV 目录第一章绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．1研究背景⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．11．2国内外研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．21．2。1数据挖掘技术研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．21．2．2物流路径数据研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯31．2．3云计算研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯41．3主要内容和组织架构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．5第二章相关理论基础⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．62．1数据挖掘理论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．62．1．1数据挖掘概述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯62．1．2数据挖掘分类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯62．1．3数据挖掘步骤⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．72．1．4数据挖掘在物流中的应用⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯72．2物流路径数据理论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．82．2．1物流和物流信息化⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯82．2．2物流路径数据理论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一92．3云计算理论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．112．3．1云计算定义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯112．3．2云计算特点⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯112．3．3云计算体系架构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯122．3．4云计算关键技术⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．142。4本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯15第三章序列模式挖掘基本理论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。163．1序列模式基本原理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯163．2序列模式基本概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯163．3序列模式发现算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯173，4序列模式的应用和发展⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯203．5本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．21第四章物流路径频繁模式挖掘⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯224．1频繁模式挖掘应用⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一224．2频繁路径挖掘⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯234．2．1物流路径相关概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯234．2．2物流路径数据特性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．244．3RFID数据⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯254．4基于Apriori思想的频繁路径模式挖掘⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯26V 4．5本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯29第五章云计算环境下物流路径频繁模式挖掘⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯305．1MapReduce计算模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯305．1．1MapReduce计算模型简介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一305．1．2MapReduce计算模型过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯315．1．3MapReduce处理数据流程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．3l5．2基于MapReduce的序列模式算法改进⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．325．2．1基于MapReduce的AprioriAll算法并行改进⋯⋯⋯⋯⋯⋯⋯325．2．2改进的算法与MapReduce结合⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯335．2．3改进算法优势分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．355．2．4算法在物流路径数据分析应用意义分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯355．3应用实例⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯355．3．11．频繁序列挖掘过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．375．3．22．频繁序列挖掘过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯405．3．33．频繁序列挖掘过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．435．3．4计算结果分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯455．4本章小结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．45第六章结论与展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯466．1结论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．466．2展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯46参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．47攻读硕士学位期间发表的论文⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．51特别声明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯52VI 插图清单图2．1数据挖掘过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．7图2—2云计算的体系⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯12图2．3HDFS体系结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯14图5．1MapReduce处理数据集过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．32VII 表格清单表3．1顾客交易数据库示例⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯16表3．2顾客序列数据库示例⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．16表3．3大项集⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯18表3．4转换后的数据库⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．19表4．1物流活动数据库示例⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯24表4．2路径序列数据库示例⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯24表4．3路径序列数据库⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一26表4．4候选1．序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯26表4．5频繁l一序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一27表4-6转换后的路径数据库⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．27表4．7过度候选2序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯28表4．8频繁2．序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯28表5．1物流活动数据库D⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯36表5．2路径序列数据库PD⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．37表5．3转换后的路径序列数据库PD⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．37表5-4候选1一序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯40表5．5频繁1．序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯40表5-6候选2．序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯43表5．7频繁2．序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．43表5．8候选3序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．45表5-9频繁3．序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．45VIII 第一章绪论1．1研究背景随着物流信息化水平不断提高，物联网技术的不断发展和应用，GIS、GPS和RFID等技术广泛应用于物流行业，产生了海量的物流信息数据，将GIS、GPS和RFID等技术引入物流供应链管理，可以跟踪物流网络中移动物品的运动轨迹，获取物流路径数据。数据挖掘DM(DataMining)，就是借助一系列信息技术对多个大型异构或同构数据库或数据仓库中的数据进行分析，从中获取对人们有用的或者感兴趣的信息和知识，这些信息和知识是隐含的、事先未知、潜在有用的，提取的知识可以用模式、规则、概念和规律等形式进行表示。数据挖掘的目标是从海量的历史数据中获取有用的、感兴趣的信息和知识。这些知识和信息，对于决策具有相当大的潜在价值。利用获取的信息和知识，能够根据已掌握的数据对即将可能发生的行为做出结果预测，从而为企业的经营决策和市场策划等提供决策依据。通过对物流数据进行数据挖掘分析，可以获取潜在的、有用的信息，为物流业务活动提供决策支持。对物流路径数据进行挖掘分析，找出频繁路径信息，获取关于货物流向的知识，用户能够进一步了解货物的移动趋势，预测货物的移动信息，找出异常的移动货物，可以优化物流环节，从而降低整个物流成本，为用户物流业务经营提供有力的决策支持。云计算(CloudComputing)是一种全新的计算模式，利用这种方式，可以有效的整合各类资源，实现软硬件资源和信息的共享，这些资源和信息可以以按需的方式提供给用户、计算机和其他设备。随着信息技术的普遍应用和高速发展，数据呈现以GB、TB再到PB级的方式爆炸增长，这给数据挖掘技术带来了极大的挑战。数据挖掘面临的两个最重要的问题是：一是如何对海量数据进行存储和计算，二是如何快速、高效、低成本的从这些数据中挖掘出新颖的、有潜在价值的信息和知识。云计算的出现为数据挖掘技术的发展带来了机遇。云计算技术通过使存储和计算能力均匀的分布到集群中的多个存储和计算节点上，实现对超大数据集的巨大的存储和计算能力。由于可以使用大量的廉价计算机通过集群来代替价格高昂的服务器，云计算大大的降低了成本。使用云计算技术提供的巨大的存储能力和计算能力，数据挖掘技术进入了基于云计算的数据挖掘时代。本文正是基于上述研究背景，对物流路径数据频繁模式挖掘问题进行系统研究。采用数据挖掘的序列模式挖掘算法对物流路径数据进行频繁模式挖掘，同时借助云计算环境的MapReduce编程模式，针对路径数据特点，研究适合物流路径的频繁模式挖掘问题。 1．2国内外研究现状1．2。1数据挖掘技术研究现状在激烈的市场竞争中，信息对于企业的生存和发展起着愈来愈关键的作用，随着企业信息水平的不断发展和提高，数据库技术的快速发展，企业数据库中存储的数据量随着时间增长和业务扩大不断增加，人们对于数据的需求不仅仅是简单的查询和统计，而是有更进一步的需求，希望从大量的历史数据中发现规则和关系，从而可以用来辅助决策和研究。目前数据库系统无法有效从大量的数据中发现隐含的规律和模式，因此出现了“数据爆炸但知识贫乏”的状况，从而导致了知识发现和数据挖掘技术的出现。数据挖掘，又称数据库中的知识发现(KDD)，是一门从丰富的历史数据中发现其隐含规律的技术，融合了数据库、统计学、人工智能等多门技术。数据挖掘这个词语第一次出现是在第11届国际联合人工智能学术会议(1989年8月)，1995年举行了第一届KDD国际学术会议。然后在多个学科领域(如数据库、知识工程、信息处理和人工智能等)的学术刊物上出现了专门的KDD刊物和专栏⋯。近年来，在GartnerGroup在一次高级技术调查中，数据挖掘和人工智能被列为“未来三到五年内将对工业产生深远影响的五大关键技术”之首，同时，数据挖掘和并行处理体系被列为未来五年内投资焦点的十大新兴技术前两位。最近Gartner的一份HPC研究表明，“随着数据捕获、传输和存储技术的快速发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用更为广阔的并行处理系统来创建新的商业增长点”。目前，国外专家对数据挖掘主要研究方面有：将统计学回归方法运用于数据挖掘；对知识发现方法的进一步研究，如将遗传算法运用到知识发现中；将数据挖掘和数据库紧密结合等。在应用方面主要包括：不断生产和完善数据挖掘商业软件工具，注重系统而不是孤立的解决问题过程。数据挖掘软件用户主要集中在电信公司、保险公司、大型百货公司、大型银行和销售业等。国外许多IT企业都非常注重数据挖掘的开发和应用，成立了数据挖掘研究中心，例如IBM和微软。目前市面上比较常见的数据挖掘软件有SAS公司的EnterpriseMiner，IBM公司的SPSSClementine，SGI公司的SetMiner等。同国外相比，国内对DM的研究较晚，从事DM研究的人员主要分布在研究所、在高校和部分企业。目前，对数据挖掘技术的主要研究方面有：数据挖掘算法优化【21、基于Web的数据挖掘【3】、数据挖掘中的隐私保护[41、目标客户发现【5】、购物篮分析等。此外，随着云计算的不断成熟和广泛应用，基于云计算的数据挖掘成为一个研究热点，主要是数据挖掘算法的并行化问题【6J。因此，未来几十年，不管是从理论研究角度还是从企业实际发展角度来看，数据挖掘毫无疑问将会是学术科研和企业应用领域共同关注的热门焦点。随着2 企业信息化水平的不断提高，数据挖掘理论研究的不断丰富和完善，企业对数据挖掘的需求必将日益增加，数据挖掘技术的应用会愈来愈广泛。1．2．2物流路径数据研究现状传统的物流路径问题是指由Dantzing和Ramser[7J提出的VRP(VehicleRoutingProblem，车辆路径问题)，主要是研究基于一定约束条件下的，多目标优化问题，即在满足一定的约束条件下，为了达到目标最优而选择合适的路径。本文研究的是关于物品在流通过程中的路径问题，这里的物流路径指的是，移动的物品随时间变换而地理位置随之变换形成的运动轨迹，通过先进的信息技术识别和追踪移动物品的位置信息，获取物品的移动路径信息。随着各种先进的数据采集技术(GPS，GIS和RFID技术等)用于对移动的物品进行识别和追踪，为了对这些移动的数据进行管理，提出了移动对象数据库的概念¨J。物品移动路径数据信息获取主要依赖于先进的数据采集技术，由于具有无接触、能穿透非金属介质、识别距离大、精度高以及信息收集处理快捷等优点，RFID(radiofrequencyidentification，无线射频识别)技术作为一种主要的数据采集技术用于识别和跟踪移动物品，以此获取物流路径数据。RFID最早发明于第二次世界大战期间，将RFID标签和阅读器安装在飞机上，用来辨别敌我。从20世纪90年代开始，RFID技术逐渐用于物流供应链管理【9J，通过RFID技术可以识别和跟踪移动的物品，从而可以实时的了解物品在物流的那个节点上，实现供应链的可视化和信息共享，提高物流运作效率。对于物流信息获取问题，文献【101研究了如何用电子标签技术来追踪移动物品的物流路径信息，从而获取移动物品的路径数据。进而文献[11]提出对这些海量的移动路径数据信息进行分析，从而获取物品的移动趋势信息。随着物流信息化水平的不断提高，数据采集技术的发展和更新，产生了大量的数据，这里面就包含了物品的移动路径数据，由于海量的数据中隐含着具有潜在价值的信息，通过采用数据挖掘技术来获取这些信息，可以提高物流管理效率，提升企业竞争力【I2|。对海量的移动物品的路径进行数据分析，常见的挖掘任务有聚类分析、异常检测和序列模式挖掘等。文献【13】针对路径数据的特点，对序列模式挖掘算法GSP进行改进，用于发现频繁物流路径。文献[14】针对现代物流系统提出了一种基于路径数据的频繁封闭路径挖掘算法。文献【l5】在借鉴了DNA序列研究的基础上，对路径数据进行了聚类分析。文献【16】主要研究了路径数据的异常检测问题。 对物品移动路径的挖掘分析，虽然最近几年才开始研究，但是随着物联网技术的不断发展，云计算的技术的不断成熟，必将成为企业界和学术界的一个愈来愈感兴趣的热门研究领域。1．2．3云计算研究现状21世纪初，由于互联网的飞速发展，作为搜索领域的领军企业Google公司搜索量急剧增长，原有的服务器无法满足海量搜索的需求，为此技术天才JeffDean设计出了一种全新的技术架构，一次满足快速增长的搜索需求，由此云计算概念诞生。自Google公司于2007年最早提出云计算的概念，亚马逊于2007年7月第一个发布面向企业服务的云计算应用服务，短短的六年时间，云计算成为许多研究机构和IT厂商的重点发展战略之一，云计算已经由概念转变为大规模应用，成为目前互联网和信息技术领域的一个研究热点。在科学研究领域，来自美国伯克利大学的学者Berkeley迈克．阿姆布鲁斯特在《AbovetheClouds：ABerkeleyViewofCloud》【l7】一文中，概括的阐述了云计算的历史、概念、意义、商业应用和价值、障碍和展望等方面。另外来自美国加州斯坦福大学的学者安迪．贝克托姆尔则从云计算服务提供者和服务客户的角度做了一个类似的简要概述。此外，学术界还举办了针对云计算的研讨会；2009年1月在印度班加罗尔举办了第一届云计算专题研讨会，IBM、甲骨文和SAP实验室等齐聚一堂分享了印度云计算专家的经验【l引。2009年10月在德国慕尼黑举办了首届国际云计算大会，会议主题包含了云计算自动平台、基础设施和云计算应用等方面。2012年10月11日，全球最大的专业技术人员协会电气电子工程师学会，在印度班加罗尔召开了首届IEEE新兴市场云计算大会fIEEECloudComputingforEmergingMarketsConference)t19】。在云计算商业应用和价值方面，许多IT企业都推出了自己的云计划：IBM主要针对企业级云计算市场，于2007年8月提出了“蓝云”计划；Google公司则以互联网的每一个终端用户为自己的客户群，于2007年10月提出了“消费云”计划；亚马逊公司则基于互联网应用软件，提出了“弹性云”计划，既瞄准了企业用户又瞄准了互联网终端的每一个用户。同国外相比，国内对云计算的研究虽然较晚，不过对云计算的研究非常重视，云计算在国内的发展速度飞快，2009年5月22号，在相关政府部门的指导下举办了“首届中国云计算大会"【20】大会，主要探讨了云计算的实质内涵和发展趋势及其对社会发展、教育和产业等带来的影响，分享了云计算的最新研究成果。此外，很多企业都提出了自己的云计算建设方案，IBM在中国无锡建立了国内第一个云计算中心，已经于2008年5月投入使用；阿里巴巴集团旗下子公司阿里软件宣布将筹建多个“电子商务云计算中心”【211，首个云计算中心将于2009年初落户江苏南京；在国内产商中，华为则在2011年第一个发布了4 其云服务“cloud+”[221，华为的could+云月艮务内置在华为的云手机上，主要包含四个组成部分，分别是智慧云、Cloud+网盘、全备份和安全卫士。1．3主要内容和组织架构本文主要研究云计算环境下物流路径数据挖掘算法，就是在云计算MapReduce计算模式下，针对路径数据特点，对序列模式挖掘算法进行一定的改进，使之适用于物流路径频繁模式发现。在总结了前人研究经验的基础上，通过对经典算法的研究，借鉴了云计算的MapReduce计算模式，对序列模式挖掘算法进行了基于MapReduce的并行化改进，最终实现了云计算环境下序列模式挖掘理论在物流频繁路径模式中的应用，本文组织结构安排如下：第一章绪论。主要介绍了研究背景以及国内外研究现状，本文研究内容和组织结构。第二章相关理论基础。为后续内容作铺垫，首先介绍了数据挖掘的基本定义，数据挖掘的分类，数据挖掘的一般步骤和其在物流领域的应用情况；随后介绍了物流数据路径理论，包括物流和物流信息，物流路径数据的表示及其分类，简单介绍了几种路径挖掘任务；最后介绍了云计算的定义、特点、体系结构和关键技术第三章序列模式挖掘基本理论。详细介绍了序列模式的基本原理、概念和发现算法等，在序列模式基本原理介绍中着重强调了序列的顺序和时间属性，这是序列模式理论可以用于分析物流频繁路径的理论基础。第四章物流路径频繁模式挖掘。主要介绍了物流路径的概念，物流路径频繁模式发现算法以及物流路径频繁模式应用情况，重点强调了由于路径实质上是一种序列数据，故可以采用序列模式挖掘的AprioriAll算法用于发现频繁路径，用传统的序列模式算法挖掘路径频繁模式时，会产生大量无用的候选序列，且需要对数据进行多次扫描，因此可以借鉴云计算的MapReduce计算模式进行并行化改进。第五章云计算环境下的物流路径频繁模式挖掘。详细的介绍了云计算的MapReduce计算模型的计算过程和处理数据流程，主要介绍了基于MapReduce的AprioriAll算法的改进，并且用改进的算法对物流路径进行频繁模式分析，研究结果表明本文的研究思想是可行的。第六章结论与展望。首先总结了本课题的主要研究成果，然后对该研究领域中仍然存在的研究方向和内容进行了一定的展望。 第二章相关理论基础2．1数据挖掘理论2．1．1数据挖掘概述数据挖掘(DM，DataMining)，也称“数据库中的知识发现”，指从大量的、不完全的、有噪声的、模糊的、随机的数据中，发现隐含的、先前未知的、有潜在价值的知识的过程。数据挖掘是一门交叉学科，融合了统计学、机器学习、人工智能和数据库等多门学科。随着信息技术的发展，大量的数据能够被记录下来，迫切需要从这些大量的数据中获取有用的信息，数据挖掘作为一种新型的数据分析技术，必将成为未来一段时间内信息技术产业的一个研究重点。2．1．2数据挖掘分类按照数据挖掘功能，分类如下：(1)关联分析：寻找数据子集间的关联关系或者一些数据与其他数据之间的派生关系，最常见的是关联规则挖掘。关联规则挖掘是由Agrawal[23】等人首先提出的，用于发现顾客购买不同商品之间的关系。一个关联规则的例子“85％的顾客购买了打印机和电脑同时会购买内存条’’。(2)分类分析：找出描述和区分数据类或概念的模型(或函数)，以便能够使用模型预测类标号未知的对象【241，即通过对训练数据集进行分析获得一定的分类规则，以此对新的数据集进行分类。常见的分类方法包括决策树、神经网络、贝叶斯网络、支持向量机和粗糙集等。(3)聚类分析：把数据按相似性分成不同类别，类内数据之间的相似性尽量大，不同类的数据间的相似性尽量小。同分类分析不同的是，聚类分析没有目标属性用于指导聚类过程，是一种无监督学习过程。常见的聚类方法有K—means算法等。(4)序列分析：用于发现序列数据库中相对时间或是发生顺序所出现的高频率子序列。序列模式的一个例子是“租客租用了《天龙八部》和《神雕英雄传》很可能在一个月之后租用《神雕侠侣》”。序列模式挖掘可用于DNA分析、Web访问模式分析、天气预报和网络入侵检测等领域。(5)孤立点分析：用于发现异常的事件或行为。孤立点(或离群点)指的是数据集中某些与其他数据行为不一致的数据。孤立点分析主要有两个任务，第一是如何定义孤立点；第二是如何找出数据集中的孤立点。孤立点分析可用于欺骗检测、网络入侵检测等领域。(6)概念描述：概念描述就是概括某类对象的相关特征，用一定的规则对该类对象的内涵进行描述。概念描述主要分为两类描述：区别性描述和特征性描述。区别性描述主要描述不同类之间的区别特性，特征描述主要描述某一类6 对象共有的特征。有多种方法来生成不同类的区别性描述，例如遗传算法、决策树方法等；生成一个类的特征性描述只涉及该类对象中所有对象的共性。2．1．3数据挖掘步骤第一步是数据清洗与集成，数据清洗一般包括消除噪声、推导计算缺值数据、消除重复记录、完成数据类型转换等，其目的是消除噪声和不一致的数据；数据集成是将来自不同数据源中的相关数据进行组合。第二步是数据选择与变换，选择合适的数据来进行分析，其目的是确定发现数据挖掘作对象，即目标数据，它是根据数据挖掘任务从经过数据清理和集成的数据库中抽取的一组数据；数据变换的目的将数据变换或统一成合适形式。第三步是发现模式，选择合适的模型对目标数据集的数据进行挖掘分析，发现模式。第四步是结果评估，对于挖掘分析出的模式，根据一定的评估标准对其进行评估，踢出冗余和无关的规则，某些模式可能与实际不相符或是不能满足用户需求，因此需要返回到前面几个步骤，重新进行数据挖掘。因此数据挖掘的过程是多次迭代的，直到有意义的知识被提取出来。数据预肄理数据选择与变换挖掘分析结果评估i．⋯一一一一一一一一一一．．．⋯．一一一一一一一．．．．．．⋯一一一一一一一一一．．．．．．．!一一一．．．．．．一一．．⋯⋯一一一一一一一．．．一．．一．⋯一一．．．．!⋯．．．．．．．⋯．．．．．．．一一一一一．．．．⋯一一．，童，．⋯一一一一．．一．．．．．图2．1数据挖掘过程2．1．4数据挖掘在物流中的应用目前，物流领域成为数据挖掘技术的非常重要的应用领域。随着条形码技术的广泛应用，RFID技术的不断发展，物流信息化水平的不断提高，物流企业收集和存储了大量关于货物进出历史记录、货物运输记录、货物库存记录和采购记录等物流信息，积累了大量的数据；另一方面，物流企业为了更好得为客户提供优质服务，降低物流成本，需要在平时的物流经营活动中，进行高效的决策。数据挖掘技术的目的是从大量的数据中获取潜在价值的知识，因此采用数据挖掘技术对物流历史数据进行挖掘分析，获取关于配送模式和趋势、运输行为、库存采购等相关知识，可以用于指导改进配送模式、运输路线和库存管理等，从而提高企业核心竞争力。下面简单介绍数据挖掘技术在物流领域的几个应用方面： (1)优化物流配送在物流系统中，物流中心的选址问题是一个非常重要的问题，最优的方案可以使商品在流通的整个环节实现最大效益，选址问题是一个NP难问题【2引，利用数据挖掘中的遗传算法，对其改进，可以较为快速的获取最佳选址中心。此外在进行物流配送时，可以对可户进行分类，然后再针对性的进行路径安排，从而可以提高配送效率。(2)优化库存决策采用数据挖掘技术对运输数据和库存数据进行分析，决定发货顺序，从而保证一定的库存。通过对库存历史数据进行关联规则分析，可以获取某些货物之间的关联规则，从而可以为库存和采购提供依据，对某货物的库存数据进行分析，还可以预测其需求量，从而及时调整库存，降低供应链成本。(3)优化运输决策随着GPS和GIS等技术在运输监控中的应用，存储了大量关于货物运输的信息，对其进行关联分析，可以获取运输货物之间的关联性，即运输某种货物的顾客可能需要运输其他某种货物。利用这些信息，可以构建货物推荐，优化运输配置和货物组合，为客户提供更加优质的服务。(4)市场和趋势分析利用数据挖掘技术对历史物流数据进行分析挖掘，获取客户的运输习惯和货物趋势等其他重要信息。收集一定时间内的存储的物流数据，对季节性货物的运输量和库存趋势等进行挖掘分析，获取其趋势信息，从而为确定风险货物及运输量和库存运作决策提供支持。(5)货物流向分析随着物联网技术的发展，RFID技术的应用，产生了大量关于货物路径的数据。RFID数据包含着关于某种货物的路径数据信息，RFID数据的特点是数据量庞大性和实时性，传统的查询方法难以获取精准信息，因此需要借助数据挖掘技术对其进行分析，获取物品的移动趋势。利用数据挖掘技术中的序列模式挖掘，对物品的移动路径进行分析，可以获取物品的移动趋势信息，获取货物的流向知识，本文正是研究序列模式挖掘在物流路径数据挖掘中的的应用，利用物流路径频繁模式挖掘频繁路径，可以发现某类货物的货物流向情况。2．2物流路径数据理论2．2．1物流和物流信息化对于物流的理论研究始于20世纪初的美国，1916年美国学者Arch．Shaw首次将物流称为PhysicalDistribution。在他的著作《市场流通中的若干问题》中，Arch．Shaw首次阐述了物流在流通领域的作用，书中指出“物资经过时间或空间的转移，会产生附加值’’。当时的物流被理解为“在连接生产和消费间对 物流履行保管、运输、装卸、包装、加工等功能，以及支持控制这些功能的信息功能，它在物资销售中起到桥梁作用”。随着对物流认识的加深，对物流概念的定义也在不断演进，美国物流管理协会(CLM)对物流进行了多次定义，1986年CLM对于物流的定义是“对物品、服务及相关信息，从起源地到消费地的有效率地、有效益地流动和存储，进行计划、执行和控制，以满足顾客要求的过程”，最新一次在2003年，CLM将物流定义修整为“物流是供应链活动的一部分，是对货物、服务及相关信息从起源到消费地的有效率、有效益的正向和反向流动和储存进行的计划、执行和控制、以满足顾客要求"。物流信息是指反映物流各种活动内容中有关的知识、资料、图象、数据、文件的总称【261，物流信息是物流企业在经营物流活动(如包装、运输、存储、包装和装卸等)而产生的，因此精准和及时的物流信息对物流活动的有效控制具有很重要的意义，物流信息业被称为现代物流的神经中枢。物流信息化是通过使用现代信息技术和开发利用信息资源，对供应链各个企业的计划、协调、客户服务和控制活动进行有效的管理【27|。物流信息化包含两层含义：信息成为物流业务中商流、物流和资金流的载体，通过网络技术进行信息传递；通过信息交换实现物流业务的管理，将现代信息技术应用于整个物流领域以实现物流管理的全面信息化。2．2．2物流路径数据理论2．2．2．1路径数据表示在现代物流中，存在着大量移动的物品，通过数据采集技术记录物品的运动轨迹，产生了大量的路径数据信息。为了管理和应用这些数据，有必要研究路径数据的表示方法。(1)基于线段表示为了准确的获取物品移动过程中的路径信息，需要记录移动物品任意时刻的位置，但是在实际应用中，由于服务器和网络等的限制，一般采取隔一段时间定位移动物品的位置信息。基于线段的路径表示指的是，对移动物品的信息进行采样，每隔一定的时间段来获取移动物品的位置和速度等信息，然后再采样点之间采用线性插值的方式来得到对象的完整路径。文献【28】对于这种表示方法做出了如下定义：采用形如MO=(ID，P，f)的数据元组来记录某一移动物品的位置信息，，其中肋是移动物体的唯一标识符，P是标识为仞的物品在t时刻的位置信息，t为移动物品的记录时间。其中P采用二元组表示，P=仁，yJ，x和Y分别表示二维空间里的横纵坐标值。9 路径则表示为一系列采样点的位置信息，即MOP=(MOl，M02⋯．，MOn)，其中n表示采样的个数。在得到移动对象的采样点之后，在采样点之间采用线性插值方法进行连接，则得到对移动物品的完整痕迹。采用这种方法来表示物品的路径数据，和物品的路径数据有一定的误差。(2)基于移动模式串的表示采用基于线段的表示方法，不能准确的记录物品的路径数据信息，存在一定的误差，随着数据采集技术的不断更新，RFID技术用于物流供应链管理，通过将运输的物品贴上RFID标签，物品经过物流的某个节点时，RFID阅读器会记录此时的详细位置信息和时间信息，因此能够完整的获取物品移动的路径信息，Chen[29】等人提出了用一系列位置构成序列的移动模式串方法来表示路径数据。物品的位置信息描述为形如(ID，Location，t)的数据元组，ID是物品的唯一标识符，Location表示t时间所处位置信息，t表示记录的时间，其中Location是逻辑地点或业务阶段的标识符，可以表示仓库、配送中心和零售商等。考虑对某个地点信息记录一次，按照时间顺序对一些关于某个物品的记录信息排序，则得到该物体的移动路径表示为ID(Locationl，Location2，⋯，Locationm)的序列。如某物品先后经过物流节点s1，s2，s5，s6则该物品的路径表示为(sl，‘s2，s5，s6)，关于路径数据的概念在第四章有较为详细的介绍。本文采用基于移动模式串的表示方法，因为该表示方法能够更加精准的描述物品的路径信息，便于对路径数据进行数据挖掘分析，但是对于网络和服务器的性能有更高的要求，因此本文研究云计算环境下的物流路径数据分析工作。2．2．2．2路径数据类型(1)简单的路径数据某移动物品的路径表示为形如ID(Locationl，Location2，⋯，Locationm)的数据，称为简单路径数据。这里ID表示移动物品的标识，Location表示物品路径节点。实际上路径数据是由一系列路径节点按照时间顺序组成的，因此实质上属于序列数据。这里的路径节点只是位置的标识符。本文研究简单路径数据的数据挖掘分析，是路径数据挖掘的探索性研究。(2)复杂的路径数据复杂的路径数据是指除简单路径数据之外的还包含了时间信息，位置详细信息和物品多维信息等的路径数据[151。例如包含时间信息的路径数据表示为ID<(Locationl，t1)，(Location2，t2)，⋯，(Locationm，tm)>。10 2．2．2．3路径数据挖掘(1)路径聚类分析，根据路径之间的相似性，对路径数据分簇，是簇内相似性最大，簇间相似性最小，对路径数据进行聚类分析可以发现路径的分布模式，和路径之间的关系。路径聚类分析的关键问题是相似性度量。(2)异常路径分析，用数据挖掘中的孤立点分析方法来发现异常路径，异常路径分析用于物流的货物流向分析时，异常路径可能是货物丢失和不能按时到达的原因。(3)路径频繁模式分析，由于路径其实是一种序列数据，因此用序列模式挖掘方法发现频繁出现的的路径序列。本文研究的正是路径频繁模式挖掘问题。2．3云计算理论2．3．1云计算定义云计算这个概念首先由Google公司的首席执行官EricSchmidt于2006年提出的，短短几年时间，云计算在企业界和学术界掀起了一股应用和研究热潮。根据ISO组织2009年的调查，云计算的定义多达20种。目前唯一一个得到广泛认可和支持的定义是由NIST(NationalInstituteofStandardsandTechnology，美国国家标准和技术研究院)提出的云计算的定义。2009年4月NIST的PeterMell和TimGrance提出的云计算定义【3o】：“云计算是一种能通过网络以便利的、按需付费的方式来获取计算资源(包括网络、服务器、存储、应用和服务等)并提高其可用性的模式，这些资源来自以共享的、可配置的资源池，并能够以最省力和无人干预的方式来获取和释放”。在云计算中，大量的软、硬件资源被整合在一起，以分布式共享的形式存在，可以动态的扩展和配置，最终以服务的形式提供给用户。用户按需租用云中的资源，无需了解云内部细节，也无需管理，只需按使用量付费即可。云计算是一种新的商业模式，它不同于传统的IT运用模式，许多专家认为云计算可能改变整个互联网的产业结构。2．3．2云计算特点云计算具有如下特点：(1)超大规模“云”具有相当大规模[311，Google公司的云计算中心已经拥有100多万台服务器，IBM、Amazon、Microsof和雅虎等企业也具有相当规模的云计算中心。云计算能为用户提供强大的存储功能和计算能力。(2)虚拟化虚拟化‘321是云计算最突出的特点之一。虚拟化技术云计算的重要根基，它把各种IT资源、软件、硬件、操作系统和存储网络等要素都进行虚拟化，放在云 计算平台中统一管理。云计算中所有应用的物理平台和部署环境都依赖虚拟平台的管理、扩展、迁移和备份，各操作都通过虚拟化层次完成。(3)可伸缩性可以快速、弹性的给用户提供服务，“云”的规模能能快速的扩展，以满足应用的需求，也可以迅速的释放，实现缩小。对用户来讲，可以申请的服务看起来是无限的，可以在任何时间购买任何数量的服务。(4)面向服务特性在云计算中，通过开发的标准和协议，软、硬件资源被抽象成资源，并以服务的形式提供给客户。(5)通用性云计算并不局限于某一个应用，在云计算平台下，可以为用户构造多种应用，可以同时支撑不同的应用运行。(6)低费用云计算通过整合分散的、甚至是闲置的资源来提供服务，这种模式能够降低成本是显然和必然的，资源共享还能实现节能和减排。(7)安全性云计算中的各种资源在物理上是以分布式存在的，即云计算系统在物理上是一个分布式系统，对信息安全和灾害防御等问题有更严格的要求，因此更需要先进的技术来保证安全性。2．3．3云计算体系架构云计算是一种崭新的计算模式，是分布式计算、并行计算和网格计算等信息技术的进一步发展。按照NSIT对云计算的定义，云计算的体系如图2．1所图2-2云计算的体系架构12 (1)IaaS(InfrastructureasaService，基础即服务)：交付给客户的服务是各种基础设施资源的运用，包括网络、存储和计算等。利用这些基础设施资源，用户可以部署和运行操作系统和应用程序。由供应商管理和操控各种底层云计算基础设施，客户可以控制操作系统的选择、存储空间、部署的应用。在这种服务模式下，客户无需购买硬件设备和相关软件，也无需考虑各种维护方法，通过租用云计算提供的相应的基础设施，即满足自己的需求。IaaS的典型实例有：AmazonEC2，S3。AmazonEC2采用Xen虚拟化技术，以Xen虚拟机的形式动态的为用户提供计算资源。Amazon公司还为用户提供简单存储服务(SimpleStorageService，S3)。(2)PaaS(PlatformasaService，平台即服务)：采用提供的某种开发语言和工具，客户开发应用程序，将应用程序部署到供应商提供的云计算基础设施上。供应商提供的服务包括运行时环境、共享服务及自动化管理服务等。客户无需考虑底层基础设施，但是可以控制部署在基础设施上的应用程序。同传统的开发模式相比，采用PaaS服务模式开发应用程序，为软件开发和应用带来了很大的便利，一方面，由于PaaS提供的高级编程接口简单易懂，可以大大缩短软件开发周期；同时采用同一平台开发和运行应用程序，兼容性问题也大大减少。典型的PaaS实例有Google公司的GoogleAPPEngine和微软公司的windowsAzurePlatfonil，GoogleAPPEngine为用户提供了支持java和Python开发Web应用；WindowsAzurePlatforill，运行在微软数据中心的服务器和网络基础设施上，通过互联网来对外提供服务。(3)SAAS(SoftwareasaService，软件即服务)：交付给客户的服务是云计算基础设施上运行的应用程序，即软件提供方按照客户的需求，将应用程序租用给客户，客户通过瘦客户端界面即可访问和使用。SaaS云供应商负责管理和维护云中的各种软硬件设施，用户无需考虑软件的安装、升级和病毒防御问题。与传统的桌面软件相比，SaaA服务模式的优势体现在：首先使用简单，客户无需安装应用软件的副本，也无需考虑维护和升级等问题，无论何时何地，只要连接网络就可以访问自己定制的服务；其次SaaS支持公开协议，现有的SaaS服务支持公开协议(HTML4／HTML5)，因此用户只需通过浏览器就能访问和使用SaaS服务；SaaS服务初始成本低，用户以租用的形式就可以得到自己所需的SaaS服务，无需在使用前支付昂贵的许可证等费用。SaaS服务产品众多，具有代表性的有Google公司和GoogleApps和微软公司的OfficeWebApps。 2．3．4云计算关键技术云计算是一种新型的超级计算方式，以数据为中心，是一种数据密集型的超级计算【331。许多企业推出了自己的云计算平台，虽然业界对于云计算还未统一标准，但基本上都涉及了虚拟化技术、资源管理技术和任务管理等技术，其中云计算较为独特的技术有数据存储、数据管理和编程模式，本文从以上三个技术来介绍云计算的关键技术。2．3．4．1数据存储技术云计算环境采用分布式和冗余方式来存储数据，采用分布式能实现对海量数据的存储，并且经济可行；采用为同一数据备份这种冗余存储方式，能够保证数据的可靠性。为了保证对海量数据的访问和使用，云计算的数据存储技术必须具备高容错、高可靠性、高扩展性、高获得性和高吞吐率等特征。目前，云计算数据存储技术主要有Google公司开发的GFS(GoogleFileSystem)[34】和Apache基金会开发的Hadoop实现的HDFS(HadoopDistributedFileSystem)[351。大部分IT商，包括雅虎、英特尔的云平台采用的是HDFS对数据进行存储。HDFS是基于GFS的开源实现，是一个主／从(maser／slave)体系结构，如图2．2所示。HDFS集群拥有一个NameNode和很多个DataNode，可以被多个客户端(Client)同时访问。NameNode部署在一个专门的机器上，可以看成是HDFS的管理者，主要负责管理文件的系统命名空间，记录元数据的变换，协调客户端对文件的访问等。DataNode存储实际数据，HDFS的数据通常是按照64MB被分成不同的数据块，每个数据块分散的储存在不同的DataNode。客户端要访问数据时，先与NameNode通信，获取文件的的数据块位置，然后直接从DataNode上读取文件。HDFSArchiteeture图2-3HDFS体系结构14 2．3．4．2数据管理技术云计算显著优势之一是能对海量数据进行存储和处理分析，从而为客户提供优质服务。虽然GFS和HDFS等分布式文件系统较好的解决了海量数据的文件组织问题，但若要实现大数据集的高效管理、快速定位等问题，需要开发专门的数据管理系统来实现对云计算环境下结构化数据的管理。目前较为成熟的云计算数据管理系统有谷歌的BigTable[36]并1]Hadoop的子项目Hbase【3列。Hbase是较为成熟的支持结构化数据的云数据管理系统之一，是GoogleBigTable的开源实现。Hbase是一个稀疏的、长期存储的(存在硬盘上)、多维度的、排序的映射表。每张表元素由行健(row)、列(column)(<列簇(family)>：<限定符(qualifier)>)和时间戳(timestamp)唯一确定。每个值是一个不解释的字符数组，数据都是字符串。2．3．4．3编程模式云计算技术面临的又一个重要问题是如何对大量的数据进行计算，一般采用的方法是并行计算。现阶段，对于很多开发人员，并行计算还是一个较为棘手的问题，特别是在分布式环境下。为了使一般的开发人员都能享受云计算带来的好处，云计算主要采用MapReduce[弼】编程模型。MapReduce是一种简化的并行计算的编程模型，它屏蔽了底层并行计算的诸多细节问题，开发人员只需设定Map和Reduce两个函数即可。关于MapReduce，本文第五章节有详细介绍。2．4本章小结基本理论介绍，本章首先介绍了数据挖掘的基本定义，数据挖掘的分类，数据挖掘的一般步骤和其在物流领域的应用情况；随后介绍了物流数据路径理论，包括物流和物流信息，物流路径数据的表示及其分类，简单介绍了几种路径挖掘任务，最后介绍了云计算的定义、特点、体系结构和关键技术。 第三章序列模式挖掘基本理论3．1序列模式基本原理随着数据挖掘在DNA分析和Web访问等领域的研究和应用，序列数据中的知识发现问题成为数据挖掘一个活跃的研究分支。序列模式问题最早由Aarawal和Srikant[”】于1995年提出，最初提出是想通过在顾客交易序列数据库中挖掘频繁序列，从而发现一段时间内顾客的购买活动规律。例如顾客购买办公设备时，先买了联想的一套台式机，两个月之后可能会购买内存条，一个月之后购买打印机。序列模式类似于关联规则，不过其更强调事件的顺序和时间属性。3．2序列模式基本概念Aarawal和Srikant[”】给出关于序列模式的主要概念如下：给定一个顾客交易数据库D，每项交易包含如下字段：顾客标识(customer．id)，交易时间(transaction．time)，以及在每次交易中购买的商品项(items)。假定在同一交易时间同一顾客只进行一次交易，每次交易不考虑所购买项的数量，只考虑一个项是否购买。表3．1顾客交易数据库示例CidTidItem22013．01．10a，b52013．01．11C22013．01．13d22013．01．14e．{，g42013．01．15d32013．01．16d，h，g12013．01．18d12013．01．20C42013．01．22e，g42013．01．26C表3-2顾客序列数据库示例CidItemSet1<(d)，《c)>2<(a。b)，《d)-(e，f，g)>3<《d．h。g)>4<(d)，(e．g)t《c)>5<纠>16 定义3．1(项集)设I={‘，f2，．．．，f。)是项的集合，其中it,是数据项(item)。项集是非空的项的集合。定义3．2(序列)序列是由若干项集组成的有序队列，记作一条序列S为