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

鮑 世 方

(上海公安學院 上海 200137)

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

鮑 世 方

(上海公安學院 上海 200137)

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

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

0 引 言

隨著我國城鎮化進程的不斷加速，人口的流動造成社會治安環境日趨復雜，刑事案件發案率居高不下。其中“系列入室盜竊案的發案率一直居高不下且呈高發態勢[1]”，其多發性、連續性、跨區域流竄性對人民的生命財產安全構成極大的威脅，對社會的穩定發展造成了嚴重的影響[2]。

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

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

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

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

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

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

1 案件特征數據提取

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

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

(1) 數值特征

這些特征通常為實數或整數，比如案發位置坐標。

(2) 類別特征

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

(3) 文本特征

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

1.1 提取案發時間

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

(1) 按日期提取

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

(2) 按星期提取

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

(3) 按時段提取

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

1.2 提取案發地理坐標

根據報案時提供的案發地點的地址信息，通過地理坐標轉換工具，將文字描述的地址信息，轉換為地理坐標[10]。本文以百度地圖為例，具體實現步驟如下：

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

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

(3) 調用百度地圖API[11]，根據地址信息獲取地理坐標信息。

(4) 如果獲取到地理坐標信息，將地址信息和坐標信息關聯；如果未獲取到地里坐標信息，將地址信息最后一位截取掉，重新執行步驟3、步驟4。重復執行6次，如果還未關聯到坐標信息，跳出循環。

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

1.3 提取侵入方式

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

1.4 提取侵入部位

根據房屋的結構將案件侵入部位歸納為：門、陽臺、廚房、臥室、衛生間、地下室、天井、天臺，記為：[1,1,1,1,1,1,1,1]。根據各個案件情況，按提取的侵入部位將其標記為：

[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 提取作案手段

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

[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 提取案情關鍵詞

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

表1 入室盜竊案情關鍵詞提取

2 圖聚類算法

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

2.1 入室盜竊案件空間特征向量的構建

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

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

根據特征提取規則將案件特征值轉換為空間特征向量，見表3所示。

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

2.2 設定相似度加權計算模型

入室盜竊案件按不同特征的組合計算案件集合的相似度與案件特征數量為非線性相關，其相似度不一定隨案件特征數量的增多而提高。為了進一步提高案件相似度的精度，通過加入經驗值設定案件特征的權值進行加權計算來提高案件的相似度精度。

2.3 構建案件相似度矩陣

依據案件空間特征向量和案件特征的權值構建案件的相似度矩陣。設定案件a1和a2；案件的特征表示為f11-f18和f21-f28；案件特征的權值為q1-q8；案件a1和a2的特征相似度為fx1-fx8；則a1和a2的相似度為：

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

其中：

fx3=f13和f23中相等的個數/f13的長度

fx8=f18和f28中相等的個數/f18的長度

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

2.4 構造案件關系圖

根據案件的相似度矩陣利用Spark的MLlib工具包GraphX建立案件的無向圖[5]，見圖1所示。

圖1 案件的無向圖

2.5 圖分割算法

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

(1) 最小分割算法

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

(1)

對于規范的數據，利用最小分割算法進行分割的效果會比較好，而對于非規范的數據，利用最小分割算法會出現偏向最小分割的結果。

(2) 最小比率分割算法

(2)

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

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

(3)

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

(4) 最小最大分割算法

(4)

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

3 實驗結果及分析

3.1 實驗數據集

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

3.2 實驗環境

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

3.3 實驗評價標準指標

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

3.4 串并案模型驗證

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

表4 入室盜竊案件串并準確率對比

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

4 結 語

本文基于Spark分布式計算框架和圖聚類算法架構了用于偵破系列案件的串并案分析模型。從當前已發生個別案件開始，在公安海量數據中進行串并分析，根據圖聚類的結果，刻畫出犯罪團伙；在公安實戰工作中能夠對系列入室盜竊案件的偵破提供有效地支撐。在聚類過程中，特征值的選取當前主要依據警務專家的經驗值，在相關特征的提取方面也存在一定的難度，尚需要人工的參與。因此對于串并案自動分析模型的研究還面臨著一些挑戰，如何實現案件之間相似度的自動計算將是下一步研究的方向。

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

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

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

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

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

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

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

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

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

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

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

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

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

[14] 王會青,陳俊杰.基于圖劃分的譜聚類方法的研究[J].計算機工程與設計,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。鮑世方，講師，主研領域：公安信息系統研發，公安數據分析，公安信息化教學。