量化交易中文教材

第 23 章 最小生成树

本章对应原书第 23 章。最小生成树问题是：用总权重最小的一组边把所有顶点连起来。它是贪心算法能够得到全局最优的经典例子，两种标准算法——Kruskal 和 Prim——分别建立在上两章的并查集和优先队列之上。对量化读者，这一章有直接的用武之地：Mantegna 的"相关性网络最小生成树"是金融网络分析的经典工具，Kruskal 算法加边的过程与单链接层次聚类完全等价，而单链接聚类正是层次风险平价（HRP）的第一步。本章最后会从 MST 一路实现到 HRP。

学习目标

读完本章，你应当能够：

  1. 叙述最小生成树问题，理解"切割、横跨、尊重、轻量级边"四个概念，并用剪切粘贴法证明安全边定理（切割性质），以及与之配套的环性质。
  2. 写出 Kruskal 算法和 Prim 算法，说出它们分别用二叉堆、斐波那契堆、邻接矩阵实现时的复杂度，并能根据图的稠密程度选择实现。
  3. 说清 MST 与单链接层次聚类的等价关系：切掉最长的 \(k-1\) 条边得到 \(k\) 类，MST 路径上的最大边就是单链接距离（次优超度量）。
  4. 用 Mantegna 距离 \(d_{ij}=\sqrt{2(1-\rho_{ij})}\) 构造股票相关性 MST，解读中心节点、树长变化等指标。
  5. 完整实现层次风险平价的三步（树聚类、准对角化、递归二分），并说明它在什么情况下优于逆方差和样本最小方差组合，以及单链接带来的局限。

读前导读

这一章在解决什么问题。 90 只股票两两之间有 4005 个相关系数，大部分是噪声，人眼看不出结构。最小生成树（MST）的做法是：只保留 89 条"最强"的连接，既把所有股票连成一个整体，又不留任何冗余的环。留下来的这副"骨架"能清楚地显示哪些股票扎堆成行业、谁是行业的枢纽、市场在危机时如何"抱团"。更重要的是，它是层次风险平价（HRP）的第一步。HRP 你可能在 CFA 或业内文章里听说过：它不求协方差矩阵的逆，从而避开了均值—方差优化"估计误差最大化"的老问题。本章从算法一路讲到 HRP 的完整实现。

先用点和线把问题说清楚。 第 22 章说过，图就是点（顶点）和线（边）。本章的图有两个特点：

  • 无向、带权：每条线上标一个数字 \(w(u,v)\)，叫"权重"，可以理解为"连接成本"或"距离"。在股票网络中，点是股票，线的权重是由相关系数换算出的距离：越相关，距离越短。
  • 完全图：任意两只股票之间都有一条线（都有一个相关系数）。

树是"连通而且没有环"的图：所有点都能互相走到，但任意两点之间只有唯一一条路。有 \(n\) 个点的树恰好有 \(n-1\) 条线——少一条就断开，多一条就出现环。生成树是从原图的线里挑出 \(n-1\) 条、刚好构成一棵覆盖所有点的树；最小生成树是总权重最小的那一棵。股票版本就是"用总距离最短的 89 条线把 90 只股票串起来"，自然会优先保留相关性最高的那些连接。

需要先想起来的数学。

  • 向量、内积与长度。 向量 \(z=(z_1,\dots,z_T)\) 的长度是 \(\|z\|=\sqrt{z_1^2+\cdots+z_T^2}\)，两个向量的内积 \(z_i^{\mathsf T}z_j=\sum_t z_{it}z_{jt}\)。把收益序列标准化后，内积就是相关系数——这是 Mantegna 距离公式的来源。见 第 00 册第 06 章 线性代数速成。
  • 协方差矩阵、逆与条件数。 组合方差 \(w^{\mathsf T}\Sigma w\) 你很熟悉。最小方差组合要用 \(\Sigma^{-1}\)；当股票数接近样本天数时，\(\Sigma\) 的估计接近"奇异"（不可逆），求逆会把小的估计误差放大成大的权重误差。条件数就是衡量这种放大倍数的指标。\(\mathrm{diag}(\Sigma)\) 表示只取对角线上的方差、其余置零。同见第 06 章。
  • 集合与切割记号。 \(V-S\) 是"\(V\) 里不在 \(S\) 中的元素"；\(T-\{(x,y)\}\cup\{(u,v)\}\) 是"从 \(T\) 里拿掉边 \((x,y)\)，再放进边 \((u,v)\)"；\(\subseteq\) 是"包含于"。见 第 00 册第 08 章 读懂数学证明与符号。
  • 贪心与交换论证。 本章的核心证明（切割性质）就是第 16 章交换论证的一个实例：拿一棵假想的最优树，换一条边，证明不会变差。
  • 并查集与优先队列。 Kruskal 用第 21 章的并查集判断"加这条边会不会成环"；Prim 用优先队列（堆）每次取出最小者，堆在本册第 06 章介绍。

怎么读这一章。 23.1 必读。23.2 是理论核心：四个概念（切割、横跨、尊重、轻量级边）和定理 23.1 的证明值得认真读一遍，其余 23.2.4 的事实列表可以只看"环性质"和"边权多重集相同"两条。23.3 Kruskal 最直观，必读。23.4 Prim 第一次可以只看算法思路和复杂度表格里"稠密图用矩阵版"这一行。23.5 可以跳过。23.6 是量化读者的重点：23.6.1 的距离公式、23.6.2 的三条等价关系、23.6.3 的 HRP 三步，建议对照 23.6.5 的结果解读一起读。代码第一次可以只看输出。

23.1 问题

23.1.1 定义

原书以电路设计引出问题：要把 \(n\) 个引脚连成电气上等价，用 \(n-1\) 根导线即可，希望导线总长最短。抽象成图：连通无向图 \(G=(V,E)\)，每条边 \((u,v)\) 有权重 \(w(u,v)\)，求一个无环的边子集 \(T\subseteq E\)，它连接所有顶点，并使

\[w(T)=\sum_{(u,v)\in T}w(u,v)\]

最小。\(T\) 无环且连接所有顶点，必然是一棵树，称为生成树（spanning tree）；所求的就是最小生成树（minimum spanning tree, MST）。所有生成树都恰好有 \(|V|-1\) 条边，"最小"指的是总权重最小。

原书图 23.1 的例子（本章反复使用）：顶点 a–i，边权为 a-b 4、a-h 8、b-c 8、b-h 11、c-d 7、c-f 4、c-i 2、d-e 9、d-f 14、e-f 10、f-g 2、g-h 1、g-i 6、h-i 7。一棵 MST 是 {g-h 1, c-i 2, f-g 2, a-b 4, c-f 4, c-d 7, b-c 8, d-e 9}，总权 37。MST 不一定唯一：把 (b,c) 换成 (a,h) 得到另一棵总权 37 的 MST。

白话解释：为什么生成树一定恰好 \(|V|-1\) 条边？从 \(|V|\) 个孤立的点出发，每加一条连接两个不同"团"的线，团的个数减 1；要把 \(|V|\) 个团并成 1 个，正好需要 \(|V|-1\) 条线。多加一条，它两端已经在同一团里，必然形成环。 小例子：三只股票 A、B、C，距离 A–B 0.3、B–C 0.5、A–C 0.9。生成树只能有 2 条边，可选 {AB, BC}（总 0.8）、{AB, AC}（总 1.2）、{BC, AC}（总 1.4）。MST 是 {AB, BC}：最远的那条 A–C 被丢掉，因为 A 和 C 已经可以通过 B 间接连上。

23.1.2 本章路线

两种算法 Kruskal 和 Prim 用二叉堆都能做到 \(O(E\lg V)\)；Prim 用斐波那契堆可以做到 \(O(E+V\lg V)\)。两者都是贪心算法：每一步选当前看起来最好的边。贪心一般不保证全局最优，但对 MST 可以证明某些贪心策略一定得到最小权生成树。根本原因是图的森林构成一个拟阵（原书 16.4 节，本册由其他章节介绍），这里我们直接用切割性质证明。

白话解释：本册第 16 章 16.4 节就是拟阵一节（其中"图拟阵"和"最小生成树可以化归为加权拟阵上的贪心"两段与这里直接对应），没读过也不影响本章，因为下面会用切割性质单独证明。"森林"指没有环、但不一定连通的一组边，也就是若干棵树并排放着。

23.2 通用方法与切割性质

23.2.1 通用方法

维护一个边集 \(A\)，保持如下循环不变式：

每次迭代之前，\(A\) 是某棵最小生成树的子集。

每一步找一条边 \((u,v)\)，使 \(A\cup\{(u,v)\}\) 仍是某棵 MST 的子集。这样的边称为 \(A\) 的安全边（safe edge）。

def GENERIC_MST(G, w):
    A = set()
    while A does not form a spanning tree:
        find an edge (u, v) that is safe for A
        A = A | {(u, v)}
    return A

初始化时 \(A=\varnothing\) 显然满足不变式；每步只加安全边，不变式保持；终止时 \(A\) 是一棵生成树且包含于某棵 MST，所以它就是 MST。只要 \(A\) 还不是生成树，安全边一定存在（某棵包含 \(A\) 的 MST 里还有不在 \(A\) 中的边）。难点在于高效地找到它。

23.2.2 切割与轻量级边

  • 切割（cut）\((S,V-S)\) 是顶点集 \(V\) 的一个划分。
  • 若边 \((u,v)\) 的一个端点在 \(S\)、另一个在 \(V-S\)，称它横跨（crosses）该切割。
  • 若边集 \(A\) 中没有边横跨某切割，称该切割尊重（respects）\(A\)。
  • 横跨某切割的边中权重最小的称为该切割的轻量级边（light edge），可能因平局而不唯一。

白话解释：切割就是"把所有股票随便分成两堆"，比如 \(S=\) {银行股}、\(V-S=\) {其他所有股票}。横跨切割的边就是"一端是银行股、另一端不是"的那些连接。轻量级边是这些跨堆连接里距离最短的一条，也就是"银行股与非银行股之间最相关的那一对"。"切割尊重 \(A\)"是说已经选进来的边都不跨堆——已选的连接要么全在银行股内部，要么全在外部。 切割性质的直观含义：任何一种分堆方式下，两堆之间最短的那条桥一定可以放进某棵 MST。因为两堆总要至少有一座桥连起来，选最短的那座不会吃亏。

定理 23.1（安全边判定，即切割性质）　设 \(G\) 是连通无向带权图，\(A\) 包含于某棵 MST，\((S,V-S)\) 是尊重 \(A\) 的任一切割，\((u,v)\) 是横跨该切割的一条轻量级边，则 \((u,v)\) 对 \(A\) 是安全的。

证明（剪切粘贴法 cut-and-paste）：设 \(T\) 是包含 \(A\) 的 MST。若 \((u,v)\in T\)，已证完。否则把 \((u,v)\) 加入 \(T\)，它与 \(T\) 中从 \(u\) 到 \(v\) 的简单路径 \(p\) 构成一个环（原书图 23.3）。\(u\) 和 \(v\) 在切割两侧，所以 \(p\) 上至少有一条边 \((x,y)\) 也横跨切割；切割尊重 \(A\)，所以 \((x,y)\notin A\)。从 \(T\) 中删去 \((x,y)\)，树分成两块，再加入 \((u,v)\) 重新连上，得到新的生成树

\[T'=T-\{(x,y)\}\cup\{(u,v)\}.\]

因为 \((u,v)\) 是轻量级边，\(w(u,v)\le w(x,y)\)，所以

\[w(T')=w(T)-w(x,y)+w(u,v)\le w(T).\]

\(T\) 已经最小，故 \(T'\) 也是 MST。又 \(A\subseteq T'\)，所以 \(A\cup\{(u,v)\}\subseteq T'\)，\((u,v)\) 是安全边。

推导拆解：证明的逻辑是"换一条边不吃亏"，分四步。 第一步：已知有一棵最优树 \(T\) 包含 \(A\)，但可能不包含我们想加的 \((u,v)\)。 第二步：把 \((u,v)\) 硬塞进 \(T\)。树里任意两点之间本来就有唯一一条路，再加一条直连线就成了环。 第三步：这个环从切割的一侧（\(u\) 所在的 \(S\)）出发，最后回到另一侧（\(v\)），中途必须至少再跨一次切割，跨的那条边记作 \((x,y)\)。因为切割尊重 \(A\)，\((x,y)\) 不在 \(A\) 中，拿掉它不会破坏已选的边。 第四步：拿掉 \((x,y)\)，环断开，又变回一棵树 \(T'\)。\((u,v)\) 是跨切割的边里最轻的，所以 \(w(u,v)\le w(x,y)\)，新树总权重不增。\(T\) 本来就最小，\(T'\) 不可能更小，只能相等，所以 \(T'\) 也是最优树，而且它同时包含 \(A\) 和 \((u,v)\)。 金融直觉：类似组合优化里的"替换论证"：如果最优组合里某个持仓可以被一个风险更低、其余条件相同的替代品换掉，换完结果不会更差，所以总存在一个包含该替代品的最优组合。

23.2.3 推论与森林视角

算法执行过程中 \(A\) 始终无环，\(G_A=(V,A)\) 是一个森林，开始时是 \(|V|\) 棵单顶点树。安全边总是连接 \(G_A\) 中两个不同的分量，每加一条边树的个数减 1，循环恰好执行 \(|V|-1\) 次。

推论 23.2　设 \(A\) 包含于某棵 MST，\(C\) 是森林 \(G_A\) 中的一棵树。若 \((u,v)\) 是连接 \(C\) 与 \(G_A\) 中另一棵树的轻量级边，则 \((u,v)\) 对 \(A\) 安全。（取切割 \((V_C,V-V_C)\) 即可。）

23.2.4 环性质与其他事实

原书 23.1 节习题里有几条非常有用的结论：

  • 环性质（23.1-5）：若 \(e\) 是某个环上权重最大的边，则 \(G-e\) 有一棵 MST 也是 \(G\) 的 MST。也就是说，环上的最重边可以放心排除。
  • 最轻边（23.1-1）：全图权重最小的边一定属于某棵 MST。
  • 逆命题不成立（23.1-2）：安全边不一定是某个特定切割的轻量级边。
  • 唯一性（23.1-6）：若每个切割的轻量级边都唯一，则 MST 唯一；边权互不相同时 MST 唯一。逆命题不成立。
  • 边权多重集相同（23.1-8）：同一个图的所有 MST，其边权排序后的列表完全相同。这一点对聚类很重要：不论平局怎么打破，单链接的合并高度序列不变。
  • 动态更新（23.1-11）：把一条非树边的权重降低后，把它加入 MST 形成一个环，删去环上最重的边即可，\(O(V)\)。

23.3 Kruskal 算法

23.3.1 算法

Kruskal 算法中 \(A\) 是一个包含所有顶点的森林。它把所有边按权重从小到大考察：若当前边连接森林中两棵不同的树，就加入；否则（两端已在同一棵树中，加入会成环）就跳过。设加入的边 \((u,v)\) 连接树 \(C_1\) 与 \(C_2\)，它是连接 \(C_1\) 与其他树的轻量级边（更轻的边都已考察过，要么已加入、要么在树内部），由推论 23.2 它是安全边。

判断"两端是否在同一棵树中"正是上一章并查集的工作：

def MST_KRUSKAL(G, w):
    A = set()
    for v in G.V:
        MAKE_SET(v)
    for (u, v) in sorted(G.E, key=w):      # 按权非降序
        if FIND_SET(u) != FIND_SET(v):     # 两端在不同的树中
            A.add((u, v))
            UNION(u, v)
    return A

23.3.2 例子

在图 23.1 上运行（原书图 23.4）：依次考察 (h,g)1 加入、(c,i)2 加入、(g,f)2 加入、(a,b)4 加入、(c,f)4 加入、(i,g)6 跳过（成环）、(c,d)7 加入、(h,i)7 跳过、(a,h)8 和 (b,c)8 中先考察的那条加入、另一条跳过、(d,e)9 加入，其余 (e,f)10、(b,h)11、(d,f)14 都跳过。

白话解释：Kruskal 就是"把所有连接按距离从短到长排好，从头往下看：两端还不在同一团，就连上；已经在同一团，就跳过"。以 (i,g)6 为例：此前 i 已经通过 c–i、c–f、f–g 连到了 g，i 和 g 已在同一团，再连就成环，所以跳过。 金融直觉：在股票网络上这就是"先连最相关的一对，再连次相关的一对……"，每连一次，两个小组并成一个大组。这个过程与上一章用并查集做相关性阈值分组完全相同，只是这里把阈值从严到松一路放宽，并把每一步都记录下来。

23.3.3 复杂度

用按秩合并加路径压缩的并查集：排序 \(O(E\lg E)\)；\(|V|\) 次 MAKE-SET 和 \(O(E)\) 次 FIND-SET、UNION 共 \(O((V+E)\,\alpha(V))\)。图连通，\(|E|\ge|V|-1\)，并查集部分为 \(O(E\,\alpha(V))\)。又 \(\alpha(V)=O(\lg E)\)，总时间 \(O(E\lg E)\)；因为 \(|E|<|V|^2\)，\(\lg E=O(\lg V)\)，可以写成

\[O(E\lg V).\]

瓶颈在排序。若边已经有序，或者边权是小整数可以用计数排序（原书 23.2-4），Kruskal 就是 \(O(E\,\alpha(V))\)，近乎线性。

23.4 Prim 算法

23.4.1 算法

Prim 算法中 \(A\) 始终是一棵树：从任意根 \(r\) 出发，每一步加入一条连接"树"与"树外某个顶点"的轻量级边，直到覆盖所有顶点。由推论 23.2，每一步都是安全边。它与 Dijkstra 最短路算法几乎一模一样。

实现的关键是快速找到这条边。把所有不在树中的顶点放在一个以 key 为关键字的最小优先队列 \(Q\) 中：\(v.key\) 是 \(v\) 与树中顶点之间所有边的最小权重（没有这样的边时为 \(\infty\)），\(v.\pi\) 是对应的树中端点。

def MST_PRIM(G, w, r):
    for u in G.V:
        u.key = float('inf'); u.pi = None
    r.key = 0                            # 保证根最先被取出
    Q = MinPriorityQueue(G.V, key=lambda v: v.key)
    while Q:
        u = Q.extract_min()              # u 关联横跨切割 (V-Q, Q) 的一条轻量级边
        for v in G.Adj[u]:
            if v in Q and w(u, v) < v.key:
                v.pi = u
                v.key = w(u, v)          # 隐含一次 DECREASE-KEY

算法隐式维护 \(A=\{(v,v.\pi):v\in V-\{r\}-Q\}\)，结束时 \(Q\) 为空，MST 就是 \(\{(v,v.\pi):v\in V-\{r\}\}\)。

循环不变式（每次 while 迭代之前）：(1) \(A=\{(v,v.\pi):v\in V-\{r\}-Q\}\)；(2) 已放入 MST 的顶点恰为 \(V-Q\)；(3) 对所有 \(v\in Q\)，若 \(v.\pi\ne\) NIL，则 \(v.key<\infty\)，且 \(v.key\) 是把 \(v\) 连到树中某个顶点的轻量级边 \((v,v.\pi)\) 的权重。取出 \(u\) 就是把 \((u,u.\pi)\) 加入 \(A\)；随后的 for 循环更新 \(u\) 的邻居的 key，维持第 (3) 条。

例子（原书图 23.5，根为 a）：依次加入 (a,b)4；此时 (b,c)8 与 (a,h)8 都是轻量级边，任选其一（图中选 (b,c)）；然后 (c,i)2、(c,f)4、(f,g)2、(g,h)1、(c,d)7、(d,e)9。

白话解释：Prim 像"滚雪球"：从一个点出发，每次把"离雪球最近的那个外部点"吸进来。v.key 记的是"点 \(v\) 到当前雪球的最短距离"，v.pi 记的是"雪球里离 \(v\) 最近的是谁"。每吸进一个新点 \(u\)，就检查 \(u\) 的邻居：如果经由 \(u\) 离雪球更近，就更新它们的 key。 以上例开头为例：从 a 出发，b 的 key 为 4、h 的 key 为 8，先吸进 b；b 带来 c（key 8），h 的 key 仍为 8（b–h 是 11，没变小）；两者平局，图中选了 c。 与 Kruskal 的区别：Kruskal 同时在各处"多点开花"，各个小团最后合并；Prim 始终只有一个团在长大。结果都是 MST，但 Prim 的加边顺序不是"由近到远"，所以不能直接当作聚类的合并顺序。

23.4.2 复杂度取决于优先队列

实现 EXTRACT-MIN DECREASE-KEY 总时间 适用
二叉最小堆 \(O(\lg V)\)，共 \(V\) 次 \(O(\lg V)\)，至多 \(E\) 次 \(O(E\lg V)\) 一般稀疏图
斐波那契堆 摊还 \(O(\lg V)\) 摊还 \(O(1)\) \(O(E+V\lg V)\) 理论最优；\(\lvert E\rvert=\omega(V)\) 时渐近更快
邻接矩阵 + 线性扫描 \(O(V)\) \(O(1)\) \(O(V^2)\) 稠密图（如完全图）
二叉堆 + 懒惰删除 \(O(\lg E)\) 用重新插入代替 \(O(E\lg V)\) 工程常用，heapq 即可

几点说明：

  • "\(v\in Q\)"的判断用每个顶点一个布尔标志即可 \(O(1)\)。
  • 邻接矩阵版本（原书 23.2-2）每轮线性扫描所有顶点找最小 key，共 \(|V|\) 轮，\(O(V^2)\)。对 \(|E|=\Theta(V^2)\) 的稠密图，它与斐波那契堆版本同阶，但常数小得多、实现简单得多。股票相关性网络是完全图，正好用这个版本。
  • 原书 23.2-3 的结论：稀疏图（\(|E|=\Theta(V)\)）上斐波那契堆并不比二叉堆渐近更快；稠密图上更快。
  • 边权是 \(1\) 到 \(|V|\) 的整数时，Prim 可用 vEB 树做到 \(O(E\lg\lg V)\)；边权不超过常数 \(W\) 时用桶数组做到 \(O(E)\)（原书 23.2-5）。

23.4.3 Kruskal 还是 Prim

两者渐近复杂度相同，选择主要看数据形态：边已排序或边权是小整数、图稀疏、需要中间的森林结构（比如做聚类）时用 Kruskal；图稠密、以矩阵形式给出时用 \(O(V^2)\) 的 Prim。还有一个常被忽略的区别：Kruskal 的加边顺序就是单链接聚类的合并顺序，而 Prim 的加边顺序与聚类没有直接关系，需要事后对边排序。

23.5 思考题与注记选讲

  • 23-1 次优最小生成树：边权互异时 MST 唯一，但次优 MST 不一定唯一。关键结论是次优 MST 只需与 MST 交换一条边。预先用 \(O(V^2)\) 时间算出树上任意两点间路径的最大边 \(\max[u,v]\)（从每个顶点做一次 BFS/DFS），再枚举非树边 \((x,y)\)，取 \(w(x,y)-w(\max[x,y])\) 最小者，总计 \(O(V^2)\)。
  • 23-2 稀疏图上的 MST：预处理 MST-REDUCE 让每个顶点选它最轻的关联边并收缩，顶点数至少减半，\(O(E)\) 时间；做 \(k=\lg\lg V\) 轮后再跑斐波那契堆 Prim，总时间 \(O(E\lg\lg V)\)。原书注记指出，最早的 MST 算法——Borůvka 1926 年的算法——相当于反复做 MST-REDUCE，共 \(O(\lg V)\) 轮。Borůvka 算法每轮的工作天然可以并行，是分布式和 GPU 上求 MST 的常用方法。
  • 23-3 瓶颈生成树：最大边权在所有生成树中最小的生成树。MST 一定是瓶颈生成树；判断瓶颈值是否不超过 \(b\)，只需保留权重不超过 \(b\) 的边并检查连通性。更强的事实是：MST 上任意两点之间路径的最大边，是所有连接这两点的路径中最大边的最小值（minimax 路径）。下一节会看到，这正是单链接距离。
  • 23-4 其他 MST 算法：(a) 按权重从大到小考察边，若删去后图仍连通就删去——正确（"反向删除"，环性质的应用）；(b) 按任意顺序加边、不成环就加——错误，只得到某棵生成树；(c) 按任意顺序加边，一旦成环就删去环上最重的边——正确（环性质），可以用动态树高效实现。
  • 注记：Prim 算法其实 Jarník 在 1930 年就提出了。\(|E|=\Omega(V\lg V)\) 时斐波那契堆 Prim 是 \(O(E)\)；更稀疏的图上有 Fredman–Tarjan 的 \(O(E\lg^*V)\)、Gabow 等人的 \(O(E\lg\lg^*V)\)、Chazelle 的 \(O(E\,\hat\alpha(E,V))\)；Karger–Klein–Tarjan 给出了期望 \(O(V+E)\) 的随机算法。

23.6 量化实战：从相关性 MST 到层次风险平价

23.6.1 Mantegna 的相关性最小生成树

Mantegna（1999）提出用 MST 提取股票市场的层次结构。做法是把相关系数变成距离：

\[d_{ij}=\sqrt{2(1-\rho_{ij})}.\]

这不是随意的选择。把股票 \(i\) 的收益序列标准化并除以 \(\sqrt T\)，得到单位长度向量 \(z_i\)，则 \(\rho_{ij}=z_i^{\mathsf T}z_j\)，于是

\[\|z_i-z_j\|^2=\|z_i\|^2+\|z_j\|^2-2z_i^{\mathsf T}z_j=2(1-\rho_{ij}).\]

推导拆解： 第一步，标准化：\(z_{it}=\dfrac{r_{it}-\bar r_i}{\sigma_i\sqrt T}\)（用除以 \(T\) 的总体标准差 \(\sigma_i\)），即先减均值、再除以标准差，再除以 \(\sqrt T\)。这样 \(\|z_i\|^2=\sum_t z_{it}^2=\frac{1}{T\sigma_i^2}\sum_t(r_{it}-\bar r_i)^2=1\)，每个向量长度为 1。 第二步，内积等于相关系数：\(z_i^{\mathsf T}z_j=\frac{1}{T\sigma_i\sigma_j}\sum_t(r_{it}-\bar r_i)(r_{jt}-\bar r_j)=\frac{\mathrm{Cov}(r_i,r_j)}{\sigma_i\sigma_j}=\rho_{ij}\)。 第三步，展开距离平方：\(\|z_i-z_j\|^2=\sum_t(z_{it}-z_{jt})^2=\sum_t z_{it}^2+\sum_t z_{jt}^2-2\sum_t z_{it}z_{jt}\)，这和 \((a-b)^2=a^2+b^2-2ab\) 是同一个展开，代入前两步得 \(1+1-2\rho_{ij}\)。 几何直觉：每只股票是单位球面上的一个点，相关系数是两点夹角的余弦，\(d_{ij}\) 是两点之间的直线距离。完全正相关时两点重合，完全负相关时位于球的两端。

所以 \(d_{ij}\) 就是标准化收益向量之间的欧氏距离，满足三角不等式，是一个真正的度量。\(\rho=1\) 时 \(d=0\)，\(\rho=0\) 时 \(d=\sqrt2\)，\(\rho=-1\) 时 \(d=2\)。López de Prado 在 HRP 中用的 \(\sqrt{(1-\rho)/2}\) 只差一个常数倍，得到的 MST 和单链接树完全相同——MST 只依赖边权的相对顺序，对距离做任何单调变换都不改变它。

在 \(N\) 只股票的完全图上求 MST，得到 \(N-1\) 条边的"市场骨架"。常用的解读有：

  • 中心节点：MST 中度数高的股票往往是行业龙头或与大盘高度同步的股票，可以作为行业代表或对冲工具。
  • 行业结构：同行业股票在树上倾向于聚成一枝；不按官方行业、而按 MST 分枝来分组，就是一种统计行业分类。
  • 树长与市场状态：危机时市场因子主导，所有股票相关性升高，距离变小，MST 的总长度和平均边长明显缩短，结构也更集中——这可以作为市场"同涨同跌"程度的指标。
  • 过滤噪声：\(N(N-1)/2\) 个相关系数中大多是噪声，MST 只保留 \(N-1\) 条最强的连接。它的推广平面最大过滤图（PMFG）保留 \(3(N-2)\) 条边，信息更多。

23.6.2 MST 就是单链接聚类

单链接层次聚类（single-linkage clustering）从每个点自成一类开始，每次合并"最近的两类"，两类之间的距离定义为它们之间最近的那对点的距离。把这个过程和 Kruskal 算法对照：Kruskal 按距离从小到大考察边，边的两端若在不同的树里就合并——这正是"合并当前最近的两类"。因此：

  1. 单链接的合并高度序列 = MST 的边权排序后的序列；
  2. 把 MST 中最长的 \(k-1\) 条边切断，剩下的 \(k\) 个连通分量就是单链接聚类的 \(k\) 个类；
  3. 两只股票 \(i,j\) 的单链接距离（它们第一次被合并到同一类时的高度）等于 MST 上 \(i\) 到 \(j\) 路径中最长的那条边。这个距离称为次优超度量（subdominant ultrametric），它满足比三角不等式更强的 \(d^<(i,j)\le\max\{d^<(i,k),d^<(k,j)\}\)，是所有不超过原距离的超度量中最大的一个。由思考题 23-3 的 minimax 性质，它也是所有连接 \(i,j\) 的路径上"最大一步"的最小值。

白话解释：第 3 条用一个例子看最清楚。设 MST 上有一条路径 工商银行 —0.3— 建设银行 —0.5— 招商银行 —0.9— 平安银行。工商银行和平安银行的单链接距离不是它们的直接距离，而是这条路径上最长的一步 0.9：阈值放宽到 0.9 之前，两者分属不同的组；放宽到 0.9 的那一刻，最后一座"桥"连通，它们才被并进同一组。 "超度量"不等式 \(d^<(i,j)\le\max\{d^<(i,k),d^<(k,j)\}\) 比三角不等式强：三角不等式说"绕路不比直达更近"，即 \(d(i,j)\le d(i,k)+d(k,j)\)；超度量把右边的"加"换成"取较大者"，意味着任何三点中，最大的两个距离必须相等。这正是"层次结构"的数学刻画：同一子组内的两只股票，到组外任一股票的距离都相同。

上一章并查集的阈值分组，就是这里在某一高度切割的结果。所以链式效应（两个类只要有一对点靠得近就整体合并）也是 MST 聚类和 HRP 第一步的固有特点。

23.6.3 层次风险平价（HRP）

经典的均值–方差最小方差组合需要求协方差矩阵的逆。当股票数 \(N\) 与样本长度 \(T\) 相近时，样本协方差矩阵的条件数很大，求逆会放大估计误差，得到的权重极端、不稳定、样本外表现差（数值优化与病态问题见第 04 册，多元波动率与协方差建模见第 06 册）。López de Prado（2016）提出的层次风险平价（Hierarchical Risk Parity, HRP）完全不求逆，分三步：

第一步：树聚类。 由相关系数计算距离 \(d_{ij}=\sqrt{(1-\rho_{ij})/2}\)，做单链接层次聚类，即求 MST。（原论文在聚类前还把距离矩阵的每一列当作向量，再计算一次列与列之间的欧氏距离；不少开源实现省略这一步，本章代码也省略。）

第二步：准对角化（quasi-diagonalization）。按聚类树的叶子顺序重排协方差矩阵的行和列，使相关性强的股票排在一起，大的协方差元素集中到对角线附近。

第三步：递归二分（recursive bisection；其递归式与复杂度分析见第 04b 章）。把排好序的股票列表从中间一分为二。对每一半，用"组内逆方差权重"算出这一半作为一个子组合的方差 \(V_1,V_2\)：

\[\tilde w=\frac{\mathrm{diag}(\Sigma_i)^{-1}}{\mathbf 1^{\mathsf T}\mathrm{diag}(\Sigma_i)^{-1}},\qquad V_i=\tilde w^{\mathsf T}\Sigma_i\,\tilde w.\]

然后按风险反比分配权重：左半边乘以 \(\alpha=1-\dfrac{V_1}{V_1+V_2}\)，右半边乘以 \(1-\alpha\)。对每一半递归，直到只剩单只股票。

推导拆解：用 4 只股票走一遍。排好序后是 [A, B | C, D]，方差分别为 0.04、0.04、0.01、0.01（年化波动 20%、20%、10%、10%）。 组内逆方差权重：左半边 A、B 方差相同，\(\tilde w=(0.5,0.5)\)；若 A、B 相关系数为 0.8，则 \(V_1=0.25\times0.04+0.25\times0.04+2\times0.25\times0.8\times0.04=0.036\)。右半边同理，设 C、D 相关 0.8，\(V_2=0.009\)。 分配：\(\alpha=1-\frac{0.036}{0.045}=0.2\)，左半边拿 20%，右半边拿 80%。注意 \(\alpha=\frac{V_2}{V_1+V_2}\)，即"对方的方差占比"，方差越大的一半拿得越少，这就是"风险反比"。 再对每一半递归：A、B 各拿 \(0.2\times0.5=0.1\)，C、D 各拿 \(0.8\times0.5=0.4\)。 公式里 \(\mathrm{diag}(\Sigma_i)^{-1}\) 是"只用各自方差的倒数"，分母 \(\mathbf 1^{\mathsf T}\mathrm{diag}(\Sigma_i)^{-1}\) 是这些倒数之和（\(\mathbf 1\) 是全 1 向量），作用是把权重归一化到和为 1。整个过程只对对角线上的单个数字求倒数，从不对整个矩阵求逆，这就是 HRP 数值稳健的原因。

直观上，HRP 先在"大类之间"按风险分配，再在类内部分配。如果市场里有一大群高度相关的股票（比如同一个行业扎堆了 40 只），等权或逆方差组合会给这一群很高的总权重，而它们其实只相当于一个风险来源；HRP 在树的上层就把这一群当作一个整体，只给它与其他大类相当的风险预算。它全程只用到对角元素求逆，数值上非常稳健，而且权重全为正。

它的局限也要清楚：单链接带来的链式效应会让树的形状对少数几个相关系数很敏感；第三步按列表长度对半切分，而不是沿着聚类树的真实分叉切分（后续文献有沿树切分的改进版本）；它不使用期望收益，只是一个风险分配方法。在资产之间没有明显层次结构时，它并不比简单方法更好。下面的实验会同时展示这两种情形。

23.6.4 代码

代码分三部分：

  1. 在原书图 23.1 上实现并验证 Kruskal（含路径减半的并查集）和 Prim（二叉堆 + 懒惰删除）；
  2. 模拟 3 个板块、9 个行业、90 只股票的收益，用 \(O(V^2)\) 的稠密 Prim 求 Mantegna MST，与 scipy 对照；统计中心节点和同行业边比例；验证"切掉最长 \(k-1\) 条边 = 单链接 \(k\) 类"和"MST 边权 = 单链接合并高度"；比较平静期与危机期的树长；
  3. 实现 HRP，在两种真实协方差结构下，各用 200 次独立的 120 天样本估计协方差，比较等权、逆方差、样本最小方差和 HRP 的样本外波动（用真实协方差 \(w^{\mathsf T}\Sigma w\) 评价，排除样本外抽样噪声）。
import numpy as np, heapq
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.cluster.hierarchy import linkage, fcluster, leaves_list
from scipy.spatial.distance import squareform
from sklearn.metrics import adjusted_rand_score

# ======== 1. Kruskal 与 Prim：在原书图 23.1 上验证 ========
class DSU:
    def __init__(s, n): s.p = list(range(n)); s.r = [0]*n
    def find(s, x):
        while s.p[x] != x: s.p[x] = s.p[s.p[x]]; x = s.p[x]   # 路径减半
        return x
    def union(s, a, b):
        a, b = s.find(a), s.find(b)
        if a == b: return False
        if s.r[a] < s.r[b]: a, b = b, a
        s.p[b] = a; s.r[a] += s.r[a] == s.r[b]; return True

def kruskal(n, edges):                       # edges: [(w, u, v)]
    dsu, T = DSU(n), []
    for w, u, v in sorted(edges):            # 按权非降序
        if dsu.union(u, v): T.append((u, v, w))
    return T

def prim_dense(W):                           # W: 稠密权矩阵，O(V^2)，适合完全图
    n = len(W); in_tree = np.zeros(n, bool)
    key = np.full(n, np.inf); pi = np.full(n, -1); key[0] = 0
    for _ in range(n):
        u = int(np.argmin(np.where(in_tree, np.inf, key)))   # 线性扫描找最小 key
        in_tree[u] = True
        upd = (~in_tree) & (W[u] < key)
        key[upd] = W[u][upd]; pi[upd] = u
    return [(int(pi[v]), v, W[v, pi[v]]) for v in range(1, n)]

def prim_heap(n, adj, r=0):                  # adj[u] = [(w, v)]，二叉堆 + 懒惰删除
    in_tree = [False]*n; T = []; pq = [(0, r, -1)]
    while pq:
        w, u, p = heapq.heappop(pq)
        if in_tree[u]: continue              # 过期条目：代替 DECREASE-KEY
        in_tree[u] = True
        if p >= 0: T.append((p, u, w))
        for wv, v in adj[u]:
            if not in_tree[v]: heapq.heappush(pq, (wv, v, u))
    return T

names = "abcdefghi"; ix = {c: i for i, c in enumerate(names)}
E = [("a","b",4),("a","h",8),("b","c",8),("b","h",11),("c","d",7),("c","f",4),("c","i",2),
     ("d","e",9),("d","f",14),("e","f",10),("f","g",2),("g","h",1),("g","i",6),("h","i",7)]
edges = [(w, ix[u], ix[v]) for u, v, w in E]
adj = [[] for _ in names]
for w, u, v in edges: adj[u].append((w, v)); adj[v].append((w, u))
Tk = kruskal(9, edges); Tp = prim_heap(9, adj)
fmt = lambda T: " ".join(f"{names[u]}{names[v]}:{w}" for u, v, w in T)
print("Kruskal:", fmt(Tk), "| 总权", sum(w for *_, w in Tk))
print("Prim   :", fmt(Tp), "| 总权", sum(w for *_, w in Tp))

# ======== 2. Mantegna 相关性 MST：模拟 3 个板块、9 个行业、90 只股票 ========
def simulate(T, mkt_vol, rng, n_sec=3, ind_per_sec=3, per_ind=10):
    K = n_sec*ind_per_sec; N = K*per_ind
    ind = np.repeat(np.arange(K), per_ind); sec = ind // ind_per_sec
    m = rng.normal(0, mkt_vol, (T, 1))
    S = rng.normal(0, 0.006, (T, n_sec)); I = rng.normal(0, 0.006, (T, K))
    R = m + S[:, sec] + I[:, ind] + rng.normal(0, 0.012, (T, N))
    return R, ind

rng = np.random.default_rng(23)
R, ind = simulate(500, 0.008, rng)
C = np.corrcoef(R.T); N = len(C)
D = np.sqrt(2*(1 - C)); np.fill_diagonal(D, 0)          # Mantegna 距离

T_mst = prim_dense(D)
w_scipy = minimum_spanning_tree(D).sum()
print(f"\nN={N}: 自写 Prim 总长 {sum(w for *_, w in T_mst):.6f} | scipy 总长 {w_scipy:.6f}")

deg = np.zeros(N, int)
for u, v, _ in T_mst: deg[u] += 1; deg[v] += 1
hub = np.argsort(-deg)[:5]
print("度数最高的 5 只股票(所属行业):", [(int(h), int(ind[h]), int(deg[h])) for h in hub])
same = np.mean([ind[u] == ind[v] for u, v, _ in T_mst])
print(f"MST 中同行业边的比例: {same:.2f}")

# 切掉最长的 k-1 条边 = 单链接聚类成 k 类
k = 9
keep = sorted(T_mst, key=lambda e: e[2])[:N - k]
dsu = DSU(N)
for u, v, _ in keep: dsu.union(u, v)
lab_mst = np.array([dsu.find(i) for i in range(N)])
Z = linkage(squareform(D, checks=False), method="single")
lab_sl = fcluster(Z, t=k, criterion="maxclust")
print("MST 断边聚类 与 单链接 maxclust 一致:", adjusted_rand_score(lab_mst, lab_sl) == 1.0,
      f"| 与真实行业 ARI={adjusted_rand_score(ind, lab_mst):.3f}")
print("Kruskal 合并高度 == 单链接 Z 的合并高度:",
      np.allclose(sorted(w for *_, w in T_mst), np.sort(Z[:, 2])))

# 危机期：市场因子波动放大，树"收缩"
for label, mv in [("平静期", 0.006), ("危机期", 0.025)]:
    Rr, _ = simulate(250, mv, np.random.default_rng(7))
    Dr = np.sqrt(2*(1 - np.corrcoef(Rr.T)))
    L = minimum_spanning_tree(Dr).data
    print(f"{label}: 市场波动 {mv:.3f}, MST 平均边长 {L.mean():.3f}, 最长边 {L.max():.3f}")

# ======== 3. 层次风险平价 HRP（López de Prado） ========
def hrp_weights(cov, corr):
    dist = np.sqrt(np.clip(0.5*(1 - corr), 0, None)); np.fill_diagonal(dist, 0)
    Z = linkage(squareform(dist, checks=False), method="single")  # 第一步：单链接 = MST
    order = list(leaves_list(Z))                                  # 第二步：准对角化
    w = np.ones(len(cov))
    def cluster_var(idx):
        c = cov[np.ix_(idx, idx)]; ivp = 1/np.diag(c); ivp /= ivp.sum()
        return ivp @ c @ ivp
    stack = [order]
    while stack:                                                  # 第三步：递归二分
        items = stack.pop()
        if len(items) < 2: continue
        L, Rr = items[:len(items)//2], items[len(items)//2:]
        vL, vR = cluster_var(L), cluster_var(Rr)
        a = 1 - vL/(vL + vR)                                      # 方差小的一半分得多
        w[L] *= a; w[Rr] *= 1 - a
        stack += [L, Rr]
    return w / w.sum(), order

def cov_homog(seed=99, n_sec=3, ind_per_sec=3, per_ind=10):
    # 情形 A：与 simulate 相同的"市场+板块+行业"结构，各组规模相同
    K = n_sec*ind_per_sec; N = K*per_ind
    ind = np.repeat(np.arange(K), per_ind); sec = ind // ind_per_sec
    idio = np.random.default_rng(seed).uniform(0.008, 0.025, N)
    return 0.008**2 + 0.006**2*(sec[:, None] == sec[None, :]) \
           + 0.006**2*(ind[:, None] == ind[None, :]) + np.diag(idio**2)

def cov_hetero(seed=99, sizes=(40, 20, 10, 5, 5), rho_in=(0.7, 0.5, 0.4, 0.3, 0.3),
               vol_cl=(0.02, 0.015, 0.012, 0.01, 0.008), rho_out=0.15):
    # 情形 B：一个 40 只的高相关大簇（如同一行业扎堆）+ 若干小簇
    lab = np.repeat(np.arange(len(sizes)), sizes); N = len(lab)
    Cr = np.full((N, N), rho_out)
    for k_, r_ in enumerate(rho_in): Cr[np.ix_(lab == k_, lab == k_)] = r_
    np.fill_diagonal(Cr, 1)
    vol = np.array(vol_cl)[lab] * np.random.default_rng(seed).uniform(0.8, 1.2, N)
    return Cr * np.outer(vol, vol)

rng = np.random.default_rng(2024)
for case, Sig in [("A 同质结构", cov_homog()), ("B 异质簇结构", cov_hetero())]:
    N = len(Sig); Lc = np.linalg.cholesky(Sig)
    res = {"等权": [], "逆方差 IVP": [], "样本最小方差 MV": [], "HRP": []}
    for trial in range(200):
        X = rng.standard_normal((120, N)) @ Lc.T       # 只用 120 天样本估计 N×N 协方差
        S = np.cov(X.T); Cs = np.corrcoef(X.T)
        w_eq = np.ones(N)/N
        w_ivp = 1/np.diag(S); w_ivp /= w_ivp.sum()
        Si = np.linalg.pinv(S); w_mv = Si @ np.ones(N); w_mv /= w_mv.sum()
        w_hrp, order = hrp_weights(S, Cs)
        for k_, w in zip(res, [w_eq, w_ivp, w_mv, w_hrp]):
            res[k_].append(np.sqrt(w @ Sig @ w * 252))    # 用真实协方差评价样本外波动
    w_opt = np.linalg.solve(Sig, np.ones(N)); w_opt /= w_opt.sum()
    print(f"\n[{case}] N={N}, 真实最小方差组合年化波动(理论下限) {np.sqrt(w_opt @ Sig @ w_opt*252):.4f}")
    for k_, v in res.items():
        print(f"  {k_:12s} 样本外年化波动 均值 {np.mean(v):.4f}  标准差 {np.std(v):.4f}")
    print(f"  最后一次 HRP 权重范围 {w_hrp.min():.4f} ~ {w_hrp.max():.4f} | "
          f"MV 负权重个数 {(w_mv < 0).sum()}")

运行输出：

Kruskal: gh:1 ci:2 fg:2 ab:4 cf:4 cd:7 ah:8 de:9 | 总权 37
Prim   : ab:4 bc:8 ci:2 cf:4 fg:2 gh:1 cd:7 de:9 | 总权 37

N=90: 自写 Prim 总长 86.417382 | scipy 总长 86.417382
度数最高的 5 只股票(所属行业): [(37, 3, 7), (55, 5, 6), (4, 0, 6), (43, 4, 5), (79, 7, 4)]
MST 中同行业边的比例: 0.91
MST 断边聚类 与 单链接 maxclust 一致: True | 与真实行业 ARI=1.000
Kruskal 合并高度 == 单链接 Z 的合并高度: True
平静期: 市场波动 0.006, MST 平均边长 1.042, 最长边 1.180
危机期: 市场波动 0.025, MST 平均边长 0.596, 最长边 0.664

[A 同质结构] N=90, 真实最小方差组合年化波动(理论下限) 0.1442
  等权           样本外年化波动 均值 0.1449  标准差 0.0000
  逆方差 IVP      样本外年化波动 均值 0.1444  标准差 0.0000
  样本最小方差 MV    样本外年化波动 均值 0.2891  标准差 0.0348
  HRP          样本外年化波动 均值 0.1452  标准差 0.0002
  最后一次 HRP 权重范围 0.0047 ~ 0.0235 | MV 负权重个数 45

[B 异质簇结构] N=80, 真实最小方差组合年化波动(理论下限) 0.0691
  等权           样本外年化波动 均值 0.1606  标准差 0.0000
  逆方差 IVP      样本外年化波动 均值 0.1119  标准差 0.0026
  样本最小方差 MV    样本外年化波动 均值 0.1191  标准差 0.0113
  HRP          样本外年化波动 均值 0.0920  标准差 0.0028
  最后一次 HRP 权重范围 0.0011 ~ 0.0870 | MV 负权重个数 41

23.6.5 结果解读

算法验证。 两种算法在图 23.1 上都得到总权 37 的 MST。Kruskal 选了 (a,h)，Prim 选了 (b,c)，正是原书说的两棵不同的 MST，权重相同。

相关性 MST。 自写的 \(O(V^2)\) Prim 与 scipy 的总长度完全一致。MST 的 89 条边中 91% 连接同行业股票，度数最高的几只股票分散在不同行业，各自充当本行业的枢纽。切掉最长的 8 条边得到的 9 类，与 scipy 单链接 maxclust=9 的结果完全相同，并且与真实的 9 个行业完全吻合（ARI=1.000）；MST 的边权排序后与单链接的合并高度逐一相等。这三个"一致"正是 23.6.2 的三条等价关系。

危机期的树收缩。 市场因子波动从 0.006 放大到 0.025 时，所有股票的相关性被市场因子抬高，MST 平均边长从 1.04 缩到 0.60，最长边从 1.18 缩到 0.66。实证文献中观察到的危机期 MST "收缩"就是这个机制。MST 平均边长（或者总长）因此可以作为一个市场联动程度的监控指标。

HRP 的两种情形。

  • 情形 A（同质结构）：9 个行业规模相同、因子载荷相同。这时等权和逆方差组合已经非常接近真实最小方差组合（0.1449、0.1444 对理论下限 0.1442），HRP（0.1452）没有额外好处，只是略差一点点。用 120 天样本估计 90×90 协方差再求逆的样本最小方差组合，样本外波动高达 0.289，是理论下限的两倍，而且一半的权重是负的——这就是"估计误差最大化"。
  • 情形 B（异质簇结构）：有一个 40 只股票、组内相关 0.7 的大簇，加上几个小簇。等权组合把一半权重压在这个大簇上，波动 0.161；逆方差组合 0.112；样本最小方差 0.119 且仍有 41 个负权重；HRP 为 0.092，四者中最低，且权重全为正、范围合理（0.001 到 0.087）。HRP 的优势来自树的上层把大簇当作一个整体分配风险。

两种情形对照起来，结论是：HRP 的价值取决于资产之间有没有明显的层次结构；在有结构时它稳健地优于简单的风险分配方法和样本最小方差，在没有结构时它不会带来坏处，但也不会带来好处。这里用真实协方差评价，只衡量了"估计误差导致的损失"；在真实数据上回测，还要考虑结构随时间漂移、换手率和交易成本。真实的理论下限 0.069 与 HRP 的 0.092 之间仍有差距，用收缩估计（Ledoit–Wolf）或因子模型改进协方差估计，可以进一步缩小差距。

本章小结

最小生成树是连通无向带权图中总权重最小的生成树，恰有 \(|V|-1\) 条边，不一定唯一，但所有 MST 的边权多重集相同。核心工具是切割性质——尊重 \(A\) 的切割上的轻量级边对 \(A\) 安全，用剪切粘贴法证明；配套的环性质说环上最重的边可以排除。Kruskal 按边权从小到大加边，用并查集避免成环，\(O(E\lg V)\)，瓶颈在排序；Prim 从一个根生长一棵树，用最小优先队列选边，二叉堆 \(O(E\lg V)\)、斐波那契堆 \(O(E+V\lg V)\)、邻接矩阵 \(O(V^2)\)，后者最适合完全图。在量化中，相关性距离 \(\sqrt{2(1-\rho)}\) 上的 MST 给出市场的层次骨架；Kruskal 的过程就是单链接聚类，MST 路径上的最大边就是单链接距离；HRP 用单链接树重排协方差矩阵，再按风险递归二分配权，不求逆、权重为正，在资产有层次结构时明显优于样本最小方差和简单的风险分配方法。

概念 / 算法 公式 / 复杂度 要点
MST \(\min_T w(T)=\sum_{(u,v)\in T}w(u,v)\) \(\lvert V\rvert-1\) 条边；边权多重集唯一
切割性质 尊重 \(A\) 的切割上的轻量级边对 \(A\) 安全 剪切粘贴：\(w(T')=w(T)-w(x,y)+w(u,v)\le w(T)\)
环性质 环上最重的边可删去 反向删除算法的依据
Kruskal \(O(E\lg V)\)（排序为瓶颈） 并查集判环；加边顺序 = 单链接合并顺序
Prim 二叉堆 \(O(E\lg V)\)；斐波那契堆 \(O(E+V\lg V)\)；矩阵 \(O(V^2)\) 与 Dijkstra 同构；稠密图用矩阵版
Mantegna 距离 \(d_{ij}=\sqrt{2(1-\rho_{ij})}=\lVert z_i-z_j\rVert\) 真正的度量；单调变换不改变 MST
单链接距离 MST 路径上的最大边 次优超度量；minimax 路径
HRP 树聚类 → 准对角化 → 递归二分，\(\alpha=1-\frac{V_1}{V_1+V_2}\) 不求逆、权重为正；有层次结构时优势明显

练习

基础

  1. 证明全图权重最小的边一定属于某棵 MST。（原书 23.1-1。）
  2. 证明环性质：若 \(e\) 是某个环上权重最大的边，则 \(G-e\) 有一棵 MST 也是 \(G\) 的 MST。（原书 23.1-5。）
  3. 证明：若每个切割的轻量级边都唯一，则 MST 唯一；举例说明逆命题不成立。（原书 23.1-6。）
  4. 写出邻接矩阵上 \(O(V^2)\) 的 Prim 算法。（原书 23.2-2。提示：本章代码中的 prim_dense。）
  5. 已知一棵 MST，把某条树边的权重降低，原树还是 MST 吗？把某条非树边的权重降低，如何在 \(O(V)\) 时间内更新 MST？（原书 23.1-10、23.1-11。）

进阶

  1. 证明同一个图的所有 MST 的边权排序列表都相同。（原书 23.1-8。）由此说明：单链接聚类的合并高度序列与平局如何打破无关。
  2. 说明 Borden 教授的分治算法（把顶点分成两半，分别递归求 MST，再用一条最轻的横跨边连起来）为什么是错的，给出反例。（原书 23.2-8。）
  3. 思考题 23-1：在 \(O(V^2)\) 时间内求次优 MST。在相关性网络中，"次优 MST 与 MST 的权重差"能说明什么？（提示：差很小说明树的结构对噪声敏感。）
  4. 思考题 23-3：证明 MST 是瓶颈生成树，并证明 MST 上任意两点路径的最大边等于所有连接这两点的路径中最大边的最小值。用 23.6.4 的代码数值验证：对随机两只股票，比较 MST 路径最大边与 scipy.cluster.hierarchy.cophenet 给出的单链接共表距离。
  5. 修改 23.6.4 的 HRP：(a) 把第一步改为平均链接或 Ward 法，比较情形 B 下的样本外波动；(b) 把第三步改为沿聚类树的真实分叉二分，而不是按列表长度对半切；(c) 把样本协方差换成 Ledoit–Wolf 收缩估计（sklearn.covariance.LedoitWolf），再与最小方差组合比较。总结每个改动的效果。

原书推荐习题：23.1-5、23.1-6、23.1-8、23.1-11、23.2-2、23.2-3、23.2-8，思考题 23-1、23-3、23-4。

原书对照

本章小节 原书章节 PDF 页码
23.1 问题 23 导言 p.645–646
23.2 通用方法与切割性质 23.1 Growing a minimum spanning tree p.646–651
23.3–23.4 Kruskal 与 Prim 算法 23.2 The algorithms of Kruskal and Prim p.652–659
23.5 思考题与注记 Problems 23-1 ～ 23-4、Chapter notes p.659–663
23.6 量化实战 原书无，本册补充（Mantegna 1999；López de Prado 2016） —