基于轨迹相似度的轨迹推荐算法分析研究计算机科学与技术专业.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)支持不等