﻿ Spark环境下犯罪人员时空关联规则挖掘 Spatiotemporal Association Rules Mining for Key Personnel Based on FP-Growth in Spark Environment

Hans Journal of Data Mining
Vol. 08  No. 04 ( 2018 ), Article ID: 27022 , 10 pages
10.12677/HJDM.2018.84022

Spatiotemporal Association Rules Mining for Key Personnel Based on FP-Growth in Spark Environment

Bo Cheng1, Weihong Li1, Haoxin Tong2

1South China Normal University, Guangzhou Guangdong

2Guangdong Finest Planning Information Technology Co., Ltd., Guangzhou Guangdong

Received: Sep. 7th, 2018; accepted: Sep. 22nd, 2018; published: Sep. 29th, 2018

ABSTRACT

Taking the improvement of public security enforcement efficiency and the urgent need for crime prevention and improvement, focusing on key personnel, car ticketing and hotel accommodation data, we analyzed the key personnel data and other data to get association rules in the framework of Spark distributed computing using the method of spatio-temporal association rules based on FP-growth, and find potential key personnel. This method has been successfully applied to the policing system. It has been proved through practical tests that the method is effective in detecting potential offenders.

Keywords:Spark, FP-Growth, Spatio-Temporal Association Rules, Potential Key Personnel

Spark环境下犯罪人员时空关联规则挖掘

1华南师范大学，广东 广州

2航天精一（广东）信息科技有限公司，广东 广州

1. 引言

2. 研究方法

2.1. 关联规则基本概念

2.1.1. 支持度和置信度

$\text{Support}\left(\text{X}\ge \text{Y}\right)=\text{P}\left(\text{X},\text{Y}\right)/\text{P}\left(\text{I}\right)=\text{P}\left(\text{X}\cup \text{Y}\right)/\text{P}\left(\text{I}\right)=\text{num}\left(\text{XUY}\right)/\text{num}\left(\text{I}\right)$ (1)

$\text{Confidence}\left(\text{X}\ge \text{Y}\right)=\text{P}\left(\text{Y}|\text{X}\right)=\text{P}\left(\text{X},\text{Y}\right)/\text{P}\left(\text{X}\right)=\text{P}\left(\text{XUY}\right)/\text{P}\left(\text{X}\right)$ (2)

2.1.2. 频繁项集和关联规则

2.1.3. 时空关联规则

2.2. FP-Growth算法

FP-growth算法为了减少I/O操作，提高效率，引入了一些数据结构存储数据，主要包括项头表、FP-Tree和节点链表。项头表(Header Table)即找出频繁1项集，删除低于支持度的项集，并按照出现的次数降序排序，这是第一次扫描数据。然后从数据中删除非频繁1项集，并按照项头表的顺序排序，这是第二次也是最后一次扫描数据。FP-Tree (Frequent Pattern Tree)初始时只有一个根节点Null，将每一条数据里的每一项，按照排序后的顺序插入FP-Tree，节点的计数为1，如果有共用的祖先，则共用祖先的节点计数 + 1。FP-Tree的挖掘过程如下，从长度为1的频繁模式开始挖掘。可以分为3个步骤：

1) 构造它的条件模式基(CPB, Conditional Pattern Base)，条件模式基(CPB)就是我们要挖掘的Item的前缀路径；

2) 然后构造它的条件FP-Tree (Conditional FP-tree)；

3) 递归的在条件FP-Tree上进行挖掘。

FP-growth函数的输入：tree是指原始的FP-Tree或者是某个模式的条件FP-Tree，a是指模式的后缀(在第一次调用时a = NULL，在之后的递归调用中a是模式后缀)；

FP-growth函数的输出：在递归调用过程中输出所有的模式及其支持度。每一次调用FP-growth输出结果的模式中一定包含FP-growth函数输入的模式后缀。

2.3. 研究方法流程

1) 将犯罪人员数据划分为训练数据和测试数据，两者的比例为4:1；对所有数据进行预处理。将犯罪人员训练数据和交通出行、住宿消费数据统一作为算法输入数据上传至HDFS；

2) 设置最小支持度(min_sup)和最小置信度(min_conf)，使用Spark Mlib对输入数据进行计算；

Figure 1. Flow chart of research methods

3) 根据设置的min_sup和min_conf条件对频繁项集进行剪枝，得到关联规则结果集；

4) 利用犯罪人员测试数据对关联规则结果集进行检验，检查关联规则的正确性和算法有效性。

3. 实验流程

3.1. 数据预处理

1) 数据提取：从X市警务系统数据库中抽取出用于关联规则分析的犯罪数据及相关数据，包括犯罪人员数据、交通出行数据、住宿消费数据，并从各数据中提取出分析所需的相应属性字段(见表1)；

2) 数据清洗：数据表中字段存在空值、错误值等问题，如身份证号码为空或长度不够等，需要对存在问题的字段进行一定处理。本文直接删除存在错误的数据，因为其所占比例较小，不影响分析；

3) 数据转换、加载：本研究数据中涉及到身份证号码等隐私信息，通过加密算法进行加密处理。由于本研究使用SparkMllib中的FP-growth算法进行计算，因此将转换后的数据文件上传至Hdfs中。

Table 1. Crime and related data information

3.2. 挖掘过程

1) 交通出行数据关联规则挖掘

2) 住宿消费数据时空关联规则挖掘

3) 综合交通出行、住宿消费数据的时空关联规则挖掘

4. 关联规则结果分析

4.1. 交通出行关联规则

4.2. 住宿消费时空关联规则

Table 2. Traffic Association Rules

Table 3. Accommodation consumption association rules

Table 4. Rules for spatial and temporal association of accommodation consumption

4.3. 综合时空关联规则

4.4. 潜在犯罪人员分析及检验

5. 结束语

Figure 2. Statistics of the results of the data association rules

Table 5. Comprehensive data association rules

Spatiotemporal Association Rules Mining for Key Personnel Based on FP-Growth in Spark Environment[J]. 数据挖掘, 2018, 08(04): 210-219. https://doi.org/10.12677/HJDM.2018.84022

1. 1. Ng, V., Chan, S., Lau, D., et al. (2007) Incremental Mining for Temporal Association Rules for Crime Pattern Discov-eries. Proceedings of the 18th Australasian Database Conference (ADC 2007), Ballarat, Victoria, 29 January-2 February 2007, 123-132.

2. 2. Buczak, A.L. and Gifford, C.M. (2010) Fuzzy Association Rule Mining for Community Crime Pattern Discovery. ACM SIGKDD Workshop on Intelligence and Security Informatics, Washington, DC, 25-28 July 2010, 1-10. https://doi.org/10.1145/1938606.1938608

3. 3. Tan, Y., Qi, Z. and Wang, J. (2012) Applications of Association Rules in Computer Crime Forensics. Applied Mechanics & Materials, 157-158, 1281-1286. https://doi.org/10.4028/www.scientific.net/AMM.157-158.1281

4. 4. Joshi, A. and Suresh, M.B. (2014) Compact Structure of Felonious Crime Sets Using FP-Tree Comparable Algorithms Analysis. International Journal of Computer Science and Information Technologies, 5, 2694-2699.

5. 5. Usha, D. and Rameshkumar, K. (2013) Frequent Pattern Mining Algorithm for Crime Dataset: An Analysis. International Journal of Engineering Sciences & Research Tech-nology, 2, 3379-3384.

6. 6. Usha, D. and Rameshkumar, K. (2014) A Complete Survey on Application of Frequent Pattern Mining and Association Rule Mining on Crime Pattern Mining. International Journal of Advances in Computer Science and Technology, 3, 264-275.

7. 7. Shekhar, S., Mohan, P., Oliver, D., et al. (2014) Crime Pattern Analysis: A Spatial Frequent Pattern Mining Approach Crime Pattern Analysis: A Spatial Frequent Pattern Mining Approach. Crime Pattern Analysis a Spatial Frequent Pattern Mining Approach.

8. 8. Isafiade, O., Bagula, A. and Berman, S. (2015) A Revised Frequent Pattern Model for Crime Situation Recognition Based on Floor-Ceil Quartile Function. Procedia Computer Science, 55, 251-260. https://doi.org/10.1016/j.procs.2015.07.042

9. 9. Asmai, S.A., Roslin, N.I.A., Abdullah, R.W., et al. (2014) Pre-dictive Crime Mapping Model Using Association Rule Mining for Crime Analysis. Science International, 26, 1703-1706.

10. 10. 林和, 莫照, 虞龙江, 等. 基于Rough集数据挖掘在犯罪人口数据库中的应用[J]. 计算机科学技术, 2007.

11. 11. 虞龙江. 模糊与粗集理论在犯罪人口数据库中的应用[D]: [硕士学位论文]. 兰州: 兰州大学, 2003.

12. 12. 魏士靖, 张基温, 耿汝年. 基于犯罪画像的计算机取证分析方法研究[J]. 微计算机信息, 2006, 22(4): 237-239.

13. 13. 魏士靖. 关联规则在画像分析取证中的应用[J]. 中国科技论文在线, 2005.

14. 14. 宿娜. 基于关联规则的实时网络取证模型研究[D]: [硕士学位论文]. 青岛: 山东科技大学, 2013.

15. 15. 盛巍. 侦查信息关联规则原理[J]. 科技信息, 2012(36): 300-300.

16. 16. 于娜. 基于关联规则算法的嫌疑程度关系发现方法研究[D]: [硕士学位论文]. 大连: 大连工业大学, 2015.

17. 17. 徐伟, 张军. 关联规则在犯罪行为分析中的应用研究[C]//中国科协年会. 第十届中国科协年会论文集: 2008年卷.

18. 18. 汤毅平. 基于Apriori算法的重新犯罪关联规则挖掘[J]. 指挥信息系统与技术, 2016(3): 91-95.

19. 19. 冯卓慧, 冯前进. 基于关联规则的再犯罪特征分析[J]. 浙江理工大学学报(社会科学版), 2017, 38(1): 57-60.

20. 20. 闫密巧, 过仲阳, 任浙豪. 基于聚类关联规则的公交扒窃犯罪时空分析[J]. 华东师范大学学报: 自然科学版, 2017(3): 145-152.

21. 21. 孙越恒, 王文俊, 迟晓彤, 等. 基于多维时间序列模型的社会安全事件关联关系挖掘与预测[J]. 天津大学学报(社会科学版), 2016, 18(2): 97-102.

22. 22. 王慧, 郑涛, 张建岭. 基于聚类的关联规则算法在刑事犯罪行为分析中的应用[J]. 中国人民公安大学学报(自然科学版), 2010, 16(3): 64-67.

23. 23. 王海波, 张永田, 吴升. 基于数据立方体的多最小支持度关联规则在犯罪分析中的应用[J]. 测绘科学技术学报, 2016, 33(4): 405-409.

24. 24. 杜威, 邹先霞. 增量关联规则挖掘算法在犯罪行为中的应用研究[J]. 中国人民公安大学学报(自然科学版), 2011, 17(2): 56-58.

25. 25. 许阳泉. 关联规则在财产犯罪分析中的应用[D]: [硕士学位论文]. 福州: 福州大学, 2014.

26. 26. 张予. 数据挖掘技术在高危人员犯罪信息挖掘的应用研究[D]: [硕士学位论文]. 南昌: 南昌大学, 2009.

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

28. 28. 李晶晶. 时空数据挖掘在环境保护中的应用研究[D]: [硕士学位论文]. 长沙市: 中南大学, 2008.

29. 29. Xue, C.J., Dong, Q. and Ma, W.X. (2014) Object-Oriented Spatial-Temporal Association Rules Mining on Ocean Remote Sensing Imagery. 35th International Symposium on Remote Sensing of Environment, Beijing, 22-26.

30. 30. Mennis, J. and Liu, J.W. (2005) Mining Association Rules in Spatio-Temporal Data: An Analysis of Urban Socioeconomic and Land Cover Change. Transactions in GIS, 9, 5-17. https://doi.org/10.1111/j.1467-9671.2005.00202.x

31. 31. 叶文菁, 吴升. 基于加权时空关联规则的公交扒窃犯罪模式识别[J]. 地球信息科学学报, 2014, 16(4): 537-544.