留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

顾及时空语义的疑犯位置时空预测

段炼 胡涛 朱欣焰 叶信岳 王少华

段炼, 胡涛, 朱欣焰, 叶信岳, 王少华. 顾及时空语义的疑犯位置时空预测[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 765-770. doi: 10.13203/j.whugis20170238
引用本文: 段炼, 胡涛, 朱欣焰, 叶信岳, 王少华. 顾及时空语义的疑犯位置时空预测[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 765-770. doi: 10.13203/j.whugis20170238
DUAN Lian, HU Tao, ZHU Xinyan, YE Xinyue, WANG Shaohua. Spatio-Temporal Prediction of Suspect Location by Spatio-Temporal Semantics[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 765-770. doi: 10.13203/j.whugis20170238
Citation: DUAN Lian, HU Tao, ZHU Xinyan, YE Xinyue, WANG Shaohua. Spatio-Temporal Prediction of Suspect Location by Spatio-Temporal Semantics[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 765-770. doi: 10.13203/j.whugis20170238

顾及时空语义的疑犯位置时空预测

doi: 10.13203/j.whugis20170238
基金项目: 

国家自然科学基金 41401524

广西自然科学基金 2015GXNSFBA139191

广西自然科学基金 2018JJA150089

警用地理信息技术公安部重点实验室开放课题 2016LPGIT03

北部湾环境演变与资源利用教育部重点实验室开放基金 2014BGERLXT14

矿山空间信息技术国家测绘地理信息局重点实验室开放基金 KLM201409

测绘遥感信息工程国家重点实验室开放基金 (16)03

详细信息
    作者简介:

    段炼, 博士, 副教授, 主要从事警情时空数据挖掘理论与方法研究。wtusm@163.com

    通讯作者: 胡涛, 博士。thu6@kent.edu
  • 中图分类号: P208

Spatio-Temporal Prediction of Suspect Location by Spatio-Temporal Semantics

Funds: 

National Natural Science Foundation of China 41401524

Guangxi Natural Science Foundation 2015GXNSFBA139191

Guangxi Natural Science Foundation 2018JJA150089

Open Research Program of Key Laboratory of Police Geographic Information Technology, Ministry of Public Security 2016LPGIT03

Open Research Program of Key Laboratory of Environment Change and Resources Use in Beibu Gulf, Ministry of Education 2014BGERLXT14

Open Research Program of Key Laboratory of Mine Spatial Information Technologies, NASG KLM201409

Open Fund of State Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing (16)03

More Information
    Author Bio:

    DUAN Lian, PhD, associate professor, specializes in geo-policing data mining. E-mail: wtusm@163.com

    Corresponding author: HU Tao, PhD. E-mail: thu6@kent.edu
图(3)
计量
  • 文章访问数:  1071
  • HTML全文浏览量:  104
  • PDF下载量:  190
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-03-26
  • 刊出日期:  2019-05-05

顾及时空语义的疑犯位置时空预测

doi: 10.13203/j.whugis20170238
    基金项目:

    国家自然科学基金 41401524

    广西自然科学基金 2015GXNSFBA139191

    广西自然科学基金 2018JJA150089

    警用地理信息技术公安部重点实验室开放课题 2016LPGIT03

    北部湾环境演变与资源利用教育部重点实验室开放基金 2014BGERLXT14

    矿山空间信息技术国家测绘地理信息局重点实验室开放基金 KLM201409

    测绘遥感信息工程国家重点实验室开放基金 (16)03

    作者简介:

    段炼, 博士, 副教授, 主要从事警情时空数据挖掘理论与方法研究。wtusm@163.com

    通讯作者: 胡涛, 博士。thu6@kent.edu
  • 中图分类号: P208

摘要: 预测疑犯的社会活动行踪,对案件嫌疑人的排查以及犯罪行为的主动预防具有重大意义。当前研究主要依据疑犯的历史系列作案位置预测其住址或未来犯罪位置,缺少对其复杂社会活动位置的转移过程进行建模,也没有考虑位置数据稀疏性对预测性能产生的影响。为此,提出了融合时空语义的位置时空预测(spa-tio-temporal semantics location prediction,SSLP)模型。首先,利用疑犯在不同语义时段和语义位置上的分布邻近性提取目标疑犯的相似疑犯群体;其次,结合该群体的轨迹数据和位置语义信息,基于核密度平滑方法估算出涉及未记录位置的转移频次及其时态访问概率;最后,采用贝叶斯模型实现疑犯个体的时空预测。实验结果表明,基于W市2013年1月至6月间158名疑犯的17 539个位置记录数据,SSLP模型在top-k距离偏离度和top-k精确率上优于其他流行方法40%~50%,对疑犯位置数据稀疏性具有优异的适应能力。

English Abstract

段炼, 胡涛, 朱欣焰, 叶信岳, 王少华. 顾及时空语义的疑犯位置时空预测[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 765-770. doi: 10.13203/j.whugis20170238
引用本文: 段炼, 胡涛, 朱欣焰, 叶信岳, 王少华. 顾及时空语义的疑犯位置时空预测[J]. 武汉大学学报 ● 信息科学版, 2019, 44(5): 765-770. doi: 10.13203/j.whugis20170238
DUAN Lian, HU Tao, ZHU Xinyan, YE Xinyue, WANG Shaohua. Spatio-Temporal Prediction of Suspect Location by Spatio-Temporal Semantics[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 765-770. doi: 10.13203/j.whugis20170238
Citation: DUAN Lian, HU Tao, ZHU Xinyan, YE Xinyue, WANG Shaohua. Spatio-Temporal Prediction of Suspect Location by Spatio-Temporal Semantics[J]. Geomatics and Information Science of Wuhan University, 2019, 44(5): 765-770. doi: 10.13203/j.whugis20170238
  • 根据疑犯位置跟踪数据预测疑犯未来位置,对案件嫌疑人排查以及“犯罪黑数”[1]探测等具有重要的应用价值。在犯罪地理画像研究中,学者们基于平均作案距离[2]、用地类型[3]、路网结构[4]、动力学模型[5]、回归模型[6]等进行相关犯罪个体的位置预测。然而,这些研究未能顾及位置数据稀疏性对预测准确性的影响[7]。普通用户的位置预测研究通过结合社交关系数据[8]、交通数据[9]或多源移动数据[10]来缓解单个用户数据稀疏性问题,但由于疑犯的防备性,他们的社交数据量极少且缺少地理标识;而已有研究中涉及的多源数据与疑犯个体移动偏好的相关性小,难以提供他们有效的位置分布先验信息。为应对以上挑战,本文提出了融合时空语义的位置时空预测(spatio-temporal semantics location prediction,SSLP)模型。该模型首先使用具有入室盗窃案底的疑犯位置数据,提取与目标疑犯具有类似社会习性的疑犯群体,将其轨迹集作为目标疑犯的位置数据源;其次,估算疑犯在轨迹点周边位置(未记录位置)与其他位置间的转移频次及其在各位置上的时态分布概率;最后,采用贝叶斯方法实现疑犯的位置时空预测。

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

    • 定义1  空间语义向量:区域r的空间语义向量表示为:sr=[sr1 sr2srk],其中,sri为区域r的第i个社会环境特征。社会环境特征类型包括月犯罪率、人口数、房屋密度、各类职业的数量、道路密度和各类兴趣点(point of interest,POI)的数量等。

      基于余弦距离公式,sisj的空间语义距离可表示为:

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

      据此,两轨迹点ij距离量度ω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)

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

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

      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的访问强度qt,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)

      式中,bu,s为疑犯u访问聚类簇s的总次数;bt,u,s为疑犯u在语义时间t访问s的次数;It{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) 疑犯uv在聚类簇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) 结合两疑犯uv在所有聚类簇上的访问模式差异度,获取疑犯间的相似度:

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

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

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

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

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

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

      定义4  密度吸引集及密度吸引子:设pipx为基本区域单元,对于$\exists {p_i} \in D$,存在dixω,即区域ix间的空间距离小于阈值ω,则称Dpx的密度吸引集,pipx的密度吸引子。

    • p0为轨迹位置,px为外围位置,求p0px的转移频次。已知D={p1pipN}为px的密度吸引集,p0D中各轨迹位置转移的频次为{c10ci0cN0}。在仅考虑空间距离时,p0px转移的物理频次$\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为密度吸引子的总数;KGuas(·)为高斯核函数;dxipxp0的空间距离;hf为根据物理距离估计位置转移频次时核密度函数的带宽。

      仅考虑位置语义相似度时,p0px的语义转移频次$\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)

      式中,ρ0xp0px间的空间语义距离;hs为根据语义距离估计位置转移频次时核密度函数的带宽。

      对式(7)、式(8)求均值,即可估算出p0px转移的频次为:

      $$c_x^0 = \frac{{\dot c_x^0 + \ddot c_x^0}}{2} $$ (9)
    • p0为轨迹位置,px为外围位置,求pxp0的转移频次。已知px的密度吸引集D中各轨迹位置p1pipN至轨迹位置p0的转移频次,则利用式(7)和式(8),可分别计算出pxp0转移的物理频次$\dot c_0^x$和语义频次和$\ddot c_0^x$。结合这两者,可获得pxp0的转移频次$c_0^x$为:

      $$c_0^x = \frac{{\dot c_0^x + \ddot c_0^x}}{2} $$ (10)
    • 外围位置px至外围位置py的转移频次从两方面获取:(1)将py看作轨迹位置,利用式(9)计算pxpy的转移频次cxy;(2)将px看作轨迹位置,利用式(10)计算pxpy之间的转移频次cyx。则pxpy的转移频次为两者的均值:

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

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

    • 位置ij的转移概率piji到达j的频次cij除以i到达其他所有位置频次之和,即:

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

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

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

      $$\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为目标位置;zi, 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$与轨迹位置ri的空间距离;|D|为密度吸引子的数量。

    • 给定目标疑犯的历史位置序列Tp={n1=rk+1, n2=rk+2nh=rk+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)

      式中, rx为待预测的位置;th+1w=tw为以周天(DOW)表示的待预测时间;th+1d=td为以小时语义时段(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(tw|rk+h)与P(td|rk+h),基于式(12)可获得p(k+h)x

    • 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个社区内的人口数量、教育程度分布、性别、出生年份分布、民族分布等社会经济信息。

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

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

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

    • 本研究与当前最新或常用的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)

      其中,

      $$B\left( {{\rm{\Delta }}t} \right) = {B_0}{{\rm{e}}^{ - {a_0}{\rm{\Delta }}t}} $$

      式中,dij为目标位置i与某系列犯罪位置j间的距离;B0为系列犯罪位置间的平均间距;Δt为目标时间与当前时段的差值;a0fg都为系数。

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

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

      $$\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)

      式中,rj为第j个实际位置;ut分别为目标用户和目标时间;gl为第l个潜在地理位置;|K|为所有实际位置的数量;|L|为所有潜在地理位置的数量。

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

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

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

      图  1  top-k距离偏离度

      Figure 1.  top-k Deviation

    • 图 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  top-k精确率

      Figure 2.  top-k Precision

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

      图  3  不同方法预测结果可视化

      Figure 3.  Visualization of Prediction Results with Different Methods

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

参考文献 (15)

目录

    /

    返回文章
    返回