基于轨迹相似度的轨迹推荐算法分析研究计算机科学与技术专业.docx

摘要1前言3第一章绪论41.1 研究背景及意义41.2 本文的主要工作和创新点51.3 本文的组织结构5第二章轨迹数据压缩算法72.1 降采样方法72.2 Douglas-Peucker算法82.3 离散傅里叶变换算法102.4 分段聚合近似算法112.5 基于速度和方向的轨迹压缩算法122.6 基于GeoHash的数据点压缩算法13第三章轨迹相似度度量标准153.1 距离度量函数153.2 欧几里得距离153.3 DynamicTimeWraping163.4 LongestCommonSubsequences173.5 EditDistanceonRealSequence18第四章轨迹数据的存储方法194.1 对空间点的存储方法194.1.1 R树系列194.1.2 KD树系歹IJ204.2 对时间序列的存储方法204.2.1 对点的倒排索引204.2.2 对特征维度的索引21第五章基于轨迹相似度的轨迹推荐方法225.1 相似度模型225.2 索引策略235.3 算法流程245.4 实验和分析25第六章总结与展望286.1 总结286.2 展望28参考文献30致谢错误!未定义书签。摘要本文以轨迹推荐问题为突破口，研究并分析了轨迹的压缩方法、轨迹相似度度量标准、轨迹特征提取算法以及轨迹索引查询方法等，并且综合了已有方法的优势,针对已有方法的不足，设计了一套基于轨迹相似度的轨迹推荐算法，保证了高效而准确的相似轨迹的推荐。具体的说，本文开展了以下研究：1 .一种轨迹数据的特征提取算法。现有的对于轨迹数据的特征提取算法大多没有考虑的轨迹数据的存储和索引。这些提取出来的特征虽然能够从一定程度上对轨迹数据进行了降维，但是这样的特征提取也只能算是一种数据压缩，我们不能在保证没有漏检的情况下使用这些特征。而本文提出的方法则既能保证数据的压缩效果，也能保证没有漏检情况的发生。2 .基于轨迹相似度的轨迹数据的推荐方法现有的轨迹推荐算法大都是基于机器学习算法，对轨迹数据进行聚类，或者建立用户画像，在拥有相同用户画像的相似用户之间互相推荐轨迹。本文在上面的轨迹数据的特征提取算法的基础上，设计了一套基于轨迹相似度的轨迹推荐算法，单纯的从轨迹相似的角度为用户推荐轨迹数据。关键词：轨迹相似度；文件索引；特征提取；轨迹压缩；相似度查询AbstractThispaperstudiesandanalyzesthetrajectorycompressionmethod,thetrajectorysimilaritymetric,thetrajectoryfeatureextractionalgorithm,andthetrajectoryindexquerymethod,andintegratestheadvantagesoftheexistingmethods.Atrajectoryrecommendationalgorithmbasedontrajectorysimilarityisdesignedtoensuretheefficientandaccuratesimilartrajectoryrecommendation.Specifically,thisarticlehascarriedoutthefollowingresearch:1. Afeatureextractionalgorithmfortrajectorydata.Mostexistingfeatureextractionalgorithmsfortrajectorydatadonottakethestorageandindexingoftrajectorydataintoaccount.Althoughtheseextractedfeaturescanreducethedimensionofthetrajectorydatatosomeextent,suchfeatureextractioncanonlyberegardedasakindofdatacompression.Wecannotusethesefeatureswhichmaycausefalsedismissal.Themethodproposedinthispapernotonlyguaranteesthecompressioneffectofdata,butalsoensuresthatnofalsedismissaloccurs.2. RecommendedmethodfortrajectorydatabasedontrajectorysimilarityMostoftheexistingtrajectoryrecommendationalgorithmsarebasedonmachinelearningalgorithms,clusteringtrajectorydata,orcreatinguserportraits,andrecommendingtrajectoriesbetweensimilarusershavingthesameuserportrait.Inthispaper,atrajectoryrecommendationalgorithmbasedontrajectorysimilarityisdesigned,whichsimplyrecommendsthetrajectorydataforusersfromtheperspectiveoftrajectorysimilarity.Keywords:TrajectorySimilarity;FileIndex;FeatureExtraction;TrajectoryCompression;SimilarityQuery前三近年来，随着无线定位设备的广泛使用，我们能够越来越方便的获得由这些定位设备发送的定位数据。这些数据通常由经度、纬度、高度和其他辅助信息组成。这些数据给我们带来了大量的研究价值，但是同时也给我们的计算和挖掘能力带来了巨大的挑战。庞大的数据量要求更好的数据存储能力、更快的数据计算能力和更高的数据结构设计能力。同时，如何对这些数据进行高效地应用也是一个复杂的问题。当前.，学术界对轨迹数据挖掘的研究正得到越来越多的重视。对于轨迹数据相似性问题的研究可以追溯到度时间序列相似性问题的研究。时间序列相似性问题的最早研究论文由Agrawal等人在1993年发表。起初加入研究行列的有IBM公司的Agrawal和UCIrvine的一些研究小组，在最近一段时间内则UCRiverside的EamonnKeogh和CarnegieMellon大学的ChristosFaloutsos领导的研究小组则更加活跃。除此之外，UCSantaBarbara大学、Maryland大学、NewYork大学、SimonFraSer大学等都有对相应进行研究的研究小组。国内的相关研究近年来势头强劲，其中有清华大学、复旦大学、浙江大学、中国科技大学、西安交通大学、香港大学、香港城市大学等。而且不仅在学术界，在工业界也逐渐展开了对轨迹序列的相似性问题的研究。知名的研究机构包括Yahoo、IBM、Google以及美国国家航空航天局NASA等。这些公司都有很多专职人员参与本问题的研究。一些资深的数据挖掘领域人士甚至认为，对轨迹数据的挖掘已经成为目前数据挖掘中最具挑战性的问题之一。以经典的轨迹数据相似性查询问题为例，如何既保证查询的效率，又能保证查询的准确性一直是一个值得权衡的问题。在很多情景下，我们为了保证查询的准确性，我们需要牺牲查询的效率，采用全表查找等形式；在有的情形下我们可能不太关注查询的精确度，这样我们就可以通过粗略查找或者近似查找的方法，降低算法复杂度提高查询的效率。为了同时提高算法的准确率和执行效率，本文对轨迹数据的压缩、存储和轨迹数据相似度度量标准进行研究，以设计一个高效的基于轨迹相似度的轨迹推荐算法为主要研究课题。第一章绪论本章首先介绍了轨迹存储与推荐算法的研究背景和意义，其次概括了本文做的主要工作和贡献，以及主要的创新点。最后介绍了本篇论文的组织结构。1.1 研究背景及意义时间序列挖掘研究自从上世纪90年代提出以来，得到了国内外的广泛关注，成为研究的热点领域之一。它包括时间序列的相似性搜索、聚类、分类、模式匹配、规则发现、异常检测等各个方面。轨迹数据是时间序列的一种特殊形式，通常由经度、纬度、高度和其他辅助信息组成，已经成为诸如经济、管理、计算机、数学、电子等诸多学科的交叉研究范畴。轨迹数据相似性问题也是时间序列挖掘中的一个基础问题，它的主要研究内容是判别轨迹数据是否相似、如何衡量相似程度、如何比较轨迹的相似等，它的外在表现是轨迹数据的相似性搜索。随着各种无线通信和定位技术的高速发展，人们可以非常方便地收集到大量轨迹数据。轨迹数据具有很高的应用价值，人们可以进行通过运用这些数据进行相应的数据分析来实现很多重要的功能。如根据日常活动轨迹，我们可以向人们推荐潜在的朋友；根据动作的轨迹，我们可以进行人们动作目的的识别；根据已有的车辆轨迹，我们可以向驾驶员推荐最为流行的行车路线等。相似轨迹查找是对轨迹数据进行充分运用的基础功能之一，即要求对于给定的某个时间序列，从大型数据集合中找出与之相似的时间序列1,主要包括轨迹相似度度量、轨迹数据压缩、轨迹数据存储、轨迹推荐等。但是，由于轨迹数据获取的方便性，轨迹数据的规模也在呈几何数量地增加。因此如何更快、更好、更高效地进行轨迹查找就成了现阶段的一个巨大的挑战。更快，就是要求能够尽可能减少单次查询的时间消耗；更好，就是要求查询的结果更加符合给定的要求；更高效，就是指将空间和性能运用在更有价值的地方。近几年，相似轨迹的查询研究有了很大的进步，提出了很多有效的算法。在轨迹压缩方面，提出了通过减少轨迹点的冗余度来加速轨迹查询的各种轨迹压缩算法，代表性的有DOUgIaS-PeUCker算法2、离散傅里叶变换方法、奇异值分解方法3、滑动窗口法等。在轨迹相似度度量方面，提出了通过设计更优化的相似度度量标准来节约时间的各种下限算法，常用的算法有LB_Kim5、LB_Yi6>1.BjeeOghr7、LB_PAA8等。在轨迹存储方面，提出了通过设计更加优秀的索引结构和搜索树来加快查找的过程。上述的各种方法各有优缺点，我们将在第二章到第五章中进行详细地分析说明。1.2 本文的主要工作和创新点本文总结并分析了目前较为流行的轨迹数据加工处理的方法，详细研究了各种轨迹压缩技术、轨迹相似度度量标准、轨迹特征提取算法以及轨迹索引查询方法等,分析了各自的应用场景和优缺点。并提出了一套高效的对相似轨迹进行查询的方法。和原有算法相比，该算法具有如下创新：(1)基于文件索引。不需要同时将所有数据读入内存，适合对大量数据进行查找。并且利用索引文件，不需要进行全表查找，可以更高效地进行查找，有效提高了查询效率，减少了查询时间。(2)支持增量添加数据。在数据集扩大时不需要重新构建索引，只需要按照规则将新添加的数据加入数据集即可，具有较强的扩展性。(3)不会出现漏检(FalseDismissal,FD)的情况。为了提高数据的查询效率，当前很多查询方案都将类似KNN(kNearestNeighbor)的问题描述为ANN(APProXimateNeareStNeighbOr)问题。由于不需要保证结果的绝对准确性，所以ANN问题的解决速度比KNN问题快得多，但是代价就是要牺牲准确率，他无法保证检索出最合适的结果，而是一个较为合适的结果。本文提出的方案既可以保证高效率，也可以杜绝漏检情况的发生。(4)支持不等长轨迹数据的比较。即使是轨迹数据长度不同，该算法也可以高效的进行比较以及索引。本文利用的MSRA(MicrosoftResearchAsia)提供的GeoLife数据集9-11对本文提出的方法进行了仿真实验，并与当前已有的方法进行了对比分析，验证了本文提出的方法的正确性和高效性。1.3 本文的组织结构本文共分为六章，各章节的安排如下：第一章为绪论。本章首先简要介绍了本文所涉及的研究课题的背景、意义、实际应用等。然后概括了本文的主要工作和创新点，最后阐述了本文的组织结构。第二章：轨迹数据压缩算法。本章主要介绍了当前主流的轨迹数据压缩算法,并且分析了各个算法的优劣和应用场景。第三章：轨迹相似度度量标准。本章主要介绍了收到学术界广泛认可的相似度度量标准以及这些度量标准的优化版本、下界版本。第四章：轨迹数据的存储方法。本章主要介绍了用于存储轨迹数据的数据结构以及常用的查找方法。第五章：基于轨迹相似度的轨迹推荐方法。本章主要介绍了本文提出的基于轨迹相似度的推荐算法，同时通过实验加以对比分析。第六章：总结与展望。总结全文，提出未来工作的设想与展望。第二章轨迹数据压缩算法通常而言，大多数的轨迹数据都是通过传感器定时采集物体的运动状态，并将数据进行存储。由于传感器的采样率不同，数据获取的密度也有所差异。大多情况下，对于车辆轨迹的采样间隔是秒级的，而对行人轨迹采样的间隔大约是分钟级的。在这种采集频率下，每一辆车一天就大约可以采集到4GB左右的数据，而每一个行人每一天就大约可以采集到160GB的轨迹数据。这导致了采集得到的轨迹数据的规模非常大，其中很多轨迹点包含了很多的冗余信息，有效信息较少，没有存储的必要性。为了能够减少存储时的总数据量，并提高存储的每一个点的有效性，现阶段提出了很多轨迹数据压缩方法。本文详细阐述了目前广泛使用的一些轨迹数据压缩算法，并对它们进行了对比分析，分别阐述了它们的优势和缺点，以及在实际生活中适用的场景。2.1 降采样方法减少一条轨迹中轨迹点的个数最简单而直观的方法就是降低采样率。比如对于一个可控的采样设备，原本是每隔五秒钟获取一个坐标数据，使用降采样方法，可以修改为每隔一分钟获取一个坐标数据，这样数据量就减少为了原先的十二分之一。通过讲采样时间间隔改为更大的树枝，可以达到获取较少的轨迹数据的目的。对于采样率固定的设备，无法更改采样时间，可以通过一些数据过滤算法对数据点进行过滤。通常来说，数据过滤方法可以分为两种：(1)在线过滤。这类方法主要适用于一些不停获得的流式数据。这些数据的重要级别通常比较低，因此可以设置一个较低的采样率，让存储设备每隔N个数据存储一次，这样数据量就可以缩减到原来的1/M有时候为了减少舍弃的轨迹点造成的影响，可以设置一个缓存窗口，每当获得一个轨迹点，就将这个轨迹点添加进缓存窗口。当窗口满了的时候，计算窗口里所有轨迹点的平均值，得到相应的平均点，将这个平均点加入最终的轨迹序列，并且将缓存窗口清空。(2)离线过滤。这类方法主要适用于数据已经完全获取的情况。该类算法通过对存储的轨迹点进行随机采样，或按照固定间隔进行删减，达到压缩存储的轨迹点个数的目的。降采样方法非常的简单、易用、可靠。在大多数场景下都能使用，而且可以精准的控制压缩后轨迹点的个数，非常便捷。但是该类算法常常受到个采样率的选择的影响。在不同场景或是相同场景的不同阶段，采样率的最佳选择都会有所差异。如果将采样率设置得太低，那么将会有大量的轨迹点丢失，和原始轨迹出入较大；如果将采样率设置得太高，那么仍然保留了很多冗余的数据，压缩不完全。而且由于删减轨迹点方法常常带有随机性，很容易将一些重要的轨迹点删除，导致压缩后的轨迹失去了某些重要的特征。总而言之，由于降采样的方法简单，高效，适合快速地将一些稠密的轨迹点变得稀疏，所以比较适合用于对轨迹做初步的压缩。2.2 Douglas-Peucker算法Douglas-Peucker算法12是一个经典的轨迹数据压缩算法，弥补了朴素降采样方法容易使轨迹失去关键特征的不足。该算法的原理是只删除对轨迹特征影响比较小的点，从而保证能够保留轨迹的绝大部分特征。Douglas-Peucker算法的具体步骤如下：输入：T 输入：i 输入：/ 输入：£ 输出：Douglas-Peucker算法条轨迹轨迹起点的序号轨迹终点的序号预设的误差阈值压缩之后的轨迹1. functionDOUGLASPEUCKEREijQ2. 找出pi+p中距离线段哂最远的点P.,并设这个距离为由St3. ifdist>DOUGLASPEUCKERiT,i,f,)DoIJGLASPEUCKERGfj6)输出哂以呵作为近似轨迹通过一个例子对DoUgIaS-PeUCker算法进行简单的说明。给定一个轨迹序列T=<p0.plfp2，.，Pi6>，首先连接PO和Pi6，分别计算剩余点到这条线段的垂直距离,如图2.1(a)所示。从图2.1(a)中可以看出，pg离这条线段的距离最大，那么就选择该点作为下一个分段点，将这个轨迹分割为PoP%P9P16两部分，如图2.2(b)所示，(a)步骤一(b)步骤二(c)步骤三图2.1DoUglaS-PeUCker算法步骤然后对这两个部分递归这个过程，于是又将该轨迹分成了四段，如图2.3(C)所示。假设到此为止，所有的点到他所属的连线的距离均小于阈值£,那么这个时候，就可以用PoP3P9P16表示整个轨迹。从图2.1中可以看出，虽然轨迹点的数量大大减少了，但是压缩后得到的轨迹点仍然能够较好地保持了原先轨迹的特征。DOUgIaS-PeUCker算法通过计算，在轨迹压缩的同时，也有选择地保留维护轨迹最大特征的轨迹点，很大程度的消除了冗余的轨迹点。同时这个算法的压缩程度也是可控的，压缩率也可以与轨迹的还原率成正比。但是该算法的时间复杂度为0(n2)f相较于其他轨迹压缩算法，运行速率较慢。虽然也有一些相关的加速算法13,能够将该类算法的复杂度优化到。(汨。92九)，但是优化后的算法的灵活性就下降了很多。同时，如果阈值设置对DoUglaS-PeUCker算法也有很大的影响。2.3 离散傅里叶变换算法离散傅里叶变换算法14也经常用来对时序数据进行将降维。离散傅里叶变换本质上是一种谱分解算法，理论上可以用多个正弦波去拟合任何一个函数。因此对于一个长度为的时间序列，可以通过个正弦波来组合还原。由于这个正弦波所占的比重不同，可以去掉这当中对轨迹贡献较小的那些正弦波，用留下来的波来表示整个序列。离散傅里叶变换算法特征分解如图2.2所示。图2.2离散傅里叶变换的特征分解图从图2.2可知，对于给定一维序列X,我们可以通过将四条正弦波按不同权重进行加权得到X',并用X'作为X的近似序列。在数据压缩的同时，也很好地保留了X的重要基本特征。但是，由于轨迹数据并不是单纯的一维时间序列，而是二维时间序列，因此需要分别对时间序列的两个维度都进行离散傅里叶变换。原始离散傅里叶变换算法的复杂度是0(N2),快速傅里叶变换可以将算法复杂度优化到O(NIogN)Q离散傅里叶变换比较适合拟合运动变化较为频繁的轨迹，对于行人或者车辆这种方向变化不大的轨迹压缩的效果并不是特别好。所以在实际运用中，离散傅里叶变换通常被用于一维的时间序列的压缩而很少被用来做轨迹数据的压缩。2.4 分段聚合近似算法分段聚合近似(PiecewiseAggregateApproximation,PAA)是一个非常经典的对轨迹数据进行压缩近似的算法。该算法的目的是对于一条给定的长度为的轨迹T=(%,y),(%2，、2)，(Xi，%)，将它压缩为一个长度为几'的轨迹7'，其中"九。那么分段聚合近似算法即首先对轨迹段进行平均分段，然后对每一个分段求一个平均值作为最终结果的一部分。具体的计算方法如下：Nn)ixi=nXj(21)NJ=Nn(i-l)+l1.(Nn)iYi=N*(22)可以通过控制71'的值来控制压缩的比例以及还原度的比例。当几'越大时，还原度越高，压缩率越低；当优越小时，还原度越低，压缩率越高，当n，缩小到1的时候，轨迹就退化成了一个轨迹点。对图2.3中的轨迹X,我们采用分段聚合近似来将其分割成八段，最终组合成近似轨迹X',如图2.3所示。可以看出，分段聚合近似组成的轨迹还是能够从整体上保证轨迹的特征不会丢失，而且计算的复杂度比较低，相比之前算法动辄O(N2)的复杂度，他只需要O(N)即可完成压缩。不过在每个分段求平均值这个做法很有可能会带来“平均值陷阱”，使得该分段内的极大和极小的特征被平均化了，从一定程度上会导致特征的丢失。图2.3分段聚合近似特征分解图2.5 基于速度和方向的轨迹压缩算法基于速度和方向的轨迹压缩算法是专门用于车辆轨迹这种带有明显的方向和速度特性的轨迹的压缩。原始的轨迹压缩算法仅仅考虑轨迹的几何特征，而没有考虑轨迹本身的含义。对于车辆轨迹而言，驾驶员关注的不是自己的历史轨迹，而是自身的方向和速度，因此可以根据这个特性，使用基于速度和方向的轨迹压缩算法对轨迹进行压缩15。轨迹压缩算法需要事先设定速度阈值和方向容忍度阈值。根据这两个阈值可以从前一个轨迹点预测出下一个轨迹点应当出现范围。如果新的轨迹点落在这个范围内，则将这个新的轨迹点舍弃，否则就将新的轨迹点加入最终的近似轨迹中，如图2.4所示图2.4基于速度和方向的轨迹压缩算法示意图首先设定一个速度的范围，比如设置速度区间为。力,然后设定一个角度的旋转区间6。对于上图中的这条轨迹丁=<P1,P2,P3,P16>，首先将PoPl加入压缩后的轨迹集，然后延长PoPi,通过之前设定的速度区间和角度旋转区间，以及Pl到P2的采样时间隔的时间，可以预测出P2点允许出现的扇形区域。如果P2确实落在这个扇形区间，就说明P2这个点具有的信息量有限，没有存储的必要，则舍弃该轨迹点,从而达到轨迹压缩的目的。在图2.4中，轨迹点2295/6/8*11912必3邛14邛15都可以根据如上原则被删除，从而得到压缩后的轨迹。基于速度和方向的轨迹压缩算法相较于之前的轨迹压缩方法，可能会保留更多的轨迹点，但是这种算法压缩后的轨迹不仅保留了原轨迹的形状信息，而且保留了原轨迹的方向和速度信息。同时该算法的复杂度只有。(N)。2.6 基于GeoHash的数据点压缩算法轨迹数据是时间序列数据的一种，但是与时间序列数据有所差异，即时间序列数据除了时间维度之外可以看成是一维的，而轨迹序列中承载的数据却是一个二维（经度、维度），甚至是三维（高度）的。因此为了方便后期的比较，可以先将一个二位数据点压缩成一个一维的数据。将二维数据转化为一维数据最经典的模型就是皮亚诺曲线。皮亚诺曲线是一个曲线序列的极限，一个能填满一个封闭图形的不可导的曲线。与皮亚诺曲线有异曲同工之妙的就是GeoHash算法。GeOHaSh算法首先将地球作为一个大的区域，然后这个区域沿着东西、南北方向分别进行二分，对每一个子区域进行编码；然后再对每一个子区域进行二分，再编码重复这个操作，直至精度满足给定的要求。这样每一个坐标点（其实是一个近似于点的区域）就对应于一个数值，可以用这个一维的值来代替二维的坐标点。以经纬度值（116.389550,39.928167）为例。首先对纬度39.928167进行逼近编码。具体如图2.5所示。纬度范围划分区间O划分区间139.92321(-90,90)(-90;0.0)(OQ90)12(0.0,90)(OQ45.0)(45.0,90)O3(OQ45.0)(0.0122.5)(22.5,45.0)14(22.5,45.0)(22.5?33.75)(33.75,45.0)15(33.75j45.0)(33.75,39.375)(39.375,45.0)16(39.375j45.0)(39.375r42.1875)(42.1875,45.0)O7(39.375,42.1875)(39.375140.7812)(40.7812,42.1875)O8(39,375?40,7812)(39.375r40.0781)(40.078L40.7812)O9(39.375,40.0781)(39.375139.7265)(39.7265,40.0781)110(39.7265,40.0781)(39.7265,39.9023)(39.9023,40.0781)111(39.9023,40.0781)(39.9023,39.9902)(39.9902540.0781)O12(39.9023,39.9902)(39.9023,39.9462)(39.9462y39.9902)O13(39.9023y39.9462)(39.9023,39.9243)(39.9243,39.9462)O14(39.9023,39.9243)(39.9023,39.9133)(39.9133：39.9243)115(39.9133,39.9243)(39.9133,39.9188)(39.9188j39.9243)1图2.5GeoHash算法编码示意图根据图2.5可以看出，在精度等级为15时，纬度部分的GeoHash编码值是uIio100ioi100oiov,同理,经度部分的编码值就是“理Iiio度IloooI1”。然后将经度和维度的编码值交叉组合，经度的编码放在偶数位，维度的编码放在奇数位，并且将得到的Ol串转化为十进制数字，再转化为base32编码，即可得到这个坐标点对应的GeOHaSh编码“wx4ge”°将这些编码值从大到小进行连线，可以发现这其实就是填充了整个平面的Z阶曲线，如图2.6所示。Z茏图2.6GeoHash算法的Z阶曲线GeoHash能够在精度允许的范围内将二位数据有效压缩为一维数据，但是美中不足的是GeoHash编码无法保证二维坐标相邻的点的编码值也相邻，因此并不方便做索引。从图2.6中，我们可以看出相邻的点基本保持相邻关系，但是仍然存在一些，突变，的位置。如果在轨迹查询的时候查询到了这些轨迹点，那么就很容易出现漏检的情况。由于GeoHash简单、快捷、节约存储的特点，在对查询精度要求不高的情况下，GeoHaSh的用处非常多。但是如果场景对查询精度有要求，那么Ge。HaSh可能表现效果不佳。第三章轨迹相似度度量标准如何衡量两条轨迹之间的相似性是相似轨迹进行查询时的核心问题之一。由于在不同场景下轨迹查询的侧重点不同，因此相似度度量标准也不同。在本章，我们对一些常用的相似轨迹度量标准进行分析说明。3.1 距离度量函数首先给出关于轨迹的距离度量函数的定义：对于给定的一个定义在轨迹数据上的空间T,以及任意两条7中的轨迹X与>7上的距离度量函数d定义为：dT×TR(3.1)其中R是实数空间，且d具有如下性质：(l)d(%,y)O(非负性)(2) d(x,y)=0<=>X=y(自反性)(3) d(x,y)=d(y,x)(对称性)(4)(可选)d(x,y)d(x,z)+d(z,y),Vx,y,zT(三角不等式)前三条性质是距离函数的必备条件，且比较容易满足。最后一个三角形不等式性质很多距离度量函数较难满足。在大多数情况下，三角形不等式的性质不是距离函数的必备条件。但是严格来说，如果一个距离度量函数不满足三角形不等式，那么它的价值相对较低，因为不满足三角形不等式的距离函数无法满足通常所理解的“两点之间直线最短”的概念，这也意味着它不存在极限唯一性，所以不能用来做索引比较。因此，如果说一个函数能够满足上述的定义，那么就认为它是一个合格的距离度量函数。3.2 欧几里得距离欧几里得距离是一个非常经典的距离度量单位，也被一直用来进行轨迹之间的距离度量。欧几里得距离的定义如下：给定两条长为的时间序列A与3,它们之间的欧几里得距离定义为：eud(A,B)=L1(l-bi)2(3.2)其中Qi和瓦分别是时间序列A与B的第i个元素。显然，轨迹间的欧几里得距离其实就是计算两个长度相同的轨迹中对应点的距离，并求和归一化。欧几里得距离是Wrm的一个特例。LP-几Orm定义为：Ip-norm(4B)=°企匕(Qt-九)，(3.3)当p=2的时候，就是欧几里得距离。类似的，当P=I时，。一九OrTn是曼哈顿距离，当P=8的时候，Z00-norm就变成了：nIoonorm=max(Iai-bj)(3.4)i=1欧距离以及，P-Tiorm已经被广泛的作为相似轨迹的度量标准，这种方法计算简单，物理含义直观，而且复杂度较低。不过它们只能够用来比较两条轨迹长度相同的轨迹，对于轨迹长度不同的两条轨迹，便无法使用了。3.3 DynamicTimeWrapingDTW(DynamicTimeWraping)最先被用于语音识别，能够比较好地处理局部时间偏移，计算两条不等长的序列之间的距离。DTW距离定义如下：tifm=Oorn=O(3.5)DTW(Rest（八）,ReSt(B)dist(a1,b1) + minDTW(ReStG4),B),elseDTW(A,Rest(B)其中m和/i分别时间序列A与B的长度，ReSt（八）表示出去除去第一个点后的序列A,ReSt(B)表示除去第一个点后的序列B,disM%,瓦)表示这两个点之间的距离，通常是欧氏距离。如图3.1所示，DTW能通过对某些点进行复制，从而计算出不等长时间序列之间的距离，从而反应出两个序列之间的相似程度。但是由于DTW距离的时间复杂度为0(nm),当序列长度变长时，计算的性能会很差。针对DTW较高的时间复杂度的问题，国内外的研究人员也提出了很多优化算法，比如LB-Keogh16,LBJmproved170这些优化算法基本是通过限制两个匹配点之间的范围差来计算一个标准DTW的下限，但是这些算减小时间复杂度的同时，也牺牲了精度。DTW算法能够非常方便的比较两个不等长轨迹的“距离”，因此在实际使用中应用非常广泛。但是它有一个致命的缺陷，就是DTW距离并不满足三角形不等式，因此从严格意义上讲，并不是一个好的距离度量单位。图3.1DTW算法轨迹点匹配示意图1.ongestCommonSubsequences1.CSS(LongestCommonSubsequences)算法通常被用于带有噪声序列的降噪处理18。该算法通过比较给定的两条序列之间的对应点来完成降噪处理，它的具体定义如下：O1ifTn=Oorn=01.CSS(ReStG4),ReSt(B)+1,ifdist(a1,b1)<©6)max(LCSS(ReStG4),B),LCSS(A,ReSt(B),else1.CSS算法常被描述为相似度度量标准，而不是距离度量标准，所以为了将相似度度量标准转换成距离度量标准，需要做如下处理：LCSSdist(AfB) = I-LCSS(AB)min(4,B)(3.7)1.CSS算法需要一个阈值£来判断两个点是否在误差允许的范围内。从公式(3.7)中我们可以看出，LCSSdis0,1,而且数值越大，说明这两个轨迹越相似。1.CSS算法有一个极佳的特性就是它能够消除异常值带来的影响。DTW算法和欧氏距离中计算过程中每一个点都会对影响最终的计算结果，而LCSS算法会有选择的放弃一些误差较大的点，减小部分点对最终结果的影响。不过LCSS算法执行的复杂度是O(IAl*B),时间运行效率比较低，而且LCSS也不支持三角形不等式，无法方便地进行索引比较。EditDistanceonRealSequence1.CSS算法能够有效地降低异常值带来的影响，但是却不能区分具有相同子序列但是大小不同的轨迹。因此LeiChen等人19提出了EDR(EditDistanceonRealSequence)函数作为新的距离度量标准。EDR距离定义如下:n,ifm=0m,ifn=0EDR(A1B)= <EDR(ReStG4), ReSt(B) +0,ifdistHeadCA),Head(B')y)e1,elsemin<EOR(4Res亡)+1EDR(Rest（八）fB)+1(3.8)EDR也需要一个最小距离阈值E来判断两个点是否是同一个点。由于EDR能够匹配间隔不相同的两个轨迹，因此比LCSS更加准确，也更加具有代表性，不过相较于其它算法，EDR的时间复杂度并没有什么优势。第四章轨迹数据的存储方法为了能够更高效的对轨迹数据进行查找，需要对轨迹数据进行存储和检索。从本质上讲，轨迹数据其实可以看成是时间序列和空间点的结合，而无论从时间序列,还是空间点的角度上讲，我们都需要一个能够索引多维数据的数据结构。本章将会对一下目前常用的对多维数据进行存储的方法进行分析。4.1 对空间点的存储方法对空间点进行存储的方法目前在业界已经比较成熟，绝大多数主流数据库都支持对多维数据的存储和索引。而且随着相关方面研究的深入，提出了很多优化算法。不过总体来说，存储和索引方法通常基本是围绕两个基本模型进行深入优化的：一个是R树，另一个就是KD树。4.1.1 R树系列R树是GUTTMAN于1984年提出的最早支持有序扩展的对象存取方法之一，并且也是目前为止应用最为广泛的一种空间索引结构。许多人们耳熟能详的空间数据库系统，比如OraCleSpatial,PostgreSQL和MapInfoSpatialWaro等均提供对R树的支持。同时，在R树的基础上也提出了很多优化算法，最著名的有R+树、R*树等。R树是一个高度平衡树，它可以看成是B树在K个维度上的自然扩展。它用空间对象的MBR(Minimumboundingrectangle)来近似表达空间对象，根据物体的MBR建立R树，我们就可以直接对在空间中占据一定范围的空间对象进行存储和索引。空间对象的MBR被包含于R树的叶结点中。在R树空间索引中，可以设计一些虚拟的矩形目标，将一些空间位置相近的目标，包含在这个矩形内。这些虚拟的矩形作为空间索引，它将含有所包含的空间对象的指针。虚拟矩形还可以进一步细分，即可以再套虚拟矩形形成多级空间索引。在R树的构造中，我们要求虚拟矩形要尽可能少地重叠，并且要求一个空间对通常仅被一个虚拟矩形所包含。但是空间对象千姿百态，它们的MBR经常重叠。R+树改进了R树的空间索引，为了平衡，它允许虚拟矩形相互重叠，并允许一个空间目标被多个虚拟矩形所包含。R*树都是完全动态的，插入、删除操作可以与查询操作混合进行，而且不需要进行定期的全局重建。它允许不同子树的最小外包矩形发生重叠，因此这种结构在进行精确匹配搜索的时候会产生多条搜索路径。R*树的性能都比其他R树变种高。对于点数据的访问，它的性能提升更加明显。R*树主要是考虑降低面积、边长、路径矩形的重叠，R*树即使面对分布非常不规则的数据时也能表现得十分稳定。又由于强制插入算法的使用，避免了不必要的分裂，这样一来，R*树就得到了动态的重构，使得存储效率得到了提升。但是R*的实现代价仅比R树的