刘旭斌，齐凤亮，于 健，李培军，魏克刚，许舒人



基于时空信息的假币犯罪热点区域探测系统

刘旭斌1,3，齐凤亮2，于 健2，李培军3，魏克刚3，许舒人3

（1. 中国科学院大学，北京 100049；2. 公安部物证鉴定中心，北京 100038； 3. 中国科学院软件研究所 软件工程技术研究开发中心，北京 100190）

目前已有的犯罪热点分析方式是通过计算犯罪率或使用空间聚类方法，这些方法没有有效的利用时间信息，无法准确反映犯罪分布特征，且很难灵活地从不同层级去判断热点，同时在地图中进行实时渲染。本文采用基于时空数据场的层次聚类算法分析假币收缴数据，挖掘犯罪热点，设计并实现了假币犯罪热点区域探测系统，通过时空数据场理论可以充分融合时空信息，而层次聚类算法可以实现分级聚类，从而满足警方不同层级查看热点区域的需求。

时空信息；时空数据场；热点区域探测；层次聚类

0 引言

近些年来假币犯罪案件逐年增多，银行收缴假币事件也越来越频繁，这在一定程度上影响了社会经济稳定发展，因此，警方逐渐加大了对假币犯罪的打击力度。在假币的流通过程中，部分地区会因为人口数量、教育程度以及经济状况等原因易成为受害重灾区，即假币犯罪热点区域，故从流通热点角度出发打击假币犯罪是一种行之有效的方式。随着犯罪数据的累积，如何有效挖掘数据中潜在的价值为警方提供决策支持成为了亟待解决的问题。本文旨在通过分析大量假币犯罪数据，发现假币流通中热点区域，从而帮助警方更加快速的分析案件。

传统的假币犯罪热点分析方式是通过计算某段时间内各个区域的犯罪率来判断热点区域，但这很难灵活地从不同层级去判断热点，没有很好的融合时间和空间信息，而且无法实时地在地图中进行渲染。虽然目前已有研究人员通过数据挖掘技术来发掘热点，但大多只考虑了时间或空间因素，导致分析出的热点无法全面准确地揭示犯罪分布特征。本文采用基于时空数据场的层次聚类算法分析银行收缴假币热点区域，从而反映假币犯罪热点，通过时空数据场理论可以很好地将时空信息融合在一起综合考虑，而层次聚类算法通过分级聚类，可满足警方宏观和微观查看热点区域的需求，最终使用热力图的方式进行展示，更加清晰直观。

1 相关工作

犯罪地理学指出，犯罪行为从一开始就与地理环境密切相关[1,2]，大量研究也表明犯罪具有明显的时空聚集特性，即存在“犯罪热点”[3-6]。热点区域探测的研究方法融合了犯罪学、环境地理学、统计学、地理信息科学以及制图学等多学科理论及相关技术。热点区域分析指在特定时间区间内，对过往历史数据进行统计分析或采用聚类等机器学习技术，分析出犯罪高发区域，并结合信息可视化技术，在地图上采用热力图方式展示。目前已有很多学者对此开展研究，提出了一些可行的探测方法，主要分为“基于区域统计数据的热点探测方法”和“基于离散点的热点探测方法”。

基于区域统计数据的探测方法大多是通过计算各个辖区的犯罪率、人口总量以及案件总量等统计指标，从而识别出一段时间内的热点犯罪区域或者某辖区的热点犯罪时间段。该方法易受统计指标选取和可变区域单元等因素影响。

基于离散点的探测方法主要是指点模式分析中的空间聚类方法，主要有犯罪位置数量统计法、分割法、层级聚类法、密度估计法等[7,8]。层级聚类法可以通过人为改变聚类参数来调整聚集规模，并按照一定规则产生层级不等的聚集，满足了警方对犯罪热点宏观与微观的不同处置要求[9]。扫描统计法使用了不同半径的圆形扫描窗口搜索整个研究区域，从而监测点数据的显著聚集情况，采用了蒙特卡洛模拟检验显著性[10]。

以往的研究多集中于犯罪空间聚集情况的识别和探测，对于数据的时间信息缺乏足够重视和深度挖掘[11,12]。近些年来，越来越多的学者将时间信息作为犯罪时空分布研究的重要因素，只有结合时空信息，才能完整准确地表达犯罪地理分布特征。对此，一些学者提出了若干代表性方法。例如，为了将时间信息融入到点集分析中，Brunsdon等提出了时空核密度估计法，得到可放置于时空立方体中的三维核密度估计面。而通过使用圆柱体替换空间扫描统计法中圆形的扫描窗口，可将其扩展到时空维度，得到时空扫描统计法。Nakaya等在一项犯罪时空分析的研究中，将日本京都2003年到2004年街头偷盗案件的数据分布于时空立方体中，综合了前述的时空核密度法和时空扫描统计法两种分析方法，较好地识别和解读了研究区域内的犯罪热点及其随时间的变化转移情况[13]。

由于热点探测的目标是方便警务人员从宏观和微观两个方面观察热点区域，层次聚类算法中不同的层级聚类满足了宏观和微观的探测需求，该算法的停止阈值（聚类个数）参数由警务人员指定，而其他聚类算法提前确定参数大多比较困难，采用层次聚类可以将参数交由警务人员确定，故增加了算法分析的可靠性。同时，如果只考虑空间信息，无法全面准确地揭示犯罪分布特征，故本文结合时空信息进行探测分析。综合考虑，本文提出了一种基于时空信息的层次聚类算法进行假币流通中的热点区域探测。

2 时空信息分析

通过分析业务数据，将银行收缴假币数据的特点归纳如下：

（1）同一个人在一次被收缴中存在多次录入情况，具体表现为同一个人在很短的时间间隔内，被同一家银行支行录入多次收缴记录；

（2）每个城市的银行支行的地点是确定的，如果只基于距离做分析的话，不论时间段如何选择，只要这些支行在该段时间内收缴过至少一次，则会导致探测出的热点区域基本都一样；

（3）收缴事件过多，且存在多个收缴事件点处于同一位置，但时间不同，基于时空信息聚类，两个事件可能会被划分到两个区域中，但他们在地图上属于同一个点，所以基于事件聚类显然不合理；

针对第一个问题，本文认为同一个人在同一银行支行同一天被收缴多次的时候，可以认为只收缴了一次，将这几条记录合并为一次收缴事件，具体表现为收缴金额叠加、冠字号并入一个集合。

针对第二个问题，本文将融合时间和空间信息，作为聚类的基础数据，当时间区间不同时，地理位置上的同一点可表达为不同的值，因此，在聚类时，会更加合理的表达点的聚集性。

针对第三个问题，本文采用基于银行支行位置点聚类，当时间区间确定时，如果同一个位置点存在多个收缴事件，则该位置的时间信息有多个，这样与其他位置点计算势能以及差异度时，无法确定使用哪一个时间，而热点探测的目标是分析该时间区间内的平均热点区域，故本文采取将多个收缴事件的收缴时间求均值，作为该位置点的时间属性。

3 时空数据场理论

早在1837年，物理学家法拉第就提出了场的概念，用于描述物体间的非接触相互作用。数据场理论[14]借鉴物理学中场的思想，在抽象的数域空间中引入了物体间的相互作用及其场描述方法。数据场中对象之间的相互作用可以通过定量的势能函数来实现，任何一个数据对象的状态是场中所有其他对象共同作用的结果，其势能值将成为数据对象之间度量相似度的标准，从而实现数据对象检测和聚集区域的分类。

时空数据场银行收缴假币数据，尤其是收缴假币点，不仅包含空间地理信息，而且还包含了丰富的时间信息。对于一个收缴点，它刚刚形成时的能量最强，而且随着时间的推移能量会衰减，所以两点之间相互作用的强度与时间有关系。

4 基于时空数据场的层次聚类算法

4.1 参数优化

由上一小节可知，我们将计算所有收缴点在场中的叠加势能值，然后基于此进行层次聚类。然而，由公式（4）可知，存在未知影响因子σ，且其对结果影响较大，故我们将根据公式（3）对其进行优化求解。

实质上，影响因子σ的最优值是具有单一变量的非线性函数，即最小化势能熵，minH(σ)。目前存在许多算法可以解决这个最优化问题，例如简单的启发式算法、随机搜索方法和模拟退火等。本文采用黄金分割算法来求解影响因子σ的最优值，但由于黄金分割算法需要确定最初的搜索闭区间，而σ∈(0,+∞)，故需要找到一种方法求出最初的合理搜索区间。进退法可以用于确定一维无约束优化问题中的初始搜索区间，故本文采用了一种融合了进退法和黄金分割算法的方法来解决一维无约束优化问题，求出σ的最优解。算法详细描述如下：

输入：收缴点数据集D = {x | xi= (lngi，lati，ti), i = 1, 2, 3…n}

σ初始值a

σ步长缩放因子m

输出：最优解

1: a1 = a, h1 = H(D, a1), a2 = a1*m, h2 = H(D, a2)

3: a3 = a2*h, h3 = H(D, a3)

5: a1 = a2, a2 = a3, h2 = h3, a3 = a2*h, h3 = H(D, a3)

6: end while

7: end if

9: swap(a1, a2), swap(f1, f2), a3 = a2/h, h3 = H(D, a3)

11: a1 = a2, a2 = a3, h2 = h3, a3 = a2/h, h3 = H(D, a3)

12: end while

13: end if

14: left = min(a1, a3), right = max(a1, a3)

15: σr= left + 0.618034 * (right - left), σl= left + right -σr

16: h2 = H(D, σr), h1 = H(D, σl)

19: right =σr, σr=σl, h2 = h1, σl= left + right -σr, h1 = H(D, σl)

20: end if

21: else

22: left =σl, σl=σr, h1 = h2, σr= left + right -σl, h2 = H(D, σr)

23: end else

24: end while

25: return 1.618 * (right + left)/2

4.2 层次聚类算法

输入：S: 所有簇的label，每个簇代表一个收 缴点

d: 两两簇之间的差异值矩阵

N: 最终输出的簇的个数

输出：N个簇

1: procedure LABEL(L)

2: L1 = []

3: N = (number of rows in L) + 1

4: U = new UNION-FIND(N)

7: U.UNION(a, b)

8: end for

9: return L1

10: endprocedure

11: class UNION-FIND

12: method CONSTRUCTOR(N)

13: parent = new int[2N − 1]

14: parent[0, . . . , 2N − 2] all is None

15: end method

16: method UNION (m, n)

17: parent[m] = nextlabel

18: parent[n] = nextlabel

19: nextlabel = nextlabel + 1

20: end method

21: method EFFICIENT- FIND(n)

22: p = n

23: while parent[n] is not None do

24: n = parent[n]

25: end while

27: p, parent[p] = parent[p], n

28: end while

29: return n

30: end method

31: end class

32: procedure MST-LINKAGE(S, d, N)

33: L = MST-LINKAGE-CORE(S, d)

34: Stably sort L with respect to the third column.

35: L = LABEL(L)

36: L = RECOVERY (L, S, N)

37: return L

38: endprocedure

39: procedure MST-LINKAGE-CORE (S0, d)

40: L = []

41: c = (any element of S0)

42: D0[s] = 1 for s 2 S0 {c}

43: for i in (1, . . ., |S0| − 1) do

44: Si= Si−1 {c}

45: for s in Sido

46: Di[s] = min{Di−1[s], d[s, c]}

47: end for

49: Append (c, n, Di[n]) to L

50: c = n

51: end for

52: return L

53: end procedure

54: procedure RECOVERY (L, S, N)

55: tmp = [], valid = []

56: for label in S do:

57: Append ({label}) to tmp, Append (True) to valid

58: end for

59: for step in [0,1…,size(S)-N-1]:

60: a = L[step][0], b = L[step][1], Append (True) to valid

62: end for

63: ret = []

64: for i in [0,1…,size(valid)-1]:

65: if valid[i] == True:

66: Append (tmp[i]) to ret

67: end if

68: end for

69: return ret

5 系统设计与实现

假币犯罪热点探测分析包括四个部分，分别为热点聚类分析、时空信息计算、热力值计算和用户查询处理四个小模块。图1是热点探测分析的流程图，介绍了用户查询模块，热点聚类分析模块，时空信息计算模块和热力值计算模块是如何协作完成热点区域探测分析的。

图1 热点探测分析流程图

如图1所示，热点探测聚类分析的主要功能是根据用户指定的时间和空间范围生成对应的热力图，首先是用户查询处理模块接收用户的查询条件，主要包括时间段和区域（精确到县级别），根据这些查询条件从数据库中查询出所有符合的收缴记录。然后热点聚类分析模块通过统计计算这些收缴记录，得到各个银行点以及其在这段时间内的收缴信息，由时空信息计算模块计算银行点的时空属性，之后进行时空数据场公式中的影响因子参数优化，优化时需要调用时空信息计算模块来计算各个参数取值时的势能熵。当参数最优值确定后，计算此时的各个银行点势能值，接下来热点聚类分析模块基于此势能值进行层次聚类，得到各个热点区域，再将此聚类信息传入热力值计算模块，通过结合其他收缴属性特征和各个区域的势能值，热力值计算模块可以计算得到各个区域的热点值大小，然后由热点聚类分析模块将此热力值加入到聚类结果中，返回给用户查询处理模块，最后返回探测结果。

5.1 时空信息计算

该模块主要的作用是计算每个聚类银行点的时空属性，由于空间点信息已确定，故此处介绍银行点处的时间信息计算。

首先，遍历每一个银行点在选定时间范围内的所有收缴事件，根据被收缴人姓名、身份证号、收缴时间、收缴地点属性判断是否为同一个人同一天在同一家银行多次被收缴，若是，则将这两个事件合并为一个，合并策略是收缴金额相加。然后使用合并完的收缴事件来计算该银行点处的时间属性。用户的目标旨在查询一段时间一个区域范围内的收缴热点，当用户选定时间范围时，更希望看到的是该段时间内的平均热点。故本系统在处理此处的时间融合时，采取的策略是简单的将合并完事件的时间值求平均，作为该银行点在这段时间内的收缴时间。

在计算完银行点收缴时间的均值后，然后根据第四章介绍的公式（2）和（4），计算出该区域内所有的银行点处的势能值，根据公式（3），计算势 能熵。

5.2 热点聚类分析

根据各银行点处的势能值，可以计算出两两银行点之间的势能差，作为这两点的差异度，故我们可以计算得到差异度矩阵。聚类算法的目标是使得类中对象之间差异度越小越好，而类间对象之间的差异度越大越好。将差异度矩阵输入到第五章介绍的层次聚类算法中进行分析，同时，可以指定聚类的个数，增加了系统灵活度。该模块类图如下图2所示。

图2 热点聚类模块类图

类图中的STCluster类关联HotVal类和STCal类，其中HotVal类对应热力值计算模块，STCal类对应时空信息计算模块，而STCluster类则对应热点聚类分析模块。STCluster类中的preDeal()方法统计各个银行点上的收缴事件以及进行预处理，getSamples()方法负责对原有银行点采样，getOptimalFactor()方法获取最优的影响因子参数，execCluster()方法则是进行聚类过程计算。

5.3 热力值计算

通过层次聚类获得了各个聚类簇，但这无法反应各个簇所在区域的假币收缴热点情况，故需要计算各个簇的热力值，然后在热力图中进行热度渲染。

经过对假币犯罪数据的经验分析，我们筛选出冠字号、收缴金额这两个属性，同时再结合计算出的势能值以及该簇内收缴事件的发生量，通过将这些信息进行融合，来计算热力值。计算公式如下：

5.4 用户查询处理

该模块主要负责接收用户查询请求，调用其他模块处理请求，并返回数据给前端进行展示。

5.5 效果展示

当浏览器端接收到返回的热点探测结果后，会在前端进行地图上的热力图渲染。热点区域探测结果的可视化，主要包括若干个热点区域的叠加可视化、某一热点区域的可视化、各个银行点的位置展示以及各个银行点的统计信息展示。同时，将以列表形式展示各个热点区域的信息，包括银行数量、平均收缴时间等。

首先，数据展示模块用列表形式来展示热点探测结果的统计信息。如图3。

图3 热点区域探测-探测结果列表

图3表示2016.05.01到2016.05.14期间云南省的热点探测结果，其中热点划分个数为3。通过上图可以看到，该结果列表显示了各个热点的一些统计信息，包括该热点包含的银行数量、该热点的热度相对大小（即热力值）和在这段时间内的平均收缴时间点。

在结果列表页面，用户可勾选某一个或某几个热点，点击渲染，即可在地图上渲染指定热点的热力图。

如图4所示，该热力图展示了热点编号为2的热力区域范围。通过该图，可以清晰查看在指定时间段内其中一个热点的大致区域，从而反应假币流通中的一个热点区域。

图5展示了热点编号1和2的叠加热点区域。相较于一个热点区域的展示，多个热点的叠加能够更加精确地反应假币流通中热点情况，上图通过两个热点的叠加，可以方便用户更加便捷的发现假币收缴的热点集中区域，可以知道，叠加区域的假币流通更为频繁。同时，通过使用不能深浅的颜色绘制热点区域，能够更加形象展示各个热点区域的热力值大小，颜色越深，热力值越大，表示该区域的假币流通更为频繁。

为了使用户分析热力图时更加全面，在渲染热力图的同时，在地图中标注出了各个银行点的位置，用户通过点击标注点，即可查看该银行点的收缴情况等信息。具体如图6所示。

以上展示了热点划分个数为3时的探测效果，当划分个数设置为1时，可以从更宏观的角度观察热点的大致区域分布。具体如图7所示，从该图可以看出全省热点犯罪的大致区域，而划分个数为3时，展示的热点区域划分更加精细。

图5 热点区域探测-热力图叠加渲染结果

图6 热点区域探测-银行点收缴情况

图7 热点区域探测-热力图渲染结果

6 结语

本文分析大量假币收缴数据的特征，通过时空数据场的方法将假币收缴事件中的时空信息融合起来，采用层次聚类法探测不同层级的热点区域，帮助警务人员从宏观和微观两个角度观察热点区域，同时显示热点信息以及收缴基本信息。在下一步工作中，我们将会基于历史假币犯罪热点区域预测未来的热点区域，帮助警方进行犯罪预防。

[1] 孙峰华, 李世泰, 黄丽萍. 中外犯罪地理规律实证研究.人文地理, 2006, 21(5): 14-18.

[2] 孙峰华, 魏晓. 犯罪地理学研究的新进展. 人文地理, 2004, 19(5): 60-63.

[3] Johnson S D. Repeat burglary victimization: A tale of two theories. Journal of Experimental Criminology, 2008, 4(3): 215-240.

[4] 赵勇, 刘民, 柏书华, 等. 系列入室盗窃案件的犯罪距离研究.中国人民公安大学学报: 社会科学版, 2010(2): 143-149.

[5] Grubesic T H, Mack E A. Spatial-temporal interaction of urban crime. Journal of Quantitative Criminology, 2008, 24(3): 285-306.

[6] Bowers K J, Johnson S D. Domestic burglary repeats and space-time clusters. European Journal of Criminology, 2005, 2(1): 67-92.

[7] 孙吉贵, 刘杰, 赵连宇. 聚类算法研究. 软件学报, 2008, 19(1): 48-61.

[8] 邓敏, 刘启亮, 李光强, 等. 基于场论的空间聚类算法.遥感学报, 2010, 14(4): 702-709.

[9] Levine N. CrimeStat III. Washington DC: the National Institute of Justice, 2009.

[10] Kulldorff M. A spatial scan statistic[J]. Communications in Statistics - Theory and Methods. 1997, 26(6): 1481-1496.

[11] Felson M, Poulsen E. Simple indicators of crime by time of day[J]. International Journal of Forecasting. 2003, 19(4): 595-601.

[12] Ratcliffe J H. The hotspot matrix: A framework for the spatio-temporal targeting of crime reduction[J]. Police Practice and Research. 2004, 5(1): 5-23.

[13] Nakaya T, Yano K. Visualising crime clusters in a space-time cube: An exploratory data-analysis approach using space-time kernel density estimation and scan statistics[J]. Transactions in GIS. 2010, 14(3): 223-239.

[14] Li Deyi, Du Yi. Artificial intelligence with uncertainty[M]. Beijing: National Defence Industry Press, 2005.

Hot Spot Detection System for Counterfeit Currency Crime Based on Spatio Temporal Information

LIU Xu-bin1,3, QI Feng-liang2, YU Jian2, LI Pei-jun3, WEI Ke-gang3, XU Shu-ren3

(1. University of Chinese Academy of Sciences, Beijing 100049, China; 2. Institute of Forensic Sciences, Ministry of Public Security, Beijing 100038, China; 3. Technology Center of Software Engineering, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China)

At present, the analysis of crime hotspots is by calculating crime rate or using spatial clustering method. These methods do not use time information effectively and cannot accurately reflect the characteristics of crime distribution, and it is difficult to flexibly determine hotspots from different levels while performing real-time rendering in maps. This paper adopts a hierarchical clustering algorithm based on spatio-temporal data field to analyze the data of counterfeit currency seizures, mine criminal hotspots, and design and implement a hot currency area detection system for counterfeit currency crimes. Spatio-temporal data field theory can fully integrate spatio-temporal information, and hierarchical clustering algorithm can achieve hierarchical clustering, so as to meet the needs of police at different levels to view hot spots.

Spatio-temporal information; Spatio-temporal data field; Hot spot detection; Hierarchical clustering

TP 317

A

10.3969/j.issn.1003-6970.2018.10.020

刘旭斌(1992-)，男，硕士，分布式计算、数据挖掘；齐凤亮(1983-)，男，硕士，情报分析、文件检验；于健(1988-)，男，硕士，反假币情报分析；李培军(1976-)，男，硕士，CCF会员，大数据、商业智能；魏克刚(1977-)，男，硕士，计算机软件、软件工程；许舒人(1961-)，男，学士，CCF高级会员、计算机应用委员会委员，网络分布计算和软件工程。

刘旭斌，齐凤亮，于健，等. 基于时空信息的假币犯罪热点区域探测系统[J]. 软件，2018，39（10）：97-104