基于時空信息的假幣犯罪熱點區域探測系統

劉旭斌，齊鳳亮，于 健，李培軍，魏克剛，許舒人

?

基于時空信息的假幣犯罪熱點區域探測系統

劉旭斌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