Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2022, Vol. 56 Issue (2): 280-287    DOI: 10.3785/j.issn.1008-973X.2022.02.008
计算机与控制工程     
面向移动对象的松散型传染模式挖掘方法
陈玉1(),戴华1,2,*(),李博涵3,杨庚1,2
1. 南京邮电大学 计算机学院、软件学院、网络空间安全学院，江苏 南京 210023
2. 江苏省大数据安全与智能处理重点实验室，江苏 南京 210023
3. 南京航空航天大学 计算机科学与技术学院，江苏 南京 211106
Loose infection pattern mining algorithms over moving objects
Yu CHEN1(),Hua DAI1,2,*(),Bo-han LI3,Geng YANG1,2
1. School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
2. Jiangsu Key Laboratory of Big Data Security and Intelligent Processing, Nanjing 210023, China
3. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
 全文: PDF(696 KB)   HTML
摘要：

针对现有研究方案中对病毒或病菌的传染模式定义过于严格，可能丢失重要且正确的传染事件的问题，提出面向移动对象的松散型传染模式挖掘算法. 给出松散型传染事件的模式定义；提出基于滑动窗口的松散型传染模式挖掘算法(LIPMA)，按照传染事件发生的时间先后顺序，从初始传染源开始，利用滑动窗口机制，依次对每一个待检测对象进行分析处理，进而挖掘所有传染事件；提出基于R-tree索引的优化挖掘算法LIPMA+，该优化算法在每一轮的处理过程中，通过降低每一轮待检测对象的规模，实现挖掘效率的提升. 实验结果表明，所提出的传染模式挖掘算法能够对松散型传染事件进行高效、正确的挖掘，且能够挖掘更多潜在的传染事件；优化算法的挖掘效率显著提升，LIPMA+的平均挖掘时间仅占LIPMA的2%.
关键词： 移动对象;  数据挖掘;  传染模式;  地理空间数据;  R树    
Abstract:

The definition of infection pattern of viruses or germ in the existing research schemes is so strict that important and correct infection events may be missed. Thus, a loose infection pattern mining algorithm oriented to moving objects was proposed. Loose infection model was defined and loose infection pattern mining algorithm (LIPMA), which used a sliding window mechanism, was proposed. According to the time sequence of the occurrence of infectious events, LIPMA uses the sliding window mechanism to analyze and process each object to be detected in turn, thereby mining all infectious events. On this basis, an optimized mining algorithm LIPMA+ based on R-tree was proposed. The optimized algorithm reduces the size of the object to be detected in each round of processing to improve the mining efficiency. Experimental results show that the proposed infection pattern mining algorithm can efficiently and accurately mine loose infectious events, and can mine more potential infectious events. The mining efficiency of the optimized algorithm was significantly improved, and the average mining time of LIPMA+ only accounted for 2% of that of LIPMA.
Key words: moving object    data mining    infection pattern    geospatial data    R-tree
收稿日期: 2021-07-13 出版日期: 2022-03-03
CLC:  TP 399  
基金资助: 国家自然科学基金资助项目（61872197, 61972209, 61902199）；南京邮电大学自然科学基金资助项目（NY217119）；江苏省科研与实践创新计划项目(KYCX210768)
通讯作者: 戴华     E-mail: 1348987670@qq.com;daihua@njupt.edu.cn
作者简介: 陈玉（1998—），女，硕士生，从事数据挖掘研究. orcid.org/0000-0002-1378-8453. E-mail: 1348987670@qq.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
陈玉
戴华
李博涵
杨庚

引用本文:

陈玉,戴华,李博涵,杨庚. 面向移动对象的松散型传染模式挖掘方法[J]. 浙江大学学报(工学版), 2022, 56(2): 280-287.

Yu CHEN,Hua DAI,Bo-han LI,Geng YANG. Loose infection pattern mining algorithms over moving objects. Journal of ZheJiang University (Engineering Science), 2022, 56(2): 280-287.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2022.02.008    或    https://www.zjujournals.com/eng/CN/Y2022/V56/I2/280

图 1  基于轨迹的传染模式
图 2  传染模式的示意图
图 3  松散型传染事件数量的变化曲线
图 4  挖掘时间的变化曲线
1 MORITA T, TOYODA A, AISU S, et al Animals exhibit consistent individual differences in their movement: a case study on location trajectories of Japanese macaques[J]. Ecological Informatics, 2020, 56: 101057
doi: 10.1016/j.ecoinf.2020.101057
2 KANG J, YU R, HUANG X, et al Blockchain for secure and efficient data sharing in vehicular edge computing and networks[J]. IEEE Internet of Things Journal, 2019, 6 (3): 4660- 4670
doi: 10.1109/JIOT.2018.2875542
3 GUO L, ZHANG D X, CONG G, et al Influence maximization in trajectory databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 29 (3): 627- 641
4 杜金姬, 秦闯亮 一类具有logistic增长的随机SIRS传染病模型的平稳分布和灭绝性[J]. 高师理科学刊, 2020, 40 (10): 13- 17
DU Jin-ji, QIN Chuang-liang Stationary distribution and extinction of a stochastic SIRS epidemic model with logistic growth[J]. Journal of Science of Teachers’ College and University, 2020, 40 (10): 13- 17
doi: 10.3969/j.issn.1007-9831.2020.10.004
5 LAUBE P. Computational movement analysis[M]. Switzer land: Springer, 2014.
6 LIU W, GAO Z J A distributed flocking control strategy for UAV groups[J]. Computer Communications, 2020, 153: 95- 101
doi: 10.1016/j.comcom.2020.01.076
7 JEUNG H Y, YIU M L, ZHOU X F, et al Discovery of convoys in trajectory databases[J]. Proceedings of the VLDB Endowment, 2008, 1 (1): 1068- 1080
doi: 10.14778/1453856.1453971
8 ORAKZAI F, CALDERS T, PEDERSEN T B k/2-hop: fast mining of convoy patterns with effective pruning[J]. Proceedings of the VLDB Endowment, 2019, 12 (9): 948- 960
doi: 10.14778/3329772.3329773
9 SADEGHNEJAD-BARKOUSARAIE A, BATTA R, SUDIT M Convoy movement problem: a civilian perspective[J]. Journal of the Operational Research Society, 2016, 68: 1- 20
10 LI Z H, DING B, HAN J W, et al Swarm: mining relaxed temporal moving object clusters[J]. Proceedings of the VLDB Endowment, 2010, 3 (1/2): 723- 734
11 HOUSSEIN E H, AHMED M M, ELAZIZ M A, et al Solving multi-objective problems using bird swarm algorithm[J]. IEEE Access, 2021, 9: 36382- 36398
doi: 10.1109/ACCESS.2021.3063218
12 WANG X B, LIUC, ZHU M L. Instant traveling companion discovery based on traffic-monitoring streaming data [C]// 2016 13th Web Information Systems and Applications Conference. Wuhan: IEEE, 2016: 89-94.
13 CHAO F, HE Z Q, FENG R K, et al Predictive trajectory-based mobile data gathering scheme for wireless sensor networks[J]. Complexity, 2021, (2): 3941074
14 SONG X Y, SUN W, ZHANG Q L A dynamic hierarchical clustering data gathering algorithm based on multiple criteria decision making for 3D underwater sensor networks[J]. Complexity, 2020, 8835103
15 NASERIAN E, WANG X H, XU X L, et al A framework of loose travelling companion discovery from human trajectories[J]. IEEE Transactions on Mobile Computing, 2018, 17 (11): 2497- 2511
doi: 10.1109/TMC.2018.2813369
16 XU J Q, LU H, BAO Z F IMO: a toolbox for simulating and querying “infected” moving objects[J]. Proceedings of the VLDB Endowment, 2020, 13 (12): 2825- 2828
doi: 10.14778/3415478.3415485
17 GUTTMAN A. R-trees: a dynamic index structure for spatial searching[C]// Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. Boston: ACM, 1984, 14(2): 47-57.
18 YUAN J, ZHENG Y, XIE X, et al. Driving with knowledge from the physical world[C]// Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. California: ACM, 2011: 316-324.
[1] 李根,翟伟,邬岚. 基于梯度提升决策树的汇合交互作用研究[J]. 浙江大学学报(工学版), 2022, 56(4): 649-655.
[2] 李鑫悦,陈淑琴,李鸿亮,楼云霄,李佳鹤. 应用数据挖掘的高校教学建筑空调使用及其能耗分析[J]. 浙江大学学报(工学版), 2020, 54(9): 1677-1689.
[3] 齐建鹏, 于彦伟, 王创存, 曹磊, 宋鹏. 基于多线程的不确定移动对象连续k近邻查询[J]. 浙江大学学报(工学版), 2018, 52(1): 142-150.
[4] 王成龙,李诚,冯毅萍,荣冈. 作业车间调度规则的挖掘方法研究[J]. 浙江大学学报(工学版), 2015, 49(3): 421-429.
[5] 陈楠,寿黎但,陈刚,陈珂,胡天磊. 面向动态环境的移动对象自适应索引方法[J]. J4, 2013, 47(3): 442-448.
[6] 王相兵,童水光,钟崴,张健. 基于可拓重用的液压挖掘机结构性能方案设计[J]. J4, 2013, 47(11): 1992-2002.
[7] 马进, 李锋, 李建华. 分布式数据挖掘中基于扰乱的隐私保护方法[J]. J4, 2010, 44(2): 276-282.
[8] 石怀东，蔡铭，吴洪森，董金祥，富浩. 增量式频繁闭合序列挖掘算法[J]. J4, 2009, 43(8): 1389-1395.
[9] 王光增, 曹一家, 戚军, 等. 电力企业通用报表综合管理系统设计与实现[J]. J4, 2009, 43(11): 2062-2066.
[10] 王志勇 曹一家. 层次匹配范例推理在短期负荷预测中的应用[J]. J4, 2007, 41(9): 1598-1603.
[11] 刘渊 吴以才. 基于效益度的高效关联规则挖掘算法[J]. J4, 2007, 41(6): 909-914.
[12] 陈荣 高济 郭航. 面向网格计算的按需入侵检测模型[J]. J4, 2006, 40(3): 387-391.