基于聚类关联规则的公交扒窃犯罪时空分析

闫密巧,过仲阳,任浙豪

(华东师范大学地理科学学院,上海200241)

基于聚类关联规则的公交扒窃犯罪时空分析

闫密巧,过仲阳,任浙豪

(华东师范大学地理科学学院,上海200241)

提出了一种基于聚类的时空关联规则的公交犯罪挖掘算法.针对某市一个区的110报警数据库中的大量业务信息进行分析.首先,通过文本挖掘技术从案情信息中提取时间、地点等信息,并利用高德地图API的地理编码服务和POI搜索功能对提取的地址信息进行地址匹配,提取受害人上下车站点、乘坐公交线路等信息.其次,对提取得到的时空数据进行归并处理.最后,根据案发时段、季节以及是否节假日进行聚类分析,然后在簇内进行时空关联规则分析.这种挖掘方法具有以下特点：①在聚类基础上进行关联规则分析,减少扫描数据库次数,大大缩小数据扫描范围,提高算法效率,更加适合海量犯罪数据的挖掘.②聚类后簇内数据具有相似性,特征更加明显,在此基础上进行关联规则分析产生较小的频繁项集,并且提取出置信度较高的规则.③考虑犯罪行为的时空特性,挖掘过程中同时考虑了案发季节、是否节假日等因素.

公交扒窃;聚类分析;关联规则;犯罪模式识别

0 引言

随着城市公共交通迅猛发展,客流量明显增多,这也给犯罪分子进行扒窃犯罪提供了便利.公交扒窃已成为影响公共秩序和危害人们出行安全的热点问题.由于公交扒窃犯罪的动态特征,受害人往往不能确定被扒的时间、地点等,这给公安机关侦破案件以及打击犯罪增加了难度.在国外,对于公共交通犯罪行为的研究主要集中在暴力犯罪、破坏公共设施等方面.根据发生时的状态可以分为两种,即在站点候车时发生的和在移动的车辆上发生的.例如Herrmann对纽约市扒窃犯罪行为进行时空热点分布研究,结果发现扒窃犯罪热点分布在地铁站周围,并且白天(下午15∶00高峰期)多分布在学校周围,夜里(凌晨1∶00左右)多分布于企业周围[1].而对发生在移动车辆上的犯罪行为的研究较少,Netown对公交犯罪行为的时间和地点分别进行过统计,分析得出那些穿越高犯罪率区域的公交路线比其他路线更易发生扒窃,并且在高犯罪率的区域的停靠站点越多的线路越容易发生扒窃[2].Newton提出将公交犯罪行为分为“静态犯罪”和“非静态(线性)犯罪”,并指出研究的重点和难点是如何分析非静态(线性)犯罪事件[3].在国内,针对公交扒窃犯罪的研究非常少,主要集中在公交扒窃犯罪的预防机制、治理对策和案件的定性量刑方面[4-7].目前的研究大多使用统计分析方法对案件数量、作案人员的特征等做简单统计,使用数据挖掘方法对公交扒窃犯罪进行研究的还较少.并且对公交扒窃犯罪的研究往往将时间和空间割裂开来,忽略了其时空特性.现有研究主要是基于经验的总结,例如分析作案手段、作案团伙活动范围等,缺乏定量的分析研究.本文同时结合了时间和空间特性,利用基于聚类的关联规则对公交扒窃犯罪行为进行分析.

在进行案件分析的时候,若是单纯进行聚类,仅仅以相似的案件为依据来提取犯罪行为规律,虽然可以提取覆盖范围较大的时空规律,但是它的准确率不高.而对于Apriori算法,它并没有将相似的犯罪行为聚类,而是提取频繁出现的项集作为规则产生的依据,因此往往它得出的犯罪时空规律准确率比较理想,但是覆盖率不够.基于聚类的时空关联规则,通过综合应用这两种算法寻求一种平衡,旨在得到准确率和覆盖率都较高的犯罪时空规律.

另外,110接报数据库数据量大,若采用传统的关联规则算法,需要多次扫描数据库,产生大量候选项集,挖掘效率低下.基于聚类的时空关联规则算法,首先将公交扒窃时空数据聚为若干簇,然后在簇内进行关联规则分析.可缩小数据扫描范围,减少扫描数据库的时间,提高算法效率,更适合数据量大的犯罪数据挖掘.

1 基于聚类的时空关联规则挖掘

1.1 时空关联规则

关联规则由Agrawal等人在1993年提出[8].关联规则是形如A⇒B的蕴含式,规则A⇒B在事务集D中成立,具有支持度s和置信度c.其中s是事务集D中A和B同时出现的概率,它是概率P(A∪B).c是事务集D中A出现的情况下,B出现的概率,这是条件概率P(A|B).即∶

空间数据都是时间的函数,在一些事务和现象中存在时间和空间的相关关系[10].在实际研究和应用中,人们对于时间和空间之间的关系更加感兴趣,从而促使时空关联规则的出现.时空关联规则算法就是从既有时间属性又有空间属性的事物表中提取频繁项集和关联规则的方法.

目前时空关联规则主要应用在交通、物流、土地资源、环境等领域[11-15],主要存在两方面问题,一方面是处理海量数据时算法效率问题,另一方面是时空谓词的表述、提取问题.本文采用基于聚类的关联规则,有效缩小关联规则算法中数据扫描范围,提高算法效率.在时空谓词的提取上,结合文本分词、地图服务API及地理编码等更高效精准的提取时空谓词.

1.2 基于聚类的时空关联规则

聚类分析和关联规则都是数据挖掘中的经典方法.关联规则旨在找出给定数据集中各项之间有趣的联系.聚类就是将数据对象分组成多个簇.同一个簇中的对象彼此相似,与其他簇中的对象相异.聚类分析的应用之一就是做数据预处理,通过聚类分析得到若干簇,簇内对象相似性较高,在簇内提取关联规则针对性更强、更加集中而且效率更高.所以基于聚类的关联规则也是十分重要的研究方向.

关联规则挖掘是一个两步的过程,首先找出所有频繁项集,然后由满足最小支持度和最小置信度的频繁项集产生强规则.Apriori算法是一种最有影响的挖掘频繁项集的算法.但Apriori算法的不足之处是可能产生大量候选项集,并且需要多次扫描数据库,通过模式匹配检查一个很大的候选项集.对海量犯罪数据挖掘尤其如此.基于聚类的关联规则的基本思想是首先将数据集聚类为k个簇,在各个簇内进行关联规则分析.相比Apriori算法,基于聚类的关联规则算法只需扫描一次数据库,生成M张聚类表,在聚类表内进行关联规则分析要比直接在110接报信息数据库中简单得多,大大缩小了数据扫描范围,减少数据扫描时间,降低开销,提高挖掘效率[16].其基本流程如图1所示.

图1 基于聚类的关联规则算法流程Fig.1 The flow chart of association rules based on clustering

目前基于聚类的关联规则的研究主要将聚类分析作为数据预处理步骤,经过聚类达到数据降维、筛选孤立点等目的[17-22].在犯罪领域,还没有应用基于聚类的时空关联规则对具有“动态犯罪”特征的公交扒窃案件进行分析的研究.本文通过综合应用聚类分析和时空关联规则这两种算法,旨在提高公交扒窃犯罪时空规则的支持度和置信度.

2 公交扒窃犯罪模式识别

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

本文以某市的一个区2015年全年的110接报案数据为基础,选择公交扒窃案件为研究对象,利用文本挖掘技术从简要案情描述文本中提取时空信息,并按照一定规则对时空数据进行归并,将数据结构化,得到公交扒窃案件时空数据表.首先,采用K-Means聚类分析算法,根据案发时段、季节以及是否节假日进行聚类.然后,对得到的各个簇,进行关联规则分析.公交扒窃案的挖掘流程如图2所示.

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

(1)时空信息提取

数据处理流程包括文本提取和数据归并两部分.首先,根据案件数据库中的简要案情描述信息,利用文本信息提取技术并结合高德地图JavaScriptAPI提取受害人乘车时间、上下车站点等信息.利用开源的中文分词工具对案情描述文本进行分词和词性标注,设计相应的分词词典,将公交站点名称加入分词词典中.利用规则匹配的方法从分词结果中提取出上下车站点名和上车时间,如表1所示.

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

(2)信息归并

本文对提取得到的时空数据进行归并.空间数据包括受害人上下车站点及途经站点,以相邻站点将受害人途经站点划分为公交路段.为了研究方便,约定对于只提取出一个公交站点的,用该站与下一站组成的公交路段表示.

对于时间数据,考虑到一位乘客乘坐公交车时间一般不超过2 h,且公交扒窃案件多发生在5∶00—23∶00时间段内,因此文本将5∶00—23∶00按2 h为间隔划分为9个公交时段,23∶00至第二天5∶00作为单独的一个公交时段.然后对提取的案发时间进行归约,根据从文本提取出的时间和公交车在某两站之间运行的时间确定案发时段.得到的大部分案发时段完全落入公交时段内的,直接用该公交时段表示.对于案发时段介于两个公交时段之间的,案发时段落入哪个公交时段的比例更大,则以该公交时段表示.特别的,对于星期的划分考虑重要节假日,将假期前一天定为周五,假期第一天定为周六,后续假期均定为周日,调休日定为周一.经过数据处理后,提取出5 394条完整记录作为分析数据,公交扒窃案件时空数据结构如表2所示.

表2 公交扒窃案件时空数据表Tab.2spatio-temporal data table of bus pickpocket case

(3)案件信息挖掘

公交扒窃案件具有“动态犯罪”的特征,实际案发位置是不确定的,根据案情描述文本提取的案发公交路段只是可能的案发位置.因此应考虑各公交路段的案发率,由此区分各公交路段的重要程度.叶文菁等提出一种公交扒窃案件中各公交路段权重的计算方法[15,23],用每个案件中涉及的公交路段数的倒数作为公交路段的权重.例如,某人从公交站点A到站点C之间发现被扒,提取的案发公交路段为AB、BC,运用关联规则分析时对AB、BC路段分别作一次统计,理解为在AB段发生了一次扒窃,BC段也发生一次扒窃,显然不合实际.若考虑各路段的案发概率,则此案件发生在AB段和BC段的概率都为0.5,可以理解为在AB段发生了0.5次扒窃, BC段发生0.5次扒窃,这样更符合实际.设某公交路段的权重为Wi,第i条案件记录中涉及的公交路段个数为k,则第i条案件记录中各个公交路段的权重即为

公交扒窃案件数据中的空间属性用X表示,Xim表示第i条案件记录中某一公交段,用Y表示时间属性,Yi表示第i条案件记录中的案发时段,加权支持度和加权置信度计算方法如公式(4)—(7)所示[23].

其中,Wi为各公交路段的权重.特别的,第i条记录的时间权重Wj=1.

使用Apriori算法提取频繁项集需要满足Apriori算法向下封闭性,即频繁项集的所有非空子集都必须是频繁的.设{Xim,Yj}为频繁项集,由Count(Xim)＞Count(Xim∪Yj)且Wj=1,可得WSupport(Xim)＞WSupport(Xim∪Yj)＞Supportmin,即{Xim}也是频繁的.同理{Yj}也为频繁项集.所以,对于公交扒窃案件进行加权关联规则分析满足Apriori算法向下封闭性,可使用Apriori算法进行连接和剪枝.

2.2 实验结果与分析

对5 439条记录根据案发季节、时段和星期进行K-Means聚类得到4张聚类表,其结构如表3所示.然后,分别对各聚类表作关联规则分析,首先,设定最小支持度0.1%,最小置信度50%,对4个聚类表进行挖掘.然后分别对每个聚类表挖掘的结果进行排序,先按支持度排序,再按照置信度排序,选取两次排位都在前5的项集,对4个聚类表得到的共20个项集综合排序,选取排位前7的强规则,由此确定加权支持度和加权置信度的实际的阈值分别为0.19%和66.67%.结果如表4所示.

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

表4 基于聚类的时空关联规则提取的强规则Tab.4 Efficient rules for spatio-temporal association rules based on clustering

本文同时对5 439条记录在不经过聚类的情况下,直接应用基于Apriori算法的关联规则对所有犯罪记录进行分析,以此对比两种分析方法的效率.设定最小支持度0.1%,最小置信度50%.对挖掘结果进行排序,取前7条记录,由此确定加权支持度和加权置信度的实际的阈值分别为0.1%和53.33%.结果如表5所示.

表5 关联规则分析提取的强规则Tab.5 Efficient rules for spatio-temporal association rules

对比表4和表5可知,经过聚类后在簇内进行关联规则分析可提取出置信度更高的规则.同时,在未经过聚类分析而直接应用关联规则分析提取出的强规则中犯罪时段集中在“7—9”时段内,而未能提取出其他时段内的强规则,提取结果的覆盖范围窄.

分析两种方法提取的扒窃犯罪发生的路段和时段的分布差异.值得注意的是,在基于聚类的关联规则分析中,两个不同的聚类表提取出了的相同强规则,而在直接进行关联规则分析时却忽略了这些规则(见表6).例如在秋季和冬季非节假日的7—9时段为类标签的两个聚类簇内都提取出了规则Is (公交扒窃案)∧In (高科西路莲溪路-高科西路白杨路)⇒In Time(7—9),而直接进行时空关联规则分析中并没有提取出该规则.原因可能是秋冬季节人们衣着较厚,实施扒窃不易被人发觉,7—9时间段是上班高峰期,客流量大.所以,犯罪分子作案集中在秋冬季节工作日的7—9时段,而春夏两季作案相对较少.如果不经过聚类而是在整个数据集中扫描,由于支持度小于阈值而忽略该规则,而基于聚类关联规则能够覆盖更大范围的数据,发现容易忽略但有趣的规则.

表6 不同聚类簇中提取的相同强规则Tab.6 Efficient rules in different clusters

3 结论

本文将基于聚类的关联规则算法应用在公交扒窃犯罪分析中.针对公安数据库数据量大的特点,传统Apriori算法需要多次扫描数据库,算法效率较低,并不适合海量数据的挖掘.而基于聚类的关联规则,只需扫描一次数据库,聚成若干张聚类表,在聚类表中挖掘频繁项集,扫描范围要小得多,提高挖掘效率.同时,在进行聚类分析过程中,考虑到案发季节、时段、是否节假日等因素.聚类后簇内数据相似度较高,数据特征更加明显,在此基础上做关联分析提取出的规则置信度较高,更具有实际意义.根据提取的规则中案发公交路段和案发时间段的关系可以为警力部署提供参考,对提高公安机关的工作效率,打击犯罪的精准度都有重要意义.

[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]刘鹏.大数据背景下的摰燎榔瓟犯罪及打防对策[J].山东警察学院学报,2016,28(5):91-98.

[5]郭玮.审查逮捕阶段侦查员证言效力及路径选择——以北京市某区检察院“零口供”型公交扒窃类案件为视角[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.数据挖掘概念与技术[M].范明,孟小峰,译.北京:机械工业出版社,2001.

[10]李德仁,王树良,史文中,等.论空间数据挖掘和知识发现[J].武汉大学学报(信息科学版),2001,26(6):491-499.

[11]夏英,张俊,王国胤.时空关联规则挖掘算法及其在ITS中的应用[J].计算机科学,2011,38(9):173-176.

[12]李晶晶.时空数据挖掘在环境保护中的应用研究[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]叶文菁,吴升.基于加权时空关联规则的公交扒窃犯罪模式识别[J].地球信息科学学报,2014,16(4):537-544.

[16]杨立波.基于聚类的关联规则挖掘算法[J].太原大学学报,2011,12(1):113-116.

[17]袁楠,金晖,田玲,等.基于聚类和模糊关联规则的中医药对量效分析[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]周梅.基于聚类的关联规则交叉销售模型研究[J].现代商业,2010,(26):73.

[21]石敏.基于聚类划分的关联规则在Web日志挖掘中的应用研究[D].武汉:武汉理工大学,2014.

[22]王慧,郑涛,张建岭.基于聚类的关联规则算法在刑事犯罪行为分析中的应用[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)

闫密巧,女,硕士研究生,研究方向为数据挖掘.

过仲阳,男,教授,博士生导师,研究方向为数据挖掘、数据可视化.

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