一种用户移动轨迹中敏感轨迹模式的净化方法

摘要

本发明公开了一种用户移动轨迹中敏感轨迹模式的净化方法。该方法依据用户移动轨迹数据分布于道路网络的特性，定义基于道路的网络有向图，在网络有向图中预设敏感点及敏感轨迹模式集，采用全局与局部匹配相结合的方法对获取的用户移动轨迹进行净化，得到不包含敏感轨迹模式的用户移动轨迹。该方法可以实现批量敏感轨迹模式的快速隐藏，实现处理后的数据相对于原始数据具有较小失真度。

主权项

一种用户移动轨迹中敏感轨迹模式的净化方法，其特征在于，具体包括以下步骤：步骤1、构建道路网络有向图：以道路交叉点作为道路网络有向图的顶点，以道路上的相邻顶点的连线作为道路网络有向图的边；步骤2、将道路网络有向图中若干个顶点预设为敏感点，根据敏感点来确定敏感轨迹模式集PS＝{P₁,P₂,...,P_M}，其中，为敏感轨迹模式，i＝1,2,3...,M，M，n均为正整数,v₁,v₂,...,v_n均为道路网络有向图的顶点，且其中至少有一个敏感点；a₁,a₂,...,a_n‑1为相邻两个顶点之间的时间间隔；步骤3、记录用户移动轨迹点有序列表，将所有用户移动轨迹点有序列表中不属于道路网络有向图中顶点的轨迹点删除，得到用户移动顶点有序列表TV_j＝{<p₁,t₁>,<p₂,t₂>,...,<p_N,t_N>},t₁<t₂<...<t_N，其中，p_b＝(x_b,y_b),b＝1,2,3,...,N，N为正整数，j为正整数；顶点p_b表示用户在t_b时刻所处的空间位置，x_b,y_b分别表示顶点p_b的横纵坐标值；其中，每个用户移动顶点有序列表对应一条用户移动顶点轨迹${\mathrm{PV}}_j=p_1\stackrel{t_2-t_1}{\to }{p}_2\stackrel{t_3-t_2}{\to }{p}_3...\stackrel{t_N-t_{N-1}}{\to }{p}_N;$步骤4、设定匹配时间容限τ，将每个用户移动顶点有序列表对应的用户移动顶点轨迹分别与敏感轨迹模式集进行匹配运算，得到每个用户移动顶点有序列表的全局匹配集其中PV_j是TV_j所对应的用户移动顶点轨迹，TV_j∈TVS，TVS为用户移动顶点有序列表集合；步骤5、以全局匹配集不为空集为条件，确定需要净化的用户移动顶点有序列表；步骤6、对每个需要净化的用户移动顶点有序列表进行净化，得到不包含敏感轨迹模式的所有用户移动顶点有序列表，具体净化过程为：步骤6‑1、将需要净化的用户移动顶点有序列表中的顶点与该有序列表的全局匹配集进行匹配运算，得到该用户移动顶点有序列表中每个顶点对应的局部匹配集；步骤6‑2、删除最大局部匹配集对应的顶点，得到新的用户移动顶点有序列表后执行步骤6‑3；当最大局部匹配集对应的顶点为两个或两个以上时，则选择一个顶点删除；步骤6‑3、将新的用户移动顶点有序列表对应的用户移动顶点轨迹与敏感轨迹模式集进行匹配，如果得到的全局匹配集为空集，则用户移动顶点有序列表净化完成，否则，重复步骤6‑1至步骤6‑3。