一種基于Spark/DBSCAN算法的城市公交扒竊行為分析方法

馮佳樂 王占宏 陳德華

摘 要： 隨著中國城鎮化進程的不斷加速，城市公交扒竊行為給公民的生命財產安全構成極大的威脅，對社會風氣造成了持續性的影響。研究中基于“犯罪行為是行為人主觀意識對客觀環境的反致行為”[1]這一理論，采用NLPIR漢語分詞系統，整理以往城市公交扒竊行為數據，提取犯罪行為時間、位置數據，在Spark分布式計算框架下，利用DBSCAN算法做地理位置數據的聚類分析，發現造成犯罪反致行為[1]的客觀環境和規律。通過改善客觀環境，進而提高預防和控制犯罪行為的水平。

關鍵詞： 中文分詞；Spark；DBSCAN；公交扒竊

Abstract：With the acceleration of China's urbanization process the city bus theft poses a great threat to people's lives and property resulting in a sustained effect on social climate. Based on "crime is the revoni behavior of subjective consciousness and the objective environment" [1]theory using NLPIR Chinese word segmentation system organizing the past city bus theft data extracting time and position data of criminal behavior in the framework of Spark distributed computing DBSCAN algorithm is used to realize the clustering analysis of geographical location data therefore discover the objective environment caused by criminal behavior and law of renvoi. By improving the objective environment the level of preventing and controlling criminal behavior could be improved.

Key words： NLPIR；Spark；DBSCAN；bus theft

引言

隨著中國城鎮化進程的不斷加速，城市公共交通也得到了大力發展，造成其載客量大、流動性強等特點，給人們帶來便利的同時，也為違法行為創造了現實可能，同時還將給人們的生命財產安全構成一定威脅。而且因其突出的流動性所導致，偵查工作也隨即增加了告破難度，這也會給現代社會的有序發展制造了潛在隱患和不和諧因素。針對這一問題，關于城市公交扒竊犯罪行為的分析研究則具有重要的現實意義。

城市公交扒竊[2]犯罪是指以非法占有為目的，在城市公共交通工具上或公交乘車、候車場所，乘被害人不備之機，通過采用手掏、劃包、夾取、剪取等秘密手段竊取他人隨身攜帶財物的犯罪行為。

1 開發技術研究解析

NLPIR[3]是由張華平博士主持研發的漢語分詞系統，重點包括了中文分詞、詞性標注、命名實體識別、用戶詞典功能、關鍵詞提取等功能。

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

DBSCAN[5]（Density-Based Spatial Clustering of Applications with Noise）作為基于密度算法的經典代表，在聚類分析中得到越來越多的應用。與劃分和層次聚類方法不同，DBSCAN可將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區域劃分為簇，并可在噪聲的空間數據庫中發現任意形狀的聚類。但是DBSCAN算法在處理數據時，需要多次重復掃描。在進行海量數據聚類時，DBSCAN算法會消耗大量的內存和I/O開銷[6]。另外，DBSCAN算法在計算時需要用戶提供2個全局參數，即鄰域半徑和鄰域內包含對象的個數，這些參數對聚類結果很敏感，由于用戶難以確定參數，就需要不斷地更新嘗試，這對性能也將構成嚴峻挑戰。文獻[7]也進一步提出了改進的DBSCAN算法。文獻[8-9]又研發了基于云計算和Hadoop平臺的DBSCAN算法。

綜上分析可知，如果研究采用基于Spark分布式計算框架就可以有效解決DBSCAN算法的缺陷。Spark是基于內存的分布式計算框架，在DBSCAN算法計算中可以大幅減少I/O開銷和內存開銷；而且由于其分布式計算的特點，程序可以同時計算多個參數組合，比較聚類效果的優劣，用戶不再需要確定參數就可以獲得理想的聚類效果。

基于此，在本文中，研究采用了NLPIR漢語分詞系統，結合政務公開數據和地圖服務，匯總整理以往城市公交扒竊行為數據，提取犯罪行為時間、位置數據，利用Spark分布式計算的優勢，基于DBSCAN做出地理位置數據的聚類分析，發現造成犯罪反致行為的客觀環境和規律，增強防扒意識，減少人民的財產損失。

2 城市公交扒竊行為數據整理

本文研究的數據主要是犯罪時間和犯罪位置。根據具體情況，犯罪時間、犯罪位置都沒有對應指定的特征數據，就需要通過處理分析公交扒竊案情描述信息來提取特征數據。案情描述示例則可見表1。為此，即采用張華平博士主持研發的漢語分詞系統來展開特征數據提取研究。其中，犯罪位置數據就是通過辨識得出描述中的站點名稱和線路名稱，再借助公交線路查詢服務，最終獲取犯罪位置數據。

2.1 提取公交線路信息

公交線路是城市公交扒竊案中的基礎重要數據，提取的公交線路數據的準確性就決定了整個分析過程的可靠性。而利用政務公開數據（城市公交線路）就可優化所提取公交線路的準確性。過程中，設計提取步驟如下：

（1）基于完全匹配的規則?；谕耆ヅ涞囊巹t，從案情描述中提取、且記錄公交線路信息，并標記案件信息。

（2）基于同音匹配規則。對于步驟（1）沒有匹配到公交線路的案件信息，基于同音匹配規則，重新提取、且記錄公交線路信息，并標記案件信息。

（3）手工提取公交線路。對于步驟（1）、（2）沒有匹配到公交線路的案件信息，進行手工提取，記錄提取到公交線路信息，并標記案件信息。如果還未提取到公交線路數據，可以考慮舍棄案件數據。

2015年8月25日14時30分左右，報警人于涼城新村乘上758路公交車，其于14時55分左右行駛至政立路武川路下車時發現其衣服左側口袋被割破，隨身攜帶的身份證以及800元現金被盜，故來所報案。

2.2 提取犯罪時間數據

由于時間的特殊性，可以利用正則表達式從城市公交扒竊案情描述信息中提取到犯罪時間數據。根據提取到的犯罪時間數據，即可得知案發日期、案發星期、案發月份、案發季節等，進而利用政務公開數據（天氣），獲取案發當日的天氣情況。

2.3 提取犯罪位置數據

2.3.1 根據公交線路獲取公交站點信息

依據提取到的公交線路信息，利用公交線路查詢服務獲取公交線路的所有公交站點數據和地理坐標數據。以高德地圖服務[10]為例，研發可得設計代碼如下：

function lineSearch（lineName） {

AMap.plugin（[AMap.LineSearch]，function（）{

var linesearch = new AMap.LineSearch（{

pageIndex： 1 city： 上海，

pageSize： 1 extensions： all

}）；

line.search（lineName， function（st rt） {

if （rs == complete && rt.info == OK） {

var lineArr =rt.lineInfo；

var lineNum = rt.lineInfo.length；

if （lineNum > 0） {

for （var i = 0；i < lineNum；i++） {

//公交線路路線（坐標數據）

var pathArr = lineArr[i].path；

//所有的站點的坐標和站點名稱

var sts= lineArr[i].via_stops；

var len = sts.length；

var stPot =sts[0].location；

var ePot = sts[len - 1].location；

}

}

}

}）；

}）；}

2.3.2 提取上下車站點數據

將2.3.1節中獲取的站點信息作為字典信息，與公交扒竊案情描述信息進行比對，并依據“上車”、“下車”等特殊標記獲取上、下車站點名稱及坐標信息。如果未獲取到上車站點信息的，將公交線路的起點作為上車站點信息；如果未獲取到下車站點信息，將公交線路的終點作為下車站點信息。根據獲取的上、下車站點信息與公交線路站點信息進行比對，將上、下車站點之間的公交站點作為案發的途經站點信息。上、下車站點信息和途經站點信息即為公交扒竊案的案發地理位置信息。

3 城市公交扒竊行為分析

城市公交扒竊行為是一種“靜態”和“動態”的犯罪行為的綜合體，由于作案時間和作案地點都不確定，所以其犯罪行為可能發生在上、下車站點（靜態）和途經站點（動態）。本文通過提取公交站點的地理位置信息獲取案發地理位置信息，利用Spark分布式計算框架，以案發位置信息為研究內容，基于DBSCAN算法進行地理位置數據的聚類分析，從而發現公交扒竊行為的客觀因素及行為規律。

以某市公交扒竊報案數據為研究對象，通過DBSCAN算法偽代碼描述分析過程。定義集合XYMap用于存放聚類結果，設研究半徑為R，研究可得分析過程表述如下：

步驟1 給發生扒竊的公交線段編號排序，得到新的公交線段集合A。

步驟2 依次獲取公交線段A_i及A_i包含的公交站點集合A_i.List。

步驟3 依次從A_i.List中獲取相鄰的2個公交站點（a，b）。

步驟4 獲取公交線段A_（i+j）及包含的公交站點集合A_（i+j）.List。（j從1開始，i+j<=A.count）。

步驟5 依次從A_（i+j）.List獲取相鄰的2個公交站點（c，d）

步驟6 計算a，b，c，d的交點e，如果交點e在（a，b）線段上，則將交點e存入集合XYMap中，并將A_i和A_（i+j）標記為visited；否則計算（a，b）的中點和（c，d）的中點的距離R_i，如果R_i<=R，則將（a，b）的中點和（c，d）的中點的中點存入集合XYMap中，并將A_i和A_（i+j）標記為visited；

否則跳過。

步驟7 重復步驟5～6，直到d為A_（i+j）.List中的最后一個站點。

步驟8 重復步驟4～7，直到i+j>A.count。

步驟9 重復步驟3～8，直到b為A_i.List中的最后一個站點。

步驟10 重復步驟2～9，直到Ai為A中的最后一個公交線段。

步驟11 獲取所有未被標記為visited的公交線段集合，通過迭代計算相鄰點的中點，計算出公交線段的中點，存入集合XYMap中。

步驟12 返回集合XYMap，并在地圖中繪制及展示結果。

算法運行后的聚類效果如圖1所示。從地圖展示效果分析，案件呈現以多種不規則形狀，一般集中在地鐵、車站、醫院、學校、商業區附近，這一結果與文獻[2]中的結論一致，這也同時驗證了城市公交扒竊往往發生在人群集中、經濟繁榮的地方。

DBSCAN算法以地理位置信息進行聚類，以案件的聚類結果將案件標記為“地鐵”案件、“車站”案件、“醫院”案件、“學?！卑讣ⅰ吧虡I街”案件，分別對案件按時間運行統計，具體結果可見表2。

4 結束語

城市公交扒竊行為就是指在公共場合趁人不備，采取秘密的方式竊取他人財物的做法，發生在公共交通工具內及候車點附近，比如人群集中的商業區、經營或運行規律的學校和醫院以及承載交通連接的公共交通站點附近，案發時間與區域的經營時間、以及人們的行為習慣有關。

本文設計提出了一種城市公交扒竊行為分析的方法，期待能夠開創城市公交扒竊行為有效防治新局面。通過城市公交扒竊行為的結果分析表明：城市公交扒竊的發生與客觀環境有關，即由偷盜者主觀判斷客觀環境利于扒竊才會付諸行動?；谶@一理論，通過提高人民的警惕性和增強公共交通站點的安全措施就可有效減少城市公交扒竊行為的發生。

參考文獻

[1] 閆冬. 淺談犯罪行為產生的原因[J]. 黑龍江科技信息 2010 （13）： 181.

[2] 任光宇. 城市公交扒竊犯罪防治研究[D]. 長沙：湖南大學 2008.

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

[4] 百度. Spark[EB/OL]. http：//baike.baidu.com/item/SPARK/.

[5] BORDOGNA G LENCO D. Fuzzy core DBScan clustering algorithm[M]//LAURENT A STRAUSS O BOUCHON-MEUNIER B et al. Information Processing and Management of Uncertainty in KnowledgeBased Systems. IPMU 2014. Communications in Computer and Information Science. Cham：Springer International Publishing 2014： 100-109.

[6] 李杰 賈瑞玉 張璐璐. 一個改進的基于DBSCAN的空間聚類算法研究[J]. 計算機技術與發展 2007 17（1）： 114-116.

[7] 羅啟福. 基于云計算的DBSCAN算法研究[D]. 武漢：武漢理工大學 2013.

[8] 王雅光. 基于Hadoop平臺的DBSCAN算法應用研究[D]. 廣州：廣東工業大學 2013.

[9] GHANBARPOUR A MINAEI B. EXDBSCAN：An extension of DBSCAN to detect clusters in multi-density datasets[C]//2014 Iranian Conference on Intelligent Systems（ICIS）. Bam，Iran：IEEE 2014： 1-5.

[10]高德. 高德地圖服務[EB/OL]. [2012]. http：//lbs.amap.com/.