基于划分的自适应轨迹拐点提取压缩算法.pdf
《基于划分的自适应轨迹拐点提取压缩算法.pdf》由会员分享,可在线阅读,更多相关《基于划分的自适应轨迹拐点提取压缩算法.pdf(10页珍藏版)》请在咨信网上搜索。
1、基于划分的自适应轨迹拐点提取压缩算法郑汉捷1,2,3,邬群勇1,2,3,尹延中1,2,3,王涵菁1,2,3,张晨1,2,31(空间数据挖掘与信息共享教育部重点实验室(福州大学),福州350108)2(数字中国研究院(福建),福州350003)3(卫星空间信息技术综合应用国家地方联合工程研究中心,福州350108)通信作者:邬群勇,E-mail:摘要:海量的轨迹数据为管理分析和数据挖掘工作带来了巨大的挑战,轨迹压缩技术成为解决这一问题的一种有效方案.针对目前多数轨迹压缩算法需要人为干预设定阈值的问题,融合特征聚类与轨迹划分的思想提出了一种自适应的轨迹拐点提取压缩算法.算法从轨迹的全局方向特征与局
2、部方向特征出发考虑,依次进行了轨迹粗划分、子轨迹合并以及轨迹细划分的工作.实验结果显示,随着轨迹规模的增大,与其他算法相比,该算法基本能够在保持更高压缩率的同时产生更低的方向误差.提出的算法具有自适应和高精度拐点识别的优势,在其他轨迹压缩场景之下仍有着较高的参考价值.关键词:轨迹数据;轨迹压缩;聚类簇引用格式:郑汉捷,邬群勇,尹延中,王涵菁,张晨.基于划分的自适应轨迹拐点提取压缩算法.计算机系统应用,2023,32(11):212221.http:/www.c-s- Trajectory Inflexion Extraction and Compression Algorithm Based
3、on PartitionZHENGHan-Jie1,2,3,WUQun-Yong1,2,3,YINYan-Zhong1,2,3,WANGHan-Jing1,2,3,ZHANGChen1,2,31(KeyLabofSpatialDataMining&InformationSharingofMinistryofEducation(FuzhouUniversity),Fuzhou350108,China)2(TheAcademyofDigitalChina(Fujian),Fuzhou350003,China)3(National&LocalJointEngineeringResearchCente
4、rofSatelliteGeospatialInformationTechnology,Fuzhou350108,China)Abstract:Massivetrajectorydataposechallengestomanagementanalysisanddatamining,andtrajectorycompressiontechnologyhasbecomeaneffectivesolutiontothisproblem.Aimingattheproblemthatmostcurrenttrajectorycompressionalgorithmsneedhumaninterventi
5、ontosetthresholds,thisstudyproposesanadaptivetrajectoryinflectionpointextractionandcompressionalgorithmwhichcombinestheideaoffeatureclusteringandtrajectorypartition.Basedontheglobalandlocaldirectioncharacteristicsofthetrajectory,thealgorithmcarriesouttheroughtrajectorydivision,sub-trajectorymerging,
6、andfinetrajectorydivision.Theexperimentalresultsshowthatwiththeincreasingtrajectorysize,theproposedalgorithmcanproducelowerdirectionerrorandmaintainahighercompressionratethanotheralgorithms.Thealgorithmfeaturesadaptiveandhigh-precisioninflectionpointrecognitionandstillhasahighreferencevalueunderothe
7、rtrajectorycompressionscenarios.Key words:trajectorydata;trajectorycompression;clusteringgroup随着定位技术和移动通信技术的快速发展和应用普及,轨迹数据的获取变得越发容易,已经在不同的领域突显出重要的研究价值1.然而,较高的采样频率会产生大量的轨迹记录,从而导致轨迹数据规模的爆炸式增长.对于一线城市而言,仅是出租车的轨迹数据量,一天就已经能够达到 TB 级以上2.这将严重影响数据计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Applicat
8、ions,2023,32(11):212221doi:10.15888/ki.csa.009289http:/www.c-s-中国科学院软件研究所版权所有.Tel:+86-10-62661041基金项目:国家自然科学基金(42201500,41471333);福建省科技计划引导项目(2021H0036)收稿时间:2023-04-13;修改时间:2023-05-17;采用时间:2023-06-01;csa 在线出版时间:2023-09-21CNKI 网络首发时间:2023-09-22212软件技术算法SoftwareTechniqueAlgorithm存储、管理与查询分析效率,给服务器带来极大的
9、压力,为进一步的数据挖掘工作带来巨大的挑战,且轨迹中往往包含大量的冗余数据,导致了不必要的存储空间浪费.为减少轨迹数据存储空间和简化轨迹数据分析,轨迹数据的压缩存储成为加速轨迹模式挖掘的一种方式和研究热点3.然而,轨迹数据同时具有时序特征和空间特征,常规的时序数据压缩算法并不能简单适用于轨迹数据压缩的场景,需要充分考虑轨迹的特殊性,设计更有效的轨迹压缩算法以满足海量轨迹数据管理的需求.常见的轨迹压缩算法可以分为以下几类4:基于路网约束的轨迹压缩,此类算法考虑到车辆受限于道路的特点,仅适用于车辆轨迹的压缩工作5,6;基于相似度量的轨迹压缩,此类算法通过度量轨迹间的相似性,将相似的轨迹进行统一的压
10、缩,适用于存在较多相似轨迹的压缩场景7;基于语义信息的轨迹压缩,此类算法一般通过提取轨迹中的语义信息进行压缩,具有较好的可读性,但是将导致轨迹空间信息的丢失8,9;基于特征点提取的轨迹压缩,此类算法限制条件较少,适用于大多数轨迹压缩场景,本文将主要研究此类压缩算法.O(n2)基于特征点提取的轨迹压缩关键在于如何寻找到轨迹中具有代表性的特征点,轨迹中的特征点通常具有丰富的信息能够很好地反映出轨迹的形状以及运动规律.根据选择特征点方式的不同,轨迹压缩算法分为基于全局特征的轨迹压缩以及基于局部特征的轨迹压缩1.道格拉斯-普客算法(Douglas-Peucker,DP)10是最为经典的基于全局特征的轨
11、迹压缩算法,它以一种从上到下的思想,逐步对轨迹进行迭代划分,并使用垂直欧氏距离度量轨迹的压缩误差.Meratnia 等11在DP 算法的基础上考虑了轨迹的时空特征,使用时间同步欧氏距离(synchronousEuclideandistance,SED)代替垂直欧氏距离进行轨迹迭代划分,提出了从上到下的时间比压缩算法(topdowntimeratio,TD-TR).DP和 TD-TR 算法作为经典的全局压缩算法,能够很好地保留轨迹的整体形状,但是由于其递归的特性,算法时间复杂度为.与上述两种考虑位置的压缩算法不同,SP 算法12是保留方向的轨迹压缩算法,算法基于一个给定的方向误差构建轨迹与误差阈
12、值的图结构,通过找到图中的最短路径,得到保留方向信息的轨迹.由于选择合适的方向误差阈值对于不同的应用具有挑战性,作者又提出了 Error-Search 算法13,该算法能够搜索在一定压缩率下方向误差最低的压缩轨迹.同样这两个算法的时间复杂度也较高,因此不适合处理大型轨迹数据集.O(n)基于局部特征的轨迹压缩算法相比而言有着更快的执行效率,其时间复杂度一般为,对于需要实时在线的轨迹压缩需求,基于局部特征的压缩算法较为合适.垂距限值法和角度限值法是其中比较有代表性的方法:通过依次遍历轨迹中的三元组,每一步进行垂距(或角度)的判断决定是否保留轨迹点.李升宏等14借鉴垂距限值法和角度限值法的思想,提出
13、了余弦垂距判别算法(cosineverticaldistancediscrimination,CVDD),压缩效果要优于 DP 算法.邬群勇等15对轨迹进行开放角计算,去除了轨迹中方向变化较小的中间点.Yuan 等16考虑了轨迹的方向运动特征,提出了一种基于轨迹转角的拐点提取方法.上述方法拥有较高的执行效率,但是难以识别出局部变化小而累积变化大的时空弯曲现象,因此很有可能会遗漏某些重要的轨迹特征点.田智慧等17对基于轨迹转角的方法16进行改进,在角度阈值的基础上增加了累积变向角阈值,一定程度上减少了关键特征点的丢失,同时考虑速度特性,使算法能识别出相对完整的特征点.相对而言,基于窗口的轨迹压缩
14、算法将更能满足实时压缩的需求.STTrace 算法18是一种基于 SED 进行度量的在线轨迹压缩算法,该算法依赖于一个固定大小的缓冲区,通过每次删除缓冲区中 SED 误差最小的轨迹点进行压缩工作.有学者考虑将聚类算法与轨迹压缩算法相结合,在进行压缩之前,通过对轨迹的特征进行聚类以获取到潜在的轨迹特征点.Lin 等19提出了保留轨迹速度特性的自适应轨迹压缩算法(adaptivetrajectorysim-plification,ATS),该算法首先从全局的角度对轨迹的速度特征进行聚类,确定出合理的速度间隔区间,并基于基尼系数对轨迹进行递归切分,切分后的子轨迹再应用自适应的 DP 算法.张甜等20
15、在 ATS 算法的基础上进行改进,使用轮廓系数(silhouettecoefficient,SC)21确定聚类簇数,且使用 TD-TR 算法替代 DP 算法,考虑了轨迹的时间特性.杨家轩等22同时对轨迹的方向特征和速度特征进行聚类,在得到潜在的轨迹特征点后,使用信息熵对轨迹进行切分,切分后应用 TD-TR 算法实现二次压缩.上述方法的优势在于能够较好地保留轨迹的运动特征,但是实现较为复杂,且在对轨2023年第32卷第11期http:/www.c-s-计 算 机 系 统 应 用SoftwareTechniqueAlgorithm软件技术算法213迹划分后又应用了 DP 或 TD-TR 算法,因此
16、也具有较高的时间复杂度.文献 12 已证明保留轨迹方向的压缩(direction-preservingtrajectorysimplification,DPTS)比起保留轨迹位置的压缩(position-preservingtrajectorysimplifi-cation,PPTS)而言一般有着更好的压缩效果.使用DPTS 算法进行轨迹压缩,将保证压缩后轨迹在方向上的误差较小,同时在位置上的误差也能被控制在一定范围内.相反,PPTS 却无法保证方向误差.因此,本文所设计的轨迹压缩算法将考虑对轨迹方向信息的保留,也属于一种 DPTS 算法.针对目前大多数轨迹压缩算法存在的需要人为选择阈值的问题
17、,本文从轨迹的全局方向特征和局部方向特征出发考虑,提出一种自适应的轨迹拐点提取压缩算法,在避免人为选择参数的同时,实现高精度的自适应轨迹拐点提取.1轨迹相关定义=p1,p2,pi,pn(1 i n)pipi=loni,lati,ti(t1 t2 ti tn)|TR|TRsim=p1,ps1,ps2,psm,pn(1 s1 s2 sm n)p1pnpsi(1 i m)轨迹压缩问题定义如下:给定一条轨迹 TR,描述为 TR,其中为轨迹点,描述为一个三元组,包括轨迹点的经度、纬度和采样时间戳,一条轨迹的总采样点数则描述为.推导出一条压缩轨迹,其中轨迹起始点和必定被保留在轨迹中,则代表压缩后保留的轨迹
18、的特征点.pipj(1 i i+1)pipjTRSi=pipi+1TRSj1=pj1pj在轨迹 TR 中,按序列顺序取任意两个轨迹点和之间的轨迹点组成的新轨迹,称为子轨迹,描述为 STR.其中和为子轨迹的边界轨迹点,和为子轨迹的边界轨迹段.TRS1,TRS2,TRSn1 TRSi=(pi+1lon pilon,pi+1lat pilat)依次计算轨迹 TR 中 2 个相邻轨迹点的方向向量,得到一条长度为 n1 的方向向量序列,其中每一项为轨迹段方向,描述为.2自适应轨迹拐点提取压缩算法综合轨迹特征聚类的思想20和无监督的序列划分方法23提出一种自适应的轨迹拐点提取压缩算法,算法流程如图 1 所
19、示.首先,从轨迹的全局方向特征进行考虑,通过计算得到轨迹的方向向量序列;再确定合适的类簇数,使用聚类算法以方向向量序列中的每一项为基本单元进行聚类,将轨迹映射成一条类簇标签序列,在标签变化处进行轨迹划分得到了粗划分下的子轨迹序列;其次,遍历子轨迹序列,搜索到仅有两个轨迹点的子轨迹作为待合并子轨迹,通过判断基于余弦相似性的子轨迹合并条件来决定是否将其与相邻子轨迹进行合并,完成对所有子轨迹的判断后得到合并后的子轨迹序列;之后,对于每一条子轨迹的边界轨迹段,计算其轮廓系数以决定是否对子轨迹的边界进行移动,完成对所有子轨迹的判断后得到边界移动后的子轨迹序列.相邻的子轨迹间共享一个边界轨迹点,提取此类轨
20、迹点即为轨迹的拐点.最后保留轨迹的起点、拐点和终点,其轨迹序列为压缩后轨迹.2.1 基于轨迹方向特征聚类的轨迹粗划分本文使用 K-means 对轨迹的方向向量进行聚类,以获得具有代表性的方向间隔.聚类要求输入一个k 值以表示数据分类簇,一般可以根据先验知识或肘部法19得出.本文将轨迹的行驶方向划分为 8 个核心方向,方位角依次为 0,45,315.以核心方向作为区间中心,8 个核心方向恰好将行驶方向划分为 8 个区间,分别为 337.5,360 0,22.5),22.5,67.5),292.5,337.5).据此,给出了确定 k 值的方法:对于一条轨迹 TR 的方向向量序列,计算每一个向量的方
21、位角,记录每一个向量方位角所属的方位角区间,最后统计向量所属的方位角区间总个数,将其作为 K-means聚类的 k 值.0,2聚类算法中的核心步骤在于针对数据集中的每一个向量,计算它到 k 个聚类中心的距离并将其分配到距离最小的聚类中心所对应的类中,通常使用欧氏距离度量向量与聚类中心的距离.针对轨迹方向向量进行聚类,倾向于计算向量之间的方向相似性,因此本文使用余弦距离进行距离度量,计算公式如式(1)所示.余弦距离的取值范围为,越趋近于 0,表示向量之间的方向更加吻合.cosineDistance(x,y)=1ni=1xiyini=1xi2ni=1yi2(1)xiyi其中,x 和 y 为两个向量
22、,和 分别描述向量 x 和 y 中的每一个分量.基于余弦距离对轨迹的方向向量序列进行聚类后,计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第11期214软件技术算法SoftwareTechniqueAlgorithm每一个方向向量被分配了一个标签以标识其所属的类别,一条轨迹映射为一条标签序列,在标签变化处进行轨迹划分实现轨迹的粗划分.O(lnk)对轨迹粗划分的时间复杂度进行分析.这部分的算法时间复杂度基本由 K-means 算法决定,为,其中 l 为迭代次数,n 为轨迹段数,k 为类簇数.开始输出划分后得到的子轨迹序列轨迹粗划分子轨迹合并输入一条原始轨迹输入子轨迹序列
23、搜索仅有两个轨迹点的子轨迹基于余弦相似性计算子轨迹的合并阀值计算子轨迹与相邻子轨迹在方向上的不相似程度将子轨迹与相邻子轨迹进行合并是是不相似程度小于阀值输出合并后的子轨迹序列输入合并后的子轨迹序列遍历每条子轨迹的边界轨迹段,计算其轮廓系数轮廓系数大于零否遍历到子轨迹另一侧的边界轨迹段或是下一条子轨迹的边界轨迹段继续计算子轨迹这一侧边界轨迹的轮廓系数对子轨迹边界进行移动对所有子轨迹的边界进行移动判断输出边界移动后的子轨迹序列保留子轨迹的起终点输出压缩后轨迹结束轨迹细划分对所有子轨迹进行合并判断轨迹方向计算轨迹方向聚类在标签变化处进行轨迹划分图 1算法框架 2.2 基于余弦相似性的子轨迹合并通过分
24、析发现,粗划分后的子轨迹序列中的部分子轨迹仅包含两个轨迹点,对于这种情况,需要考虑将该子轨迹与其相邻的子轨迹进行合并.对轨迹方向特征聚类后会得到一系列的类簇划分边界,如果某一向量距离划分边界越近,则说明该向量距离其相邻的类簇也越近,认为该向量与其相邻的类簇中的部分向量在一定条件下也是相似的,称之是可匹配的.本文定义一个阈值以判断向量是否是可匹配的,阈值将根据不同的向量进行自适应计算,如式(2)所示:mergeThreshold(x)=maxxiclusterxcosineDistance(x,xi)(2)xiclusterx其中,x 为某一向量,为与 x 属于同一类簇的向量,向量间的相似性度量
25、使用余弦距离.根据向量在所属类簇中的位置自适应计算合适的子轨迹合并阈值,如果向量靠近类簇的划分边界,那么将会得到较大的阈值;反之,则会得到较小的阈值.计算待合并子轨迹与其相邻子轨迹方向的不相似程度,将计算的结果与阈值进行对比,若小于阈值,则进行合并,否则不进行合并.越大的阈值将表现出越强的子轨迹合并倾向,而越小的阈值将表现出越弱的子轨迹合并倾向.通过考虑子轨迹间的局部方向相似情况,对子轨迹进行适当的合并,能够有效地减少某些潜在错误的轨迹划分结果,一定程度上提高了轨迹划分的准确性.子轨迹合并的伪代码如算法 1 所示.算法 1.子轨迹合并算法STRS=p1,pi,pi,pj,pm,pn(1ijmn
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 划分 自适应 轨迹 拐点 提取 压缩 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。