基于Voronoi图和距离衰减效应的模糊实例空间并置模式挖掘算法

空间并置模式挖掘用于发现一组空间特征，它们的实例在空间中频繁地相互邻近。传统的空间并置模式挖掘过程中，将空间实例抽象成点对象，每个实例对应一个确定位置。然而，规模较大的空间实例有多个重要位置点(如医院、公园入口)，其空间位置因对其入口的认知不同而存在差异，具有模糊性。对于这些模糊实例，本文考虑其重要位置点对该实例规模的贡献，重新定义实例间的邻近度。此外，传统的并置模式挖掘方法忽略了特征实例的空间分布密度以及邻近实例间的邻近程度，采用静态的距离阈值来识别邻近实例。本文考虑特征的分布密度，用Voronoi图自适应提取不同特征的邻近实例，结合邻近实例的距离衰减函数，更加科学地描述实例间的邻近度。提出一种同时考虑模糊实例规模和距离衰减效应的空间并置模式挖掘方法，为实现快速挖掘，设计了极大团和哈希表搜索参与实例的挖掘框架。在真实数据集和合成数据集上进行实验，验证本文的算法可以发现传统空间并置模式挖掘方法所忽略的有意义模式。

空间并置模式挖掘是空间数据挖掘的一个重要分支。从空间数据集中发现频繁空间并置模式就是发现一组空间特征，其实例频繁地相互邻近。例如，在一个城市的兴趣点(POI)数据集中，通过使用频繁空间并置模式挖掘技术，我们发现银行、超市和汽车站这3 个特征的实例经常在邻近区域内一起出现，我们就称{银行、超市、汽车站}是一个频繁空间并置模式。频繁空间并置模式挖掘技术可以发现空间数据集中特征之间的内在联系，该技术已经广泛应用于诸多领域，如公共安全、城市规划、商业、交通等基于位置的服务。

传统的空间并置模式挖掘方法将空间实例抽象成点对象，但规模较大的空间实例覆盖面积可能跨越很多实例的邻域，例如医院和花店、药店。因此，对于医院这样具有较大覆盖面积的实例，使用多个入口共同表示此实例更加准确。实际生活中，实例的位置因人们对其入口的认知而不同，具有模糊性。在生活实践中模糊数据普遍存在，数据的边界或概念的定义具有模糊性。比如，“高”和“矮”、“胖”和“瘦”、“远”和“近”等。现有的基于模糊集的空间并置模式挖掘方法用模糊隶属度来表示模糊数据[1]。本文使用隶属度集对多个入口隶属于同一模糊实例这一现象给出客观的度量方式，隶属度集为模糊实例不同入口处人流量大小的比例，以此来表示不同位置属于该实例的概率。