基于海量物流轨迹数据的分析挖掘系统

《基于海量物流轨迹数据的分析挖掘系统》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

武汉理工大学硕士学位论文AbstractIntheageoftheelectroniccommerce,theelectroniccommerce,logisticsindustry,logisticsvehiclesaremoreprosperitythanever.MoreandmorelogisticsvehiclesGPSdataareproduced.Thesedatacontainalotoftrafficinformationsuchasroadconditions,vehicles,andevensocialandeconomicdevelopment.Throughstatisticsandanalysisofvehicledrivingdistance,time,location,vehicleparkingcharacteristics,trajectorydataminingcanfindshippinglinecharacteristics,providelogisticscompanybasedonvehicleschedulingschemessuchastime,cost,andderivedaseriesofLBSapplication.TakingmassiveGPSdataasthedatasource,usingmassivetrajectorydataminingandrelatedtheoryofroadrecommending,composedbyonlineandofflinesystem,thispaperproposesandrealizesadesignframeworkofrouterecommendingsystemforlogisticsvehiclethroughestablishingclusteringmodelandanalyzingmassiveGPSdatatounderstandthedrivingruleoflogisticsvehicles.Thekeyapproachisdeepstudyingondatapreprocessing,stopsdetecting,routesegmenting,similarfreighttrajectoryclusteringandfreightlinesrecommending.Thespecificworkisasfollows:Asanecessaryworkintrajectorydatamining，istudythepretreatmentmethod,includingdatacleaning,dataofabnormaldetectionandexclusion,andwiththecharacteristicsofthissystemalltheGPSdatainanalysisandputforwardakindofanomalydetectionalgorithmbasedonthehistoricaltrajectorydata.Thealgorithmformassivedataprocessinghaslowtimecomplexity.Parkingpointsdetectionandpathintegralcanfindthatthepatternoflogisticsvehiclesandgoods.Inthispaper,onthebasisofnaivebayesalgorithm,iputforwardanewwayfortrajectorysegmentation,accordingtothelogisticsvehicleparkingandordinaryponitsusingthedifferentattributesoftimeandspacebetweenthemwhengoodsareloadedandunloaded.Iregulatefreighttrajectoriesclusteringsimilartothesamestartingpointandendpointofthetrajectory.thenprojectthemonthesamelatitude.Afterthatusingk-meansalgorithm,thecharacteristicoftrajectoryisanalyzed,andfinallygetII万方数据 武汉理工大学硕士学位论文logisticsvehiclegeneralmovementtracks.Intherecommendationofshippinglines,basedonthedifferenceofhistoricaltrajectorydataintime,distanceandcost,idesignanddrawthecorrespondingrecommendedrouteguidancewhichlogisticsdriveradoptsthroughreasonabledrivingscheme.Comparedwithtraditionalpretreatmentmethod.Thesetestsshowthatthemethodofpretreatmenttrajectoryisfaster,moreefficient,butsacrificingsomeprecision.Detectingparkingspotsandtracksegmentationachievegoodeffects.Inthecasesofmissingstopsofvehicletrajectoryanalysis,theresearchresultshaveveryimportanttheoreticalsignificance.Keywords:bayesianclassifier,trajectorydatamining,carving,abnormalpointfilter,k-meansclusteringIII万方数据 武汉理工大学硕士学位论文目录摘要.................................................................................................................................IAbstract...............................................................................................................................II目录................................................................................................................................IV第1章绪论.....................................................................................................................11.1课题来源..............................................................................................................11.2研究的背景和意义..............................................................................................11.3国内外研究现状..................................................................................................21.4论文内容和组织结构..........................................................................................4第2章轨迹数据挖掘技术研究.....................................................................................52.1轨迹数据挖掘介绍..............................................................................................52.1.1轨迹数据挖掘概念...................................................................................52.1.2轨迹数据挖掘内容...................................................................................52.2轨迹数据挖掘流程..............................................................................................62.2.1数据来源和预处理...................................................................................62.2.2轨迹数据路径分割和聚类分析...............................................................82.3基于历史轨迹的线路推荐服务..........................................................................92.4本章小结............................................................................................................10第3章轨迹数据预处理和轨迹分割方法研究...........................................................113.1轨迹计算流程....................................................................................................113.2轨迹数据预处理................................................................................................123.2.1轨迹数据特征.........................................................................................123.2.2轨迹数据异常点检测.............................................................................133.3停车点识别方法研究........................................................................................143.4轨迹分割方法研究............................................................................................173.4.1贝叶斯分类器概述.................................................................................173.4.2构造停车点训练集.................................................................................183.4.3基于朴素贝叶斯分类器的停车点分类.................................................203.5本章小结............................................................................................................23IV万方数据 武汉理工大学硕士学位论文第4章海量轨迹数据聚类算法研究.............................................................................244.1轨迹聚类的意义和问题....................................................................................244.2轨迹表达和相似性度量....................................................................................254.2.1轨迹规则化.............................................................................................254.2.2轨迹相似性度量.....................................................................................304.3轨迹聚类............................................................................................................324.3.1常见聚类算法比较.................................................................................324.3.2基于-均值算法的轨迹聚类.................................................................334.4基于GPS数据的线路推荐方法.......................................................................354.5本章小结............................................................................................................37第5章系统验证和结果分析.........................................................................................385.1实验基础和条件................................................................................................385.2系统实现与验证................................................................................................385.2.1数据预处理.............................................................................................385.2.2停车点识别.............................................................................................395.2.3轨迹分割.................................................................................................425.2.4轨迹聚类..................................................................................................43第6章工作总结和展望.................................................................................................446.1本文工作总结....................................................................................................446.2下一步工作展望................................................................................................44致谢.................................................................................................................................46参考文献...........................................................................................................................48作者在攻读硕士学位期间发表的专利...........................................................................51V万方数据 武汉理工大学硕士学位论文第1章绪论1.1课题来源中科院深圳先进技术研究所和深圳市宇易通科技有限公司合作开发设计的一个易流云平台系统，该平台旨在为物流企业提供真实物流信息服务的真实运力服务。1.2研究的背景和意义当今社会属于互联网高速发展的时代，许多传统行业都受到了剧烈的冲击，其中电子商务逐渐兴起，商业活动的网上交易呈爆发式增长，伴随来的是物流行业的蓬勃发展，为物流车辆轨迹数据挖掘提供了海量的数据源。轨迹数据挖掘是数据挖掘在轨迹上面的新的应用，它包括了轨迹数据存储、轨迹数据预处理、轨迹数据获取和挖掘以及应用。尽管有关于传统的数据挖掘系统已经有了多年很成熟的理论和方法，但是由于轨迹数据的特殊性，依然有许多轨迹问题需要深入研究，例如轨迹索引、查询、模式挖掘、不确定性和隐私保护等。其具体特点如下：（1）数据海量性：物流车一般以30s的间隔向数据中心发送当前位置，这些移动在全国各地路网中的物流车辆每天生成的GPS数据都达到了GB,甚至TB规模，并且还在不断增长中。这既是发展数据挖掘的驱动力，也是对数据挖掘的面临的难题。（2）数据稀疏性：虽然这些轨迹数据规模庞大，但是由于地理因素（如车辆行驶在山区、雨雪天气）、设备故障等原因，并不能保证每一个路段都有完整的GPS信息，甚至会有一些是错误的GPS数据。（3）数据复杂性：物流车辆在实际行驶过程中受到各方面主客观等因素难以简单通过某个模型或者理论进行评估和预测。主要有下列因素，每个司机都有自己的驾驶习惯，即使同一个司机在驾驶过程中也会针对不同客观条件改变自己的驾驶行为，例如天气、实时路况，这些不确定性无疑增加了轨迹数据挖掘的复杂性。（4）数据丰富性，在海量的轨迹数据背后隐藏着全国实时路况信息、物流运输状况信息和我国不同区域经济发展水平。对于我国道路基础建设、交通路1万方数据 武汉理工大学硕士学位论文径规划、物流车辆调度等提高我国物流行业水平具有重大意义。车辆轨迹是车辆的位置和时间的记录序列，可以很容易的使用小型GPS记录仪、车内导航设备、甚至手机获取，作为轨迹数据挖掘中的重要研究对象，分析和挖掘这种数据类型可以应用于城市热点区域分析、智慧物流和交通规划[2]等多个方面。不同的物流车辆轨迹通过分解在不同时间、空间等很多维度上以后，既有相同或者类似的部分，也有不同的地方，通过分析和统计其相似性和相异特征可以挖掘出轨迹数据背后包含的很多知识。在我国建设信息网络技术，城市，交通，物流的背景下，这些知识作为宝贵的财富可以不断推动我国向信息化、智慧化城市、物流积极发展，降低运输成本，提高经济效益，最终实现物流业智能化、智慧化。1.3国内外研究现状轨迹数据中的知识模式发现和处理有很多不同的方式，可以首先通过不同概念模型描述轨迹，然后在不同维度上的特征将轨迹分组，接着分析这些经过分组后的轨迹组内和组间相似性和相异性，发现偏离正常数据的异常轨迹，针对不同应用场景调整轨迹分类策略等，最终达到发现获取轨迹背后的知识。在这一个过程中，经常会遇到各种各样难以克服的困难，譬如数据量巨大、数据维数灾难、数据受到主客观因素污染、数据不确定、知识发现角度多种、知识[3]表示困难等技术难点。轨迹数据挖掘发现的知识类型和所使用的方法密切相关。所发现的知识的价值受到数据挖掘算法的影响，常用的轨迹数据挖掘技术有规则归纳、概念簇集、关联发现等。在实际轨迹数据挖掘应用中，应当根据不同的需求采用不同的工具、方法以及理论。目前的轨迹数据挖掘研究工作中主要为轨迹聚类、轨迹分类、离群点检测、兴趣区域、隐私保护、位置推荐等方面。作为轨迹挖掘重要的一部分：异常轨迹检测中，也已经提出了许多算法。传统的轨迹异常检测中，通常是提取轨迹[4]某些特征，计算这些特征间的差值再进行加权得到轨迹间的距离。克诺尔通过将轨迹分解、降低维数得到若干个包含主要轨迹有用信息并且相互独立的特征,如轨迹所包含的GPS点的数量、轨迹运动快慢、轨迹起始点的坐标位置、轨迹运动趋势等。通过检测的异常和正常轨迹数据路径的距离不同，以确定其缺陷的异常信息，它的缺陷在于:由于轨迹内部不同局部区域也存在特征上的差异,因2万方数据 武汉理工大学硕士学位论文[5]此上述方法只适用于特征单一或者长度较短的轨迹。伊利诺伊大学的Li建议构建了一种轨迹异样检查框架ROAM。该框架将首先通过轨迹离散化分成一个个独立的名为Motif的片段，该片段提取轨迹的某些特征信息构成Motif特征空间，利用构建的Motif中的属性信息，这个分类器最终用于将不同轨迹数据分类从而获取轨迹背后蕴藏的知识。为了克服传统轨迹中无法针对轨迹较长或者特征较复杂进行有效的检测。[6]刘良序首先通过不同轨迹间的相似程度的不同提出了部分相似、完全相似和离群轨迹的模型，将一段较长的轨迹分为若干独立无关的轨迹段，利用之前定义的模型和概念，然后比较每一个分段之间的匹配程度，设定不同阈值来确定这些较长的轨迹是否相似，并且使用了R树来来克服计算量过大的问题。也有一些科研人员通过数据挖掘中的密度聚类思想，密度越大的地方，轨迹越趋向于[7]正常轨迹，密度越小的地方轨迹越有可能为异常轨迹，譬如Liu。轨迹聚类是在相似的轨迹中找到不相似部分的过程。轨迹特征空间中不同密度代表不同轨迹在该属性上相似程度的不同，并且特征空间中不同的属性对[8]轨迹相似程度的影响也各不相同。不同轨迹从时间区间这个角度来看，其相似性也各有不同，本文从时间间隔出发，将不同聚类方法分为如下几类，如表1-1所示。这些方法逐渐在相似的时间间隔从时间上的要求相似性，本地时间间隔相似，最后到没有时间对应的相似性下降。它反映了人们在时间和空间探索时空轨迹和轨迹相似性度量的多样性。表1-1轨迹聚类方法分类列表相似性度量代表聚类方法[9][10]全区间时间相似欧式距离，最小外接矩形距离[11]全区间变换对应相似动态时间规整[12]多子区间对应相似最长公共子序列距离[13]单子区间对应相似子轨迹聚类[14]单点对应相似历史最近距离[15]无时间区间对应相似单向距离目前有关轨迹数据挖掘的研究主要关注在轨迹的时空特性上，已经建立了一些关于轨迹数据建模、数据存储、轨迹索引、轨迹查询、轨迹挖掘方面，但3万方数据 武汉理工大学硕士学位论文[16]是有关轨迹的语义信息的理论研究却并不多，Yan等人提出了面向轨迹数据语义信息分析与挖掘，获取物体有关运动的未知知识，这些知识是轨迹挖掘更深层次的应用。在目前云计算和大数据的时代下，只有对轨迹数据挖掘进行更深入分析和挖掘，研究物流系统模仿或者实现人类的在不同诸如天气、实时路况等诸多客观因素下的行为，具备模仿人的智能，学习推断并自适应解决出现在物流运输、存储的问题的能力，也就是当商品从出库、车辆中转调度、行驶路线和时间一系列问题作出合理正确的规划，最终达到物流的智慧化。1.4论文内容和组织结构本文依据轨迹数据挖掘的一般流程，首先分析GPS数据特征，并提出针对海量轨迹数据的预处理方法，接着提出采用贝叶斯分类器算法，并将此算法应用到的轨迹分割处理中，将不同车的不同轨迹提取出来，接着研究了轨迹聚类的相关算法，提出将K均值的聚类算法运用到轨迹聚类中。最后针对以上算法和系统进行了实验，将以上结果应用带货运线路推荐系统中。第一章中本文系统阐述了轨迹数据挖掘产生的原因和意义和一些已有的方法和理论研究的发展和现状，以及存在的问题，最后是论文的结构。第二章主要阐述了轨迹挖掘概念、一般过程和方法，提出了一种基于历史轨迹数据的货车运送线路推荐系统。第三章介绍了轨迹计算的一般流程，详细分析了数据预处理、停车点识别和轨迹分割的流程，提出了轨迹数据异常检测算法，基于朴素贝叶斯分类器的轨迹分割算法，完成了货运车辆的起止点识别，从而为轨迹分割提供了依据。第四章详细阐释了货运车辆轨迹聚类意义和存在的问题，分析了轨迹聚类流程，首先将轨迹规则化，然后通过K-均值算法将轨迹聚类获取货运线路常用行驶路线，并提出了基于GPS数据的线路推荐方法。第五章对整个系统进行实现和验证，利用matlab绘图总结分析得出结论。第六章总结与展望，对于本文所做工作不足之处进行了总结和对未来轨迹数据挖掘的展望。4万方数据 武汉理工大学硕士学位论文第2章轨迹数据挖掘技术研究2.1轨迹数据挖掘介绍2.1.1轨迹数据挖掘概念轨迹数据挖掘（TrajectoryDataMining）是数据挖掘技术中的一个重要的新兴领域，它的研究对象来源于越来越多可移动装置上装有GPS等定位设备并不断记录人类或者车辆的运行轨迹，在传统的数据挖掘过程和算法基础上针对移动轨迹数据特征，重点研究轨迹数据预处理、轨迹数据中的不确定性研究、轨迹数据索引与存储、轨迹模式发现、轨迹隐私保护以及基于位置信息的社会化服务。是计算机技术、存储技术、统计学、地理信息学和新技术等多学科的整合。轨迹数据本身的海量性、复杂性也对传统的数据挖掘算法提出了很多新的挑战，原有的数据挖掘对象往往数据量比起轨迹数据而言不大，为此很多新兴的数据库存储和索引技术、大数据处理解决方案也层出不穷不断，例如空间数[17]据库、内存数据库、批处理数据处理框架、实时流计算框架等。一般而言，轨迹数据挖掘，是指从大量轨迹数据的集合C中发现隐含模式m和知识n的结果S。因此，轨迹数据挖掘的过程可以看作为一个函数：[18]£:C→S（m,n），（2-1）输入是轨迹数据，输出是隐含模式m和知识n。通过使用某些技术、理论，从大量的轨迹数据提取模式、发现庞大知识的一个过程。2.1.2轨迹数据挖掘内容轨迹数据挖掘目前的研究热点集中于轨迹聚类、异常点检测、轨迹分类、位置推荐等方面。如图2-1所示。（1）轨迹聚类。通过轨迹聚类的方式可以发现轨迹数据中的相似性和异常特征，从而得到对于轨迹应用中有益的模式，例如发现热点区、通过大量物流车辆的历史轨迹可以找到收益最高的行驶路线、监控物流货运车司机驾驶行为等。通过研究不同轨迹数据在时空等方面的特征，定义设计不同的准则去度量轨迹的相似性，利用相似性的不同将轨迹区分开来。5万方数据 武汉理工大学硕士学位论文轨迹数据挖掘异常点检测轨迹聚类轨迹分类位置推荐图2-1轨迹数据挖掘热点分类图（2）异常点检测。在数据挖掘领域，异常数据的识别是其中比较重要的一部分，所谓的异常数据指的并非由随机误差造成的偏离大部分数据的特征的那部分数据。异常数据就识别出数据集中的异常点。同时混杂在异常数据中的正确数据也需要识别。它涉及怎么样定义异常数据和寻求有效的算法来识别并剔除掉这部分数据。（3）轨迹分类。轨迹分类与轨迹聚类的目的相反，指的是通过统计和分析不同轨迹间的时空特征，抽象出轨迹模型，并以此模型作为分类器，对目标轨迹进行分类，这是一个不断迭代的过程，并且出于不同的分类目的定义目标轨迹模式，通过轨迹历史模型，从而智能的将轨迹数据分类。（4）位置服务。车辆的行驶轨迹不仅仅是车辆行驶路线的一种记录，更是反映了驾驶人员针对驾驶活动期间客观因素，例如天气、实时路况、加油站等地理位置信息的智能反应，通过搜集、统计、分析这些历史轨迹可以极大提高车辆管理、监控、调度、路径规划效率，在当今越来越开放的网络条件下，实时共享位置信息，可以为公司和客户提供精准且高效的物流配送服务。随着这些位置信息的不断挖掘和共享，极大降低了物流行业中的沟通成本，降低中间环节消耗。2.2轨迹数据挖掘流程2.2.1数据来源和预处理轨迹数据来源是移动设备所发出的位置信息，对于物流轨迹数据而言，通常是GPS信息。预处理的过程首先是分析所获取数据的总体特征，再依据数据的特征采用不同过滤算法。6万方数据 武汉理工大学硕士学位论文（1）挖掘数据来源轨迹数据挖掘来源通常是终端设备上产生的位置记录，然后位置信息传回数据中心以日志文件形式存放。本文采用的是数据中心的GPS日志记录。表2-1是GPS日志的记录表结构。表2-1GPS日志记录表结构属性域描述车辆编号车辆的唯一编号经度以度为单位的维度值乘以10的6次方纬度以度为单位的维度值乘以10的6次方里程0.1KM速度KM/H方向0-359，正北为0，顺时针高度海拔高度，单位米GPS时间接收到GPS的时间状态0位：0：未定位1：3D定位一条典型的GPS日志记录如下，其中各个字段之间用逗号隔开,车牌号码已经被加密。XI081FB4GU,115045136,30511584,412698,62,75,0,13-12-120:5:48,1。（2）轨迹数据特征分析轨迹数据特征分析是指观测轨迹记录中所具有的包括空间属性、数字特征、分布结构等在内的特征，是数据应用的基础，它包括很多方面的统计和分析，例如离散轨迹点随着时间增长时候的方向信息、起止点最远距离信息，最大时间间距信息等一维数据信息。在这些一维数据的基础上分析轨迹点的密度的稀疏性、分布结构的信息有利于发现热点区域等，通过线性回归的方式有利于常见轨迹模式的发现和提取，不断研究轨迹时间与时间、时间和空间、空间与空间之间的关系。（3）轨迹数据异常检测轨迹数据挖掘领域异常检测一直是研究热点，通过数据挖掘中的常规模式析取可以发现大量轨迹数据时空特征以及背后的语义信息，但是有时候异常的出现也包含很多重要信息，例如可以修正之前轨迹特征空间划分的方式，发现7万方数据 武汉理工大学硕士学位论文隐藏或者突发的信息等。所谓异常，有很多各种各样的概念描述，概括而言指的是这样的一些数据具有整个数据集合中不同寻常的属性和特征，异常与错误不同，异常的产生并非人为原因造成，也并不是随机因素影响。轨迹异常检测可以分为两个过程实现，首先在轨迹数据特征分析的基础之上发现和定义异常特征，然后利用这些特征空间与轨迹数据集比对，找到符合这些异常特征的数据集，不断迭代修正异常特征空间，最终检测出异常轨迹数据。目前关于异常检测有很多种方法：例如使用统计学知识对轨迹的时空分布特征统进行分析，找到不符合常规分布特征的数据集合。通过定义轨迹间距离的方式来发现异常轨迹，关于距离的定义也有很多种，欧式距离、曼哈顿距离、汉明距离、切比雪夫距离等。定义轨迹在时空属性的密度特征也可以发现异常轨迹，密度大的[19]区域的轨迹趋向于正常轨迹，密度小的区域的轨迹趋向于异常轨2.2.2轨迹数据路径分割和聚类分析通过GPS设备获取的轨迹数据只包含每一轨迹点的经纬度和对应的时刻信息，通过这些数据无法直接得到活动行为的特征信息，如停车时间、是否卸货、物流的目的地、以及其他信息。要想获取这些信息首先就必须进行停车点侦测，判断是那些时刻是真实停车，还是GPS产生了漂移误差，或是由于红绿灯、交通拥堵造成的停车，或者是停车卸货等一系列重要信息和知识。图2-2为停留点侦测示意图。轨迹分割是轨迹数据挖掘的基础和前提，目前，轨迹分割算法有探索和机[20]器学习方法两大类。探索性方法考虑移动对象停留和移动时的时空特征或定位设备的特征，作为已知经验，设计算法对轨迹原始数据进行处理和分析。机器学习是人工智能的一个分支，目的是构建一个可以从数据集中学习的系统，机器学习主要解决数据表示和泛化的问题，数据实例的表示和评估是所有机器学习系统中的重要部分，机器学习系统对数据集泛化的能力是对未知数据分类和计算的核心关键部分。通过机器学习的方式可以使轨迹数据挖掘更加智能，不仅能够发现轨迹已有的特征，还能针对未知轨迹数据学习发现新的特征。机器学习方法有很多种，决策树学习，关联规则学习，人工神经网络，支持向量[21]机学习，聚类，贝叶斯网络等。聚类的目的是尝试将具有相似特征的轨迹划分开来，凸显不同轨迹间的相似性，为更深层次的研究打下基础。可以将轨迹特征空间中不同属性相互独立8万方数据 武汉理工大学硕士学位论文[22]抽取出来，找到每一个被划分的属性与整体分布特征之间的关系。根据相似度量的不同，常见的基于距离轨迹聚类方法有基于欧氏距离、最长公共子序列距离、时间聚焦距离、历史最近距离等。轨迹停留点点停留区域行驶路径图2-2停留点侦测示意图2.3基于历史轨迹的线路推荐服务目前基于位置的服务（LBS）已经在市面上取得了大量应用，例如旅游线路分享、车辆调度和安保等。简单的将轨迹展现在地图或者其它的媒介上，统计其行驶距离、时间、频率、停车位置等难以发现轨迹中包含的司机驾驶习惯，交通道路信息，热点区域以及路径信息等。其实，轨迹记录了驾驶人员在真实世界的活动，而这些活动将在一定程度上体现了驾驶时的各种环境因素，比如交通路况、天气、经济成本等。而传统的路径推荐系统主要是通过基于地图的最短路径算法生成的推荐线路，通过这种的算法规划得到的路径由于没有考虑到实际中地理位置信息，例如停车场，加油站，货运园区工厂以及道路限行、限速路段，监控区域等，并且这些地理位置信息经常出现新增，变更，删除，不准的状况。基于历史轨迹的路线推荐系统由于是考虑了实际需求，由于是司机驾驶的实际路径结果，包含了司机对真实地理天气和道路综合考虑的结果，因此推荐的线路也更合理、更多样，可以基于最少时间、最少费用，也可以最9万方数据 武汉理工大学硕士学位论文短路径等。基于历史轨迹的线路推荐服务的一般结构如图2-3所示。它是依赖聚类结果，包含基础的数据处理并挖掘相关知识。包括数据采集、数据预处理、数据分析。GPS记录日数轨轨推志预预处理迹迹荐用户空间数据库处后GPS分聚算理记录割类法用户信用级算算服务别法法器数据预处理模块数据挖掘模块推荐系统模块理模块图2-3基于历史轨迹的线路推荐服务一般结构2.4本章小结本章细述了轨迹数据挖掘的基本流程：数据源的获取，数据预处理，轨迹分割、轨迹聚类，推荐服务。对基于历史轨迹的线路推荐服务系统做了分析，说明了使用的聚类算法和推荐算法，根据数据挖掘的知识完成货运线路推荐功能。10万方数据 武汉理工大学硕士学位论文第3章轨迹数据预处理和轨迹分割方法研究3.1轨迹计算流程通过定位技术采集到的原始轨迹数据只是一系列的经纬度、时间、速度等信息，通过这些信息无法直接得到物流货运车的活动行为的特征信息，例如运送货物的起始点、途经哪些城市信息，以及更深层次的活动规律等。这些原始的GPS数据必须经过一系列的处理步骤，才能获取到物流货运车的送货规律等[23]特征信息。如图3-1为轨迹计算的流程图。其中轨迹预处理包括数据规范化、异常点去除等，原始的GPS位置信息并不包含停车点信息，停车点识别指的是从轨迹点中提取停车位置信息，上步中识别出来的停车点信息由于并不包含货运车辆的上下货的位置信息，轨迹分割便是从轨迹中识别出一趟完整的货运信息，包括货运的起点和终点等信息。这是本文的核心部分，最终得到的轨迹输出结果可以用于物流货运车辆的轨迹推荐。输入数据预处理停车点识别轨迹分割输出图3-1轨迹计算流程图11万方数据 武汉理工大学硕士学位论文3.2轨迹数据预处理3.2.1轨迹数据特征使用车辆的海量GPS数据要面临的首要问题，是如何发现和处理大量数据中的异常元素。有很多客观因素诸如天气、实时路况、设备异常会使轨迹数据发生异常。本文基于某物流公司每天实际的GPS数据进行了空间分析，包括时间、速度和位置信息，得出的空间特征和规律如下。（1）数据量大。本文中货运车辆每周产生的数据记录数约为4千万条。详尽的数据对分析和挖掘有利。但对后续的数据的分析过程和算法提出了高的要[24]求。针对此问题，本文基于Hadoop分布式平台以提升GPS并行处理的能力。（2）数据重复。造成数据重复的原因是多种多样的,例如当车辆处于信号差的区域，山区，隧道等，或者设备本身异常或者故障导致重复发送相同GPS数据，车辆停车时也可能会造成GPS数据发送重复，所以，因这对这些数据记录进行标注并删除。这样便可以有效的压缩减少无效的数据。（3）数据缺失。物流货运车辆在其运行期间GPS接收机设定的接收时间间隔一般为30秒到1分钟之间,但是由于地理因素（如车辆行驶在山区、雨雪天气）、设备故障等原因，并不能保证每一个路段都有完整的GPS信息，甚至会有一些是错误的GPS数据。这些缺失的数据对于获取和分析轨迹行驶信息造成的严重的影响，这些缺失的数据可以通过借助一些地理信息补回。（4）GPS漂移。在GPS设备定位过程中，所标识的位置和用户实际位置有一定的出入，常见的现象是实际轨迹和先漂移轨迹混杂在一起。车辆即使实际原地位置不动的时候产生的经纬度信息也是不断变换的。有很多客观原因会造成这种现象，例如GPS设备在长期使用过程中并没有初始化或者调校，造成实际位置和显示的位置之间有一定的误差，设备实时搜到的卫星数量、卫星本身的位置分布等，由于CPU处理速度或者算法不够好，使得车辆在以较快速度行驶时的GPS信号与车辆静止时候相比较，经纬度偏移。目前GPS设备在城市中定位精度在10米左右，偏移在50米左右，由于城市道路密集和复杂，这些偏移足能够影响轨迹数据分析结果。使用包含重复、异常和错误的GPS数据会影响后续轨迹数据挖掘的结果和效率，因此对海量GPS数据中的异常元素进行排除具有很重要的意义。12万方数据 武汉理工大学硕士学位论文3.2.2轨迹数据异常点检测[25][26][27]目前关于轨迹异常点排除算法大多通过基于划分、统计、密度等方法。基于统计的方法通常是使用一些数据在统计学上的分布特征，例如正态分布异常点检测，如果某个数据对象偏离数据集均值到阈值则被归为异常点。该方法依赖于数据的分布、异常点类型等，该方法有坚实的数理统计理论支撑，然而当缺少数据分布特征的参数时，通过一些方法确定分布来拟合也是十分复杂低效的。使用划分的方法是一种常见的聚类分析手段。它通过将所有数据聚类成不同的簇，然后没有归类到任何簇的数据点则为异常点，该方法的时间和空间复杂度低，发现的异常点可靠性高，例如常使用K-均值聚类算法将轨迹聚类。该方法存在的缺点是需要预先知道聚类数K值，聚类中心选取不准可能导致无法得到正确的分类结果。密度检测方式是数据挖掘中的常用方法，轨迹数据集中每一条轨迹被投射到不同维度上，然后比较每一块区域内的密度以及相邻区域大小，密度大的地方轨迹数据越趋向正常，密度越小的区域轨迹为异常数据可能性较大。它存在一个很大的问题就是计算量大，每次必须计算每一点的邻域，造成速度慢。此外还有利用路网等GIS信息进行道路匹配的思想进行的异常点检测，该方法由于需要精确的知道路网信息，此外算法时间和空间复杂度高，当面临本文所遇到的海量轨迹数据处理的时候难以适应在实际生产中需要快速得到分析结果的应用中。为了快速高效的检测轨迹中异常点，本文采用了基于网格划分的思想来对异常点进行检测的思想。其算法过程如下：（1）将地图区域按网格划分。本文将GPS数据定义为一个二维平面中的一个点pi{lonlati,i}，表示经度，lati表示为纬度。以地球纬度和经度作为坐标轴2将包含地图区域可以简单映射为一个二维平面R{(lonlatlonRlat,)|,R}。然后使用平行于坐标轴的直线把地图划分大小相等的网格R{lon,lon,lat,lat}，其中lon、lon、lat、lat分别为格子的imaxminmaxminmaxminmaxmin上边界、下边界、右边界、左边界，所划分得到格子的集合S{,RRR,...R,}R。123ii12定义一个映射关系FR:S，通过分别对经纬度上下取整得R{ceillon(),floorlonceillat(),(),floorlat()},其中lon和lat的精度的不同将会iiiiiii影响格子的大小。（2）计算映射到网格轨迹数据点数量P。判断P是否小于异常点阈值cntcntC，如果成立，则该网格内的所有数据点判为异常点，否则非异常点。thre13万方数据 武汉理工大学硕士学位论文（3）对于非异常点的网格R，找到网格内数量最大的网格作为第一个类G，i1计算网格内部的中心点R(R...R)/n，然后找到欧式距离它最远的网格点cn1作为第二个类G。2（4）计算其它网格到初始两个类的网格的欧式距离d。如果网格距离小于ijD，则将该网格归到此类，否则，将其定义为新类G。threi（5）获取没有被归类到任何类中的网格，该网格内的点既可以被认为异常点。本算法相比较传统的划分方法的异常点检测有如下优点:（1）不必事先指定分类数K，在不断的分类迭代中获取分类数。（2）初始分类中心并不是随机生成的，有效避免了只能收敛到局部最优的情况。（3）可以有效且方便的检测出异常点，由于道路一般比较分散，尤其是货运车辆所行驶的线路，不在网格内的数据点既可以判为异常点。（4）时间复杂度低。由于对整个区域按照网格划分计算，所有其时间复杂度接近于线性复杂度，当分类数越小时，数据越集中时时间复杂度越低。本算法的流程图如图3-2所示。3.3停车点识别方法研究轨迹分割就是首先将空间上离散的轨迹点划分成停车点和移动点两大类，并且停车点可以划分为三种类型，第一种主要为在城市道路中由于红绿灯等待造成的停车，一般这种停车时间较短，对于轨迹分割没有意义。第二种由于司机加油、吃饭、交通拥堵造成的停车，这种停车时间一般较长，对于本文的轨迹分割有较大影响。第三种为停车卸货，通过这个停车点可以识别出一趟货运线路的起始点位置等信息。在充分考虑了GPS数据特征的情况下，我们可以依货运车的速度信息来判断是否停车，本文采用了基于速度的停车点算法。该算[28]法分为3个步骤，计算GPS点的速度，判断疑似停车点，停车点点识别。（1）计算GPS点的速度由于GPS的定位精度较准，误差一般在10m到50m之间，时间间隔一般为30s到60s之间。GPS点的速度可以由相邻前后GPS点连成直线的平均速度来替代。如图3-3GPS点速度计算示意图。计算P点的速度公式为：4dd3,44,5vp4（3-1）tt3,44,514万方数据 武汉理工大学硕士学位论文开始所有数据将地图划分为网格计算网格内数据点个数否个数大于阈值Cthre是初始化类数K-3调整类数量计算对象到类的距离否距离大于阈值Dthre是归类到已有类中没有被分到任何类网网格内数据为异常点格中的数据为异常点图3-2轨迹异常检测算法流程图式3-1中d表示GPS点p和p之间的位置差为p和p的时间间隔，vij,ijtij,ijpi为p时刻的速度。i图3-3GPS点速度计算示意图15万方数据 武汉理工大学硕士学位论文（2）判断疑似停车点停车点的判断需要靠速度阈值来判断，可以设置一个速度上限v来判断是max否停车，首先依据v将所有的GPS点划分为两类，疑似停车点和行驶点，并max且由于停车的时候不应该只有一个点的速度小于v，至少应当有若干个。形成max一个停车点候选区域。停车上限v可以设置为人步行的速度约为1m/s。该过程max如示意图3-4所示。其中速度的单位m/s。停车点速度停车点p11.0疑似停车点p20.6疑似停车点停车区域p30疑似停车点p40疑似停车点p55GPS点分类行驶点合并停车点p610行驶点p12行驶点7p80疑似停车点停车区域p90疑似停车点p100疑似停车点图3-4停车区域判断示意图（3）停车点识别通过前面计算得到的一系列疑似停车点，可以结合停车距离的阈值范围，选择停车时间最长的疑似停车点作为最终的停车位置。具体算法步骤如下：I.读取轨迹中的第一个疑似停车点s，将其放入停车点序列Seq中。1II.判断是否还有疑似停车点si(2,3,4,5...)，如果有则计算这个点与上一i个停车点s的距离间隔d，如果d小于距离阈值d，则将该点放i1ii1,ii1,max入停车序列Seq中，并重复步骤II，否则进入步骤III。III.计算Seq中的停留起始时间Seqstart.和结束时间Seqend.，如果停留时间小于时间阈值，则清空Seq，如果大于，则保留此次停车记录。tmintmin通过停车点识别，可以找到物流货运车的简单行驶规律，例如停车地点，逗留时间，但是对于深层次的轨迹信息挖掘这是远远不够的，只能通过对停车点更深层次的挖掘才能获取货运车辆一趟完整的货运信息。16万方数据 武汉理工大学硕士学位论文3.4轨迹分割方法研究3.4.1贝叶斯分类器概述轨迹数据挖掘中，如何对轨迹数据集合分类是一个重要问题，准确的分类是后续轨迹分析的基础。分类是从数据集合中提取描述数据类中重要属性的过程，通过分类可以更深入了解数据特征，机器学习中已经有很多种分类方法，例如模式识别和统计学方法，传统的分类方法中都是基于较小的数据规模，近年来随着大数据越来越受到科研界的重视，逐渐发展出来一些针对海量数据分类的技术。分类器可以用来判定一个未知的数据归于哪一类，例如在轨迹数据挖掘中，当进行轨迹分割的时候就需要判断哪些点属于停车点，哪些点属于卸货点，这就是分类问题的一个典型应用。数据分类过程可以分为两步，第一步是学习，也就是构造分类模型，第二部是分类，就是利用第一步产生的分类器对未知数据进行分类。第一步中，通过描述已经带有类型信息的数据集合来构造分类器，这被称为训练阶段，例如，一个数据由向量X组成，其有n维属性组成X{,,...}xxxx,123n整个数据集由C{,,...}xxxx组成。每一个数据X都已经归属于特定的类属性123nAAA,,,...A其中每一类属性A都是离散值并且无序。由数据X组成的集合被123nii称为训练集，并且每一份数据都是随机抽样生成。由于数据类型已知，这一步被称为有监督学习，与此对应的是无监督学习，数据集合中的数据类型未知。这一步分类过程可以视为学习一个这样的映射或函数关系yfx()，其中，x代表属性，y代表类型，从这个角度来看我们希望获取实际的这个映射关系f.通常，这种映射关系以分类规则、决策树或者数学方程的形式展现。在停车点类型判断中，这个映射关系就是一个可以判断某一个停车点为卸货点还是普通停车点，并且被用于对未知数据进行判断。在第二步中利用第一步生成的分类器对数据进行分类，首先分类器的准确性是需要考虑的问题，如果使用训练集来评估准确性，显然可以得到非常理想的结果,因为分类器倾向于拟合这些数据，因此必须考虑使用测试数据集来评估分类器的准确性，这些测试数据集和训练集之间是相互独立的。分类器的准确性由测试数据集中有多大比例数据被正确分类决定，如果一个分类器的正确性在可以接受的范围，该分类器便可以对未知数据集进行分类，否则得迭代生成新的分类器。因此分类器的质量受到了训练集数量和质量、数据特征空间选取等多方面影响。17万方数据 武汉理工大学硕士学位论文贝叶斯分类器是一种统计学分类器，它能预测给定数据属于哪一种类型的概率，贝叶斯理论的基础是贝叶斯公式。在该公式中X是数据本身，通常假设其有n维属性，将H设为X属于某一特定类型C的假设，在分类问题中，我们想要求出的是PHX(|),也就是已知X的情况下，它属于类型C的概率大小，这种概率被称为后验概率，与此对应的是先验概率PH(),在轨迹数据停车点类型判断中该概率即为所有停车点集合中卸货点的概率。与此类似PHX(|)是已知假设H的情况下是X的概率。综上贝叶斯公式即为PXHPH(|)()[29]PXH(|)（3-2）PX()[30-31]朴素贝叶斯分类是一种十分简单的分类算法，在不考虑类型之间的关系时候，它是一种最小错误率分类器。朴素贝叶斯分类器的基本思想是在待分类项已知的情况下，求解其归属每一种类型的后验概率，具有最大后验概率的类型时便可以将待分类项判定为该类，图3-5即为朴素贝叶斯分类器流程图。其基本流程：（1）由训练数据X{,,...}xxxx组成的训练集，并且X的类型已知，x为123niX一个特征属性。（2）设有n种类别的集合C{,CCCC,...}。分类器判断具有最大后验概123n率的X归属类型，也就是X归属为C的条件为PCX(|)PC(|X)，其中iij1jm。3.4.2构造停车点训练集货运车辆停车有多种原因，例如红绿灯、交通拥堵、司机休息交接、停车装运货物、停车卸载货物等一系列人为和非人为因素。其中装货点和卸货点是各家物流公司及司机综合考虑了时间、距离、成本等要素的结果。对于后面的货运线路优化、推荐有重要指导作用。本文所使用的轨迹数据中不包含装卸货信息，因此缺乏足够的装卸货的先验知识和训练集。通过计算停车时间等或者行驶距离等方法来从一系列的停车点中识别出装卸货点，忽略了这些连续停车点之间相互的关联关系。例如，假如有在一条历史轨迹中存在相邻两个停车点。并且停车时间也相近，距离上一个停车点也经历了较长的距离和时间。分类器必须对这两个停车点识别分类的时候，如果通过上述间隔时间和距离的判断方法，则会将第一个停车点识别为装卸货点。18万方数据 武汉理工大学硕士学位论文准备工作阶段确定特征属性获取训练样本分对每个类别计算类器P（）对每个特征属性训计算所有划分的练条件概率阶段对每个类别计算PCX(|)为最大iPC(|X)j应用阶段图3-5朴素贝叶斯分类器流程图为了解决上述问题，本文采用了数据挖掘和机器学习的方法来完成了算法设计。具体流程是从历史轨迹中发现货运车辆装卸货的时空特征，获取车辆停车时间长度和停车点相邻距离等先验知识，有了足够的先验知识以后，就可以依据这些先验知识预测车辆下一次停车装卸货时间和地点。先验知识的准确度将会影响分类器的效果，具体到本文的轨迹数据该先验知识可以从物流货运车里程和停车时间观测获得。一般而言，同一类型物流货运车装卸货一般所消耗的时间和一次运输所行驶的里程v一般为一个趋向于一个常数，这是因为物流货运车司机驾驶习惯、所行驶的线路相对固定，有的车辆偏向于短途、有的偏向于长途等。本文首先使用停车点时间间隔和空间间隔的特征，找到确信的一趟货运线路的起点或者终点，依据物流行业的经验，一辆车停车时间在2个小时以上基本可以判断为装卸货，由于起点和终点在停车时间角度上基本上是一样的，可以将这两种停车时间看作一种类型。基于此本文提出了简单停车点识别算法。具体算法步骤为依次读取通过上文中停车点识别获取的停车点信息，如果相邻19万方数据 武汉理工大学硕士学位论文停车点的距离大于v,停车时间阈值,则该停车点为起始点。算法描述如maxmax下，式中GPS数据点r{,tlonlatodm,,},t表示GPS发射时刻，lon,lat表示iiiiiiii此时刻的经纬度，odm表示此时刻物流车的总的行驶里程。停车点ivs{lonlatodmttprevdis,,,,,},其prevdis相邻两次停车点的里程间隔，t为停iiiisiiisi车起始时刻，t为停车时长。rs代表停车点，cs代表普通停车点。本算法的本iiii质是将每一个货运车辆的停车点分为起止停车点或者普通停车点。本文提出的简单停车点识别方法如算法3-1所示。停车时间设置足够长的时候上述算法可以正确识别出起止停车点和普通停车点。然而对于相邻距离较近的停车点或停车时间不够长的点却无法区分。对于剩余难以分类的停车点，本文采用了梯度下降法的算法来识别它们在停车时长的区别。经过了简单距离和时间的识别算法后，剩余的起止点构成集合RS，其余的普通停车点构成CS。由于每辆车行驶的路径，司机驾驶习remainremain惯相对固定，所有最终真实的起止点时间会收敛到，所以当计算RS中maxremain的每次起止点停车时间与的时候,如果足够小，那么就是该辆车的起止停车点的停车时长。然而显然无法从原始轨迹中直接获取，本文采用梯度下降法逐步将减小，最终将起止点停车时间收敛至。||RSt（3-3）remainii本文提出算法如下算法3-2所示。该算法从函数Interval的初值出发，并init考虑如下序列,,,...,使得，可以得到123optimumii1Interval()Interval()Interval()...最终可以顺利收敛到。上述算法123optimum中IntervalVS({},)的具体实现如算法3-3所示下。从算法3-3易看出当初始值很大时，这样起止点集合RS将为空，为所initi有停车点时间长度之和，随着沿着逐渐减小，其也会随之减小。然后下i降到期望值附近以后可能会'之字型'下降，最终收敛到。optimum综上，本文首先通过简单判断方法依据停车时间长度和停车点之间的间max隔v初步获取了最可靠的起止停车点集合RS，然后使用梯度下降法完成了对maxi起止停车最优时长的计算，然后依据该最优值去分析停车点类型，构造训optimum练集。3.4.3基于朴素贝叶斯分类器的停车点分类朴素贝叶斯分类器是基于贝叶斯定理的一类分类器，贝叶斯定理如下20万方数据 武汉理工大学硕士学位论文dPY()PXY(i|)1PYX(|)（3-4）PX()式3-4中Y是类别变量，X{,}xx是待分类的特征向量。具体到本文中；12X{,}xx中的xvsprevdis.,即停车点之间的距离，xvst，即停车时长。121i2iiiY{,yy}有两种类别，y0代表普通停车，y0代表起止点停车。停车点1212分类问题可以描述为对某一类别X求其argmax((PYyX|))，然后依据其概率i值判断X的类别。InputVS{vsvsvs,,...vs},一条轨迹中的停车点集合123nv,相邻停车点的距离阈值max,停车时间阈值maxOutputRS{rsrsrs,,...rs}起止点集合123n1CS{cscscs,,...cs}普通停车点集合123n2Procedureprevdis,10,20,nnRSnullCS,nullfori1;ini;dovsprevdis..vsodmprevdis;iiiifvsprevdisv.andvstthenimaxiiimaxprevidsvsodm.irsvsni1RSaddrs:()n1nn111elsecsvsni2CSaddcs:()n2nn221endifendforreturnVSRSCS{,,}算法3-1简单停车点识别算法21万方数据 武汉理工大学硕士学位论文InputVS{VS,...VS}多条轨迹中集合,,停车时间长度，为迭代步长1ninitOutput最优起止点停车时长,CS{cscscs,,,...,cs}普通停车点集optimum123n2ProcedurewhileoptimuminitcuroptimumIntervalVS({},)1curIntervalVS({},)2curIntervalVS({},)3curargmin{,,}optimun123endwhilereturnoptimum算法3-2复杂停车点识别算法InputVS{VSVSVSVS,,...}多条轨迹中集合,预测起止点停车时间长度123nOutput起止点停车时间与预测时间的差值Procedurenullfori1;ini;do{VSRSCS,,NaiveMethodVSv(,,)}iiiimaxmaxifRSnulltheni|VSallt.|iielse{RS,CSremoveVSRSCS(,,)}remainremainiii||RStremainiiendifreturn算法3-3函数IntervalVS({},)具体实现22万方数据 武汉理工大学硕士学位论文在一个给定的训练集中，显然PY()可以通过观察或者计算得出，然而训练集的构造需要一些简单办法难以区分的停车点，假设有n个起止停车点，n个pc普通停车点，n个简单办法难以区分的停车点，然后通过朴素贝叶斯方法识别h出来的n个起止停车点，普通停车点的概率为式3-5所示，起止停车点概率如r3-6所示nnnchrPY()y（3-5）1nnnpchnnprPY()y（3-6）2nnnpch由于x和x是连续型变量，可以设其为正态分布，因此122()xiij212ijPX(xY|y)exp（3-7）iii2ij其中为X的均值，为训练集中的方差，Xy。ijiijij朴素贝叶斯是一种简单的统计学概率的分类器，它的基础理论是贝叶斯定理，假定类之间属性是相互独立的，分类效果极其稳定，在本文的停车点判断，停车时间长度和车辆行驶距离是相互独立的。由于类条件密度的估计是基于所有的数据集，所以有很强的抗孤立噪声的能力，若干个停车点的噪声错误都最终被整个数据集平均化了。当一条轨迹中的所有起止点都被识别出来以后，以这些停车点位分割点，将轨迹进行分割，则就获取了每辆车所有的运输起始点和终点，为后续的轨迹聚类提供了数据支持。3.5本章小结本章主要介绍了轨迹计算的流程，一般而言其需要经过数据预处理、停车点识别、轨迹分割，数据预处理是之间依据轨迹数据特征，对数据进行异常点检测、去除重复、数据规范化等操作，重点介绍了一种基于网格的轨迹异常点检测算法，该算法通过将轨迹点映射到不同区域中，然后网格内数据点个数和对网格进行分类从而发现异常点。然后通过车辆速度进行停车点识别，得到了一系列可靠的停车点，然后基于该停车点，利用朴素贝叶斯分类器算法获取货运车辆起止卸货停车点，完成了轨迹分割。23万方数据 武汉理工大学硕士学位论文第4章海量轨迹数据聚类算法研究4.1轨迹聚类的意义和问题海量轨迹数据中包含了经纬度信息、时间标签、速度、方向、海拔、里程等时空信息，有的还有参考停车启动信息，以及隐藏在背后关于交通道路，司机对于实际地理位置信息等实际状况判断信息，深入挖掘这些信息对于提供LBS[32]服务将会有广阔的应用前景。例如在新浪微博、腾讯微博、微信等一系列LBS应用中在百度地图、新浪微博、微信、公交软件等一系列LBS应用中，用户可以不断的实时在地图上显示自己的位置和轨迹，朋友之间聚会时开启实时位置共享便可以看到好友的实时位置信息，司机在行驶途中也可以广播实时路况，这些信息都不仅生动展现了人们所处环境信息也帮助人们直观了解了未知区域信息，更为重要的是这些信息是实时的。但是若只是简单的分享位置信息、在[33]地图上展现信息并不能充分的挖掘这些背后隐藏的知识。通过轨迹聚类的方式可以挖掘出轨迹中的频繁模式，可以从海量的轨迹中蕴含的知识中发现有用的知识，这对于物流公司货运线路推荐、车辆调度和管理十分有意义。目前，海量轨迹聚类研究的问题包括两类。（1）怎样表示轨迹之间的相异度以及相异度的大小。用通俗的话说，相异度就是两个东西差别有多大，当车辆轨迹展示在地图上的时候，我们可以通过直观感受大体得到轨迹之间的相似程度，但是计算机没有这种直观能力，必须通过一些数学手段将我们人体直观感受到的区别大小定量的表示出来。（2）依据轨迹数据的特征和轨迹分析的需求，提出面向应用的轨迹特征概念和聚类方法。即在时空轨迹的定义、模型和表达方式的基础之上，针对不同[34]的分析需求采取不同的聚类算法和策略。综上，可以将轨迹聚类方法划分为轨迹表达、相似性度量和聚类算法三个[35]步骤。本文提出了如图4-1所示的轨迹聚类算法流程图。轨迹表达包括轨迹定[36]义和线性插值两部分。车辆轨迹数据是一系列的离散点序列连成的折线，可以d看作为一个映射ft:R,其中将物体在时刻tR的位置映射到一个d维的空间，一般是二维或者三维空间。车辆在实际运行中其实际轨迹是连续的，但是采集并存储在计算中的时候是离散化的，并且往往依据GPS采样频率的不同对轨迹进行线性插值，扩充轨迹语意表达。通过相似性度量可以确定轨迹之间的时空关系,设分别有两条轨迹A{,...,},aaaBbb{,...,}b，可以使用12nn1224万方数据 武汉理工大学硕士学位论文dAB(,)fAB(,)R表示轨迹A和B的距离，也即是相异度，其中R为实数域。聚类与分类不同，分类问题中类型信息是已知的，而在聚类问题中，类型信息是未知的，聚类问题将一个完成的数据集合分为若干组，组内有的数据尽可能的相似，组间的数据尽可能相异度越大。其中相异度由距离来表征。聚类是研究领域内的一个重难点问题，他需要以下若干个条件（1）可扩展性（2）兼容各种数据格式（3）能够容忍噪声。其中每个组叫做一个簇。轨迹聚类依据分析挖掘目的的不同，基于不同的相似性度量，选择不同基于密度、距离、统计等的聚类算法完成轨迹聚类从而发现常用轨迹模式。轨迹表达相似性度量轨聚轨迹类轨迹定义迹时空相似性聚结数线性插值类果图4-1轨迹聚类算法流程图4.2轨迹表达和相似性度量4.2.1轨迹规则化通常，在轨迹挖掘方法中，例如聚类算法中需要直接对数据进行加法、减法或矩阵运算等。然后轨迹数据是由一系列离散点组成，不同的轨迹有不同数量的轨迹点数据，因此直接对这些轨迹进行上述运算并不可行，一般而言，在轨迹挖掘方法中若需要对轨迹进行直接运算需要支持如下两种操作。distXY(,)distYX(,)|XY|（4-1）meanXY(,)meanYX(,)|XY|/2（4-2）其中X和Y分别代表任意两条轨迹。轨迹规则化可以将任意原始轨迹投影到统一的多维度空间以支持上述两种运算。在前面的章节中，已经提到过一条包含n个GPS点的轨迹可以描述为4-3所示，式中nZ和xy,[0,360]iiR{(,),(,xyxy),...,(,xy)}（4-3）1122nn25万方数据 武汉理工大学硕士学位论文x表示纬度，y表示纬度轨迹起始点为(,)xy，终点为(,xy)，若不考虑轨ii11nn迹方向，可以将轨迹表述如下：axbx[,xx)1112yaxbx[,xx)（4-4）2223axbx[x,x)33nn1其中yyii1aixxii1byaxiiiiab,R（4-5）iinZxy,[0,360]iiin[1,]纬度(,)xy(xy,)11nn11(,xy)(,xy)2266(,xy)(,xy)55nn(,xy33)(,xy44)经度度图4-2为式4-4描述的轨迹图该轨迹可以通过算法x将其投影到一个固定维数的特征空间中去。该算法的定义如下，S:GPS点所在平面。SS:平面逆时针旋转度。f():xS平面内的轨迹表达式。算法x的过程如下：（1）将平面坐标系统S分别旋转,构造两个平面坐标系统：S和S。（2）将平面S内的轨迹分别投射到S和S中。（3）在S中获取连续的j个抽样点[,,...,xxx],计算yf()x；同理在S中12nii'''''获取连续的j个抽样点[,xx,...,x]，计算得到yf()x。（4）经过上述步12nii26万方数据 武汉理工大学硕士学位论文骤后得到轨迹。'''R{,yy,...,yyy,,y,...,}（4-6）12jn12轨迹R可以看作为一个二维空间里面的曲线，属于一个参数集合{,,}j,和可以视为在二维空间内从两个角度去观测轨迹，j为轨迹的分辨率，j值越大，轨迹的表达越精确。图4-3为通过算法4-1得到的轨迹图。Yx5x2x4x1x6xy35y4Yy6yy31y2图4-3算法4-1得到的轨迹图轨迹规则化预处理算法如算法4-1所示。本文提出的算法4-2如下所示。通过规则化后，轨迹R依然保留了轨迹的走向趋势特征，这是因在上述的算法第三步过程中将原来处于平面S中的轨迹R转换为RRRRRii[(,xy),(,xy),...,(,xyxy),(x,其中yy)...(f()x,，因此轨迹)]1122jjj1j1j2j2jjA和轨B的距离可定义为：22iiAAAAdistAB(,)fxy((,ii),(,xyii))fgxy((,ii),(,gxyii))（4-7）ii11通过式4-7，显然可以看出gxx(,)是一个常数，因此在计算轨迹A和B之ii间距离的时候可是简化为：22iiABABdistAB(,)fgy((i,yi))dy(i,yi)（4-8）ii11AB其中dfg*，从式4-8中可以看出轨迹A和轨迹B的区别在于yy和，ii其中02ij，因此式4-6的轨迹保留了其轨迹走向特征。由于轨迹所在平面是二维空间，所以当需要描述二维空间中的一个物体形状的时候需要从两个角度去观测，所以本文将二维平面分别旋转,构造两个平面坐标系统S和S。27万方数据 武汉理工大学硕士学位论文此外,大小的选取也十分重要，在轨迹规则化过程中，必须使规则化后的轨迹信息中包含全部原始轨迹中形状和趋势信息。如图4-3中所示，一条完整的轨迹是一系列单向的GPS点组成，而轨迹的走向也反映到这些GPS点序列中，因此线性拟合这些折线可以获取得到轨迹的走向趋势信息。假若在原始平面中中。。线性拟合的直线与x轴之间的夹角为，则,分别为45和+135。Input:D,原始轨迹数据N,轨迹数据集中轨迹的条数M,单条轨迹数组Output：L，预处理后的轨迹数组Procedure:whileiNdowhilejMido[]ifx(x)0then21a(-)/(-)yyxx2121bxa*y11elsea0b0endifaddabxxintoT{,,,}12jj1endwhileaddTintoLii1endwhile算法4-1轨迹规则化预处理算法通过上述将轨迹R规则化以后，所有的轨迹可以看作为被投影到一个维度为2j的空间中，因此它们可以像二维平面中的GPS点数据一样运算。在现实世28万方数据 武汉理工大学硕士学位论文界中，当轨迹没有受到噪声等干扰时，大多数轨迹都是以一种或者多种模式反复出现，并且这些轨迹之间十分紧密。图4-4为通过PCA方法将轨迹数据降到Input:D,原始轨迹数据，L,轨迹数据集，xR,经度的右边界N,轨迹数据集中轨迹的条数M,单条轨迹数组，xL,经度的左边界Output：R，规则化后的轨迹数组Procedure：NM,ZTnulllistRnulllistinterval()xRxLwhileiNdoaddxLintervali*intoTendwhilei0j0z0whileiNdocurrentrouteithrouteasalistfromLwhilezNdosifcurrentsamplecurrentroutej[][3]thenaddcurrentroute([0]*currentsamplecurrentroute[1])intoRelsejj1endifendwhilezz1endwhilejj1endwhile算法4-2轨迹规则化算法29万方数据 武汉理工大学硕士学位论文三维后的--83.4GPS数据分布图，该图上有2个区域的点紧密聚集在一起，这说明有两地之间有两条常行驶路线。-8833..4-83.4535--83.4--83.45--83.5--137.4-83.55--137.5-83.6190.42190.43190.45190.46190.47190.48190.44-图4-4轨迹数据降到三维后的GPS数据分布图4.2.2轨迹相似性度量在分类的过程中，同样的输入轨迹样本采取不同的相似性度量准则的时候表征出来的相异度往往也不一样，因此合理采用相异度计算准则非常重要，否则即使本应该归为一类的轨迹也会因为距离计算方法不当而导致巨大差异，直到影响后续的聚类效果。通常，在空间计算中，距离可以依据不同数据集的特征来选择不同，但是不论何种计算方法，该方法必须满足如下三种条件：（1）distab(,)distba(,)；（2）distab(,)distbc(,)distac(,)；（3）distab(,)0。本文主要讨论如下三种定义距离的方法。假设有两条轨迹X和Y分别通过规则化后得到为[,,...]xxx和[,yy,...]y，12k12k并且定义yx为轨迹第i个点之间的距离。ii(1)欧氏距离k2distXY(,)i1(xiiy)（4-9）多维空间中点与点之间的距离常用该方式计算，它表示其真实距离，在轨迹计算中，两个点的欧式距离即为真实地理上的距离。在二维空间中的欧氏距30万方数据 武汉理工大学硕士学位论文离就是两点之间的直线段距离。欧式距离看作轨迹的相似程度，通常在大多数情况下，距离越近就越轨迹就越相似,但是也有不适用情况，如图4-5所示，如果使用欧式距离，轨迹A和轨迹B的距离显然更大，切比雪夫距离可以很好的处理这种状况，但是在大多数状况下，欧氏距离依然是一个很好的选择。ABC图4-5欧式距离不适用情况示意图（2）曼哈顿距离kdistXY(,)|xiiy|（4-10）i1曼哈顿距离是一种几何学的欧几里得距离，是一种新的衡量标准两点之间的距离，它采用两点的绝对笛卡尔坐标的差异。在实际应用中，轨迹数据中通常存在噪声，而这些噪声往往属于正态分布，因此曼哈顿距离可以有效的修正轨迹中存在的正态分布的噪声所造成的误差。如图4-6为曼哈顿距离不适用情况示意图，显然轨迹A和B是不同的，但是它们之间的距离并不为零，可见曼哈顿距离并不使用所有情况。AB图4-6为曼哈顿距离不适用情况示意图（3）切比雪夫距离distXY(,)max(|xy|)（4-11）iii切比雪夫距离是一种描述向量之间距离的方式，它用两个向量之间坐标差异最大值表示。这中计算距离的方式有很好的抗噪声性能，轨迹是否平行也有很好的距离表示性能。图4-7为切比雪夫距离示意图。31万方数据 武汉理工大学硕士学位论文AdB图4-7为切比雪夫距离示意图以上三种距离定义方式，都能在一些场景下适用于轨迹间的距离定义，本文基于轨迹规则化的结果，采用了欧氏距离的定义距离方式，可以有效的消除类似图4-5所示的误差状况。4.3轨迹聚类4.3.1常见聚类算法比较聚类是将一个集合分为若干个子集合的过程，每个子集都是一个簇，每一个簇内的对象都是相似的，簇间的数据对象并不相似。关于聚类已经有了很多不同的算法。聚类的过程是由聚类算法实现的，而不是人实现的，因此通过聚类算法可以发现未知的簇。在海量轨迹数据挖掘中，它可以发现常出现的轨迹模式。作为统计学的一个分支，聚类分析被广泛的研究和应用，聚类算法本身也必须满足一些要求才能真正达到将数据聚类的效果，这些因素包括对于不同属性数据类型必须有可扩展，可以抗噪声，能发现不同聚类形状的数据簇。有很多种聚类算法，这些方法之间很难有一个明确的界限，因为这些算法互相之[37]间有交叠的部分，通常有如下几种聚类算法。分割方法：给定一个有n个数据对象的集合，将这个集合分割为k个部分，其中k