根据疑犯位置跟踪数据预测疑犯未来位置，对案件嫌疑人排查以及“犯罪黑数”^[1]探测等具有重要的应用价值。在犯罪地理画像研究中，学者们基于平均作案距离^[2]、用地类型^[3]、路网结构^[4]、动力学模型^[5]、回归模型^[6]等进行相关犯罪个体的位置预测。然而，这些研究未能顾及位置数据稀疏性对预测准确性的影响^[7]。普通用户的位置预测研究通过结合社交关系数据^[8]、交通数据^[9]或多源移动数据^[10]来缓解单个用户数据稀疏性问题，但由于疑犯的防备性，他们的社交数据量极少且缺少地理标识；而已有研究中涉及的多源数据与疑犯个体移动偏好的相关性小，难以提供他们有效的位置分布先验信息。为应对以上挑战，本文提出了融合时空语义的位置时空预测(spatio-temporal semantics location prediction，SSLP)模型。该模型首先使用具有入室盗窃案底的疑犯位置数据，提取与目标疑犯具有类似社会习性的疑犯群体，将其轨迹集作为目标疑犯的位置数据源；其次，估算疑犯在轨迹点周边位置（未记录位置）与其他位置间的转移频次及其在各位置上的时态分布概率；最后，采用贝叶斯方法实现疑犯的位置时空预测。

1 位置时空转移概率计算方法 1.1 相似疑犯提取

首先，基于空间邻近性对轨迹点进行聚类；然后，通过比较各时段内疑犯在不同聚类簇的停留情况获得疑犯间的时空相似度，进而获得前k个（top-k）与目标疑犯移动模式最相似的其他疑犯。

1.1.1 轨迹点空间聚类

定义1  空间语义向量：区域r的空间语义向量表示为：s_r=[s_r1 s_r2s_rk]，其中，s_ri为区域r的第i个社会环境特征。社会环境特征类型包括月犯罪率、人口数、房屋密度、各类职业的数量、道路密度和各类兴趣点（point of interest，POI）的数量等。

基于余弦距离公式，s_i和s_j的空间语义距离可表示为：

${\rho _{ij}} = \cos \left( {{\mathit{\boldsymbol{s}}_i}, {\mathit{\boldsymbol{s}}_j}} \right) $

(1)

据此，两轨迹点i和j距离量度ω_ij可用空间物理距离与空间语义距离统一表示为：

${\omega _{ij}} = \left\{ {\begin{array}{*{20}{l}} {{d_{ij}} \times \left( {1 - {\rho _{ij}}} \right), {d_{ij}} \le \delta }\\ {\infty , {d_{ij}} > \delta } \end{array}} \right. $

(2)

式中，d_ij为两轨迹点间的空间距离；δ为阈值。以ω_ij作为两点间的距离，基于密度聚类方法可得到轨迹点聚类簇集合S。

1.1.2 疑犯相似性计算

通过各语义时间内疑犯在各轨迹点聚类簇的停留情况来表达疑犯相似性，具体计算步骤如下。

1) 依据社会作息规律，划分3类语义时间：(1)日时段（time of day，TOD），TOD={（0~6）, （6~12）, （12~18）, （18~24）}，依次代表一天中的0~6点(凌晨)、6~12点(上午)、12~18点(下午)以及18~24点(晚上)。(2)周时段（day of week，DOW），DOW={1…7}，代表星期一至星期日。(3)休息日（rest of day，ROD），ROD={0, 1}，0代表节假日，1代表工作日。

2) 基于TF-IDF方法^[11]，获得疑犯u在语义时段t对聚类簇s的访问强度q_t,u,s：

${q_{t, u, s}} = \frac{{{b_{t, u, s}}}}{{{b_{u, {\rm{s}}}}}} \times {\rm{lg}}\frac{{\left| U \right|}}{{{I_t}\left\{ s \right\}}} $

(3)

式中，b_u,s为疑犯u访问聚类簇s的总次数；b_t,u,s为疑犯u在语义时间t访问s的次数；I_t{s}表示在语义时间t访问过聚类簇s的疑犯数量；|U|为疑犯总数量。该方法能体现聚类簇对疑犯的重要程度。

3) 疑犯u访问聚类簇s的时态模式：

$\begin{array}{l} {z_{s, u}} \sim {\rm{multi}}\left( {{z_{1, u, s}}, {z_{2, u, s}} \ldots {z_{\left| T \right|, u, s}}} \right)\\ \;\;\;\;{z_{t, u, s}} = {q_{i, u, s}} \times {\left( {\sum\limits_{j = 1}^{\left| T \right|} {{q_{j, u, s}}} } \right)^{ - 1}} \end{array} $

(4)

式中，multi(·)为多项式分布；|T|为所有语义时段的数量。

4) 疑犯u和v在聚类簇s上的访问模式差异度:

$\begin{array}{l} J\left( {{z_{s, u}}, {z_{s, v}}} \right) = K({z_{s, u}}||\frac{{{z_{s, u}} + {z_{s, v}}}}{2}) + \\ K({z_{s, v}}||\frac{{{z_{s, u}} + {z_{s, v}}}}{2}) \end{array} $

(5)

式中，J(·)为Jensen-Shannon散度计算公式；K(·)为相对熵计算公式。

5) 结合两疑犯u和v在所有聚类簇上的访问模式差异度，获取疑犯间的相似度：

$\Delta {Q_{u, v}} = {[J({z_{s, u}}, {z_{s, v}})]^{ - 1}} $

(6)

式中, |S|为轨迹点聚类簇的数量。

依据式（6）可得到与目标疑犯行踪最相似的前k个疑犯。他们的轨迹数据将作为目标疑犯的数据源。

1.2 位置转移频次估算 1.2.1 位置转移频次估算

基于核密度平滑方法，利用空间距离和空间语义相似度估算未记录位置的转移模式。

定义2  轨迹位置：原始数据集中各轨迹点所在的基本区域单元。

定义3  外围位置：轨迹位置周围未被记录的基本区域单元。

定义4  密度吸引集及密度吸引子：设p_i、p_x为基本区域单元，对于$\exists {p_i} \in D$，存在d_ix≤ω，即区域i和x间的空间距离小于阈值ω，则称D为p_x的密度吸引集，p_i为p_x的密度吸引子。

1.2.2 轨迹位置至外围位置的转移频次

设p₀为轨迹位置，p_x为外围位置，求p₀至p_x的转移频次。已知D={p₁…p_i…p_N}为p_x的密度吸引集，p₀向D中各轨迹位置转移的频次为{c₁⁰…c_i⁰…c_N⁰}。在仅考虑空间距离时，p₀向p_x转移的物理频次$\dot c_x^0$为：

$\dot c_x^0 = \frac{1}{{{h_d}N}}\sum\limits_{i = 1}^N {c_i^0 \times {K_{{\rm{Guass}}}}\left( {{d_…{xi}}} \right)} $

(7)

式中，N为密度吸引子的总数；K_Guas(·)为高斯核函数；d_xi为p_x和p₀的空间距离；h_f为根据物理距离估计位置转移频次时核密度函数的带宽。

仅考虑位置语义相似度时，p₀与p_x的语义转移频次$\ddot c_x^0$为：

$\ddot c_x^0 = \frac{1}{{{h_s}N}}\sum\limits_{i = 1}^N {c_i^0 \times {K_{{\rm{Guass}}}}\left( {1 - {\rho _{0x}}} \right)} $

(8)

式中，ρ_0x为p₀与p_x间的空间语义距离；h_s为根据语义距离估计位置转移频次时核密度函数的带宽。

对式（7)、式（8）求均值，即可估算出p₀向p_x转移的频次为：

$c_x^0 = \frac{{\dot c_x^0 + \ddot c_x^0}}{2} $

(9)

1.2.3 外围位置至轨迹位置的转移频次

设p₀为轨迹位置，p_x为外围位置，求p_x至p₀的转移频次。已知p_x的密度吸引集D中各轨迹位置p₁…p_i…p_N至轨迹位置p₀的转移频次，则利用式(7)和式(8)，可分别计算出p_x向p₀转移的物理频次$\dot c_0^x$和语义频次和$\ddot c_0^x$。结合这两者，可获得p_x向p₀的转移频次$c_0^x$为：

$c_0^x = \frac{{\dot c_0^x + \ddot c_0^x}}{2} $

(10)

1.2.4 外围位置至外围位置的转移频次

外围位置p_x至外围位置p_y的转移频次从两方面获取：(1)将p_y看作轨迹位置，利用式（9）计算p_x向p_y的转移频次c_xy；(2)将p_x看作轨迹位置，利用式（10）计算p_x与p_y之间的转移频次c_yx。则p_x与p_y的转移频次为两者的均值:

$c_y^x = \frac{{{c_{xy}} + {c_{yx}}}}{2} $

(11)

至此，可得到包括轨迹位置和外围位置间的转移频次。

1.2.5 Markov位置转移模式

位置i向j的转移概率p_ij为i到达j的频次c_ij除以i到达其他所有位置频次之和，即：

${p_{ij}} = {c_{ij}} \times {\left( {\sum\limits_{k = 1}^{\left| G \right|} {{c_{ik}}} } \right)^{ - 1}} $

(12)

式中，|G|为所有位置的数量。

1.3 外围位置的时态分布概率估算

利用轨迹位置的时态分布来估算疑犯在外围位置上的时态访问概率。首先，获取疑犯在各轨迹位置的时态分布：

$\begin{array}{l} P\left( {t|r} \right) \sim {\rm{multi}}\left( {{z_{1, u, r}}, {z_{2, u, r}} \ldots {z_{\left| T \right|, u, r}}} \right), \\ \;\;\;\;{z_{i, u, r}} = {q_{i, u, r}} \times {\left( {\sum\limits_{j = 1}^{\left| T \right|} {{q_{j, u, r}}} } \right)^{ - 1}} \end{array} $

(13)

式中，u为目标疑犯；r为目标位置；z_{i, u, r}为目标疑犯u在时间i出现在位置r的概率值。

利用核密度估算方法，基于外围位置$\tilde r$的密度吸引集D（由轨迹位置构成），获取疑犯在$\tilde r$上的时态分布：

$\begin{array}{l} P\left( {t|\tilde r} \right) \sim {\rm{multi}}\left( {{z_{1, u, \tilde r}}, {z_{2, u, \tilde r}} \ldots {z_{\left| T \right|, u, \tilde r}}} \right)\\ {z_{t, u, \tilde r}} = \frac{1}{{{h_d}\left| D \right|}}\sum\limits_{i = 1}^{\left| D \right|} {{z_{t, u, {r_i}}} \times {K_{G{\rm{uass}}}}\left( {{d_{\tilde r{r_i}}}} \right)} \end{array} $

(14)

式中，${d_{\tilde r{r_i}}}$为外围位置$\tilde r$与轨迹位置r_i的空间距离；|D|为密度吸引子的数量。

1.4 贝叶斯位置时空预测模型

给定目标疑犯的历史位置序列T^p={n₁=r_k+1, n₂=r_k+2…n_h=r_k+h}以及待预测的语义时间，则区域x成为疑犯下一驻留位置的概率表示为：

$\begin{array}{l} {P_x} = P({n_{h + 1}} = {r_x}|t_{h + 1}^w = {t_w}, t_{h + 1}^d = {t_d}, \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{n_h} = {r_{k + h}}) \end{array} $

(15)

式中, r_x为待预测的位置；t_h+1^w=t_w为以周天（DOW）表示的待预测时间；t_h+1^d=t_d为以小时语义时段（TOD）表示的待预测时间。

设疑犯位置间的转移概率与其在各语义时段上的位置分布相互独立，采用贝叶斯方法对式（15）展开得到：

${P_x} \propto P\left( {{t_w}|{r_{k + h}}} \right)P\left( {{t_d}|{r_{k + h}}} \right){p_{\left( {k + h} \right)x}} $

(16)

基于式（13）和式（14）可得到P(t_w|r_k+h)与P(t_d|r_k+h)，基于式（12）可获得p_(k+h)x。

2 疑犯位置时空预测实验 2.1 数据说明

1）全局空间的格网划分。采用100×100的格网覆盖W市主要城区，每个网格约为256 m×224 m。

2）疑犯轨迹数据集。该数据集包括了W市2013年1月－6月分布在1 020个位置上的158名疑犯的17 539个轨迹点。

3）其他数据：(1)犯罪事件数据，包含了2013年1月－12月W市的102 861起犯罪事件。(2) POI数据集，包括102 641个POI，每条POI记录包括兴趣点类别、经纬度坐标等信息。POI的类型包括餐饮、交通、旅店、居民小区、教育、文体娱乐、商场、政府和事业单位、工厂、企业公司、卫生和银行。(3)社会经济环境数据集：包括W市3 602个社区内的人口数量、教育程度分布、性别、出生年份分布、民族分布等社会经济信息。

2.2 测试指标

top-k距离偏离度（top-k deviation, TD）^[12]：描述了结果中top-k个概率最大的位置与正确位置之间的最短距离。该指标越小越好。

top-k精确率（top-k precision, TP）^[13]：对预测结果排序得到L_R序列，如果正确位置存在于L_R的top-k个预测结果中，则称该次测试为正确预测。该值越大越好。

以上两项指标的k设为9，位置间的距离为网格的中心间距。

2.3 比较方法

本研究与当前最新或常用的5种犯罪位置预测方法进行比较。

1) 最频繁方法(most frequent, MF)：该模型计算出疑犯在各时段上的位置频次，将目标时段t中出现频次最大的位置作为预测值。

2) 时态Rossmo方法(temporal-Rossmo, TR)^[4]。该模型在传统的犯罪地理画像模型Rossmo公式中引入了时态效应。利用目标疑犯在目标时间的前10个位置作为系列犯罪位置。

${h_{ij}} = \left\{ {\begin{array}{*{20}{l}} {\frac{1}{{{{\left( {{d_{ij}}} \right)}^f}}}, {d_{ij}} > B\left( {{\rm{\Delta }}t} \right)}\\ {\frac{{B{{\left( {{\rm{\Delta }}t} \right)}^{f - g}}}}{{2B\left( {{\rm{\Delta }}t} \right) - {{\left( {{d_{ij}}} \right)}^g}}}, {d_{ij}} \le B\left( {{\rm{\Delta }}t} \right)} \end{array}} \right. $

(17)

其中，

式中，d_ij为目标位置i与某系列犯罪位置j间的距离；B₀为系列犯罪位置间的平均间距；Δt为目标时间与当前时段的差值；a₀、f和g都为系数。

3) 层次式Pitman-Yor日时段先验模型(hierarchical Pitman-Yor prior hour-day model，HPHD)^[14]。采用Markov矩阵表达位置间的转移概率，采用高斯分布表达时间上的位置访问模式。

4) 3W方法(who, when and where，W³)。W^4[15]采用概率生成模型描述特定用户在特定时空出现特定主题的词汇分布概率。由于本文不涉及推特，因此其位置预测模型变为W³：

$\begin{array}{l} P\left( {{r_j}|u, t} \right) = \\ \sum\limits_{l = 1}^{|L|} P \left( {u, t, {g_l}, {r_j}} \right){\left( {\sum\limits_{l = 1}^{|L|} {\sum\limits_{k = 1}^{|K|} P } \left( {u, t, {g_l}, {r_k}} \right)} \right)^{ - 1}} \end{array} $

(18)

式中，r_j为第j个实际位置；u和t分别为目标用户和目标时间；g_l为第l个潜在地理位置；|K|为所有实际位置的数量；|L|为所有潜在地理位置的数量。

5) 规律和从众性位置预测方法(regularity and conformity location prediction，RCLP)^[7]：使用重力模型估算网格的转移概率，使用矩阵分解技术进行用户的时态位置分布概率计算。由于本文不涉及功能区划分和网格内的位置分布计算，因此在计算过程中去除这两个因子。

由于数据稀疏，以上方法可能没有返回结果，这时，以查询轨迹中的最后一个轨迹点为准。

2.4 top-k距离偏离度比较

图 1表示相似疑犯数量m与各模型top-k距离偏离度的关系。无论m取任何值，SSLP的top-k距离偏离度明显优于其他5个模型。随着m的增加，包括SSLP在内的所有模型均通过相似疑犯数量的增加而获得了更多的轨迹数据，且其top-k距离偏离度的指标性能开始提升。这说明本文提出的利用相似疑犯的轨迹作为目标疑犯的补充数据能让各模型具备有效的数据稀疏缓解能力。当m=24时，SSLP的top-k距离偏离度仍然优于其他5个模型约10%~22%。

2.5 top-k精确率比较

图 2表示各模型中相似疑犯数量m与其top-k精确率的关系。随着m的增加，SSLP的top-k精确率分布在12%~18%，明显优于其他5个流行方法。当m为0时，SSLP的top-k精确率为12%，优于RCLP的20%，是TR方法的3倍，说明SSLP的抗稀疏能力强。随着m从0增加到8，SSLP的top-k精确率从12%上升到18%，提高了50%。以上结果表明，相对于RCLP通过重力模型获取位置间的转移概率，本文的基于核密度的位置转移频次估算方法能更加准确地表达疑犯的位置转移模式。此外，HPHD利用高斯模型表达人员的时态分布，而本文采用了多项式分布来表达该模式，能更加准确地反映疑犯的日常位置分布习性。

2.6 预测结果可视化

在相同查询条件下，图 3给出了某次预测中SSLP和其他5个流行方法的预测结果。由图 3可知，SSLP的最优位置距离正确位置（+）最近，而正确位置在预测结果集中排在第3位；RCLP和HPHD模型的最优位置距离正确位置稍远，且正确位置在预测结果中的排名也较为靠后。W³、MF和TR模型预测性能更差，它们的最优位置距离正确位置较远，趋向接近查询位置；此外，W³和TR模型的预测结果集未能包括正确位置。

3 结语

本文提出了基于时空语义的疑犯位置时空预测方法, 该方法在top-k距离偏离度和top-k精确率上远超其他流行的位置预测方法。今后将引入更多的特征，如疑犯的位置驻留时间、疑犯所在团伙信息等，进一步提高位置预测准确率。