基于图结构的空间同位模式挖掘

doi:10.11947/j.AGCS.2024.20230012

摘要/Abstract

摘要：

空间同位模式反映了不同地理要素分布的依存关系，是地理学第一定律的体现，也符合空间大数据分析重在揭示事物关联特征的目标。空间同位模式挖掘需要顾及空间分布耦合机制，探测空间邻近关系及基于支持度等指标分析高频共生模式。现有方法多在判定邻近关系的同时搜索共生模式，导致在挖掘高阶共生模式时需要实时修正几何邻近关系，在复杂系统下丧失计算过程的灵活性。考虑到图数据蕴含的拓扑连接信息与空间同位模式相契合，本文提出一种基于图结构的空间同位模式挖掘方法。该方法一步完成几何上的邻近关系探测，然后在图数据库中通过子图搜索完成逻辑上的同位模式判别。首先，基于Delaunay三角网构建自适应邻接图，利用自适应邻接过滤器删除无效连接。然后，通过候选子图的不断连接、剪枝、生长，逐步从N元递推获取N＋1元候选同位模式。最后，通过计算支持度指标并与预定义阈值比较以确定空间同位模式。本文基于不断生长迭代的图遍历思想提升了空间同位模式挖掘面向更复杂的空间场景的普适性。试验表明本文方法具备高效的挖掘能力，相较传统算法，在多元空间同位模式的挖掘任务中效果更优。

关键词: 空间同位模式, 自适应邻接图, 图遍历, Apriori算法

Abstract:

Under the first law of geography, spatial co-location patterns reflect the dependency of different geographic elements’ distribution, satisfying the association discovery of big spatial data analysis. Spatial co-location pattern mining needs to consider the spatial conjunction mechanisms, detect spatial neighborhood relationships and search high-frequency patterns with metrics such as support. The common co-location mining methods usually combine geometric computation and logical reasoning, which resulting in the need to correct geometric neighborhoods while mining higher-order co-location patterns. Considering that the topological information contained in graph data is suited to spatial co-location pattern, this study proposes a graph structure-based co-location pattern mining method that completes the geometric proximity detection in one step, and then completes the logical co-location pattern discrimination by subgraph search in the graph database. Firstly, we construct the adjacency graph based on the Delaunay triangle network and use an adaptive adjacency filter to eliminate invalid connections. Second, the N＋1 elements of candidate co-location patterns are obtained recursively from the N elements through continuous joining, pruning, and growing of subgraphs. Finally, the spatial co-location patterns are determined by calculating the support metrics and compared with predefined thresholds. Based on the concept of continuous graph traversal, this study improves the generality of spatial co-location pattern mining in complex scenarios. Experiments show that this method is more efficient than traditional algorithms, with better results in multivariate spatial co-location pattern mining.

Key words: spatial co-location pattern, adaptive neighborhood graph, graph traversal, Apriori algorithm

中图分类号:

P208

王靖涵, 艾廷华, 吴昊, 徐海江, 栗广岳. 基于图结构的空间同位模式挖掘[J]. 测绘学报, 2024, 53(4): 724-735.

Jinghan WANG, Tinghua AI, Hao WU, Haijiang XU, Guangyue LI. Spatial co-location pattern mining based on graph structure[J]. Acta Geodaetica et Cartographica Sinica, 2024, 53(4): 724-735.

图/表 20

图1

图2

图3

算法1

图4

表1

表2

图5

表3

图6

表4

图7

表5

图8

表6

图9

图10

图11

表7

图12

参考文献 32

[1]	马荣华, 马晓冬, 蒲英霞. 从GIS数据库中挖掘空间关联规则研究[J]. 遥感学报, 2005, 9(6):733-741.
	MA Ronghua, MA Xiaodong, PU Yingxia. Spatial association rule mining from GIS database[J]. Journal of Remote Sensing, 2005, 9(6):733-741.
[2]	KOPERSKI K. A progressive refinement approach to spatial data mining [D].Vancouver: Simon Fraser University, 1999.
[3]	SIERRA R, STEPHENS C R. Exploratory analysis of the interrelations between co-located Boolean spatial features using network graphs[J]. International Journal of Geographical Information Science, 2012, 26(3):441-468.
[4]	FLOUVAT F, NQUYEN V S, DESMIER E, et al. Domain-driven co-location mining extraction, visualization and integration in a GIS[J]. Geoinformatica An International Journal of Advances of Computer Science for Geographic, 2015, 19(1):147-183.
[5]	DIJKSTRA A, JANSSEN F, DE BAKKER M, et al. Using spatial analysis to predict health care use at the local level: a case study of type 2 diabetes medication use and its association with demographic change and socioeconomic status[J]. PLoS One, 2013, 8(8):e72730.
[6]	JUNG C, SUN C H. Development of a GIService based on spatial data mining for location choice of convenience stores in Taipei city[C]//Proceedings of 2006 Geoinformatics: Geospatial Information Technology.Wuhan: SPIE, 2006, 6421: 367-376.
[7]	蔡建南, 刘启亮, 徐枫, 等. 多层次空间同位模式自适应挖掘方法[J]. 测绘学报, 2016, 45(4):475-485. DOI: 10.11947/j.AGCS.2016.20150337.
	CAI Jiannan, LIU Qiliang, XU Feng, et al. An adaptive method for mining hierarchical spatial co-location patterns[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(4):475-485. DOI: 10.11947/j.AGCS.2016.20150337.
[8]	姚晓婧. 面向城市服务设施数据的同位模式挖掘研究[J]. 测绘学报, 2018, 47(10):1426. DOI: 10.11947/j.AGCS.2018.20170580.
	YAO Xiaojing. Co-location researches on urban public-service facilities[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(10):1426. DOI: 10.11947/j.AGCS.2018.20170580.
[9]	LIU Qiliang, LIU Wenkai, DENG Min, et al. An adaptive detection of multilevel co-location patterns based on natural neighborhoods[J]. International Journal of Geographical Information Science, 2021, 35(3):556-581.
[10]	QIN Kun, LIN Hui, YUE Yang, et al. Spatial humanities and geo-computation for social sciences: advances and applications[J]. Journal of Geodesy and Geoinformation Science, 2022, 5(2):1-6.
[11]	TOBLER W R. A computer movie simulating urban growth in the Detroit region[J]. Economic Geography, 1970, 46:234.
[12]	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. Houston: IEEE, 2006.
[13]	艾廷华, 周梦杰, 李晓明. 网络空间同位模式的加色混合可视化挖掘方法[J]. 测绘学报, 2017, 46(6):753-759. DOI: 10.11947/j.AGCS.2017.20160324.
	AI Tinghua, ZHOU Mengjie, LI Xiaoming. Mining co-location pattern of network spatial phenomenon based on the law of additive color mixing[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(6):753-759.DOI: 10.11947/j.AGCS.2017.20160324.
[14]	YOO J S, BOW M. Mining spatial colocation patterns: a different framework[J]. Data Mining and Knowledge Discovery, 2012, 24(1):159-194.
[15]	SHEKHAR S, HUANG Y. Discovering spatial co-location patterns: a summary of results[C]//Proceedings of 2001 International symposium on spatial and temporal databases.Berlin: Springer, 2001: 236-256.
[16]	HUANG Y, SHEKHAR S, XIONG H. Discovering colocation patterns from spatial data sets: a general approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(12):1472-1485.
[17]	AGRAWAL R, IMIELIŃSKI T, SWAMI A. Mining association rules between sets of items in large databases[C]//Proceedings of 1993 ACM SIGMOD international conference on Management of data. Washington: ACM Press, 1993: 207-216.
[18]	YU Wenhao, AI Tinghua, HE Yakun, et al. Spatial co-location pattern mining of facility points-of-interest improved by network neighborhood and distance decay effects[J]. International Journal of Geographical Information Science, 2017, 31(2):280-296.
[19]	禹文豪, 艾廷华, 刘鹏程, 等. 设施POI分布热点分析的网络核密度估计方法[J]. 测绘学报, 2015, 44(12):1378-1383,1400. DOI: 10.11947/j.AGCS.2015.20140538.
	YU Wenhao, AI Tinghua, LIU Pengcheng, et al. Network kernel density estimation for the analysis of facility POI hotspots[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(12):1378-1383,1400. DOI: 10.11947/j.AGCS.2015.20140538.
[20]	ZHOU Mengjie, AI Tinghua, WU Chao, et al. A visualization approach for discovering colocation patterns[J]. International Journal of Geographical Information Science, 2019, 33(3):567-592.
[21]	刘文凯, 刘启亮, 蔡建南. 自然邻域支持下的空间同位模式挖掘方法[J]. 测绘学报, 2019, 48(1):95-105. DOI: 10.11947/j.AGCS.2019.20170653.
	LIU Wenkai, LIU Qiliang, CAI Jiannan. Discovery of co-location patterns based on natural neighborhood[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(1):95-105.DOI: 10.11947/j.AGCS.2019.20170653.
[22]	YOO J S, SHEKHAR S, SMITH J, et al. A partial join approach for mining co-location patterns[C]//Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems.Washington: ACM Press, 2004: 241-249.
[23]	MOHAN P, SHEKHAR S, SHINE J A, et al. A neighborhood graph based approach to regional co-location pattern discovery: a summary of results[C]//Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Chicago: ACM Press, 2011: 122-132.
[24]	艾廷华. 深度学习赋能地图制图的若干思考[J]. 测绘学报, 2021, 50(9):1170-1182. DOI: 10.11947/j.AGCS.2021.20210091.
	AI Tinghua. Some thoughts on deep learning enabling cartography[J]. Acta Geodaetica et Cartographica Sinica, 2021, 50(9):1170-1182.DOI: 10.11947/j.AGCS.2021.20210091.
[25]	CHIAN V C, HILDEBRANDT M, RUNKLER T, et al. Learning through structure: towards deep neuromorphic knowledge graph embeddings[C]//Proceedings of 2021 International Conference on Neuromorphic Computing. Wuhan: IEEE, 2021: 61-70.
[26]	ZHANG Zhenghao, HUANG Jianbin, TAN Qinglin. Association rules enhanced knowledge graph attention network[J]. Knowledge-Based Systems, 2022, 239:108038.
[27]	陈崇成, 林剑峰, 吴小竹, 等. 基于NoSQL的海量空间数据云存储与服务方法[J]. 地球信息科学学报, 2013, 15(2):166-174.
	CHEN Chongcheng, LIN Jianfeng, WU Xiaozhu, et al. Massive geo-spatial data cloud storage and services based on NoSQL database technique[J]. Journal of Geo-Information Science, 2013, 15(2):166-174.
[28]	MILLER J J. Graph database applications and concepts with Neo4j[C]//Proceedings of 2013 Southern Association for Information Systems Conference. Atlanta: [s.n.], 2013: 2324.
[29]	LEE D T, SCHACHTER B J. Two algorithms for constructing a Delaunay triangulation[J]. International Journal of Computer & Information Sciences, 1980, 9(3):219-242.
[30]	ZHANG Lihua, TANG Lulu, JIA Shuaidong, et al. A collaborative simplification method for multiple coastlines based on the hierarchical triangulation network partition[J]. Journal of Geodesy and Geoinformation Science, 2020, 3(2):93-104.
[31]	BATRA S, TYAGI C. Comparative analysis of relational and graph databases[J]. International Journal of Soft Computing Engineering, 2012, 2(2):509-512.
[32]	边馥苓, 万幼. k-邻近空间关系下的空间同位模式挖掘算法[J]. 武汉大学学报(信息科学版), 2009, 34(3):331-334,338.
	BIAN Fuling, WAN You. A novel spatial co-location pattern mining algorithm based on k-nearest feature relationship[J]. Geomatics and Information Science of Wuhan University, 2009, 34(3):331-334,338.

Input：	初始元数K＝1，支持度阈值Pt_s，空间特征集F＝{f₁，f₂，f₃，…，f_m}，K元候选集C_K，邻接图边集Edge
Output：	空间同位模式Co_P
	G₁⇐F　//记录图中的所有空间特征，生成一元子图
	while G_K≠∅ do　// 当K元子图非空时继续
		create Ct for each item in C_K＋1　//建立候选项计数器
		for g in G_K do　//遍历邻接图中每个K元子图
			for edge in Edge do //遍历邻接图中所有边
				if \|g∪edge\|＝f_i then　//如果边和子图相交于某实例点
					g′⇐prune(g∪edge)　//边连接并剪枝
					C_K＋1⇐G′，Ct⇐Ct＋1 //更新候选模式，G′为代表g′的空间模式，记录频度
				end if
			end for
		end for
		if Sup>Pt_s then　//判断是否频繁
			G_K＋1⇐C_K＋1，Co_P⇐Co_P＋C_K＋1　//生成K＋1元子图，更新空间同位模式
		else:
			Remove edge　//删除Edge中非同位模式的边
		end if
		K⇐K＋1
	end

模式	元素	频数	支持度	支持度对比	是否为同位模式
{A，B}	A	5	5/7	7/11>Pt_s	是
{A，B}	B	7	7/11	7/11>Pt_s	是
{A，C}	A	3	3/7	3/7>Pt_s	是
{A，C}	C	3	3/6	3/7>Pt_s	是
{A，D}	A	3	3/7	3/7>Pt_s	是
{A，D}	D	3	3/6	3/7>Pt_s	是
{B，C}	B	4	4/11	4/11>Pt_s	是
{B，C}	C	3	3/6	4/11>Pt_s	是
{B，D}	B	4	4/11	4/11>Pt_s	是
{B，D}	D	3	3/6	4/11>Pt_s	是
{C，D}	C	2	2/6	2/6>Pt_s	是
{C，D}	D	2	2/6	2/6>Pt_s	是

模式	元素	频数	支持度	支持度对比	是否为同位模式
{A，B，C}	A	2	2/7	3/11>Pt_s	是
	B	3	3/11
	C	3	3/6
{A，B，D}	A	4	4/7	6/11>Pt_s	是
	B	6	6/11
	D	4	4/6
{A，C，D}	A	2	2/7	2/7>Pt_s	是
	C	2	2/6
	D	2	2/6
{B，C，D}	B	4	4/11	2/6>Pt_s	是
	C	2	2/6
	D	3	3/6

POI点种类	标签	数量
中餐	1	782
西餐	2	306
购物中心	3	58
便利店	4	245
停车场	5	484
公司	6	6628
加油站	7	503

空间同位模式	包含元素种类	包含元素数量	元素总数	支持度	阈值比较
[中餐，西餐]	中餐	258	782	0.329 92	0.329 92>Pt_s
[中餐，西餐]	西餐	189	306	0.617 64	0.329 92>Pt_s
[中餐，便利店]	中餐	212	782	0.271 10	0.271 10>Pt_s
[中餐，便利店]	便利店	135	245	0.551 02	0.271 10>Pt_s
[中餐，停车场]	中餐	162	782	0.207 16	0.207 16>Pt_s
[中餐，停车场]	停车场	164	484	0.338 84	0.207 16>Pt_s
[中餐，加油站]	中餐	109	782	0.139 39	0.139 39>Pt_s
[中餐，加油站]	加油站	96	503	0.190 85	0.139 39>Pt_s
[西餐，购物中心]	西餐	28	306	0.091 50	0.091 50>Pt_s
[西餐，购物中心]	购物中心	26	58	0.448 28	0.091 50>Pt_s
[西餐，便利店]	西餐	71	306	0.232 03	0.232 03>Pt_s
[西餐，便利店]	便利店	74	245	0.302 04	0.232 03>Pt_s
[西餐，停车场]	西餐	87	306	0.284 31	0.196 28>Pt_s
[西餐，停车场]	停车场	95	484	0.196 28	0.196 28>Pt_s
[西餐，加油站]	西餐	33	306	0.107 84	0.059 64>Pt_s
[西餐，加油站]	加油站	30	503	0.059 64	0.059 64>Pt_s
[购物中心，停车场]	购物中心	22	58	0.379 31	0.057 85>Pt_s
[购物中心，停车场]	停车场	28	484	0.057 85	0.057 85>Pt_s
[便利店，停车场]	便利店	61	245	0.248 98	0.142 56>Pt_s
[便利店，停车场]	停车场	69	484	0.142 56	0.142 56>Pt_s
[便利店，加油站]	便利店	47	245	0.191 84	0.085 49>Pt_s
[便利店，加油站]	加油站	43	503	0.085 49	0.085 49>Pt_s
[停车场，加油站]	停车场	82	484	0.169 42	0.169 42>Pt_s
[停车场，加油站]	加油站	86	503	0.170 97	0.169 42>Pt_s