一种从时空数据中挖掘事件影响传播树的新方法

房滇武; 王丽珍; 邹目权; 邓飞

doi:10.11959/j.issn.2096-6652.202446

您当前的位置：

首页 >

文章列表页 >

一种从时空数据中挖掘事件影响传播树的新方法

专题：社会计算与社会智能 | 更新时间：2025-01-24

- 一种从时空数据中挖掘事件影响传播树的新方法
- A new method for mining event influence propagation trees from spatio-temporal data
- 智能科学与技术学报 2024年6卷第4期页码：509-521
- 作者机构：
  
  1. 昆明学院信息工程学院，云南昆明 650214
  2. 滇池学院，云南昆明 650228
  3. 富滇银行股份有限公司博士后科研工作站，云南昆明 650200
- 作者简介：
  
  [ "\t\t\t\t\t\t\t房滇武（1971- ），男，博士，昆明学院讲师、硕士生导师，主要研究方向为时空数据挖掘、模式识别和图神经网络等。" ]
  [ "\t\t\t\t\t\t\t王丽珍（1962- ），女，博士，滇池学院教授、博士生导师，IEEE高级会员，中国计算机学会（CCF）杰出会员，主要研究方向为空间数据挖掘、交互式数据挖掘和大数据分析及应用等。" ]
  [ "\t\t\t\t\t\t\t邹目权（1986- ），男，博士，富滇银行股份有限公司博士后科研工作站博士后，昆明学院硕士生导师，主要研究方向为空间数据挖掘和数字金融。" ]
  [ "\t\t\t\t\t\t\t邓飞（1986- ），男，西安交通大学博士生，昆明学院硕士生导师，主要研究方向为神经网络和机器学习。" ]
- 基金信息：
  
  昆明学院引进人才科研项目(XJ20230085);云南省彩云博士后计划—创新项目(YNBH24024);云南省地方本科高校基础研究联合专项(202101BA070001-152);昆明学院重点科研团队项目(XJ20230047);云南省院士专家工作站项目(202205AF150031)
- DOI：10.11959/j.issn.2096-6652.202446
  中图分类号： TP391.4
- 收稿日期：2024-08-15，
  
  修回日期：2024-11-01，
  
  纸质出版日期：2024-12-15
- 稿件说明：
移动端阅览
房滇武,王丽珍,邹目权等.一种从时空数据中挖掘事件影响传播树的新方法[J].智能科学与技术学报,2024,06(04):509-521.

FANG Dianwu,WANG Lizhen,ZOU Muquan,et al.A new method for mining event influence propagation trees from spatio-temporal data[J].Chinese Journal of Intelligent Science and Technology,2024,06(04):509-521.
房滇武,王丽珍,邹目权等.一种从时空数据中挖掘事件影响传播树的新方法[J].智能科学与技术学报,2024,06(04):509-521. DOI： 10.11959/j.issn.2096-6652.202446.

FANG Dianwu,WANG Lizhen,ZOU Muquan,et al.A new method for mining event influence propagation trees from spatio-temporal data[J].Chinese Journal of Intelligent Science and Technology,2024,06(04):509-521. DOI： 10.11959/j.issn.2096-6652.202446.

摘要

时空事件连锁发生的现象，在现实中很常见。为揭示这类现象背后的机制，开启了影响传播模式挖掘研究。挖掘事件影响传播树是其中一项基础工作，通常根据事件时空邻近关系，生成事件邻居集，用前缀树方法构建事件影响传播树。在时空事件较稠密时，组合式增长使挖掘时间与空间成本剧增，无法对大规模数据进行挖掘。为此，提出一种新方法，通过构建地理空间实体KD树，检索事件之间的时空邻近关系。设计一种三层哈希图数据结构存储事件的时空邻近关系，使事件影响传播树的信息虚拟化，不创建树实体，避免组合爆炸和大量树操作，提高挖掘效率，降低空间成本。在LSTW时空数据集上的实验结果，验证了新方法的效果。

Abstract

In reality

there was often a phenomenon where spatio-temporal events happened one by one. To uncover the mechanism behind phenomenon of this kind

the research of influence propagation pattern mining was initiated. One of fundamental tasks was to mine event influence propagation trees. A traditional way was used to generate a set of spatio-temporal event neighbors based on spatio-temporal proximity of events

and apply a prefix tree method to construct an event influence propagation tree. Once the spatio-temporal events were dense

the cost of mining time and space would be significantly increased by an explosive growth in the number of combinations

therefore

it would be difficult to mine large-scale data. To this end

a new method was proposed to construct a KD tree of geographic entities and retrieve the spatio-temporal proximity relationship between events. A three-layer Hashmap data structure was designed to store the spatio-temporal proximity relationship between events

virtualizing the information of event influence propagation trees without creating entities of trees. Thus combinatorial explosion and a large number of tree operations were avoided

the mining efficiency was improved and spatial costs were cut down. The experimental results on the LSTW spatio-temporal dataset verify the effectiveness and efficiency of new method.

关键词

Keywords

references

TOBLER W. On the first law of geography: a reply[J]. Annals of the Association of American Geographers, 2004, 94(2): 304-310.

SHEKHAR S, HUANG Y. Discovering spatial co-location patterns: a summary of results[C]//Proceedings of the 7th International Symposium. Berlin: Springer, 2001: 236-256.

YOO J S, SHEKHAR S, CELIK M. A join-less approach for co-location pattern mining: a summary of results[C]//Proceedings of the 5th IEEE International Conference on Data Mining (ICDM'05). Piscataway: IEEE Press, 2006: 813-816.

YOO J S, SHEKHAR S. A joinless approach for mining spatial colocation patterns[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(10): 1323-1337.

WANG L Z, BAO Y Z, LU J, et al. A new join-less approach for co-location pattern mining[C]//Proceedings of the 2008 8th IEEE International Conference on Computer and Information Technology. Piscataway: IEEE Press, 2008: 197-202.

BAO X G, WANG L Z. A clique-based approach for co-location pattern mining[J]. Information Sciences, 2019, 490: 244-264.

YANG P Z, WANG L Z, WANG X X, et al. SCPM-CR: a novel method for spatial co-location pattern mining with coupling relation consideration[J]. IEEE Transactions on Knowledge and Data Engineering, 2022, 34(12): 5979-5992.

ANDRZEJEWSKI W, BOINSKI P. A parallel algorithm for building iCPI-trees[C]//Proceedings of the 18th East European Conference on Advances in Databases and Information Systems. Cham: Springer International Publishing, 2014: 276-289.

ANDRZEJEWSKI W, BOINSKI P. Parallel GPU-based plane-sweep algorithm for construction of iCPI-trees[J]. Journal of Database Management, 2015, 26(3): 1-20.

ANDRZEJEWSKI W, BOINSKI P. Efficient spatial co-location pattern mining on multiple GPUs[J]. Expert Systems with Applications, 2018, 93: 465-483.

ANDRZEJEWSKI W, BOINSKI P. Parallel approach to incremental co-location pattern mining[J]. Information Sciences, 2019, 496: 485-505.

HUANG Y, ZHANG P S. On the relationships between clustering and spatial co-location pattern mining[C]//Proceedings of the 2006 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'06). Piscataway: IEEE Press, 2006: 513-522.

LU J L, WANG L Z, FANG Y. Mining causal rules hidden in spatial co-locations based on dynamic spatial databases[C]//Proceedings of the 2016 International Conference on Computer, Information and Telecommunication Systems (CITS). Piscataway: IEEE Press, 2016: 1-6.

WANG X X, LEI L, WANG L Z, et al. Spatial colocation pattern discovery incorporating fuzzy theory[J]. IEEE Transactions on Fuzzy Systems, 2022, 30(6): 2055-2072.

ZHAO J S, WANG L Z, BAO X G, et al. Mining co-location patterns with spatial distribution characteristics[C]//Proceedings of the 2016 International Conference on Computer, Information and Telecommunication Systems (CITS). Piscataway: IEEE Press, 2016: 1-5.

WANG L Z, BAO X G, ZHOU L H, et al. Maximal sub-prevalent co-location patterns and efficient mining algorithms[C]//Proceedings of the 18th International Conference on Web Information Systems Engineering. Cham: Springer International Publishing, 2017: 199-214.

WANG L Z, BAO X G, ZHOU L H, et al. Mining maximal sub-prevalent co-location patterns[J]. World Wide Web, 2019, 22(5): 1971-1997.

YU W H. Identifying and analyzing the prevalent regions of a co-location pattern using polygons clustering approach[J]. ISPRS International Journal of Geo-Information, 2017, 6(9): 259.

FANG Y, WANG L Z, HU T. Spatial co-location pattern mining based on density peaks clustering and fuzzy theory[C]//Proceedings of the Second International Joint Conference on Asia-Pacific Web and Web-Age Information Management. Cham: Springer International Publishing, 2018: 298-305.

BAO X G, WANG L Z. Discovering interesting co-location patterns interactively using ontologies[C]//Proceedings of the International Conference on Database Systems for Advanced Applications Workshops. Cham: Springer International Publishing, 2017: 75-89.

WANG L Z, BAO X G, CAO L B. Interactive probabilistic post-mining of user-preferred spatial co-location patterns[C]//Proceedings of the 2018 IEEE 34th International Conference on Data Engineering (ICDE). Piscataway: IEEE Press, 2018: 1256-1259.

YANG S S, WANG L Z, BAO X G, et al. A framework for mining spatial high utility co-location patterns[C]//Proceedings of the 2015 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). Piscataway: IEEE Press, 2015: 595-601.

王晓璇, 王丽珍, 陈红梅, 等. 基于特征效用参与率的空间高效用co-location模式挖掘方法[J]. 计算机学报, 2019, 42(8): 1721-1738.

WANG X X, WANG L Z, CHEN H M, et al. Mining spatial high utility co-location patterns based on feature utility ratio[J]. Chinese Journal of Computers, 2019, 42(8): 1721-1738.

WANG L Z, JIANG W G, CHEN H M, et al. Efficiently mining high utility co-location patterns from spatial data sets with instance-specific utilities[C]//Proceedings of the International Conference on Database Systems for Advanced Applications. Cham: Springer International Publishing, 2017: 458-474.

XIONG H, SHEKHAR S, HUANG Y, et al. A framework for discovering co-location patterns in data sets with extended spatial objects[C]//Proceedings of the 2004 SIAM International Conference on Data Mining. Philadelphia A: Society for Industrial and Applied Mathematics, 2004: 78-89.

LI J D, ADILMAGAMBETOV A, MOHOMED JABBAR M S, et al. On discovering co-location patterns in datasets: a case study of pollutants and child cancers[J]. GeoInformatica, 2016, 20(4): 651-692.

BEMBENIK R, JÓŹWICKI W, PROTAZIUK G. Methods for mining co-location patterns with extended spatial objects[J]. International Journal of Applied Mathematics and Computer Science, 2017, 27(4): 681-695.

陈兰. 空间高影响co-location模式挖掘[D]. 昆明: 云南大学, 2017.

CHEN L. Spatial high-impact co-location pattern mining[D]. Kunming: Yunnan University, 2017.

LEI L L, WANG L Z, ZENG Y M, et al. Discovering high influence co-location patterns from spatial data sets[C]//Proceedings of the 2019 IEEE International Conference on Big Knowledge (ICBK). Piscataway: IEEE Press, 2019: 137-144.

QIAN F, HE Q M, HE J F. Mining spread patterns of spatio-temporal co-occurrences over zones[C]//Proceedings of the International Conference on Computational Science and Its Applications. 2009: 677-692.

QIAN F, YIN L, HE Q M, et al. Mining spatio-temporal co-location patterns with weighted sliding window[C]//Proceedings of the 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems. Piscataway: IEEE Press, 2009: 181-185.

HUANG Y, ZHANG L Q, ZHANG P S. A framework for mining sequential patterns from spatio-temporal event data sets[J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(4): 433-448.

CHEN L, GAO Y J, FANG Z Q, et al. Real-time distributed co-movement pattern detection on streaming trajectories[J]. Proceedings of the VLDB Endowment, 2019, 12(10): 1208-1220.

HU X, WANG G Y, DUAN J L. Mining maximal dynamic spatial colocation patterns[C]//Proceedings of the IEEE Transactions on Neural Networks and Learning Systems. Piscataway: IEEE Press, 2021: 1026-1036.

SHEKHAR S, JIANG Z, ALI R, et al. Spatiotemporal data mining: a computational perspective[J]. ISPRS International Journal of Geo-Information, 2015, 4(4): 2306-2338.

MA D, CHEN H, WANG L, et al. Dominant feature mining of spatial sub-prevalent co-location patterns[J]. Journal of Computer Applications. 2019, 40: 465-472.

尚焱, 樊欣唯, 于洪. 考虑用户和传播属性的节点影响力评估算法[J]. 计算机工程与科学, 2015, 37(11): 2105-2111.

SHANG Y, FAN X W, YU H. A novel node influence measurement algorithm based on characteristics of users and propagation[J]. Computer Engineering and Science, 2015, 37(11): 2105-2111.

PENG S C, YANG A M, CAO L H, et al. Social influence modeling using information theory in mobile social networks[J]. Information Sciences, 2017, 379: 146-159.

LI W H, LI C, GENG Y L. APS: attribute-aware privacy-preserving scheme in location-based services[J]. Information Sciences, 2020, 527: 460-476.

CITRARO S, ROSSETTI G. Eva: attribute-aware network segmentation[C]//Proceedings of the Eighth International Conference on Complex Networks and Their Applications. Berlin: Springer, 2020: 141-151.

SUBBIAN K, AGGARWAL C, SRIVASTAVA J. Content-centric flow mining for influence analysis in social streams[C]//Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. New York: ACM Press, 2013: 841-846.

FENG K Y, CONG G, JENSEN C S, et al. Finding attribute-aware similar regions for data analysis[J]. Proceedings of the VLDB Endowment, 2019, 12(11): 1414-1426.

BROCKMANN D, HUFNAGEL L, GEISEL T. The scaling laws of human travel[J]. Nature, 2006, 439(7075): 462-465.

BONACCORSI G, PIERRI F, CINELLI M, et al. Economic and social consequences of human mobility restrictions under COVID-19[J]. Proceedings of the National Academy of Sciences of the United States of America, 2020, 117(27): 15530-15535.

ZAKI M J. Efficiently mining frequent trees in a forest: algorithms and applications[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(8): 1021-1035.

ZAKI M J. Efficiently mining frequent embedded unordered trees[J]. Fundam Informaticae, 2004, 66: 33-52.

JIMÉNEZ A, BERZAL F, CUBERO J C. Mining induced and embedded subtrees in ordered, unordered, and partially-ordered trees[M]. Berlin: Springer, 2008.

MOOSAVI S, SAMAVATIAN M H, NANDI A, et al. Short and long-term pattern discovery over large-scale geo-spatiotemporal data[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2019: 2905-2913.

HUANG Y, ZHANG L Q, YU P. Can we apply projection based frequent pattern mining paradigm to spatial co-location mining? [C]//Proceedings of the 9th Pacific-Asia Conference on the Methodologies for Knowledge Discovery and Data Mining (PAKDD 2005). Berlin: Springer, 2005: 719-725.

WANG L Z, BAO Y Z, LU Z Y. Efficient discovery of spatial co-location patterns using the iCPI-tree[J]. The Open Information Systems Journal, 2009, 3(2): 69-80.

项凤涛, 苏炯铭, 谷学强, 等. 基于智能体建模的新冠肺炎疫情传播问题研究[J]. 智能科学与技术学报, 2023, 5(1): 51-57.

XIANG F T, SU J M, GU X Q, et al. Research on the spread and countermeasures of COVID-19 using agent-based modeling[J]. Chinese Journal of Intelligent Science and Technology. 2023,5(1): 51-57.

覃缘琪, 季青原, 葛俊, 等. 城市交通路网动态短时推理与精准预测研究[J]. 智能科学与技术学报, 2022, 4(3): 380-395.

QIN Y Q, JI Q Y, GE J, et al. Short-term traffic state reasoning and precise prediction in urban networks[J]. Chinese Journal of Intelligent Science and Technology, 2022, 4(3): 380-395.

陈苑文, 王晓, 李灵犀, 等. 基于社会媒体数据增强的交通态势感知研究及进展[J]. 智能科学与技术学报, 2022, 4(1): 1-13.

CHEN Y W, WANG X, LI L X, et al. Traffic situational awareness research and development enhanced by social media data: the state of the art and prospects[J]. Chinese Journal of Intelligent Science and Technology, 2022, 4(1): 1-13.

张阳, 胡月, 辛东嵘. 一种考虑时空关联的深度学习短时交通流预测方法[J]. 智能科学与技术学报, 2021, 3(2): 172-178.

ZHANG Y, HU Y, XIN D R. A deep learning short-term traffic flow prediction method considering spatial-temporal association[J]. Chinese Journal of Intelligent Science and Technology, 2021, 3(2): 172-178.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据