Loading...
墨滴

张春成

2021/07/09  阅读:33  主题:默认主题

所谓路径依赖

所谓路径依赖

继续图论。 本文将借用之前“过于简单粗暴”的图示来说明所谓“路径依赖”的问题。 往大了说,它代表一种全局和局部的矛盾关系。


简单回顾

前文《最小连通图》介绍了图论的基本设定,以及一种连通所有节点的方法; 前文《图的距离度量》介绍了一种简单的,基于最小连通图的节点之间距离度量方法; 前文《图的谱聚类》介绍了同样基于最小连通图距离度量的节点聚类方法。

但最小连通图这个东西,只是一种“简单粗暴”的连通方式

优势:所需要的边长之和全局最小;

劣势:局部效率的风险过大。

一句话来讲,我们可以说全局最优会损害局部利益。

路径依赖

我们不妨拽一个流行词来形容这个问题, 称为“路径依赖”,如下图所示

BadLocal
BadLocal

我们的目的是从节点86走到节点56, 这是两个十分靠近的节点,但其路径却出乎意料的长。 这是由于全局最短的路径并没有对这一局部提供足够的关注和支持。 或者从另一个角度来说,提供直接或较为靠近的连接这两个节点的路径, 会不可避免地提高全局长度。 为了说明这个问题,我们分别从“具体”和“抽象”两个维度进行展开。

具体依赖

把节点想象成地址,把路径想象成道路,我们不难得到这样一个推论

  • 如果要连通所有地点,而使所需的公路总里程最短,可以使用“最小连通图”方法;
  • 但这种方法不具有通行效率最优性,从而增加个体使用这个道路体系的成本。

抽象依赖

把节点想象成理念或知识,把路径想象成知识体系的逻辑链条,则有以下推论

  • 知识谱系的顶层设计若追求高速发展或弯道超车的全局最优,必然要满足路径全局最短原则;
  • 因此,使用这些技术体系的人,会不可避免地陷入局部低效的路径依赖困境;
  • 这种困境主要表现为,局中人在完成具体工作时,很难获得资源来完成一些看似简单而且必要的周边工作,从而造成可观的工作延迟和资源浪费。

这部分本想展开,但又觉得没啥意思,算了。

数据支持

我们就事论事,对“路径依赖”问题进行简单量化,如下图所示

Histogram Separation
Histogram Separation

上图画的是什么呢? 画的是全部节点对之间路径长度的直方图。

什么是直方图呢? 直方图就是取各种值的数量统计。

图中,红色是不同类别节点之间的距离统计;蓝色代表同类之内节点之间的距离统计。

这个类别是什么? 就是谱聚类得到的类别。

可以看到

  • 在全局最短的条件下,同类节点之间的距离较短,中值约为6
  • 而不同类别节点之间的距离则大大增加,中值约为20
  • 差值14就是路径依赖带来的成本。

这就是路径依赖带来的问题。

分析代码

分析代码较为简单,如下

# %%
# Separate Within- and Across-Labels Distances
across = []
within = []

n = len(nodes)

for j in range(n):
    for k in range(n):
        if j == k:
            continue

        v = dist_graph[j, k]

        if nodes['label'][j] == nodes['label'][k]:
            within.append(v)
        else:
            across.append(v)

# %%
# Plot Histogram of the Distances
df1 = pd.DataFrame(within)
df1.columns = ['y']
df1['name'] = 'within'

df2 = pd.DataFrame(across)
df2.columns = ['y']
df2['name'] = 'across'

df = pd.concat([df1, df2], axis=0, ignore_index=True)

fig = px.histogram(df, x='y', color='name', opacity=0.8,
                   title='Histogram of Separation')
fig.show()

张春成

2021/07/09  阅读:33  主题:默认主题

作者介绍

张春成