客服电话:15682930301

电子技术论文

当前位置: 毕业论文>计算机论文>电子技术论文 > 正文

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

发布时间:2020-02-03 14:13文字数:13152字

  摘 要:本文以轨迹推荐问题为突破口,研究并分析了轨迹的压缩方法、轨迹相似度度量标准、轨迹特征提取算法以及轨迹索引查询方法等,并且综合了已有方法的优势,针对已有方法的不足,设计了一套基于轨迹相似度的轨迹推荐算法,保证了高效而准确的相似轨迹的推荐。具体的说,本文开展了以下研究:

  1. 一种轨迹数据的特征提取算法。

  现有的对于轨迹数据的特征提取算法大多没有考虑的轨迹数据的存储和索引。这些提取出来的特征虽然能够从一定程度上对轨迹数据进行了降维,但是这样的特征提取也只能算是一种数据压缩,我们不能在保证没有漏检的情况下使用这些特征。而本文提出的方法则既能保证数据的压缩效果,也能保证没有漏检情况的发生。

  2. 基于轨迹相似度的轨迹数据的推荐方法

  现有的轨迹推荐算法大都是基于机器学习算法,对轨迹数据进行聚类,或者建立用户画像,在拥有相同用户画像的相似用户之间互相推荐轨迹。本文在上面的轨迹数据的特征提取算法的基础上,设计了一套基于轨迹相似度的轨迹推荐算法,单纯的从轨迹相似的角度为用户推荐轨迹数据。

  关键词:轨迹相似度;文件索引;特征提取;轨迹压缩;相似度查询

  前 言

  近年来,随着无线定位设备的广泛使用,我们能够越来越方便的获得由这些定位设备发送的定位数据。这些数据通常由经度、纬度、高度和其他辅助信息组成。这些数据给我们带来了大量的研究价值,但是同时也给我们的计算和挖掘能力带来了巨大的挑战。庞大的数据量要求更好的数据存储能力、更快的数据计算能力和更高的数据结构设计能力。同时,如何对这些数据进行高效地应用也是一个复杂的问题。当前,学术界对轨迹数据挖掘的研究正得到越来越多的重视。

  对于轨迹数据相似性问题的研究可以追溯到度时间序列相似性问题的研究。时间序列相似性问题的最早研究论文由 Agrawal 等人在1993 年发表。起初加入研究行列的有 IBM 公司的 Agrawal 和 UC Irvine 的一些研究小组,在最近一段时间内则 UC Riverside 的 Eamonn Keogh 和 Carnegie Mellon 大学的 Christos Faloutsos 领导的研究小组则更加活跃。除此之外,UC Santa Barbara 大学、 Maryland 大学、New York 大学、Simon Fraser大学等都有对相应进行研究的研究小组。国内的相关研究近年来势头强劲,其中有清华大学、复旦大学、浙江大学、中国科技大学、 西安交通大学、香港大学、香港城市大学等。而且不仅在学术界,在工业界也逐渐展开了对轨迹序列的相似性问题的研究。知名的研究机构包括 Yahoo、IBM、Google 以及美国国家航空航天局 NASA 等。这些公司都有很多专职人员参与本问题的研究。

  一些资深的数据挖掘领域人士甚至认为,对轨迹数据的挖掘已经成为目前数据挖掘中最具挑战性的问题之一。

  以经典的轨迹数据相似性查询问题为例,如何既保证查询的效率,又能保证查询的准确性一直是一个值得权衡的问题。在很多情景下,我们为了保证查询的准确性,我们需要牺牲查询的效率,采用全表查找等形式;在有的情形下我们可能不太关注查询的精确度,这样我们就可以通过粗略查找或者近似查找的方法,降低算法复杂度提高查询的效率。为了同时提高算法的准确率和执行效率,本文对轨迹数据的压缩、存储和轨迹数据相似度度量标准进行研究,以设计一个高效的基于轨迹相似度的轨迹推荐算法为主要研究课题。

  第一章 绪 论

  本章首先介绍了轨迹存储与推荐算法的研究背景和意义,其次概括了本文做的主要工作和贡献,以及主要的创新点。最后介绍了本篇论文的组织结构。

  1.1 研究背景及意义

  时间序列挖掘研究自从上世纪 90 年代提出以来,得到了国内外的广泛关注,成为研究的热点领域之一。它包括时间序列的相似性搜索、聚类、分类、模式匹配、规则发现、异常检测等各个方面。轨迹数据是时间序列的一种特殊形式,通常由经度、纬度、高度和其他辅助信息组成,已经成为诸如经济、管理、计算机、数学、电子等诸多学科的交叉研究范畴。轨迹数据相似性问题也是时间序列挖掘中的一个基础问题,它的主要研究内容是判别轨迹数据是否相似、如何衡量相似程度、如何比较轨迹的相似等,它的外在表现是轨迹数据的相似性搜索。

  随着各种无线通信和定位技术的高速发展,人们可以非常方便地收集到大量轨迹数据。轨迹数据具有很高的应用价值,人们可以进行通过运用这些数据进行相应的数据分析来实现很多重要的功能。如根据日常活动轨迹,我们可以向人们推荐潜在的朋友;根据动作的轨迹,我们可以进行人们动作目的的识别;根据已有的车辆轨迹,我们可以向驾驶员推荐最为流行的行车路线等。

  相似轨迹查找是对轨迹数据进行充分运用的基础功能之一,即要求对于给定的某个时间序列,从大型数据集合中找出与之相似的时间序列[1],主要包括轨迹相似度度量、轨迹数据压缩、轨迹数据存储、轨迹推荐等。但是,由于轨迹数据获取的方便性,轨迹数据的规模也在呈几何数量地增加。因此如何更快、更好、更高效地进行轨迹查找就成了现阶段的一个巨大的挑战。更快,就是要求能够尽可能减少单次查询的时间消耗;更好,就是要求查询的结果更加符合给定的要求;更高效,就是指将空间和性能运用在更有价值的地方。

  近几年,相似轨迹的查询研究有了很大的进步,提出了很多有效的算法。在轨迹压缩方面,提出了通过减少轨迹点的冗余度来加速轨迹查询的各种轨迹压缩算法,代表性的有Douglas-Peucker算法[2]、离散傅里叶变换方法、奇异值分解方法[3]、滑动窗口法[4]等。在轨迹相似度度量方面,提出了通过设计更优化的相似度度量标准来节约时间的各种下限算法,常用的算法有LB_Kim[5]、LB_Yi[6]、LB_Keogh[7]、LB_PAA[8]等。在轨迹存储方面,提出了通过设计更加优秀的索引结构和搜索树来加快查找的过程。上述的各种方法各有优缺点,我们将在第二章到第五章中进行详细地分析说明。

  1.2 本文的主要工作和创新点

  本文总结并分析了目前较为流行的轨迹数据加工处理的方法,详细研究了各种轨迹压缩技术、轨迹相似度度量标准、轨迹特征提取算法以及轨迹索引查询方法等,分析了各自的应用场景和优缺点。并提出了一套高效的对相似轨迹进行查询的方法。和原有算法相比,该算法具有如下创新:

  (1)基于文件索引。不需要同时将所有数据读入内存,适合对大量数据进行查找。并且利用索引文件,不需要进行全表查找,可以更高效地进行查找,有效提高了查询效率,减少了查询时间。

  (2)支持增量添加数据。在数据集扩大时不需要重新构建索引,只需要按照规则将新添加的数据加入数据集即可,具有较强的扩展性。

  (3)不会出现漏检(False Dismissal,FD)的情况。为了提高数据的查询效率,当前很多查询方案都将类似KNN(k Nearest Neighbor)的问题描述为ANN(Approximate Nearest Neighbor)问题。由于不需要保证结果的绝对准确性,所以ANN问题的解决速度比KNN问题快得多,但是代价就是要牺牲准确率,他无法保证检索出最合适的结果,而是一个较为合适的结果。本文提出的方案既可以保证高效率,也可以杜绝漏检情况的发生。

  (4)支持不等长轨迹数据的比较。即使是轨迹数据长度不同,该算法也可以高效的进行比较以及索引。

  本文利用的MSRA(Microsoft Research Asia)提供的GeoLife数据集[9-11]对本文提出的方法进行了仿真实验,并与当前已有的方法进行了对比分析,验证了本文提出的方法的正确性和高效性。

  1.3 本文的组织结构

  本文共分为六章,各章节的安排如下:

  第一章为绪论。本章首先简要介绍了本文所涉及的研究课题的背景、意义、实际应用等。然后概括了本文的主要工作和创新点,最后阐述了本文的组织结构。

  第二章:轨迹数据压缩算法。本章主要介绍了当前主流的轨迹数据压缩算法,并且分析了各个算法的优劣和应用场景。

  第三章:轨迹相似度度量标准。本章主要介绍了收到学术界广泛认可的相似度度量标准以及这些度量标准的优化版本、下界版本。

  第四章:轨迹数据的存储方法。本章主要介绍了用于存储轨迹数据的数据结构以及常用的查找方法。

  第五章:基于轨迹相似度的轨迹推荐方法。本章主要介绍了本文提出的基于轨迹相似度的推荐算法,同时通过实验加以对比分析。

  第六章:总结与展望。总结全文,提出未来工作的设想与展望。

  第二章 轨迹数据压缩算法

  通常而言,大多数的轨迹数据都是通过传感器定时采集物体的运动状态,并将数据进行存储。由于传感器的采样率不同,数据获取的密度也有所差异。大多情况下,对于车辆轨迹的采样间隔是秒级的,而对行人轨迹采样的间隔大约是分钟级的。在这种采集频率下,每一辆车一天就大约可以采集到4GB左右的数据,而每一个行人每一天就大约可以采集到160GB的轨迹数据。这导致了采集得到的轨迹数据的规模非常大,其中很多轨迹点包含了很多的冗余信息,有效信息较少,没有存储的必要性。为了能够减少存储时的总数据量,并提高存储的每一个点的有效性,现阶段提出了很多轨迹数据压缩方法。本文详细阐述了目前广泛使用的一些轨迹数据压缩算法,并对它们进行了对比分析,分别阐述了它们的优势和缺点,以及在实际生活中适用的场景。

  2.1 降采样方法

  减少一条轨迹中轨迹点的个数最简单而直观的方法就是降低采样率。比如对于一个可控的采样设备,原本是每隔五秒钟获取一个坐标数据,使用降采样方法,可以修改为每隔一分钟获取一个坐标数据,这样数据量就减少为了原先的十二分之一。通过讲采样时间间隔改为更大的树枝,可以达到获取较少的轨迹数据的目的。

  对于采样率固定的设备,无法更改采样时间,可以通过一些数据过滤算法对数据点进行过滤。通常来说,数据过滤方法可以分为两种:

  (1)在线过滤。这类方法主要适用于一些不停获得的流式数据。这些数据的重要级别通常比较低,因此可以设置一个较低的采样率,让存储设备每隔N个数据存储一次,这样数据量就可以缩减到原来的1/N。有时候为了减少舍弃的轨迹点造成的影响,可以设置一个缓存窗口,每当获得一个轨迹点,就将这个轨迹点添加进缓存窗口。当窗口满了的时候,计算窗口里所有轨迹点的平均值,得到相应的平均点,将这个平均点加入最终的轨迹序列,并且将缓存窗口清空。

  (2)离线过滤。这类方法主要适用于数据已经完全获取的情况。该类算法通过对存储的轨迹点进行随机采样,或按照固定间隔进行删减,达到压缩存储的轨迹点个数的目的。

  降采样方法非常的简单、易用、可靠。在大多数场景下都能使用,而且可以精准的控制压缩后轨迹点的个数,非常便捷。但是该类算法常常受到个采样率的选择的影响。在不同场景或是相同场景的不同阶段,采样率的最佳选择都会有所差异。如果将采样率设置得太低,那么将会有大量的轨迹点丢失,和原始轨迹出入较大;如果将采样率设置得太高,那么仍然保留了很多冗余的数据,压缩不完全。而且由于删减轨迹点方法常常带有随机性,很容易将一些重要的轨迹点删除,导致压缩后的轨迹失去了某些重要的特征。总而言之,由于降采样的方法简单,高效,适合快速地将一些稠密的轨迹点变得稀疏,所以比较适合用于对轨迹做初步的压缩。

  2.2 Douglas-Peucker算法

  Douglas-Peucker算法[12]是一个经典的轨迹数据压缩算法,弥补了朴素降采样方法容易使轨迹失去关键特征的不足。该算法的原理是只删除对轨迹特征影响比较小的点,从而保证能够保留轨迹的绝大部分特征。Douglas-Peucker算法的具体步骤如下:

  2.3 离散傅里叶变换算法

  离散傅里叶变换算法[14]也经常用来对时序数据进行将降维。离散傅里叶变换本质上是一种谱分解算法,理论上可以用多个正弦波去拟合任何一个函数。因此对于一个长度为n的时间序列,可以通过n个正弦波来组合还原。由于这n个正弦波所占的比重不同,可以去掉这当中对轨迹贡献较小的那些正弦波,用留下来的波来表示整个序列。离散傅里叶变换算法特征分解如图2.2所示。  2.5 基于速度和方向的轨迹压缩算法

  基于速度和方向的轨迹压缩算法是专门用于车辆轨迹这种带有明显的方向和速度特性的轨迹的压缩。原始的轨迹压缩算法仅仅考虑轨迹的几何特征,而没有考虑轨迹本身的含义。对于车辆轨迹而言,驾驶员关注的不是自己的历史轨迹,而是自身的方向和速度,因此可以根据这个特性,使用基于速度和方向的轨迹压缩算法对轨迹进行压缩[15]。

  轨迹压缩算法需要事先设定速度阈值和方向容忍度阈值。根据这两个阈值可以从前一个轨迹点预测出下一个轨迹点应当出现范围。如果新的轨迹点落在这个范围内,则将这个新的轨迹点舍弃,否则就将新的轨迹点加入最终的近似轨迹中,如图2.4所示

  图2.4 基于速度和方向的轨迹压缩算法示意图

  首先设定一个速度的范围,比如设置速度区间为[a,b],然后设定一个角度的旋转区间  2.6 基于GeoHash的数据点压缩算法

  轨迹数据是时间序列数据的一种,但是与时间序列数据有所差异,即时间序列数据除了时间维度之外可以看成是一维的,而轨迹序列中承载的数据却是一个二维(经度、维度),甚至是三维(高度)的。因此为了方便后期的比较,可以先将一个二位数据点压缩成一个一维的数据。

  将二维数据转化为一维数据最经典的模型就是皮亚诺曲线。皮亚诺曲线是一个曲线序列的极限,一个能填满一个封闭图形的不可导的曲线。与皮亚诺曲线有异曲同工之妙的就是GeoHash算法。

  GeoHash算法首先将地球作为一个大的区域,然后这个区域沿着东西、南北方向分别进行二分,对每一个子区域进行编码;然后再对每一个子区域进行二分,再编码……重复这个操作,直至精度满足给定的要求。这样每一个坐标点(其实是一个近似于点的区域)就对应于一个数值,可以用这个一维的值来代替二维的坐标点。以经纬度值(116.389550, 39.928167)为例。首先对纬度39.928167进行逼近编码。具体如图2.5所示。

  图2.5 GeoHash算法编码示意图

  根据图2.5可以看出,在精度等级为15时,纬度部分的GeoHash编码值是“110100101100010”,同理,经度部分的编码值就是“101110001100011”。然后将经度和维度的编码值交叉组合,经度的编码放在偶数位,维度的编码放在奇数位,并且将得到的01串转化为十进制数字,再转化为base32编码,即可得到这个坐标点对应的GeoHash编码“wx4g0e”。将这些编码值从大到小进行连线,可以发现这其实就是填充了整个平面的Z阶曲线,如图2.6所示。

  图2.6 GeoHash算法的Z阶曲线

  GeoHash能够在精度允许的范围内将二位数据有效压缩为一维数据,但是美中不足的是GeoHash编码无法保证二维坐标相邻的点的编码值也相邻,因此并不方便做索引。从图2.6中,我们可以看出相邻的点基本保持相邻关系,但是仍然存在一些“突变”的位置。如果在轨迹查询的时候查询到了这些轨迹点,那么就很容易出现漏检的情况。

  由于GeoHash简单、快捷、节约存储的特点,在对查询精度要求不高的情况下,GeoHash的用处非常多。但是如果场景对查询精度有要求,那么GeoHash可能表现效果不佳。

  第三章 轨迹相似度度量标准

  如何衡量两条轨迹之间的相似性是相似轨迹进行查询时的核心问题之一。由于在不同场景下轨迹查询的侧重点不同,因此相似度度量标准也不同。在本章,我们对一些常用的相似轨迹度量标准进行分析说明。

  3.1 距离度量函数

  首先给出关于轨迹的距离度量函数的定义:

  对于给定的一个定义在轨迹数据上的空间T,以及任意两条T中的轨迹x与yT上的距离度量函数d定义为:  前三条性质是距离函数的必备条件,且比较容易满足。最后一个三角形不等式性质很多距离度量函数较难满足。在大多数情况下,三角形不等式的性质不是距离函数的必备条件。但是严格来说,如果一个距离度量函数不满足三角形不等式,那么它的价值相对较低,因为不满足三角形不等式的距离函数无法满足通常所理解的“两点之间直线最短”的概念,这也意味着它不存在极限唯一性,所以不能用来做索引比较。因此,如果说一个函数能够满足上述的定义,那么就认为它是一个合格的距离度量函数。

  3.2 欧几里得距离

  欧几里得距离是一个非常经典的距离度量单位,也被一直用来进行轨迹之间的距离度量。欧几里得距离的定义如下:

  给定两条长为n的时间序列A与B,它们之间的 欧几里得距离定义为:

  已经被广泛的作为相似轨迹的度量标准,这种方法计算简单,物理含义直观,而且复杂度较低。不过它们只能够用来比较两条轨迹长度相同的轨迹,对于轨迹长度不同的两条轨迹,便无法使用了。

  3.3 Dynamic Time Wraping

  DTW(Dynamic Time Wraping)最先被于语音识别,能够比较好地处理局部时间偏移,计算两条不等长的序列之间的距离。DTW距离定义如下: 当序列长度变长时,计算的性能会很差。针对DTW较高的时间复杂度的问题,国内外的研究人员也提出了很多优化算法,比如LB_Keogh[16], LB_Improved[17]。这些优化算法基本是通过限制两个匹配点之间的范围差来计算一个标准DTW的下限,但是这些算减小时间复杂度的同时,也牺牲了精度。DTW算法能够非常方便的比较两个不等长轨迹的“距离”,因此在实际使用中应用非常广泛。但是它有一个致命的缺陷,就是DTW距离并不满足三角形不等式,因此从严格意义上讲,并不是一个好的距离度量单位。  3.4 Longest Common Subsequences

  LCSS(Longest Common Subsequences)算法通常被用于带有噪声序列的降噪处理[18]。该算法通过比较给定的两条序列之间的对应点来完成降噪处理,它的具体定义如下:

  LCSS算法常被描述为相似度度量标准,而不是距离度量标准,所以为了将相似度度量标准转换成距离度量标准,需要做如下处理:

  LCSS算法有一个极佳的特性就是它能够消除异常值带来的影响。DTW算法和欧氏距离中计算过程中每一个点都会对影响最终的计算结果,而LCSS算法会有选择的放弃一些误差较大的点,减小部分点对最终结果的影响。不过LCSS算法执行的复杂度是 ,时间运行效率比较低,而且LCSS也不支持三角形不等式,无法方便地进行索引比较。

  3.5 Edit Distance on Real Sequence

  LCSS算法能够有效地降低异常值带来的影响,但是却不能区分具有相同子序列但是大小不同的轨迹。因此Lei Chen等人[19]提出了EDR(Edit Distance on Real Sequence)函数作为新的距离度量标准。EDR距离定义如下:

  来判断两个点是否是同一个点。由于EDR能够匹配间隔不相同的两个轨迹,因此比LCSS更加准确,也更加具有代表性,不过相较于其它算法,EDR的时间复杂度并没有什么优势。

  第四章 轨迹数据的存储方法

  为了能够更高效的对轨迹数据进行查找,需要对轨迹数据进行存储和检索。从本质上讲,轨迹数据其实可以看成是时间序列和空间点的结合,而无论从时间序列,还是空间点的角度上讲,我们都需要一个能够索引多维数据的数据结构。本章将会对一下目前常用的对多维数据进行存储的方法进行分析。

  4.1 对空间点的存储方法

  对空间点进行存储的方法目前在业界已经比较成熟,绝大多数主流数据库都支持对多维数据的存储和索引。而且随着相关方面研究的深入,提出了很多优化算法。不过总体来说,存储和索引方法通常基本是围绕两个基本模型进行深入优化的:一个是R树,另一个就是KD树。

  4.1.1 R树系列

  R树是GUTTMAN于1984年提出的最早支持有序扩展的对象存取方法之一,并且也是目前为止应用最为广泛的一种空间索引结构。许多人们耳熟能详的空间数据库系统,比如Oracle Spatial,PostgreSQL和MapInfo SpatialWaro等均提供对R树的支持。同时,在R树的基础上也提出了很多优化算法,最著名的有R+树、R*树等。

  R树是一个高度平衡树,它可以看成是B树在K个维度上的自然扩展。它用空间对象的MBR(Minimum bounding rectangle)来近似表达空间对象,根据物体的MBR建立R树,我们就可以直接对在空间中占据一定范围的空间对象进行存储和索引。空间对象的MBR被包含于R树的叶结点中。在R树空间索引中,可以设计一些虚拟的矩形目标,将一些空间位置相近的目标,包含在这个矩形内。这些虚拟的矩形作为空间索引,它将含有所包含的空间对象的指针。虚拟矩形还可以进一步细分,即可以再套虚拟矩形形成多级空间索引。

  在R树的构造中,我们要求虚拟矩形要尽可能少地重叠,并且要求一个空间对通常仅被一个虚拟矩形所包含。但是空间对象千姿百态,它们的MBR经常重叠。 R+ 树改进了R树的空间索引,为了平衡,它允许虚拟矩形相互重叠,并允许一个空间目标被多个虚拟矩形所包含。

  R*树都是完全动态的,插入、删除操作可以与查询操作混合进行,而且不需要进行定期的全局重建。它允许不同子树的最小外包矩形发生重叠,因此这种结构在进行精确匹配搜索的时候会产生多条搜索路径。R*树的性能都比其他R树变种高。对于点数据的访问,它的性能提升更加明显。R*树主要是考虑降低面积、边长、路径矩形的重叠,R*树即使面对分布非常不规则的数据时也能表现得十分稳定。又由于强制插入算法的使用,避免了不必要的分裂,这样一来,R*树就得到了动态的重构,使得存储效率得到了提升。但是R*的实现代价仅比R树的实现代价稍高。

  4.1.2 KD树系列

  kd树是每个节点都为k维点的二叉树。所有的非叶子节点都可以视为用一个超平面把空间分区成两个半空间。节点左边的子树代表在超平面左边的点,节点右边的子树代表在超平面右边的点。选择超平面的方法如下:每个节点都与k维中垂直于超平面的那一维有关。因此,如果选择按照x轴来进行划分,所有x值小于指定值的节点都会出现在左子树,所有x值大于指定值的节点都会出现在右子树。这样一来,超平面可以用这个x值来确定,其法线就是x轴的单位向量。KD树能够非常被方便的用来解决K近邻问题,因此应用也十分的广泛。

  对KD树也有相当多的优化方案,比如用B树来对KD树进行扩展,通过采纳B树面向块的存储方式,使得KD树的文件读写次数得以减少,进而优化其外部内存的访问,这就得到了KDB树。如果考虑到对空间的极度优化,还有BKD树[20],通过组合多个KD树可以提供更高的空间利用率,更高性能的查询和更新。BKD树目前已经成功过应用在著名的搜索引擎Lucene以及著名的搜索框架ElasticSearch中了。它使得es处理数值型数据和高维数据性能提高了约30%,空间节约了约60%。

  4.2 对时间序列的存储方法

  4.2.1 对点的倒排索引

  倒排索引也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。

  对于时间序列的数据来说,由于时间序列与文档类似,都是由多个元素组成,因此我们也可对时间序列数据采用倒排索引。将每一个时间序列看成是一份文档,将每一个时间点看成是一个单词,那么在存储的时候只需要存储每一个时间点,以及这个时间点对应的时间序列的编号即可。也可以将时间点扩展为一个小的时间序列段,这样使得对时间序列的索引更有意义。

  对于采取了倒排索引的时间序列,当我们需要进行最近邻查询的时候,就可以利用倒排索引,计算待查询轨迹中所有轨迹段包含的轨迹,然后在这个子集合中再精细的查询,达到“先过滤,后查询”的目的。通过这种方法能够比较高效的进行轨迹查找,而不需要进行全表扫描。

  4.2.2 对特征维度的索引

  除了对时间序列进行倒排索引,我们还可以通过特征提取的方法,利用各种特征提取的函数,从时间序列中提取出重要的数据或者是问题域关注的特征值,并运用前面介绍的多维数据索引方法进行索引。在这类算法中,对时间序列进行特征提取的算法十分重要。由于应用场景不同,特征提取的算法也不同。对于较短的时间序列,甚至可以将每一个数据点看成是一个特征,但是一定要保证特征值的个数远小于数据量,否则就会造成维度灾难。通常我们会采用一些固定的特征提取方法,比如类似PAA的采样方式,或者是一些基于极值或者特征值的计算。

  第五章 基于轨迹相似度的轨迹推荐方法

  为了更高效的解决相似轨迹的查询问题,本章提出了一个基于DTW相似度的相似轨迹搜索算法,在保证对相似轨迹的推荐不存在遗漏的前提下,极大优化了搜索效率,准确并高效的完成了对相似轨迹的推荐。

  5.1 相似度模型

  考虑到目前各种关于轨迹相似度的距离定义中效果最好的就是DTW算法,因此在我们的方法中,我们也采用DTW作为距离度量标准。但是,作为通用的距离比较标准,不同轨迹之间,常用的DTW距离的尺度是不一样的。原本DTW距离被定义为两条轨迹之间的轨迹点,两两顺序组合,并计算这些轨迹点对的距离之和。这就导致了轨迹点对数的不同会直接导致DTW距离尺度的不同。这就不方便我们在统一的尺度下进行比较。对DTW距离进行归一化是一个不错的方法,但是这样又会使得计算变得复杂。所以在这个基础上,我们提出了扩展的DTW算法。

  在扩展的DTW算法中,对于给定两个轨迹S和Q,DTW距离定义如下:

  5.3 算法流程

  我们整个的LBINDEX算法流程如图5.1所示。整个过程分为两个阶段。第一个阶段是预处理阶段,这个阶段分为两个过程。首先要将文本形式的数据集整理进入数据库,一方面是加快数据的读取速度,另一方面也是让每一条轨迹能够通过ID被唯一的定位;然后要对所有的轨迹提取特征向量,并且利用特征向量构建索引,并且存入索引文件,这个步骤非常重要,是整个系统性能的瓶颈所在,也是提高检索性能的关键。第二个阶段是查询阶段,这个阶段也分为两个步骤,首先提取待查询轨迹的特征,并且根据阈值s利用索引文件进行近邻查询,得到一个候选集;然后对于候选集的每一个轨迹计算他与待查询轨迹的实际距离,并根据阈值s过滤掉不合法的数据得到最终的查询结果。

  对于查询系统而言,我们关注的是查询阶段的时间复杂度。假设整个数据集的大小是

  5.4 实验和分析

  为了验证本套方案的可行性,我们进行了一系列实验进行验证。我们采用了微软亚洲研究院提供的GeoLife数据集进行实验。GeoLife数据集包含了182个用户在三年内采集到的17621条轨迹数据,总共约有2000w个轨迹点。本次实验为了获得更多的轨迹,我们将数据集中的轨迹拆分成20多万条长度约为100的轨迹段。

  实验的机器是搭载Intel? Core? i7-7500U @2.70GHz的台式笔记本,并装载了window10系统。

  我们的实验除了采用本文推荐的LBINDEX方法外,另外加入了NA?VE,PAASAMP,PAAAVG三种算法作为对比方法。其中NA?VE就是一个最平凡的全表搜索方法。PAASAMP是利用PAA均匀采样算法获得特征值进行索引并过滤的算法,PAAAVG是利用PAA平均采样算法获得特征值进行索引并过滤的算法。

  在实验中,我们选择了七种不同的阈值,每一次实验我们会随机抽取一条轨迹,搭配选择的阈值,利用四种算法查询相邻的轨迹。我们总共会进行十次实验,并将结果以及运行时间累加作为最终的数据。实验中,我们采用了Lucene的BKD树作为索引算法的实现。Lucene 是一个基于 Java 的全文信息检索工具包,它不是一个完整的搜索应用程序,而是为你的应用程序提供索引和搜索功能。Lucene 目前是 Apache家族中的一个开源项目。也是目前最为流行的基于 Java 开源全文检索工具包。Lucene中采用了BKD树作为多维索引的实现方式,相比于常见的KD树,BKD树维护了多个静态的KDB树,能够提供更高的查询速度,并且能够对空间有近乎于100%的利用率。Lucene提供的索引实现也经受了大量的实际验证,在业界已经能够代表索引功能的较高水平。同时,我们采用了Mysql数据库为轨迹数据提供ID到数据的映射,保证了较好的IO查询效率以及较大的吞吐量。

  为了更好的反应实验的特征,我们采用了三个评价标准来衡量算法的质量。第一个是候选集的准确率,也就是候选集中符合要求的轨迹占候选集大小的百分比。第二个是算法的召回率,也就是通过对候选集进行过滤后获得的符合要求的轨迹占数据集中所有符合要求的轨迹的百分比。第三个是算法的运行时间,这里是每一个算法运行十次的时间总和。

  实验结果如图5.2所示。在实验中,由于NA?VE并没有过滤的步骤,因此NA?VE算法的准确率和召回率都是100%。在此基础上,从图表中我们可以看出,LBINDEX算法的准确性是上下各个算法中最好的,这说明利用LBINDEX算法得到的候选集是非常好的。LBINDEX算法的召回率也是唯一达到了100%的,这说明利用该算法可以完全避免漏检情况的发生。同时LBINDEX的计算时间也是非常短。相比普通检索方法,计算效率非常高。

  我们也发现随着当阈值的增大,算法本身的计算时间也是成倍增加的,这是因为算法本身的复杂度与阈值的选择息息相关,当阈值增大导致候选集增大时,算法的计算时间也会相应的成倍增加。

  (b) 四种算法的召回率 (c) 四种算法的查询时间

  图5.2 四种算法在GeoLife上的实验结果

  第六章 总结与展望

  6.1 总结

  本文分析并总结了当前业界对轨迹数据的处理、分析、查询的各项研究的研究现状,并且针对相似轨迹查询问题展开了研究,获得了如下的研究成果。

  (1) 一种轨迹数据的特征提取算法。

  现有的对于轨迹数据的特征提取算法大多没有考虑的轨迹数据的存储和索引问题。这些提取出来的特征虽然能够从一定程度上对轨迹数据进行了降维,但是这样的特征提取也只能算是一种数据压缩,我们不能在保证没有漏检的情况下使用这些特征。而本文提出的方法则既能保证数据的压缩效果,也能保证没有漏检情况的发生。

  (2) 基于轨迹相似度的轨迹数据的推荐方法

  现有的轨迹推荐算法大都是基于机器学习算法,对轨迹数据进行聚类,或者建立用户画像,在拥有相同用户画像的相似用户之间互相推荐轨迹。本文在上面的轨迹数据的特征提取算法的基础上,设计了一套基于轨迹相似度的轨迹推荐算法,单纯的从轨迹相似的角度为用户推荐轨迹数据。

  6.2 展望

  本文解决了对于轨迹数据的高效近邻搜索与推荐的问题,较好的满足了我们的性能与准确性要求。但是在研究的过程中,我们也发现了很多应该得到进一步研究的问题,这些问题在本文中暂时并没有得到较好的处理,我们期望这些问题在接下来的工作中能够得到进一步的分析和研究:

  (1) 性能的优化。

  本算法的搜索时间随着阈值的增大而增大明显,我们希望能有一个更好的办法尽量减少阈值对算法性能的影响。同时,我们也期望能够更好的减少轨迹相似性计算的复杂度以及索引构建与查找的时间复杂度,这需要我们设计更好的轨迹相似度度量标准,以及更加高效的多维索引树。

  (2) 索引存放问题。

  本算法是基于索引的查询方法,如果数据量过大导致单机内存无法保存完整索引,那么本方法的使用就存在问题了。目前我们的方法还无法处理分布式索引,如果数据量达到如此的规模那么我们就需要另觅新的方法了。

  (3) 对子轨迹的索引。

  目前我们只能做到给定轨迹数据,我们从数据库里推荐一个轨迹,而且这个轨迹只能是数据库中的一项,而不能是一个子轨迹。而现实应用中,我们很多的轨迹其实是连续的,我们很多都是人为的按照时间、事件、地点等因素将大的轨迹段拆分成小的轨迹段,作为查询的基本单位。而事实上这样分割的轨迹段很可能会将一些重要的轨迹段进行了拆分,造成查询的遗漏。在今后的工作中,我们期望能够直接查询出一条轨迹中的任何一个子轨迹段,而不用实现进行轨迹分割。

  (4) 扩展数据的应用方法。

  对于轨迹数据的应用方法其实还很广阔,但是目前我们也仅仅开发了其中一小块的应用场景。在接下来的研究中,我们期望能更好的挖掘轨迹数据的应用场景,为人们的工作和生活带来便利。

  

移动版:基于轨迹相似度的轨迹推荐算法

本文标签: