閆密巧,過仲陽,任浙豪

(華東師范大學地理科學學院,上海200241)

基于聚類關聯(lián)規(guī)則的公交扒竊犯罪時空分析

閆密巧,過仲陽,任浙豪

(華東師范大學地理科學學院,上海200241)

提出了一種基于聚類的時空關聯(lián)規(guī)則的公交犯罪挖掘算法.針對某市一個區(qū)的110報警數(shù)據(jù)庫中的大量業(yè)務信息進行分析.首先,通過文本挖掘技術從案情信息中提取時間、地點等信息,并利用高德地圖API的地理編碼服務和POI搜索功能對提取的地址信息進行地址匹配,提取受害人上下車站點、乘坐公交線路等信息.其次,對提取得到的時空數(shù)據(jù)進行歸并處理.最后,根據(jù)案發(fā)時段、季節(jié)以及是否節(jié)假日進行聚類分析,然后在簇內(nèi)進行時空關聯(lián)規(guī)則分析.這種挖掘方法具有以下特點：①在聚類基礎上進行關聯(lián)規(guī)則分析,減少掃描數(shù)據(jù)庫次數(shù),大大縮小數(shù)據(jù)掃描范圍,提高算法效率,更加適合海量犯罪數(shù)據(jù)的挖掘.②聚類后簇內(nèi)數(shù)據(jù)具有相似性,特征更加明顯,在此基礎上進行關聯(lián)規(guī)則分析產(chǎn)生較小的頻繁項集,并且提取出置信度較高的規(guī)則.③考慮犯罪行為的時空特性,挖掘過程中同時考慮了案發(fā)季節(jié)、是否節(jié)假日等因素.

公交扒竊;聚類分析;關聯(lián)規(guī)則;犯罪模式識別

0 引言

隨著城市公共交通迅猛發(fā)展,客流量明顯增多,這也給犯罪分子進行扒竊犯罪提供了便利.公交扒竊已成為影響公共秩序和危害人們出行安全的熱點問題.由于公交扒竊犯罪的動態(tài)特征,受害人往往不能確定被扒的時間、地點等,這給公安機關偵破案件以及打擊犯罪增加了難度.在國外,對于公共交通犯罪行為的研究主要集中在暴力犯罪、破壞公共設施等方面.根據(jù)發(fā)生時的狀態(tài)可以分為兩種,即在站點候車時發(fā)生的和在移動的車輛上發(fā)生的.例如Herrmann對紐約市扒竊犯罪行為進行時空熱點分布研究,結果發(fā)現(xiàn)扒竊犯罪熱點分布在地鐵站周圍,并且白天(下午15∶00高峰期)多分布在學校周圍,夜里(凌晨1∶00左右)多分布于企業(yè)周圍[1].而對發(fā)生在移動車輛上的犯罪行為的研究較少,Netown對公交犯罪行為的時間和地點分別進行過統(tǒng)計,分析得出那些穿越高犯罪率區(qū)域的公交路線比其他路線更易發(fā)生扒竊,并且在高犯罪率的區(qū)域的?？空军c越多的線路越容易發(fā)生扒竊[2].Newton提出將公交犯罪行為分為“靜態(tài)犯罪”和“非靜態(tài)(線性)犯罪”,并指出研究的重點和難點是如何分析非靜態(tài)(線性)犯罪事件[3].在國內(nèi),針對公交扒竊犯罪的研究非常少,主要集中在公交扒竊犯罪的預防機制、治理對策和案件的定性量刑方面[4-7].目前的研究大多使用統(tǒng)計分析方法對案件數(shù)量、作案人員的特征等做簡單統(tǒng)計,使用數(shù)據(jù)挖掘方法對公交扒竊犯罪進行研究的還較少.并且對公交扒竊犯罪的研究往往將時間和空間割裂開來,忽略了其時空特性.現(xiàn)有研究主要是基于經(jīng)驗的總結,例如分析作案手段、作案團伙活動范圍等,缺乏定量的分析研究.本文同時結合了時間和空間特性,利用基于聚類的關聯(lián)規(guī)則對公交扒竊犯罪行為進行分析.

在進行案件分析的時候,若是單純進行聚類,僅僅以相似的案件為依據(jù)來提取犯罪行為規(guī)律,雖然可以提取覆蓋范圍較大的時空規(guī)律,但是它的準確率不高.而對于Apriori算法,它并沒有將相似的犯罪行為聚類,而是提取頻繁出現(xiàn)的項集作為規(guī)則產(chǎn)生的依據(jù),因此往往它得出的犯罪時空規(guī)律準確率比較理想,但是覆蓋率不夠.基于聚類的時空關聯(lián)規(guī)則,通過綜合應用這兩種算法尋求一種平衡,旨在得到準確率和覆蓋率都較高的犯罪時空規(guī)律.

另外,110接報數(shù)據(jù)庫數(shù)據(jù)量大,若采用傳統(tǒng)的關聯(lián)規(guī)則算法,需要多次掃描數(shù)據(jù)庫,產(chǎn)生大量候選項集,挖掘效率低下.基于聚類的時空關聯(lián)規(guī)則算法,首先將公交扒竊時空數(shù)據(jù)聚為若干簇,然后在簇內(nèi)進行關聯(lián)規(guī)則分析.可縮小數(shù)據(jù)掃描范圍,減少掃描數(shù)據(jù)庫的時間,提高算法效率,更適合數(shù)據(jù)量大的犯罪數(shù)據(jù)挖掘.

1 基于聚類的時空關聯(lián)規(guī)則挖掘

1.1 時空關聯(lián)規(guī)則

關聯(lián)規(guī)則由Agrawal等人在1993年提出[8].關聯(lián)規(guī)則是形如A?B的蘊含式,規(guī)則A?B在事務集D中成立,具有支持度s和置信度c.其中s是事務集D中A和B同時出現(xiàn)的概率,它是概率P(A∪B).c是事務集D中A出現(xiàn)的情況下,B出現(xiàn)的概率,這是條件概率P(A|B).即∶

空間數(shù)據(jù)都是時間的函數(shù),在一些事務和現(xiàn)象中存在時間和空間的相關關系[10].在實際研究和應用中,人們對于時間和空間之間的關系更加感興趣,從而促使時空關聯(lián)規(guī)則的出現(xiàn).時空關聯(lián)規(guī)則算法就是從既有時間屬性又有空間屬性的事物表中提取頻繁項集和關聯(lián)規(guī)則的方法.

目前時空關聯(lián)規(guī)則主要應用在交通、物流、土地資源、環(huán)境等領域[11-15],主要存在兩方面問題,一方面是處理海量數(shù)據(jù)時算法效率問題,另一方面是時空謂詞的表述、提取問題.本文采用基于聚類的關聯(lián)規(guī)則,有效縮小關聯(lián)規(guī)則算法中數(shù)據(jù)掃描范圍,提高算法效率.在時空謂詞的提取上,結合文本分詞、地圖服務API及地理編碼等更高效精準的提取時空謂詞.

1.2 基于聚類的時空關聯(lián)規(guī)則

聚類分析和關聯(lián)規(guī)則都是數(shù)據(jù)挖掘中的經(jīng)典方法.關聯(lián)規(guī)則旨在找出給定數(shù)據(jù)集中各項之間有趣的聯(lián)系.聚類就是將數(shù)據(jù)對象分組成多個簇.同一個簇中的對象彼此相似,與其他簇中的對象相異.聚類分析的應用之一就是做數(shù)據(jù)預處理,通過聚類分析得到若干簇,簇內(nèi)對象相似性較高,在簇內(nèi)提取關聯(lián)規(guī)則針對性更強、更加集中而且效率更高.所以基于聚類的關聯(lián)規(guī)則也是十分重要的研究方向.

關聯(lián)規(guī)則挖掘是一個兩步的過程,首先找出所有頻繁項集,然后由滿足最小支持度和最小置信度的頻繁項集產(chǎn)生強規(guī)則.Apriori算法是一種最有影響的挖掘頻繁項集的算法.但Apriori算法的不足之處是可能產(chǎn)生大量候選項集,并且需要多次掃描數(shù)據(jù)庫,通過模式匹配檢查一個很大的候選項集.對海量犯罪數(shù)據(jù)挖掘尤其如此.基于聚類的關聯(lián)規(guī)則的基本思想是首先將數(shù)據(jù)集聚類為k個簇,在各個簇內(nèi)進行關聯(lián)規(guī)則分析.相比Apriori算法,基于聚類的關聯(lián)規(guī)則算法只需掃描一次數(shù)據(jù)庫,生成M張聚類表,在聚類表內(nèi)進行關聯(lián)規(guī)則分析要比直接在110接報信息數(shù)據(jù)庫中簡單得多,大大縮小了數(shù)據(jù)掃描范圍,減少數(shù)據(jù)掃描時間,降低開銷,提高挖掘效率[16].其基本流程如圖1所示.

圖1 基于聚類的關聯(lián)規(guī)則算法流程Fig.1 The flow chart of association rules based on clustering

目前基于聚類的關聯(lián)規(guī)則的研究主要將聚類分析作為數(shù)據(jù)預處理步驟,經(jīng)過聚類達到數(shù)據(jù)降維、篩選孤立點等目的[17-22].在犯罪領域,還沒有應用基于聚類的時空關聯(lián)規(guī)則對具有“動態(tài)犯罪”特征的公交扒竊案件進行分析的研究.本文通過綜合應用聚類分析和時空關聯(lián)規(guī)則這兩種算法,旨在提高公交扒竊犯罪時空規(guī)則的支持度和置信度.

2 公交扒竊犯罪模式識別

2.1 公交扒竊犯罪模式挖掘流程

本文以某市的一個區(qū)2015年全年的110接報案數(shù)據(jù)為基礎,選擇公交扒竊案件為研究對象,利用文本挖掘技術從簡要案情描述文本中提取時空信息,并按照一定規(guī)則對時空數(shù)據(jù)進行歸并,將數(shù)據(jù)結構化,得到公交扒竊案件時空數(shù)據(jù)表.首先,采用K-Means聚類分析算法,根據(jù)案發(fā)時段、季節(jié)以及是否節(jié)假日進行聚類.然后,對得到的各個簇,進行關聯(lián)規(guī)則分析.公交扒竊案的挖掘流程如圖2所示.

圖2 公交扒竊犯罪模式挖掘流程Fig.2 Crime pattern recognition of bus pickpocket

(1)時空信息提取

數(shù)據(jù)處理流程包括文本提取和數(shù)據(jù)歸并兩部分.首先,根據(jù)案件數(shù)據(jù)庫中的簡要案情描述信息,利用文本信息提取技術并結合高德地圖JavaScriptAPI提取受害人乘車時間、上下車站點等信息.利用開源的中文分詞工具對案情描述文本進行分詞和詞性標注,設計相應的分詞詞典,將公交站點名稱加入分詞詞典中.利用規(guī)則匹配的方法從分詞結果中提取出上下車站點名和上車時間,如表1所示.

表1 公交扒竊案情描述文本分詞及信息提取結果Tab.2 Text segmentation and information extraction of the bus pick pocketing case

(2)信息歸并

本文對提取得到的時空數(shù)據(jù)進行歸并.空間數(shù)據(jù)包括受害人上下車站點及途經(jīng)站點,以相鄰站點將受害人途經(jīng)站點劃分為公交路段.為了研究方便,約定對于只提取出一個公交站點的,用該站與下一站組成的公交路段表示.

對于時間數(shù)據(jù),考慮到一位乘客乘坐公交車時間一般不超過2 h,且公交扒竊案件多發(fā)生在5∶00—23∶00時間段內(nèi),因此文本將5∶00—23∶00按2 h為間隔劃分為9個公交時段,23∶00至第二天5∶00作為單獨的一個公交時段.然后對提取的案發(fā)時間進行歸約,根據(jù)從文本提取出的時間和公交車在某兩站之間運行的時間確定案發(fā)時段.得到的大部分案發(fā)時段完全落入公交時段內(nèi)的,直接用該公交時段表示.對于案發(fā)時段介于兩個公交時段之間的,案發(fā)時段落入哪個公交時段的比例更大,則以該公交時段表示.特別的,對于星期的劃分考慮重要節(jié)假日,將假期前一天定為周五,假期第一天定為周六,后續(xù)假期均定為周日,調休日定為周一.經(jīng)過數(shù)據(jù)處理后,提取出5 394條完整記錄作為分析數(shù)據(jù),公交扒竊案件時空數(shù)據(jù)結構如表2所示.

表2 公交扒竊案件時空數(shù)據(jù)表Tab.2spatio-temporal data table of bus pickpocket case

(3)案件信息挖掘

公交扒竊案件具有“動態(tài)犯罪”的特征,實際案發(fā)位置是不確定的,根據(jù)案情描述文本提取的案發(fā)公交路段只是可能的案發(fā)位置.因此應考慮各公交路段的案發(fā)率,由此區(qū)分各公交路段的重要程度.葉文菁等提出一種公交扒竊案件中各公交路段權重的計算方法[15,23],用每個案件中涉及的公交路段數(shù)的倒數(shù)作為公交路段的權重.例如,某人從公交站點A到站點C之間發(fā)現(xiàn)被扒,提取的案發(fā)公交路段為AB、BC,運用關聯(lián)規(guī)則分析時對AB、BC路段分別作一次統(tǒng)計,理解為在AB段發(fā)生了一次扒竊,BC段也發(fā)生一次扒竊,顯然不合實際.若考慮各路段的案發(fā)概率,則此案件發(fā)生在AB段和BC段的概率都為0.5,可以理解為在AB段發(fā)生了0.5次扒竊, BC段發(fā)生0.5次扒竊,這樣更符合實際.設某公交路段的權重為Wi,第i條案件記錄中涉及的公交路段個數(shù)為k,則第i條案件記錄中各個公交路段的權重即為

公交扒竊案件數(shù)據(jù)中的空間屬性用X表示,Xim表示第i條案件記錄中某一公交段,用Y表示時間屬性,Yi表示第i條案件記錄中的案發(fā)時段,加權支持度和加權置信度計算方法如公式(4)—(7)所示[23].

其中,Wi為各公交路段的權重.特別的,第i條記錄的時間權重Wj=1.

使用Apriori算法提取頻繁項集需要滿足Apriori算法向下封閉性,即頻繁項集的所有非空子集都必須是頻繁的.設{Xim,Yj}為頻繁項集,由Count(Xim)＞Count(Xim∪Yj)且Wj=1,可得WSupport(Xim)＞W(wǎng)Support(Xim∪Yj)＞Supportmin,即{Xim}也是頻繁的.同理{Yj}也為頻繁項集.所以,對于公交扒竊案件進行加權關聯(lián)規(guī)則分析滿足Apriori算法向下封閉性,可使用Apriori算法進行連接和剪枝.

2.2 實驗結果與分析

對5 439條記錄根據(jù)案發(fā)季節(jié)、時段和星期進行K-Means聚類得到4張聚類表,其結構如表3所示.然后,分別對各聚類表作關聯(lián)規(guī)則分析,首先,設定最小支持度0.1%,最小置信度50%,對4個聚類表進行挖掘.然后分別對每個聚類表挖掘的結果進行排序,先按支持度排序,再按照置信度排序,選取兩次排位都在前5的項集,對4個聚類表得到的共20個項集綜合排序,選取排位前7的強規(guī)則,由此確定加權支持度和加權置信度的實際的閾值分別為0.19%和66.67%.結果如表4所示.

表3 聚類表1Tab.3 Cluster table 1

表4 基于聚類的時空關聯(lián)規(guī)則提取的強規(guī)則Tab.4 Efficient rules for spatio-temporal association rules based on clustering

本文同時對5 439條記錄在不經(jīng)過聚類的情況下,直接應用基于Apriori算法的關聯(lián)規(guī)則對所有犯罪記錄進行分析,以此對比兩種分析方法的效率.設定最小支持度0.1%,最小置信度50%.對挖掘結果進行排序,取前7條記錄,由此確定加權支持度和加權置信度的實際的閾值分別為0.1%和53.33%.結果如表5所示.

表5 關聯(lián)規(guī)則分析提取的強規(guī)則Tab.5 Efficient rules for spatio-temporal association rules

對比表4和表5可知,經(jīng)過聚類后在簇內(nèi)進行關聯(lián)規(guī)則分析可提取出置信度更高的規(guī)則.同時,在未經(jīng)過聚類分析而直接應用關聯(lián)規(guī)則分析提取出的強規(guī)則中犯罪時段集中在“7—9”時段內(nèi),而未能提取出其他時段內(nèi)的強規(guī)則,提取結果的覆蓋范圍窄.

分析兩種方法提取的扒竊犯罪發(fā)生的路段和時段的分布差異.值得注意的是,在基于聚類的關聯(lián)規(guī)則分析中,兩個不同的聚類表提取出了的相同強規(guī)則,而在直接進行關聯(lián)規(guī)則分析時卻忽略了這些規(guī)則(見表6).例如在秋季和冬季非節(jié)假日的7—9時段為類標簽的兩個聚類簇內(nèi)都提取出了規(guī)則Is (公交扒竊案)∧In (高科西路蓮溪路-高科西路白楊路)?In Time(7—9),而直接進行時空關聯(lián)規(guī)則分析中并沒有提取出該規(guī)則.原因可能是秋冬季節(jié)人們衣著較厚,實施扒竊不易被人發(fā)覺,7—9時間段是上班高峰期,客流量大.所以,犯罪分子作案集中在秋冬季節(jié)工作日的7—9時段,而春夏兩季作案相對較少.如果不經(jīng)過聚類而是在整個數(shù)據(jù)集中掃描,由于支持度小于閾值而忽略該規(guī)則,而基于聚類關聯(lián)規(guī)則能夠覆蓋更大范圍的數(shù)據(jù),發(fā)現(xiàn)容易忽略但有趣的規(guī)則.

表6 不同聚類簇中提取的相同強規(guī)則Tab.6 Efficient rules in different clusters

3 結論

本文將基于聚類的關聯(lián)規(guī)則算法應用在公交扒竊犯罪分析中.針對公安數(shù)據(jù)庫數(shù)據(jù)量大的特點,傳統(tǒng)Apriori算法需要多次掃描數(shù)據(jù)庫,算法效率較低,并不適合海量數(shù)據(jù)的挖掘.而基于聚類的關聯(lián)規(guī)則,只需掃描一次數(shù)據(jù)庫,聚成若干張聚類表,在聚類表中挖掘頻繁項集,掃描范圍要小得多,提高挖掘效率.同時,在進行聚類分析過程中,考慮到案發(fā)季節(jié)、時段、是否節(jié)假日等因素.聚類后簇內(nèi)數(shù)據(jù)相似度較高,數(shù)據(jù)特征更加明顯,在此基礎上做關聯(lián)分析提取出的規(guī)則置信度較高,更具有實際意義.根據(jù)提取的規(guī)則中案發(fā)公交路段和案發(fā)時間段的關系可以為警力部署提供參考,對提高公安機關的工作效率,打擊犯罪的精準度都有重要意義.

[1]HERRMANN C.A micro-level spatiotemporal analysis of crime,place&business establishment type[D].New York:The City University of New York,2011.

[2]NEWTON A.A study of bus route crime risk in urban areas:the changing environs of a bus journey[J].Built Environment,2008,34(1):88-103.

[3]NEWTON A D.Crime on public transport:‘static’and‘non-static’(moving)crime events[J].University of Huddersfield,2004,5(3):25-42.

[4]劉鵬.大數(shù)據(jù)背景下的摰燎榔瓟犯罪及打防對策[J].山東警察學院學報,2016,28(5):91-98.

[5]郭瑋.審查逮捕階段偵查員證言效力及路徑選擇——以北京市某區(qū)檢察院“零口供”型公交扒竊類案件為視角[J].南都學壇, 2015,(5):76-79.

[6]王敏.公交扒竊罪犯的社會干預機制[J].決策與信息旬刊,2012(5):28-28.

[7]胡煒.公交車上犯罪的原因與預防[J].法制與社會,2013(8):76-77.

[8]AGRAWAL R,IMIELI′NSKI T,SWAMI A.Mining association rules between sets of items in large databases[J]. ACM SIGMOD Record,1993,22(2):207-216.

[9]HAN J,KAMBER M.數(shù)據(jù)挖掘概念與技術[M].范明,孟小峰,譯.北京:機械工業(yè)出版社,2001.

[10]李德仁,王樹良,史文中,等.論空間數(shù)據(jù)挖掘和知識發(fā)現(xiàn)[J].武漢大學學報(信息科學版),2001,26(6):491-499.

[11]夏英,張俊,王國胤.時空關聯(lián)規(guī)則挖掘算法及其在ITS中的應用[J].計算機科學,2011,38(9):173-176.

[12]李晶晶.時空數(shù)據(jù)挖掘在環(huán)境保護中的應用研究[D].長沙:中南大學,2008.

[13]XUE C J,DONG Q,MA W X.Object-oriented spatial-temporal association rules mining on ocean remote sensing imagery[C]//35th International Symposium on Remote Sensing of Environment(ISRSE35).Beijing, 2013.

[14]MENNIS J,LIU J W.Mining association rules in spatio-temporal data:an analysis of urban socioeconomic and land cover change[J].Transactions in Gis,2005,9(1):5-17.

[15]葉文菁,吳升.基于加權時空關聯(lián)規(guī)則的公交扒竊犯罪模式識別[J].地球信息科學學報,2014,16(4):537-544.

[16]楊立波.基于聚類的關聯(lián)規(guī)則挖掘算法[J].太原大學學報,2011,12(1):113-116.

[17]袁楠,金暉,田玲,等.基于聚類和模糊關聯(lián)規(guī)則的中醫(yī)藥對量效分析[J].計算機應用研究,2009,26(1):59-61.

[18]SETHI P,ALAGIRISWAMY S.Association rule based similarity measures for the clustering of gene expression data[J].Open Medical Informatics Journal,2010,4(1):63.

[19]ISAKKI A D P,RAJAGOPALAN S P.Analysis of customer behavior using clustering and association rules[J]. International Journal of Computer Applications,2012,43(23):19-26.

[20]周梅.基于聚類的關聯(lián)規(guī)則交叉銷售模型研究[J].現(xiàn)代商業(yè),2010,(26):73.

[21]石敏.基于聚類劃分的關聯(lián)規(guī)則在Web日志挖掘中的應用研究[D].武漢:武漢理工大學,2014.

[22]王慧,鄭濤,張建嶺.基于聚類的關聯(lián)規(guī)則算法在刑事犯罪行為分析中的應用[J].中國人民公安大學學報(自然科學版),2010, (3):65-67.

[23]AGRAWAL R,SRIKANT R.Fast algorithms for mining association rules[C]//Proceedings of the Twentieth Internaltional Conference on Very Large Databases.Santiago,1994.

(責任編輯：李萬會)

Spatio-temporal analysis of bus pickpocketing using association rules based on clustering

YAN Mi-qiao,GUO Zhong-yang,REN Zhe-hao
(School of Geography Sciences,East China Normal University,Shanghai200241,China)

This paper introduced the spatio-temporal association rules based on clustering minging to f i nd out the spatio-temporal crime patterns of bus pickpocketing.It can be carried out through three steps.Firstly,extract time,places and other information from the case information by text extraction.Then,conf i rm the boarding stations and getting of fstations of victims using the geocoding service and POI search capability of Amap API.Divide the bus routes into sections according to the bus stops and merge the crime time into time interval.Thirdly,the analysis of association rules based on clustering is carried out to discover the patterns of bus pickpocketing.The results prove that theproposed mining model has the following characteristics：①This method can reduce the database scanning times,the candidate item sets amount and improve time efficiency of the searching.②After clustering,the data in a cluster is similar and the characteristics are more obvious.On this basis,the association rules of high conf i dence are extracted.③When the analysis was carried out,the temporal and spatial characteristics of the bus pickpocketing crime were also considered.

bus pickpocketing;clustering;spatio-temporal association rules;crime pattern recognition

TP391.4

A

10.3969/j.issn.1000-5641.2017.03.016

1000-5641(2017)03-0145-08

2016-06-17

國家理科基地科研訓練及科研能力提高項目(J1310028)

閆密巧,女,碩士研究生,研究方向為數(shù)據(jù)挖掘.

過仲陽,男,教授,博士生導師,研究方向為數(shù)據(jù)挖掘、數(shù)據(jù)可視化.

E-mail：zyguo@geo.ecnu.edu.cn.