CN110555061A - 轨迹相似度确定方法和装置 - Google Patents
轨迹相似度确定方法和装置 Download PDFInfo
- Publication number
- CN110555061A CN110555061A CN201910851151.0A CN201910851151A CN110555061A CN 110555061 A CN110555061 A CN 110555061A CN 201910851151 A CN201910851151 A CN 201910851151A CN 110555061 A CN110555061 A CN 110555061A
- Authority
- CN
- China
- Prior art keywords
- track
- behavior
- point
- trace
- points
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims abstract description 50
- 230000006399 behavior Effects 0.000 claims description 348
- 238000004422 calculation algorithm Methods 0.000 claims description 45
- 230000015654 memory Effects 0.000 claims description 20
- 238000004364 calculation method Methods 0.000 claims description 18
- 238000005259 measurement Methods 0.000 claims description 9
- 230000007704 transition Effects 0.000 claims description 8
- 230000008859 change Effects 0.000 claims description 7
- 238000007418 data mining Methods 0.000 abstract description 2
- 230000009471 action Effects 0.000 description 25
- 238000010586 diagram Methods 0.000 description 9
- 238000004891 communication Methods 0.000 description 6
- 230000006870 function Effects 0.000 description 6
- 238000004590 computer program Methods 0.000 description 4
- 230000000694 effects Effects 0.000 description 4
- 230000004048 modification Effects 0.000 description 3
- 238000012986 modification Methods 0.000 description 3
- 230000008569 process Effects 0.000 description 3
- 238000012545 processing Methods 0.000 description 3
- 230000009466 transformation Effects 0.000 description 3
- 230000008901 benefit Effects 0.000 description 2
- 238000013461 design Methods 0.000 description 2
- 230000003993 interaction Effects 0.000 description 2
- 239000004973 liquid crystal related substance Substances 0.000 description 2
- 238000011160 research Methods 0.000 description 2
- 230000001413 cellular effect Effects 0.000 description 1
- 238000006243 chemical reaction Methods 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 238000013500 data storage Methods 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 238000010295 mobile communication Methods 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 230000001151 other effect Effects 0.000 description 1
- 230000001953 sensory effect Effects 0.000 description 1
- 239000007787 solid Substances 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
- 230000000007 visual effect Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/24—Querying
- G06F16/245—Query processing
- G06F16/2458—Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/29—Geographical information databases
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- Databases & Information Systems (AREA)
- Data Mining & Analysis (AREA)
- General Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Mathematical Physics (AREA)
- Computational Linguistics (AREA)
- Software Systems (AREA)
- Probability & Statistics with Applications (AREA)
- Fuzzy Systems (AREA)
- Remote Sensing (AREA)
- Television Signal Processing For Recording (AREA)
Abstract
本申请公开了轨迹相似度确定方法，涉及数据挖掘分析领域。具体实现方案为：根据目标对象行为数据中的位置信息和时间信息，在时空坐标系中构建第一行为轨迹和第二行为轨迹；基于第一行为轨迹的各轨迹点，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离；根据最小编辑距离，确定第一行为轨迹与第二行为轨迹的相似度。本申请利用位置信息和时间信息在时空坐标系中构建行为轨迹，并基于最小编辑距离的方式对两个行为轨迹的相似度进行计算，因此能够更加准确的得到目标对象的行为轨迹相似度。
Description
技术领域
本申请涉及一种数据处理领域，尤其涉及一种数据挖掘分析领域。
背景技术
在目前的目标对象行为数据研究方案中，通常是将目标对象行为数据投影到二维平面坐标系内进行目标对象行为轨迹的构建和分析。然而这种方式忽略了时间因素对目标对象行为轨迹所产生的影响。尤其是当目标对象长时间处于同一位置时，如果不考虑时间因素，其空间位置是始终没有发生变化的，反映在坐标系中仅为一个点。而在考虑时间因素的研究方案中，由于不同行为数据的获取时间不同，同一时间节点上可能会出现无对应数据的情况，从而导致生成的行为轨迹无法准确的进行相似度研究。
发明内容
本申请实施例提供一种轨迹相似度确定方法和装置，以解决现有技术中的一个或多个技术问题。
第一方面，本申请实施例提供了一种轨迹相似度确定方法，包括：
根据目标对象行为数据中的位置信息和时间信息，在时空坐标系中构建第一行为轨迹和第二行为轨迹；
基于第一行为轨迹的各轨迹点，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离；
根据最小编辑距离，确定第一行为轨迹与第二行为轨迹的相似度。
本实施例利用位置信息和时间信息在时空坐标系中构建行为轨迹，并基于最小编辑距离的方式对两个行为轨迹的相似度进行计算，因此能够更加准确的确定目标对象的行为轨迹相似度。
在一种实施方式中，基于第一行为轨迹的各轨迹点，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离，包括：
在第一行为轨迹上确定第一目标轨迹点；
在第二行为轨迹上生成第二目标轨迹点，第二目标轨迹点与第一目标轨迹点的坐标相同；
根据预设编辑距离算法，计算生成第二目标轨迹点的第一编辑距离；
利用递归求解算法，计算第二目标轨迹点之前的第二行为轨迹转换到第一目标轨迹点之前的第一行为轨迹的第二编辑距离；
根据第一编辑距离和第二编辑距离，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离。
本实施例通过在第二行为轨迹上生成第二目标轨迹点，弥补了目标对象行为数据不足，导致的第二行为轨迹缺失进行相似度比较的轨迹点的问题。
在一种实施方式中，基于第一行为轨迹的各轨迹点，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离，包括：
在第一行为轨迹上确定第三目标轨迹点和第四目标轨迹点；
去除第二行为轨迹上的冗余轨迹点，冗余轨迹点为时间坐标处于第三目标轨迹点与第四目标轨迹点的时间坐标之间的的轨迹点；
根据预设编辑距离算法，计算去除冗余轨迹点的第三编辑距离；
利用递归求解算法，计算冗余轨迹点之前的第二行为轨迹转换到第三目标轨迹点之前的第一行为轨迹的第四编辑距离；
根据第三编辑距离和第四编辑距离，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离。
本实施例通过在第二行为轨迹上去除冗余轨迹点，弥补了由于用户行为数据量不一致，导致的第一行为轨迹与第二行为轨迹难以进行相似度比较的问题。
在一种实施方式中，在第二行为轨迹上生成第二目标轨迹点，包括：
将第二行为轨迹上的一个轨迹点变更为第二目标轨迹点；或，
在第二行为轨迹上增加一个第二目标轨迹点。
本实施例可以实现根据不同情况，选择不同的第二轨迹点生成方式。
在一种实施方式中，将第二行为轨迹上的一个轨迹点变更为第二目标轨迹点的预设编辑距离算法为：
其中，L(P1，P2)表示变更轨迹点的预设编辑距离，P1表示第二行为轨迹上的一个轨迹点，P2表示第二目标轨迹点，x1为P1在X轴的坐标，y1为P1在Y轴的坐标，x2为P2在X轴的坐标，y2为P2在Y轴的坐标。
本实施例的算法能够准确的计算出变更轨迹点的编辑距离。
在一种实施方式中，在第二行为轨迹上增加一个第二目标轨迹点的预设编辑距离算法为：
其中，AL(Pk)表示增加轨迹点的预设编辑距离，Pk表示增加的第二目标轨迹点，Pi表示第二行为轨迹上位于第二目标轨迹点之前的一个轨迹点，Pj表示第二行为轨迹上位于第二目标轨迹点之后的一个轨迹点，L(Pi，Pk)表示轨迹点Pi与轨迹点Pk之间的编辑距离，L(Pk，Pj)表示轨迹点Pk与轨迹点Pj之间的编辑距离。
本实施例的算法能够准确的计算出增加轨迹点的编辑距离。
在一种实施方式中，去除第二行为轨迹上的冗余轨迹点的预设编辑距离算法为：
其中，DL(Pk)表示去除冗余轨迹点的预设编辑距离，Pk表示冗余轨迹点，Pi表示第二行为轨迹上位于冗余轨迹点之前的一个轨迹点，Pj表示第二行为轨迹上位于冗余轨迹点之后的一个轨迹点，L(Pi，Pk)表示轨迹点Pi与轨迹点Pk之间的编辑距离，L(Pk，Pj)表示轨迹点Pk与轨迹点Pj之间的编辑距离。
本实施例的算法能够准确的计算出去除轨迹点的编辑距离。
在一种实施方式中，根据目标对象行为数据中的位置信息和时间信息，在时空坐标系中构建第一行为轨迹和第二行为轨迹，包括：
根据各位置信息，基于时空坐标系的经度坐标轴和纬度坐标轴生成初始坐标点；
根据各位置信息对应的时间信息，基于时空坐标系的时间坐标轴，按时序对各初始坐标点进行排列，形成多个轨迹点；
基于多个轨迹点，构建第一行为轨迹和第二行为轨迹。
本实施例在时空坐标系中构建出了包含有时间特征的行为轨迹，使得构建的第一行为轨迹和第二行为轨迹更具相似度比较的价值。
在一种实施方式中，根据各位置信息，基于时空坐标系的经度坐标轴和纬度坐标轴生成初始坐标点之前，还包括：
将各位置信息的度量单位统一为经纬度单位；
将各时间信息的度量单位进行统一。
本实施例通过对度量单位进行统一，解决了因度量单位不一致导致的编辑距离计算误差，同时还降低了构建行为轨迹和计算编辑距离的复杂性。
第二方面，本申请实施例提供了一种轨迹相似度确定装置，包括：
构建模块，用于根据目标对象行为数据中的位置信息和时间信息，在时空坐标系中构建第一行为轨迹和第二行为轨迹；
计算模块，用于基于第一行为轨迹的各轨迹点，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离；
确定模块，用于根据最小编辑距离，确定第一行为轨迹与第二行为轨迹的相似度。
在一种实施方式中，计算模块包括：
第一确定子模块，用于在第一行为轨迹上确定第一目标轨迹点；
第一生成子模块，用于在第二行为轨迹上生成第二目标轨迹点，第二目标轨迹点与第一目标轨迹点的坐标相同；
第一计算子模块，用于根据预设编辑距离算法，计算生成第二目标轨迹点的第一编辑距离；
第二计算子模块，用于利用递归求解算法，计算第二目标轨迹点之前的第二行为轨迹转换到第一目标轨迹点之前的第一行为轨迹的第二编辑距离；
第三计算子模块，用于根据第一编辑距离和第二编辑距离，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离。
在一种实施方式中，计算模块包括：
第二确定子模块，用于在第一行为轨迹上确定第三目标轨迹点和第四目标轨迹点；
去除子模块，用于去除第二行为轨迹上的冗余轨迹点，冗余轨迹点为时间坐标处于第三目标轨迹点与第四目标轨迹点的时间坐标之间的的轨迹点；
第四计算子模块，用于根据预设编辑距离算法，计算去除冗余轨迹点的第三编辑距离；
第五计算子模块，用于利用递归求解算法，计算冗余轨迹点之前的第二行为轨迹转换到第三目标轨迹点之前的第一行为轨迹的第四编辑距离；
第六计算子模块，用于根据第三编辑距离和第四编辑距离，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离。
在一种实施方式中，第一生成子模块包括：
生成单元，用于将第二行为轨迹上的一个轨迹点变更为第二目标轨迹点；或，用于在第二行为轨迹上增加一个第二目标轨迹点。
在一种实施方式中，构建模块包括：
第二生成子模块，用于根据各位置信息，基于时空坐标系的经度坐标轴和纬度坐标轴生成初始坐标点；
形成子模块，用于根据各位置信息对应的时间信息，基于时空坐标系的时间坐标轴，按时序对各初始坐标点进行排列，形成多个轨迹点；
构建子模块，用于基于多个轨迹点，构建第一行为轨迹和第二行为轨迹。
第三方面，本申请实施例提供了一种电子设备，电子设备的功能可以通过硬件实现，也可以通过硬件执行相应的软件实现。硬件或软件包括一个或多个与上述功能相对应的模块。
在一个可能的设计中，电子设备的结构中包括处理器和存储器，存储器用于存储支持电子设备执行上述轨迹相似度确定方法的程序，处理器被配置为用于执行存储器中存储的程序。电子设备还可以包括通信接口，用于与其他设备或通信网络通信。
第四方面，本申请实施例提供了一种存储有计算机指令的非瞬时计算机可读存储介质，用于存储电子设备及电子设备所用的计算机软件指令，其包括用于执行上述轨迹相似度确定所涉及的程序。
上述申请中的一个实施例具有如下优点或有益效果：本申请因为采用利用位置信息和时间信息在时空坐标系构建行为轨迹，以及基于最小编辑距离计算两个行为轨迹相似度的技术手段，所以克服了在二维平面坐标系中构建和分析行为轨迹时，忽略时间因素的技术问题，进而达到能够更加准确的得到目标对象的行为轨迹相似度技术效果。
上述可选方式所具有的其他效果将在下文中结合具体实施例加以说明。
附图说明
附图用于更好地理解本方案，不构成对本申请的限定。其中：
图1是根据本申请第一实施例的轨迹相似度确定方法的流程示意图；
图2是根据本申请第一实施例的轨迹相似度确定方法的步骤S100的流程示意图；
图3是根据本申请第一实施例的在时空坐标系中构建行为轨迹的示意图；
图4是根据本申请第一实施例的另一轨迹相似度确定方法的步骤S100的流程示意图；
图5是根据本申请第一实施例的轨迹相似度确定方法的步骤S200的流程示意图；
图6是根据本申请第一实施例的另一轨迹相似度确定方法的步骤S200的流程示意图；
图7是根据本申请第一实施例的轨迹相似度确定方法的流程框图；
图8是根据本申请第二实施例的轨迹相似度确定装置的示意图；
图9是根据本申请第二实施例的轨迹相似度确定装置的计算模块的示意图；
图10是根据本申请第二实施例的另一轨迹相似度确定装置的计算模块的示意图；
图11是根据本申请第二实施例的轨迹相似度确定装置的第一生成子模块的示意图；
图12是根据本申请第二实施例的轨迹相似度确定装置的构建模块的示意图；
图13是用来实现本申请实施例的轨迹相似度确定方法的电子设备的框图。
具体实施方式
以下结合附图对本申请的示范性实施例做出说明，其中包括本申请实施例的各种细节以助于理解，应当将它们认为仅仅是示范性的。因此，本领域普通技术人员应当认识到，可以对这里描述的实施例做出各种改变和修改，而不会背离本申请的范围和精神。同样，为了清楚和简明，以下的描述中省略了对公知功能和结构的描述。
根据本申请的第一实施例，本申请提供了一种轨迹相似度确定方法，如图1所示，该方法包括：
S100：根据目标对象行为数据中的位置信息和时间信息，在时空坐标系中构建第一行为轨迹和第二行为轨迹。
目标对象行为数据可以包括目标对象在线上活动或线下活动中所留下的行为轨迹信息。例如，道路卡口、摄像头、基站等采集到的目标对象的行为。又如，目标对象通过对终端操作，所记录下的目标对象的行为。
目标对象可以是人、车辆等。
位置信息可以包括目标对象不同时刻产生行为的地点信息、地点坐标、GPS信息等。时间信息可以包括目标对象产生行为的时间。且时间信息与位置信息是相关联的，每个位置信息都具有对应的时间信息。
时空坐标系至少为三维时空坐标系，具体采用的坐标系可以根据需要进行选择。
第一行为轨迹可以是基于目标对象同一行为数据源的数据所构建的，也可以是基于多个不同行为数据源的数据所构建的。第二行为轨迹同理，不再赘述。在构建第一行为轨迹和第二行为轨迹时，两条轨迹所利用的目标对象行为数据可以均是同一时间范围内所采集到的数据。也可以仅部分行为数据时同一时间范围内所采集到的数据。其中，时间范围的大小可以根据需要进行选择。例如，同一时刻的行为数据、同一天的行为数据或是同一月、同一年的行为数据均可。
在一个示例中，第一行为轨迹和第二行为轨迹均是融合了目标对象的线上、线下活动行为而构建的。因此能够在时间和空间两个维度的基础上，更加全面的反应目标对象的行为轨迹。
S200：基于第一行为轨迹的各轨迹点，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离。最小编辑距离可以理解为将第二行为轨迹完全转换为第一行为轨迹所需的最小操作成本。
S300：根据最小编辑距离，确定第一行为轨迹与第二行为轨迹的相似度。
本实施例利用位置信息和时间信息在时空坐标系中构建行为轨迹，并基于最小编辑距离的方式对两个行为轨迹的相似度进行计算，因此能够更加准确的确定目标对象的行为轨迹相似度。
在一种实施方式中，如图2所示，根据目标对象行为数据中的位置信息和时间信息，在时空坐标系中构建第一行为轨迹和第二行为轨迹，包括：
S110：根据各位置信息，基于时空坐标系的经度坐标轴和纬度坐标轴生成初始坐标点。
S120：根据各位置信息对应的时间信息，基于时空坐标系的时间坐标轴，按时序对各初始坐标点进行排列，形成多个轨迹点。
S130：基于多个轨迹点，构建第一行为轨迹和第二行为轨迹。
在一个示例中，构建第一行为轨迹所需的轨迹点和构建第二行为轨迹所需的轨迹点可以根据需要进行选择。第一行为轨迹和第二行为轨迹可以包括相同的轨迹点。
本实施例在时空坐标系中构建出了包含有时间特征的行为轨迹，使得构建的第一行为轨迹和第二行为轨迹更具相似度比较的价值。
在一个应用示例中，如图3所示，时空坐标系包括表示经度的X轴，表示纬度的Y轴，以及表示时间的Z轴。根据目标对象行为数据中的位置信息和时间信息，在时空坐标系中生成一系列的坐标点P1(x1，y1，z1)、P2(x2，y2，z2)、P3(x3，y3，z3)、P4(x4，y4，z4)、Q1(x5，y5，z5)、Q2(x6，y6，z6)、Q3(x7，y7，z7)、Q4(x8，y8，z8)。其中，P1、P2、P3、P4构建了第一行为轨迹，Q1、Q2、Q3、Q4构建了第二行为轨迹。每两个轨迹点之间通过有向向量进行连接，有向向量表示两个轨迹点之间的时间位置关系。
如果目标对象的位置发生了变化，其位置信息是不同的，在时空坐标系中所生成的轨迹点也是不同的。如果目标对象的位置没有发生变化，但是由于时间是持续的，即便根据位置信息生成的各轨迹点在XY轴所构建平面上的投影是一个点，但在Z轴上仍可以体现为不同轨迹点(平行于Z轴的多个轨迹点)。由此可知，即便目标对象的位置没有发生变化，本申请构建的时空坐标系也能够很好的对目标对象的行为进行很好的展现。
在一个示例中，时空坐标系的坐标轴单位可以根据需要进行选择调整，并不限于经纬度坐标轴。
在一种实施方式中，如图4所示，根据各位置信息，基于时空坐标系的经度坐标轴和纬度坐标轴生成初始坐标点之前，还包括：
S140：将各位置信息的度量单位统一为经纬度单位。
S150：将各时间信息的度量单位进行统一。
本实施例通过对度量单位进行统一，降低了构建行为轨迹和计算编辑距离的复杂性。
在一种实施方式中，如图5所示，基于第一行为轨迹的各轨迹点，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离，包括：
S201：在第一行为轨迹上确定第一目标轨迹点。第一目标轨迹点可以是第一行为轨迹上的任一点。
S202：在第二行为轨迹上生成第二目标轨迹点，第二目标轨迹点与第一目标轨迹点的坐标相同。可以理解为在第二行为轨迹上生成第一目标轨迹点。
S203：根据预设编辑距离算法，计算在第二行为轨迹上生成第二目标轨迹点的第一编辑距离。根据生成第二目标轨迹点的方式不同，预设编辑距离算法可以不同。
S204：利用递归求解算法，计算第二目标轨迹点之前的第二行为轨迹转换到第一目标轨迹点之前的第一行为轨迹的第二编辑距离。
S205：根据第一编辑距离和第二编辑距离，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离。
本实施例通过在第二行为轨迹上生成第二目标轨迹点，弥补了目标对象行为数据不足，导致的第二行为轨迹缺失进行相似度比较的轨迹点的问题。
在一个示例中，第二行为轨迹上位于第二目标轨迹点之前的各轨迹点，也可以通过上述步骤进行编辑距离计算。第二行为轨迹上的每个轨迹点均可以被认为是第二目标轨迹点。
在一个示例中，第一行为轨迹包括m个轨迹点，第二行为轨迹包括n个轨迹点。当第一行为轨迹上的轨迹点m作为第一目标轨迹点时，在第二行为轨迹上生成一个轨迹点m(将第二行为轨迹上的轨迹点n变更为轨迹点m)，然后计算将轨迹点n变更为轨迹点m的编辑距离，以及计算轨迹点n之前的第二行为轨迹转变为m点之前的第一行为轨迹的编辑距离。
计算轨迹点n之前的第二行为轨迹转变为m点之前的第一行为轨迹的编辑距离，包括：将第一行为轨迹上的m-1作为第一目标轨迹点，在轨迹点n之前的第二行为轨迹上添加一个轨迹点m-1，然后计算在轨迹点n之前的第二行为轨迹上添加一个轨迹点m-1的编辑距离，以及计算轨迹点m-1之前的第二行为轨迹转变为m-1点之前的第一行为轨迹的编辑距离。
利用递归求解的方式，按时间顺序由后至前依次计算第二行为轨迹上各轨迹点，直至完成第二行为轨迹到第一行为轨迹的转换。
在一个示例中，还可以利用动态规划求解的方式，计算第二行为轨迹转换到第一行为轨迹的第二编辑距离。
在一种实施方式中，在第二行为轨迹上生成第二目标轨迹点，包括：
将第二行为轨迹上的一个轨迹点变更为第二目标轨迹点。或，
在第二行为轨迹上增加一个第二目标轨迹点。
本实施例可以实现根据不同情况，选择不同的第二轨迹点生成方式。
在一个示例中，本申请中任意两个轨迹点之间的编辑距离均可采用下述编辑距离公式计算。
其中，L(P1，P2)表示两个轨迹点的编辑距离，P1表示轨迹点，P2表示轨迹点，x1为P1在X轴的位置坐标，y1为P1在Y轴的位置坐标，x2为P2在X轴的位置坐标，y2为P2在Y轴的位置坐标，z1为P1在Z轴的时间坐标，z2为P2在Z轴的时间坐标，k表示时间阈值。
当P1和P2之间的时间差小于时间阈值k时，则可通过计算编辑距离。
当P1和P2之间的时间差大于时间阈值k时，则认为两个轨迹点之间的编辑距离无穷远。
时间阈值k可以进行调整。当行为轨迹上的轨迹点较稀疏时，k值可以适当增大。当行为轨迹上的轨迹点较密集时，k值可以适当减小。从而使得两个轨迹点之间的编辑距离公式可以适配不同的行为轨迹。
在一种实施方式中，将第二行为轨迹上的一个轨迹点变更为第二目标轨迹点的预设编辑距离算法为：
其中，L(P1，P2)表示变更轨迹点的预设编辑距离，P1表示第二行为轨迹上的一个轨迹点，P2表示第二目标轨迹点，x1为P1在X轴的坐标，y1为P1在Y轴的坐标，x2为P2在X轴的坐标，y2为P2在Y轴的坐标。当P1和P2之间的时间差小于时间阈值k时，两个点之间的时间属性可以抹去，其之间的距离等同于在X、Y轴所形成的平面坐标系内的欧式距离，因此可通过计算编辑距离。当P1和P2之间的时间差大于时间阈值k时，则认为两个轨迹点之间的编辑距离无穷远。
本实施例的算法能够准确的计算出变更轨迹点的编辑距离。
在一种实施方式中，在第二行为轨迹上增加一个第二目标轨迹点的预设编辑距离算法为：
其中，AL(Pk)表示增加轨迹点的预设编辑距离，Pk表示增加的第二目标轨迹点，Pi表示第二行为轨迹上位于第二目标轨迹点之前的一个轨迹点，Pj表示第二行为轨迹上位于第二目标轨迹点之后的一个轨迹点。N表示第二行为轨迹上的最后一个轨迹点。L(Pi，Pk)表示轨迹点Pi与轨迹点Pk之间的编辑距离。L(Pk，Pj)表示轨迹点Pk与轨迹点Pj之间的编辑距离。
本实施例的算法能够准确的计算出增加轨迹点的编辑距离。
在一种实施方式中，如图6所示，基于第一行为轨迹的各轨迹点，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离，包括：
S206：在第一行为轨迹上确定第三目标轨迹点和第四目标轨迹点。第三目标轨迹点和第四目标轨迹点可以是第一行为轨迹上的任意两个轨迹点。
S207：去除第二行为轨迹上的冗余轨迹点，冗余轨迹点为时间坐标处于第三目标轨迹点与第四目标轨迹点的时间坐标之间的的轨迹点。
在一个示例中，当第一行为轨迹上有8个轨迹点，而第二行为轨迹上有9个轨迹点时，则可以将第二行为轨迹上多余的轨迹点去除。
S208：根据预设编辑距离算法，计算去除冗余轨迹点的第三编辑距离。
S209：利用递归求解算法，计算冗余轨迹点之前的第二行为轨迹转换到第三目标轨迹点之前的第一行为轨迹的第四编辑距离。
S210：根据第三编辑距离和第四编辑距离，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离。
本实施例通过在第二行为轨迹上去除冗余轨迹点，弥补了由于用户行为数据量不一致，导致的第一行为轨迹与第二行为轨迹难以进行相似度比较的问题。
在一种实施方式中，去除第二行为轨迹上的冗余轨迹点的预设编辑距离算法为：
其中，DL(Pk)表示去除冗余轨迹点的预设编辑距离，Pk表示冗余轨迹点，Pi表示第二行为轨迹上位于冗余轨迹点之前的一个轨迹点，Pj表示第二行为轨迹上位于冗余轨迹点之后的一个轨迹点。L(Pi，Pk)表示轨迹点Pi与轨迹点Pk之间的编辑距离。L(Pk，Pj)表示轨迹点Pk与轨迹点Pj之间的编辑距离。
本实施例的算法能够准确的计算出去除轨迹点的编辑距离。
在一个示例中，第二行为轨迹可以分别通过增加轨迹点、删除轨迹点以及变更轨迹点的方式，计算第二行为轨迹到第一行为轨迹的编辑距离。每个轨迹点的不同变换方式会得到不同的编辑距离，并且每个轨迹点的变换均会对其他轨迹点的变换方式产生不同程度的影响，使得其他轨迹点的编辑距离发生改变。因此为了准确的获取到第二行为轨迹转变为第一行为轨迹的最小编辑距离，可以对每个轨迹点均分别采用上述三种方式计算编辑距离。
在一个示例中，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离，可以采同以下公式：
其中，E(Pa，Qb)表示截止到轨迹点Pa的第一行为轨迹与截止到轨迹点Qb的第二行为轨迹之间的编辑距离。AL(Pa)表示增加轨迹点Pa。AL(Qb)表示增加轨迹点Qb。E(Pa-1，Qb-1)表示截止到轨迹点Pa-1的第一行为轨迹与截止到轨迹点Qb-1的第二行为轨迹之间的编辑距离。E(Pa-1，Qb)表示截止到轨迹点Pa-1的第一行为轨迹与截止到轨迹点Qb的第二行为轨迹之间的编辑距离。E(Pa，Qb-1)表示截止到轨迹点Pa的第一行为轨迹与截止到轨迹点Qb-1的第二行为轨迹之间的编辑距离。L(Pa，Qb)表示轨迹点Pa到轨迹点Qb的最小编辑距离。a表示第一行为轨迹的第a个轨迹点，b表示第二行为轨迹的第b个轨迹点，m表示第一行为轨迹的最后一个轨迹点，n表示第二行为轨迹的最后一个轨迹点。
的含义为：在第二行为轨迹点Qb之后增加第一行为轨迹截止到轨迹点Pa的所有轨迹点。
的含义为：在第一行为轨迹点Pa之后增加第二行为轨迹截止到轨迹点Qb的所有轨迹点。
E(Pa，Qb)＝E(Pa-1，Qb-1)的含义为：轨迹点Pa与Qb重合，此刻两个行为轨迹的增量为0，因此只需计算截止到轨迹点Pa-1的第一行为轨迹与截止到轨迹点Qb-1的第二行为轨迹之间的编辑距离。
E(Pa，Qb)＝E(Pa-1，Qb-1)+L(Pa，Qb)的含义为：计算轨迹点Pa到轨迹点Qb的最小编辑距离，以及截止到轨迹点Pa-1的第一行为轨迹与截止到轨迹点Qb-1的第二行为轨迹之间的最小编辑距离。
E(Pa，Qb)＝E(Pa-1，Qb)+AL(Pa)的含义为：计算在第二行为轨迹上增加轨迹点Pa的编辑距离，以及截止到轨迹点Pa-1的第一行为轨迹与截止到轨迹点Qb的第二行为轨迹之间的最小编辑距离。
E(Pa，Qb)＝E(Pa，Qb-1)+AL(Qb)的含义为：计算在第一行为轨迹上增加轨迹点Qb的编辑距离，以及截止到轨迹点Pa的第一行为轨迹与截止到轨迹点Qb-1的第二行为轨迹之间的编辑距离。
通过上述递归算法，对各轨迹点如此递归下去，即可准确的计算出两个行为轨迹的相似度。
本申请实施例在进行两个行为轨迹的相似度比较时，通过增加轨迹点、删除轨迹点以及变更轨迹点的方式可以解决目标对象行为数据中丢失轨迹点、多记录轨迹点及错误记录轨迹点的问题。
在一个示例中，如图7所示，本申请轨迹的相似度确定方法包括：
轨迹信息坐标化过程：基于目标对象的线上轨迹信息、线下轨迹信息、其他轨迹信息，对轨迹信息中的位置信息时空化，生成位于经纬度坐标系中的初始坐标点。然后利用时间信息对各初始坐标点时空序列化，生成在时空坐标系中的三维空间轨迹点。
时空轨迹(行为轨迹)定义过程：定义任意两个轨迹点之间的编辑距离，以及定义增加轨迹点、删除轨迹点和变更轨迹点的编辑距离。
研究相似性过程：通过增加轨迹点、删除轨迹点和变更轨迹点的方式，利用递归算法计算时空轨迹的相似性。
根据本申请的第二实施例，本申请提供了一种轨迹相似度确定装置，如图8所示，该轨迹相似度确定装置100包括：
构建模块10，用于根据目标对象行为数据中的位置信息和时间信息，在时空坐标系中构建第一行为轨迹和第二行为轨迹。
计算模块20，用于基于第一行为轨迹的各轨迹点，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离。
确定模块30，用于根据最小编辑距离，确定第一行为轨迹与第二行为轨迹的相似度。
在一种实施方式中，如图9所示，计算模块20包括：
第一确定子模块201，用于在第一行为轨迹上确定第一目标轨迹点。
第一生成子模块202，用于在第二行为轨迹上生成第二目标轨迹点，第二目标轨迹点与第一目标轨迹点的坐标相同。
第一计算子模块203，用于根据预设编辑距离算法，计算生成第二目标轨迹点的第一编辑距离。
第二计算子模块204，用于利用递归求解算法，计算第二目标轨迹点之前的第二行为轨迹转换到第一目标轨迹点之前的第一行为轨迹的第二编辑距离。
第三计算子模块205，用于根据第一编辑距离和第二编辑距离，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离。
在一种实施方式中，如图10所示，计算模块20包括：
第二确定子模块206，用于在第一行为轨迹上确定第三目标轨迹点和第四目标轨迹点。
去除子模块207，用于去除第二行为轨迹上的冗余轨迹点，冗余轨迹点为时间坐标处于第三目标轨迹点与第四目标轨迹点的时间坐标之间的的轨迹点。
第四计算子模块208，用于根据预设编辑距离算法，计算去除冗余轨迹点的第三编辑距离。
第五计算子模块209，用于利用递归求解算法，计算冗余轨迹点之前的第二行为轨迹转换到第三目标轨迹点之前的第一行为轨迹的第四编辑距离。
第六计算子模块210，用于根据第三编辑距离和第四编辑距离，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离。
在一种实施方式中，如图11所示，第一生成子模块202包括：
生成单元2021，用于将第二行为轨迹上的一个轨迹点变更为第二目标轨迹点。或，用于在第二行为轨迹上增加一个第二目标轨迹点。
在一种实施方式中，如图12所示，构建模块10包括：
第二生成子模块11，用于根据各位置信息，基于时空坐标系的经度坐标轴和纬度坐标轴生成初始坐标点。
形成子模块12，用于根据各位置信息对应的时间信息，基于时空坐标系的时间坐标轴，按时序对各初始坐标点进行排列，形成多个轨迹点。
构建子模块13，用于基于多个轨迹点，构建第一行为轨迹和第二行为轨迹。
在一种实施方式中，生成单元2021中将第二行为轨迹上的一个轨迹点变更为第二目标轨迹点的预设编辑距离算法为：
其中，L(P1，P2)表示变更轨迹点的预设编辑距离，P1表示第二行为轨迹上的一个轨迹点，P2表示第二目标轨迹点，x1为P1在X轴的坐标，y1为P1在Y轴的坐标，x2为P2在X轴的坐标，y2为P2在Y轴的坐标。
在一种实施方式中，生成单元2021中在第二行为轨迹上增加一个第二目标轨迹点的预设编辑距离算法为：
其中，AL(Pk)表示增加轨迹点的预设编辑距离，Pk表示增加的第二目标轨迹点，Pi表示第二行为轨迹上位于第二目标轨迹点之前的一个轨迹点，Pj表示第二行为轨迹上位于第二目标轨迹点之后的一个轨迹点，L(Pi，Pk)表示轨迹点Pi与轨迹点Pk之间的编辑距离，L(Pk，Pj)表示轨迹点Pk与轨迹点Pj之间的编辑距离。
在一种实施方式中，第四计算子模块208中去除第二行为轨迹上的冗余轨迹点的预设编辑距离算法为：
其中，DL(Pk)表示去除冗余轨迹点的预设编辑距离，Pk表示冗余轨迹点，Pi表示第二行为轨迹上位于冗余轨迹点之前的一个轨迹点，Pj表示第二行为轨迹上位于冗余轨迹点之后的一个轨迹点，L(Pi，Pk)表示轨迹点Pi与轨迹点Pk之间的编辑距离，L(Pk，Pj)表示轨迹点Pk与轨迹点Pj之间的编辑距离。
在一个示例中，计算模块20用于计算第二行为轨迹转换到第一行为轨迹的最小编辑距离，可以采用以下公式：
其中，E(Pa，Qb)表示截止到轨迹点Pa的第一行为轨迹与截止到轨迹点Qb的第二行为轨迹之间的编辑距离。AL(Pa)表示增加轨迹点Pa。AL(Qb)表示增加轨迹点Qb。E(Pa-1，Qb-1)表示截止到轨迹点Pa-1的第一行为轨迹与截止到轨迹点Qb-1的第二行为轨迹之间的编辑距离。E(Pa-1，Qb)表示截止到轨迹点Pa-1的第一行为轨迹与截止到轨迹点Qb的第二行为轨迹之间的编辑距离。E(Pa，Qb-1)表示截止到轨迹点Pa的第一行为轨迹与截止到轨迹点Qb-1的第二行为轨迹之间的编辑距离。L(Pa，Qb)表示轨迹点Pa到轨迹点Qb的最小编辑距离。a表示第一行为轨迹的第a个轨迹点，b表示第二行为轨迹的第b个轨迹点，m表示第一行为轨迹的最后一个轨迹点，n表示第二行为轨迹的最后一个轨迹点。
的含义为：在第二行为轨迹点Qb之后增加第一行为轨迹截止到轨迹点Pa的所有轨迹点。
的含义为：在第一行为轨迹点Pa之后增加第二行为轨迹截止到轨迹点Qb的所有轨迹点。
E(Pa，Qb)＝E(Pa-1，Qb-1)的含义为：轨迹点Pa与Qb重合，此刻两个行为轨迹的增量为0，因此只需计算截止到轨迹点Pa-1的第一行为轨迹与截止到轨迹点Qb-1的第二行为轨迹之间的编辑距离。
E(Pa，Qb)＝E(Pa-1，Qb-1)+L(Pa，Qb)的含义为：计算轨迹点Pa到轨迹点Qb的最小编辑距离，以及截止到轨迹点Pa-1的第一行为轨迹与截止到轨迹点Qb-1的第二行为轨迹之间的最小编辑距离。
E(Pa，Qb)＝E(Pa-1，Qb)+AL(Pa)的含义为：计算在第二行为轨迹上增加轨迹点Pa的编辑距离，以及截止到轨迹点Pa-1的第一行为轨迹与截止到轨迹点Qb的第二行为轨迹之间的最小编辑距离。
E(Pa，Qb)＝E(Pa，Qb-1)+AL(Qb)的含义为：计算在第一行为轨迹上增加轨迹点Qb的编辑距离，以及截止到轨迹点Pa的第一行为轨迹与截止到轨迹点Qb-1的第二行为轨迹之间的编辑距离。
需要说明的是，本申请提供的轨迹相似度确定装置100可以实现上述任一轨迹相似度确定方法实施例。
根据本申请的实施例，本申请还提供了一种电子设备和一种可读存储介质。
如图13所示，是根据本申请实施例的轨迹相似度确定的方法的电子设备的框图。电子设备旨在表示各种形式的数字计算机，诸如，膝上型计算机、台式计算机、工作台、个人数字助理、服务器、刀片式服务器、大型计算机、和其它适合的计算机。电子设备还可以表示各种形式的移动装置，诸如，个人数字处理、蜂窝电话、智能电话、可穿戴设备和其它类似的计算装置。本文所示的部件、它们的连接和关系、以及它们的功能仅仅作为示例，并且不意在限制本文中描述的和/或者要求的本申请的实现。
如图13所示，该电子设备包括：一个或多个处理器901、存储器902，以及用于连接各部件的接口，包括高速接口和低速接口。各个部件利用不同的总线互相连接，并且可以被安装在公共主板上或者根据需要以其它方式安装。处理器可以对在电子设备内执行的指令进行处理，包括存储在存储器中或者存储器上以在外部输入/输出装置(诸如，耦合至接口的显示设备)上显示图形用户界面(Graphical User lnterface，GUI)的图形信息的指令。在其它实施方式中，若需要，可以将多个处理器和/或多条总线与多个存储器和多个存储器一起使用。同样，可以连接多个电子设备，各个设备提供部分必要的操作(例如，作为服务器阵列、一组刀片式服务器、或者多处理器系统)。图13中以一个处理器901为例。
存储器902即为本申请所提供的非瞬时计算机可读存储介质。其中，所述存储器存储有可由至少一个处理器执行的指令，以使所述至少一个处理器执行本申请所提供的轨迹相似度确定的方法。本申请的非瞬时计算机可读存储介质存储计算机指令，该计算机指令用于使计算机执行本申请所提供的轨迹相似度确定的方法。
存储器902作为一种非瞬时计算机可读存储介质，可用于存储非瞬时软件程序、非瞬时计算机可执行程序以及模块，如本申请实施例中的轨迹相似度确定的方法对应的程序指令/模块(例如，附图8所示的构建模块10、计算模块20和确定模块30)。处理器901通过运行存储在存储器902中的非瞬时软件程序、指令以及模块，从而执行服务器的各种功能应用以及数据处理，即实现上述方法实施例中的轨迹相似度确定的方法。
存储器902可以包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需要的应用程序；存储数据区可存储根据轨迹相似度确定的电子设备的使用所创建的数据等。此外，存储器Y02可以包括高速随机存取存储器，还可以包括非瞬时存储器，例如至少一个磁盘存储器件、闪存器件、或其他非瞬时固态存储器件。在一些实施例中，存储器902可选包括相对于处理器901远程设置的存储器，这些远程存储器可以通过网络连接至轨迹相似度确定的电子设备。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。
轨迹相似度确定的方法的电子设备还可以包括：输入装置903和输出装置904。处理器901、存储器902、输入装置903和输出装置904可以通过总线或者其他方式连接，图13中以通过总线连接为例。
输入装置903可接收输入的数字或字符信息，以及产生与轨迹相似度确定的电子设备的用户设置以及功能控制有关的键信号输入，例如触摸屏、小键盘、鼠标、轨迹板、触摸板、指示杆、一个或者多个鼠标按钮、轨迹球、操纵杆等输入装置。输出装置904可以包括显示设备、辅助照明装置(例如，LED)和触觉反馈装置(例如，振动电机)等。该显示设备可以包括但不限于，液晶显示器(Liquid Crystal Display，LCD)、发光二极管(Light EmittingDiode，LED)显示器和等离子体显示器。在一些实施方式中，显示设备可以是触摸屏。
此处描述的系统和技术的各种实施方式可以在数字电子电路系统、集成电路系统、专用集成电路(Application Specific lntegrated Circuits，ASIC)、计算机硬件、固件、软件、和/或它们的组合中实现。这些各种实施方式可以包括：实施在一个或者多个计算机程序中，该一个或者多个计算机程序可在包括至少一个可编程处理器的可编程系统上执行和/或解释，该可编程处理器可以是专用或者通用可编程处理器，可以从存储系统、至少一个输入装置、和至少一个输出装置接收数据和指令，并且将数据和指令传输至该存储系统、该至少一个输入装置、和该至少一个输出装置。
这些计算程序(也称作程序、软件、软件应用、或者代码)包括可编程处理器的机器指令，并且可以利用高级过程和/或面向对象的编程语言、和/或汇编/机器语言来实施这些计算程序。如本文使用的，术语“机器可读介质”和“计算机可读介质”指的是用于将机器指令和/或数据提供给可编程处理器的任何计算机程序产品、设备、和/或装置(例如，磁盘、光盘、存储器、可编程逻辑装置(programmable logic device，PLD))，包括，接收作为机器可读信号的机器指令的机器可读介质。术语“机器可读信号”指的是用于将机器指令和/或数据提供给可编程处理器的任何信号。
为了提供与用户的交互，可以在计算机上实施此处描述的系统和技术，该计算机具有：用于向用户显示信息的显示装置(例如，CRT(Cathode Ray Tube，阴极射线管)或者LCD(液晶显示器)监视器)；以及键盘和指向装置(例如，鼠标或者轨迹球)，用户可以通过该键盘和该指向装置来将输入提供给计算机。其它种类的装置还可以用于提供与用户的交互；例如，提供给用户的反馈可以是任何形式的传感反馈(例如，视觉反馈、听觉反馈、或者触觉反馈)；并且可以用任何形式(包括声输入、语音输入或者、触觉输入)来接收来自用户的输入。
可以将此处描述的系统和技术实施在包括后台部件的计算系统(例如，作为数据服务器)、或者包括中间件部件的计算系统(例如，应用服务器)、或者包括前端部件的计算系统(例如，具有图形用户界面或者网络浏览器的用户计算机，用户可以通过该图形用户界面或者该网络浏览器来与此处描述的系统和技术的实施方式交互)、或者包括这种后台部件、中间件部件、或者前端部件的任何组合的计算系统中。可以通过任何形式或者介质的数字数据通信(例如，通信网络)来将系统的部件相互连接。通信网络的示例包括：局域网(Local Area Network，LAN)、广域网(Wide Area Network，WAN)和互联网。
计算机系统可以包括客户端和服务器。客户端和服务器一般远离彼此并且通常通过通信网络进行交互。通过在相应的计算机上运行并且彼此具有客户端-服务器关系的计算机程序来产生客户端和服务器的关系。
根据本申请实施例的技术方案，本申请因为采用利用位置信息和时间信息在时空坐标系构建行为轨迹，以及基于最小编辑距离计算两个行为轨迹相似度的技术手段，所以克服了在二维平面坐标系中构建和分析行为轨迹时，忽略时间因素的技术问题，进而达到能够更加准确的得到目标对象的行为轨迹相似度技术效果。
应该理解，可以使用上面所示的各种形式的流程，重新排序、增加或删除步骤。例如，本发申请中记载的各步骤可以并行地执行也可以顺序地执行也可以不同的次序执行，只要能够实现本申请公开的技术方案所期望的结果，本文在此不进行限制。
上述具体实施方式，并不构成对本申请保护范围的限制。本领域技术人员应该明白的是，根据设计要求和其他因素，可以进行各种修改、组合、子组合和替代。任何在本申请的精神和原则之内所作的修改、等同替换和改进等，均应包含在本申请保护范围之内。
Claims (16)
1.一种轨迹相似度确定方法，其特征在于，包括：
根据目标对象行为数据中的位置信息和时间信息，在时空坐标系中构建第一行为轨迹和第二行为轨迹；
基于所述第一行为轨迹的各轨迹点，计算所述第二行为轨迹转换到所述第一行为轨迹的最小编辑距离；
根据最小编辑距离，确定所述第一行为轨迹与所述第二行为轨迹的相似度。
2.根据权利要求1所述的方法，其特征在于，基于第一行为轨迹的各轨迹点，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离，包括：
在所述第一行为轨迹上确定第一目标轨迹点；
在所述第二行为轨迹上生成第二目标轨迹点，所述第二目标轨迹点与所述第一目标轨迹点的坐标相同；
根据预设编辑距离算法，计算生成所述第二目标轨迹点的第一编辑距离；
利用递归求解算法，计算所述第二目标轨迹点之前的第二行为轨迹转换到所述第一目标轨迹点之前的第一行为轨迹的第二编辑距离；
根据所述第一编辑距离和所述第二编辑距离，计算所述第二行为轨迹转换到所述第一行为轨迹的最小编辑距离。
3.根据权利要求1所述的方法，其特征在于，基于第一行为轨迹的各轨迹点，计算第二行为轨迹转换到第一行为轨迹的最小编辑距离，包括：
在所述第一行为轨迹上确定第三目标轨迹点和第四目标轨迹点；
去除所述第二行为轨迹上的冗余轨迹点，所述冗余轨迹点为时间坐标处于所述第三目标轨迹点与所述第四目标轨迹点的时间坐标之间的轨迹点；
根据预设编辑距离算法，计算去除所述冗余轨迹点的第三编辑距离；
利用递归求解算法，计算所述冗余轨迹点之前的第二行为轨迹转换到所述第三目标轨迹点之前的第一行为轨迹的第四编辑距离；
根据所述第三编辑距离和所述第四编辑距离，计算所述第二行为轨迹转换到所述第一行为轨迹的最小编辑距离。
4.根据权利要求2所述的方法，其特征在于，在所述第二行为轨迹上生成第二目标轨迹点，包括：
将所述第二行为轨迹上的一个轨迹点变更为所述第二目标轨迹点；或，
在所述第二行为轨迹上增加一个所述第二目标轨迹点。
5.根据权利要求4所述的方法，其特征在于，将所述第二行为轨迹上的一个轨迹点变更为所述第二目标轨迹点的预设编辑距离算法为：
其中，L(P1，P2)表示变更轨迹点的预设编辑距离，P1表示所述第二行为轨迹上的一个轨迹点，P2表示所述第二目标轨迹点，x1为P1在X轴的坐标，y1为P1在Y轴的坐标，x2为P2在X轴的坐标，y2为P2在Y轴的坐标。
6.根据权利要求4所述的方法，其特征在于，在所述第二行为轨迹上增加一个所述第二目标轨迹点的预设编辑距离算法为：
其中，AL(Pk)表示增加轨迹点的预设编辑距离，Pk表示增加的所述第二目标轨迹点，Pi表示所述第二行为轨迹上位于所述第二目标轨迹点之前的一个轨迹点，Pj表示所述第二行为轨迹上位于所述第二目标轨迹点之后的一个轨迹点，L(Pi，Pk)表示轨迹点Pi与轨迹点Pk之间的编辑距离，L(Pk，Pj)表示轨迹点Pk与轨迹点Pj之间的编辑距离。
7.根据权利要求3所述的方法，其特征在于，去除所述第二行为轨迹上的冗余轨迹点的预设编辑距离算法为：
其中，DL(Pk)表示去除冗余轨迹点的预设编辑距离，Pk表示所述冗余轨迹点，Pi表示所述第二行为轨迹上位于所述冗余轨迹点之前的一个轨迹点，Pj表示所述第二行为轨迹上位于所述冗余轨迹点之后的一个轨迹点，L(Pi，Pk)表示轨迹点Pi与轨迹点Pk之间的编辑距离，L(Pk，Pj)表示轨迹点Pk与轨迹点Pj之间的编辑距离。
8.根据权利要求1所述的方法，其特征在于，根据目标对象行为数据中的位置信息和时间信息，在时空坐标系中构建第一行为轨迹和第二行为轨迹，包括：
根据各所述位置信息，基于所述时空坐标系的经度坐标轴和纬度坐标轴生成初始坐标点；
根据各所述位置信息对应的时间信息，基于所述时空坐标系的时间坐标轴，按时序对各所述初始坐标点进行排列，形成多个轨迹点；
基于所述多个轨迹点，构建所述第一行为轨迹和所述第二行为轨迹。
9.根据权利要求8所述的方法，其特征在于，根据各所述位置信息，基于所述时空坐标系的经度坐标轴和纬度坐标轴生成初始坐标点之前，还包括：
将各所述位置信息的度量单位统一为经纬度单位；
将各所述时间信息的度量单位进行统一。
10.一种轨迹相似度确定的装置，其特征在于，包括：
构建模块，用于根据目标对象行为数据中的位置信息和时间信息，在时空坐标系中构建第一行为轨迹和第二行为轨迹；
计算模块，用于基于所述第一行为轨迹的各轨迹点，计算所述第二行为轨迹转换到所述第一行为轨迹的最小编辑距离；
确定模块，用于根据最小编辑距离，确定所述第一行为轨迹与所述第二行为轨迹的相似度。
11.根据权利要求10所述的装置，其特征在于，所述计算模块包括：
第一确定子模块，用于在所述第一行为轨迹上确定第一目标轨迹点；
第一生成子模块，用于在所述第二行为轨迹上生成第二目标轨迹点，所述第二目标轨迹点与所述第一目标轨迹点的坐标相同；
第一计算子模块，用于根据预设编辑距离算法，计算生成所述第二目标轨迹点的第一编辑距离；
第二计算子模块，用于利用递归求解算法，计算所述第二目标轨迹点之前的第二行为轨迹转换到所述第一目标轨迹点之前的第一行为轨迹的第二编辑距离；
第三计算子模块，用于根据所述第一编辑距离和所述第二编辑距离，计算所述第二行为轨迹转换到所述第一行为轨迹的最小编辑距离。
12.根据权利要求10所述的装置，其特征在于，所述计算模块包括：
第二确定子模块，用于在所述第一行为轨迹上确定第三目标轨迹点和第四目标轨迹点；
去除子模块，用于去除所述第二行为轨迹上的冗余轨迹点，所述冗余轨迹点为时间坐标处于所述第三目标轨迹点与所述第四目标轨迹点的时间坐标之间的的轨迹点；
第四计算子模块，用于根据预设编辑距离算法，计算去除所述冗余轨迹点的第三编辑距离；
第五计算子模块，用于利用递归求解算法，计算所述冗余轨迹点之前的第二行为轨迹转换到所述第三目标轨迹点之前的第一行为轨迹的第四编辑距离；
第六计算子模块，用于根据所述第三编辑距离和所述第四编辑距离，计算所述第二行为轨迹转换到所述第一行为轨迹的最小编辑距离。
13.根据权利要求11所述的装置，其特征在于，所述第一生成子模块包括：
生成单元，用于将所述第二行为轨迹上的一个轨迹点变更为所述第二目标轨迹点；或，用于在所述第二行为轨迹上增加一个所述第二目标轨迹点。
14.根据权利要求10所述的装置，其特征在于，所述构建模块包括：
第二生成子模块，用于根据各所述位置信息，基于所述时空坐标系的经度坐标轴和纬度坐标轴生成初始坐标点；
形成子模块，用于根据各所述位置信息对应的时间信息，基于所述时空坐标系的时间坐标轴，按时序对各所述初始坐标点进行排列，形成多个轨迹点；
构建子模块，用于基于所述多个轨迹点，构建所述第一行为轨迹和所述第二行为轨迹。
15.一种电子设备，其特征在于，包括：
至少一个处理器；以及
与所述至少一个处理器通信连接的存储器；其中，
所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够执行权利要求1-9中任一项所述的方法。
16.一种存储有计算机指令的非瞬时计算机可读存储介质，其特征在于，所述计算机指令用于使所述计算机执行权利要求1-9中任一项所述的方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910851151.0A CN110555061B (zh) | 2019-09-06 | 2019-09-06 | 轨迹相似度确定方法和装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201910851151.0A CN110555061B (zh) | 2019-09-06 | 2019-09-06 | 轨迹相似度确定方法和装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN110555061A true CN110555061A (zh) | 2019-12-10 |
| CN110555061B CN110555061B (zh) | 2022-04-05 |
Family
ID=68739779
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201910851151.0A Active CN110555061B (zh) | 2019-09-06 | 2019-09-06 | 轨迹相似度确定方法和装置 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN110555061B (zh) |
Cited By (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111190989A (zh) * | 2019-12-31 | 2020-05-22 | 深圳安智杰科技有限公司 | 离散轨迹分析方法、装置、电子设备及可读存储介质 |
| CN111414444A (zh) * | 2020-03-02 | 2020-07-14 | 北京明略软件系统有限公司 | 一种时空轨迹信息的处理方法和装置 |
| CN111797295A (zh) * | 2020-06-19 | 2020-10-20 | 云从科技集团股份有限公司 | 一种多维时空轨迹融合方法、装置、机器可读介质及设备 |
| CN111831178A (zh) * | 2020-06-29 | 2020-10-27 | 中国科学院软件研究所 | 一种基于运动趋势信息的三维环境下辅助目标选择方法及系统 |
| CN111930791A (zh) * | 2020-05-28 | 2020-11-13 | 中南大学 | 一种车辆轨迹的相似度计算方法、系统及存储介质 |
| CN112015956A (zh) * | 2020-09-04 | 2020-12-01 | 杭州海康威视数字技术股份有限公司 | 移动对象的相似性确定方法、装置、设备和存储介质 |
| CN112037245A (zh) * | 2020-07-22 | 2020-12-04 | 杭州海康威视数字技术股份有限公司 | 一种确定追踪目标相似度的方法和系统 |
| CN112561948A (zh) * | 2020-12-22 | 2021-03-26 | 中国联合网络通信集团有限公司 | 基于时空轨迹的伴随轨迹识别方法、设备及存储介质 |
| CN113055821A (zh) * | 2021-03-15 | 2021-06-29 | 北京京东乾石科技有限公司 | 用于发送信息的方法和装置 |
| CN114238792A (zh) * | 2021-12-20 | 2022-03-25 | 阿波罗智联(北京)科技有限公司 | 用于轨迹点数据挖掘的方法及装置、电子设备和介质 |
| CN115476654A (zh) * | 2022-09-05 | 2022-12-16 | 集度科技有限公司 | 用于控制通风装置的扫风控制方法、装置及电子设备 |
| CN115809307A (zh) * | 2022-11-21 | 2023-03-17 | 曙光云计算集团有限公司 | 时空轨迹生成方法、装置、计算机设备和存储介质 |
| WO2023123893A1 (zh) * | 2021-12-27 | 2023-07-06 | 深圳云天励飞技术股份有限公司 | 对象轨迹相似度的获得方法、装置、电子设备及存储介质 |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105243148A (zh) * | 2015-10-25 | 2016-01-13 | 西华大学 | 一种基于签到数据的时空轨迹相似性度量方法及系统 |
| US9593957B2 (en) * | 2010-06-04 | 2017-03-14 | Microsoft Technology Licensing, Llc | Searching similar trajectories by locations |
| CN106776482A (zh) * | 2016-12-01 | 2017-05-31 | 河海大学 | 一种轨迹相似度计算方法 |
| CN106844409A (zh) * | 2016-06-16 | 2017-06-13 | 南京航空航天大学 | 快速连续历史轨迹距离查询技术 |
| CN106959113A (zh) * | 2016-01-08 | 2017-07-18 | 中兴通讯股份有限公司 | 移动终端运动轨迹的匹配方法及装置 |
| CN110162586A (zh) * | 2019-05-24 | 2019-08-23 | 中国科学院地理科学与资源研究所 | 一种适用于移动目标分支轨迹的相似度查询系统及方法 |
-
2019
- 2019-09-06 CN CN201910851151.0A patent/CN110555061B/zh active Active
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9593957B2 (en) * | 2010-06-04 | 2017-03-14 | Microsoft Technology Licensing, Llc | Searching similar trajectories by locations |
| CN105243148A (zh) * | 2015-10-25 | 2016-01-13 | 西华大学 | 一种基于签到数据的时空轨迹相似性度量方法及系统 |
| CN106959113A (zh) * | 2016-01-08 | 2017-07-18 | 中兴通讯股份有限公司 | 移动终端运动轨迹的匹配方法及装置 |
| CN106844409A (zh) * | 2016-06-16 | 2017-06-13 | 南京航空航天大学 | 快速连续历史轨迹距离查询技术 |
| CN106776482A (zh) * | 2016-12-01 | 2017-05-31 | 河海大学 | 一种轨迹相似度计算方法 |
| CN110162586A (zh) * | 2019-05-24 | 2019-08-23 | 中国科学院地理科学与资源研究所 | 一种适用于移动目标分支轨迹的相似度查询系统及方法 |
Non-Patent Citations (2)
| Title |
|---|
| NURULLAH SAMED SAVAŞ等: "Evaluation of different algorithms for measuring the similarities of trajectory datasets", 《IEEE》 * |
| 朱进: "基于运动特征的轨迹相似性度量研究", 《中国博士学位论文全文数据库 基础科学辑》 * |
Cited By (19)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111190989A (zh) * | 2019-12-31 | 2020-05-22 | 深圳安智杰科技有限公司 | 离散轨迹分析方法、装置、电子设备及可读存储介质 |
| CN111190989B (zh) * | 2019-12-31 | 2023-03-14 | 深圳安智杰科技有限公司 | 离散轨迹分析方法、装置、电子设备及可读存储介质 |
| CN111414444A (zh) * | 2020-03-02 | 2020-07-14 | 北京明略软件系统有限公司 | 一种时空轨迹信息的处理方法和装置 |
| CN111930791B (zh) * | 2020-05-28 | 2022-07-15 | 中南大学 | 一种车辆轨迹的相似度计算方法、系统及存储介质 |
| CN111930791A (zh) * | 2020-05-28 | 2020-11-13 | 中南大学 | 一种车辆轨迹的相似度计算方法、系统及存储介质 |
| CN111797295B (zh) * | 2020-06-19 | 2021-04-02 | 云从科技集团股份有限公司 | 一种多维时空轨迹融合方法、装置、机器可读介质及设备 |
| CN111797295A (zh) * | 2020-06-19 | 2020-10-20 | 云从科技集团股份有限公司 | 一种多维时空轨迹融合方法、装置、机器可读介质及设备 |
| CN111831178A (zh) * | 2020-06-29 | 2020-10-27 | 中国科学院软件研究所 | 一种基于运动趋势信息的三维环境下辅助目标选择方法及系统 |
| CN111831178B (zh) * | 2020-06-29 | 2023-01-17 | 中国科学院软件研究所 | 一种基于运动趋势信息的三维环境下辅助目标选择方法及系统 |
| CN112037245B (zh) * | 2020-07-22 | 2023-09-01 | 杭州海康威视数字技术股份有限公司 | 一种确定追踪目标相似度的方法和系统 |
| CN112037245A (zh) * | 2020-07-22 | 2020-12-04 | 杭州海康威视数字技术股份有限公司 | 一种确定追踪目标相似度的方法和系统 |
| CN112015956A (zh) * | 2020-09-04 | 2020-12-01 | 杭州海康威视数字技术股份有限公司 | 移动对象的相似性确定方法、装置、设备和存储介质 |
| CN112561948A (zh) * | 2020-12-22 | 2021-03-26 | 中国联合网络通信集团有限公司 | 基于时空轨迹的伴随轨迹识别方法、设备及存储介质 |
| CN112561948B (zh) * | 2020-12-22 | 2023-11-21 | 中国联合网络通信集团有限公司 | 基于时空轨迹的伴随轨迹识别方法、设备及存储介质 |
| CN113055821A (zh) * | 2021-03-15 | 2021-06-29 | 北京京东乾石科技有限公司 | 用于发送信息的方法和装置 |
| CN114238792A (zh) * | 2021-12-20 | 2022-03-25 | 阿波罗智联(北京)科技有限公司 | 用于轨迹点数据挖掘的方法及装置、电子设备和介质 |
| WO2023123893A1 (zh) * | 2021-12-27 | 2023-07-06 | 深圳云天励飞技术股份有限公司 | 对象轨迹相似度的获得方法、装置、电子设备及存储介质 |
| CN115476654A (zh) * | 2022-09-05 | 2022-12-16 | 集度科技有限公司 | 用于控制通风装置的扫风控制方法、装置及电子设备 |
| CN115809307A (zh) * | 2022-11-21 | 2023-03-17 | 曙光云计算集团有限公司 | 时空轨迹生成方法、装置、计算机设备和存储介质 |
Also Published As
| Publication number | Publication date |
|---|---|
| CN110555061B (zh) | 2022-04-05 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN110555061B (zh) | 轨迹相似度确定方法和装置 | |
| CN110595494B (zh) | 地图误差确定方法和装置 | |
| JP7258066B2 (ja) | 測位方法、測位装置及び電子機器 | |
| CN111462029B (zh) | 视觉点云与高精地图融合方法、装置和电子设备 | |
| JP7242738B2 (ja) | 点群を更新するための方法、点群を更新するための装置、電子機器、非一時的コンピュータ可読記憶媒体及びコンピュータプログラム | |
| CN110617825B (zh) | 一种车辆定位方法、装置、电子设备和介质 | |
| EP3896624A2 (en) | Speed planning method and apparatus for self-driving, device, medium and vehicle | |
| JP7228623B2 (ja) | 障害物検出方法、装置、設備、記憶媒体、及びプログラム | |
| CN111216738B (zh) | 自动驾驶中车辆的控制方法、装置、电子设备及车辆 | |
| KR102568948B1 (ko) | 장애물 속도를 결정하는 방법, 장치, 전자 기기, 저장 매체 및 프로그램 | |
| JP7194215B2 (ja) | キーポイントの特定方法及び装置、機器、記憶媒体 | |
| CN111598246B (zh) | 量子吉布斯态生成方法、装置及电子设备 | |
| CN111597287B (zh) | 地图生成方法、装置及设备 | |
| CN111625612B (zh) | 高精地图的纠偏方法和装置、电子设备和存储介质 | |
| CN111737636B (zh) | 路径曲线的生成方法、装置、计算机设备和存储介质 | |
| US20210239491A1 (en) | Method and apparatus for generating information | |
| JP2021128779A (ja) | データ拡張の方法及び装置、機器、記憶媒体 | |
| CN111158666A (zh) | 实体归一化处理方法、装置、设备及存储介质 | |
| CN111597987A (zh) | 用于生成信息的方法、装置、设备和存储介质 | |
| CN111966767B (zh) | 轨迹热力图生成方法、装置、电子设备和存储介质 | |
| CN111967481A (zh) | 视觉定位方法、装置、电子设备及存储介质 | |
| CN113012555B (zh) | 地图显示方法、装置、电子设备和存储介质 | |
| JP2021174531A (ja) | 目標追跡方法及び装置、電子機器、記憶媒体並びにコンピュータプログラム | |
| CN111814651A (zh) | 车道线的生成方法、装置和设备 | |
| CN111488972A (zh) | 数据迁移方法、装置、电子设备和存储介质 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |