面向城市服务设施数据的同位模式挖掘研究

姚晓婧

中国科学院遥感与数字地球研究所，北京 100101

城市空间是人类活动的主要区域，随着数据采集和共享技术的快速发展，大量与城市相关的数据可被获取。公共服务设施数据作为城市各类数据的地理基础，其中蕴含着丰富的人类群体智慧。在智慧城市建设的发展契机下，利用数据挖掘手段，从较为成熟的城市设施数据中提取有趣的规律和知识，以指导新城市的合理规划和后续设施的合理布局，成为目前一个重要的应用和研究热点。

同位模式挖掘是解决上述命题的有效方法，它隶属于空间数据挖掘的一个分支，用来寻找具有空间依赖性的特征类型组合，即所谓的流行同位模式。流行模式表现于它们所代表的实例频繁地出现在同一地点。目前，关于该领域的研究多数弱化了地理空间的特异性，体现在对距离衰减作用和地理异质特性考虑的不足，导致这些方法应用于城市服务设施数据上存在自适应性差和精确度不够的现象，此外，效率较低和内存需求较高也一直是制约该研究领域的重要瓶颈之一。

本文在现有同位模式挖掘研究的基础上，提出了3个新的算法，分别为：①考虑距离衰减效应的同位模式挖掘方法；②基于泰森多边形和距离回馈函数的自适应同位模式挖掘方法；③高效且节省空间的极大同位模式挖掘方法。这3个算法从实例关系的处理、模式流行度的计算、候选模式的获取和空间团实例的计算上，层次递进地解决了上述提到的问题。此外，基于每个算法的改进重点，笔者利用北京城市公共服务设施数据进行了大量的试验，验证了算法的有效性。本文的研究工作和创新点包括以下几个方面：

(1) 首次在实例关系的处理和模式流行程度的鉴定中，将实例之间的距离值作为变量考虑进去，由于挖掘过程中顾及了距离衰减效应的影响，因此有效提升了挖掘结果的精确度。

(2) 提出一种基于泰森多边形的实例连接方法，打破了常规只考虑邻近实例连接的局限性，不仅有效避免了由于距离阈值设置不合理产生的冗余连接计算量和存储需求，而且由于同时保留了较远和较近距离的实例连接关系和距离值，使得模式流行程度的判定过程中充分融入距离衰减效应的考虑成为可能。

(3) 发现基于泰森多边形的连接实例的距离集合符合广义极大值的分布规律，基于这一特征，本文提出利用统计学的方法估计表征区域密度的距离截断参数，省去了用户预先设定距离阈值的过程，有效提高了同位模式挖掘在未知区域上执行的自适应性。

(4) 将流行的二阶同位模式抽象为一个稀疏的无向完全图，引入一种快速的候选极大同位模式挖掘方法。该方法具体将“退化度次序”和“关键点的选择”融入到经典的极大团发现算法中，有效提升了候选极大同位模式的计算效率。

(5) 采用了一种层次性的验证方法，构建了一个压缩树结构，用来存储较长候选同位模式的团实例关系。该方法摒弃了现有算法在剪枝程序之前需要为邻近实例对构建冗余初始结构的过程，并且只需要通过较少而且容易的树节点操作即可获取所有的团实例，有效削减了挖掘过程的内存和时间需求。