基于信令轨迹查目标用户的方法、系统和计算机可读介质与流程

1.本技术涉及数据分析技术，更具体而言，涉及基于信令轨迹查目标用户的方法、系统和计算机可读介质。

背景技术：

2.通信运营商存储有大量移动通信信令数据。信令不同于用户的有用信号(其直接通过移动通信网络由发信者传输到收信者)，需要在移动通信网络的移动台、、控制中心和移动交换中心之间传输，并接受分析、处理而形成一系列操作和控制。信令数据中包含有能够体现用户移动路径的轨迹数据(又称为“信令轨迹”)。在某些情况下，相关机构可以依赖该数据查、追踪具有特定轨迹的用户。该技术尤其对于追缉涉嫌犯罪人员具有重要意义。然而，现有技术的准确率较低且耗时较长，极大阻碍了该技术的推广应用。

技术实现要素：

3.本发明提供了一种基于信令轨迹查目标用户的方法。该方法包括：召回符合目标轨迹点序列t(p1,p2,...,pn)的候选用户，进而得到候选轨迹点序列ts(ps1,ps2,...,psm)；将候选轨迹点序列与目标轨迹点序列进行比对，生成距离矩阵d；基于距离矩阵，利用动态规划计算轨迹间的最短路径d；和根据最短路径，查目标用户。
4.在一个实施方案中，该方法还包括对候选用户的轨迹进行轨迹预处理，进而得到候选轨迹点序列。
5.在一个实施方案中，该方法还包括将最短路径归一化为轨迹相似度。
6.在一个实施方案中，召回包括针对每个目标轨迹点pi，匹配在与目标轨迹点时间ti对应的时间区间(t_starti,t_endi)内轨迹与目标轨迹点位置重合的用户作为候选用户。
7.在一个实施方案中，当ti已知时，(t_starti,t_endi)＝(t
i-x,ti+x)，当ti未知时，t_starti＝min{t_start,t1,...,t
i-1
}且t_endi＝min{t
i+1
,...,tn,t_end}，其中(t_start,t_end)为目标轨迹点序列的时间区间。
8.在一个实施方案中，距离矩阵的大小为n
×
(m-1)，其中的每个元素dij为目标轨迹点pi到候选轨迹点序列中的线段psjps
j+1
的最短距离。
9.在一个实施方案中，如果目标轨迹点pi对应的时间范围(t_starti,t_endi)与候选轨迹点序列中的线段psjps
j+1
对应的时间范围(tsj,ts
j+1
)无交集，则距离矩阵中的每个元素dij为正无穷，其中tsj为候选轨迹点psj对应的时间。
10.在一个实施方案中，该方法还包括基于最短路径矩阵sd，计算最短路径，其中最短路径矩阵的大小为n
×
(m-1)，其中的每个元素
11.在一个实施方案中，最短路径d＝sd
n(m-1)
，并且目标轨迹t到候选轨迹ts的owd距离为owd(t,ts)＝d/n。
12.本发明还提供了一种基于信令轨迹查目标用户的系统。该系统包括：召回装置，其用于召回符合目标轨迹点序列t(p1,p2,...,pn)的候选用户，进而得到候选轨迹点序列ts(ps1,ps2,...,psm)；比对装置，其将候选轨迹点序列与目标轨迹点序列进行比对，生成距离矩阵d；计算装置，其基于距离矩阵，利用动态规划计算轨迹间的最短路径d；和查装置，其根据最短路径，查目标用户。
13.本发明还提供了一种计算机可读介质，其上存储有计算机程序，该计算机程序被处理器执行时实现上面叙述的方法。
14.本发明的技术方案可以不依赖于轨迹点的具体时间点，扩大了轨迹检索的应用范围，轨迹检索召回率达到85％左右；并且基于全新的算法，准确率能够达到90％以上。
附图说明
15.图1是根据本发明的实施例的基于信令轨迹查目标用户的方法的示意性流程图。
16.图2是示出传统owd算法中涉及的距离的示意图。
具体实施方式
17.现在将参照若干示例性实施例来说明本发明的内容。应当理解，说明这些实施例仅是为了使得本领域普通技术人员能够更好地理解并且因此实现本发明的内容，而不是暗示对本发明的范围进行任何限制。
18.如本文中所使用的，术语“包括”及其变体应当解读为意味着“包括但不限于”的开放式术语。术语“基于”应当解读为“至少部分地基于”。术语“一个实施例”和“一种实施例”应当解读为“至少一个实施例”。术语“另一个实施例”应当解读为“至少一个其他实施例”。
19.本发明的技术方案可以用于各种用途和场景，优选地用于刑事追缉场景。在本发明的实施例中，目标用户可以是步行或使用交通工具移动的。下面参照图1分步骤详细说明本发明的基于信令轨迹查目标用户的方法。在本发明的实施例中，下列步骤中的一项或多项可以从该方法中省略，并且每个步骤不一定按如下顺序执行。
20.召回符合目标轨迹点序列的候选用户
21.在本发明的实施例中，召回的目的在于查到行程/移动线路初步符合特定轨迹的一个或多个用户。在本发明的实施例中，该特定轨迹点是人为设置的。在本发明的实施例中，该特定轨迹可以表示为由一个或多个轨迹点构成的序列，称为目标轨迹点序列(或轨迹点序列)t(p1,p2,...,pn)，其中n为轨迹点的个数，其中轨迹点序列中的轨迹点按时间顺序从早到晚排列。在本发明的实施例中，待进行查的时间范围可以表示为(t_start,t_end)。需要指出的是，t_start和t_end并不一定分别等于轨迹点序列中最早和最晚轨迹点对应的时间，这是因为轨迹点通常是间断而非连续的，而且存在个别轨迹点或轨迹点的时间未被记录的情形。在本发明的实施例中，任意轨迹点pi可以由(loni,lati,ti)表示，其中loni表示经度，lati表示纬度,ti表示该轨迹点的时间，若该轨迹点的时间未知,则ti为在本发明的其他实施例中，还可以使用不同于经纬度的其他方式表示地理位置。
22.由于移动通信用户的数量十分庞大，将上述轨迹序列与每个用户的轨迹进行一一比对是不现实，因此需要对候选用户进行召回，从而大幅提高后续比对、匹配的效率。另外，
如上面讨论的，轨迹点通常是间断的，而且可能存在未记录的情形，为了提高召回率，避免遗漏，本发明人提出可以对轨迹点时间进行转换。在本发明的优选实施例中，可以将ti转换为时间区间(t_starti,t_endi)。在本发明的某些进行时间转换的实施例中，若ti是已知的，则(t_starti,t_endi)＝(t
i-x,ti+x)，其中x可以是根据具体情况自行调节的任意时间，例如10分钟。在本发明的某些进行时间转换的实施例中，若ti是未知的，则t_starti＝min{t_start,t1,...,t
i-1
}且t_endi＝min{t
i+1
,...,tn,t_end}，min{}函数对括号内的时间进行比较，并取其中的最早者。在本发明的实施例中，还可以通过其他方法定义时间区间。
23.在本发明的实施例中，针对每个轨迹点pi，对全量信令数据进行查，匹配得到候选用户集合si。在本发明的实施例中，“全量信令数据”指的是一个或多个通信运营商保存的全部信令数据。在本发明的实施例中，匹配的用户指的是在(t_starti,t_endi)的时间区间内，与轨迹点pi位置重合的用户。在本发明的优选实施例中，可以将轨迹点pi对应的(loni,lati)转换为位置编码后再进行匹配。在本发明的更优选实施例中，使用geohash或s2索引进行位置编码转换。在本发明的实施例中，针对所有轨迹点，可以得到候选用户集合序列{s1,s2,...,sn}。在本发明的实施例中，可以对该集合序列中用户出现的次数进行统计，然后选取出现次数最多的一部分用户(例如，前20,000人)作为候选用户进行后续过程。
24.对候选用户进行轨迹预处理
25.在本发明的实施例中，可以对候选用户进行轨迹预处理，其目的在于去除或修正轨迹序列中不合理存在的轨迹点。在本发明的实施例中，针对任意候选用户，其在(t_start,t_end)区间内的轨迹为ts。在本发明的实施例中，对ts进行轨迹预处理包括进行轨迹去重、消除乒乓切换、去飘移点等操作。在本发明的实施例中，一些代表性轨迹预处理示例如下：
26.(1)轨迹去重：对于特定短时间(例如，1分钟)内重复的轨迹点，只保留最早的轨迹点，去除其他轨迹点。
27.(2)消除乒乓切换：“乒乓切换”指的是移动通信设备(例如，手机)在两个间来回切换。若当前轨迹点pi的位置与下一个轨迹点p
i+1
的位置不同，但是却与下两个轨迹点p
i+2
的位置相同，并且时间间隔在特定短时间(例如，5分钟)内，则满足乒乓切换的要求。在上述情况下，仅保留pi轨迹点，去除p
i+1
和p
i+2
两个轨迹点。
28.(3)去飘移点：若当前轨迹点与前一个轨迹点相比，速度大于阈值(例如可以取200km/h)，则去除该轨迹点。
29.在本发明的实施例中，不断重复上述操作，直到所有轨迹点均符合上述要求，则完成轨迹预处理。在本发明的实施例中，在轨迹预处理后，针对每个候选用户的轨迹点序列，得到预处理后的轨迹点序列(或候选轨迹点序列)ts(ps1,ps2,...,psm)，其中m为轨迹点的个数，psi也可以由(loni,lati,ti)组成，此处的ti是明确的且为真实/实际时间。
30.将候选轨迹点序列与目标轨迹点序列进行比对，生成距离矩阵
31.本领域中通常使用owd算法评估轨迹相似度。该算法在2008年提出，是一种基于形状的距离算法，而不考虑时间约束。根据其定义，轨迹t1与t2的owd距离计算如下：
32.33.其中t1为(p1,p2,...,pn),pi为(loni,lati)，t2为(ps1,ps2,...,psn),psj为(lonj,latj)；|t1|表示轨迹t1的长度n(即轨迹点的个数)，而(p,t2)表示轨迹点p到轨迹t2的距离，即轨迹点p至t2中所有线段(psi，ps
i+1
)的最短距离(如图2所示)。
34.然而，传统owd算法只能计算无时间约束的两条轨迹的相似度，无法解决“时间约束”条件下的相似度比对。在实际轨迹检索过程中(例如本发明上面描述的那些过程中)，候选轨迹点的时间是明确的，目标轨迹点的时间可能是不明确或缺失的，待比对的轨迹点序列t和候选轨迹序列ts具有对应于轨迹点的时间要素，因此需要对传统owd算法进行改造，采用距离矩阵的方法计算出t中的每个轨迹点对应到ts中各线段的距离。
35.在本发明的实施例中，发明人定义了一个距离矩阵d，该矩阵的大小为n
×
(m-1)，其中n和m分别对应于轨迹点序列t和候选轨迹序列ts中轨迹点的个数，而该矩阵中的每个元素dij为轨迹t中的任意轨迹点pi到轨迹ts中的任意线段psjps
j+1
的最短距离。在本发明的实施例中，最短距离指的是点到线段的垂线距离；当不存在该垂线时，指的是点到最近的线段端点的距离。在本发明的实施例中，若pi对应的时间范围(t_starti,t_endi)与线段psjps
j+1
对应的时间范围(tsj,ts
j+1
)有交集，则dij等于点pi到线段psjps
j+1
的距离；否则dij记为正无穷。
36.基于距离矩阵，利用动态规划计算轨迹间的最短路径
37.在本发明的实施例中，根据上面计算得到的距离矩阵dij，利用动态规划求出最短路径d，并且将该最短路径d作为轨迹t到ts的距离。具体作法如下：
38.定义最短路径矩阵sd，矩阵大小为n
×
(m-1)，其中n和m分别对应于轨迹点序列t和候选轨迹序列ts中轨迹点的个数，而sd
ij
表示t的子序列(p1,p2,...,pi)到ts的子序列(ps1,ps2,...,ps
j+1
)的最短路径。子序列对应的是轨迹序列的子集，动态规划是不断由子序列进行延展，直至完整的轨迹，即可求解出轨迹之间的最短路径。为此，发明人作出如下定义：
[0039][0040]
利用动态规划算法，i从1至n循环，j从1至m-1循环，可依次计算出矩阵sd中所有项的值，进而可以得到d＝sd
n(m-1)
。最后，轨迹t到ts的owd距离定义为owd(t,ts)＝d/|t|，|t|表示轨迹t的长度n(即轨迹点的个数)。在本发明的实施例中，可以根据上述最短路径查可疑目标，例如将一定距离以内的用户认定为目标用户。
[0041]
将最短路径转换为轨迹相似度，进而查符合条件的可疑目标
[0042]
在本发明的实施例中，还可以将上面得到的owd距离进行归一化，得到轨迹的相似度s＝max(1-owd(t,ts)/dist,0)，其中dist为归一化距离，一般取1000。在本发明的实施例中，可以按相似度由大到小排序，得到排名前n(例如可以取200)的用户供相关部门进一步分析。在本发明的实施例中，还可以在其他算法的基础上应用上述改进，例如可以将owd算法替换为dtw(动态时间归整，dynamic time wraping)算法，并且在dtw算法的基础上应用距离矩阵和动态规划计算。
[0043]
本发明各实施例的方法和装置可以实现为纯粹的软件模块(例如用java语言来编写的软件程序)，也可以根据需要实现为纯粹的硬件模块(例如专用asic芯片或fpga芯片)，还可以实现为结合了软件和硬件的模块(例如存储有固定代码的固件系统)。
[0044]
本发明的另一个方面是一种计算机可读介质，其上存储有计算机可读指令，所述指令被执行时可实施本发明各实施例的方法。
[0045]
本领域普通技术人员可以意识到，以上所述仅为本发明的示例性实施例，并不用于限制本发明。本发明还可以包含各种修改和变化。任何在本发明的精神和范围内作的修改和变化均应包含在本发明的保护范围内。

技术特征：

1.一种基于信令轨迹查目标用户的方法，包括：召回符合目标轨迹点序列t(p1,p2,...,p
n
)的候选用户，进而得到候选轨迹点序列ts(ps1,ps2,...,ps
m
)；将所述候选轨迹点序列与所述目标轨迹点序列进行比对，生成距离矩阵d；基于所述距离矩阵，利用动态规划计算轨迹间的最短路径d；和根据所述最短路径，查所述目标用户。2.根据权利要求1所述的方法，还包括：对所述候选用户的轨迹进行轨迹预处理，进而得到所述候选轨迹点序列。3.根据权利要求1所述的方法，还包括：将所述最短路径归一化为轨迹相似度。4.根据权利要求1所述的方法，所述召回包括：针对每个目标轨迹点p
i
，匹配在与目标轨迹点时间t
i
对应的时间区间(t_start
i
,t_end
i
)内轨迹与所述目标轨迹点位置重合的用户作为所述候选用户。5.根据权利要求4所述的方法，其中当t
i
已知时，(t_start
i
,t_end
i
)＝(t
i-x,t
i
+x)，当t
i
未知时，t_start
i
＝min{t_start,t1,...,t
i-1
}且t_end
i
＝min{t
i+1
,...,t
n
,t_end}，其中(t_start,t_end)为所述目标轨迹点序列的时间区间。6.根据权利要求1所述的方法，其中所述距离矩阵的大小为n
×
(m-1)，其中的每个元素dij为目标轨迹点p
i
到所述候选轨迹点序列中的线段ps
j
ps
j+1
的最短距离。7.根据权利要求4所述的方法，其中如果目标轨迹点p
i
对应的时间范围(t_start
i
,t_end
i
)与所述候选轨迹点序列中的线段ps
j
ps
j+1
对应的时间范围(ts
j
,ts
j+1
)无交集，则所述距离矩阵中的每个元素dij为正无穷，其中ts
j
为候选轨迹点ps
j
对应的时间。8.根据权利要求6所述的方法，还包括：基于最短路径矩阵sd，计算所述最短路径，其中所述最短路径矩阵的大小为n
×
(m-1)，其中的每个元素9.根据权利要求8所述的方法，其中所述最短路径d＝sd
n(m-1)
，并且目标轨迹t到候选轨迹ts的owd距离为owd(t,t
s
)＝d/n。10.一种基于信令轨迹查目标用户的系统，包括：召回装置，其用于召回符合目标轨迹点序列t(p1,p2,...,p
n
)的候选用户，进而得到候选轨迹点序列ts(ps1,ps2,...,ps
m
)；比对装置，其将所述候选轨迹点序列与所述目标轨迹点序列进行比对，生成距离矩阵d；计算装置，其基于所述距离矩阵，利用动态规划计算轨迹间的最短路径d；和查装置，其根据所述最短路径，查所述目标用户。11.一种计算机可读介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现根据权利要求1-9中任一项所述的方法。

技术总结

本申请涉及基于信令轨迹查目标用户的法、系统和计算机可读介质。该方法包括：召回符合目标轨迹点序列T(p1,p2,...,p

技术研发人员：

黄卫航 甘云锋 江敏 高雁冰

受保护的技术使用者：

杭州数澜科技有限公司

技术研发日：

2022.09.05

技术公布日：

2022/12/8