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

馮佳樂 王占宏 陳德華

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

關(guān)鍵詞： 中文分詞；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

引言

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

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

1 開發(fā)技術(shù)研究解析

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

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

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

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

基于此，在本文中，研究采用了NLPIR漢語分詞系統(tǒng)，結(jié)合政務(wù)公開數(shù)據(jù)和地圖服務(wù)，匯總整理以往城市公交扒竊行為數(shù)據(jù)，提取犯罪行為時間、位置數(shù)據(jù)，利用Spark分布式計算的優(yōu)勢，基于DBSCAN做出地理位置數(shù)據(jù)的聚類分析，發(fā)現(xiàn)造成犯罪反致行為的客觀環(huán)境和規(guī)律，增強防扒意識，減少人民的財產(chǎn)損失。

2 城市公交扒竊行為數(shù)據(jù)整理

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

2.1 提取公交線路信息

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

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

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

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

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

2.2 提取犯罪時間數(shù)據(jù)

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

2.3 提取犯罪位置數(shù)據(jù)

2.3.1 根據(jù)公交線路獲取公交站點信息

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

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++） {

//公交線路路線（坐標數(shù)據(jù)）

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 提取上下車站點數(shù)據(jù)

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

3 城市公交扒竊行為分析

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

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

步驟1 給發(fā)生扒竊的公交線段編號排序，得到新的公交線段集合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 重復(fù)步驟5～6，直到d為A_（i+j）.List中的最后一個站點。

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

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

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

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

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

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

DBSCAN算法以地理位置信息進行聚類，以案件的聚類結(jié)果將案件標記為“地鐵”案件、“車站”案件、“醫(yī)院”案件、“學(xué)校”案件、“商業(yè)街”案件，分別對案件按時間運行統(tǒng)計，具體結(jié)果可見表2。

4 結(jié)束語

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

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

參考文獻

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

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

[3] 張華平. NLP漢語分詞系統(tǒng)[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]. 計算機技術(shù)與發(fā)展 2007 17（1）： 114-116.

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

[8] 王雅光. 基于Hadoop平臺的DBSCAN算法應(yīng)用研究[D]. 廣州：廣東工業(yè)大學(xué) 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]高德. 高德地圖服務(wù)[EB/OL]. [2012]. http：//lbs.amap.com/.