Spatiotemporal Sub-prevalent Co-location Pattern Mining

LI Xin-yuan; CHEN Hong-mei; XIAO Qing; WANG Li-zhen

doi:10.13718/j.cnki.xdzk.2020.11.008

2020 Volume 42 Issue 11

Article Contents

Previous Article Next Article

LI Xin-yuan, CHEN Hong-mei, XIAO Qing, et al. Spatiotemporal Sub-prevalent Co-location Pattern Mining[J]. Journal of Southwest University Natural Science Edition, 2020, 42(11): 68-76. doi: 10.13718/j.cnki.xdzk.2020.11.008

Citation:

LI Xin-yuan, CHEN Hong-mei, XIAO Qing, et al. Spatiotemporal Sub-prevalent Co-location Pattern Mining[J]. Journal of Southwest University Natural Science Edition, 2020, 42(11): 68-76. doi: 10.13718/j.cnki.xdzk.2020.11.008

Spatiotemporal Sub-prevalent Co-location Pattern Mining

School of Information Science and Engineering, Yunnan University, Kunming 650504, China

More Information

Corresponding author: CHEN Hong-mei ;
Received Date: 14/10/2020
Available Online: 20/11/2020
MSC: TP391

Abstract

Spatial co-location pattern mining is an important research area, and has been widely applied in various fields such as environment protection, public transport, location-based services and urban computing. Compared with the traditional pattern based on clique instances, the spatial sub-prevalent pattern based on star instances can reveal richer spatial correlations among features. However, the temporal characteristic of spatial data, which is an important dimension of spatial data, is not considered by the current spatial sub-prevalent pattern. Hence, in this paper, a spatiotemporal sub-prevalent pattern based on star instances is presented by analyzing spatial instances whose locations change over time. Firstly, a metric to measure the pattern called "time sub-frequency" is proposed. Then, the anti-monotonicity of the metric is proven, and an efficient algorithm for mining the pattern is designed. Finally, the validity of the algorithm presented herein and the applicability of the pattern are verified through a number of experiments.
- spatial data mining,
- spatiotemporal data,
- spatiotemporal sub-prevalent co-location pattern

References

[1]	范高峰.带时间约束的co-location模式挖掘[D].昆明: 云南大学, 2012.http://cdmd.cnki.com.cn/Article/CDMD-10673-1012419406.htm Google Scholar
[2]	WANG L Z, BAO X G, ZHOU L H, et al. Maximal Sub-prevalent Co-location Patterns and Efficient Mining Algorithms [M] //Lecture Notes in Computer Science. Cham: Springer International Publishing, 2017: 199-214. Google Scholar
[3]	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. doi: 10.1007/s11280-018-0646-2 CrossRef Google Scholar
[4]	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. doi: 10.1109/TKDE.2004.90 CrossRef Google Scholar
[5]	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 - GIS '04. November 12-13, 2004. Washington DC, USA. New York: ACM Press, 2004: 241-249. Google Scholar
[6]	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. doi: 10.1109/TKDE.2006.150 CrossRef Google Scholar
[7]	WANG L Z, BAO Y Z, LU J, et al. A New Join-less Approach for Co-location Pattern Mining [C] //2008 8th IEEE International Conference on Computer and Information Technology. July 8-11, 2008, Sydney, NSW, Australia. IEEE, 2008: 197-202. Google Scholar
[8]	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. Google Scholar
[9]	WANG L Z, ZHOU L H, LU J, et al. An Order-clique-based Approach for Mining Maximal Co-locations [J]. Information Sciences, 2009, 179(19): 3370-3382. doi: 10.1016/j.ins.2009.05.023 CrossRef Google Scholar
[10]	王晓璇, 王丽珍, 陈红梅, 等.基于特征效用参与率的空间高效用co-location模式挖掘方法[J].计算机学报, 2019, 42(8): 1721-1738. Google Scholar
[11]	LIU Z, HUANG Y. Mining Co-locations under Uncertainty [M] //Advances in Spatial and Temporal Databases. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013: 429-446. Google Scholar
[12]	雷乐, 王丽珍, 肖清.空间co-location模式挖掘中的模糊技术初探[J].计算机工程与应用, 2019, 55(21): 158-166. Google Scholar
[13]	YOO J S, SHEKHAR S, KIM S, et al. Discovery of Co-evolving Spatial Event Sets [C] //Proceedings of the 2006 SIAM International Conference on Data Mining. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2006: 306-315. Google Scholar
[14]	CELIK M, SHEKHAR S, ROGERS J P, et al. Mixed-Drove Spatiotemporal Co-Occurrence Pattern Mining [J]. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(10): 1322-1335. doi: 10.1109/TKDE.2008.97 CrossRef Google Scholar
[15]	CELIK M, SHEKHAR S, ROGERS J P, et al. Mining at most Top-K% Mixed-drove Spatio-temporal Co-occurrence Patterns: a Summary of Results [C] //2007 IEEE 23rd International Conference on Data Engineering Workshop. April 17-20, 2007, Istanbul, Turkey. IEEE, 2007: 565-574. Google Scholar
[16]	CELIK M. Discovering Partial Spatio-temporal Co-occurrence Patterns [C] //Proceedings 2011 IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services. June 29 - July 1, 2011, Fuzhou, China. IEEE, 2011: 116-120. Google Scholar
[17]	QIAN F, YIN L, HE Q M, et al. Mining Spatio-temporal Co-location Patterns with Weighted Sliding Window [C] //2009 IEEE International Conference on Intelligent Computing and Intelligent Systems. November 20-22, 2009, Shanghai, China. IEEE, 2009: 181-185. Google Scholar
[18]	HUO J T, ZHANG J Z, MENG X F. On Co-occurrence Pattern Discovery from Spatio-temporal Event Stream [M] //Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013: 385-395. Google Scholar
[19]	YANG L, WANG L Z. Mining Traffic Congestion Propagation Patterns Based on Spatio-temporal Co-location Patterns [J]. Evolutionary Intelligence, 2020, 13(2): 221-233. doi: 10.1007/s12065-019-00332-4 CrossRef Google Scholar
[20]	马董, 陈红梅, 王丽珍, 等.空间亚频繁co-location模式的主导特征挖掘[J].计算机应用, 2020, 40(2): 465-472. Google Scholar

Access History

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(8) / Tables(2)

Export Citation

PDF

XML

Article Metrics

Article views(625) PDF downloads(84) Cited by(0)

Access History

Other Articles By Authors

on this site
on Google Scholar

HTML

随着空间数据的激剧增多，空间数据挖掘在测绘、导航、环境保护、公共交通、位置服务和城市计算等领域得到广泛应用.空间co-location模式挖掘是空间数据挖掘的重要分支，旨在挖掘其实例在空间中频繁关联的空间特征的子集，例如小丑鱼通常居住在海葵的触手之间，商场附近总是有KTV^[1].传统co-location模式采用团实例模型，该模型要求模式实例中的特征实例两两邻近形成团，从而忽略了空间特征间重要的非团的空间关系.针对这个问题，文献[2-3]提出了更具普适性的星型实例模型及亚频繁co-location模式，该模型放松了团约束，可以发现空间特征间更丰富的空间关系.

然而，上述星型实例模型及亚频繁co-location模式没有考虑空间数据的时间特性，而时间却是空间数据的关键要素.在现实世界中，空间实例的生存或位置会随着时间的变化而变化，例如，医院、学校等特征的实例有生命期，人、车等特征的实例会移动.在这样的时空数据上挖掘co-location模式，不同的时间将会得到不同的模式，即co-location模式也会随着时间的变化而变化，例如：{人，车，餐厅}是早上6点到8点的一个co-location模式；而{人，办公楼}是上午9点到12点的一个co-location模式.此外，分析不同时间的co-location模式及其随时间的变化规律，将有助于我们进一步了解空间特征间的时空关系，为co-location模式在环境保护、公共交通、位置服务和城市计算等领域的深入应用提供决策支持.

基于上述分析，本文考虑空间实例的位置随着时间变化而变化，研究基于星型实例模型的时空亚频繁模式挖掘.本研究主要面临2个方面的挑战：①基于星型实例模型及亚频繁模式，如何有效地融入时间信息并合理地定义时空亚频繁模式? ②面对计算更为复杂的时空数据，如何高效地挖掘时空亚频繁模式?

具体地，本研究主要工作包括：

(1) 分析融入时间信息的方式，提出时空亚频繁co-location模式及其度量指标：时间亚频繁度.

(2) 证明时空亚频繁模式的反单调性(向下闭合性)，提出有效的时空亚频繁模式挖掘算法.

(3) 在合成数据集基础上进行大量实验，验证了所提算法的有效性及时空亚频繁模式的实用性.

1. 相关工作

根据所采用的实例模型，空间co-location模式主要可以分为2类：基于团实例模型的co-location模式和基于星型实例模型的co-location模式.

1.1. 基于团实例模型的co-location模式

基于团实例模型的co-location模式由文献[4]提出，该模型要求模式实例中的特征实例两两邻近形成团，并采用参与度(最小参与率)度量模式的频繁程度.为了提高模式挖掘效率，文献[4]证明了参与度的反单调性(向下闭合性)，并提出了基于完全连接的join-based算法.针对生成候选模式实例时大量连接操作导致算法效率低的问题，文献[5]通过划分特征实例，提出了基于部分连接的partial join算法；文献[6]采用星型邻居实例及模式实例查找方法，提出了无连接的join-less算法.而文献[7-9]采用前缀树降低模式实例生成代价，分别提出了基于CPI-tree结构的无连接算法^[7]，基于iCPI-tree结构的模式挖掘算法^[8]，以及基于有序团的极大模式挖掘算法^[9].

在团实例模型下，研究者从效用、不确定性、模糊性等方面对co-location模式进行了广泛研究^[10-12].研究者也引入时间维度，进行了时空数据上的co-location模式研究.文献[13]计算各个时间片上的模式参与度，然后通过标准化欧式距离计算最终的模式参与度；文献[14]定义了空间上邻近且时间上持久但不一定邻近的混合对象组，提出了一种混合驱动时空共现模式挖掘算法MDCOPs；文献[15]提出了top-k MDCOPs算法；文献[16]进一步考虑对象的生存周期，提出了PACOPs算法；文献[17]采用加权滑动窗口模型，进一步考虑各时间片间的关联关系，在多个时间片上挖掘模式；文献[18]基于动态增量滑动窗口从时空事件流中挖掘时空共现模式.文献[19]考虑交通数据的时空特性，提出采用参与度和传播影响力度量模式有趣性，挖掘频繁同现且具有强传播影响力的拥堵模式.

1.2. 基于星型实例模型的co-location模式

基于星型实例模型的co-location模式由文献[2-3]提出，该模型放宽了团约束条件，仅需模式实例中的特征实例与中心特征实例邻近，从而可以发现更丰富的空间关系.文献[2-3]针对传统团实例模型及co-location模式的不足，提出星型实例模型及亚频繁co-location模式，并证明了亚频繁模式的反单调性，提出了2种高效的极大亚频繁模式挖掘算法，即基于前缀树的算法PTBA和基于分区的算法PBA；文献[20]考虑空间特征间的主导关系，定义了亚频繁模式中的主导特征及主导特征模式，提出了有效的挖掘算法.

与上述研究不同，本文考虑空间实例的时间特性，研究时空亚频繁co-location模式挖掘.

3. 挖掘算法

首先，提出一种朴素算法，然后，证明时间亚频繁度的反单调性(向下闭合性)，并基于反单调性，提出新的高效的时空亚频繁模式挖掘算法(STSCP，SpatioTemporal Sub-prevalent Co-location Patterns mining algorithm).

3.1. 朴素算法

朴素算法的基本思想是：首先，对每个时间片，使用空间亚频繁模式挖掘算法，挖掘所有空间亚频繁模式；然后，在所有时间片上，计算这些模式的时间亚频繁度，以挖掘时空亚频繁模式.朴素算法会尽早删除空间上不满足空间亚频繁阈值的模式，但在生成所有时间片的空间亚频繁模式之前，它不会尽早删除时间上不满足时间亚频繁阈值的模式，这导致了不必要的计算成本.

3.2. STSCP算法

根据文献[2-3]，星型参与度具有反单调性(向下闭合性)，即给定时间片t及其上的两个模式P_i和P_j，如果P_i⊆P_j，则SPI^t(P_i)≥SPI^t(P_j).因此，如果P_i不是空间亚频繁模式(即SPI^t(P_i)＜θ)，则P_j也不是空间亚频繁模式(即SPI^t(P_j)＜θ).

本研究所提的时间亚频繁度也具有反单调性(向下闭合性)，下面给予证明.

引理1   (时间亚频繁度TSF的反单调性)给定时间片集T及其上的2个模式P_i和P_j，如果P_i⊆P_j，则TSF(P_i)≥TSF(P_j).

证  对于任一时间片t∈T，因为SPI^t(P_i)≥SPI^t(P_j)，所以如果SPI^t(P_j)≥θ，则SPI^t(P_i)≥θ.因此有{t|SPI^t(P_j)≥θ，t∈T}⊆{t|SPI^t(P_i)≥θ，t∈T}.所以，TSF(P_i)≥TSF(P_j).

根据引理1，有如下引理2.

引理2   给定时间片集T及其上的2个模式P_i和P_j，如果P_i⊆P_j且P_i不是时空亚频繁模式(即TSF(P_i)＜δ)，则P_j也不是时空亚频繁模式(TSF(P_j)＜δ).

利用引理2，本研究提出新的高效的时空亚频繁模式挖掘算法STSCP.算法STSCP的基本思想是采用“候选生成—亚频繁测试”方式，从1阶开始，逐阶挖掘时空亚频繁模式，并在候选生成中，利用引理2删除不可能满足条件的候选模式.具体地，仅用k阶亚频繁模式，连接生成k+1候选模式；如果k+1阶候选模式的某个k阶子模式不是亚频繁模式，则删除该k+1阶候选模式；测试剩余候选模式是否是亚频繁模式.算法STSCP描述如表 1所示.

在算法中，步骤1-2用于为每个时间片生成星型邻居实例集；步骤5-12给出一个迭代过程，直至生成的高阶时空亚频繁模式集为空.该迭代过程的功能解释如下.

生成候选时空亚频繁模式(步骤6)：仅用k阶时空亚频繁模式，连接生成k+1阶候选时空模式，如果k+1阶候选时空模式的某个k阶子模式不是时空亚频繁模式，则删除该k+1阶候选时空模式.

生成候选空间亚频繁模式(步骤8)：对时间片t，初始时，k+1阶候选时空模式为其上的k+1阶候选空间模式.如果k+1阶候选空间模式的某个k阶子模式不是其上的空间亚频繁模式，则从时间片t上删除该k+1阶候选空间模式.

生成星型参与实例(步骤9)：对时间片t，生成其上候选空间模式的星型参与实例.

生成空间亚频繁模式(步骤10)：对时间片t，计算其上k+1阶候选空间模式的星型参与度，生成k+1阶空间亚频繁模式.

生成时空亚频繁模式(步骤11)：采用时间亚频繁表记录时间片0~t上的k+1阶空间亚频繁模式及其当前的时间亚频繁度.如果k+1阶空间亚频繁模式的时间亚频繁度小于δ-(1-(t+1)/|T|)，则删除该k+1阶空间亚频繁模式(即k+1阶候选时空模式)，后继时间片不需再处理，从而尽早删除不满足时间亚频繁阈值的模式，减少不必要的计算，提高挖掘效率.

5. 结论

时间是空间数据的重要维度，在现实世界中，空间实例的生存或位置会随着时间的变化而变化，而现有星型实例模型及亚频繁co-location模式没有考虑空间数据的时间特性.因此，本研究基于星型实例模型的时空亚频繁co-location模式挖掘.首先分析了融入时间的方式，定义了时空亚频繁模式的指标，提出了时空亚频繁co-location模式.然后，基于星型参与度的反单调性证明了时间亚频繁度满足向下闭合性，提出了有效的时空亚频繁模式挖掘算法.最后，在合成数据集基础上进行大量实验，验证了所提算法能够挖掘到更丰富、更有价值的时空亚频繁co-location模式.

Figure (8) Table (2) Reference (20)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

Message Board

Spatiotemporal Sub-prevalent Co-location Pattern Mining