基于轨迹相似度的轨迹推荐算法.docx

本科毕业设计（论文）学院(部)计算机科学与技术学院题目基于轨迹相似度的轨迹推荐算法年级2014级专业软件工程班级计14软件1班学号1427406034姓名丁庆祝指导老师刘安职称副教授论文提交日期2018年5月19日苏州大学本科生毕业设计（论文）31目录摘要1前言3第一章绪论41.1研究背景及意义41.2本文的主要工作和创新点51.3本文的组织结构6第二章轨迹数据压缩算法72.1降采样方法72.2Douglas-Peucker算法82.3离散傅里叶变换算法102.4分段聚合近似算法112.5基于速度和方向的轨迹压缩算法122.6基于GeoHash的数据点压缩算法13第三章轨迹相似度度量标准163.1距离度量函数163.2欧几里得距离163.3DynamicTimeWraping173.4LongestCommonSubsequences183.5EditDistanceonRealSequence19第四章轨迹数据的存储方法204.1对空间点的存储方法204.1.1R树系列204.1.2KD树系列214.2对时间序列的存储方法224.2.1对点的倒排索引224.2.2对特征维度的索引22第五章基于轨迹相似度的轨迹推荐方法235.1相似度模型235.2索引策略245.3算法流程255.4实验和分析27第六章总结与展望306.1总结306.2展望30参考文献32致谢34摘要本文以轨迹推荐问题为突破口，研究并分析了轨迹的压缩方法、轨迹相似度度量标准、轨迹特征提取算法以及轨迹索引查询方法等，并且综合了已有方法的优势，针对已有方法的不足，设计了一套基于轨迹相似度的轨迹推荐算法，保证了高效而准确的相似轨迹的推荐。具体的说，本文开展了以下研究：一种轨迹数据的特征提取算法。现有的对于轨迹数据的特征提取算法大多没有考虑的轨迹数据的存储和索引。这些提取出来的特征虽然能够从一定程度上对轨迹数据进行了降维，但是这样的特征提取也只能算是一种数据压缩，我们不能在保证没有漏检的情况下使用这些特征。而本文提出的方法则既能保证数据的压缩效果，也能保证没有漏检情况的发生。基于轨迹相似度的轨迹数据的推荐方法现有的轨迹推荐算法大都是基于机器学习算法，对轨迹数据进行聚类，或者建立用户画像，在拥有相同用户画像的相似用户之间互相推荐轨迹。本文在上面的轨迹数据的特征提取算法的基础上，设计了一套基于轨迹相似度的轨迹推荐算法，单纯的从轨迹相似的角度为用户推荐轨迹数据。关键词：轨迹相似度；文件索引；特征提取；轨迹压缩；相似度查询AbstractThispaperstudiesandanalyzesthetrajectorycompressionmethod,thetrajectorysimilaritymetric,thetrajectoryfeatureextractionalgorithm,andthetrajectoryindexquerymethod,andintegratestheadvantagesoftheexistingmethods.Atrajectoryrecommendationalgorithmbasedontrajectorysimilarityisdesignedtoensuretheefficientandaccuratesimilartrajectoryrecommendation.Specifically,thisarticlehascarriedoutthefollowingresearch:1.Afeatureextractionalgorithmfortrajectorydata.Mostexistingfeatureextractionalgorithmsfortrajectorydatadonottakethestorageandindexingoftrajectorydataintoaccount.Althoughtheseextractedfeaturescanreducethedimensionofthetrajectorydatatosomeextent,suchfeatureextractioncanonlyberegardedasakindofdatacompression.Wecannotusethesefeatureswhichmaycausefalsedismissal.Themethodproposedinthispapernotonlyguaranteesthecompressioneffectofdata,butalsoensuresthatnofalsedismissaloccurs.2.RecommendedmethodfortrajectorydatabasedontrajectorysimilarityMo