王 晟 郭紅鈺

(華北計算技術(shù)研究所公安系統(tǒng)部門 北京 100083)

0 引 言

社區(qū)矯正工作是司法體制改革工作的重要內(nèi)容，隨著司法體制改革工作的開展，社區(qū)矯正得到了快速的發(fā)展。目前，在社區(qū)矯正領(lǐng)域并沒有對社區(qū)矯正人員在界內(nèi)的行為軌跡進行分析，只是對人員是否有越界的行為進行檢測。

矯正人員再犯風(fēng)險評估是社區(qū)矯正的一項基礎(chǔ)性工作，具有迫切的現(xiàn)實需求。實際中，矯正人員再犯風(fēng)險主要來自于自身環(huán)境和社會環(huán)境兩個方面，其中：自身環(huán)境信息包括家庭背景、受教育程度、健康狀況等數(shù)據(jù)，但這些信息更多是靜態(tài)的甚至可以偽裝，難以反映矯正人員的真實狀態(tài)。而和社會環(huán)境相關(guān)的動態(tài)信息對矯正人員再犯影響更大，這些信息往往隱含在矯正人員日常動態(tài)行為中。目前，社區(qū)矯正人員佩戴了具有GPS功能的定位手環(huán)或手機，能準確獲取出行位置信息[3]。為此，需要獲取和分析矯正人員的軌跡大數(shù)據(jù)。

本文研究的是社區(qū)矯正人員的軌跡信息，將監(jiān)測的人員位置信息和時間地理位置等相結(jié)合[11]，試圖發(fā)現(xiàn)人員軌跡的規(guī)律[7]，旨在對社區(qū)矯正人員的軌跡信息進行拆分歸類，給監(jiān)管業(yè)務(wù)提供支持。

1 軌跡分段

軌跡是符合一定條件的點所形成的圖形，或者說，符合一定條件的點的全體所組成的集合，叫做滿足該條件的點的軌跡。一個社區(qū)矯正人員一天的軌跡包含了這個人整天的活動地點和路徑，這些軌跡錯綜復(fù)雜，既有該人員的活動地點，也包含著其途經(jīng)往返的點。從整體上來分析軌跡信息是很困難的，也不能夠提取到與其他人員的共同點。所以在社區(qū)矯正領(lǐng)域?qū)θ藛T軌跡的分析首先就是要將該軌跡來進行分段處理[13]，這樣能夠?qū)⒁粋€整體的難處理的問題分解成一個個細小的子問題，也容易對各個軌跡特征進行分析統(tǒng)計。

1.1 軌跡特征點識別

定義1軌跡：設(shè)gi為一個移動物體的第i個GPS信號點，那么一連串的含有時間標記的GPS點則可以表示該移動物體從g1移動到gi的軌跡TR，TR={g1g2…gigi+1…gn}。

定義2軌跡特征點：在一條軌跡中選取一些點，這些最能代表軌跡特征的點就被稱為軌跡特征點。

在將軌跡分段前，首先就是要簡化軌跡，找到社區(qū)矯正人員的軌跡特征點。如圖1所示。

圖1 社區(qū)矯正人員的軌跡圖

可以看到，該人員外出經(jīng)過一系列的地點，最終又回到了起點?？傮w上說，只能判斷該人員在這一天外出了，但是他外出時，到底目的地是什么并不清楚。在社區(qū)矯正領(lǐng)域，人員的活動情況和時間緊密相連，在一個場所停留時間足夠長才表示該人員在該場所活動。

同時在該場地內(nèi)部的行為軌跡，我們并不關(guān)心。換句話說，本文關(guān)心的是該人員在某個時間是否到過某個場地。在現(xiàn)有的軌跡識別算法中，取特征點時一般是根據(jù)軌跡的變化角度、變化速度等[5]。然而在一個場地內(nèi)的軌跡曲曲折折，變化快慢與否對本文來說無關(guān)緊要。如何去掉這些次要因素，選取需要的軌跡特征點是本文解決的一個問題。

考慮到人員行為的時間和位置特點，本文對具有噪聲的基于密度的聚類方法DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法進行了改進，從而實現(xiàn)了特征點的選取。

1.2 DBSCAN算法

DBSCAN這是基于密度的算法，它能夠較為效率地去除噪聲點，聚類后的結(jié)果是將數(shù)據(jù)分成了若干個簇，簇的形狀可以是任意的，沒有要求。

在DBSCAN算法中，首先需要設(shè)置兩個參數(shù)Eps和MinPts。Eps代表的是檢索時的半徑；MinPts代表的是判斷是否是核心點時需要包含點的最小數(shù)目。該算法將輸入點分為三種：核心點、邊界點和噪聲點。核心點是指在該點的半徑為Eps的范圍內(nèi)有最少MinPts個數(shù)的點；邊界點指在該點同樣大小的范圍內(nèi)沒有MinPts個數(shù)的點并且該點在其他核心點的Eps鄰域內(nèi)；最后剩余的點就是噪聲點。在該算法中，從一個點向外擴散的時候需要滿足一定的條件——密度相連[18]。

DBSCAN算法的目的是找到密度相連對象的最大集合。算法的具體過程描述如下：掃描全部數(shù)據(jù)集，找到其中任意一個核心點，尋找從該點出發(fā)的所有密度相連的數(shù)據(jù)點。將該簇標記為已查找，重新掃描標記為未查找的點的數(shù)據(jù)集，尋找沒有被聚類的核心點，重復(fù)以上步驟，直至數(shù)據(jù)集中沒有新的核心點。

1.3 改進的DBSCAN算法

通過DBSCAN算法可以找到不同形狀的簇，但是對于社區(qū)矯正數(shù)據(jù)來說，時間是一個很重要的屬性，同一個場所，在白天和晚上活動有可能會帶來很大的不同。比如說，白天去別人家和晚上去別人家就會有區(qū)別，白天在街上閑逛與晚上在街邊蹲點就不一樣等。DBSCAN算法無法區(qū)分不同時間經(jīng)過同一個位置的數(shù)據(jù)，所以本文通過引進時間變量來解決這個問題。給每個點加入時間屬性來代表該點采集的時間，在DBSCAN算法中遍歷每個點，判斷它的Eps鄰域時需要按照時間順序來往前和往后統(tǒng)計，即加入TEps代表時間鄰域。統(tǒng)計對象p的鄰域內(nèi)的點需要同時滿足Eps和TEps，這樣就把不同時間相同位置的數(shù)據(jù)區(qū)分開來了。

1.4 軌跡分段

時空軌跡分類的過程主要分為軌跡預(yù)處理、特征提取、建立分類器3個階段[8]。將運動軌跡作為整體聚類會丟失相似子軌跡段，而相似子軌跡段在實際應(yīng)用中用處很大[9]。

在獲得了軌跡的特征點后，下一步可以進行軌跡分段了。上文提到，在社區(qū)矯正領(lǐng)域，時間是很重要的屬性，同一個地方，在不同的時間點停留有著很大的區(qū)別。在一般軌跡分段的時候所采用的軌跡角度和速度變化[4]在社區(qū)矯正領(lǐng)域反而并不重要。所以，本文按照時間屬性進行分段。

首先根據(jù)業(yè)務(wù)特征給出需要分割的時間段，比如一般意義上的白天和黑夜的時間段，或者禁止外出的時間段等。然后分別掃描各時間段內(nèi)的所有點，如果該特征點的持續(xù)時間在多個時間段內(nèi)，那么在這些時間段中都包含該點。最后將各組的點按照時間順序連線就得到了分段后的軌跡。其偽代碼如下：

SET T1,T2,T3,…,Tn

//設(shè)置分類時間段

GET p(x,y,t1,t2)

//獲取特征點

WHILE i

//遍歷分類的時間段

IF (t1in ti) or (t2in Ti)

then p in List

是一個重大人生角色的轉(zhuǎn)變，從一個天真爛漫，倍受寵愛的少女，變?yōu)橐粋€要哺育寶寶的媽媽。尤其是一些較年輕的新手媽媽，自己好像還是一個孩子，一下子要面對孩子的哭鬧，半夜要給寶寶喂奶，換尿布，這些突如其來的變化，會給心理造成一定的影響。

//將符合條件的特征點放入所屬的集合中

END

2 軌跡聚類

軌跡分段后要對分段后的軌跡進行聚類，這是為了對多個人員或者同一個人員多個天數(shù)的數(shù)據(jù)進行比對，這樣才可以獲得軌跡的共性，進行進一步的分析。

2.1 軌跡距離

將軌跡分段后，可以對多個對象的軌跡片段進行聚類，這樣可以為社區(qū)矯正人員的行為分析、預(yù)測和異常行為監(jiān)控等做準備。

軌跡聚類的算法有很多，比如針對空間網(wǎng)絡(luò)的聚類[10]、基于結(jié)構(gòu)相似的軌跡聚類[4]等。對于軌跡聚類來說，如何衡量兩個軌跡之間的距離或相似性是需要解決的核心問題[2]。傳統(tǒng)的異常點檢測算法中衡量對象之間距離的方式無法直接用來檢測兩個軌跡之間的距離[1]，這是由于軌跡是由若干個點組成的，無法單獨去比較其中的一個點。目前來說，Lee等[17]提出的TROAD檢查方法利用模式識別領(lǐng)域的Hausdorff距離來計算軌跡子段之間的距離是一種有效的方式。在該方法中的Hausdorff距離是由需要測量的兩個有向線段之間的平行距離、垂直距離和夾角三個部分加權(quán)求和求得的。這個方法考慮的是軌跡的空間特性，但是對于社區(qū)矯正領(lǐng)域，兩個軌跡的方向、水平距離和垂直距離都不能代表它們是否相似。我們需要考慮更多的是軌跡特征點的實際意義[15]，而與到達軌跡特征點的途徑無關(guān)。這是因為在兩個不同的城市有著相同類型的建筑，分別經(jīng)過這兩個建筑的軌跡是相似的，而它們的方向、水平距離和垂直距離都毫無意義?？紤]到這個因素，結(jié)合地理位置信息[16]來表示軌跡距離會更好些。

將采集的GPS坐標和地圖坐標對應(yīng)，在地圖上標識出坐標后可以識別周圍的建筑物信息。由社區(qū)矯正的業(yè)務(wù)特點將建筑物分為幾類，比如醫(yī)院、娛樂場所、體育場所和餐館等。賦予這幾類建筑所占的權(quán)重，將軌跡經(jīng)過的建筑物的權(quán)重進行比較，權(quán)重相差越小則軌跡距離越短，越相似。具體的軌跡距離可以這樣表示：兩個軌跡之間的距離d(tr1,tr2)=|M(tr1)-M(tr2)|，M(tri)表示該軌跡的權(quán)重，一條包含n個點的軌跡的權(quán)重可以這樣表示：

M(tri)=f(t1)·(a1M1)+f(t2)·(a2M2)+…+

f(tn)·(anMn)

式中：f(ti)表示該時間段的權(quán)重系數(shù)；Mi表示該建筑物對應(yīng)的權(quán)重；ai標識在該場所的持續(xù)時間。

2.2 軌跡聚類算法

輸入：Eps—半徑

MinPts—給定點在E鄰域內(nèi)成為核心對象的最小鄰域點數(shù)。

D—集合。

輸出：目標類簇集合

方法：Repeat

1) 判斷輸入線段是否為核心對象

2) 找出核心對象的E鄰域中的所有直接密度可達線段。

Until 所有輸入線段都判斷完畢

Repeat

針對所有核心對象的E鄰域內(nèi)所有直接密度可達線段找到最大密度相連對象集合，中間涉及到一些密度可達對象的合并。

Until 所有核心對象的Eps鄰域都遍歷完畢

2.3 聚類效果

本文采用的數(shù)據(jù)是社區(qū)矯正人員的軌跡數(shù)據(jù)，選取了一個人的軌跡數(shù)據(jù)。由于數(shù)據(jù)的保密性，本文對數(shù)據(jù)的信息做了處理，不顯示其周圍具體的建筑信息和身份信息等，只用事先根據(jù)業(yè)務(wù)特點分好的建筑類型來表示其活動場所。可以看到該人員這天的密集活動區(qū)域有幾個，通過上文的軌跡特征點選取算法，選取特征點后的軌跡如圖2所示。

圖2 簡化后的軌跡圖

可以看到，該人員在這一天從A點(家)出發(fā)去了C點(醫(yī)院)然后回到了B點(家)。通過對該人員的其他更多天數(shù)的軌跡經(jīng)過同樣的處理后，經(jīng)過聚類發(fā)現(xiàn)其大致與這一天的軌跡圖形是一樣的，但是目的地不一樣，更多的目的地是超市和飯店。由此可以得出：這一天該人員的軌跡與平常不一致，經(jīng)過分析可以知道該人員是去了醫(yī)院。這樣，通過對軌跡的聚類可以提取出人員的日常軌跡特征，為社區(qū)矯正業(yè)務(wù)提供支持。

3 實驗結(jié)果統(tǒng)計分析

本文選擇的數(shù)據(jù)是社區(qū)矯正人員的軌跡數(shù)據(jù)集，從中選擇了數(shù)人的百余天的數(shù)據(jù)進行分類，結(jié)果如表1所示。

表1 數(shù)據(jù)統(tǒng)計對比

本文用a、b、c來代表三個人。由表1可以知道a基本上都在家中，偶爾出超市買點東西，有幾天去了醫(yī)院；b超過三分之二的天數(shù)都去了超市，而且在數(shù)據(jù)處理的過程中發(fā)現(xiàn)都去的同一家超市，有可能b在這個超市工作也有可能真的是每天去超市養(yǎng)成的習(xí)慣；c則是全部都在家，并且在數(shù)據(jù)處理時，發(fā)現(xiàn)軌跡點都是同一個點，這有可能是腕表失效或信號太弱等情況。

通過對軌跡數(shù)據(jù)的分段、簡化[14]、聚類后可以發(fā)現(xiàn)他們的軌跡是有規(guī)律的，提取出這些特征后可以為以后的業(yè)務(wù)需求提供數(shù)據(jù)支持。

4 結(jié) 語

本文通過學(xué)習(xí)研究DBSCAN算法，在社區(qū)矯正領(lǐng)域得以改進、應(yīng)用，成功地將社區(qū)矯正人員的行為軌跡拆分并加以聚類，能較好地將他們的日常軌跡和異常軌跡區(qū)分開來。