Loading...
墨滴

张春成

2021/07/08  阅读:52  主题:默认主题

图的谱聚类

图的谱聚类

本文将继续介绍图的谱聚类方法,不纠结方法,只尝试说明它的用途。


谱聚类

在图论中,谱聚类有清晰的定义:

谱聚类是基于图中节点的关系对节点进行聚类的方法。

鉴于前文已经对图有了较为清楚的介绍,我们直接以中国省市地图为例,进行效果展示

ChinaMap
ChinaMap

图的节点是根据中国实际省市坐标进行绘制, 节点之间的连接是由“最小连通图”的原则进行计算的。 这些边的颜色代表经过谱聚类之后,这些节点得到的类别标签。

如果你熟悉中国地理,会看到一些相当有意思的东西。

捕风捉影

我们发挥想象力,试图对这些连接和谱聚类结果进行解释。 可以看到

不同颜色边的交界处,或多条边的交界处,都属于潜在的重要地点。

酒泉

汉军远征西域,曾打到“酒泉”。 从图中可以看到,酒泉等于扼守住了整个西域的关节。

ChinaJiuquan
ChinaJiuquan

锦州

德胜跟二号吵架也要先打锦州,因为整个东北只有这一条入关的路。 结果拿到后,只能从海路转进,天下半定。

ChinaJinzhou
ChinaJinzhou

百色

当年为啥哪都碰壁,但百色能成? 很简单,这地方从地理上属于广西,从交通上又离广州更近,属于两不管的灯下黑,成功率当然大些。

ChinaBaise
ChinaBaise

包邮

难怪敢吹出“江浙沪”包邮,这块区域肉眼可见的交通便利。

ChinaSuzhou
ChinaSuzhou

交通要津

传统的交通要道,如郑州、武汉等,也是肉眼可见的属于多边的交叉点。

ChinaZhengzhou ChinaWuhan

实现代码

在上文基础上,我们需要补充下列代码

# Clustering
clustering = SpectralClustering(n_clusters=15,
                                affinity='precomputed',
                                assign_labels='discretize')

_dist = dist.copy()
_dist[dist == np.inf] = 0

_map = dist > -1
for r in route:
    _map[r[0], r[1]] = False
    _map[r[1], r[0]] = False
_map
_dist[_map] = 0

label = clustering.fit_predict(_dist)

# Plot

links = []
for j, r in enumerate(route):
    a = nodes.loc[r[0]]
    b = nodes.loc[r[1]]
    l = str(label[r[0]])
    nodes.loc[r[0], 'label'] = l
    nodes.loc[r[1], 'label'] = l
    links.append((a[0], a[1], j, l))
    links.append((b[0], b[1], j, l))

nodes['name'] = df_all['name']
links = pd.DataFrame(links, columns=['x''y''group''label'])

# %%
size_kwargs = dict(
    width=600,
    height=500
)
fig1 = px.scatter(nodes, x='x', y='y', hover_name='name',
                  color='label', title='Scatter Plot', **size_kwargs)
fig1.show()
fig2 = px.line(links, x='x', y='y', line_group='group',
               color='label', **size_kwargs)
fig2.show()

# %%
fig = go.Figure()

for d in fig1.data:
    d['marker']['opacity'] = 0.2
    d['marker']['color'] = 'gray'
    fig.add_trace(d)

for d in fig2.data:
    fig.add_trace(d)

fig.update_layout({'title''Least Length Route',
                   'width'600'height'500})
fig.show()

张春成

2021/07/08  阅读:52  主题:默认主题

作者介绍

张春成