基于Spark/GraphX圖聚類算法的入室盜竊串并案研究

鮑 世 方

(上海公安學(xué)院 上海 200137)

基于Spark/GraphX圖聚類算法的入室盜竊串并案研究

鮑 世 方

(上海公安學(xué)院 上海 200137)

隨著我國城鎮(zhèn)化進(jìn)程的不斷加速，廣泛的人口流動使社會治安環(huán)境日趨復(fù)雜，犯罪分子系列性作案居高不下，給人民的生命財產(chǎn)安全構(gòu)成極大的威脅。針對刑事犯罪活動中日益突出的系列入室盜竊案件，提出采用圖聚類算法來進(jìn)行串并案分析。首先利用Spark/GraphX分布式圖計算框架，通過提取入室盜竊案的案件特征，計算兩兩案件之間的相似度，構(gòu)建案件相似度矩陣；然后依據(jù)圖論理論，采用圖聚類算法實現(xiàn)串并案分析模型。實戰(zhàn)工作表明該模型可為偵破案件提供有效的串并線索，極大地減少人工作業(yè)，提高了偵查工作的效率。

Spark GraphX 圖聚類算法 入室盜竊 串并案

0 引 言

隨著我國城鎮(zhèn)化進(jìn)程的不斷加速，人口的流動造成社會治安環(huán)境日趨復(fù)雜，刑事案件發(fā)案率居高不下。其中“系列入室盜竊案的發(fā)案率一直居高不下且呈高發(fā)態(tài)勢[1]”，其多發(fā)性、連續(xù)性、跨區(qū)域流竄性對人民的生命財產(chǎn)安全構(gòu)成極大的威脅，對社會的穩(wěn)定發(fā)展造成了嚴(yán)重的影響[2]。

犯罪分子的反偵查能力日益提高，犯罪分子作案時多戴手套、穿鞋套等以達(dá)到不留“痕跡”的目的，現(xiàn)場的指紋和腳印等具有標(biāo)識性的犯罪線索很可能被破壞，留下的案件線索有限，對傳統(tǒng)的經(jīng)驗型串并案分析[2]是極大的挑戰(zhàn)。傳統(tǒng)的經(jīng)驗型串并案分析根據(jù)單一的比較明確的特征屬性進(jìn)行數(shù)據(jù)碰撞搜索已不能滿足現(xiàn)實的需要，更不能很好地對抗職業(yè)犯罪和高科技犯罪。因此如何快速有效地從雜亂無章的案件信息中發(fā)現(xiàn)“蛛絲馬跡”，進(jìn)而實現(xiàn)串案并案偵查成為案件偵破工作中的重中之重。

串并案[2]是系列刑事案件偵破工作中的重要方法，在案件之間相互補充、相互舉證，特別是在個案偵查工作陷入困境時，更體現(xiàn)其有效性。但傳統(tǒng)的經(jīng)驗串并案是依據(jù)偵查人員的經(jīng)驗，進(jìn)行人工逐一排查，這種分析不但繁瑣，而且效率低下，偵查人員的經(jīng)驗直接影響串并案結(jié)果的準(zhǔn)確性。近年來一些專家利用數(shù)據(jù)挖掘技術(shù)進(jìn)行串并案的研究，推進(jìn)了數(shù)據(jù)挖掘技術(shù)在公安實戰(zhàn)中的應(yīng)用[3]。

圖聚類算法[4-5]是建立在圖論基礎(chǔ)上的聚類算法[6-8]，它根據(jù)分割函數(shù)，將圖分割為K個(K≥2)子圖，使得子圖內(nèi)部的關(guān)聯(lián)更緊密，子圖之間的關(guān)聯(lián)更稀松。文獻(xiàn)[7]提出一種基于Hash函數(shù)樣本抽樣的大規(guī)模數(shù)據(jù)聚類算法；文獻(xiàn)[5,8]提出的屬性圖聚類算法是一種圖聚類算法的特殊情況，是在圖聚類算法的基礎(chǔ)上考慮圖節(jié)點和邊的屬性的相似性進(jìn)行圖分割，其中文獻(xiàn)[5]在此基礎(chǔ)上提出一種加權(quán)屬性圖聚類。如何快速有效地通過分割函數(shù)進(jìn)行圖分割是目前研究的熱點和難點。

Spark[9]是UC Berkeley AMP lab所開源的類Hadoop MapReduce的通用的并行計算框架，Spark基于map reduce算法實現(xiàn)的分布式計算，擁有Hadoop MapReduce所具有的優(yōu)點；但不同于MapReduce的是Job中間輸出和結(jié)果可以保存在內(nèi)存中，從而不再需要讀寫HDFS，因此Spark能更好地適用于數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)等需要迭代的map reduce的算法。

GraphX[9]是一個分布式圖處理框架，基于Spark平臺提供對圖計算和圖挖掘簡潔易用的而豐富多彩的接口，是一個分布式的圖處理系統(tǒng)。

本文通過分析往年入室盜竊案件數(shù)據(jù)，提取案發(fā)時間、案發(fā)地理坐標(biāo)、侵入方式、作案手段、案情關(guān)鍵詞等犯罪行為特征數(shù)據(jù)，利用Spark/GraphX分布式圖計算框架，計算兩兩案件之間的相似度；依據(jù)圖論理論，將案件看成圖(G)中的頂點(V)，將案件之間的相似度看成圖(G)中的邊(E)，這樣就得到了一個基于案件相似度的圖；采用圖聚類算法實現(xiàn)串并案分析模型，給偵破案件提供更多線索和依據(jù)，提高偵查工作的效率，節(jié)省大量的人工串并案成本。

1 案件特征數(shù)據(jù)提取

本文研究的案件為入室盜竊案件，案件特征數(shù)據(jù)主要是案發(fā)時間、案發(fā)位置、侵入方式、侵入部位、作案手段、案情關(guān)鍵詞。其中侵入方式、侵入部位、作案手段和案情關(guān)鍵詞都反應(yīng)了犯罪嫌疑人的作案習(xí)慣，對串并案尤為重要。但這些數(shù)據(jù)都存儲在案情描述里面，本文研究通過文本分析實現(xiàn)案件特征數(shù)據(jù)的提取。

本文對案件特征數(shù)據(jù)提取采用Spark特征提取方法(利用Spark MLlib中的mllib.feature包)，將每個案件信息轉(zhuǎn)換為用向量表示的特征數(shù)值。特征(feature)是用于模型訓(xùn)練的變量，比較常用的有以下幾種：

(1) 數(shù)值特征

這些特征通常為實數(shù)或整數(shù)，比如案發(fā)位置坐標(biāo)。

(2) 類別特征

取值只能是可能集合中的某一種，借助k之1方法將其表示為長度為k的二元向量。比如案發(fā)時間、侵入方式、侵入部位、作案手段。k之1(1-of-k)方法是一種用于機(jī)器學(xué)習(xí)任務(wù)的特征變量表示方法。假設(shè)變量可取值有k個，如果對這些值用1到k進(jìn)行編序，則可以用長度為k的二元向量來表示一個變量的取值，這個向量里，該取值對應(yīng)的序號所在的元素為1，其他元素都為0。

(3) 文本特征

數(shù)據(jù)中的文本內(nèi)容，將文本內(nèi)容分詞，提取詞干，并用二元向量表示為稀疏矩陣的一種派生特征。比如案情關(guān)鍵詞。

1.1 提取案發(fā)時間

由于入室盜竊案件的特殊性，受害人報案時只能提供案發(fā)時間段，比如：2015年2月15日10點到2015年2月15日19點。我們從以下三個維度提取案件時間特征：

(1) 按日期提取

將時間段標(biāo)記為：[起始日期時間，截止日期時間]。本例中為[2015-02-15 10:00:00, 2015-02-15 19:00:00]，后期計算相似度是如果兩個時間段有交集標(biāo)記為1，否則標(biāo)記為0。

(2) 按星期提取

根據(jù)案發(fā)日期時間段獲取起始日期和結(jié)束日期，根據(jù)日期函數(shù)獲取日期對應(yīng)的星期，從而獲取案發(fā)日期時間段的星期范圍。經(jīng)過計算得知2015年2月15日為星期三，所以案發(fā)時間段的星期范圍為星期三；如果起始日期和結(jié)束日期不一致，星期范圍依次類推。為了便于計算我們將計算出的星期范圍用向量標(biāo)記，比如：星期三記為：[0，0，1，0，0，0，0]，將星期三、星期五記為：[0，0，1，0，1，0，0]。

(3) 按時段提取

根據(jù)案發(fā)日期時間段提取案發(fā)的時間段。本例中為[10，19]，如果起始時間點大于截止時間點，比如將[19，1]標(biāo)記為[19，24][0，1]。為了更準(zhǔn)確度提取時段的特征信息，我們將時間段劃分為凌晨(0-3)、黎明(3-6)、早上(6-9)、上午(9-12)、中午(12-14)、下午(14-17)、傍晚(17-20)、深夜(20-24)。例如：將[0，24]標(biāo)記為[1，1，1，1，1，1，1，1]，將[10，19]標(biāo)記為[0，0，0，1，1，1，1，0]，將[19，1]標(biāo)記為[1，0，0，0，0，0，1，1]。

1.2 提取案發(fā)地理坐標(biāo)

根據(jù)報案時提供的案發(fā)地點的地址信息，通過地理坐標(biāo)轉(zhuǎn)換工具，將文字描述的地址信息，轉(zhuǎn)換為地理坐標(biāo)[10]。本文以百度地圖為例，具體實現(xiàn)步驟如下：

(1) 獲取百度地圖授權(quán)[11]。

(2) 將案件信息分批次標(biāo)記，建立唯一鍵，便于分布式操作。

(3) 調(diào)用百度地圖API[11]，根據(jù)地址信息獲取地理坐標(biāo)信息。

(4) 如果獲取到地理坐標(biāo)信息，將地址信息和坐標(biāo)信息關(guān)聯(lián)；如果未獲取到地里坐標(biāo)信息，將地址信息最后一位截取掉，重新執(zhí)行步驟3、步驟4。重復(fù)執(zhí)行6次，如果還未關(guān)聯(lián)到坐標(biāo)信息，跳出循環(huán)。

(5) 最終獲取案件案發(fā)位置坐標(biāo)，形如：[121.232 3,31.322]。

1.3 提取侵入方式

入室盜竊案件由于其特殊性，往往在案發(fā)后才發(fā)現(xiàn)，無法準(zhǔn)確的獲取。本文研究通過分析案情描述將侵入方式可歸納為：從門侵入、從窗侵入、攀爬侵入、其他侵入，記為[1,1,1,1]。根據(jù)各個案件情況，按提取的侵入方式將其標(biāo)記為[1,0,0,0]、[0,1,0,0]、[0,0,1,0]、[0,0,0,1]。

1.4 提取侵入部位

根據(jù)房屋的結(jié)構(gòu)將案件侵入部位歸納為：門、陽臺、廚房、臥室、衛(wèi)生間、地下室、天井、天臺，記為：[1,1,1,1,1,1,1,1]。根據(jù)各個案件情況，按提取的侵入部位將其標(biāo)記為：

[1,0,0,0,0,0,0,0]、[0,1,0,0,0,0,0,0]、[0,0,1,0,0,0,0,0]、[0,0,0,1,0,0,0,0]、[0,0,0,0,1,0,0,0]、 [0,0,0,0,0,1,0,0]、[0,0,0,0,0,0,1,0] 、 [0,0,0,0,0,0,0,1]

1.5 提取作案手段

作案手段反應(yīng)嫌疑人的個人技能和作案習(xí)慣，特別是慣犯，即使有意隱藏，也難免留下獨特的作案痕跡。根據(jù)作案選擇的工具和個人技能，將作案手段歸納為：技術(shù)開鎖、撬鎖、倒插片、溜門、撬門、門挖洞、釣魚、攀爬、撬窗、破壞窗柵、破壞窗網(wǎng)、砸窗玻璃，記為：[1,1,1,1,1,1,1,1,1,1,1,1]。根據(jù)各個案件情況，按提取的作案手段將其標(biāo)記為：

[1,0,0,0,0,0,0,0,0,0,0,0]、[0,1,0,0,0,0,0,0,0,0,0,0]、[0,0,1,0,0,0,0,0,0,0,0,0]、[0,0,0,1,0,0,0,0,0,0,0,0]、[0,0,0,0,1,0,0,0,0,0,0,0]、[0,0,0,0,0,1,0,0,0,0,0,0]、[0,0,0,0,0,0,1,0,0,0,0,0]、[0,0,0,0,0,0,0,1,0,0,0,0]、[0,0,0,0,0,0,0,0,1,0,0,0]、[0,0,0,0,0,0,0,0,0,1,0,0]、[0,0,0,0,0,0,0,0,0,0,1,0]、[0,0,0,0,0,0,0,0,0,0,0,1]。

1.6 提取案情關(guān)鍵詞

通過分析案情描述信息來提取關(guān)鍵詞特征數(shù)據(jù)，本文通過漢語分詞系統(tǒng)NLPIR/ICTCLAS[12]開放的詞頻統(tǒng)計接口，統(tǒng)計案情描述的詞頻，形成案情關(guān)鍵詞組。比如對以下案情描述進(jìn)行詞頻統(tǒng)計，提取關(guān)鍵詞，見表1所示。

表1 入室盜竊案情關(guān)鍵詞提取

2 圖聚類算法

圖論是一個數(shù)學(xué)學(xué)科，研究一組實體(稱為頂點)之間兩兩關(guān)系(稱為邊)的特點。GraphX是基于Spark進(jìn)行并行圖計算的程序庫。本文基于圖論將每個案件看作圖的頂點，案件之間的相似度看作圖的邊而構(gòu)成無向圖，利用GraphX對圖分布式操作功能，對案件及其相似度構(gòu)成的無向圖進(jìn)行圖分割，使分割后的子圖內(nèi)部聯(lián)系更密切，子圖之間聯(lián)系更稀松，以達(dá)到案件串并的目的。

2.1 入室盜竊案件空間特征向量的構(gòu)建

案件特征提取的目的是將案件數(shù)據(jù)表示為多維空間特征向量，每行表示一起入室盜竊案件的空間向量，每一列表示入室盜竊案件的一個特征向量，見表2所示。

表2 入室盜竊案件特征多維空間特征向量表示

根據(jù)特征提取規(guī)則將案件特征值轉(zhuǎn)換為空間特征向量，見表3所示。

表3 入室盜竊案件特征值空間特征向量表示

2.2 設(shè)定相似度加權(quán)計算模型

入室盜竊案件按不同特征的組合計算案件集合的相似度與案件特征數(shù)量為非線性相關(guān)，其相似度不一定隨案件特征數(shù)量的增多而提高。為了進(jìn)一步提高案件相似度的精度，通過加入經(jīng)驗值設(shè)定案件特征的權(quán)值進(jìn)行加權(quán)計算來提高案件的相似度精度。

2.3 構(gòu)建案件相似度矩陣

依據(jù)案件空間特征向量和案件特征的權(quán)值構(gòu)建案件的相似度矩陣。設(shè)定案件a1和a2；案件的特征表示為f11-f18和f21-f28；案件特征的權(quán)值為q1-q8；案件a1和a2的特征相似度為fx1-fx8；則a1和a2的相似度為：

x12=∑ifxi×qii=1,2,…,8

其中：

fx3=f13和f23中相等的個數(shù)/f13的長度

fx8=f18和f28中相等的個數(shù)/f18的長度

依據(jù)上面的公式構(gòu)建案件的相似度矩陣，矩陣是n乘n的下三角矩陣，n代表案件的數(shù)量，具體的數(shù)值代表案件與案件之間的相似度。

2.4 構(gòu)造案件關(guān)系圖

根據(jù)案件的相似度矩陣?yán)肧park的MLlib工具包GraphX建立案件的無向圖[5]，見圖1所示。

圖1 案件的無向圖

2.5 圖分割算法

圖聚類算法就是依據(jù)圖的頂點間的相似度實現(xiàn)聚類算法，其思想就是使用圖論的知識，將樣本數(shù)據(jù)構(gòu)建成的圖進(jìn)行分割操作。圖分割的主要目的是使同組之間的權(quán)重最高[13]，而不同組別之間的權(quán)重盡可能的低的過程。權(quán)重越高，表示相似度越大，案件串并的可能性就越大，權(quán)重太低，表示相似度越小，案件串并的可能性就越小，放棄案件之間的串并[14]。假如將一個圖G劃分為A，B兩個子圖，其中|A|，|B|分別表示子圖 A，B中頂點的個數(shù)。圖分割算法[15-17]主要由以下幾種：

(1) 最小分割算法

Cut(A,B)=∑u∈A,v∈Bw(u,v)

(1)

對于規(guī)范的數(shù)據(jù)，利用最小分割算法進(jìn)行分割的效果會比較好，而對于非規(guī)范的數(shù)據(jù)，利用最小分割算法會出現(xiàn)偏向最小分割的結(jié)果。

(2) 最小比率分割算法

(2)

最小比率分割算法只考慮到如何使A，B兩個子圖間的相似性最小，這樣可以減少分割的次數(shù)。

(3) 最小規(guī)范化分割算法

(3)

將A，B兩個子圖的相似程度表示為Cut(A,B)，將A圖中所有點的權(quán)值之和表示為sumA，最小規(guī)范化分割算法不僅對規(guī)范化數(shù)據(jù)實用，對于非規(guī)范的數(shù)據(jù)也比較實用。

(4) 最小最大分割算法

(4)

最小最大分割算法即要求最小化A、B之間的相似性，同時最大化sum(A,A)與sum(B,B)，這樣即減少分割次數(shù)，又保證分割效果。

3 實驗結(jié)果及分析

3.1 實驗數(shù)據(jù)集

實驗數(shù)據(jù)集來自某市公安部門2015年案件信息和串并破案記錄，經(jīng)特征提取后進(jìn)行的實驗。

3.2 實驗環(huán)境

本文選取的硬件環(huán)境為通過虛擬技術(shù)虛擬出多臺配置相同的硬件。2 GB運行內(nèi)存，操作系統(tǒng)為CentOS7，Spark版本為2.2.0，Hadoop版本為2.8.0，編程語言Scala版本為2.12.2，JDK版本為1.8。

3.3 實驗評價標(biāo)準(zhǔn)指標(biāo)

影響案件串并模型的優(yōu)劣，一是案件特征的提取速度和案件相似度計算速度。二是串并案的準(zhǔn)確性。其中串并案的準(zhǔn)確性尤為重要，但是案件特征的提取速度和案件相似度計算速度也應(yīng)在可控范圍內(nèi)，否則無論串并案的準(zhǔn)確性再高也失去了實戰(zhàn)的意義。

3.4 串并案模型驗證

本文主要基于Spark分布式計算框架，來驗證不同切割函數(shù)的優(yōu)劣。非分布式的方法不在進(jìn)行實驗驗證，因為隨著數(shù)據(jù)量的增加，從理論上分析非分布式的方法的速度會越來越慢，直至不可控。而Spark分布式計算框架是基于內(nèi)存計算，減少大量的I/O操作，通過提高機(jī)器性能，可以將案件特征的提取速度和案件相似度計算速度控制在合理范圍內(nèi)，為實戰(zhàn)應(yīng)用打下堅實的基礎(chǔ)；通過完善分割函數(shù)，串并案模型的準(zhǔn)確性也會得到改善，表4為各種分割函數(shù)的效果對比，準(zhǔn)確率以實際串并破案為依據(jù)。

表4 入室盜竊案件串并準(zhǔn)確率對比

由表4可知，基于Spark/GraphX分布式圖計算框架下，利用最小最大分割函數(shù)進(jìn)行圖分割，無論從速度還是準(zhǔn)確率上對比，效果都最為明顯。實驗發(fā)現(xiàn)，根據(jù)最小最大分割比率，通過適當(dāng)減少案件之間的相似度比較的維度，速度和準(zhǔn)確率會有明顯提高，這對于實戰(zhàn)也是非常有用的。

4 結(jié) 語

本文基于Spark分布式計算框架和圖聚類算法架構(gòu)了用于偵破系列案件的串并案分析模型。從當(dāng)前已發(fā)生個別案件開始，在公安海量數(shù)據(jù)中進(jìn)行串并分析，根據(jù)圖聚類的結(jié)果，刻畫出犯罪團(tuán)伙；在公安實戰(zhàn)工作中能夠?qū)ο盗腥胧冶I竊案件的偵破提供有效地支撐。在聚類過程中，特征值的選取當(dāng)前主要依據(jù)警務(wù)專家的經(jīng)驗值，在相關(guān)特征的提取方面也存在一定的難度，尚需要人工的參與。因此對于串并案自動分析模型的研究還面臨著一些挑戰(zhàn)，如何實現(xiàn)案件之間相似度的自動計算將是下一步研究的方向。

[1] 劉東進(jìn),鄭旭強.利用刑事技術(shù)偵破入室盜竊系列案的幾點體會[J].廣東公安科技,2016,24(4):55-56.

[2] 韓寧,陳巍.基于聚類分析的串并案研究[J].中國人民公安大學(xué)學(xué)報(自然科學(xué)版),2012,18(1):53-58.

[3] 張超,張金波,伍坤.基于數(shù)據(jù)挖掘聚類方法識別串并多發(fā)性侵財案件平臺的設(shè)計與實現(xiàn)[J].警察技術(shù),2017(2):34-36.

[4] 陳德華,解維,李悅.面向大規(guī)模圖數(shù)據(jù)的分布式并行聚類算法研究[J].計算機(jī)研究與發(fā)展,2012(49):222-227.

[5] 張素智,張琳,曲旭凱.基于最短路徑的加權(quán)屬性圖聚類算法研究[J].計算機(jī)應(yīng)用與軟件,2016,33(11):212-214,281.

[6] 石鎧,任濼錕,彭一鳴,等.基于多節(jié)點社團(tuán)意識系統(tǒng)的屬性圖聚類算法[J].計算機(jī)科學(xué),2017,44(S1):433-437.

[7] 郭占元,林濤.面向大規(guī)模數(shù)據(jù)快速聚類K-means算法的研究[J].計算機(jī)應(yīng)用與軟件,2017,34(5):43-47,53.

[8] 邊宅安,李慧嘉,陳俊華,等.多智能體系構(gòu)架下的屬性圖分布式聚類算法[J].計算機(jī)科學(xué),2017,44(S1):407-413.

[9] 百度.Spark[EB/OL].http://baike.baidu.com/item/spark/.

[10] 王增利,劉學(xué)軍,陸娟.入室盜竊多尺度地理因子分析[J].地理學(xué)報,2017,72(2):329-340.

[11] 百度.百度地圖服務(wù)[EB/OL].http://lbsyun.baidu.com/.

[12] 張華平.NLP漢語分詞系統(tǒng)[EB/OL].http://ictclas.nlpir.org.

[13] 劉曉平,吳敏,金燦.采用圖分解的特征識別算法研究[J].圖學(xué)學(xué)報,2010,31(1):67-71.

[14] 王會青,陳俊杰.基于圖劃分的譜聚類方法的研究[J].計算機(jī)工程與設(shè)計,2011,32(1):289-292.

[15] Ulrike von Luxburg.A Tutorial on Spectral Clustering[EB/OL].http://www.kyb.mpg.de.

[16] Bach F R,Jordan M I.Learning Spectral Clustering[J].Advances in Neural Information Processing Systems,2003,16(2):2006.

[17] Aarti Singh.Spectral Clustering[EB/OL].https://www.cs.cmu.edu.

RESEARCHOFBUNCHINGANDMERGINGBURGLARYCASEBASEDONSPARK/GRAPHXGRAPHCLUSTERINGALGORITHM

Bao Shifang

(ShanghaiPoliceCollege,Shanghai200137,China)

With the acceleration of the urbanization process in our country, the extensive population flow makes the public security environment become more and more complex, and the serial crimes of criminals are still high, which poses a great threat to the people’s lives and property safety. In this paper, in view of the increasingly prominent series of burglaries in criminal activities, a graph clustering algorithm is proposed to perform the parallel case analysis. First of all, we used the Spark/GraphX distributed computing framework to extract the case characteristics of burglaries, calculated the similarity between cases, and built the case similarity matrix. Then, according to the graph theory, the graph clustering algorithm was used to implement the parallel case analysis model. The actual combat work shows that the model can provide effective string and clue for detecting cases, greatly reduce manual operation and improve the efficiency of the investigation.

Spark GraphX Graph clustering algorithm Burglary Bunching and merging case

TP3

A

10.3969/j.issn.1000-386x.2017.09.022

2017-07-26。鮑世方，講師，主研領(lǐng)域：公安信息系統(tǒng)研發(fā)，公安數(shù)據(jù)分析，公安信息化教學(xué)。