基于众包地理空间信息的道路网络丰富化与路径计算

### 基于众包地理空间信息的道路网络丰富化与路径计算 #### 1. 空间关系提取 - **数据来源**：选择旅行博客作为众包地理空间数据的丰富来源。利用经典的网络爬虫技术，从20个旅行博客中收集数据，构建了一个包含250,000篇文本的数据库。 - **提取步骤** 1. **检测POI和空间关系**：从文本中获取定性空间关系，需要检测兴趣点（POI）或地名，以及连接这些POI的空间关系。 2. **地理解析和地理编码**：采用地理解析（检测候选短语）和地理编码（将短语与实际坐标信息关联）的方法。 3. **使用NLTK提取空间关系**：遵循相关方法，使用自然语言处理工具包（NLTK）进行空间关系提取，得到形如 (Pi, Rk, Pj) 的三元组，其中Pi和Pj是命名实体（地标），Rk是它们之间的空间关系。 4. **地理编码POI**：依靠GeoNames地理名称数据库，对提取的POI进行地理编码。从旅行博客文本语料库中提取了500,000个POI，其中约480,000个能够成功地理编码，最终得到约600,000个三元组。 - **聚焦区域**：为了获得有意义的结果，聚焦于巴黎和纽约这两个城市。提取的三元组定义了空间关系图，节点表示POI，边表示它们之间的空间关系。在本工作中，仅考虑表示接近性的距离和拓扑关系，如“near”“close”等。 #### 2. 空间关系建模 - **特征提取** - 为了训练概率模型，需要有信息价值的特征。将每个空间关系建模为距离和方向的函数。 - 从旅行博客中提取空间关系（如“near”）的出现情况，为每个出现创建二维空间特征向量 D = (Dd, Do)⊺，其中Dd表示距离，Do表示方向。 - 最终为每个空间关系得到一组二维特征向量 Drel = {D1, D2, ..., Dn}。 - **概率建模** - 使用二维特征向量集训练高斯混合模型（GMMs）。 - 一般来说，GMM是M个分量高斯密度的加权和，公式为 p(d|λ) = ∑(i = 1 to M) wig(d; μi, Σi)，其中d是l维数据向量（这里l = 2），wi是混合权重，g(d; μi, Σi)是具有均值向量 μi 和协方差矩阵 Σi 的高斯密度函数。 - 使用期望最大化（EM）算法进行参数估计，直到对数似然 L = ∑(j = 1 to m) log(p(Dj|λ)) 收敛。 - 最终为每个空间关系得到训练好的GMM pk(D|λ)，基于此通过贝叶斯推理得到POI对的接近度得分。 #### 3. 从关系图到加权图 - **相关定义** - 设 P = {P1, ..., Pm} 表示代表POI的节点集合，R = {R1, ..., Rn} 表示预定义的空间接近关系集合。 - Ri,j 表示从文本中提取的两个不同节点 Pi 和 Pj 之间的关系集合，Di,j 表示它们之间的空间特征向量。 - D 表示所有具有非空关系集合的POI对之间的空间特征向量集合。 - **计算后验概率**：根据空间特征数据 Di,j 估计类 Rk ∈ Ri,j 的后验概率，公式为： \[P(Rk|Di,j) = \frac{p(Di,j|Rk)P(Rk)}{\sum_{l = 1}^{n} p(Di,j|Rl)P(Rl)}\] - **计算接近度得分**：将所有后验概率组合成一个接近度得分 Wi,j，公式为： \[Wi,j = \frac{1}{|R|} \cdot \frac{\sum_{i = 1}^{|Ri,j|} P(Rk|Di,j)}{\max_{k} \{P(Rk|D)\}}\] - **得到加权图**：将接近度得分 Wi,j 分配给关