道路网络层次结构的随机层次树模型

摘要

层次结构是地理空间普遍存在的规律和现象，在道路网络中通常以国道、省道、一般道路等的等级属性来表示。发掘道路网络的层次结构非常重要，对于出行路径分析、地图综合、空间多尺度表达与数据库更新、智能交通系统、城市规划等具有重要的应用价值。然而道路网络的层次划分并没有统一的标准，等级属性具有主观性且依赖于数据的完整性。现有研究已经提出了很多层次构建方法，但极大程度上主观性强、需要人工干预，未实现自动地构建层次，并且未自动地建立层次间的连通关系。 不止在道路网络中，层次化是自然界与社会组织中普遍存在、自觉与不自觉广泛使用的基本组织形式之一，存在于能以网络形式表达的现实世界中，例如航空网络、社交网络以及鸟群、鱼群的群集组织等。层次结构对于计算机而言深埋在关系复杂的数据中，发掘并自动地建立网络自然意义上的层次结构本质上讲是一种隐式知识的显式化、形式化和可计算化，是众多学科亟待解决的关键问题。为此，本文提出了随机层次树模型，该模型以层次化生长性为原则，采用贝叶斯统计进行数学建模，实现了自动地构建网络的层次。 首先，对现有网络层次构建模型进行了深入、系统的评估，指出现有模型尚存在的主要问题和面临的关键挑战。在此基础之上，本文基于层次化生长性设计了随机层次树模型。该模型假设层次存在并由生长而来，将由结点和边组成的网络转换成具有“冗余边”的树状结构。层次化生长性要求每个上层节点能够连接更多的子节点，为保持层次间的关联要求每个下层节点必须与相邻的上层节点的某一结点相连，组成树状结构的边称为“必须边”。其余的“冗余边”为网络提供便捷的健壮性，能够兼顾网络的整体经济型，并使得网络半径尽可能的小。 进而，本文基于贝叶斯统计方法按照上述思想建立了随机层次树的数学模型。建立树状结构的过程采用逐层选点的方式，层次化生长是自上而下，先设定顶层节点，与顶层节点相连的其他节点作为第二层，再从剩余节点中找到与第二层节点相连的作为第三层，以此类推直到所有节点都被纳入层次结构中。“必须边”的后验概率由逐层生成树结构的层次化选取累计得出，“冗余边”的后验概率由其所在位置和当前网络所有连边决定。由此组合而成了该模型的后验概率，至此建立了随机层次树的数学模型。 接下来，使用模拟退火算法进行模型求解，并鉴于求解的随机性，提出了节点相似度的稳定一致解求解方法。根据模型特点，在单次模拟退火算法求解中：设计了 9 种状态迁移方式；引入“真子树”、“当前真子树”、灵活的选点方式来促进实现各态历经；合理的温度控制和足够的迭代次数达到细节平衡。继而，对多次模拟退火的求解结果进行分析，由节点之间的相似度累计得出同一网络不同层次树之间的整体相似度量化指标，进而求得相似度最高的层次树作为稳定一致解。由此在有限的时间和资源下找到了随机层次树的合理解。 本文在实际道路网络中进行层次构建，并对构建结果进行了系统地分析和评估，验证了随机层次树模型的有效性。首先选取四种典型模式的道路网络为例进行层次构建，具体的步骤为：道路路段→路划→对偶图→随机层次树，并给出了层次构建结果。结果分析涵盖了层次的数目、层次的整体状态、结果的稳定性和与网络中心性测度指标的比较。结果分析表明，实际道路网络层次的数目在4-5层之间，同时，整体的分布状态为“纺锤形”结构，层次构建结果合理可靠，且稳定性高。 本文在两个方面开展了该模型应用的实验和分析，验证了随机层次树模型在不同应用上的适用性。两个应用分别是地图综合中的道路选取和航空网络的层次构建。实验结果表明，构建的道路网络层次与标准制图结果的符合度很高，能够很好地满足多比例尺道路网络地图制图的需要；随机层次树模型能够有效地构建合理的航空网络层次，从而验证了随机层次树模型具有适用性，具有较广泛的应用前景。 随机层次模型是一种无权无向网络的通用性层次划分方法，本文假设层次存在，并认为层次由生长而来，通过模拟退火算法给一个无序的网络赋予一个有序、有组织的分层，实现了复杂有环路网络层次结构的自动发掘和构建，并且自动地建立层次间的连通关系，在实际应用中具有可靠性且取得了不错的效果。随机层次树模型为网络层次构建提供了新方法，新技术，在近期内，该模型还可以用于其他网络的层次构建，辅助分析网络的反演与预测；长远来看期望能够辅助构建“开放的复杂巨系统”的地理系统，丰富和完善大数据时代的空间数据模型。

目录

第一个书签之前