EyeBlogs
Investment4 phút đọcNâng cao

Minimum Spanning Tree: Từ lý thuyết đồ thị đến thị trường chứng khoán

Biến ma trận tương quan của hàng trăm cổ phiếu thành một cây duy nhất — và vì sao khoảng cách √(2(1−ρ)) là lựa chọn tự nhiên.

Tác giả: EyeBlogs
Mục lục

Với 300 cổ phiếu, ma trận tương quan có gần 45.000 cặp giá trị. Không ai đọc nổi chừng đó con số. Năm 1999, Rosario Mantegna đề xuất một ý tưởng đơn giản mà mạnh mẽ: coi mỗi cổ phiếu là một đỉnh của đồ thị, biến tương quan thành khoảng cách, rồi chỉ giữ lại cây khung nhỏ nhất (minimum spanning tree — MST)[1]. Kết quả là một cấu trúc chỉ có N−1N - 1 cạnh nhưng vẫn phản ánh rõ các cụm ngành.

Từ giá đến tương quan

Gọi Pi(t)P_i(t) là giá đóng cửa của cổ phiếu ii tại phiên tt. Ta làm việc với log return thay vì giá:

ri(t)=ln⁡Pi(t)−ln⁡Pi(t−1)r_i(t) = \ln P_i(t) - \ln P_i(t-1)

Hệ số tương quan Pearson giữa hai cổ phiếu ii và jj trên một cửa sổ thời gian:

ρij=⟨rirj⟩−⟨ri⟩⟨rj⟩(⟨ri2⟩−⟨ri⟩2)(⟨rj2⟩−⟨rj⟩2)\rho_{ij} = \frac{\langle r_i r_j \rangle - \langle r_i \rangle \langle r_j \rangle} {\sqrt{\left(\langle r_i^2 \rangle - \langle r_i \rangle^2\right)\left(\langle r_j^2 \rangle - \langle r_j \rangle^2\right)}}

trong đó ⟨⋅⟩\langle \cdot \rangle là trung bình theo thời gian. Ta có ρij∈[−1,1]\rho_{ij} \in [-1, 1].

Biến tương quan thành khoảng cách

Tương quan không phải là một khoảng cách: nó không thoả bất đẳng thức tam giác, và “gần nhau” lại tương ứng với giá trị lớn. Mantegna dùng phép biến đổi:

dij=2(1−ρij)d_{ij} = \sqrt{2\left(1 - \rho_{ij}\right)}

Khi đó dij∈[0,2]d_{ij} \in [0, 2]: hai cổ phiếu tương quan hoàn hảo có dij=0d_{ij} = 0, hai cổ phiếu ngược chiều hoàn toàn có dij=2d_{ij} = 2.

Vì sao lại là căn bậc hai?

Chuẩn hoá chuỗi return của mỗi cổ phiếu thành vector r~i\tilde{r}_i có trung bình 0 và độ dài 1. Khi đó tích vô hướng chính là tương quan, r~i⋅r~j=ρij\tilde{r}_i \cdot \tilde{r}_j = \rho_{ij}, và:

∥r~i−r~j∥2=∥r~i∥2+∥r~j∥2−2 r~i⋅r~j=2(1−ρij)\lVert \tilde{r}_i - \tilde{r}_j \rVert^2 = \lVert \tilde{r}_i \rVert^2 + \lVert \tilde{r}_j \rVert^2 - 2\,\tilde{r}_i \cdot \tilde{r}_j = 2\left(1 - \rho_{ij}\right)

Nói cách khác, dijd_{ij} chính là khoảng cách Euclid giữa hai vector đã chuẩn hoá. Vì vậy nó tự động thoả mọi tiên đề của một metric, kể cả bất đẳng thức tam giác dij≤dik+dkjd_{ij} \le d_{ik} + d_{kj}.

Cây khung nhỏ nhất

Cho đồ thị vô hướng liên thông G=(V,E)G = (V, E) với trọng số w:E→Rw: E \to \mathbb{R}. Một cây khung là tập T⊆ET \subseteq E gồm ∣V∣−1|V| - 1 cạnh nối mọi đỉnh mà không tạo chu trình. MST là cây khung có tổng trọng số nhỏ nhất:

T∗=arg⁡min⁡T∑(i,j)∈TwijT^{*} = \arg\min_{T} \sum_{(i,j) \in T} w_{ij}

Cả hai thuật toán kinh điển đều dựa trên tính chất lát cắt (cut property): với mọi cách chia VV thành hai phần, cạnh nhẹ nhất bắc qua lát cắt luôn thuộc một MST nào đó[4].

Tiêu chí Kruskal (1956)[2] Prim (1957)[3]
Ý tưởng Duyệt cạnh từ nhẹ đến nặng, bỏ cạnh tạo chu trình Mở rộng dần một cây từ một đỉnh gốc
Cấu trúc dữ liệu chính Union-Find (disjoint set) Priority queue
Độ phức tạp O(Elog⁡E)O(E \log E) O(Elog⁡V)O(E \log V) với binary heap
Phù hợp Đồ thị thưa, cạnh đã có sẵn dạng danh sách Đồ thị dày

Với ma trận tương quan, đồ thị là đầy đủ: E=N(N−1)/2E = N(N-1)/2. Với vài trăm cổ phiếu, cả hai đều chạy trong tích tắc.

Cài đặt bằng Python

Đoạn code dưới đây cài Kruskal với Union-Find, không phụ thuộc thư viện đồ thị nào. Đầu vào là DataFrame giá đóng cửa, mỗi cột là một mã cổ phiếu.

market_mst.py
import numpy as np
import pandas as pd




def correlation_distance(prices: pd.DataFrame) -> pd.DataFrame:
    """Ma trận khoảng cách d_ij = sqrt(2(1 - rho_ij)) từ giá đóng cửa."""
    log_returns = np.log(prices).diff().dropna()
    rho = log_returns.corr()
    # clip trước khi lấy căn: sai số dấu phẩy động có thể làm 1 - rho hơi âm (=> NaN)
    return np.sqrt((2 * (1 - rho)).clip(lower=0))




class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))


    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x


    def union(self, a: int, b: int) -> bool:
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False  # a và b đã cùng cây => thêm cạnh sẽ tạo chu trình
        self.parent[root_b] = root_a
        return True




def kruskal_mst(dist: pd.DataFrame) -> list[tuple[str, str, float]]:
    names = list(dist.columns)
    n = len(names)
    # Lấy tam giác trên của ma trận => danh sách cạnh (vectorized, không dùng vòng lặp lồng nhau)
    i, j = np.triu_indices(n, k=1)
    weights = dist.to_numpy()[i, j]
    order = np.argsort(weights, kind="stable")


    uf = UnionFind(n)
    edges = []
    for k in order:
        if uf.union(i[k], j[k]):
            edges.append((names[i[k]], names[j[k]], float(weights[k])))
            if len(edges) == n - 1:
                break
    return edges
Cạnh trong MST ρij\rho_{ij} dijd_{ij}
BANK_A — BANK_B 0.82 0.600
BANK_B — BANK_C 0.76 0.693
BANK_A — STEEL_A 0.55 0.949
STEEL_A — TECH_A 0.41 1.086

Các ngân hàng tụ lại thành một nhánh với khoảng cách nhỏ; các ngành khác nối vào qua những cạnh dài hơn. Trên dữ liệu thật, cấu trúc cụm ngành này là quan sát nổi bật nhất trong nghiên cứu gốc của Mantegna[1].

Hình 1. MST của thị trường: các cụm ngành hiện ra mà không cần gán nhãn trước. (Diagram placeholder)

Những điểm cần cẩn trọng

  • Cửa sổ thời gian: tương quan thay đổi theo chế độ thị trường. MST tính trên 3 tháng khủng hoảng có thể rất khác MST trên 3 năm.
  • Độ ổn định: với TT phiên và NN cổ phiếu, khi N/TN/T không nhỏ, ma trận tương quan mẫu chứa nhiều nhiễu. Nên thử lại MST trên các cửa sổ con để xem cạnh nào ổn định.
  • MST loại bỏ thông tin: từ N(N−1)/2N(N-1)/2 cạnh chỉ giữ lại N−1N - 1. Nó tốt cho việc nhìn cấu trúc, không thay thế được toàn bộ ma trận tương quan khi tính rủi ro danh mục.

Tài liệu tham khảo

  1. [1]Rosario N. Mantegna. Hierarchical structure in financial markets. The European Physical Journal B, 11, 193–197, 1999.
  2. [2]Joseph B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48–50, 1956.
  3. [3]Robert C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6), 1389–1401, 1957.
  4. [4]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (4th edition). MIT Press, 2022. Chương 21 — Minimum Spanning Trees.