基于图数据库的空间频繁并置模式挖掘

空间频繁并置模式(SPCP)是一组空间特征的子集,它们的实例在地理空间中频繁地出现在一起。基于内存物化实例邻近关系并搜索模式实例效率较高,但实例信息会被重复存储。图数据库技术能高效地对具有复杂关联关系的数据建模,但基于实例邻近关系图移植已有的挖掘方法不能发挥图遍历的优势。针对上述问题,探索了基于图数据库的空间频繁并置模式挖掘方法。首先,利用图数据库对空间实例及其邻近关系建模,即将实例和关系存储在图数据库中。然后,基于图数据库设计了一个称为子图(团)搜索的基本算法,采用团查找的方式生成模式的表实例从而获得参与实例,避免了传统方法中效率较低的组合或连接操作。考虑到通过生成表实例收集参与实例的效率较低,设计了参与实例验证算法,包括过滤阶段和验证阶段。过滤阶段判断一个中心实例的邻居集中所涉及的特征是否完全包含了待计算模式中的特征,验证阶段则是判断是否存在一个模式实例包含该中心实例。参与实例验证算法每次验证一个中心实例都尽可能多地去确定参与对象,从而有效地减小了搜索空间和减少了团的搜索次数。此外,对提出算法的正确性和完备性进行了证明。最后,在真实和合成数据集上做了大量的实验,验证了所提算法的效率和有效性。

基于模糊密度峰值聚类的区域同位模式并行挖掘算法

区域同位模式挖掘(RCPM,regional co-location pattern mining)是为了发掘某个局部区域内存在的同位(co-location)模式,以发现在全局中无法发现的信息.传统的区域挖掘大多会采用明确界限的几何体框定同位模式产生的区域.但是现实中的各类区域可能是无明确边界的.另外,数据的分布情况作为区域的重要特征之一,也应该成为区域选择的因素.基于上述思考,本文引入密度峰值聚类(DPC,density peak-based clustering),提出新的密度度量函数,并结合模糊集理论与k近邻距离,设计了一个行之有效的并行区域同位模式挖掘算法.实验结果表明,利用本文方法挖掘到的结果更具有现实意义,并且并行化极大地提升了挖掘算法的效率.在真实数据上,2线程下的加速比达到了1.89.