|
|
基于Voronoi图和距离衰减效应的模糊实例空间并置模式挖掘算法
|
Abstract:
空间并置模式挖掘用于发现一组空间特征，它们的实例在空间中频繁地相互邻近。传统的空间并置模式挖掘过程中，将空间实例抽象成点对象，每个实例对应一个确定位置。然而，规模较大的空间实例有多个重要位置点(如医院、公园入口)，其空间位置因对其入口的认知不同而存在差异，具有模糊性。对于这些模糊实例，本文考虑其重要位置点对该实例规模的贡献，重新定义实例间的邻近度。此外，传统的并置模式挖掘方法忽略了特征实例的空间分布密度以及邻近实例间的邻近程度，采用静态的距离阈值来识别邻近实例。本文考虑特征的分布密度，用Voronoi图自适应提取不同特征的邻近实例，结合邻近实例的距离衰减函数，更加科学地描述实例间的邻近度。提出一种同时考虑模糊实例规模和距离衰减效应的空间并置模式挖掘方法，为实现快速挖掘，设计了极大团和哈希表搜索参与实例的挖掘框架。在真实数据集和合成数据集上进行实验，验证本文的算法可以发现传统空间并置模式挖掘方法所忽略的有意义模式。
Space co-location pattern mining is used to discover a set of spatial features whose instances are frequently adjacent to each other in space. In the process of traditional space co-location pattern mining, spatial instances are abstracted into point objects, and each instance corresponds to a definite location. However, large spatial examples have multiple important location points (such as hospital, and park entrance), and their spatial locations are different due to different cognition of their entrances, which is fuzzy. For these fuzzy instances, this paper considers the contribution of important location points to the instance scale, and redefines the proximity between the instances. In addition, the traditional collocation pattern mining method ignores the spatial distribution density of feature instances and the proximity degree between neighboring instances, and uses static distance threshold to identify neighboring instances. In this paper, considering the distribution density of features, Voronoi diagram is used to adaptively extract adjacent instances with different features, and the proximity of adjacent instances is described more scientifically by combining the distance decay function of adjacent instances. In this paper, a space co-location pattern mining method is proposed, which takes into account both the fuzzy instance size and distance attenuation effects. In order to realize fast mining, a mining framework for the participating instances of maximal clique and hash table search is designed. Experiments are carried out on real data sets and synthetic data sets to verify that the proposed algorithm can find meaningful patterns ignored by traditional space co-location pattern mining methods.
| [1] | Ouyang, Z., Wang, L. and Chen, H. (2011) Mining Spatial Co-Location Patterns for Fuzzy Objects. Chinese Journal of Computers, 34, 1947-1955. https://doi.org/10.3724/SP.J.1016.2011.01947 |
| [2] | Shekhar, S. and Huang, Y. (2001) Discovering Spatial Co-Location Patterns: A Summary of Results. In: International Symposium on Spatial and Temporal Databases, Springer, Berlin, 236-256. https://doi.org/10.1007/3-540-47724-1_13 |
| [3] | Yoo, J.S., Shekhar, S., Smith, J., et al. (2004) A Partial Join Approach for Mining Co-Location Patterns. Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems, Arlington, 12-13 November 2004, 241-249. https://doi.org/10.1145/1032222.1032258 |
| [4] | Yoo, J.S. and Shekhar, S. (2006) A Joinless Approach for Mining Spatial Colocation Patterns. IEEE Transactions on Knowledge and Data Engineering, 18, 1323-1337. https://doi.org/10.1109/TKDE.2006.150 |
| [5] | Huang, Y. and Zhang, P. (2006) On the Relationships between Clustering and Spatial Co-Location Pattern Mining. 2006 18th IEEE International Conference on Tools with Artificial Intelligence (ICTAI’06), Arlington, 13-15 November 2006, 513-522. https://doi.org/10.1109/ICTAI.2006.91 |
| [6] | Wang, L., Zhou, L., Lu, J., et al. (2009) An Order-Clique-Based Approach for Mining Maximal Co-Locations. Information Sciences, 179, 3370-3382. https://doi.org/10.1016/j.ins.2009.05.023 |
| [7] | Yao, X., Peng, L., Yang, L., et al. (2016) A Fast Space-Saving Algorithm for Maximal Co-Location Pattern Mining. Expert Systems with Applications, 63, 310-323. https://doi.org/10.1016/j.eswa.2016.07.007 |
| [8] | 杨培忠, 王丽珍, 王晓璇, 等. 一种基于列计算的空间并置模式挖掘方法[J]. 中国科学(信息科学), 2022, 52(6): 1053-1068. |
| [9] | 张绍雪, 王丽珍, 陈文和. CPM-MCHM: 一种基于极大团和哈希表的空间并置模式挖掘算法[J]. 计算机学报, 2022, 45(3): 526-541. |
| [10] | Huang, Y., Pei, J. and Xiong, H. (2006) Mining Co-Location Patterns with Rare Events from Spatial Data Sets. Geoinformatica, 10, 239-260. https://doi.org/10.1007/s10707-006-9827-8 |
| [11] | Wang, L., Wu, P. and Chen, H. (2011) Finding Probabilistic Prevalent Colocations in Spatially Uncertain Data Sets. IEEE Transactions on Knowledge and Data Engineering, 25, 790-804. https://doi.org/10.1109/TKDE.2011.256 |
| [12] | 罗金, 王丽珍, 王晓璇, 等. K-近邻关系下的空间高效用核模式挖掘[J]. 计算机学报, 2022, 45(2): 354-368. |
| [13] | Wang, L., Jiang, W., Chen, H., et al. (2017) Efficiently Mining High Utility Co-Location Patterns from Spatial Data Sets with Instance-Specific Utilities. Database Systems for Advanced Applications: 22nd International Conference, DASFAA 2017, Suzhou, 27-30 March 2017, 458-474. https://doi.org/10.1007/978-3-319-55699-4_28 |
| [14] | Ouyang, Z., Wang, L. and Zhou, L. (2012) Mining Spatial Co-Location Patterns for Fuzzy Location of Instances. Journal of Frontiers of Computer Science & Technology, 6, 1144-1152. |
| [15] | Wen, F., Xiao, Q. and Wang, L. (2014) Algorithm of Mining Maximal Co-Location Patterns for Fuzzy Objects. Computer Science, 41, 138-145. |
| [16] | Yu, Q., Luo, Y., Wu, Q., et al. (2016) Hierarchical Co-Location Pattern Mining Approach of Unevenly Distributed Fuzzy Spatial Objects. Journal of Computer Applications, 36, 3113-3117. |
| [17] | Wan, Y. and Zhou, J. (2008) KNFCOM-T: A K-Nearest Features-Based Co-Location Pattern Mining Algorithm for Large Spatial Data Sets By Using T-Trees. International Journal of Business Intelligence and Data Mining, 3, 375-389. https://doi.org/10.1504/IJBIDM.2008.022735 |
| [18] | Sundaram, V.M. and Paneer, P. (2012) Discovering Co-Location Patterns from Spatial Domain Using a Delaunay Approach. Procedia Engineering, 38, 2832-2845. https://doi.org/10.1016/j.proeng.2012.06.332 |
| [19] | Qian, F., He, Q., Chiew, K., et al. (2012) Spatial Co-Location Pattern Discovery without Thresholds. Knowledge and Information Systems, 33, 419-445. https://doi.org/10.1007/s10115-012-0506-9 |
| [20] | Qian, F., Chiew, K., He, Q., et al. (2014) Mining Regional Co-Location Patterns with K NNG. Journal of Intelligent Information Systems, 42, 485-505. https://doi.org/10.1007/s10844-013-0280-5 |
| [21] | Yao, X., Chen, L., Peng, L., et al. (2017) A Co-Location Pattern-Mining Algorithm with a Density-Weighted Distance Thresholding Consideration. Information Sciences, 396, 144-161. https://doi.org/10.1016/j.ins.2017.02.040 |
| [22] | Yao, X., Chen, L., Wen, C., et al. (2018) A Spatial Co-Location Mining Algorithm That Includes Adaptive Proximity Improvements and Distant Instance References. International Journal of Geographical Information Science, 32, 980-1005. https://doi.org/10.1080/13658816.2018.1431839 |
| [23] | Bron, C. and Kerbosch, J. (1973) Algorithm 457: Finding All Cliques of an Undirected Graph. Communications of the ACM, 16, 575-577. https://doi.org/10.1145/362342.362367 |
| [24] | Eppstein, D., L？ffler, M. and Strash, D. (2013) Listing All Maximal Cliques in Large Sparse Real-World Graphs. Journal of Experimental Algorithmics (JEA), 18, 3.1-3.21. https://doi.org/10.1145/2543629 |
