基于加权实数代价编辑距离的轨迹相似性度量方法

摘要

本发明公开了一种基于加权实数代价编辑距离的轨迹相似性度量方法，包括以下步骤：步骤1：将轨迹数据表示成有序的多维实数序列；步骤2：获取两两轨迹点之间的加权欧式距离；步骤3：获取两两轨迹序列之间的加权实数代价编辑距离；步骤4：采用指数函数方法，以0.99为底，以步骤3中的加权实数代价编辑距离为幂数，获取两轨迹序列之间的轨迹相似度，进而得到其他两两轨迹序列之间的轨迹相似度。本发明不要求轨迹序列等长、能适用于多维度的轨迹数据，且能动态的根据实际需求的改变每个维度对轨迹相似性的影响因子。

权利要求

1.一种基于加权实数代价编辑距离的轨迹相似性度量方法，其特征在于，包括以下步骤：步骤1：将轨迹数据表示成有序的多维实数序列，即：

Tr＝{p1(lat1,lon1,alt1,t1),p2(lati,loni,alti,ti),...,pn(latn,lonn,altn,tn)}其中，p1(lat1,lon1,alt1,t1)为第1个轨迹点，……，pn(latn,lonn,altn,tn)为第n个轨迹点，n表示的是轨迹序列中采样点的数量，lat表示纬度，lon表示经度，alt表示高度，t表示时间点；

步骤2：获取两两轨迹点之间的加权欧式距离，即轨迹点pi(lati,loni,alti,ti)和轨迹点pj(latj,lonj,altj,tj)之间的加权欧式距离|pi-pj|weighted：其中，ω1+ω2+ω3+ω4＝1；

步骤3：获取两两轨迹序列之间的加权实数代价编辑距离，即轨迹序列R和轨迹序列S之间的加权实数代价编辑距离 获取方法如下：

1)获取将轨迹序列R转化成轨迹序列S的加权实数代价WRERP(R,S)，具体为：substitute_cost(rm,sn)＝|rm-sn|weighted其中，m、n分别为轨迹序列R和轨迹序列S的长度，Rest(R)＝{r1,r2,...,rm-1}为轨迹序列R中除去当前比较字符以外的其他部分，Rest(S)为轨迹序列S的其余部分；insert_cost(sj)为往轨迹序列R里插入sj的操作代价，delete_cost(rm,sn)为从轨迹序列R里删除ri的操作代价，substitute_cost(rm,sn)为将轨迹序列R中的rm替换成sn的操作代价；

2)按步骤1)中同样方式获取将轨迹序列S转化成轨迹序列R的加权实数代价WRERP(S,R)；

3)取WRERP(R,S)和WRERP(S,R)中的较小值作为轨迹序列R和轨迹序列S的加权实数代价编辑距离 即：步骤4：采用指数函数方法，以0.99为底，以步骤3中的加权实数代价编辑距离为幂数 ，获取轨迹序列R 和轨迹序列S之间的轨迹相似度即：

说明书

基于加权实数代价编辑距离的轨迹相似性度量方法

技术领域

[0001] 本发明涉及轨迹数据分析挖掘技术领域，具体为一种基于加权实数代价编辑距离(Weighted Edit distance with Real Penalty，WRERP)的轨迹相似性度量方法。

背景技术

[0002] 随着各种无线通信技术、定位技术以及传感器技术的快速发展，大量时空轨迹数据被产生和采集，例如动物、飓风、飞机、船舶移动用户和车辆的轨迹数据。对这些数据的分析可以帮助研究者获得很多有价值的信息，例如：子热点、行为模式、位置预测、社会事件检测和识别等。如通过对台风的移动数据进行分析可以预测出台风的运动趋势；通过分析动物迁徙的数据可以总结出它们的迁徙方式，分析出它们迁徙的原因；通过分析出租车的导航数据可以得出交通流量的模式和交通拥堵的原因，为对交通流进行合理调度提供理论基础。在此背景下，时空轨迹数据的挖掘和分析已经成为数据挖掘领域中一个新的研究热点。

[0003] 然而，时空轨迹的基本分析任务就是相似性度量。相似性度量是轨迹模式挖掘、轨迹分类、轨迹异常检测、路线计算等研究热点的关键性问题之一。如轨迹聚类指的是把相似的轨迹聚集到一起成为一类；轨迹分类指的是根据轨迹之间的相似性度量训练轨迹数据建立一个模型，通过这个模型可以判断一条轨迹的类别。轨迹异常检测指的是把与群体都不相似的轨迹检测出来。此外，它本身也是一个分析任务，例如在飓风分析中。众所周知，飓风的路径是相似的，尤其是当它们在空间和时间上彼此非常接近时。因此，当一场新的飓风发生时，气象学家使用过去具有类似初始轨迹的飓风来预测飓风的发展轨迹，特别是未来再交点和登陆点的位置。欧式距离作为最经典的相似度度量方式，要求两轨迹等长，这并不适用于飞机、船舶、飓风等轨迹。LCSS距离不要求轨迹等长，但其只关注轨迹间的相似部分，而不考虑相似子序列之间的不相似部分，这不利于异常轨迹的检测。

发明内容

[0004] 本发明所要解决的技术问题是提供一种基于加权实数代价编辑距离的轨迹相似性度量方法，用欧式距离替代传统编辑距离里删除、插入和替换操作的代价，其不要求轨迹序列等长、能适用于多维度的轨迹数据，且能动态的根据实际需求的改变每个维度对轨迹相似性的影响因子。

[0005] 为解决上述技术问题，本发明采用的技术方案是：

[0006] 一种基于加权实数代价编辑距离的轨迹相似性度量方法，包括以下步骤：

[0007] 步骤1：将轨迹数据表示成有序的多维实数序列，即：

[0008] Tr＝{p1(lat1,lon1,alt1,t1),p2(lati,loni,alti,ti),...,pn(latn,lonn,altn,tn)}

[0009] 其中，p1(lat1,lon1,alt1,t1)为第1个轨迹点，……，pn(latn,lonn,altn,tn)为第n个轨迹点，n表示的是轨迹序列中采样点的数量，lat表示纬度，lon表示经度，alt表示高度，t表示时间点；

[0010] 步骤2：获取两两轨迹点之间的加权欧式距离，即轨迹点pi(lati,loni,alti,ti)和轨迹点pj(latj,lonj,altj,tj)之间的加权欧式距离|pi-pj|weighted：

[0011]

[0012] 其中，ω1+ω2+ω3+ω4＝1；

[0013] 步骤3：获取两两轨迹序列之间的加权实数代价编辑距离，即轨迹序列R和轨迹序列S之间的加权实数代价编辑距离 获取方法如下：

[0014] 1)获取将轨迹序列R转化成轨迹序列S的加权实数代价WRERP(R,S)，具体为：

[0015]

[0016]

[0017]

[0018] substitute_cost(rm,sn)＝|rm-sn|weighted

[0019] 其中，m、n分别为轨迹序列R和轨迹序列S的长度，Rest(R)＝{r1,r2,...,rm-1}为轨迹序列R中除去当前比较字符以外的其他部分，Rest(S)为轨迹序列S的其余部分；insert_cost(sj)为往轨迹序列R里插入sj的操作代价，delete_cost(rm,sn)为从轨迹序列R里删除ri的操作代价，substitute_cost(rm,sn)为将轨迹序列R中的rm替换成sn的操作代价；

[0020] 2)按步骤1)中同样方式获取将轨迹序列S转化成轨迹序列R的加权实数代价WRERP(S,R)；

[0021] 3)取WRERP(R,S)和WRERP(S,R)中的较小值作为轨迹序列R和轨迹序列S的加权实数代价编辑距离 即：

[0022]

[0023] 步骤4：采用指数函数方法，以0.99为底，以步骤3中的加权实数代价编辑距离为幂数，获取轨迹序列R 和轨迹序列S之间的轨迹相似度即：

[0024]

[0025] 与现有技术相比，本发明的有益效果是：

[0026] 1)本发明将原本只能用于字符的编辑距离改进成能应用于实数轨迹数据的加权实数代价编辑距离，其不要求轨迹序列等长、能适用于多维度的实数轨迹序列；

[0027] 2)本发明能动态的根据实际需求的改变每个维度对轨迹相似性的影响因子，更具有灵活性；

[0028] 3)本发明采用指数的方式将两轨迹间的距离转换成相似度，使其展现方式更生动易懂；

[0029] 4)本发明中轨迹相似度的计算复杂度并不会随着轨迹数据维度的增加而增加。

附图说明

[0030] 图1为本发明的在不同相似度阈值下和不同权重下的相似轨迹对数。

[0031] 图2航班3U8882的2047a699航迹与其相似轨迹的二维平面图。

[0032] 图3航班CA404的1f94cc1c航迹与其相似轨迹的二维平面图。

[0033] 图4航班HO1201的1fc37b2d航迹与其相似轨迹的二维平面图。

具体实施方式

[0034] 下面通过附图和具体实施方式对本发明作进一步详细的说明。

[0035] 本发明提出的基于加权实数代价编辑距离的轨迹相似性度量方法是对传统的编辑距离进行的一种改进，用加权欧式距离替代编辑操作代价，使其能够应用于多维实数轨迹序列，动态的根据实际需求的改变每个维度对轨迹相似性的影响因子，从而解决长度不同、多维度的轨迹之间的相似性度量问题，最后输出为轨迹之间的相似度(0-1)，相似度越接近于1则两条轨迹越相似，相似度越接近于0则两条轨迹越不相似。

[0036] 以23个航班的900多条飞机轨迹为例，具体实施方式如下：

[0037] 步骤1：将每条飞机轨迹数据表示成有序的多维实数序列，表示方式如下：

[0038] Tr＝{p1(lat1,lon1,alt1,t1),...,p2(lati,loni,alti,ti),...,pn(latn,lonn,altn,tn)}

[0039] 其中，p1(lat1,lon1,alt1,t1)为一个轨迹点，n表示的是轨迹序列中采样点的数量，lat表示纬度，lon表示经度，alt表示高度，t表示时间点。

[0040] 步骤2：获取两两轨迹点之间的加权欧式距离，以点pi(lati,loni,alti,ti)和pj(latj,lonj,altj,tj)为例，其加权欧式距离|pi-pj|weighted获取方式如下：

[0041]

[0042] 其中，ω1+ω2+ω3+ω4＝1

[0043] 步骤3：获取两两轨迹序列之间的加权实数代价编辑距离，即轨迹序列R和轨迹序列S之间的加权实数代价编辑距离 获取方法如下：

[0044] 1)获取将轨迹序列R转化成轨迹序列S的加权实数代价WRERP(R,S)，获取方式如下：

[0045]

[0046]

[0047]

[0048] substitute_cost(rm,sn)＝|rm-sn|weighted)

[0049] 其中，m、n分别为轨迹序列R和轨迹序列S的长度，Rest(R)＝{r1,r2,...,rm-1}为轨迹序列R中除去当前比较字符以外的其他部分，Rest(S)为轨迹序列S的其余部分；insert_cost(sj)为往轨迹序列R里插入sj的操作代价，delete_cost(rm,sn)为从轨迹序列R里删除ri的操作代价，substitute_cost(rm,sn)为将轨迹序列R中的rm替换成sn的操作代价。

[0050] 2)按步骤1)中同样的方法获取将轨迹序列S转化成轨迹序列R的加权实数代价WRERP(S,R)。

[0051] 3)取WRERP(R,S)和WRERP(S,R)中的较小值作为轨迹序列R和轨迹序列S的加权实数代价编辑距离 即：

[0052]

[0053] 步骤4：采用指数函数的方法，以0.99为底，以步骤3中的加权实数代价编辑距离为幂数，获取轨迹序列R和轨迹序列S之间的轨迹相似度获取方式如下：

[0054]

[0055] 其他轨迹序列对之间的相似度获取方式与上述一样。

[0056] 为对比加权重的欧式距离和不加权重的欧式距离对轨迹相似性度量的影响，进行以下五个实验：

[0057] 1)实验1：取w1＝1,w2＝1,w3＝0,w4＝0，获取欧式距离不加权重时的二维航迹的相似度；

[0058] 2)实验2：取w1＝1,w2＝1,w3＝1,w4＝0，获取欧式距离不加权重时的三维航迹的相似度；

[0059] 3)实验3：取w1＝0.5,w2＝0.5,w3＝0,w4＝0，获取欧式距离加权重时的二维航迹的相似度；

[0060] 4)实验4：取w1＝0.333,w2＝0.333,w3＝0.333,w4＝0，获取欧式距离加权重时的三维航迹的相似度；

[0061] 5)实验5：考虑到航迹中高度的变化范围远远大于经纬度，因此将高度的权重缩小到0.00001，使高度差的平方的变化范围和经纬度差的平方的变化范围相匹配。即取w1＝0.49995,w2＝0.49995,w3＝0.00001,w4＝0，获取欧式距离加权重时的三维航迹的相似度。

[0062] 实验时相似度设定阈值——threshold，当轨迹对的相似度大于threshold时则判断这两条轨迹相似，反之不相似。表1为不同阈值下的相似轨迹对数.

[0063] 表1不同阈值下的相似轨迹对数

[0064]

[0065] 图1为在不同相似度阈值下和不同权重下的相似轨迹对数。从图1中可知，使用加权欧式距离后能够发现更多的相似轨迹，且避免了随着维度的增加，轨迹间的距离就越来越大、相似性就越来越小的问题。且当面临轨迹数据各个维度之间相差甚大时，还可以通过调节欧式距离的权重来平衡差距，就如实验五所示。

[0066] 从图1可以看出，当相似度阈值超过0.5时，相似轨迹对数就开始大幅度下降，因此此处暂以0.5作为轨迹相似度阈值。在实际应用中，实验三的权重取值是更合理和普遍的，因此，从实验三的相似轨迹中，随机选取三个航班的任一航迹，画出其与其相似轨迹的二维平面图，如图2-4所示。从图2-4中，可以直观看出这些相似轨迹十分接近、相似，因此可以说明本发明的在轨迹相似性度量上的有效性。