社區(qū)矯正人員位置信息挖掘

王 晟 郭紅鈺

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

0 引 言

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

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

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

1 軌跡分段

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

1.1 軌跡特征點(diǎn)識(shí)別

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

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

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

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

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

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

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

1.2 DBSCAN算法

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

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

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

1.3 改進(jìn)的DBSCAN算法

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

1.4 軌跡分段

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

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

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

SET T1,T2,T3,…,Tn

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

GET p(x,y,t1,t2)

//獲取特征點(diǎn)

WHILE i

//遍歷分類的時(shí)間段

IF (t1in ti) or (t2in Ti)

then p in List

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

//將符合條件的特征點(diǎn)放入所屬的集合中

END

2 軌跡聚類

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

2.1 軌跡距離

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

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

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

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

f(tn)·(anMn)

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

2.2 軌跡聚類算法

輸入：Eps—半徑

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

D—集合。

輸出：目標(biāo)類簇集合

方法：Repeat

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

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

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

Repeat

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

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

2.3 聚類效果

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

圖2 簡(jiǎn)化后的軌跡圖

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

3 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)分析

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

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

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

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

4 結(jié) 語(yǔ)

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