0 引言
疑犯位置预测对探明疑犯作案时空规律、评估案发位置与疑犯关联性等警务需求有重要的应用价值[1].但由于位置探测源(如旅店登记系统、进出港登记系统、ATM机等)数量和类型有限，警方仅能获取到他们稀疏的位置数据[2]，严重影响了疑犯位置预测的准确性.在犯罪地理学中，已有研究基于犯罪个体的系列犯罪位置序列，基于平均作案距离[3]、路网结构[4]，利用距离衰减函数[4]、贝叶斯公式[5]和动力学模型[6]等，估算锚点(住址或未来犯罪地点等)[7]在空间上的出现概率.然而，这些研究既没有考虑数据稀疏性的影响[8]，也极少考虑时间因素.近年来，基于车辆定位数据[9]、Wi-Fi信号[10]、公共交通数据[11]、人员轨迹数据[12]和地理社交网络check-in数据[13]等的位置预测成为研究热点.然而，疑犯位置数据较这些数据更加稀疏，也不存在好友关系等数据以提高预测精度.为应对以上挑战，笔者融合疑犯群体的统计先验知识和社会环境信息，基于张量联合分解方法来估算疑犯在所有时空节点上的驻留概率.
1 问题描述
疑犯位置数据集包括了W市2012年1月至2012年6月间241名疑犯的18 754个轨迹点.将研究区域网格化，获得g×g格网,G={p1, p2,…, pi,…, pg×g}.本文中g=100，每个网格覆盖的范围约为256 m×224 m[9].如图1所示.
利用各时段(笔者将一天划分为12个时段，每个时段为2小时)不同疑犯在各网格上的驻留次数，构建三维张量Q∈
U×G×T,表达“疑犯-位置-时段”的相互关系，如图2所示.其中，U为疑犯数量；G为网格数量；T为时段数量.由于疑犯位置数据的稀疏性，Q中仅有1%的项才具有数值.因此，需解决的问题是：估算Q内所有缺失项.
图1 网格化后的疑犯空间分布强度
Fig.1 Spatial distribution of suspects visiting density
图2 “疑犯-位置-时段”张量
Fig.2 “Suspect-location-time” tensor
2 系统流程
本方法具体流程如图 3所示.首先，构建“疑犯-位置-时间”张量Q.其次，抽取所有疑犯在不同时空节点驻留的统计信息，构建“疑犯-位置”矩阵与“位置-时间”矩阵，表达疑犯对各时空节点的访问模式.再将人口、路网和POI等信息按照网格尺度汇集，形成“位置-特征”矩阵，并利用出租车轨迹数据构建“位置-位置”矩阵，通过这两个矩阵描述位置间的关联性.最终，对以上张量和矩阵进行协同分解，计算出“张量Q中的缺失值”，实现疑犯个体的时空预测.
图3 系统架构图
Fig.3 System architecture
2.1 疑犯群体的位移特征抽取
基于疑犯位置数据，构建“疑犯-位置”矩阵E∈
U×G，其中，U为疑犯总数；G为网格总数.该矩阵刻画各疑犯的全局空间分布模式.
为获得所有疑犯的全局时空分布模式，构建“位置-时间”矩阵D∈G×T，其中，G表示位置数量；T表示一天内的所有时段数量.D中第i行和第j列的项D(i,j)表示所有疑犯在j时段访问i位置的次数.
2.2 位置特征抽取
2.2.1 位置-特征矩阵
具有类似社会经济环境的区域往往对疑犯具有类似的吸引力.笔者涉及的社会经济环境信息包括4个部分：POI特征集Fp、路网特征集Fr、房屋特征集Fb和人口统计特征集Fc.据此，构建“位置-特征”矩阵C∈G×(p+r+b+c)，其中，G表示位置总数;p、r、b和c分别表示Fp、Fr、Fb和Fc集的特征个数.特别的，对于category 类型的属性，将其转变为1和0表示的one-hot向量结构.
①POI特征.POI特征Fp包括：该位置内POI的空间密度以及12个类型的POI数量共13个特征.为体现区域独有的社会经济环境特性.借鉴TF-IDF方法，将位置i中类型为j的POI数量qij转换为POI类型重要度Yij，
(1)
其中，o为POI类型数量；|G|表示位置总数；|{qi: qij> 0}|表示具有POI类型j的位置个数.
②路网特征.路网特征Fr包括：该位置内的路口数量和5个等级(高速公路、一级公路、二级公路、三级公路及四级公路)的道路长度，共6个指标.
③建筑物特征.笔者抽取的房屋特征Fb包括：楼房密度、5类房屋(住宅型、商业性、行政型、工业型、其他)的数量分布、3类高度(低层、多层、高层)房屋的数量分布，共9个指标.
④人口统计特征.人口统计特征Fc涉及10个指标，分别是人口密度、4个年龄段(18岁以下、18～40岁、40～60岁、60岁以上)的人口数量分布、5类教育程度(文盲、初中、高中、大学、研究生)的人口分布.
2.2.2 位置可达性张量
位置间的空间邻近性和通勤强度体现了位置之间的疑犯转移倾向或流动的便捷程度.下面利用出租车数据表达位置间的时态通勤强度，再结合空间邻近性，计算位置间的时空可达度.
设vtij为t时段下从位置i到达位置j的出租车数量，
为t时段下从位置j出发到达位置i的出租车数量，dij为两位置的空间距离，则两位置在t时段下的关联度为：
(2)
基于上式，构建张量P∈T×G×G，将ptij作为P中的项，得以刻画位置和位置之间的空间可达度.
3 多源数据融合下的张量分解
结合矩阵因子分解和张量因子分解方法计算出Q中的所有缺失项，以获取疑犯个体在任意时空节点的驻留概率.张量Q可因此分解为：
Q≈S×U×J×T.
(3)
其中，核张量(core tensor)S∈du×dg×dt，疑犯低阶潜在因子矩阵(low rank latent factors matrix)U∈U×du、位置低阶潜在因子矩阵 J∈G×dl和时间低阶潜在因子矩阵T∈T×dt，du≤u,dl≤g,dt≤t(本文 du=dl=dt).
“疑犯-位置”矩阵E可因此分解为U和JT的乘积，即：
E≈U×JT.
(4)
同理，“位置-时间”矩阵D≈J×TT, “位置-特征”矩阵C≈I×P (P∈dl×(p+r+c))；位置可达性张量P≈W×J×JT, 其中 W∈dl×dl×dt, dl≤G,dt≤T(本文中 dl=dt).
可见，Q与E、D、C及P共享了潜在因子矩阵U、J和T；P也与E、D以及C共享了潜在因子矩阵J和T.依据这些信息交互关系，得到融合疑犯位移、社会经济环境和位置可达性数据的张量因子分解目标函数：
L (Q,S,W,U,J,T,P)=
(5)
其中，
为Frobenius 范数
作为正则惩罚项以防止模型过拟合；λ1、λ2、λ3、λ4和λ5分别为目标函数中相应项的权重值，以表达各项在目标函数中的重要程度，当它们都为0时，目标函数退化成普通的tucker分解形式(tuckerdecomposition).由于没有数值解析方法(closed-formsolution)能计算出该目标函数的全局最优解，我们基于PARAFAC-style张量分解方法 [14]找出该目标函数的最优解.
4 试验与分析
试验硬件配置为 Intel (R) Core (TM) i777003.6 GHz (4 核)，16 GB内存的计算机，操作系统为Windows 7，软件采用MATLAB2 016 a和TensorToolbox包[17].采用均方根误差和top-k最近距离作为模型性能的评价指标，其中：均方根误差(RMSE)为预测值与真实值之间的误差累加均方根，
(6)
式中：
为Q第t个项的预测值；yt为真实值.由于baseline方法中一些模型的输出结果为概率值，因此这些模型不采用该指标进行比较.
Top-k最近距离(SED@k):目标位置与前top-k个预测结果的最小距离.
(7)
该指标越小越好,本文中k=10.两网格间的距离为它们的中心间距.
4.1 比较方法
笔者所提方法称为TCDLP.Baseline方法.
①时态约束下的Kriging克吕格插值法(TK)：基于每个时间槽内空间邻近位置的访问次数作为目标位置的访问次数.
②层次Pitman-Yorprocess语言统计模型(HPHD)：描述用户在各位置上的语义时间访问强度.该方法无法对未知位置建模.
③HOSVD[15]：仅对“疑犯-位置-时间”张量进行因子分解来获取其缺失值.
试验采用交叉验证，随机从疑犯位置数据集抽取70%为训练数据，20%位验证数据，10%作为测试数据.
4.2 模型性能比较
TCDLP的参数λ1=λ2=λ3=λ4=λ5=0.05，各潜在因子数量k=10.表1为各模型在RMSE和SED@10上的性能.笔者提出的模型在这3个指标上都优于其他3种方法，说明融合多源城市社会经济环境数据对疑犯时空节点估算是有效的.TK的各项指标性能值均为最差，说明在数据稀疏情况下，空间邻近性还无法充分刻画疑犯位置分布的时空模式.基于矩阵/张量分解的方法(如TCDM和HOSVD)的各项性能指标均超过了TK，这表明，位置间的环境相似性能为疑犯时空分布模式的挖掘提供有效信息.由于HPHD给出的结果为概率形式，因此无法对其进行RMSE指标测试.
表 1 各模型的预测性能
Tab.1 Models performances, by “mean ± std”.
模型RMSE指标SED@10指标TK4.64±1.43124±65HPHD—108±62HOSVD3.53±0.6392±59TCDLP2.04±0.8281±58
4.3 TCDLP参数影响分析
让λ1～λ5在0～10变化，观察TCDLP方法在RMSE 和SED@10两个指标的变化，如图4所示.验证各外部环境信息E、D、 C和P对疑犯位置预测性能的影响.由图4可知，集成了外部环境信息后，模型预测性能有了较大提升，RMSE和SED@10的变化较大；但随着各参数的增加，相对于RMSE、SED@10的变化幅度不大，这再次验证了疑犯的社会活动趋向于集聚性.随着λ3的增加， 模型的RMSE 和SED@10都有明显提升，说明位置间的社会环境相似性对疑犯社会移动具有显著的影响.然而，一旦λ4和λ5增加到一定数值，模型的RMSE急速下降，SED@10也有一定的上升，这可能是疑犯位置关联性数据中存在噪声，λ4和λ5的增加放大了这样的噪声，造成模型性能降低.
图4 λ1～λ5对RMSE和SED@10的影响
Fig.4 Impact of λ1～λ5 on RMSE and SED@10
5 结论
提出基于张量协同分解模型估算疑犯的潜在时空分布概率算法.该算法引入社会环境信息，通过张量和矩阵的联合分解估算疑犯位置时空分布，缓解了疑犯位置数据的稀疏性.基于真实疑犯位置跟踪数据的实验结果表明，笔者所提算法在RMSE和SED@10两个指标上分别平均高于其他baseline方法50%和18%.今后的工作将对疑犯进行分类，如盗窃类、抢劫类等，针对不同犯罪类型特点设计算法，进一步提高算法的精度.
[1] Office of the privacy commissioner of canada [EO/BL]. Available online: https:∥www.priv.gc.ca/en/ (accessed on 10th Mar, 2016).
[2] 孙楠. 警用多源数据轨迹分析系统设计与实现[J]. 测绘科学, 2013, 38(5): 51-53.
[3] CHEN N C, WEI S, SONG D W. Prediction of series criminals: An approach based on modeling[C]∥International Conference on Computational and Information sciences, 2010: 72-75.
[4] KENT J D, LEITNER M. Incorporating land cover within bayesian journey-to-crime estimation models [J]. International journal of psychological studies, 2012, 4(2): 120- 140.
[5] BAUMGARTNER K C, FERRARI S, SALFATI C G. Bayesian network modeling of offender behavior for criminal profiling[C]∥IEEE Conference on Decision and Control, 2005:2702-2709.
[6] MOHLER G O, SHORT M B. Geographic pro
ling from kinetic models of criminal behavior[J]. Siam journal on applied mathematics, 2012, 72 (1):163-180.
[7] MARTINEAU M, ERIC B. Journey to murder: Examining the correlates of criminal mobility in sexual homicide[J]. Police practice and research. 2016, 17 (1):68-83.
[8] YANG A M, WU R J, WU H M, et al. The Research of Tree Topology Model for Growth of Natural Selection and Application in Geographical Profile for Criminal[C]∥Information Computing and Applications International Conference, 2010, 106: 383-390.
[9] BRÉBISSON A D, SIMON É, AUVOLAT A, et al. Articial neural networks applied to taxi destination prediction[C]∥European Conference on Principles of Data Mining and Knowledge Discovery, 2015.
[10] SONG L, KOTZ D, JAIN R, et al. Evaluating location predictors with extensive wifi mobility data[C]∥Joint Conference of the IEEE Computer and Communications Societies, IEEE, 2004, 2 (4): 1414-1424.
[11] YUAN N J, WANG Y, ZHANG F, et al. Reconstructing individual mobility from smart card transactions: A space alignment approach[C]∥International Conference on Data Mining, IEEE, 2014, 44 (2): 877-886.
[12] 胡燕, 朱晓瑛, 马刚. 基于 K-Means 和时间匹配的位置预测模型[J]. 郑州大学学报(工学版), 2017, 38(2): 17-20.
[13] JURGENS D，FINETHY T，MCCORRISTON J，et al. Geolocation prediction in twitter using social networks: a critical analysis and review of current practice[C]∥AAAI, 2015:129-141.
[14] CICHOCKI A, ZDUNEK R, PHAN A H, et al. Nonnegative matrix and tensor factorizations: applications to exploratory multiway data analysis and blind source separation[J]. Wiley publishing, 2009, 25 (Q2): 1-3.
[15] VERVLIET N, DEBALS O, SORBER L, et al. Tensorlab 3.0[CP/OL]. https:∥www.tensorlab.net/.