数据挖掘 - 从 CSV（纬度和经度）为图形创建节点/边 - 吾爱随笔录

终极目标：我想找到两点之间（对于地图上给定的纬度和经度）的最短和最冷（就温度而言）路径！

我知道像 Dijkstra 或 A* 这样的算法，它们显然是用于导航系统的算法。事实上，我能够在 Python 中使用 NetworkX成功创建一个虚拟图并轻松找到最短路径：

import  matplotlib.pyplot as plt  
import networkx as nx
%matplotlib inline

#graph object
g = nx.Graph()

#graph nodes
g.add_nodes_from(['s','a','b','c','g'])

#add edges
g.add_edge('s','a')
g.add_edge('s','b')
g.add_edge('a','b')
g.add_edge('a','c')
g.add_edge('a','g')
g.add_edge('b','c')
g.add_edge('c','g')


#labels 
g.add_edge('s','a', weight=1)
g.add_edge('s','b', weight=4)
g.add_edge('a','b', weight=2)
g.add_edge('a','c', weight=5)
g.add_edge('a','g', weight=12)
g.add_edge('b','c', weight=2)
g.add_edge('c','g', weight=3)

# pos = nx.spring_layout(g)
fixed_positions = {'s':(0,4),'a':(4,6), 'b':(4,2), 'c':(8,4), 'g':(12,4)}#dict with two of the positions set

edge_labs = dict([( (u,v), d['weight']) for u,v,d in g.edges(data=True)])

nx.draw_networkx(g, fixed_positions )
nx.draw_networkx_edge_labels(g, fixed_positions, edge_labels=edge_labs)
nx.draw_networkx_nodes(g, fixed_positions, node_color='r')
plt.title("Simple Graph")
plt.show()

创建图表后，非常简单，这条单线给出了最短路径：

nx.shortest_path(g,'s','g')
['s', 'a', 'g']

或 Dijkstra 路径：

nx.dijkstra_path(g, 's','g')
['s', 'a', 'b', 'c', 'g']

甚至 A* 搜索：

nx.astar_path(g,'s', 'g', heuristic = None )
['s', 'a', 'b', 'c', 'g']

问题：我正在努力为首先提到的终极目标的真实数据创建图形（节点和边，权重）。数据如下所示：

time,               longitude, latitude, temperature
2017-11-13 12:53:49,11.558139,48.102061, 22.1
2017-11-13 12:54:21,11.557347,48.102176, 22.3
2017-11-13 12:55:35,11.554643,48.099852, 22.1
2017-11-13 12:55:55,11.559246,48.099049, 22.2
2017-11-13 12:56:24,11.559256,48.098769, 22.3
2017-11-13 12:56:39,11.559191,48.098996, 22.4
2017-11-13 12:56:49,11.559029,48.099175, 22.2
2017-11-13 12:57:07,11.558799,48.098782, 22.1
2017-11-13 12:57:39,11.558861,48.098965, 22.3

包含time、longitude、latitude和temperature（地理数据）。

如何从这里创建节点？每个longitude，latitude对我的节点吗？这是导航和路由的方式吗？对每个点进行循环并创建一个节点听起来并不高效！或者特别是longitude，latitude地图上的节点不是所有的点都应该算是节点吗？也许是某种粗略抽样？
这个问题与前一个问题密切相关。我该如何处理边缘？如果longitude，latitude对是节点，我是否在两个连续对之间创建一条边？
同样对于权重，在这种情况下为温度，我必须再次遍历所有这些边缘以分配适当的权重？
怎么样time？我想它没有影响吧？因为我对提供过去的路径不感兴趣。重要的是现在，或者如果我以后去预测将来使用 ML（现在不重要！）。

我已经研究了很长时间，并且遇到了很多建议，例如这个老问题，或者像前面提到的 NetworkX 或Gephi 之类的工具，可能还有其他教程，但我没有看到如何从这些地理数据轻松创建图表。我虽然这应该已经很成熟了，因为地图正在广泛使用它（也许不是开源的）。我在教程或博客文章中看到的所有内容都是直观地解释概念或上面显示的非常简单的图表的实现，或者它们与地理数据无关。

任何帮助或评论或指导如何实施表示赞赏。理想情况下，我想知道如何从 CSV 到创建 Graph，以便我可以执行最短路径算法。

2019 年 10 月 9 日更新： 受到布莱恩·斯皮林 (Brian Spiering) 出色回答的极大启发（见下文），我继续搜索并遇到了2017 年在赫尔辛基大学举办的一系列课程，教授如何使用直接从OpenStreetMap数据，例如看这里。正如您在链接中看到的，有一个很棒的Python 包 osmnx，可以轻松访问下载和可视化 OpenStreetMap 数据。好消息是所有这些图都与Python NetworkX兼容, 意味着你可以做任何你想做的事情，例如像地图一样寻找最短路径。osmnx 的开发者提供了很多如何将 osmnx 与 NetworkX 一起使用的示例，我发现这些示例非常有用且有趣，一定要查看（链接到 osmnx 示例）。

具体来说，我能够在几行代码中完成以下操作（对于热情的读者）：

import osmnx as ox
import matplotlib.pyplot as plt
import networkx as nx
from IPython.display import IFrame
ox.config(log_console=True, use_cache=True)

place_name = "Steglitz, Berlin, Germany"
graph = ox.graph_from_place(place_name, network_type='walk')

# project the network to an appropriate UTM (automatically determined)
graph_projected = ox.project_graph(graph)

# you can also plot/save figures as SVGs to work with in Illustrator later
fig, ax = ox.plot_graph(graph_projected, save=True, file_format='svg')

# use networkx to calculate the shortest path between two nodes
origin_node = list(graph.nodes())[0]
destination_node = list(graph.nodes())[20]
route = nx.shortest_path(graph, origin_node, destination_node)

print(route)
[1638866960,
 1832211366,
 443546729,
 443546728,
 27433702,
 241881515,
 241881517,
 241881519,
 241881521,
 241881560,
 4422819618,
 237937128,
 5471327997,
 28196761,
 27434765,
 26627352,
 26627351,
 27434717,
 1802301824,
 2375778405]

请注意，这里的路线是分配给图中每个节点（一对纬度和经度）的 osmid 点列表（源和目的地的输入也基于！您可以直接将输入作为一对纬度和经度（基于图中找到的最近节点），例如：

origin = ox.get_nearest_node(graph, tuple(nodes[['x','y']].iloc[0].tolist()))
destination = ox.get_nearest_node(graph, tuple(nodes[['x','y']].iloc[20].tolist()))
route = nx.shortest_path(graph, origin_node, destination_node)

您可以进一步扩展它以按距离（此处为长度）最小化路径：

route_length = nx.shortest_path(graph, origin_node, destination_node, weight='length')

# plot the route with folium
route_map_length = ox.plot_route_folium(graph, route_length)

# save as html file then display map as an iframe
filepath = 'data/route_length.html'
route_map_length.save(filepath)
IFrame(filepath, width=600, height=500)

我目前正在探索如何为终极目标增加额外的重量（在我的情况下为温度）！我根据 osmnx 的教程之一得到了一些想法，其中他们显示了最短距离会计边缘等级阻抗（链接）。

祝你好运和快乐的寻路！